You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kudu.apache.org by to...@apache.org on 2016/10/17 17:13:43 UTC
[2/2] kudu git commit: ITBLL: use a faster PRNG
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 <jd...@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 <to...@apache.org>
Authored: Thu Oct 13 22:24:51 2016 -0700
Committer: Todd Lipcon <to...@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