Skip to content

bpo-46055: Speed up binary shifting operators #30044

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 18 commits into from
Dec 27, 2021
Merged

bpo-46055: Speed up binary shifting operators #30044

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
18 commits
Select commit Hold shift + click to select a range
7b11d7d
Perf: Accelerate binary shift op.
xuxinhang Dec 11, 2021
403652a
Fix: Ubuntu gcc segment fault.
xuxinhang Dec 12, 2021
dcd2796
Let PyLong_New accept a negtive size.
xuxinhang Dec 12, 2021
25bbf4d
Fix: Use Py_ARITHMETIC_RIGHT_SHIFT to avoid the undefined padding bah…
xuxinhang Dec 12, 2021
b2ef93d
Style: PEP7: add braces.
xuxinhang Dec 12, 2021
7d2203f
Fix: Bypass undefined shift operator behavior
xuxinhang Dec 13, 2021
932ad87
Revert "Let PyLong_New accept a negtive size."
xuxinhang Dec 22, 2021
596b8cf
Revert: Remove additional inline keywords.
xuxinhang Dec 22, 2021
6545e9a
Refactor: Simpilify code by using _PyLong_FromSTwoDigit
xuxinhang Dec 23, 2021
7f80cd9
Fix: Wrong rshift result.
xuxinhang Dec 23, 2021
b24c7dc
Test: More testcases.
xuxinhang Dec 23, 2021
c00a963
Refactor: Clean code.
xuxinhang Dec 23, 2021
b7ad599
Revert: Revert unrelated code.
xuxinhang Dec 23, 2021
c359521
Docs: A couple more things.
xuxinhang Dec 24, 2021
241da4c
Revert: medium_value
xuxinhang Dec 24, 2021
9ed09aa
Add attribution; fix typo
mdickinson Dec 27, 2021
c24ad0a
Merge branch 'main' into feat/binary_shift_optimization
mdickinson Dec 27, 2021
59672cf
Merge remote-tracking branch 'upstream/main' into feat/binary_shift_o…
mdickinson Dec 27, 2021
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
Docs: A couple more things.
  • Loading branch information
@xuxinhang
xuxinhang committed Dec 24, 2021
commit c359521056e3078b16f73a24c24a90e63784dc08
1 change: 1 addition & 0 deletions Misc/ACKS
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1964,6 +1964,7 @@ Doug Wyatt
Xiang Zhang
Robert Xiao
Florent Xicluna
Xinhang Xu
Arnon Yaari
Alakshendra Yadav
Hirokazu Yamamoto
Expand Down
2 changes: 2 additions & 0 deletions Misc/NEWS.d/next/Core and Builtins/2021-12-24-20-21-45.bpo-46055.R0QMVQ.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,2 @@
Speed up shifting operation involving integrates less than
:c:macro:`PyLong_BASE`.
Comment thread
mdickinson marked this conversation as resolved.
Outdated
10 changes: 5 additions & 5 deletions Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4507,14 +4507,14 @@ long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
if (Py_SIZE(a) < 0) {
/* Right shifting negative numbers is harder */
PyLongObject *a1, *a2;
a1 = (PyLongObject *)long_invert(a);
a1 = (PyLongObject *) long_invert(a);
if (a1 == NULL)
return NULL;
a2 = (PyLongObject *)long_rshift1(a1, wordshift, remshift);
a2 = (PyLongObject *) long_rshift1(a1, wordshift, remshift);
Py_DECREF(a1);
if (a2 == NULL)
return NULL;
z = (PyLongObject *)long_invert(a2);
z = (PyLongObject *) long_invert(a2);
Py_DECREF(a2);
}
else {
Expand All @@ -4529,8 +4529,8 @@ long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
return NULL;
for (i = 0, j = wordshift; i < newsize; i++, j++) {
z->ob_digit[i] = (a->ob_digit[j] >> remshift) & lomask;
if (i + 1 < newsize)
z->ob_digit[i] |= (a->ob_digit[j + 1] << hishift) & himask;
if (i+1 < newsize)
z->ob_digit[i] |= (a->ob_digit[j+1] << hishift) & himask;
}
z = maybe_small_long(long_normalize(z));
}
Expand Down