Skip to content

bpo-46406: Faster single digit int division. #30626

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
mdickinson merged 4 commits into from
Jan 23, 2022
Merged

bpo-46406: Faster single digit int division. #30626

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
660cc78
bpo-46406: Faster single digit int division.
gpshead Jan 16, 2022
91b1050
re-add the assert, reword news.
gpshead Jan 17, 2022
d09f0c7
Spell Mark's name properly.
gpshead Jan 22, 2022
9902dc2
Add a cast to silence a compiler warning.
gpshead Jan 22, 2022
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
re-add the assert, reword news.
  • Loading branch information
@gpshead
gpshead committed Jan 17, 2022
commit 91b105070660ccb62a74e278e5f65baf6b3c4fc9
5 changes: 3 additions & 2 deletions Misc/NEWS.d/next/Core and Builtins/2022-01-16-15-40-11.bpo-46406.g0mke-.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,2 +1,3 @@
The int division code has been optimized, using modern compilers it can be
20% faster on large numbers in some scenarios.
The integer division ``//`` implementation has been optimized to better let the
compiler understand its constraints. It can be 20% faster on the amd64 platform
when dividing an int by a value smaller than ``2**30``.
15 changes: 8 additions & 7 deletions Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1618,26 +1618,27 @@ v_rshift(digit *z, digit *a, Py_ssize_t m, int d)
_PyLong_Format, but that should be done with great care since ints are
immutable.

This version of the code can be >20% faster than the pre-2022 version
on todays compilers. It evolved from Mark Dickenson observing that on
x86_64 a 128:64 divide instruction was always being generated by the
compiler despite us working with 30-bit digit values. See the thread
for full context:
This version of the code can be 20% faster than the pre-2022 version
on todays compilers on architectures like amd64. It evolved from Mark
Dickenson observing that a 128:64 divide instruction was always being
Comment thread
gpshead marked this conversation as resolved.
Outdated
generated by the compiler despite us working with 30-bit digit values.
See the thread for full context:

https://mail.python.org/archives/list/python-dev@python.org/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/#NEUNFZU3TQU4CPTYZNF3WCN7DOJBBTK5

If you ever want to change this code, pay attention to performance using
different compilers, optimization levels, and cpu architectures. Beware of
PGO/FDO builds doing value specialization such as a fast path for //10. :)

Verify that 17 isn't specialized and this works as a useful test:
python -m timeit -n 1500000 -s 'x = 10**1000; r=x//10; assert r == 10**999, r' 'x//17'
Verify that 17 isn't specialized and this works as a quick test:
python -m timeit -s 'x = 10**1000; r=x//10; assert r == 10**999, r' 'x//17'

@tim-one tim-one Jan 23, 2022

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

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

Asserting that division by 10 "works" is irrelevant when the test is actually dividing by 17. But it's a timing statement, so asserting that the division works is beside the point anyway. The point is to get the timing, so

python -m timeit -s 'x = 10**1000' 'x//17'

would be best. And 17 isn't of real interest anyway. Use 10 instead. That's the value we've actually seen special-cased in PGO builds. 17 only came up when Mark temporarily fudged a PGO-build input test to pick on 17 instead of 10, just to see what would happen.

@gpshead gpshead Jan 24, 2022

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

The command is just a paste of what i was using in my terminal as a quick unittest and microbenchmark. The assert in the setup code is a unittest. It's just easy to write a concise test using 10 and what value is used there isn't really relevant to what is used in the x//17 microbenchmark expression itself.

*/
static digit
inplace_divrem1(digit *pout, digit *pin, Py_ssize_t size, digit n)
{
digit remainder = 0;

assert(n > 0 && n <= PyLong_MASK);
while (--size >= 0) {
twodigits dividend;
dividend = ((twodigits)remainder << PyLong_SHIFT) | pin[size];
Expand Down