Optimize 2 ** n: implement it as 1 << n

[vstinner]

BPO	21420
Nosy	@mdickinson, @pitrou, @scoder, @vstinner, @serhiy-storchaka, @MojoVampire
Files	pow2.patch bench_pow2.py pow2_specialized.patch

^{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 = <Date 2014-05-12.20:46:21.787>
created_at = <Date 2014-05-02.21:54:22.719>
labels = ['performance']
title = 'Optimize 2 ** n: implement it as 1 << n'
updated_at = <Date 2014-05-12.20:46:21.786>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2014-05-12.20:46:21.786>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2014-05-12.20:46:21.787>
closer = 'vstinner'
components = []
creation = <Date 2014-05-02.21:54:22.719>
creator = 'vstinner'
dependencies = []
files = ['35138', '35139', '35145']
hgrepos = []
issue_num = 21420
keywords = ['patch']
message_count = 8.0
messages = ['217800', '217801', '217802', '217820', '217823', '217863', '217897', '218360']
nosy_count = 7.0
nosy_names = ['mark.dickinson', 'pitrou', 'scoder', 'vstinner', 'Arfrever', 'serhiy.storchaka', 'josh.r']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue21420'
versions = ['Python 3.5']

[vstinner]

The algorithm for 2 ** n (long_pow) is slower than 1 << n algorithm (long_lshift). I propose to compute x**y as 1<<y if x==2 and y >= 0.

Attached patch implements this idea. According to my microbenchmark, it is 4x faster to small power (2**0 .. 2**1024) and up to 340x faster for large power (2**(2**28)).

[vstinner]

Results of bench_pow2.py on Linux.

Common platform:
CPU model: Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz
Platform: Linux-3.13.9-200.fc20.x86_64-x86_64-with-fedora-20-Heisenbug
Timer: time.perf_counter
Python unicode implementation: PEP-393
Timer info: namespace(adjustable=False, implementation='clock_gettime(CLOCK_MONOTONIC)', monotonic=True, resolution=1e-09)
CFLAGS: -Wno-unused-result -Werror=declaration-after-statement -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes
Bits: int=32, long=64, long long=64, size_t=64, void*=64

Platform of campaign orig:
Date: 2014-05-02 23:45:29
SCM: hg revision=62438d1b11c7 tag=tip branch=default date="2014-05-02 23:26 +0200"
Timer precision: 49 ns
Python version: 3.5.0a0 (default:62438d1b11c7, May 2 2014, 23:45:22) [GCC 4.8.2 20131212 (Red Hat 4.8.2-7)]

Platform of campaign pow2:
Python version: 3.5.0a0 (default:62438d1b11c7+, May 2 2014, 23:47:50) [GCC 4.8.2 20131212 (Red Hat 4.8.2-7)]
SCM: hg revision=62438d1b11c7+ tag=tip branch=default date="2014-05-02 23:26 +0200"
Timer precision: 51 ns
Date: 2014-05-02 23:48:03

---------------+--------------+----------------
Tests          |         orig |            pow2
---------------+--------------+----------------
2 ** 0         |    40 ns () |     44 ns (+9%)
2 ** 1         |   264 ns () |    62 ns (-76%)
2 ** 3         |   270 ns () |    62 ns (-77%)
2 ** 5         |   269 ns () |    62 ns (-77%)
2 ** 10        |   278 ns () |    63 ns (-78%)
2 ** 15        |   299 ns () |    62 ns (-79%)
2 ** 20        |   287 ns () |    62 ns (-78%)
2 ** 25        |   302 ns () |    62 ns (-79%)
2 ** 28        |   293 ns () |    62 ns (-79%)
2 ** (2 ** 0)  |   264 ns () |    62 ns (-77%)
2 ** (2 ** 1)  |   264 ns () |    62 ns (-76%)
2 ** (2 ** 3)  |   264 ns () |    62 ns (-77%)
2 ** (2 ** 5)  |   286 ns () |    68 ns (-76%)
2 ** (2 ** 10) |   740 ns () |    68 ns (-91%)
2 ** (2 ** 15) |  93.1 us () |  180 ns (-100%)
2 ** (2 ** 20) |  3.94 ms () | 3.89 us (-100%)
2 ** (2 ** 25) |   154 ms () |  213 us (-100%)
2 ** (2 ** 28) | 1.36 sec () | 4.01 ms (-100%)
---------------+--------------+----------------
Total          | 1.52 sec (*) | 4.23 ms (-100%)
---------------+--------------+----------------

[vstinner]

Oh, the patch implements another micro-optimization: "(x << 0) is x" becomes True. I included it in the same patch to reduce the overhead for 2 ** 0.

[scoder]

LGTM, can't see a case where this might go wrong (errors and type checks are handled before the added code).

It also seems a sufficiently common case to optimise it internally. The 2**n spelling is easier to read and to get right than the shifting, so it's good to make both similarly fast to remove an excuse for micro optimisations in Python code.

[vstinner]

pow2_specialized.patch: here is a different approach, a little bit faster. I wrote a dedicated long_pow2() function which computes 2**k.

Arguments in favor of pow2_specialized.patch instead of pow2.patch:

• it's a little bit faster
• don't touch long_lshift(), so there is no risk of performance regression
• it becomes easier to implement bpo-21419 optimization: use calloc() instead of malloc() for very large power of 2, to avoid allocating physical memory pages for zeros

Results of bench_pow2.py comparing original Python, pow2.pathc and pow2_specialized.patch:

Common platform:
Platform: Linux-3.13.9-200.fc20.x86_64-x86_64-with-fedora-20-Heisenbug
Timer info: namespace(adjustable=False, implementation='clock_gettime(CLOCK_MONOTONIC)', monotonic=True, resolution=1e-09)
Python unicode implementation: PEP-393
Bits: int=32, long=64, long long=64, size_t=64, void*=64
Timer: time.perf_counter
CPU model: Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz
CFLAGS: -Wno-unused-result -Werror=declaration-after-statement -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes

Platform of campaign orig:
SCM: hg revision=62438d1b11c7 tag=tip branch=default date="2014-05-02 23:26 +0200"
Date: 2014-05-03 14:42:56
Timer precision: 46 ns
Python version: 3.5.0a0 (default:62438d1b11c7, May 3 2014, 14:41:50) [GCC 4.8.2 20131212 (Red Hat 4.8.2-7)]

Platform of campaign pow2:
SCM: hg revision=62438d1b11c7+ tag=tip branch=default date="2014-05-02 23:26 +0200"
Python version: 3.5.0a0 (default:62438d1b11c7+, May 3 2014, 14:41:13) [GCC 4.8.2 20131212 (Red Hat 4.8.2-7)]
Date: 2014-05-03 14:41:21
Timer precision: 51 ns

Platform of campaign pow2_specialized:
SCM: hg revision=62438d1b11c7+ tag=tip branch=default date="2014-05-02 23:26 +0200"
Date: 2014-05-03 14:40:26
Python version: 3.5.0a0 (default:62438d1b11c7+, May 3 2014, 14:40:18) [GCC 4.8.2 20131212 (Red Hat 4.8.2-7)]
Timer precision: 46 ns

---------------+--------------------+--------------+-----------------
Tests          |               orig |         pow2 | pow2_specialized
---------------+--------------------+--------------+-----------------
2 ** 0         |          39 ns () | 44 ns (+11%) |            41 ns
2 ** 1         |     264 ns (+531%) | 62 ns (+48%) |        42 ns ()
2 ** 3         |     269 ns (+554%) | 62 ns (+50%) |        41 ns ()
2 ** 5         |     269 ns (+560%) | 62 ns (+51%) |        41 ns ()
2 ** 10        |     279 ns (+410%) | 63 ns (+15%) |        55 ns ()
2 ** 15        |     299 ns (+460%) | 62 ns (+16%) |        53 ns ()
2 ** 20        |     287 ns (+426%) | 62 ns (+14%) |        55 ns ()
2 ** 25        |     302 ns (+466%) | 62 ns (+16%) |        53 ns ()
2 ** 28        |     293 ns (+438%) | 62 ns (+14%) |        55 ns ()
2 ** (2 ** 0)  |     264 ns (+549%) | 62 ns (+52%) |        41 ns ()
2 ** (2 ** 1)  |     264 ns (+524%) | 62 ns (+48%) |        42 ns ()
2 ** (2 ** 3)  |     263 ns (+548%) | 62 ns (+52%) |        41 ns ()
2 ** (2 ** 5)  |     283 ns (+346%) |  68 ns (+8%) |        63 ns ()
2 ** (2 ** 10) |     715 ns (+950%) |    68 ns () |            69 ns
2 ** (2 ** 15) |  89.6 us (+51109%) |   175 ns () |           177 ns
2 ** (2 ** 20) | 3.89 ms (+100603%) |  3.86 us () |          3.86 us
2 ** (2 ** 25) |   152 ms (+66557%) | 240 us (+5%) |       228 us ()
2 ** (2 ** 28) | 1.35 sec (+33851%) |  3.99 ms () |          3.99 ms
---------------+--------------------+--------------+-----------------
Total          | 1.51 sec (+35664%) |      4.23 ms |      4.22 ms (*)
---------------+--------------------+--------------+-----------------

[mdickinson]

Victor, can you demonstrate any cases of real code where this optimization makes a significant difference?

There are many, many tiny optimisations we *could* be making in Objects/longobject.c; each of those potential optimisations adds to the cost of maintaining the code, detracts from readability, and potentially even slows down the common cases fractionally. In general, I think we should only be applying this sort of optimization when there's a clear benefit to real-world code. I don't think this one crosses that line.

In the (I suspect rare) cases where a piece of real-world code is slowed down significantly due to a non-optimized 2**n, the code author still has the option of replacing that piece of code with 1<<n manually. And in some cases, that's probably the wrong optimization anyway: an expression like x * 2**n would be better hand-optimized to x << n.

IOW, I'm -1 on making this change.

[pitrou]

I agree with Mark, there doesn't seem to be a strong point in favour of this optimization.

[vstinner]

My main motivation was to use calloc() (issue bpo-21419) for 2**n. It looks like using calloc() for this is only useful for very rare cases (very large value of n: result larger than 1 MB). I close the issue.