Skip to content

Add random.BaseRandom to ease implementation of subclasses #84526

Closed

Description

@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']

    Activity

    1. vstinner commented on Apr 20, 2020

      @vstinner
      MemberAuthor

      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.

    2. added
      stdlibStandard Library Python modules in the Lib/ directory
      on Apr 20, 2020
    3. changed the title [-]Redesign random class inheritance[/-] [+]Redesign random.Random class inheritance[/+] on Apr 20, 2020
    4. changed the title [-]Redesign random class inheritance[/-] [+]Redesign random.Random class inheritance[/+] on Apr 20, 2020
    5. rhettinger commented on Apr 20, 2020

      @rhettinger
      Contributor

      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.

    6. vstinner commented on Apr 20, 2020

      @vstinner
      MemberAuthor

      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).

    7. rhettinger commented on Apr 21, 2020

      @rhettinger
      Contributor

      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.

    8. vstinner commented on Apr 21, 2020

      @vstinner
      MemberAuthor

      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.

    9. serhiy-storchaka commented on Apr 21, 2020

      @serhiy-storchaka
      Member

      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.

    10. vstinner commented on Apr 21, 2020

      @vstinner
      MemberAuthor

      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.

    11. rhettinger commented on Apr 22, 2020

      @rhettinger
      Contributor

      -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.

    12. tim-one commented on Apr 22, 2020

      @tim-one
      Member

      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.

    13. 15 remaining items

    14. mdickinson commented on Apr 24, 2020

      @mdickinson
      Member

      [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.

    15. vstinner commented on Apr 24, 2020

      @vstinner
      MemberAuthor

      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 ;-)

    16. tim-one commented on Apr 24, 2020

      @tim-one
      Member

      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.

    17. mdickinson commented on Apr 24, 2020

      @mdickinson
      Member

      [Tim]

      Mark, you don't count ;-)

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

    18. vstinner commented on Apr 24, 2020

      @vstinner
      MemberAuthor

      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 :-)

    19. tim-one commented on Apr 24, 2020

      @tim-one
      Member

      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.

    20. rhettinger commented on Apr 25, 2020

      @rhettinger
      Contributor

      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()

    21. vstinner commented on Apr 29, 2020

      @vstinner
      MemberAuthor

      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

    22. posita commented on Sep 23, 2021

      positamannequin
      Mannequin

      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?

    23. serhiy-storchaka commented on Sep 23, 2021

      @serhiy-storchaka
      Member

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

    24. posita commented on Sep 23, 2021

      positamannequin
      Mannequin

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

    25. serhiy-storchaka commented on Sep 27, 2021

      @serhiy-storchaka
      Member

      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.

    26. transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    No one assigned

      Labels

      3.9 (EOL)end of lifestdlibStandard Library Python modules in the Lib/ directory

      Projects

      No projects

        Milestone

        No milestone

        Relationships

        None yet

        Development

        No branches or pull requests

        Issue actions