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.

[vstinner]

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

It's clearly advertised at the beginning of the documentation:

"Class Random can also be subclassed if you want to use a different basic generator of your own devising: (...)"

Do you mean that the documentation is wrong and users must not subclass random.Random?

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

I don't think that my PR 19631 has any impact on random.Random and random.SystemRandom performances. Only new 3rd party classes which will be written to inherit from the *new* random.BaseRandom loose the gauss() optimization.

It would be possible to keep the optimization, but it would make class inheritance more complex: subclasses would have to call seed(), getstate() and setstate() methods of BaseRandom. Moreover, I dislike that the base class is not thread state. I prefer to keep it simple and correct.

that reworking this doesn't solve any actual problem.

I changed the issue title to clarify my intent.

My intent is to ease the creation of subclasses. In Python 3.8, a subclass has to *override* 5 methods: getrandbits(), random(), seed(), getstate() and setstate().

With the proposed BaseRandom, a sublcass only has to *implement* *1* single method, getrandbits():

• random() and randbytes() are implemented with getrandbits() automatically
• seed(), getstate() and setstate() raise NotImplementedError, as done by SystemRandom currently. Obviously, you can override them if you want. But at least, you don't inherit the whole Mersenne Twister state by default.

The current problem is that Python 3.9 adds randbytes() which means that a class which inherit from random.Random now has to override not 5 but 6 methods: it now also has to override randbytes().

Raymond proposes to remove _random.Random.randbytes() C implementation and use instead a Python implementation which is 5x slower.

For me, it's surprising that if a subclass doesn't override all methods, it gets a Mersenne Twister implementation. See my msg366918 example. I would prefer a real base class with has no default implementation.

It doesn't prevent people to continue to inherit from random.Random: classes which inherit from random.Random continue to work.

Note: currently in my PR 19631, seed() has to be implemented since it's called by the constructor. I'm not sure if it's a good design or not.

[vstinner]

In Python 3.8, random.Random docstring starts with "Random number generator base class".

I do understand that the random module design predates the abc module (added to Python 2.7). I'm now proposing to add a real base class to move it towards modern Python stdlib coding style.

That's the behavior that I would expect from a "base class":

>>> class MySequence(collections.abc.Sequence): pass
... 
>>> seq=MySequence()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: Can't instantiate abstract class MySequence with abstract methods __getitem__, __len__

Some examples of stdlib modules which implement base classes like this:

• collections.abc.Sequence
• numbers.Complex
• selectors.BaseSelector
• typing.SupportsInt

asyncio.AbstractEventLoop doesn't fail when an instance is created, but when an abstract method is created. Users can choose to inherit from asyncio.BaseEventLoop or asyncio.AbstractEventLoop depending if they wany to inherit partially of BaseEventLoop features, or really create an event loop from scratch (AbstractEventLoop). Other classes which are designed like that:

• email._policybase.Policy
• http.cookiejar.CookiePolicy
• importlib.abc.Loader
• wsgiref.handlers.BaseHandler

I don't think that it's worth it to bother with abc.ABC abstraction here, and so I only propose to provide methods which are implemented as "raise NotImplementedError".

[vstinner]

Ok, PR 19631 is now ready for a review. I completed the documentation to better explain the rationale.

Copy of the What's New in Python 3.9 documentation:

"Add a new random.BaseRandom class: random number generator base class. A random.BaseRandom subclass must only implement a single method: getrandbits(), whereas a random.Random subclass must override 6 methods (getrandbits(), random(), randbytes(), seed(), getstate() and setstate())."

Copy of the commit message:

"BaseRandom implements random() and randbytes() using getrandbits().
It has no state and its gauss() method is thread safe. It has no
VERSION attribute and its seed() method has no version parameter.

The implementation of random.Random, random.SystemRandom and
random.Random subclasses are not affected by this change."

[rhettinger]

This is a breaking change. The published API says that random() is the base method and that getrandbits() is optional.

