Repository navigation
Optimise IteratorRandom::choose for size_hint or ExactSizeIterator #511
Description
IteratorRandom::choose uses one random number per item since it has no way of knowing how many items will follow.
We do not use size_hint since it is not guaranteed that the supplied bounds are correct; though since incorrect implementations are considered buggy we could try.
Alternatively ExactSizeIterator could be used, but probably not without specialisation.
Activity
sicking commentedon Jul 23, 2018
Opinions on what we should do if
size_hintis buggy? Should we reliably panic? Is return a "wrong" value ok?So for example, a simple implementation strategy would be to check if
size_hintreturns(N, Some(N)), and if so simply returnself.nth(rng.gen_range(0, N)). However that would return the "wrong" value rather than panic if thesize_hintimplementation was buggy.dhardy commentedon Jul 24, 2018
To quote the doc:
Beyond that there's not much guidance; i.e. I think it should be acceptable to return "incorrect" results if
size_hintis incorrect so long as the return value is eitherNoneorSome(x)wherexis a result of the iterator.nagisa commentedon Jul 24, 2018
There’s an exception for
ExactSizeIterator, but otherwise, yes, thesize_hintmay return whatever :)dhardy commentedon Jul 24, 2018
Yes, but does "may return whatever" mean:
size_hintmay never affect the result in any way (including bias); i.e. can only be used to optimise memory allocationssize_hint's maximum is too low, the result may ignore all values beyond the maximum, but must otherwise be correct and must be memory safeNoneifsize_hint's maximum is too highsize_hintis incorrect, users may do the wrong thing so long as they are memory-safenagisa commentedon Jul 24, 2018
There are no restrictions to
size_hint. Even if thesize_hintis "incorrect", or rather… inaccurate, the algorithm should work correctly as observed at the call boundary. Consider for examplecollect()on iterators. Usingsize_hint, the collection may attempt to pre-allocate some amount of storage, but if the hint (and therefore allocation) turned out to be too small, it will have to re-allocate more memory later on.So, while, there is a side-effect to using
size_hint, but it is not reasonably visible to the end user.For
IteratorRandom::chooseprobably a sufficient rule would be this:Given a deterministic backing random number generator (
r) initialized with with some well known seed, and two different implementations ofIteratorforI1andI2(that differ only in their implementation ofsize_hint), a call to<I1 as IteratorRandom>::choose(r)and<I2 as IteratorRandom>::choose(r)should:nextmethod the same number of times);nagisa commentedon Jul 24, 2018
Ultimately, however, it is up to you to decide what the semantics are when
size_hintreturns different values. You could as well just specify (in the documentation), thatsize_hintmay affect the outcome of the function, which is fine.sicking commentedon Jul 24, 2018
If we have the above requirement I don't see that we could take advantage of
size_hintto improve performance. I'll defer to @dhardy and @pitdicker.But we can always wait until specialization stabilizes and use
ExactSizeIterator.dhardy commentedon Jul 24, 2018
I suppose those constraints are necessary to avoid a change in
size_hintimplementation from affecting results in a supposedly reproducible application. Currently, reproducibility requires pinning the version of the Rand crate; optimising viasize_hintwould essentially mean the version of other crates may need to be pinned too. I'm not really sure we can get away from that anyway though.The alternative is just to point out that the implementation of
size_hintmay affect the effect of this function in documentation, as @nagisa suggests. To me this seems the more attractive option since the performance impact could be quite significant, reproducibility is less often required (especially when sampling from an iterator I think), and in any case maintaining reproducibility is a subtle thing.sicking commentedon Jul 25, 2018
I agree that pointing out that
size_hintwill affect reproducibility feels more attractive. Though we need to make it clear that that's the case even whensize_hintchanges from one valid implementation to another.Likewise to point out that
choosedepends onsize_hint, and so if ifsize_hinthas a buggy implementation, then the return values fromchoosewill not be dependable and could even panic. Though it will never result in UB.If there's agreement that that's ok, then I'm happy to write up a PR?
dhardy commentedon Jul 25, 2018
I don't think it needs to panic, but I think it's acceptable to introduce bias in the output (i.e. select some element as a fallback in case the iterator is not as long as
size_hintsays it is), or perhaps even returnNonein this case.Perhaps though we should bring this up elsewhere to get more opinions. I don't really know where people might write incorrect
size_hintimplementations.dhardy commentedon Jul 25, 2018
See: https://internals.rust-lang.org/t/size-hint-correctness-reproducibility-and-documentation/8058
dhardy commentedon Jul 31, 2018
@sicking the answer seems to be that we're allowed to break things if
size_hintis incorrect: https://internals.rust-lang.org/t/size-hint-correctness-reproducibility-and-documentation/8058/6?u=dhardy