Hi everyone:

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.

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.

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

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'll copy pasted here the example documentation:

This is example *useage*

///
unittest
{
    //Create a new Generator.
    LaggedFibonacci!ulong lf;

    //It is not yet seeded.
    assert(!lf.isSeeded);

    //Seed with a random seed.
    lf.seed(unpredictableSeed);

    //generate a new array of 10 random numbers.
    ulong[] numbers1 = lf.take(10).array();

    //An existing array can be filled with an algorithm.
    ulong[] numbers2 = new ulong[](10);
    numbers2.fill(lf);

    //Because of the reference semantics, and since there is no save,
    //we can rest assured both arrays are different.
    assert(!equal(numbers1, numbers2));
}

These are various flavours of the generator.

///
unittest
{
    //Simple declatation
    LaggedFibonacci!double myFloatingPointGenerator;
    LaggedFibonacci!ulong  myIntegralGenerator;

    //Declaration with specific length
    LaggedFibonacci607!double  mySimpleFloatingPointGenerator;
    LaggedFibonacci44497!ulong myComplexIntegralGenerator;

    //Generate specific type: ubytes in the range [0 .. 256]
    LaggedFibonacci!(ubyte, 8) myByteGenerator;

    //Generate specific type: doubles with a step of 0.125
    LaggedFibonacci!(double, 3) myPieGenerator;

    //Generate with high precision reals
    LaggedFibonacci!(real, 64) myPreciseGenerator;
}

--------

Please (kindly) destroy!

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

monarch_dodra:

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

What is its relative performance (measured with LDC2 and/or GDC) compared to Xorshift and the Mersenne Twister when it is used to generate integers and when it's used to generate floating point numbers in 0..1 (for the floating point case you have to use something like random01 to have a fair comparison)?


> In terms of quality, I'm no expert, but supposedly, it's supposed to be good, when properly seeded.

Before being merged into Phobos someone has to measure a bit the actual quality of the random numbers it produces. To avoid problems like the ones had with Xorshift. There are suites and tools to measure the quality of random numbers, like a more modern version of the famous diehard.

Bye,
bearophile

On 25/08/13 22:30, bearophile wrote:
> Before being merged into Phobos someone has to measure a bit the actual quality
> of the random numbers it produces. To avoid problems like the ones had with
> Xorshift. There are suites and tools to measure the quality of random numbers,
> like a more modern version of the famous diehard.

Diehard is out of date.  There's the Dieharder suite, and there's another by Pierre L'Ecuyer and colleagues, TestU01:
http://www.phy.duke.edu/~rgb/General/dieharder.php
http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

Dieharder is in the repositories of Debian/Ubuntu, and a first approximation of a D random test suite is probably as simple as writing a D program that outputs a sufficient quantity of random numbers, and piping them through to Dieharder. It's on the TODO list but there have been too many other things going on recently. :-P

By the way, the Xorshift problem didn't need a complicated test suite.  This was the code that showed up the problem:

    writeln("Let's test the uniformity of random numbers produced with different RNGs.");
    size_t n = 1000_000;

    foreach(Rng; PseudoRngTypes)
    {
        writeln("Generating ", n, " random numbers in [0, 1) with ", Rng.stringof);
        auto rng = Rng(unpredictableSeed);
        auto dist = Distribution(0.0, 100.0, 20);
        foreach(i; 0 .. n)
        {
            dist.add(uniform(0.0, 100.0, rng));
        }

        foreach(bin, h, c; dist.distribution)
        {
            writeln("\t", bin, "\t", h, "\t", c);
        }
        writeln;
    }

