New Lagged Fib. PRNG gen and random2.d

[Joseph Rushton Wakeling]

On 25/08/13 18:03, monarch_dodra wrote:
> I (finally) ported boost's implementation of the Lagged Fibonacci generator to
> D. I am creating this thread for review.
> https://github.com/D-Programming-Language/phobos/pull/1521
>
> The Lagged Fibonacci generator has interesting properties: For starters, you can
> generate integers or floats with it. With floats, it generates numbers in a 0 ..
> 1 range, making it a very nice generator for users that want simple uniform
> floating point generation in that range.
>
> Another interesting property, is that one can easily specify bit depth and
> return type. So for example, it is possible to generate ubytes in the [0 .. 128]
> range (7 bit depth), or floats with a 0.25 step (eg [0, 0.25, 0.5, 0.75]).
>
> In terms of quality, I'm no expert, but supposedly, it's supposed to be good,
> when properly seeded.

Nice! :-)

> Please review the design, and tell me what you think?
>
> --------
>
> One of the design goals with it, is that I think having a new PRNG is the
> perfect opportunity to try out the *long* discussed but never introduced PRNG
> reference-semantics. The LaggedFibonacciGenerator is designed the first of a new
> familly of generators: Implemented as a pimpl, and without a "save" primitive,
> it is *impossible* to accidently generate the same sequence twice. It does have
> "dup", for those that *must* have back tracking, but it is explicit.

I think that as a general approach it's nice, but we should preferably make 
generic the method of wrapping a payload.  In this way it suffices to have one 
wrapper struct that works, and then it's trivial for users to define new RNG 
types by simply defining new payload types, without having to worry about 
ensuring the reference semantics for each new design.

That was the goal of my RandomGenerator wrapper struct:
http://forum.dlang.org/thread/mailman.443.1377369357.1719.digitalmars-d@puremagic.com
http://forum.dlang.org/thread/5218FD04.8040404@webdrake.net

... which we've already discussed off-list.  I think it should be trivial to 
tweak that to be a generic version of what you've done here.

> Implemented as a pimpl, its pass-by-value is virtually free (MT19937 is an
> approx. 2KiB).
>
> Seeding *must* be done explicitly, so as to provide the fastest possible
> iteration. There is no "seed()" function, so there is no default seed *value*
> either, which will prevent the newbie mistake of "why does random program always
> output the same random sequence", and promote the use of "seed(unpredictableSeed)".

I think this is a matter of taste, but I don't think it's bad to force the user 
to seed things.  Note that the existing RNGs go to the extent of actually 
checking inside popFront() etc. if the RNG has been initialized, and if not, 
seeding it with a default value.

The only thing I'll remark is that these default-seed ideas are quite prevalent 
in other RNG implementations in other languages.  Some of the existing unittests 
may even be based on that default seeding.  So, there may be some expectation of 
that option being available.

> Other than that, there is not much to say... the idea is to try to stress test
> this PRNG, and learn as much as possible, before we tackle random2.

I think the two of us agree on the general principle that RNGs should be re-done 
as structs that wrap a reference to a payload.  Performance- and design-wise, 
I'd say that the following things are worth considering:

   (1) Should the memory management be done via GC (new) as in your
       implementation, or manually managed?  Bear in mind the general
       desirable principle that Phobos code shouldn't rely on the GC if it
       doesn't have to.

       I don't know what impact the use of the GC here can be expected to have
       on overall performance of a piece of code, and whether it might rule out
       use of this design in highly performance-conscious use-cases such as
       games, etc.

       My own use of RefCounted to ensure manual memory management (no GC)
       seems to have some scope-related issues, see:
 
http://forum.dlang.org/post/mailman.445.1377370120.1719.digitalmars-d@puremagic.com

       ... and I assume that if payload was allocated manually via malloc
       instead of new, then the same might be true.

   (2) Should we provide a generic payload wrapper, or require RNG creators
       to implement everything manually?  I strongly support a generic wrapper,
       as there is too great a risk of implementation error if we require
       the wrapping-of-a-reference to be done manually each time.

   (3) As we discussed off-list, if we do implement a generic wrapper, how
       should it work?  Should it work as per my implementation,

           alias RandomGenerator!MyEngine MyRNG;

       or instead as you suggested, as a template mixin,

           struct MyRNG
           {
               mixin RandomGenerator!MyEngine;
           }

       I can see the case for the latter as it will result in much more readable
       type names in error messages.  However, I think it has the potential to
       obscure implementation details in a way that isn't helpful.  Consider what
       happens if we do:

           alias RandomGenerator!MtEngine19937 Mt19937_64
           // ... WRONG!! we forgot to tweak the engine when we copy-pasted,
           // but at least we'll see in any error messages what type of internal
           // engine is being used

       ... compared to:

           struct Mt19937
           {
               mixin RandomGenerator!MtEngine19937;
           }
           // ... Copy-paste failure again, but this time it's obscured and we'll
           // never find out unless we look at the actual source code.

   (4) The devil's advocate position -- should we take the simple route to
       reference-type RNGs by making them final classes?  It's trivial to do but
       to me it feels "un-Phobos-ish" and will also have the problem of requiring
       a lot more code rewrites on the part of std.random users who want to
       upgrade to std.random2.

That seems like a good opening summary of issues -- destroy. :-)

Best wishes,

     -- Joe