_randbelow_with_getrandbits function inefficient with powers of two

[kara71]

BPO	37000
Nosy	@tim-one, @rhettinger, @mdickinson, @kara71
PRs	bpo-37000: Optimized randbelow for powers of two #13485

^{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 = 'https://github.com/rhettinger'
closed_at = <Date 2019-05-23.15:22:36.299>
created_at = <Date 2019-05-21.20:50:16.502>
labels = ['3.8', 'library', 'performance']
title = '_randbelow_with_getrandbits function inefficient with powers of two'
updated_at = <Date 2019-05-23.15:47:29.395>
user = 'https://github.com/kara71'

bugs.python.org fields:

activity = <Date 2019-05-23.15:47:29.395>
actor = 'mark.dickinson'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2019-05-23.15:22:36.299>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2019-05-21.20:50:16.502>
creator = 'Mathis Hammel'
dependencies = []
files = []
hgrepos = []
issue_num = 37000
keywords = ['patch']
message_count = 6.0
messages = ['343094', '343149', '343235', '343263', '343302', '343305']
nosy_count = 4.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'Mathis Hammel']
pr_nums = ['13485']
priority = 'low'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue37000'
versions = ['Python 3.8']

[kara71]

In case _randbelow_with_getrandbits is called with a power of two as its argument (say 2^k), the function will consume k+1 random bits instead of k.

Instead of never being rejected, the sampled number will be rejected on average once per call, causing a computational overhead in addition to wasting k+2 bits on average.

This is due to taking n.bit_size() instead of (n-1).bit_size() for the size of the random candidates. Using n instead of n-1 is apparently deliberate in order to save the case where n = 1, but this could be avoided by directly returning 0 if n == 1.

[mdickinson]

this could be avoided by directly returning 0 if n == 1

The other solution is to make getrandbits(0) valid, always returning 0.

[rhettinger]

Some quick notes:

• In bpo-33144, we achieved a significant speed-up for _randbelow_with_getrandbits() by removing a single test. The code for that method is thin and almost any additional logic will slow it down.

• The attached PR (now closed) causes a performance regression. Shuffling a thousand element list regressed from 505 usec per loop to 576 usec per loop.

• We only promise that the output of random() will be reproducible across versions; however, we should have an aversion to changing the output of the other methods unless it is really necessary (because it may change the result of simulations or random selections which will cause some consternation for some end-users). For seed(8675309), the result of "[randrange(1024) for i in range(10)]" changes under the PR from [823, 438, 575, 465, 718, 186, 25, 1015, 654, 988] to [411, 219, 522, 961, 679, 516, 881, 919, 287, 882]. This is allowed but not desireable.

When I get a chance, I'll take a closer look at Mark's suggestion.

[tim-one]

I believe the thrust of Mark's suggestion was that it would allow using k = (n-1).bit_length() even when n == 1, without special-casing n == 1. But you'd still be adding a new "subtract 1" operation, and would still change results in some cases.

That said, given that (0).bit_length() == 0, it's a bit surprising all on its own that getrandbits(0) raises an exception.

In any case, I'd leave _randbelow_with_getrandbits alone. Conauming "extra" bits is generally a red herring, since the underlying getrandbits() consumes 32 bits at a time from the Twister. That is, we're typically "wasting" more than a dozen bits regardless already (e.g., getrandbits(2), getrandbits(17), and getrandbits(29) all consume 32 bits).

It's unfortunate that _randbelow_with_getrandbits(power_of_2) may invoke getrandbits() more than once. But there's also a bright side: because there's always the possibility that _randbelow_with_getrandbits() may invoke getrandbits() more than once, we can't guess how many times getrandbits() _was_ called. So, in turn, we can't know how much of the Twister's state space was consumed. Which, in turn, makes it much harder to deduce the Twister's' internal state from the visible outputs (but this can be done with certainty from a long enough string of, say, random.choice([0, 1]) outputs if we knew getrandbits was called exactly once for each, despite that we're only seeing 1 bit of each 32-bit Twister output).

That last point shouldn't drive anything, but it is kinda pleasant that people inappropriately using the Twister in contexts where keeping secrets is important are partially protected by under-the-covers accept/reject methods.

[rhettinger]

it's a bit surprising all on its own that getrandbits(0)
raises an exception.

Given that there would be no randomness in the result, it makes sense to me that getrandbits(0) is documented to raise an exception.

Related:
randrange(0) raises an exception
choice([]) raises an exception

In any case, I'd leave _randbelow_with_getrandbits alone.

That makes sense to me as well. I'll mark this as closed.

There's one other bright side. If someone really cares about the speed of the power-of-two case, they can already call getrandbits(10) instead of randrange(1024). The former is about 7x faster.

Mathis, thank you for taking the time to look at this code.

[mdickinson]

Related:
randrange(0) raises an exception
choice([]) raises an exception

Those are very different from getrandbits(0): in both cases there's no reasonable value that can be returned: for the first case, there's no integer x with 0 <= x < 0; for the second, there's no element of [], period. In contrast, there's an obvious, valid, return value for getrandbits(0).

The getrandbits(0) example is much more similar to randrange(1) (in fact, it's pretty much the same thing: apart from n = 0, getrandbits(n) is equivalent at some level to randrange(2**n).

So if getrandbits(0) should be an exception on the basis of not having any randomness in the result, then randrange(1) should be an exception on the same basis, as should random.uniform(2.0, 2.0), etc.

So to me, it makes no sense at all that getrandbits(0) raises: I can't see any good reason for it to do so.