Add random.BaseRandom to ease implementation of subclasses

[vstinner]

BPO	40346
Nosy	@tim-one, @rhettinger, @mdickinson, @pitrou, @vstinner, @serhiy-storchaka, @posita
PRs	bpo-40346: Add random.BaseRandom #19631 bpo-40346: Random subclass randbytes uses getrandbits #19700

^{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 2020-04-29.16:10:34.931>
created_at = <Date 2020-04-20.21:53:09.666>
labels = ['library', '3.9']
title = 'Add random.BaseRandom to ease implementation of subclasses'
updated_at = <Date 2021-09-27.12:13:16.500>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2021-09-27.12:13:16.500>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2020-04-29.16:10:34.931>
closer = 'vstinner'
components = ['Library (Lib)']
creation = <Date 2020-04-20.21:53:09.666>
creator = 'vstinner'
dependencies = []
files = []
hgrepos = []
issue_num = 40346
keywords = ['patch']
message_count = 34.0
messages = ['366892', '366900', '366902', '366908', '366918', '366922', '366923', '366962', '366975', '367004', '367006', '367058', '367077', '367087', '367145', '367175', '367176', '367178', '367179', '367198', '367199', '367200', '367201', '367202', '367203', '367204', '367205', '367212', '367247', '367671', '402495', '402508', '402510', '402703']
nosy_count = 7.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'pitrou', 'vstinner', 'serhiy.storchaka', 'posita']
pr_nums = ['19631', '19700']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue40346'
versions = ['Python 3.9']

[vstinner]

The random.Random class has a strange inheritance which is something uncommon in Python: it inherits from _random.Random which a concrete Mersenne Twister PRNG.

When a class inherit it, like random.SystemRandom, it should carefully override the right method.

I would expect to have something like a base class with abstract methods which raise NotImplementedError, and a concrete implementation which inherits from the base class and the Mersenne Twister C implementation.

A concrete issue is the how subclass handle the newly added randbytes() method:
https://bugs.python.org/issue40286#msg366860

The base class should implement randbytes() using getrandbits(), and the Mersenne Twister would override randbytes() with its fast implementation.

It would avoid the need for such method:

    def __init_subclass__(cls, /, **kwargs):
        """Control how subclasses generate random integers.

    The algorithm a subclass can use depends on the random() and/or
    getrandbits() implementation available to it and determines
    whether it can generate random integers from arbitrarily large
    ranges.
    """

        for c in cls.__mro__:
            if '_randbelow' in c.__dict__:
                # just inherit it
                break
            if 'getrandbits' in c.__dict__:
                cls._randbelow = cls._randbelow_with_getrandbits
                break
            if 'random' in c.__dict__:
                cls._randbelow = cls._randbelow_without_getrandbits
                break

It would also be nice if the base class would support a RNG which only produce bytes, like SystemRandom with os.urandom() and implement getrandbits() from that.

I also had concerns with the implementation of bpo-40282 "Allow random.getrandbits(0)":
#19539 (review)

It's maybe time to fix the class hierarchy.

[rhettinger]

The randbytes() method could have been added effortlessly as a one line pure python method. It only became complicated as a result of premature optimization into C code and as a result of ignoring the API promises.

You really don't have to redesign the whole module. We have no user complaints. There is no problem to be fixed. IMO, this would be unnecessary churn.

[vstinner]

Attached PR 19631 adds random.BaseRandom. random.SystemRandom now inherits from BaseRandom and so no longer inherits from _random.Random: an instance now only takes 48 bytes of memory, rather than 2568 bytes (on x86-64).

[rhettinger]

Having SystemRandom() use less memory is nice. The seed() logic is reusable (not MT specific) and should be kept. Historically, subclassers were supposed to supply random(), and the getrandbits() method was optional and just added greater range to randrange. Am not sure I'm comfortable with you defining random() in pure python dividing by BPF -- that seems like a C level decision. Perhaps some factoring may be useful, but I worry that you're changing the user contracts in subtle ways and that we aren't really gaining anything out of this. I'll just wait to see what everyone else has to say. For me, I really wish you wouldn't do this and would have instead just added randbytes() in a way that was in harmony with the rest of the module. I am getting afraid to submit bug reports because instead of fixing them, it triggers broad redesign and churn. This all started because Antoine and Mark wanted getrandbits(0) to return 0; that was such a minor thing, and now the code is experiencing instability and is in some places measurably slower.

The base class should implement randbytes() using getrandbits()

That is a reimagining of the API at odds with the 20+ year history of the module. If we were starting out from scratch, that might have been a reasonable path, but with long standing, stable code, it doesn't make as much sense.

[vstinner]

Example with Python 3.8:
---

import random

class MyRandom(random.Random):
    def getrandbits(self, n):
        return 0

my = MyRandom()
print([my.randint(1, 6) for _ in range(3)])
print([my.random() for _ in range(3)])

---

Output:
---
[1, 1, 1]
[0.5654641798814677, 0.610057019404943, 0.7526620665660224]
---

[1, 1, 1] is what I expect, but what are these random [0.5654641798814677, 0.610057019404943, 0.7526620665660224] numbers?

This behavior is surprising me. I would expect the base class to be "empty", not to inherit Mersenne Twister. If I don't implement all required abstract methods: I would either expect an error when the class is created, or at least when the method is called.

Raymond:

Am not sure I'm comfortable with you defining random() in pure python dividing by BPF -- that seems like a C level decision.

My PR 19631 doesn't change random.Random.random() (still implemented in C) nor random.SystemRandom.random() (same Python implementation): they should produce exactly the same random floating point numbers.

[serhiy-storchaka]

It may be time to start emitting a warning if a Random subclass overrides random() but not getrandbits() or vice versa.

If you only override random(), methods which rely on generating random integers will use worse algorithm (slightly less uniform). If you only override getrandbits(), -- it is even worse, methods which rely on generating random floating point number will be not affected.

[vstinner]

It may be time to start emitting a warning if a Random subclass overrides random() but not getrandbits() or vice versa.

Does someone know if there are users outside the stdlib of random subclass which only implements random()? I guess that a deprecation warning should help us to know :-)

There is also an implementation detail: technically, it's also sems to possible to only implement _randbelow(): see __init_subclass__(). But I'm not sure what happens in Python 3.8 if you implement _randbelow() but not random() not getrandbits().

In my experience, all RNG either generates random bits or random bytes, but not directly random floats. Usually, floats are computed from the other operations: that's what I'm proposing in BaseRandom. random() is now computed from getrandbits(). But it remains possible to override random(), as done in random.Random.

[rhettinger]

-1 I am opposed to this redesign. There is no problem being solved that warrants changing a long standing public API. It is irresponsible to just guess at whether anyone is using the API. To add randbytes() could have just been a simple two line addition. None of what is being proposed is necessary -- there are no known user problems being solved. At best, this is unnecessary code churn. At worse, it will be a breaking change.

[tim-one]

This wasn't written with subclassing in mind to begin with. A class was just an obvious way to allow advanced users to construct instances with their own states (e.g., so they could build pseudo-independent generators for parallel programming).

When SystemRandom got added, I believe that did about as little as possible just so that it "would work".

Making it easy to create subclasses was never a goal regardless.

I don't mind if that _becomes_ a goal, but with some disclaimers:

• If that makes any method currently in use slower, it's not worth it.

• Saving bytes in a SystemRandom instance is of no practical value.

So I think I'm agreeing with Raymond that reworking this doesn't solve any actual problem. But I'm not opposed to making changes for aesthetic reasons, provided such changes don't impose costs beyond the always-present risk of breaking things with any change.