(A few data structures aren't described here, but you get the idea.)

The Xorshift problem only arose because the reference code was itself buggy. For something like Lagged Fibonacci there are already good and battle-tested implementations out there (e.g. Boost.Random) and a comparison of results for the same seeds should be sufficient for inclusion.

On Sunday, 25 August 2013 at 20:30:04 UTC, bearophile wrote:
> Before being merged into Phobos someone has to measure a bit the actual quality of the random numbers it produces. To avoid problems like the ones had with Xorshift. There are suites and tools to measure the quality of random numbers, like a more modern version of the famous diehard.

I can't comment on the quality of the PRNG itself, as I'm no RNG expert myself, but the code *was* ported from boost, and produces the same output. So arguably, we have matching quality.

On Sunday, 25 August 2013 at 20:30:04 UTC, bearophile wrote:
> What is its relative performance (measured with LDC2 and/or GDC) compared to Xorshift and the Mersenne Twister when it is used to generate integers and when it's used to generate floating point numbers in 0..1 (for the floating point case you have to use something like random01 to have a fair comparison)?

A valid question. I benched it, and the results are, IMO *very* good. The tests were run using the reference dmd 2.0.63.2, on a win7_64.

When generating uint's with 32 bits of randomness, I'm on par with MinstdRand0 in terms of speed, which is pretty good I think. It is faster than MT, but still slower than XS.

However, it can *also* generate ulongs with 64 bits of randomness, but doing so only takes roughly 40% more time. Which is great? I'd have to bench on a linux 64 with a dmd64 compiler: I think a true 64 bit implementation should have even less overhead, making LF *faster* (!) than MinstdRand0.

Another interesting bench was generating doubles: Lagged Fibonacci is able to natively generate doubles. As such, I benched it against the other generators, after dividing the output by Generator.max. This should be of interest to you...

The results are also good: I'm getting *slightly* slower times than MinstdRand0 (roughly 10% slower), but still faster than MT. HOWEVER, PRNG/PRNG.max will generate doubles with only 32 bits of significant fractional part. LF will generate doubles with either 48 bits is significance (by default), or the full 52 bits. It is *also* able to generate reals with the full 64 bits of significant data, but this is somewhat slower. Awesome!

--------

That's my biased review/comment on the numbers. I'll post them here, so you can interpret yourself.

On Monday, 26 August 2013 at 09:24:57 UTC, monarch_dodra wrote:
> That's my biased review/comment on the numbers. I'll post them here, so you can interpret yourself.

Units are ms. 1_000_000_000 iterations

/*Generate simple uints*/
Time for LinearCongruentialEngine!(uint, 16807, 0, 2147483647):  7487
Time for LinearCongruentialEngine!(uint, 48271, 0, 2147483647):  7092
Time for MersenneTwisterEngine!(uint, 32, 624, 397, 31, 2567483615u, 11, 7, 2636928640u, 15, 4022730752u, 18): 13678
Time for XorshiftEngine!(uint, 32, 13, 17, 5)             :  4266
Time for XorshiftEngine!(uint, 64, 10, 13, 10)            :  4694
Time for XorshiftEngine!(uint, 96, 10, 5, 26)             :  5697
Time for XorshiftEngine!(uint, 128, 11, 8, 19)            :  5675
Time for XorshiftEngine!(uint, 160, 2, 1, 4)              :  6401
Time for XorshiftEngine!(uint, 192, 2, 1, 4)              :  6754
Time for LaggedFibonacciEngine!(uint, 32u, 607, 273)      :  7630
Time for LaggedFibonacciEngine!(uint, 32u, 1279, 418)     :  7196
Time for LaggedFibonacciEngine!(uint, 32u, 2281, 1252)    :  7411
Time for LaggedFibonacciEngine!(uint, 32u, 3217, 576)     :  7031
Time for LaggedFibonacciEngine!(uint, 32u, 4423, 2098)    :  7402
Time for LaggedFibonacciEngine!(uint, 32u, 9689, 5502)    :  6999
Time for LaggedFibonacciEngine!(uint, 32u, 19937, 9842)   :  7478
Time for LaggedFibonacciEngine!(uint, 32u, 23209, 13470)  :  7064
Time for LaggedFibonacciEngine!(uint, 32u, 44497, 21034)  :  7528
/*Note: These generate longer ulong types*/
Time for LaggedFibonacciEngine!(ulong, 48u, 607, 273)     : 11860
Time for LaggedFibonacciEngine!(ulong, 48u, 1279, 418)    : 11675
Time for LaggedFibonacciEngine!(ulong, 48u, 2281, 1252)   : 11622
Time for LaggedFibonacciEngine!(ulong, 48u, 3217, 576)    : 11621
Time for LaggedFibonacciEngine!(ulong, 48u, 4423, 2098)   : 11699
Time for LaggedFibonacciEngine!(ulong, 48u, 9689, 5502)   : 11898
Time for LaggedFibonacciEngine!(ulong, 48u, 19937, 9842)  : 11883
Time for LaggedFibonacciEngine!(ulong, 48u, 23209, 13470) : 11870
Time for LaggedFibonacciEngine!(ulong, 48u, 44497, 21034) : 11908
Time for LaggedFibonacciEngine!(ulong, 64u, 607, 273)     : 11745
Time for LaggedFibonacciEngine!(ulong, 64u, 1279, 418)    : 11838
Time for LaggedFibonacciEngine!(ulong, 64u, 2281, 1252)   : 11656
Time for LaggedFibonacciEngine!(ulong, 64u, 3217, 576)    : 11709
Time for LaggedFibonacciEngine!(ulong, 64u, 4423, 2098)   : 11768
Time for LaggedFibonacciEngine!(ulong, 64u, 9689, 5502)   : 11863
Time for LaggedFibonacciEngine!(ulong, 64u, 19937, 9842)  : 11923
Time for LaggedFibonacciEngine!(ulong, 64u, 23209, 13470) : 11878
Time for LaggedFibonacciEngine!(ulong, 64u, 44497, 21034) : 11905

/* Generating doubles */
/* via g.front/g.max */
Time for LinearCongruentialEngine!(uint, 16807, 0, 2147483647): 12093
Time for LinearCongruentialEngine!(uint, 48271, 0, 2147483647): 12057
Time for MersenneTwisterEngine!(uint, 32, 624, 397, 31, 2567483615u, 11, 7, 2636928640u, 15, 4022730752u, 18): 19510
Time for XorshiftEngine!(uint, 32, 13, 17, 5)             : 10616
Time for XorshiftEngine!(uint, 64, 10, 13, 10)            : 10634
Time for XorshiftEngine!(uint, 96, 10, 5, 26)             : 10978
Time for XorshiftEngine!(uint, 128, 11, 8, 19)            : 11715
Time for XorshiftEngine!(uint, 160, 2, 1, 4)              : 12052
Time for XorshiftEngine!(uint, 192, 2, 1, 4)              : 12017
Time for LaggedFibonacciEngine!(uint, 32u, 607, 273)      : 12449
Time for LaggedFibonacciEngine!(uint, 32u, 1279, 418)     : 12382
Time for LaggedFibonacciEngine!(uint, 32u, 2281, 1252)    : 12334
Time for LaggedFibonacciEngine!(uint, 32u, 3217, 576)     : 12321
Time for LaggedFibonacciEngine!(uint, 32u, 4423, 2098)    : 12293
Time for LaggedFibonacciEngine!(uint, 32u, 9689, 5502)    : 12482
Time for LaggedFibonacciEngine!(uint, 32u, 19937, 9842)   : 12596
Time for LaggedFibonacciEngine!(uint, 32u, 23209, 13470)  : 12605
Time for LaggedFibonacciEngine!(uint, 32u, 44497, 21034)  : 12727
Time for LaggedFibonacciEngine!(ulong, 48u, 607, 273)     : 17727
Time for LaggedFibonacciEngine!(ulong, 48u, 1279, 418)    : 17626
Time for LaggedFibonacciEngine!(ulong, 48u, 2281, 1252)   : 17527
Time for LaggedFibonacciEngine!(ulong, 48u, 3217, 576)    : 17549
Time for LaggedFibonacciEngine!(ulong, 48u, 4423, 2098)   : 19146
Time for LaggedFibonacciEngine!(ulong, 48u, 9689, 5502)   : 18044
Time for LaggedFibonacciEngine!(ulong, 48u, 19937, 9842)  : 17612
Time for LaggedFibonacciEngine!(ulong, 48u, 23209, 13470) : 17810
Time for LaggedFibonacciEngine!(ulong, 48u, 44497, 21034) : 17855
Time for LaggedFibonacciEngine!(ulong, 64u, 607, 273)     : 17736
Time for LaggedFibonacciEngine!(ulong, 64u, 1279, 418)    : 17630
Time for LaggedFibonacciEngine!(ulong, 64u, 2281, 1252)   : 18671
Time for LaggedFibonacciEngine!(ulong, 64u, 3217, 576)    : 17775
Time for LaggedFibonacciEngine!(ulong, 64u, 4423, 2098)   : 17773
Time for LaggedFibonacciEngine!(ulong, 64u, 9689, 5502)   : 17905
Time for LaggedFibonacciEngine!(ulong, 64u, 19937, 9842)  : 17887
Time for LaggedFibonacciEngine!(ulong, 64u, 23209, 13470) : 17910
Time for LaggedFibonacciEngine!(ulong, 64u, 44497, 21034) : 17976
/* Using native doubles */
Time for LaggedFibonacciEngine!(double, 32u, 607, 273)    : 14741
Time for LaggedFibonacciEngine!(double, 32u, 1279, 418)   : 14475
Time for LaggedFibonacciEngine!(double, 32u, 2281, 1252)  : 14829
Time for LaggedFibonacciEngine!(double, 32u, 3217, 576)   : 14815
Time for LaggedFibonacciEngine!(double, 32u, 4423, 2098)  : 14817
Time for LaggedFibonacciEngine!(double, 32u, 9689, 5502)  : 14698
Time for LaggedFibonacciEngine!(double, 32u, 19937, 9842) : 14882
Time for LaggedFibonacciEngine!(double, 32u, 23209, 13470): 14819
Time for LaggedFibonacciEngine!(double, 32u, 44497, 21034): 14924
/* Native doubles, but higher precision */
Time for LaggedFibonacciEngine!(double, 48u, 607, 273)    : 14657
Time for LaggedFibonacciEngine!(double, 48u, 1279, 418)   : 14577
Time for LaggedFibonacciEngine!(double, 48u, 2281, 1252)  : 14652
Time for LaggedFibonacciEngine!(double, 48u, 3217, 576)   : 14464
Time for LaggedFibonacciEngine!(double, 48u, 4423, 2098)  : 14619
Time for LaggedFibonacciEngine!(double, 48u, 9689, 5502)  : 15168
Time for LaggedFibonacciEngine!(double, 48u, 19937, 9842) : 14904
Time for LaggedFibonacciEngine!(double, 48u, 23209, 13470): 15016
Time for LaggedFibonacciEngine!(double, 48u, 44497, 21034): 15083
Time for LaggedFibonacciEngine!(double, 64u, 607, 273)    : 14807
Time for LaggedFibonacciEngine!(double, 64u, 1279, 418)   : 14639
Time for LaggedFibonacciEngine!(double, 64u, 2281, 1252)  : 14582
Time for LaggedFibonacciEngine!(double, 64u, 3217, 576)   : 14587
Time for LaggedFibonacciEngine!(double, 64u, 4423, 2098)  : 14794
Time for LaggedFibonacciEngine!(double, 64u, 9689, 5502)  : 14893
Time for LaggedFibonacciEngine!(double, 64u, 19937, 9842) : 14802
Time for LaggedFibonacciEngine!(double, 64u, 23209, 13470): 15077
Time for LaggedFibonacciEngine!(double, 64u, 44497, 21034): 15115
Time for LaggedFibonacciEngine!(real, 64u, 607, 273)      : 19308
Time for LaggedFibonacciEngine!(real, 64u, 1279, 418)     : 19249
Time for LaggedFibonacciEngine!(real, 64u, 2281, 1252)    : 19176
Time for LaggedFibonacciEngine!(real, 64u, 3217, 576)     : 19128
Time for LaggedFibonacciEngine!(real, 64u, 4423, 2098)    : 19878
Time for LaggedFibonacciEngine!(real, 64u, 9689, 5502)    : 19221
Time for LaggedFibonacciEngine!(real, 64u, 19937, 9842)   : 19211
Time for LaggedFibonacciEngine!(real, 64u, 23209, 13470)  : 19241
Time for LaggedFibonacciEngine!(real, 64u, 44497, 21034)  : 19268

On 26/08/13 11:24, monarch_dodra wrote:
> However, it can *also* generate ulongs with 64 bits of randomness, but doing so
> only takes roughly 40% more time. Which is great? I'd have to bench on a linux
> 64 with a dmd64 compiler: I think a true 64 bit implementation should have even
> less overhead, making LF *faster* (!) than MinstdRand0.

I'll try and benchmark that myself.  Boost also defines a 64-bit Mersenne Twister which we really should have in Phobos; it'll require some tweaks to the MersenneTwisterEngine design (some more template parameters).

On 26/08/13 11:35, monarch_dodra wrote:
> On Monday, 26 August 2013 at 09:24:57 UTC, monarch_dodra wrote:
>> That's my biased review/comment on the numbers. I'll post them here, so you
>> can interpret yourself.
>
> Units are ms. 1_000_000_000 iterations

Cool -- so, you're getting faster performance than Mersenne Twister for higher-precision/wider range numbers.

That's not the same as statistical quality of course.  There are some general concerns about Lagged Fibonacci -- see:
https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator

I really must implement Mt19937_64 for comparison, and get on with creating something that tests D random numbers against Dieharder.

On Monday, 26 August 2013 at 09:37:11 UTC, Joseph Rushton Wakeling wrote:
> On 26/08/13 11:24, monarch_dodra wrote:
>> However, it can *also* generate ulongs with 64 bits of randomness, but doing so
>> only takes roughly 40% more time. Which is great? I'd have to bench on a linux
>> 64 with a dmd64 compiler: I think a true 64 bit implementation should have even
>> less overhead, making LF *faster* (!) than MinstdRand0.
>
> I'll try and benchmark that myself.  Boost also defines a 64-bit Mersenne Twister which we really should have in Phobos; it'll require some tweaks to the MersenneTwisterEngine design (some more template parameters).

FYI, I tweaked my algo a bit, as the benches revealed an issue. Please wait for a new commit before testing my code.

On Sunday, 25 August 2013 at 16:58:12 UTC, Joseph Rushton Wakeling wrote:
>
> Nice! :-)
>

