You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2017/11/17 06:33:42 UTC
systemml git commit: [SYSTEMML-2015] Performance ctable operations
(entries, rehashing)
Repository: systemml
Updated Branches:
refs/heads/master 2ae07e9ce -> f0e369407
[SYSTEMML-2015] Performance ctable operations (entries, rehashing)
This patch makes three performance improvements to ctable operations
with unknown output size or sparse output, which both rely on
hash-group-by operations.
(1) The dedicated ctable hashmap (with memory efficient entries) is used
in both CP and distributed operations and hence uses long keys by
default. This patch generalizes this hashmap to work with either int or
long keys, which improves the memory-efficiency (and thus cache behavior
for many groups) in CP.
(2) Furthermore, we now pre-allocate sparse output rows accordingly to
the average nnz per row, which we derive from the exact number of groups
encountered in the data (hashmap size).
(3) So far we used the externalized addValue for rehashing purposes as
well. However this created unnecessary garbage collection overhead due
to repeated object creation of entries. In contrast, we now use a
dedicated code path for rehashing which allows to reuse existing
entries.
On a scenario of 3 dense 10M x 1 input vectors X, Y, Z with X having
100K distinct values and Y having 10K distinct values and an output size
of 10M groups, this patch improved the runtime of 20 iterations of
table(X, Y, Z, max(X), max(Y)) from 50.5s (17.4s GC) to 32.6s (2.7s GC).
Project: http://git-wip-us.apache.org/repos/asf/systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/systemml/commit/f0e36940
Tree: http://git-wip-us.apache.org/repos/asf/systemml/tree/f0e36940
Diff: http://git-wip-us.apache.org/repos/asf/systemml/diff/f0e36940
Branch: refs/heads/master
Commit: f0e369407b9cd73157d80319e9f0121f22eb8ca0
Parents: 2ae07e9
Author: Matthias Boehm <mb...@gmail.com>
Authored: Thu Nov 16 21:45:18 2017 -0800
Committer: Matthias Boehm <mb...@gmail.com>
Committed: Thu Nov 16 22:34:09 2017 -0800
----------------------------------------------------------------------
.../instructions/cp/TernaryCPInstruction.java | 3 +-
.../spark/TernarySPInstruction.java | 10 +-
.../sysml/runtime/matrix/data/CTableMap.java | 45 ++++---
.../runtime/matrix/mapred/GMRCtableBuffer.java | 8 +-
.../runtime/util/LongLongDoubleHashMap.java | 123 ++++++++++++++-----
.../functions/sparse/SparseBlockAppendSort.java | 8 +-
.../functions/sparse/SparseBlockGetSet.java | 8 +-
7 files changed, 135 insertions(+), 70 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/main/java/org/apache/sysml/runtime/instructions/cp/TernaryCPInstruction.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/instructions/cp/TernaryCPInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/cp/TernaryCPInstruction.java
index 6d42976..34a260a 100644
--- a/src/main/java/org/apache/sysml/runtime/instructions/cp/TernaryCPInstruction.java
+++ b/src/main/java/org/apache/sysml/runtime/instructions/cp/TernaryCPInstruction.java
@@ -31,6 +31,7 @@ import org.apache.sysml.runtime.matrix.data.MatrixBlock;
import org.apache.sysml.runtime.matrix.operators.Operator;
import org.apache.sysml.runtime.matrix.operators.SimpleOperator;
import org.apache.sysml.runtime.util.DataConverter;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.EntryType;
public class TernaryCPInstruction extends ComputationCPInstruction {
private final String _outDim1;
@@ -97,7 +98,7 @@ public class TernaryCPInstruction extends ComputationCPInstruction {
MatrixBlock matBlock2=null, wtBlock=null;
double cst1, cst2;
- CTableMap resultMap = new CTableMap();
+ CTableMap resultMap = new CTableMap(EntryType.INT);
MatrixBlock resultBlock = null;
Ternary.OperationTypes ctableOp = findCtableOperation();
ctableOp = _isExpand ? Ternary.OperationTypes.CTABLE_EXPAND_SCALAR_WEIGHT : ctableOp;
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/main/java/org/apache/sysml/runtime/instructions/spark/TernarySPInstruction.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/instructions/spark/TernarySPInstruction.java b/src/main/java/org/apache/sysml/runtime/instructions/spark/TernarySPInstruction.java
index 4ef5109..5629076 100644
--- a/src/main/java/org/apache/sysml/runtime/instructions/spark/TernarySPInstruction.java
+++ b/src/main/java/org/apache/sysml/runtime/instructions/spark/TernarySPInstruction.java
@@ -50,7 +50,7 @@ import org.apache.sysml.runtime.matrix.data.Pair;
import org.apache.sysml.runtime.matrix.mapred.IndexedMatrixValue;
import org.apache.sysml.runtime.matrix.operators.Operator;
import org.apache.sysml.runtime.matrix.operators.SimpleOperator;
-import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
import org.apache.sysml.runtime.util.UtilFunctions;
public class TernarySPInstruction extends ComputationSPInstruction {
@@ -459,11 +459,11 @@ public class TernarySPInstruction extends ComputationSPInstruction {
public Iterator<Tuple2<MatrixIndexes, Double>> call(CTableMap ctableMap)
throws Exception {
ArrayList<Tuple2<MatrixIndexes, Double>> retVal = new ArrayList<>();
- Iterator<LLDoubleEntry> iter = ctableMap.getIterator();
+ Iterator<ADoubleEntry> iter = ctableMap.getIterator();
while( iter.hasNext() ) {
- LLDoubleEntry ijv = iter.next();
- long i = ijv.key1;
- long j = ijv.key2;
+ ADoubleEntry ijv = iter.next();
+ long i = ijv.getKey1();
+ long j = ijv.getKey2();
double v = ijv.value;
retVal.add(new Tuple2<>(new MatrixIndexes(i, j), v));
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/main/java/org/apache/sysml/runtime/matrix/data/CTableMap.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/CTableMap.java b/src/main/java/org/apache/sysml/runtime/matrix/data/CTableMap.java
index f93bace..b5e5e5a 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/CTableMap.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/CTableMap.java
@@ -22,7 +22,8 @@ package org.apache.sysml.runtime.matrix.data;
import java.util.Iterator;
import org.apache.sysml.runtime.util.LongLongDoubleHashMap;
-import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.EntryType;
/**
* Ctable map is an abstraction for the hashmap used for ctable's hash group-by
@@ -33,21 +34,25 @@ import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
*/
public class CTableMap
{
- private LongLongDoubleHashMap _map = null;
+ private final LongLongDoubleHashMap _map;
private long _maxRow = -1;
private long _maxCol = -1;
public CTableMap() {
- _map = new LongLongDoubleHashMap();
+ this(EntryType.LONG);
+ }
+
+ public CTableMap(EntryType type) {
+ _map = new LongLongDoubleHashMap(type);
_maxRow = -1;
_maxCol = -1;
}
-
+
public int size() {
return _map.size();
}
- public Iterator<LLDoubleEntry> getIterator() {
+ public Iterator<ADoubleEntry> getIterator() {
return _map.getIterator();
}
@@ -73,35 +78,39 @@ public class CTableMap
{
//allocate new matrix block
int nnz = _map.size();
- boolean sparse = MatrixBlock.evalSparseFormatInMemory(rlen, clen, nnz);
- MatrixBlock mb = new MatrixBlock(rlen, clen, sparse, nnz);
+ boolean sparse = MatrixBlock.evalSparseFormatInMemory(rlen, clen, nnz);
+ MatrixBlock mb = new MatrixBlock(rlen, clen, sparse, nnz).allocateBlock();
// copy map values into new matrix block
if( sparse ) //SPARSE <- cells
{
- //append cells to sparse target (prevent shifting)
- Iterator<LLDoubleEntry> iter2 = _map.getIterator();
+ //append cells to sparse target (unordered to avoid shifting)
+ SparseBlock sblock = mb.getSparseBlock();
+ Iterator<ADoubleEntry> iter2 = _map.getIterator();
while( iter2.hasNext() ) {
- LLDoubleEntry e = iter2.next();
+ ADoubleEntry e = iter2.next();
double value = e.value;
- int rix = (int)e.key1;
- int cix = (int)e.key2;
- if( value != 0 && rix<=rlen && cix<=clen )
- mb.appendValue( rix-1, cix-1, value );
+ int rix = (int)e.getKey1();
+ int cix = (int)e.getKey2();
+ if( value != 0 && rix<=rlen && cix<=clen ) {
+ sblock.allocate(rix-1, Math.max(nnz/rlen,1));
+ sblock.append( rix-1, cix-1, value );
+ }
}
//sort sparse target representation
mb.sortSparseRows();
+ mb.recomputeNonZeros();
}
else //DENSE <- cells
{
//directly insert cells into dense target
- Iterator<LLDoubleEntry> iter = _map.getIterator();
+ Iterator<ADoubleEntry> iter = _map.getIterator();
while( iter.hasNext() ) {
- LLDoubleEntry e = iter.next();
+ ADoubleEntry e = iter.next();
double value = e.value;
- int rix = (int)e.key1;
- int cix = (int)e.key2;
+ int rix = (int)e.getKey1();
+ int cix = (int)e.getKey2();
if( value != 0 && rix<=rlen && cix<=clen )
mb.quickSetValue( rix-1, cix-1, value );
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/main/java/org/apache/sysml/runtime/matrix/mapred/GMRCtableBuffer.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/mapred/GMRCtableBuffer.java b/src/main/java/org/apache/sysml/runtime/matrix/mapred/GMRCtableBuffer.java
index 3c682ce..eba98ad 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/mapred/GMRCtableBuffer.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/mapred/GMRCtableBuffer.java
@@ -33,7 +33,7 @@ import org.apache.sysml.runtime.matrix.data.CTableMap;
import org.apache.sysml.runtime.matrix.data.MatrixBlock;
import org.apache.sysml.runtime.matrix.data.MatrixCell;
import org.apache.sysml.runtime.matrix.data.MatrixIndexes;
-import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
public class GMRCtableBuffer
@@ -129,10 +129,10 @@ public class GMRCtableBuffer
}
//output result data
- Iterator<LLDoubleEntry> iter = resultMap.getIterator();
+ Iterator<ADoubleEntry> iter = resultMap.getIterator();
while( iter.hasNext() ) {
- LLDoubleEntry e = iter.next();
- key = new MatrixIndexes(e.key1, e.key2);
+ ADoubleEntry e = iter.next();
+ key = new MatrixIndexes(e.getKey1(), e.getKey2());
value.setValue(e.value);
for(Integer i: resultIDs)
_collector.collectOutput(key, value, i, reporter);
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java b/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
index 4c1cc0e..93ea7f8 100644
--- a/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
+++ b/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
@@ -29,18 +29,27 @@ import java.util.Iterator;
* to keep data in the caches and prevent high-latency random memory access.
*
*/
-public class LongLongDoubleHashMap
+public class LongLongDoubleHashMap
{
private static final int INIT_CAPACITY = 8;
private static final int RESIZE_FACTOR = 2;
private static final float LOAD_FACTOR = 0.75f;
- private LLDoubleEntry[] data = null;
+ public enum EntryType {
+ LONG, INT
+ }
+
+ private final EntryType type;
+ private ADoubleEntry[] data = null;
private int size = -1;
- public LongLongDoubleHashMap()
- {
- data = new LLDoubleEntry[INIT_CAPACITY];
+ public LongLongDoubleHashMap() {
+ this(EntryType.LONG);
+ }
+
+ public LongLongDoubleHashMap(EntryType etype) {
+ type = etype;
+ data = new ADoubleEntry[INIT_CAPACITY];
size = 0;
}
@@ -51,19 +60,20 @@ public class LongLongDoubleHashMap
public void addValue(long key1, long key2, double value)
{
//compute entry index position
- int hash = hash(key1, key2);
- int ix = indexFor(hash, data.length);
-
+ int ix = getIndex(key1, key2, data.length);
+
//find existing entry and add value
- for( LLDoubleEntry e = data[ix]; e!=null; e = e.next ) {
- if( e.key1==key1 && e.key2==key2 ) {
+ for( ADoubleEntry e = data[ix]; e!=null; e = e.next ) {
+ if( e.getKey1()==key1 && e.getKey2()==key2 ) {
e.value += value;
return; //no need to append or resize
}
}
//add non-existing entry (constant time)
- LLDoubleEntry enew = new LLDoubleEntry(key1, key2, value);
+ ADoubleEntry enew = (type==EntryType.LONG) ?
+ new LLDoubleEntry(key1, key2, value) :
+ new IIDoubleEntry(key1, key2, value);
enew.next = data[ix]; //colliding entries / null
data[ix] = enew;
size++;
@@ -72,9 +82,9 @@ public class LongLongDoubleHashMap
if( size >= LOAD_FACTOR*data.length )
resize();
}
-
- public Iterator<LLDoubleEntry> getIterator() {
- return new LLDoubleEntryIterator();
+
+ public Iterator<ADoubleEntry> getIterator() {
+ return new ADoubleEntryIterator();
}
private void resize() {
@@ -83,22 +93,38 @@ public class LongLongDoubleHashMap
return;
//resize data array and copy existing contents
- LLDoubleEntry[] olddata = data;
- data = new LLDoubleEntry[data.length*RESIZE_FACTOR];
+ ADoubleEntry[] olddata = data;
+ data = new ADoubleEntry[data.length*RESIZE_FACTOR];
size = 0;
- //rehash all entries
- for( LLDoubleEntry e : olddata ) {
+ //rehash all entries with reuse of existing entries
+ for( ADoubleEntry e : olddata ) {
if( e != null ) {
while( e.next!=null ) {
- addValue(e.key1, e.key2, e.value);
- e = e.next;
+ ADoubleEntry tmp = e;
+ e = e.next; //tmp.next overwritten on append
+ appendEntry(e.getKey1(), e.getKey2(), tmp);
}
- addValue(e.key1, e.key2, e.value);
+ appendEntry(e.getKey1(), e.getKey2(), e);
}
}
}
-
+
+ private void appendEntry(long key1, long key2, ADoubleEntry e) {
+ //compute entry index position
+ int ix = getIndex(key1, key2, data.length);
+
+ //add existing entry (constant time)
+ e.next = data[ix]; //colliding entries / null
+ data[ix] = e;
+ size++;
+ }
+
+ private static int getIndex(long key1, long key2, int length) {
+ int hash = hash(key1, key2);
+ return indexFor(hash, length);
+ }
+
private static int hash(long key1, long key2) {
int h = UtilFunctions.longHashCode(key1, key2);
@@ -113,25 +139,54 @@ public class LongLongDoubleHashMap
return h & (length-1);
}
- public class LLDoubleEntry {
- public long key1 = Long.MAX_VALUE;
- public long key2 = Long.MAX_VALUE;
+ public static abstract class ADoubleEntry {
public double value = Double.MAX_VALUE;
- public LLDoubleEntry next = null;
-
+ public ADoubleEntry next = null;
+ public ADoubleEntry(double val) {
+ value = val;
+ next = null;
+ }
+ public abstract long getKey1();
+ public abstract long getKey2();
+ }
+
+ private static class LLDoubleEntry extends ADoubleEntry {
+ private final long key1;
+ private final long key2;
public LLDoubleEntry(long k1, long k2, double val) {
+ super(val);
key1 = k1;
key2 = k2;
- value = val;
- next = null;
+ }
+ public long getKey1() {
+ return key1;
+ }
+ public long getKey2() {
+ return key2;
+ }
+ }
+
+ private static class IIDoubleEntry extends ADoubleEntry {
+ private final int key1;
+ private final int key2;
+ public IIDoubleEntry(long k1, long k2, double val) {
+ super(val);
+ key1 = (int)k1;
+ key2 = (int)k2;
+ }
+ public long getKey1() {
+ return key1;
+ }
+ public long getKey2() {
+ return key2;
}
}
- private class LLDoubleEntryIterator implements Iterator<LLDoubleEntry> {
- private LLDoubleEntry _curr;
+ private class ADoubleEntryIterator implements Iterator<ADoubleEntry> {
+ private ADoubleEntry _curr;
private int _currPos;
- public LLDoubleEntryIterator() {
+ public ADoubleEntryIterator() {
_curr = null;
_currPos = -1;
findNext();
@@ -143,8 +198,8 @@ public class LongLongDoubleHashMap
}
@Override
- public LLDoubleEntry next() {
- LLDoubleEntry ret = _curr;
+ public ADoubleEntry next() {
+ ADoubleEntry ret = _curr;
findNext();
return ret;
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockAppendSort.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockAppendSort.java b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockAppendSort.java
index 4705e4a..11038e1 100644
--- a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockAppendSort.java
+++ b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockAppendSort.java
@@ -29,7 +29,7 @@ import org.apache.sysml.runtime.matrix.data.SparseBlockCOO;
import org.apache.sysml.runtime.matrix.data.SparseBlockCSR;
import org.apache.sysml.runtime.matrix.data.SparseBlockMCSR;
import org.apache.sysml.runtime.util.LongLongDoubleHashMap;
-import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
import org.apache.sysml.test.integration.AutomatedTestBase;
import org.apache.sysml.test.utils.TestUtils;
@@ -178,10 +178,10 @@ public class SparseBlockAppendSort extends AutomatedTestBase
for( int i=0; i<rows; i++ )
for( int j=0; j<cols; j++ )
map.addValue(i, j, A[i][j]);
- Iterator<LLDoubleEntry> iter = map.getIterator();
+ Iterator<ADoubleEntry> iter = map.getIterator();
while( iter.hasNext() ) { //random hash order
- LLDoubleEntry e = iter.next();
- sblock.append((int)e.key1, (int)e.key2, e.value);
+ ADoubleEntry e = iter.next();
+ sblock.append((int)e.getKey1(), (int)e.getKey2(), e.value);
}
}
http://git-wip-us.apache.org/repos/asf/systemml/blob/f0e36940/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockGetSet.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockGetSet.java b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockGetSet.java
index 6f84637..e8cbaa8 100644
--- a/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockGetSet.java
+++ b/src/test/java/org/apache/sysml/test/integration/functions/sparse/SparseBlockGetSet.java
@@ -31,7 +31,7 @@ import org.apache.sysml.runtime.matrix.data.SparseBlockCSR;
import org.apache.sysml.runtime.matrix.data.SparseBlockMCSR;
import org.apache.sysml.runtime.util.DataConverter;
import org.apache.sysml.runtime.util.LongLongDoubleHashMap;
-import org.apache.sysml.runtime.util.LongLongDoubleHashMap.LLDoubleEntry;
+import org.apache.sysml.runtime.util.LongLongDoubleHashMap.ADoubleEntry;
import org.apache.sysml.test.integration.AutomatedTestBase;
import org.apache.sysml.test.utils.TestUtils;
@@ -236,10 +236,10 @@ public class SparseBlockGetSet extends AutomatedTestBase
for( int i=0; i<rows; i++ )
for( int j=0; j<cols; j++ )
map.addValue(i, j, A[i][j]);
- Iterator<LLDoubleEntry> iter = map.getIterator();
+ Iterator<ADoubleEntry> iter = map.getIterator();
while( iter.hasNext() ) { //random hash order
- LLDoubleEntry e = iter.next();
- sblock.set((int)e.key1, (int)e.key2, e.value);
+ ADoubleEntry e = iter.next();
+ sblock.set((int)e.getKey1(), (int)e.getKey2(), e.value);
}
}
}