It is not okay to flat out ignore the opposing comments from the module maintainers. Being on the steering committee isn't a license to do whatever you want, ignoring published APIs, breaking user code, and ignoring other contributors. If you want to go forward with this, there should be a PEP (and you should be recused from adjudicating it).

[pitrou]

If I believe what Victor wrote about:
"""
The implementation of random.Random, random.SystemRandom and
random.Random subclasses are not affected by this change.
"""

then I don't understand how the API is changed. IIUC, users subclassing random.Random won't see a difference. However, users now can subclass BaseRandom which makes it easier to obtain a full-featured random generator class.

However, if we want to think about a new subclassing API, it may be worth looking at the recent Numpy changes. Numpy added a new random generator API recently, with a design based on composition rather than inheritance (and also they switched from Mersenne Twister to another underlying PRNG!):
https://numpy.org/doc/stable/reference/random/index.html

[tim-one]

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

It's clearly advertised at the beginning of the documentation:

"Class Random can also be subclassed if you want to use a
different basic generator of your own devising: (...)"

Do you mean that the documentation is wrong and users must
not subclass random.Random?

I don't know about the docs, but I do know what the goals were whenever I wrote the code ;-) It _can_ be subclassed - but so can be any class whatsoever. There was never an intent to make usefully subclass-ing Random easy: which is precisely what you've discovered and are attempting to improve.

Already said that's fine by me, with caveats. It's not worth much that I can see, beyond scratching an "elegance" itch that I don't happen to have in this case. Who subclasses Random in the real world? Who would want to? Python wanted to in order to add SystemRandom, and did as little as necessary to do so usefully. A long time ago, I believe we also supplied a subclass to give results identical to Python's ancient (& long gone) Wichmann-Hill generator.

Those two are the only cases I've heard of (outside of the test suite).

Provided reworking it doesn't break working code or slow things down, I'm +0.

[mdickinson]

[Tim]

Who subclasses Random in the real world? Who would want to?

Um. Me?

