classification
Title: Faster bit ops for single-digit positive longs
Type: performance Stage: resolved
Components: Interpreter Core Versions:
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: yselivanov Nosy List: mark.dickinson, serhiy.storchaka, socketpair, vstinner, yselivanov
Priority: normal Keywords: patch

Created on 2016-02-11 19:33 by yselivanov, last changed 2016-12-16 21:35 by yselivanov. This issue is now closed.

Files
File name Uploaded Description Edit
fast_bits.patch yselivanov, 2016-02-11 19:33 review
Messages (8)
msg260126 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-11 19:33
This patch implements a fast path for &, |, and ^ bit operations for single-digit positive longs.  We already have fast paths for ~, and pretty much every other long op.


-m timeit -s "x=21827623" "x&2;x&2;x&2;x&333;x&3;x&3;x&4444;x&4"
with patch: 0.181          without patch: 0.403


-m timeit -s "x=21827623" "x|21222;x|23;x|2;x|333;x|3;x|3;x|4444;x|4"
with patch: 0.241          without patch: 0.342


-m timeit -s "x=21827623" "x^21222;x^23;x^2;x^333;x^3;x^3;x^4444;x^4"
with patch: 0.241          without patch: 0.332
msg260136 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-02-11 22:21
fast_bits.patch LGTM. But it would be better to have at least two reviews.
msg260190 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-02-12 17:48
You should add a tests. especially for edge cases, for negative values for example.
msg260191 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-12 17:54
> You should add a tests. especially for edge cases, for negative values for example.

There are many binop tests in test_long.py
msg260192 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-02-12 18:48
Does this patch have effect with results over 8 bits? Does it have effect after applying patches from 24165?
msg260196 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-12 19:40
> Does this patch have effect with results over 8 bits? 

-m timeit -s "x=2**40" "x&2;x&2;x&2;x&333;x&3;x&3;x&4444;x&4"
with patch: 0.404usec      without patch: 0.41


> Does it have effect after applying patches from 24165?

I'm not sure how it's related, but let's modify the test to stress the mem allocation:

-m timeit -s "x=21827623" "(x+x)&2;(x+x)&2;(x+x)&2;(x+x)&333;(x+x)&3;x&3;(x+x)&4444;(x+x)&4"

this patch+freelist: 0.337usec       only freelist: 0.496

In any case, bit operations are often used for bit-flags logic, where numbers are usually aren't too big (it's rare to see more than 30 bit flags on one field).
msg260197 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-02-12 19:42
> with patch: 0.404usec      without patch: 0.41

Sorry, I made a typo: these results should be flipped -- 0.41-0.404 is the overhead of the fastpath's 'if' check.  I'd say it's a pretty small overhead -- we already optimize all other long ops, including bit inversion.
msg283442 - (view) Author: Yury Selivanov (yselivanov) * (Python committer) Date: 2016-12-16 21:35
Closing this one, as we decided to not to micro-optimize int ops.
History
Date User Action Args
2016-12-16 21:35:17yselivanovsetstatus: open -> closed
resolution: wont fix
messages: + msg283442

stage: patch review -> resolved
2016-02-12 19:42:49yselivanovsetmessages: + msg260197
2016-02-12 19:40:29yselivanovsetmessages: + msg260196
2016-02-12 18:48:23serhiy.storchakasetmessages: + msg260192
2016-02-12 17:54:28yselivanovsetmessages: + msg260191
2016-02-12 17:48:49socketpairsetnosy: + socketpair
messages: + msg260190
2016-02-11 22:21:54vstinnersetmessages: + msg260136
2016-02-11 19:33:58yselivanovcreate