Skip to content

GH-101291: Rearrange the size bits in PyLongObject #102464

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
markshannon merged 37 commits into from
Mar 22, 2023
Merged

GH-101291: Rearrange the size bits in PyLongObject #102464

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
37 commits
Select commit Hold shift + click to select a range
0ec07e4
Add functions to hide some internals of long object.
markshannon Jan 25, 2023
292b9d0
Add internal functions to longobject.c for setting sign and digit count.
markshannon Jan 25, 2023
5c54894
Replace Py_SIZE(x) < 0 with _PyLong_IsNegative(x) in longobject.c
markshannon Feb 28, 2023
029aaa4
Replace Py_ABS(Py_SIZE(a)) with _PyLong_DigitCount(a) in longobject.c
markshannon Feb 28, 2023
b56e6da
Remove many uses of Py_SIZE in longobject.c
markshannon Feb 28, 2023
91269fc
Remove _PyLong_AssignValue, as it is no longer used.
markshannon Feb 28, 2023
c48e825
Remove some more uses of Py_SIZE in longobject.c.
markshannon Feb 28, 2023
449c0e2
Remove a few more uses of Py_SIZE in longobject.c.
markshannon Mar 1, 2023
c5ba601
Remove some more uses of Py_SIZE, replacing with _PyLong_UnsignedDigi…
markshannon Mar 1, 2023
4b3a3e8
Replace a few Py_SIZE() with _PyLong_SameSign().
markshannon Mar 1, 2023
9ef9d2c
Remove a few more Py_SIZE() from longobject.c
markshannon Mar 1, 2023
9c408c1
Replace uses of IS_MEDIUM_VALUE macro with _PyLong_IsSingleDigit.
markshannon Mar 1, 2023
548d656
Remove most of the remaining uses of Py_SIZE in longobject.c
markshannon Mar 1, 2023
3e3fefd
Replace last remaining uses of Py_SIZE applied to longobject with _Py…
markshannon Mar 1, 2023
391fb51
Don't use _PyObject_InitVar and move a couple of inline functions to …
markshannon Mar 1, 2023
df8c7d3
Correct name of inline function.
markshannon Mar 1, 2023
bc14fa6
Eliminate all remaining uses of Py_SIZE and Py_SET_SIZE on PyLongObject.
markshannon Mar 1, 2023
54c6f1b
Change layout of size/sign bits in longobject to support future addit…
markshannon Mar 2, 2023
ce6bfb2
Test pairs of longs together on fast path of add/mul/sub.
markshannon Mar 2, 2023
4c1956b
Tidy up comment and delete commented out code.
markshannon Mar 6, 2023
301158b
Add news.
markshannon Mar 6, 2023
1aa1891
Remove debugging asserts.
markshannon Mar 6, 2023
bf2a9af
Fix storage classes.
markshannon Mar 6, 2023
169f521
Remove development debug functions.
markshannon Mar 6, 2023
90f9072
Avoid casting to smaller int.
markshannon Mar 8, 2023
f143443
Apply suggestions from code review.
markshannon Mar 8, 2023
a0d661e
Widen types to avoid data loss.
markshannon Mar 8, 2023
145a2e4
Fix syntax error.
markshannon Mar 8, 2023
638a98f
Replace 'SingleDigit' with 'Compact' as the term 'single digit' seems…
markshannon Mar 9, 2023
7f5acc0
Address review comments.
markshannon Mar 16, 2023
b06bb6f
Merge branch 'main' into long-rearrange-size-bits
markshannon Mar 16, 2023
a19b0a7
Merge branch 'main' into long-rearrange-size-bits
markshannon Mar 16, 2023
87f49b2
Fix _PyLong_Sign
markshannon Mar 16, 2023
f764aa8
Replace _PyLong_Sign(x) < 0 with _PyLong_IsNegative(x).
markshannon Mar 16, 2023
9843ac0
fix sign check
markshannon Mar 16, 2023
d6cb917
Address some review comments.
markshannon Mar 22, 2023
469d26f
Change asserts on digit counts to asserts on sign where applicable.
markshannon Mar 22, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Remove many uses of Py_SIZE in longobject.c
  • Loading branch information
@markshannon
markshannon committed Feb 28, 2023
commit b56e6da6355bfafbfdacf52425c4202f64fb6cc9
2 changes: 1 addition & 1 deletion Include/cpython/longintrepr.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -95,7 +95,7 @@ PyAPI_FUNC(PyLongObject *) _PyLong_New(Py_ssize_t);
PyAPI_FUNC(PyObject *) _PyLong_Copy(PyLongObject *src);