Thanks ;)

> I think that as a general approach it's nice, but we should preferably make generic the method of wrapping a payload.

To be honest, I think that, for now, this is an "implementation detail". All our PRNG's are created with an explicit "value type", that can easily be made the "Payload", no matter what we do.

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

An "option" I had dabbled in was making the PRNG proper a "Container", which you can *slice* to obtain a high performance range. EG:

//----
auto prng = Random(); //Creates a PRNG.
auto first = prng.front; //lazilly seeds
prng.popFront(); //Checks seeded
auto second = prng.front; //Cheks seeded again...

auto fastPRNG = prng[]; //Lazilly seeds, then returns a type *guaranteed* seeded.
auto third = fastPRNG.front; //No check of isSeeded.
//----

The initial reason I played around with this, is that it was an option to "solve" the reference problem: Make the PRNG's themselves value types, and iterate using reference type *slices*. The end result (for "std.random1") has a couple *major* drawbacks though, IMO:
1. Opt-*in*: Only those aware will use it. The rest of us mortals will still get hit by the bugs.
2. Easily escapes references to locals.
3. As always, if we introduce std.random2, it'll be that much more to clean-up.

Still, I thought I'd share my ideas, even if they aren't the best solutions. It *is* an option for the (don't)auto-seed problem.

One more thing. One of the ways I see it (specifically for LF): We can add auto-seed later if we decide it was a bad idea to not have it. The opposite isn't possible.

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

Another option I had thought of, was to make the value-types Payloads as public, with *massive* "do not use signs". *We* then provide simple and generic (and pure/nothrow) GC-based wrappers.

From there, if, for whatever reason, a user needs malloc allocation, or heck, static allocation, he still has an "underhand" access to the payload implementation, but lifecycle management remains *his* responsibility.

I think: Simple and safe by default, with the possibility for extension.

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

Again, for now, I think this is implementation detail. That said, I don't buy much into the typo argument. In particular, this is something that gets copy pasted only once, so we should be relatively safe.

One of the arguments in favor of "internal" mixins is that of extension: For example, laggedFib has a very real reason to implement popFrontN, as it can potentially pop thousands of elements at once in o(1). "Internal" mixin makes it easy to extend a PRNG's capabilities past that of the "lowest common denominator". With a "alias Random = RandomGenerator!RandomPayload", you are really limited to whatever RandomGenerator wrapped.

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

Honestly, it might just be the simplest thing to do. For one, it would elegantly solve the "must be seeded" issue (allocation is initialization). It *guarantees* Reference semantics. Finally, the (supposed) overhead should be inexistant compared to the compelxity of a PRNG.

The option of allowing "public Payload" definitions could still leave an open door for those that need PRNG's, but don't use the GC (think vidjagames).