Author vstinner
Recipients josh.r, mark.dickinson, pitrou, scoder, serhiy.storchaka, vstinner
Date 2014-05-03.12:45:13
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1399121115.72.0.5607102898.issue21420@psf.upfronthosting.co.za>
In-reply-to
Content
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 #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 (*)
---------------+--------------------+--------------+-----------------
History
Date User Action Args
2014-05-03 12:45:15vstinnersetrecipients: + vstinner, mark.dickinson, pitrou, scoder, serhiy.storchaka, josh.r
2014-05-03 12:45:15vstinnersetmessageid: <1399121115.72.0.5607102898.issue21420@psf.upfronthosting.co.za>
2014-05-03 12:45:15vstinnerlinkissue21420 messages
2014-05-03 12:45:13vstinnercreate