<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jun 2, 2018 at 3:04 PM, Robert Kern <span dir="ltr"><<a href="mailto:robert.kern@gmail.com" target="_blank">robert.kern@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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" target="_blank">https://github.com/numpy/<wbr>numpy/pull/11229</a><br></div><div><a href="https://github.com/rkern/numpy/blob/nep/rng/doc/neps/nep-0019-rng-policy.rst" target="_blank">https://github.com/rkern/<wbr>numpy/blob/nep/rng/doc/neps/<wbr>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" target="_blank">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.  </div></div></div></blockquote><div><br></div><div>AFAIK, I have never seen this. Except for some corner cases (like singular transformation)</div><div>the "noise" from different linalg packages is in the range of floating point noise which is not relevant if we unit test, for example, pvalues at rtol=1e-10.</div><div><br></div><div>Based on the unit test that don't fail, "may well return completely different results" seems exaggerated.</div><div><br></div><div>(There can be huge jumps in results from linalg operations like svd around the near singular/singular threshold, i.e. when floating point noise is in the range of the rcond threshold, but that's independent of np.random and can happen in many cases when we want to have reproducible numerical noise which is not possible, but doesn't affect stability of results in well defined cases.)</div><div><br></div><div>Josef</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>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" target="_blank">https://github.com/bashtage/<wbr>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" target="_blank">https://en.wikipedia.org/<wbr>wiki/Box%E2%80%93Muller_<wbr>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" target="_blank">https://en.wikipedia.org/<wbr>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" target="_blank">https://mail.python.org/<wbr>pipermail/numpy-discussion/<wbr>2018-January/077608.html</a></div><div>- <a href="https://github.com/numpy/numpy/pull/10124#issuecomment-350876221" target="_blank">https://github.com/numpy/<wbr>numpy/pull/10124#issuecomment-<wbr>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><span class="HOEnZb"><font color="#888888"><div><br></div><div><br></div>-- <br><div dir="ltr" class="m_5805290009272334575gmail_signature">Robert Kern</div></font></span></div></div>
<br>______________________________<wbr>_________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@python.org">NumPy-Discussion@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/numpy-discussion" rel="noreferrer" target="_blank">https://mail.python.org/<wbr>mailman/listinfo/numpy-<wbr>discussion</a><br>
<br></blockquote></div><br></div></div>