[issue43040] random.py randrange() is very slow if the range is a power of 2.

Raymond Hettinger added the comment: > python2's implementation of randrange() that uses random() > under the hood was noticeably faster than python3's > randrange() that uses getrandbits() under the hood. Yes, that was a conscious decision. See https://bugs.python.org/issue9025 . We traded

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Donovan Baarda added the comment: Some points to note; I first noticed this as an apparently 5x performance regression for randrange() between pypy and pypy3. This seemed pretty significant, but admittedly the difference is largely masked by other python overheads when comparing python2 and

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Change by Raymond Hettinger : -- assignee: -> rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: htt

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Raymond Hettinger added the comment: Donovan, if the speed of the power of two case is important to you, I recommend using getrandbits() instead. It is ten times faster. $ python3.9 -m timeit -r 11 -s 'from random import randrange, getrandbits' 'randrange(2**32)' 100 loops, best of

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Donovan Baarda added the comment: I had a look at the C implementation of getrandbits() and spotted this; https://github.com/python/cpython/blob/64fc105b2d2faaeadd1026d2417b83915af6622f/Modules/_randommodule.c#L487 In my case I was also being hit by randrange(2**32) calling getrandbits(33) j

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Donovan Baarda added the comment: FTR, more articles about the slowness of generating random integers in Python; https://lemire.me/blog/2016/03/21/ranged-random-number-generation-is-slow-in-python/ https://www.reddit.com/r/Python/comments/jn0bb/randomrandint_vs_randomrandom_why_is_one_15x/ -

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Donovan Baarda added the comment: I first noticed the problem when migrating a program doing lots of randrange(2**32) calls from python2 (using pypy -O) to python3 (using pypy3 -O) on Debian. The time results were; pypy -O real    3m58.621s user    3m58.501s sys     0m0.085s pypy3 -O real  

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Mark Dickinson added the comment: @Donovan: Please get Raymond Hettinger's sign-off before merging anything. In #37000, the decision not to change things wasn't because we missed a fix, but rather because it was decided that it was better to leave things as they were. I don't think anything

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Donovan Baarda added the comment: Thanks @mark.dickinson for the heads up on that issue. Comments in the code hinted that people had tried to tackle this but IMHO they missed the real fix. I've submitted #24354 on github. It's missing an addition to the NEWS.d because I wasn't sure if someth

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Change by Donovan Baarda : -- keywords: +patch pull_requests: +23174 stage: -> patch review pull_request: https://github.com/python/cpython/pull/24354 ___ Python tracker ___ _

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Mark Dickinson added the comment: See also #37000. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https:

[issue43040] random.py randrange() is very slow if the range is a power of 2.

Change by Serhiy Storchaka : -- nosy: +mark.dickinson, rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscri

[issue43040] random.py randrange() is very slow if the range is a power of 2.

New submission from Donovan Baarda : I encountered a very significant slowdown migrating some code from python2.7 to python3.9 that I tracked down to randrange() being slow. After digging I noticed that _randbelow_with_getrandbits() calls getrandbits() 2x as many times, and asks for one more