You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Add random.BaseRandom to ease implementation of subclasses #84526
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=Noneclosed_at=<Date2020-04-29.16:10:34.931>created_at=<Date2020-04-20.21:53:09.666>labels= ['library', '3.9']
title='Add random.BaseRandom to ease implementation of subclasses'updated_at=<Date2021-09-27.12:13:16.500>user='https://github.com/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.
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.
"""
forcincls.__mro__:
if'_randbelow'inc.__dict__:
# just inherit itbreakif'getrandbits'inc.__dict__:
cls._randbelow=cls._randbelow_with_getrandbitsbreakif'random'inc.__dict__:
cls._randbelow=cls._randbelow_without_getrandbitsbreak
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)
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.
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).
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.
[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.
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.
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.
-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.
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.
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.
(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 ;-)
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.
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.
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 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.
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?
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.
Activity
vstinner commentedon Apr 20, 2020
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:
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.
[-]Redesign random class inheritance[/-][+]Redesign random.Random class inheritance[/+][-]Redesign random class inheritance[/-][+]Redesign random.Random class inheritance[/+]rhettinger commentedon Apr 20, 2020
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 commentedon Apr 20, 2020
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 commentedon Apr 21, 2020
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.
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 commentedon Apr 21, 2020
Example with Python 3.8:
---
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:
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 commentedon Apr 21, 2020
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 commentedon Apr 21, 2020
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 commentedon Apr 22, 2020
-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 commentedon Apr 22, 2020
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.
15 remaining items
mdickinson commentedon Apr 24, 2020
[Victor]
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 commentedon Apr 24, 2020
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 commentedon Apr 24, 2020
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 commentedon Apr 24, 2020
[Tim]
Yes, I was suspecting I'd fail the "real world" test. Fair enough. :-)
vstinner commentedon Apr 24, 2020
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 commentedon Apr 24, 2020
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 commentedon Apr 25, 2020
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 commentedon Apr 29, 2020
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 commentedon Sep 23, 2021
I landed here after investigating this surprising result:
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 commentedon Sep 23, 2021
Matt, your example works in 3.11. In earlier versions you need to override the __new__ method.
posita commentedon Sep 23, 2021
Thanks! Where's that documented? (Apologies if I missed it.)
serhiy-storchaka commentedon Sep 27, 2021
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.