<div dir="ltr">As promised distressingly many months ago, I have written up a NEP about relaxing the stream-compatibility policy that we currently have.<div><br></div><div><a href="https://github.com/numpy/numpy/pull/11229">https://github.com/numpy/numpy/pull/11229</a><br></div><div><a href="https://github.com/rkern/numpy/blob/nep/rng/doc/neps/nep-0019-rng-policy.rst">https://github.com/rkern/numpy/blob/nep/rng/doc/neps/nep-0019-rng-policy.rst</a><br></div><div><br></div><div>I particularly invite comment on the two lists of methods that we still would make strict compatibility guarantees for.</div><div><br></div><div>---</div><div><br></div><div><div>==============================</div><div>Random Number Generator Policy</div><div>==============================</div><div><br></div><div>:Author: Robert Kern <<a href="mailto:robert.kern@gmail.com">robert.kern@gmail.com</a>></div><div>:Status: Draft</div><div>:Type: Standards Track</div><div>:Created: 2018-05-24</div><div><br></div><div><br></div><div>Abstract</div><div>--------</div><div><br></div><div>For the past decade, NumPy has had a strict backwards compatibility policy for</div><div>the number stream of all of its random number distributions.  Unlike other</div><div>numerical components in ``numpy``, which are usually allowed to return</div><div>different when results when they are modified if they remain correct, we have</div><div>obligated the random number distributions to always produce the exact same</div><div>numbers in every version.  The objective of our stream-compatibility guarantee</div><div>was to provide exact reproducibility for simulations across numpy versions in</div><div>order to promote reproducible research.  However, this policy has made it very</div><div>difficult to enhance any of the distributions with faster or more accurate</div><div>algorithms.  After a decade of experience and improvements in the surrounding</div><div>ecosystem of scientific software, we believe that there are now better ways to</div><div>achieve these objectives.  We propose relaxing our strict stream-compatibility</div><div>policy to remove the obstacles that are in the way of accepting contributions</div><div>to our random number generation capabilities.</div><div><br></div><div><br></div><div>The Status Quo</div><div>--------------</div><div><br></div><div>Our current policy, in full:</div><div><br></div><div>    A fixed seed and a fixed series of calls to ``RandomState`` methods using the</div><div>    same parameters will always produce the same results up to roundoff error</div><div>    except when the values were incorrect.  Incorrect values will be fixed and</div><div>    the NumPy version in which the fix was made will be noted in the relevant</div><div>    docstring.  Extension of existing parameter ranges and the addition of new</div><div>    parameters is allowed as long the previous behavior remains unchanged.</div><div><br></div><div>This policy was first instated in Nov 2008 (in essence; the full set of weasel</div><div>words grew over time) in response to a user wanting to be sure that the</div><div>simulations that formed the basis of their scientific publication could be</div><div>reproduced years later, exactly, with whatever version of ``numpy`` that was</div><div>current at the time.  We were keen to support reproducible research, and it was</div><div>still early in the life of ``numpy.random``.  We had not seen much cause to</div><div>change the distribution methods all that much.</div><div><br></div><div>We also had not thought very thoroughly about the limits of what we really</div><div>could promise (and by “we” in this section, we really mean Robert Kern, let’s</div><div>be honest).  Despite all of the weasel words, our policy overpromises</div><div>compatibility.  The same version of ``numpy`` built on different platforms, or</div><div>just in a different way could cause changes in the stream, with varying degrees</div><div>of rarity.  The biggest is that the ``.multivariate_normal()`` method relies on</div><div>``numpy.linalg`` functions.  Even on the same platform, if one links ``numpy``</div><div>with a different LAPACK, ``.multivariate_normal()`` may well return completely</div><div>different results.  More rarely, building on a different OS or CPU can cause</div><div>differences in the stream.  We use C ``long`` integers internally for integer</div><div>distribution (it seemed like a good idea at the time), and those can vary in</div><div>size depending on the platform.  Distribution methods can overflow their</div><div>internal C ``longs`` at different breakpoints depending on the platform and</div><div>cause all of the random variate draws that follow to be different.</div><div><br></div><div>And even if all of that is controlled, our policy still does not provide exact</div><div>guarantees across versions.  We still do apply bug fixes when correctness is at</div><div>stake.  And even if we didn’t do that, any nontrivial program does more than</div><div>just draw random numbers.  They do computations on those numbers, transform</div><div>those with numerical algorithms from the rest of ``numpy``, which is not</div><div>subject to so strict a policy.  Trying to maintain stream-compatibility for our</div><div>random number distributions does not help reproducible research for these</div><div>reasons.</div><div><br></div><div>The standard practice now for bit-for-bit reproducible research is to pin all</div><div>of the versions of code of your software stack, possibly down to the OS itself.</div><div>The landscape for accomplishing this is much easier today than it was in 2008.</div><div>We now have ``pip``.  We now have virtual machines.  Those who need to</div><div>reproduce simulations exactly now can (and ought to) do so by using the exact</div><div>same version of ``numpy``.  We do not need to maintain stream-compatibility</div><div>across ``numpy`` versions to help them.</div><div><br></div><div>Our stream-compatibility guarantee has hindered our ability to make</div><div>improvements to ``numpy.random``.  Several first-time contributors have</div><div>submitted PRs to improve the distributions, usually by implementing a faster,</div><div>or more accurate algorithm than the one that is currently there.</div><div>Unfortunately, most of them would have required breaking the stream to do so.</div><div>Blocked by our policy, and our inability to work around that policy, many of</div><div>those contributors simply walked away.</div><div><br></div><div><br></div><div>Implementation</div><div>--------------</div><div><br></div><div>We propose first freezing ``RandomState`` as it is and developing a new RNG</div><div>subsystem alongside it.  This allows anyone who has been relying on our old</div><div>stream-compatibility guarantee to have plenty of time to migrate.</div><div>``RandomState`` will be considered deprecated, but with a long deprecation</div><div>cycle, at least a few years.  Deprecation warnings will start silent but become</div><div>increasingly noisy over time.  Bugs in the current state of the code will *not*</div><div>be fixed if fixing them would impact the stream.  However, if changes in the</div><div>rest of ``numpy`` would break something in the ``RandomState`` code, we will</div><div>fix ``RandomState`` to continue working (for example, some change in the</div><div>C API).  No new features will be added to ``RandomState``.  Users should</div><div>migrate to the new subsystem as they are able to.</div><div><br></div><div>Work on a proposed `new PRNG subsystem</div><div><<a href="https://github.com/bashtage/randomgen">https://github.com/bashtage/randomgen</a>>`_ is already underway.  The specifics</div><div>of the new design are out of scope for this NEP and up for much discussion, but</div><div>we will discuss general policies that will guide the evolution of whatever code</div><div>is adopted.</div><div><br></div><div>First, we will maintain API source compatibility just as we do with the rest of</div><div>``numpy``.  If we *must* make a breaking change, we will only do so with an</div><div>appropriate deprecation period and warnings.</div><div><br></div><div>Second, breaking stream-compatibility in order to introduce new features or</div><div>improve performance will be *allowed* with *caution*.  Such changes will be</div><div>considered features, and as such will be no faster than the standard release</div><div>cadence of features (i.e. on ``X.Y`` releases, never ``X.Y.Z``).  Slowness is</div><div>not a bug.  Correctness bug fixes that break stream-compatibility can happen on</div><div>bugfix releases, per usual, but developers should consider if they can wait</div><div>until the next feature release.  We encourage developers to strongly weight</div><div>user’s pain from the break in stream-compatibility against the improvements.</div><div>One example of a worthwhile improvement would be to change algorithms for</div><div>a significant increase in performance, for example, moving from the `Box-Muller</div><div>transform <<a href="https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform">https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform</a>>`_ method</div><div>of Gaussian variate generation to the faster `Ziggurat algorithm</div><div><<a href="https://en.wikipedia.org/wiki/Ziggurat_algorithm">https://en.wikipedia.org/wiki/Ziggurat_algorithm</a>>`_.  An example of an</div><div>unworthy improvement would be tweaking the Ziggurat tables just a little bit.</div><div><br></div><div>Any new design for the RNG subsystem will provide a choice of different core</div><div>uniform PRNG algorithms.  We will be more strict about a select subset of</div><div>methods on these core PRNG objects.  They MUST guarantee stream-compatibility</div><div>for a minimal, specified set of methods which are chosen to make it easier to</div><div>compose them to build other distributions.  Namely,</div><div><br></div><div>    * ``.bytes()``</div><div>    * ``.random_uintegers()``</div><div>    * ``.random_sample()``</div><div><br></div><div>Furthermore, the new design should also provide one generator class (we shall</div><div>call it ``StableRandom`` for discussion purposes) that provides a slightly</div><div>broader subset of distribution methods for which stream-compatibility is</div><div>*guaranteed*.  The point of ``StableRandom`` is to provide something that can</div><div>be used in unit tests so projects that currently have tests which rely on the</div><div>precise stream can be migrated off of ``RandomState``.  For the best</div><div>transition, ``StableRandom`` should use as its core uniform PRNG the current</div><div>MT19937 algorithm.  As best as possible, the API for the distribution methods</div><div>that are provided on ``StableRandom`` should match their counterparts on</div><div>``RandomState``.  They should provide the same stream that the current version</div><div>of ``RandomState`` does.  Because their intended use is for unit tests, we do</div><div>not need the performance improvements from the new algorithms that will be</div><div>introduced by the new subsystem.</div><div><br></div><div>The list of ``StableRandom`` methods should be chosen to support unit tests:</div><div><br></div><div>    * ``.randint()``</div><div>    * ``.uniform()``</div><div>    * ``.normal()``</div><div>    * ``.standard_normal()``</div><div>    * ``.choice()``</div><div>    * ``.shuffle()``</div><div>    * ``.permutation()``</div><div><br></div><div><br></div><div>Not Versioning</div><div>--------------</div><div><br></div><div>For a long time, we considered that the way to allow algorithmic improvements</div><div>while maintaining the stream was to apply some form of versioning.  That is,</div><div>every time we make a stream change in one of the distributions, we increment</div><div>some version number somewhere.  ``numpy.random`` would keep all past versions</div><div>of the code, and there would be a way to get the old versions.  Proposals of</div><div>how to do this exactly varied widely, but we will not exhaustively list them</div><div>here.  We spent years going back and forth on these designs and were not able</div><div>to find one that sufficed.  Let that time lost, and more importantly, the</div><div>contributors that we lost while we dithered, serve as evidence against the</div><div>notion.</div><div><br></div><div>Concretely, adding in versioning makes maintenance of ``numpy.random``</div><div>difficult.  Necessarily, we would be keeping lots of versions of the same code</div><div>around.  Adding a new algorithm safely would still be quite hard.</div><div><br></div><div>But most importantly, versioning is fundamentally difficult to *use* correctly.</div><div>We want to make it easy and straightforward to get the latest, fastest, best</div><div>versions of the distribution algorithms; otherwise, what's the point?  The way</div><div>to make that easy is to make the latest the default.  But the default will</div><div>necessarily change from release to release, so the user’s code would need to be</div><div>altered anyway to specify the specific version that one wants to replicate.</div><div><br></div><div>Adding in versioning to maintain stream-compatibility would still only provide</div><div>the same level of stream-compatibility that we currently do, with all of the</div><div>limitations described earlier.  Given that the standard practice for such needs</div><div>is to pin the release of ``numpy`` as a whole, versioning ``RandomState`` alone</div><div>is superfluous.</div><div><br></div><div><br></div><div>Discussion</div><div>----------</div><div><br></div><div>- <a href="https://mail.python.org/pipermail/numpy-discussion/2018-January/077608.html">https://mail.python.org/pipermail/numpy-discussion/2018-January/077608.html</a></div><div>- <a href="https://github.com/numpy/numpy/pull/10124#issuecomment-350876221">https://github.com/numpy/numpy/pull/10124#issuecomment-350876221</a></div><div><br></div><div><br></div><div>Copyright</div><div>---------</div><div><br></div><div>This document has been placed in the public domain.</div><div><br></div><div><br></div>-- <br><div dir="ltr" class="gmail_signature">Robert Kern</div></div></div>