speed-up PyLong_As*() for large longs

[sir-sigurd]

BPO	37907
Nosy	@mdickinson, @serhiy-storchaka, @animalize, @sir-sigurd, @thatbirdguythatuknownot
PRs	bpo-37907: Slightly improve performance of PyLong_AsSsize_t() with large longs #15363

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = None
created_at = <Date 2019-08-21.16:17:42.453>
labels = ['interpreter-core', '3.9', 'performance']
title = 'speed-up PyLong_As*() for large longs'
updated_at = <Date 2022-03-15.07:54:07.512>
user = 'https://github.com/sir-sigurd'

bugs.python.org fields:

activity = <Date 2022-03-15.07:54:07.512>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2019-08-21.16:17:42.453>
creator = 'sir-sigurd'
dependencies = []
files = []
hgrepos = []
issue_num = 37907
keywords = ['patch']
message_count = 3.0
messages = ['350091', '415113', '415119']
nosy_count = 5.0
nosy_names = ['mark.dickinson', 'serhiy.storchaka', 'malin', 'sir-sigurd', 'Crowthebird']
pr_nums = ['15363']
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue37907'
versions = ['Python 3.9']

Linked PRs

• gh-82088: Improve performance of PyLong_As*() for multi-digit ints #135585

[sir-sigurd]

PyLong_As*() functions computes result for large longs like this:

size_t x, prev;
x = 0;
while (--i >= 0) {
    prev = x;
    x = (x << PyLong_SHIFT) | v->ob_digit[i];
    if ((x >> PyLong_SHIFT) != prev) {
        *overflow = sign;
        goto exit;
    }
}

It can be rewritten like this:

size_t x = 0;
while (--i >= 0) {
    if (x > (size_t)-1 >> PyLong_SHIFT) {
        goto overflow;
    }
    x = (x << PyLong_SHIFT) | v->ob_digit[i];
}

This provides some speed-up:

PyLong_AsSsize_t()
$ python -m perf timeit -s "from struct import Struct; N = 1000; pack = Struct('n'*N).pack; values = (2**30,)*N" "pack(*values)" --compare-to=../cpython-master/venv/bin/python
/home/sergey/tmp/cpython-master/venv/bin/python: ..................... 9.69 us +- 0.02 us
/home/sergey/tmp/cpython-dev/venv/bin/python: ..................... 8.61 us +- 0.07 us
Mean +- std dev: [/home/sergey/tmp/cpython-master/venv/bin/python] 9.69 us +- 0.02 us -> [/home/sergey/tmp/cpython-dev/venv/bin/python] 8.61 us +- 0.07 us: 1.12x faster (-11%)

PyLong_AsSize_t()
$ python -m perf timeit -s "from struct import Struct; N = 1000; pack = Struct('N'*N).pack; values = (2**30,)*N" "pack(*values)" --compare-to=../cpython-master/venv/bin/python
/home/sergey/tmp/cpython-master/venv/bin/python: ..................... 10.5 us +- 0.1 us
/home/sergey/tmp/cpython-dev/venv/bin/python: ..................... 8.19 us +- 0.17 us
Mean +- std dev: [/home/sergey/tmp/cpython-master/venv/bin/python] 10.5 us +- 0.1 us -> [/home/sergey/tmp/cpython-dev/venv/bin/python] 8.19 us +- 0.17 us: 1.29x faster (-22%)

PyLong_AsLong()
$ python -m perf timeit -s "from struct import Struct; N = 1000; pack = Struct('l'*N).pack; values = (2**30,)*N" "pack(*values)" --compare-to=../cpython-master/venv/bin/python
/home/sergey/tmp/cpython-master/venv/bin/python: ..................... 9.68 us +- 0.02 us
/home/sergey/tmp/cpython-dev/venv/bin/python: ..................... 8.48 us +- 0.22 us
Mean +- std dev: [/home/sergey/tmp/cpython-master/venv/bin/python] 9.68 us +- 0.02 us -> [/home/sergey/tmp/cpython-dev/venv/bin/python] 8.48 us +- 0.22 us: 1.14x faster (-12%)

PyLong_AsUnsignedLong()
$ python -m perf timeit -s "from struct import Struct; N = 1000; pack = Struct('L'*N).pack; values = (2**30,)*N" "pack(*values)" --compare-to=../cpython-master/venv/bin/python
/home/sergey/tmp/cpython-master/venv/bin/python: ..................... 10.5 us +- 0.1 us
/home/sergey/tmp/cpython-dev/venv/bin/python: ..................... 8.41 us +- 0.26 us
Mean +- std dev: [/home/sergey/tmp/cpython-master/venv/bin/python] 10.5 us +- 0.1 us -> [/home/sergey/tmp/cpython-dev/venv/bin/python] 8.41 us +- 0.26 us: 1.25x faster (-20%)

The mentioned pattern is also used in PyLong_AsLongLongAndOverflow(), but I left it untouched since the proposed change doesn't seem to affect its performance.

[thatbirdguythatuknownot]

Revisiting this 2+ year-old bug report, can I create another PR that implements the old PR's comments' suggestions?

[thatbirdguythatuknownot]

New benchmarks with the new changes:

PyLong_AsSsize_t: Mean +- std dev: [orig] 10.3 us +- 0.6 us -> [modif] 9.03 us +- 0.61 us: 1.14x faster
PyLong_AsSize_t: Mean +- std dev: [orig] 10.5 us +- 2.4 us -> [modif] 9.26 us +- 0.17 us: 1.13x faster
PyLong_AsLong: Mean +- std dev: [orig] 12.7 us +- 0.1 us -> [modif] 11.2 us +- 0.4 us: 1.14x faster
PyLong_AsUnsignedLong: Mean +- std dev: [orig] 12.5 us +- 0.4 us -> [modif] 11.4 us +- 0.6 us: 1.10x faster

Benchmark hidden because not significant (2): PyLong_AsLongLong, PyLong_AsUnsignedLongLong

Geometric mean: 1.09x faster

[thatbirdguythatuknownot]

Is this issue still supposed to be open?