Or at least, I *wanted* to, when I was playing around with PCG. (See https://github.com/mdickinson/pcgrandom.) But after running into the same inelegancies (please note that I'm not calling them *issues*) as Victor, I decided to avoid the subclassing. That led to other inelegancies, like have to reproduce the code for all the various distribution sampling methods (beta, gamma, ...). But I'm okay with that; this was just a toy project.

[mdickinson]

Whoops. I thought the URL highlighter would be clever enough not to include the period. That URL is: https://github.com/mdickinson/pcgrandom

[mdickinson]

it may be worth looking at the recent Numpy changes

Agreed: I do like the NumPy composition model (the random state object _has_ a bit generator, rather than _being_ an extended bit generator).

With the various competing options and the lack of agreement on what (if anything) should be done, this feels like PEP territory.

[vstinner]

I created this issue to address Raymond's comment:
"The randbytes() method needs to depend on genrandbits()."
https://bugs.python.org/issue40286#msg366860

I wrote PR 19700 to address that and only that.

With PR 19700, Random subclasses get a randbytes() implementation which uses getrandbits().

*Maybe* we could do the same in Random subclasses for the random() method, so let's start with the simplest PR :-)

Let's fix the randbytes() issue first.

[vstinner]

Antoine:

However, if we want to think about a new subclassing API, it may be worth looking at the recent Numpy changes. Numpy added a new random generator API recently, with a design based on composition rather than inheritance (and also they switched from Mersenne Twister to another underlying PRNG!):
https://numpy.org/doc/stable/reference/random/index.html

Yeah, sometimes composition is simpler. My BaseRandom base class (PR 19631) can be used with composition indirectly, since all you need is to implemented getrandbits(). Example:

---

from numpy.random import default_rng
import random

class NumpyRandom(random.BaseRandom):
    def __init__(self):
        self._rng = default_rng()

    def getrandbits(self, n):
        # FIXME: support n larger than 64 ;-)
        return int(self._rng.integers(2 ** n))

gen = NumpyRandom()
print(gen.randint(1, 6))
print(gen.random())
print(gen.randbytes(3))

---

[vstinner]

Mark:

With the various competing options and the lack of agreement on what (if anything) should be done, this feels like PEP territory.

Honestly, if you consider that BaseRandom base class is not worth it, I will just abandon this idea. I'm not interested to write a whole PEP just for that. (Maybe someone else is more motivated than me ;-))

[vstinner]

Raymond Hettinger: "It is not okay to flat out ignore the opposing comments from the module maintainers. Being on the steering committee isn't a license to do whatever you want, ignoring published APIs, breaking user code, and ignoring other contributors. If you want to go forward with this, there should be a PEP (and you should be recused from adjudicating it)."

That's a personal attack, would you mind to stay at the technical level, please? Thanks.

[mdickinson]

[Victor]

Honestly, if you consider that BaseRandom base class is not worth it, I will just abandon this idea.

It's not that I think it's not worth it (I'm not currently convinced either way). It's more that if we're going to make a change, then it's not clear to me that the particular choice in the BaseRandom PR is necessarily the only or best way to do it. There are a good few technical choices to be made, and I think there's value in having a wider discussion.

[vstinner]

I see 3 options to fix randbytes() in subclasses:

(A) Remove the randbytes() optimization (C implementation): always implement it with getrandbits().

(B) Add BaseRandom base class: PR 19631.

(C) Modify __init_subclass__() to implement randbytes() with getrandbits() in subclasses: PR 19700

--

Option (A) is the simplest, but it makes randbytes() 5x slower.

Option (B) is my favorite: it keeps all random.Random optimization, it reduces SystemRandom footprint by 2 KB, it eases writing new subclasses (a single method must be defined).

Option (C) seems to be complicated to implement. I'm not sure that it does satisfy Raymond's requirements.

--

Option (A) and (C) don't solve my initial concern of this issue: it's not easy to subclass random.Random, it is still required to *override* 5 methods.

The main drawback of option (B) is that Random subclasses now inherit Random.randbytes() and so should override it which is new requirement. But technically, if Random.randbytes() is inherited: it respects its contract, it generates random bytes... it's just that it may not be the behavior expected by the developer.

My PR 19631 solves this drawback by *documenting* the new requirement in the Porting guide of What's New in Python 3.9. I'm not sure if it should be qualified as backward incompatible, but if yes, I propose to make it on purpose (other options have other drawbacks).

--

Honestly, so far, I'm confused. It's now unclear to me if subclassing the random.Random class is a supported feature and/or if we want to support it. It's also unclear to me if the performance matters in the random module. On one side, gauss() has an optimization which makes it not thread-safe, on the other side option (A) would make randbytes() 5x slower.

It's also possible to combine some options like (B)+(C) which solves the main (B) drawback.

Obviously, the last choice is to revert the randbytes() features (decide that it's no longer possible to add such new method to the random.Random because of drawbacks described in this issue).

--

Well, I proposed various options. Now I let you to decide ;-)

[tim-one]

Mark, you don't count ;-) Neither do I. Of course I've subclassed Random too, to experiment with other base generators (including PCG variants). But they're throwaways, and I don't care that it can require staring at the code to make as many changes as needed. Developers _of_ Python don't need things to be trivial to make quick progress.

So I remain where I was: +0, provided there are no notable runtime regressions. Nice to have (hence "+"), but don't really care if it never happens (hence "0").

As to what numpy does, I'm always in favor of following their lead when possible and Pythonic.

[mdickinson]

[Tim]

Mark, you don't count ;-)

Yes, I was suspecting I'd fail the "real world" test. Fair enough. :-)

[vstinner]

Fun fact. When I wrote my "class NumpyRandom(random.BaseRandom):" example, I found a quite serious bug in numpy:

"default_rng.integers(2**32) always return 0"
numpy/numpy#16066

Even numpy is not perfect yet :-)

[tim-one]

To be serious about numpy ;-) , people consuming a great many random outputs will eventually move to numpy out of necessity (speed). So for that reason alone it's good to mimic what they do. But more fundamentally, they have more people with relevant deep knowledge contributing to the project than Python has. When, e.g., they were considering a Twister alternative, PCG's inventor contributed extensively to their discussion, and even created a new member of the PCG family to address concerns raised by numpy contributors' testing - sll _before_ it was released.