PyAPI_FUNC(PyLongObject *)
_PyLong_FromDigits(int sign, Py_ssize_t digit_count, digit *digits);
_PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits);


#ifdef __cplusplus
Expand Down
13 changes: 10 additions & 3 deletions Include/internal/pycore_long.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -112,7 +112,7 @@ PyAPI_FUNC(char*) _PyLong_FormatBytesWriter(

/* Return 1 if the argument is positive single digit int */
static inline int
_PyLong_IsPositiveSingleDigit(const PyObject* op) {
_PyLong_IsPositiveSingleDigit(const PyLongObject* op) {
/* For a positive single digit int, the value of Py_SIZE(sub) is 0 or 1.

We perform a fast check using a single comparison by casting from int
Expand All @@ -131,7 +131,7 @@ _PyLong_IsPositiveSingleDigit(const PyObject* op) {


static inline int
_PyLong_IsSingleDigit(const PyObject* op) {
_PyLong_IsSingleDigit(const PyLongObject* op) {
assert(PyLong_Check(op));
Py_ssize_t signed_size = Py_SIZE(op);
return ((size_t)(signed_size+1)) <= 2;
Expand All @@ -152,7 +152,6 @@ _PyLong_DigitCount(const PyLongObject *op)
return Py_ABS(Py_SIZE(op));
}


static inline bool
_PyLong_IsNegative(const PyLongObject *op)
{
Expand All @@ -166,6 +165,14 @@ _PyLong_IsZero(const PyLongObject *op)
return Py_SIZE(op) == 0;
}

Comment on lines +196 to +203
Copy link
Copy Markdown
Contributor

@lpereira lpereira Mar 21, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Shouldn't this be the new implementation of _PyLong_Sign(), if _PyLong_NonCompactSign() is removed? This gets rid of a branch in the proposed version of _PyLong_Sign().

Copy link
Copy Markdown
Member

@gvanrossum gvanrossum Mar 21, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

They sure look identical to me. Maybe Mark has plans and maybe the compiler would optimize this anyway?

if (P(x))
  return F(x);
else
  return F(x);

could just become return F(x);.

Copy link
Copy Markdown
Member Author

@markshannon markshannon Mar 22, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We want the freedom to implement the "compact" and non-compact forms differently.
They have the same implementation at the moment, but that will change.

_PyLong_Sign() is part of the ABI, so we need to retain it. But almost all code using _PyLong_Sign() actually wants to know if an int is negative and should be using _PyLong_IsNegative().

static inline int
_PyLong_NonZeroSign(const PyLongObject *op)
Copy link
Copy Markdown
Member

@gvanrossum gvanrossum Mar 17, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The name confused me -- why not just _PyLong_Sign?

Copy link
Copy Markdown
Member Author

@markshannon markshannon Mar 20, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Because it shouldn't be called with 0.

It probably should be called on compact ints either. I'll check if it is, and rename it.

Copy link
Copy Markdown
Member Author

@markshannon markshannon Mar 20, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've renamed it to _PyLong_NonCompactSign which will make implementing tagged ints easier.

{
assert(PyLong_Check(op));
assert(!_PyLong_IsZero(op));
return ((Py_SIZE(op) > 0) << 1) - 1;
}

static inline bool
_PyLong_IsPositive(const PyLongObject *op)
{
Expand Down
4 changes: 2 additions & 2 deletions Modules/_decimal/_decimal.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2160,7 +2160,7 @@ dec_from_long(PyTypeObject *type, PyObject *v,

uint8_t sign = _PyLong_IsNegative(l) ? MPD_NEG : MPD_POS;

if (_PyLong_IsSingleDigit((PyObject *)l)) {
if (_PyLong_IsSingleDigit(l)) {
_dec_settriple(dec, sign, l->long_value.ob_digit[0], 0);
mpd_qfinalize(MPD(dec), ctx, status);
return dec;
Expand Down Expand Up @@ -3527,7 +3527,7 @@ dec_as_long(PyObject *dec, PyObject *context, int round)

assert(n > 0);
assert(!mpd_iszero(x));
pylong = _PyLong_FromDigits(mpd_isnegative(x) ? -1 : 1, n, ob_digit);
pylong = _PyLong_FromDigits(mpd_isnegative(x), n, ob_digit);
mpd_free(ob_digit);
mpd_del(x);
return (PyObject *) pylong;
Expand Down
6 changes: 3 additions & 3 deletions Objects/listobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2150,8 +2150,8 @@ unsafe_long_compare(PyObject *v, PyObject *w, MergeState *ms)
/* Modified from Objects/longobject.c:long_compare, assuming: */
assert(Py_IS_TYPE(v, &PyLong_Type));
assert(Py_IS_TYPE(w, &PyLong_Type));
assert(_PyLong_IsSingleDigit(v));
assert(_PyLong_IsSingleDigit(w));
assert(_PyLong_IsSingleDigit((PyLongObject *)v));
assert(_PyLong_IsSingleDigit((PyLongObject *)w));

vl = (PyLongObject*)v;
wl = (PyLongObject*)w;
Expand Down Expand Up @@ -2355,7 +2355,7 @@ list_sort_impl(PyListObject *self, PyObject *keyfunc, int reverse)
if (keys_are_all_same_type) {
if (key_type == &PyLong_Type &&
ints_are_bounded &&
!_PyLong_IsSingleDigit(key)) {
!_PyLong_IsSingleDigit((PyLongObject *)key)) {

ints_are_bounded = 0;
}
Expand Down
94 changes: 31 additions & 63 deletions Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -184,15 +184,15 @@ _PyLong_New(Py_ssize_t size)
}

PyLongObject *
_PyLong_FromDigits(int sign, Py_ssize_t digit_count, digit *digits)
_PyLong_FromDigits(int negative, Py_ssize_t digit_count, digit *digits)
{
assert(digit_count >= 0);
PyLongObject *result = _PyLong_New(digit_count);
if (result == NULL) {
PyErr_NoMemory();
return NULL;
}
assert(sign >= -1 && sign <= 1);
int sign = negative ? -1 : 1;
result->long_value.ob_size = sign * digit_count;
memcpy(result->long_value.ob_digit, digits, digit_count * sizeof(digit));
return result;
Expand All @@ -201,22 +201,16 @@ _PyLong_FromDigits(int sign, Py_ssize_t digit_count, digit *digits)
PyObject *
_PyLong_Copy(PyLongObject *src)
{
Py_ssize_t i;

assert(src != NULL);
i = Py_SIZE(src);
int sign = 1;
if (i < 0) {
i = -i;
sign = -1;
}
if (i < 2) {

if (_PyLong_IsSingleDigit(src)) {
stwodigits ival = medium_value(src);
if (IS_SMALL_INT(ival)) {
return get_small_int((sdigit)ival);
}
}
return (PyObject *)_PyLong_FromDigits(sign, i, src->long_value.ob_digit);
int size = _PyLong_DigitCount(src);
return (PyObject *)_PyLong_FromDigits(_PyLong_IsNegative(src), size, src->long_value.ob_digit);
}

static PyObject *
Expand Down Expand Up @@ -300,7 +294,7 @@ _PyLong_AssignValue(PyObject **target, Py_ssize_t value)
return 0;
}
else if (old != NULL && PyLong_CheckExact(old) &&
Py_REFCNT(old) == 1 && _PyLong_IsPositiveSingleDigit(old) &&
Py_REFCNT(old) == 1 && _PyLong_IsPositiveSingleDigit((PyLongObject *)old) &&
(size_t)value <= PyLong_MASK)
{
// Mutate in place if there are no other references the old
Expand Down Expand Up @@ -533,27 +527,14 @@ PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
return -1;
do_decref = 1;
}

res = -1;
i = Py_SIZE(v);

switch (i) {
case -1:
res = -(sdigit)v->long_value.ob_digit[0];
break;
case 0:
res = 0;
break;
case 1:
res = v->long_value.ob_digit[0];
break;
default:
sign = 1;
if (_PyLong_IsSingleDigit(v)) {
res = _PyLong_SingleDigitValue(v);
}
else {
res = -1;
i = _PyLong_DigitCount(v);
sign = _PyLong_NonZeroSign(v);
x = 0;
if (i < 0) {
sign = -1;
i = -(i);
}
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
Expand All @@ -563,8 +544,8 @@ PyLong_AsLongAndOverflow(PyObject *vv, int *overflow)
}
}
/* Haven't lost any bits, but casting to long requires extra
* care (see comment above).
*/
* care (see comment above).
*/
Copy link
Copy Markdown
Member

@gvanrossum gvanrossum Mar 21, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Accidental reformat?

Suggested change
* care (see comment above).
*/
* care (see comment above).
*/

Copy link
Copy Markdown
Member Author

@markshannon markshannon Mar 22, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

if (x <= (unsigned long)LONG_MAX) {
res = (long)x * sign;
}
Expand Down Expand Up @@ -638,18 +619,12 @@ PyLong_AsSsize_t(PyObject *vv) {
}

v = (PyLongObject *)vv;
i = Py_SIZE(v);
switch (i) {
case -1: return -(sdigit)v->long_value.ob_digit[0];
case 0: return 0;
case 1: return v->long_value.ob_digit[0];
if (_PyLong_IsSingleDigit(v)) {
return _PyLong_SingleDigitValue(v);
}
sign = 1;
i = _PyLong_DigitCount(v);
sign = _PyLong_NonZeroSign(v);
x = 0;
if (i < 0) {
sign = -1;
i = -(i);
}
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
Expand Down Expand Up @@ -737,17 +712,16 @@ PyLong_AsSize_t(PyObject *vv)
}

v = (PyLongObject *)vv;
i = Py_SIZE(v);
x = 0;
if (i < 0) {
if (_PyLong_IsPositiveSingleDigit(v)) {
return _PyLong_SingleDigitValue(v);
}
if (_PyLong_IsNegative(v)) {
PyErr_SetString(PyExc_OverflowError,
"can't convert negative value to size_t");
return (size_t) -1;
}
switch (i) {
case 0: return 0;
case 1: return v->long_value.ob_digit[0];
}
i = _PyLong_DigitCount(v);
x = 0;
while (--i >= 0) {
prev = x;
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
Expand All @@ -769,24 +743,18 @@ _PyLong_AsUnsignedLongMask(PyObject *vv)
PyLongObject *v;
unsigned long x;
Py_ssize_t i;
int sign;

if (vv == NULL || !PyLong_Check(vv)) {
PyErr_BadInternalCall();
return (unsigned long) -1;
}
v = (PyLongObject *)vv;
i = Py_SIZE(v);
switch (i) {
case 0: return 0;
case 1: return v->long_value.ob_digit[0];
if (_PyLong_IsPositiveSingleDigit(v)) {
return _PyLong_SingleDigitValue(v);
}
sign = 1;
i = _PyLong_DigitCount(v);
int sign = _PyLong_NonZeroSign(v);
x = 0;
if (i < 0) {
sign = -1;
i = -i;
}
while (--i >= 0) {
x = (x << PyLong_SHIFT) | v->long_value.ob_digit[i];
}
Expand Down Expand Up @@ -4696,7 +4664,7 @@ long_pow(PyObject *v, PyObject *w, PyObject *x)

/* if modulus == 1:
return 0 */
if (_PyLong_IsPositiveSingleDigit((PyObject *)c) && (c->long_value.ob_digit[0] == 1)) {
if (_PyLong_IsPositiveSingleDigit(c) && (c->long_value.ob_digit[0] == 1)) {
z = (PyLongObject *)PyLong_FromLong(0L);
goto Done;
}
Expand Down
2 changes: 1 addition & 1 deletion Python/bltinmodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2507,7 +2507,7 @@ builtin_sum_impl(PyObject *module, PyObject *iterable, PyObject *start)
long b;
overflow = 0;
/* Single digits are common, fast, and cannot overflow on unpacking. */
if (_PyLong_IsSingleDigit(item)) {
if (_PyLong_IsSingleDigit((PyLongObject *)item)) {
b = _PyLong_SingleDigitValue((PyLongObject *)item);
}
else {
Expand Down
10 changes: 5 additions & 5 deletions Python/bytecodes.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -356,7 +356,7 @@ dummy_func(
DEOPT_IF(!PyList_CheckExact(list), BINARY_SUBSCR);

// Deopt unless 0 <= sub < PyList_Size(list)
DEOPT_IF(!_PyLong_IsPositiveSingleDigit(sub), BINARY_SUBSCR);
DEOPT_IF(!_PyLong_IsPositiveSingleDigit((PyLongObject *)sub), BINARY_SUBSCR);
Py_ssize_t index = ((PyLongObject*)sub)->long_value.ob_digit[0];
DEOPT_IF(index >= PyList_GET_SIZE(list), BINARY_SUBSCR);
STAT_INC(BINARY_SUBSCR, hit);
Expand All @@ -373,7 +373,7 @@ dummy_func(
DEOPT_IF(!PyTuple_CheckExact(tuple), BINARY_SUBSCR);

// Deopt unless 0 <= sub < PyTuple_Size(list)
DEOPT_IF(!_PyLong_IsPositiveSingleDigit(sub), BINARY_SUBSCR);
DEOPT_IF(!_PyLong_IsPositiveSingleDigit((PyLongObject *)sub), BINARY_SUBSCR);
Py_ssize_t index = ((PyLongObject*)sub)->long_value.ob_digit[0];
DEOPT_IF(index >= PyTuple_GET_SIZE(tuple), BINARY_SUBSCR);
STAT_INC(BINARY_SUBSCR, hit);
Expand Down Expand Up @@ -466,7 +466,7 @@ dummy_func(
DEOPT_IF(!PyList_CheckExact(list), STORE_SUBSCR);

// Ensure nonnegative, zero-or-one-digit ints.
DEOPT_IF(!_PyLong_IsPositiveSingleDigit(sub), STORE_SUBSCR);
DEOPT_IF(!_PyLong_IsPositiveSingleDigit((PyLongObject *)sub), STORE_SUBSCR);
Py_ssize_t index = ((PyLongObject*)sub)->long_value.ob_digit[0];
// Ensure index < len(list)
DEOPT_IF(index >= PyList_GET_SIZE(list), STORE_SUBSCR);
Expand Down Expand Up @@ -1780,8 +1780,8 @@ dummy_func(
assert(cframe.use_tracing == 0);
DEOPT_IF(!PyLong_CheckExact(left), COMPARE_AND_BRANCH);
DEOPT_IF(!PyLong_CheckExact(right), COMPARE_AND_BRANCH);
DEOPT_IF(!_PyLong_IsSingleDigit(left), COMPARE_AND_BRANCH);
DEOPT_IF(!_PyLong_IsSingleDigit(right), COMPARE_AND_BRANCH);
DEOPT_IF(!_PyLong_IsSingleDigit((PyLongObject *)left), COMPARE_AND_BRANCH);
DEOPT_IF(!_PyLong_IsSingleDigit((PyLongObject *)right), COMPARE_AND_BRANCH);
STAT_INC(COMPARE_AND_BRANCH, hit);
assert(_PyLong_DigitCount((PyLongObject *)left) <= 1 &&
_PyLong_DigitCount((PyLongObject *)right) <= 1);
Expand Down
12 changes: 5 additions & 7 deletions Python/generated_cases.c.h
View file
Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

8 changes: 4 additions & 4 deletions Python/specialize.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1294,7 +1294,7 @@ _Py_Specialize_BinarySubscr(
PyTypeObject *container_type = Py_TYPE(container);
if (container_type == &PyList_Type) {
if (PyLong_CheckExact(sub)) {
if (_PyLong_IsPositiveSingleDigit(sub)) {
if (_PyLong_IsPositiveSingleDigit((PyLongObject *)sub)) {
instr->op.code = BINARY_SUBSCR_LIST_INT;
goto success;
}
Expand All @@ -1307,7 +1307,7 @@ _Py_Specialize_BinarySubscr(
}
if (container_type == &PyTuple_Type) {
if (PyLong_CheckExact(sub)) {
if (_PyLong_IsPositiveSingleDigit(sub)) {
if (_PyLong_IsPositiveSingleDigit((PyLongObject *)sub)) {
instr->op.code = BINARY_SUBSCR_TUPLE_INT;
goto success;
}
Expand Down Expand Up @@ -1375,7 +1375,7 @@ _Py_Specialize_StoreSubscr(PyObject *container, PyObject *sub, _Py_CODEUNIT *ins
PyTypeObject *container_type = Py_TYPE(container);
if (container_type == &PyList_Type) {
if (PyLong_CheckExact(sub)) {
if (_PyLong_IsPositiveSingleDigit(sub)
if (_PyLong_IsPositiveSingleDigit((PyLongObject *)sub)
&& ((PyLongObject *)sub)->long_value.ob_digit[0] < (size_t)PyList_GET_SIZE(container))
{
instr->op.code = STORE_SUBSCR_LIST_INT;
Expand Down Expand Up @@ -1993,7 +1993,7 @@ _Py_Specialize_CompareAndBranch(PyObject *lhs, PyObject *rhs, _Py_CODEUNIT *inst
goto success;
}
if (PyLong_CheckExact(lhs)) {
if (_PyLong_IsSingleDigit(lhs) && _PyLong_IsSingleDigit(rhs)) {
if (_PyLong_IsSingleDigit((PyLongObject *)lhs) && _PyLong_IsSingleDigit((PyLongObject *)rhs)) {
instr->op.code = COMPARE_AND_BRANCH_INT;
goto success;
}
Expand Down