I would like to extend and ask feed back on a discussion started yesterday on Slack.
The problem is about the default Julia RNG whose stream of generated random numbers can change in minor Julia version. There is a good reason for that, but it annoys some package developers who have to update their tests occasionaly. (Some people share the opinion that such tests are not ideal, but this is not the topic of this post).
A possible solution would be to create a low-maintenance RNG which we try hard to not modify. So no performance improvements (performance is not the point, although it shouldn’t perform horribly), but bug fixes might be unavoidable. And for example, if some high-level algorithm changes in Random (like how numbers in a range are generated), the old code would still be maintained for this RNG.
The Slack discussion concluded on the idea that such an RNG would be better in a package (even though it could also be useful for Base/stdlib tests):
you can pin a package across all versions of Julia (Mosè Giordano)
Package feels better because you can then use it with Julia 1.0 etc. For stdlib, the soonest this will happen is 1.6 and then you can’t use it on older releases. (Viral Shah)
So I started the StableRNGs package, which I would like others to contribute to. First by helping deciding whether this is a good idea and could be useful. And then to decide few points, like which RNG to use (currently a Lehmer linear congruential generator), how to name the package etc. If we go forward, I will prefer to put it in an organization and have co-maintainers.
If you are interested, please have a look at the README and at the code if you like, and this can be installed via ]add https://github.com/rfourquet/StableRNGs.jl at the REPL.
I think StableRNGs is perfectly fine for a name, and of course putting it in a package is the right choice.
Perhaps, if it is not too much effort, it could be useful to have a way of requesting the RNG that was/is the default specific to a Julia version. Not necessarily a super-involved API, just something like a bunch of constant aliases.
Part of the trouble is that the algorithms for generating random values of different types and collections changes, not that the underlying stream of random bits has changed (although that happens too sometimes, but far less often). I think part of the premise of StableRNGs must be that it implements things like generating a value of some type or filling arrays with random values of various types in the simplest, most obvious way possible, even if that way is suboptimal.
Indeed, and while this is impossible to guarantee in general, it’s possible for this package to freeze these algorithms for functionality provided by Random (like rand(1:3)) or shuffle), by copy-pasting them from Random if necessary when they change.
Yes that’s exactly the premise, for example rand(rng, 10) and [rand(rng) for _=1:10] will give the same result. Simplicity also helps with lowering the risk for bugs.
I think that’s doable, even if I had not planned it. Actually, IIRC there was a package doing exctly this for the transition Julia 0.6 → 0.7, which was duplicating the RNG from 0.6. This sounds like a good idea, but some input will be needed to confirm that this is really useful and will be used, and I would first focus on making one StableRNG.
function f(args ; kwargs)
draw = some_random_number_generation
for n = 1:upper_bound_depends_on_args
if condition_on_draw
modify_args_with_random_number_generation
update_draw_using_random_number_generation
else
non_random_modify_of_args
end
end
end
So each iteration of the loop depends on random numbers drawn on previous iterations, and in fact the number of random numbers that will be generated for each function call will itself be random. It isn’t obvious (to me) how to pass in the random numbers in a way that isn’t horrible.
I could try and split out the interior of the loop into a separate function, which might make the unit testing with input random numbers a bit less horrible, but it would add a layer of obfuscation to how the function reads. As it stands, a statistician (who isn’t an experienced coder) can look at the function and say “yep that’s a stationary bootstrap”. If I split out the interior of the loop it will be less obvious.
This is a feasible approach for some applications, and could even be wrapped in an implementation conforming to the RNG interface (just deliver the bits until they last, then error).
But RNG samples are data that compress extremely well (by implementing the RNG algorithm), so having a stable implementation that just generates the same draws is a much more elegant solution. In this case, the code also exists already, so we are just talking about archiving it in a nice way.
If someone is willing to donate computer time, it would be cool to run this StableRNG through bigcrush. To do so, RNGTest must be installed (it’s registered) and StableRNGs can be installed via ]add https://github.com/rfourquet/StableRNGs.jl. Then, run the following, it will take maybe 12 hours:
using StableRNGs, RNGTest
rng = LehmerRNG(0)
RNGTest.bigcrushTestU01(RNGTest.wrap(rng, UInt64), "LehmerRNG")
I’m not very familiar with the lib, so I don’t know, but I’m skeptical as there is a lot of global state in TestU01, e.g. there can be only one instance of each kind of user-provided rng (for whatever that means), e.g. I got few times the following message:
******************************************
ERROR in file unif01.c on line 1233
unif01_CreateExternGenBits: only 1 such generator can be in use
******************************************
when playing at the REPL, and this exits Julia. Looking for “thread” or “parallel” in the doc didn’t bring useful results…
julia> RNGTest.bigcrushTestU01(RNGTest.wrap(rng, UInt64), "LehmerRNG")
========= Summary results of BigCrush =========
Version: TestU01 1.2.3
Generator: LehmerRNG
Number of statistics: 160
Total CPU time: 02:13:44.93
All tests were passed
Oh cool! That’s good news both for the duration of the tests and for the result itself
I took the “12h” from the README of RNGTest (and I can’t remember how long it took for me when I used it 5y ago), this clearly needs updating!
Note that the BigCrush test battery takes about twelve hours on a normal computer.
In the testU01 docs, I now found they expect like 8h. But clearly, you must have a beefy machine!
Thanks again.
Just a thought: If i look at https://semver.org/ i get “MINOR version when you add functionality in a backwards compatible manner” - so at least i would expect backward compatible RNG, in all 1.x releases. That would mean: You get bitexact with the same intialization the same stream of output for a PNG in Base.
It’s nice that it’s openly published in the documentation, however people tend to remember common concepts better than exceptions: So if julia is semver everywhere, why not here?
It is here as well. The general term “backwards compatible” is on its own under-specified and it is up to individual projects to define it. This is done by documenting what is considered the public API and what the guarantees the API provide (which is exactly what the text in the linked section does).
Software using Semantic Versioning MUST declare a public API.
Minor version Y (x.Y.z | x > 0) MUST be incremented if new, backwards compatible functionality is introduced to the public API.
Major version X (X.y.z | X > 0) MUST be incremented if any backwards incompatible changes are introduced to the public API.
Since Julia defines reproducible random numbers as outside its public API, it is not required to increment the major version for such changes. Julia “is semver” here just like it is elsewhere; semver doesn’t make requirements about stuff outside the declared public api.
