Mir Random [WIP]

[Jonathan M Davis via Digitalmars-d]

On Friday, November 25, 2016 08:32:07 Joseph Rushton Wakeling via 
Digitalmars-d wrote:
> On Wednesday, 23 November 2016 at 21:19:51 UTC, Jonathan M Davis
>
> wrote:
> > It's quite feasible if you don't calculate front until it's
> > called or popFront is called, and then you cache the result so
> > that subsequent calls to front prior to the call to popFront
> > return the same result, but it creates additional overhead,
> > because then every call to front and popFront has to check
> > whether the value has been calculated yet. And if every range
> > in the chain of ranges has to do that, then that additional
> > overhead is going to add up.
>
> Yes, indeed.  I actually came up with a general purpose solution
> for that a while back via template mixin (although the version in
> the post linked to is not the final version: I updated it to use
> HaraldZealot's suggestion of making the frontImplementation and
> popFrontImplementation the template parameters):
> https://forum.dlang.org/post/mailman.263.1439926667.13986.digitalmars-d@pu
> remagic.com
> > In general, it's just cleaner to either calculate front on
> > every call to front (which doesn't make sense in the case of
> > random number generators) or to calculate the first front upon
> > construction and be done with it.
>
> In some ways I think it's cleaner to not privilege the first
> front value and go for "true" laziness for all front values --
> particularly when dealing with stuff like RandomSample.

It's much messier from an implementation standpoint. If the constructor
checks for empty and caches front if the range it was given was non-empty,
then every call to front can just return front, and every call to popFront
can just pop the element off and do whatever it does to turn the front from
the wrapped range into the front of this range and then cache it. If the
constructor doesn't do that work, then every call to front and every call to
popFront have to check whether they're the first time that either has been
called and _then_ they end up doing all of the same work anyway. So, there's
more code, and it's less efficient. And if every range in the chain does
that, then you're getting a lot of extra checks just to determine whether
it's the first time that front or popFront is being called. Now, if there's
never any caching of the front value, and front always calculates it, then
that might actually be more efficient if front is only ever called once per
element, because you don't get the cost of copying the element to cache it,
but if front gets called multiple times (which happens fairly often, I
think), then the cost is definitely greater.

You're never going to be able to rely on a fully lazy front anyway unless we
specified it as part of the range API that all ranges work that way, and as
it stands, very few ranges do.

> The downside is that `.front` becomes non-const.

Well, realistically, as it stands, ranges are utterly useless with const
anyway. We'd have to have a standard mechanism for getting a tail-const copy
of a range from a const or immutable range, and we don't.

> Sometimes I
> wonder whether it wouldn't have been better to require that
> `popFront()` be called before even the first call to `.front`,
> and place the onus on `popFront()` to handle any special-casing
> of the first `.front` value.

That would be terrible with chaining ranges. It also would be _very_
error-prone. It's also heading into two-phase initialization territory,
which is almost always a bad idea.

> > And I think that the general consensus has been that
> > calculating front in the constructor and popFront and caching
> > works better than calculating it on every call to front, but
> > that doesn't always work (e.g. map), and that caching does
> > cause issues occasionally.
>
> The case I always think of is: what if your input range is
> designed to correspond to sensor observations made at a
> particular time?  This is a case where cacheing the first value
> on construction is very problematic.
>
> For RNGs it's really not such a big deal so long as successive
> variates are independent, but for random algorithms I think the
> laziness matters, since their popFront is essentially
> IO-dependent (in the Haskell-style sense that randomness is IO).

Honestly, I don't think that it really works to have a range where the value
of its elements depend on when you call front or popFront. The API lets you
do it, but you're going to run into plenty of problems if you do unless you
don't care about the frequency at which the values are generated. Part of
the problem here is that ranges and the algorithms that use them are really
designed with arrays in mind. A non-random-access range reduces those
capabilities, and a basic input range doesn't actually require that the
elements be reproducible aside from multiple calls to front giving the same
result, but it's still the case that it's pretty much assumed that a range
is a fixed set of values, and pretty much nothing is concerned with how fast
front or popFront is called aside for efficiency concerns. So, if someone
has a range that calculates a value when front or popFront is called, and
that value depends on when the function is called, I think that they're just
going to have to deal with the consequences of that. It's already pretty
problematic when you have a range that's a basic input range rather than a
forward range.

Another thing to consider here is that those sorts of concerns really only
apply to basic input ranges. As soon as you have a forward range, the values
of the elements need to be completely predictable - or at least completely
reproducible - meaning that aside from caching a potentially infinite number
of elements to guarantee that save works, nothing that's doing something
like grabbing changing values from a sensor is going to be anything but a
basic input range. So, maybe we should do something special with regards to
basic input ranges and how they're treated in order to better deal with
cases like that, but if we went that route, then we pretty much couldn't
treat them like forward ranges without save anymore. In many cases, we'd
have to have separate implementations that avoided things like caching, and
that would become problematic fast.

I think that there always going to be cases where certain things have some
funky corner cases with ranges - especially the further that they get from
being dynamic arrays. We probably need to do a better job of formalizing
some of this stuff to better avoid some of those corner cases, but I think
that we're always going to be able to find something that we can define as a
range that works in many cases but starts doing weird things if we use it on
a large enough range of algorithms.

- Jonathan M Davis