On Tuesday, 13 December 2016 at 18:15:25 UTC, Joseph Rushton
Wakeling wrote:
On Saturday, 26 November 2016 at 20:13:36 UTC, Andrei
Alexandrescu wrote:
Congrats! Also thanks for using the Boost license which would
allow backporting the improvements to Phobos. Who'd be up for
it?
I've finally found a moment to look into this (I'm at home
recovering from a seasonal virus, which ironically puts some
time and mental space in my hands).
It makes for an interesting comparison. The traditional
Mersenne Twister algorithm generates N random words in one go,
and then iterates over them, before generating another N random
words, and so on. (Word == unsigned integer type.)
By contrast Ilya's implementation just updates the single next
entry in the static array that stores the state of the engine.
This would seem to work out cheaper on average: perhaps because
the update-a-variate code stays hotter, perhaps because it
involves less branching and looping. It certainly makes for a
simpler, easier to follow update.
However, it might be a good idea to benchmark this in a context
where there are a lot of random variates being generated, but
where other things are also happening that might render the
update code less "hot" than a straightforward `foreach` loop
benchmark. (Maybe try it out with a Monte Carlo simulation
...?)
The tradeoff between many cheap updates and one expensive one,
versus all updates being a little more expensive but less on
average, might not be viable in some practical use-cases.
The Phobos implementation also includes a check on whether the
generator is properly seeded, which is performed in every
`popFront()`, which has a reasonably significant impact.
Ilya's implementation can get away with not performing that
check because it uses `@disable this();` to remove the
possibility of initializing the generator without it being
properly seeded. The impact of that check can possibly be
lessened by making it a boolean comparison rather than the
existing `size_t` equality comparison.
-- action item here: could we deprecate `this()` in Phobos as
a precursor to removing
the opportunity to instantiate a generator without
properly initializing it?
I'm going to try to put together a range-based version to see
if this also makes any difference. I'll post some benchmarks
of my own once that's done, and if all looks good I'll try to
put a Phobos PR together.
A few questions -- not blockers, but nice to understand:
* @Ilya, is this implementation your own design, or do you
have a reference
for the rationale behind this revised implementation of MT?
My own.
* Is there a particular reason why the `index` variable is a
`Uint` (i.e.
the word type of the generator) rather than a `size_t`? I
presume there's
a motivation, since the casting back and forth in `opCall`
would otherwise
seem inconvenient.
If I remember correctly it is used with Using, so I use the same
type.
* Is there a motivation for the reverse iteration through the
RNG state array?
Yes, it composes add/sub with cmp operations.
Ilya