ITBLL: use a faster PRNG The SecureRandom PRNG is very very slow. Since we don't need cryptographic random numbers, we can use a simpler random. This switches to Xoroshiro128+, which is much faster but still has a long period (2^128) necessary to avoid collisions.
The implementation is from Squidlib[1] which is Apache licensed. The file itself has a license header indicating it is public domain. The original C implementation is also in the public domain[2]. Given that, I didn't reference this in LICENSE.txt or NOTICE. It's copy-pasted rather than introduced as a dependency because SquidLib is a library for writing turn-based games in Swing -- it just happens to have a good RNG in it. [1] https://github.com/SquidPony/SquidLib/blob/master/squidlib-util/src/main/java/squidpony/squidmath/XoRoRNG.java at revision b4fb31efe527d3298b8f37f3cc72e957579ad6e3 [2] http://xoroshiro.di.unimi.it/xoroshiro128plus.c Change-Id: I2f51664af25b9fb4309dd78556e954bf483d22c0 Reviewed-on: http://gerrit.cloudera.org:8080/4731 Tested-by: Kudu Jenkins Reviewed-by: Jean-Daniel Cryans <jdcry...@apache.org> Project: http://git-wip-us.apache.org/repos/asf/kudu/repo Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/0c44223e Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/0c44223e Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/0c44223e Branch: refs/heads/master Commit: 0c44223ea9e8561d9c48299007094f6f0d3f495f Parents: e5b7ebf Author: Todd Lipcon <t...@apache.org> Authored: Thu Oct 13 22:24:51 2016 -0700 Committer: Todd Lipcon <t...@apache.org> Committed: Mon Oct 17 17:13:25 2016 +0000 ---------------------------------------------------------------------- .../tools/IntegrationTestBigLinkedList.java | 47 +++++++++++++++++++- 1 file changed, 45 insertions(+), 2 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/kudu/blob/0c44223e/java/kudu-client-tools/src/main/java/org/apache/kudu/mapreduce/tools/IntegrationTestBigLinkedList.java ---------------------------------------------------------------------- diff --git a/java/kudu-client-tools/src/main/java/org/apache/kudu/mapreduce/tools/IntegrationTestBigLinkedList.java b/java/kudu-client-tools/src/main/java/org/apache/kudu/mapreduce/tools/IntegrationTestBigLinkedList.java index 7a2d6ac..5a0c0ea 100644 --- a/java/kudu-client-tools/src/main/java/org/apache/kudu/mapreduce/tools/IntegrationTestBigLinkedList.java +++ b/java/kudu-client-tools/src/main/java/org/apache/kudu/mapreduce/tools/IntegrationTestBigLinkedList.java @@ -304,6 +304,49 @@ public class IntegrationTestBigLinkedList extends Configured implements Tool { } /** + * Implementation of the Xoroshiro128+ PRNG. + * Copied under the public domain from SquidLib. + */ + private static class Xoroshiro128PlusRandom { + private long state0, state1; + public Xoroshiro128PlusRandom() { + this((long) (Math.random() * Long.MAX_VALUE)); + } + public Xoroshiro128PlusRandom(long seed) { + long state = seed + 0x9E3779B97F4A7C15L, + z = state; + z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; + z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; + state0 = z ^ (z >>> 31); + state += state0 + 0x9E3779B97F4A7C15L; + z = state; + z = (z ^ (z >>> 30)) * 0xBF58476D1CE4E5B9L; + z = (z ^ (z >>> 27)) * 0x94D049BB133111EBL; + state1 = z ^ (z >>> 31); + } + public long nextLong() { + final long s0 = state0; + long s1 = state1; + final long result = s0 + s1; + + s1 ^= s0; + state0 = Long.rotateLeft(s0, 55) ^ s1 ^ (s1 << 14); // a, b + state1 = Long.rotateLeft(s1, 36); // c + + return result; + } + public void nextBytes(final byte[] bytes) { + int i = bytes.length, n = 0; + while (i != 0) { + n = Math.min(i, 8); + for (long bits = nextLong(); n-- != 0; bits >>>= 8) { + bytes[--i] = (byte) bits; + } + } + } + } + + /** * A Map only job that generates random linked list and stores them. */ static class Generator extends Configured implements Tool { @@ -331,7 +374,7 @@ public class IntegrationTestBigLinkedList extends Configured implements Tool { static class GeneratorRecordReader extends RecordReader<BytesWritable,NullWritable> { private long count; private long numNodes; - private Random rand; + private Xoroshiro128PlusRandom rand; @Override public void close() throws IOException { @@ -359,7 +402,7 @@ public class IntegrationTestBigLinkedList extends Configured implements Tool { throws IOException, InterruptedException { numNodes = context.getConfiguration().getLong(GENERATOR_NUM_ROWS_PER_MAP_KEY, 25000000); // Use SecureRandom to avoid issue described in HBASE-13382. - rand = new SecureRandom(); + rand = new Xoroshiro128PlusRandom(); } @Override
