Repository: systemml Updated Branches: refs/heads/master 69ef76c06 -> 12ad5538a
[SYSTEMML-2379] Minor performance improvement sample w/o replacement This patch slightly improves the performance of moderately large sample w/o replacement operations. In detail, we now (1) avoid unnecessary nnz maintenance, (2) use direct array accesses, and (3) a forward instead of backward pass for random reshuffling. 1M x sample(1K, 1K): 26.3s -> 18.9s 100K x sample(10K, 10K): 20.8s -> 18.4s 10K x sample(100K, 100K): 22.7s -> 21.3s 1K x sample(1M, 1M): 26.9s -> 23.5s For larger sample operations (with outputs larger than L3 cache), the operation is mostly bound by random memory access latency. Project: http://git-wip-us.apache.org/repos/asf/systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/12ad5538 Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/12ad5538 Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/12ad5538 Branch: refs/heads/master Commit: 12ad5538a956359394251d6e105218515b19e3f4 Parents: 69ef76c Author: Matthias Boehm <[email protected]> Authored: Sun Jun 10 23:28:31 2018 -0700 Committer: Matthias Boehm <[email protected]> Committed: Sun Jun 10 23:28:51 2018 -0700 ---------------------------------------------------------------------- .../runtime/matrix/data/LibMatrixDatagen.java | 30 +++++++++----------- 1 file changed, 14 insertions(+), 16 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/systemml/blob/12ad5538/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixDatagen.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixDatagen.java b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixDatagen.java index fa47c37..c81427a 100644 --- a/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixDatagen.java +++ b/src/main/java/org/apache/sysml/runtime/matrix/data/LibMatrixDatagen.java @@ -387,41 +387,39 @@ public class LibMatrixDatagen public static void generateSample(MatrixBlock out, long range, int size, boolean replace, long seed) { //set meta data and allocate dense block out.reset(size, 1, false); - out.allocateDenseBlock(); - DenseBlock a = out.getDenseBlock(); + double[] a = out.allocateBlock().getDenseBlockValues(); seed = (seed == -1 ? System.nanoTime() : seed); if ( !replace ) { // reservoir sampling - for(int i=1; i <= size; i++) - a.set(i-1, 0, i ); + for(int i=0; i < size; i++) + a[i] = i + 1; Random rand = new Random(seed); for(int i=size+1; i <= range; i++) { if(rand.nextInt(i) < size) - a.set( rand.nextInt(size), 0, i ); + a[rand.nextInt(size)] = i; } // randomize the sample (Algorithm P from Knuth's ACP) - // -- needed especially when the differnce between range and size is small) - double tmp; - int idx; - for(int i=size-1; i >= 1; i--) { - idx = rand.nextInt(i); - // swap i^th and idx^th entries - tmp = a.get(idx, 0); - a.set(idx, 0, a.get(i, 0)); - a.set(i, 0, tmp); + // needed especially when the difference between range and size is small) + for( int i = 0; i < size-1; i++ ) { + //generate index in i <= j < size + int j = rand.nextInt(size - i) + i; + //swap i^th and j^th entry + double tmp = a[i]; + a[i] = a[j]; + a[j] = tmp; } } else { Random r = new Random(seed); for(int i=0; i < size; i++) - a.set(i, 0, 1+nextLong(r, range) ); + a[i] = 1+nextLong(r, range); } - out.recomputeNonZeros(); + out.setNonZeros(size); out.examSparsity(); }
