Skip to content

Restore (or beat) Python 2 performance for arithmetic operations on ints that fit into a single word #101291

Open
Open
Restore (or beat) Python 2 performance for arithmetic operations on ints that fit into a single word#101291
Labels
interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

Description

@markshannon
markshannon
opened on Jan 24, 2023

In Python 2 ints and longs were different objects, and the design of each was tailored to the different size and use cases.
In Python3 we dropped the distinction, but we also dropped the design for ints that fit into a single word.
We have added various fast paths for "medium" integers (e.g. #89109) but the underlying data structure gets in the way.

We should layout the int/long object so that it supports fast operations for most integers.

See faster-cpython/ideas#548 for a fuller discussion

Linked PRs

Activity

  1. markshannon
    added
    performancePerformance or resource usage
    on Jan 24, 2023
  2. markshannon
    added a commit that references this issue on Jan 30, 2023

    GH-101291: Refactor the `PyLongObject` struct into object header and …

    c1b1f51
  3. mdboom
    added a commit that references this issue on Jan 31, 2023

    pythonGH-101291: Refactor the `PyLongObject` struct into object heade…

    4874c33
  4. markshannon
    added a commit that references this issue on Mar 22, 2023

    GH-101291: Rearrange the size bits in PyLongObject (GH-102464)

    7559f5f
  5. Fidget-Spinner
    added a commit that references this issue on Mar 27, 2023

    pythonGH-101291: Rearrange the size bits in PyLongObject (pythonGH-10…

    32f8276
  6. warsaw
    added a commit that references this issue on Apr 11, 2023

    pythonGH-101291: Rearrange the size bits in PyLongObject (pythonGH-10…

    3a91146
  7. markshannon
    added a commit that references this issue on May 21, 2023

    GH-101291: Add low level, unstable API for pylong (GH-101685)

    9392379
  8. iritkatriel
    added a commit that references this issue on May 22, 2023

    GH-101291: Avoid using macros with casts in low-level long API. (#104742

    e295d86
  9. miss-islington
    added a commit that references this issue on May 22, 2023

    pythonGH-101291: Avoid using macros with casts in low-level long API. (…

    fd90299
  10. JelleZijlstra
    added a commit that references this issue on May 23, 2023

    [3.12] GH-101291: Avoid using macros with casts in low-level long API. (

    e43fbbd

  11. Yhg1s commented on Jul 6, 2023

    @Yhg1s
    Yhg1s
    on Jul 6, 2023
    Member

    Has there been any progress in documenting the changes made in Python 3.12? (#101292 (comment))

  12. gvanrossum commented on Jul 7, 2023

    @gvanrossum
    gvanrossum
    on Jul 7, 2023
    Member

    Maybe @markshannon can answer that? AFAICT all the commits linked above are his. I know we had someone who was interested in pursuing this further but she had to bow out.

  13. Yhg1s commented on Jul 20, 2023

    @Yhg1s
    Yhg1s
    on Jul 20, 2023
    Member

    @markshannon Where are we with documentation for this? If it's not documented, do we need to start working to roll this back? I'm not comfortable with this change in rc1 if it's not documented.

  14. gvanrossum commented on Jul 20, 2023

    @gvanrossum
    gvanrossum
    on Jul 20, 2023
    Member

    Mark is at EuroPython. If you are there too you can talk to him. We will get it documented.

  15. gvanrossum commented on Jul 21, 2023

    @gvanrossum
    gvanrossum
    on Jul 21, 2023
    Member

    I did a little research. It looks like there are two key changes. First, struct _longobject (defined in Include/cpython/longintrepr.h but considered an internal implementation detail) has changed. It used to be

    struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

    I.e., there was an array ob_digit whose length was abs(ob_size), where sign(ob_size) gave the sign of the overall value.

    The new (still internal) representation is as follows:

    typedef struct _PyLongValue {
    uintptr_t lv_tag; /* Number of digits, sign and flags */
    digit ob_digit[1];
} _PyLongValue;

struct _longobject {
    PyObject_HEAD
    _PyLongValue long_value;
};

    and there are new internal macros to determine the number of digits and the sign, and a bunch of internal macros to handle "compact" values (which fit in 1-2 "digits").

    There are two new public, unstable APIs to support the concept of "compact" values: PyUnstable_Long_IsCompact and PyUnstable_Long_CompactValue. See https://docs.python.org/3.12/c-api/long.html#c.PyUnstable_Long_IsCompact. (In reality these are implemented as macros, and not intended to be part of any ABI.) Everything else that digs through the internals is defined in Include/internal/pycore_long.h, and requires defining Py_BUILD_CORE.

    Details of what the bits in lv_tag mean are intentionally not published -- these are meant to be opaque. Applications that used to dig through ob_digits using ob_size as guidance will break, and have two options: Switch to calling the Python-level APIs int.to_bytes() and int.from_bytes() via PyObject_CallMethod() (see note at https://docs.python.org/3.12/c-api/long.html#c.PyLong_FromString). Or go hard-core, defining Py_BUILD_CORE and importing pycore_long.h. Or, I guess, an intermediate path is to use the new unstable public APIs for dealing with "compact" values and use the slower arbitrary-precision API for non-compact values.

    I think in the What's New in 3.12 we should at least mention the change in the struct (calling out that using ob_size and ob_digits is no longer supported) and the new unstable public APIs (and what they're for). I don't think we need to call out the hard-core option, but maybe a reminder about to_bytes() and from_bytes() would be useful (even though that's been in the docs at least since 3.10).

    @Yhg1s @markshannon What do you think of this? I volunteer to make a PR for what's new 3.12 along the lines of what I wrote above.

  16. markshannon
    added a commit that references this issue on Jul 28, 2023

    GH-101291: Add warning to "what's new" that `PyLongObject` internals …

    1ee605c
  17. miss-islington
    added a commit that references this issue on Jul 28, 2023

    pythonGH-101291: Add warning to "what's new" that `PyLongObject` inte…

    2c03b0c
  18. gvanrossum
    added a commit that references this issue on Jul 31, 2023

    [3.12] GH-101291: Add warning to "what's new" that `PyLongObject` int…

    5f7862d

  19. gvanrossum commented on Jul 31, 2023

    @gvanrossum
    gvanrossum
    on Jul 31, 2023
    Member

    @Yhg1s Assuming the changes Mark made to what's new in 3.12 are what you wanted?

  20. Yhg1s commented on Jul 31, 2023

    @Yhg1s
    Yhg1s
    on Jul 31, 2023
    Member

    Yep, that's adequate.

  21. iritkatriel
    added
    interpreter-core(Objects, Python, Grammar, and Parser dirs)
    on Nov 27, 2023
  22. vstinner
    added a commit that references this issue on Oct 13, 2024

    gh-101291: Add versionadded directives for PyUnstable_Long_* (#125384)

    c6d7b64
  23. miss-islington
    added 2 commits that reference this issue on Oct 13, 2024

    pythongh-101291: Add versionadded directives for PyUnstable_Long_* (p…

    517f0b4

    pythongh-101291: Add versionadded directives for PyUnstable_Long_* (p…

    bf6bc53
  24. vstinner
    added 2 commits that reference this issue on Oct 13, 2024

    [3.13] gh-101291: Add versionadded directives for PyUnstable_Long_* (G…

    cff627a

    [3.12] gh-101291: Add versionadded directives for PyUnstable_Long_* (G…

    243a8a9
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions