auto merge of #16965 : huonw/rust/isaac-oob--, r=alexcrichton

rand: inform the optimiser that indexing is never out-of-bounds.

This uses a bitwise mask to ensure that there's no bounds checking for
the array accesses when generating the next random number. This isn't
costless, but the single instruction is nothing compared to the branch.

A `debug_assert` for "bounds check" is preserved to ensure that
refactoring doesn't accidentally break it (i.e. create values of `cnt`
that are out of bounds with the masking causing it to silently wrap-
around).

Before:

test test::rand_isaac   ... bench: 990 ns/iter (+/- 24) = 808 MB/s
test test::rand_isaac64 ... bench: 614 ns/iter (+/- 25) = 1302 MB/s

After:

test test::rand_isaac   ... bench: 877 ns/iter (+/- 134) = 912 MB/s
test test::rand_isaac64 ... bench: 470 ns/iter (+/- 30) = 1702 MB/s

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

1 files changed, 18 insertions, 2 deletions

diff --git a/src/librand/isaac.rs b/src/librand/isaac.rs
index 0f7cda42a8a..871328e9c16 100644
--- a/src/librand/isaac.rs
+++ b/src/librand/isaac.rs
@@ -185,7 +185,19 @@ impl Rng for IsaacRng {
             self.isaac();
         }
         self.cnt -= 1;
-        self.rsl[self.cnt as uint]
+
+        // self.cnt is at most RAND_SIZE, but that is before the
+        // subtraction above. We want to index without bounds
+        // checking, but this could lead to incorrect code if someone
+        // misrefactors, so we check, sometimes.
+        //
+        // (Changes here should be reflected in Isaac64Rng.next_u64.)
+        debug_assert!(self.cnt < RAND_SIZE);
+
+        // (the % is cheaply telling the optimiser that we're always
+        // in bounds, without unsafe. NB. this is a power of two, so
+        // it optimises to a bitwise mask).
+        self.rsl[(self.cnt % RAND_SIZE) as uint]
     }
 }
 
@@ -416,7 +428,11 @@ impl Rng for Isaac64Rng {
             self.isaac64();
         }
         self.cnt -= 1;
-        unsafe { *self.rsl.unsafe_get(self.cnt) }
+
+        // See corresponding location in IsaacRng.next_u32 for
+        // explanation.
+        debug_assert!(self.cnt < RAND_SIZE_64)
+        self.rsl[(self.cnt % RAND_SIZE_64) as uint]
     }
 }