8000 bpo-46055: Speed up binary shifting operators by xuxinhang · Pull Request #30044 · python/cpython · GitHub
[go: up one dir, main page]
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
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 all commits
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
63 changes: 61 additions & 2 deletions Lib/test/test_long.py
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -946,8 +946,13 @@ def test_huge_lshift(self, size):
self.assertEqual(1 << (sys.maxsize + 1000), 1 << 1000 << sys.maxsize)

def test_huge_rshift(self):
self.assertEqual(42 >> (1 << 1000), 0)
self.assertEqual((-42) >> (1 << 1000), -1)
huge_shift = 1 << 1000
self.assertEqual(42 >> huge_shift, 0)
self.assertEqual((-42) >> huge_shift, -1)
self.assertEqual(1123 >> huge_shift, 0)
self.assertEqual((-1123) >> huge_shift, -1)
self.assertEqual(2**128 >> huge_shift, 0)
self.assertEqual(-2**128 >> huge_shift, -1)

@support.cpython_only
@support.bigmemtest(sys.maxsize + 500, memuse=2/15, dry_run=False)
Expand All @@ -956,6 +961,60 @@ def test_huge_rshift_of_huge(self, size):
self.assertEqual(huge >> (sys.maxsize + 1), (1 << 499) + 5)
self.assertEqual(huge >> (sys.maxsize + 1000), 0)

def test_small_rshift(self):
self.assertEqual(42 >> 1, 21)
self.assertEqual((-42) >> 1, -21)
self.assertEqual(43 >> 1, 21)
self.assertEqual((-43) >> 1, -22)

self.assertEqual(1122 >> 1, 561)
self.assertEqual((-1122) >> 1, -561)
self.assertEqual(1123 >> 1, 561)
self.assertEqual((-1123) >> 1, -562)

self.assertEqual(2**128 >> 1, 2**127)
self.assertEqual(-2**128 >> 1, -2**127)
self.assertEqual((2**128 + 1) >> 1, 2**127)
self.assertEqual(-(2**128 + 1) >> 1, -2**127 - 1)

def test_medium_rshift(self):
self.assertEqual(42 >> 9, 0)
self.assertEqual((-42) >> 9, -1)
self.assertEqual(1122 >> 9, 2)
self.assertEqual((-1122) >> 9, -3)
self.assertEqual(2**128 >> 9, 2**119)
self.assertEqual(-2**128 >> 9, -2**119)

def test_big_rshift(self):
self.assertEqual(42 >> 32, 0)
self.assertEqual((-42) >> 32, -1)
self.assertEqual(1122 >> 32, 0)
self.assertEqual((-1122) >> 32, -1)
self.assertEqual(2**128 >> 32, 2**96)
self.assertEqual(-2**128 >> 32, -2**96)

def test_small_lshift(self):
self.assertEqual(42 << 1, 84)
self.assertEqual((-42) << 1, -84)
self.assertEqual(561 << 1, 1122)
self.assertEqual((-561) << 1, -1122)
self.assertEqual(2**127 << 1, 2**128)
self.assertEqual(-2**127 << 1, -2**128)

def test_medium_lshift(self):
self.assertEqual(42 << 9, 21504)
self.assertEqual((-42) << 9, -21504)
self.assertEqual(1122 << 9, 574464)
self.assertEqual((-1122) << 9, -574464)

def test_big_lshift(self):
self.assertEqual(42 << 32, 42 * 2**32)
self.assertEqual((-42) << 32, -42 * 2**32)
self.assertEqual(1122 << 32, 1122 * 2**32)
self.assertEqual((-1122) << 32, -1122 * 2**32)
self.assertEqual(2**128 << 32, 2**160)
self.assertEqual(-2**128 << 32, -2**160)

@support.cpython_only
def test_small_ints_in_huge_calculation(self):
a = 2 ** 100
Expand Down
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 integers less than
:c:macro:`PyLong_BASE`. Patch by Xinhang Xu.
17 changes: 16 additions & 1 deletion Objects/longobject.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4493,6 +4493,15 @@ long_rshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
Py_ssize_t newsize, hishift, i, j;
twodigits accum;

if (IS_MEDIUM_VALUE(a)) {
stwodigits m, x;
digit shift;
m = medium_value(a);
shift = wordshift == 0 ? remshift : PyLong_SHIFT;
x = m < 0 ? ~(~m >> shift) : m >> shift;
return _PyLong_FromSTwoDigits(x);
}

if (Py_SIZE(a) < 0) {
/* Right shifting negative numbers is harder */
PyLongObject *a1, *a2;
Expand Down Expand Up @@ -4566,11 +4575,17 @@ _PyLong_Rshift(PyObject *a, size_t shiftby)
static PyObject *
long_lshift1(PyLongObject *a, Py_ssize_t wordshift, digit remshift)
{
/* This version due to Tim Peters */
PyLongObject *z = NULL;
Py_ssize_t oldsize, newsize, i, j;
twodigits accum;

if (wordshift == 0 && IS_MEDIUM_VALUE(a)) {
stwodigits m = medium_value(a);
// bypass undefined shift operator behavior
stwodigits x = m < 0 ? -(-m << remshift) : m << remshift;
return _PyLong_FromSTwoDigits(x);
}

oldsize = Py_ABS(Py_SIZE(a));
newsize = oldsize + wordshift;
if (remshift)
Expand Down
0