Apart from Mark chiming in, the Python project just doesn't get that level of help in these areas.

[rhettinger]

SystemRandom is a weird special case. Otherwise, almost every PRNG is going to need seed(), getstate(), and setstate(). A base class should each offer some reusable code to minimize the burden on the subclass:

• The existing seed method allows multiple input types to be collapsed to a long integer. A subclass can extend this as needed or can override it completely. This is useful and will tend to give a more consistent API across multiple RNGs.

• The getstate/setstate methods take care of the gauss_next value and allow the seeding to be versioned. This is also useful and helps us insulate users from state related implementation details such as gauss_next.

Please don't lose the above functionality by default.

Also, please make sure that code written to the existing spec continues to work.¹

+1 on offering a PCG generator; however, it should an additional alternative to MT and SystemRandom rather than a replacement. Also, it needs to work well on 32-bit builds. Notes should be added that its state space is *much* smaller than MT, so shuffle() becomes state space limited at much smaller population sizes -- meaning that a large number of possible permutations become unreachable by shuffle() -- for example, to cover all possible shuffles for a deck of 52 playing cards requires 226 bits.² Also, I expect that PCG won't offer us the same performance advantage as it does for numpy because the MT code itself is only a fraction of the time in a call to random(); the rest of the time is in the function call overhead, converting the bytes to a C double, and creating a new Python float object.

I would still like to see a PEP for this.

¹ https://code.activestate.com/recipes/576707/
² factorial(52).bit_length()

[vstinner]

I created this issue to propose PR 19631 (BaseRandom class) which looked like as a good idea to me: simple base class which fix different kind of problems.

But it seems like other people would prefer a complete rewrite from scratch and require a PEP.

I abandonned my BaseRandom PR bpo-19631 and my PR 19700 since there is no clear consensus on these changes. I'm not interested to write a PEP to redesign the module random.

I also close this issue as rejected. If someone wants to enhance the random module, it seems like a PEP is needed: at least, please open a separated issue.

I wrote PR bpo-19797 "Remove C implementation of Random.randbytes()" to address initial Raymond's concern on randbytes() implementation:
https://bugs.python.org/issue40286#msg366860

[posita]

I landed here after investigating this surprising result:

  # test_case.py
  from random import Random
  from typing import Sequence, Union
  
  _RandSeed = Union[None, int, Sequence[int]]
  
  class MyRandom(Random):
    def __init__(
      self,
      seed: _RandSeed = None,
    ):
      if seed is not None and not isinstance(seed, int):
        seed = sum(seed)
      super().__init__(seed)
 
  MyRandom([1, 2])

Output:

  python ./test_case.py
  Traceback (most recent call last):
    File "/…/./test_case.py", line 16, in 
  <module>
      MyRandom([1, 2])
  TypeError: unhashable type: 'list'

In my observation, the Random class aspires to be an interface (and default implementation), but doesn't really live up to those aspirations. (See also python/typeshed#6063.) I suspect nudging Random closer to its claims was the point of this proposal. I'm kind of sad it (or something like it) was rejected in favor of a process that will probably take years. Is there a reason not to do both, meaning heal what lives in the standard library now to live up to its own marketing *and* work toward a better interface in the future?

[serhiy-storchaka]

Matt, your example works in 3.11. In earlier versions you need to override the __new__ method.

[posita]

Thanks! Where's that documented? (Apologies if I missed it.)

[serhiy-storchaka]

That you need to override the __new__ method? I don't know whether it is documented specially. But the constructor calls __new__() and then __init__(). If changing the argument in __init__ does not help, it is because it was already proceeded in __new__.

If you ask about changes in 3.11, it is a side effect of bpo-44260.