rust-lang/rust — pull request #16965 by huonw (2014-09-03 13:26:47+00:00)
Title: rand: remove bounds checks in Isaac*Rng.next_* via good type choice.

Choose a small type such that range(type) = domain(array) (regarding an
array as a function) so that the optimiser can see that there is no
possibility of an out of bounds access.

Performing this change loses space for the extra index value used inside
the isaac routine, and so requires some changes from the published ISAAC
algorithm. The result is this implementation departs from the canonical
one very slightly, but only in the sense that the internal state can be
different at certain points, the output stream is identical. (To be
sure: you can check the test verifying the stream is not touched in this
changeset, and that it still passes.)

What's the point of all this? A 10-15% speed-up in generation speed:

Before:

test rand_isaac ... bench: 1014 ns/iter (+/- 47) = 788 MB/s
test rand_isaac64 ... bench: 609 ns/iter (+/- 11) = 1313 MB/s

After:

test rand_isaac ... bench: 866 ns/iter (+/- 47) = 923 MB/s
test rand_isaac64 ... bench: 497 ns/iter (+/- 33) = 1609 MB/s

(It also removes the `unsafe` code in `Isaac64Rng.next_u64`, with
a *gain* in performance; today is a good day.)