This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push:
new ea2d971 [SYSTEMDS-274] Fix compressed colMins/colMaxs w/ shared
dictionary
ea2d971 is described below
commit ea2d971ec4ad3a0cf93fe78224a6f14176a6235b
Author: Matthias Boehm <mboe...@gmail.com>
AuthorDate: Sun May 31 18:26:55 2020 +0200
[SYSTEMDS-274] Fix compressed colMins/colMaxs w/ shared dictionary
This patch fixes remaining issues of incorrect results for colMins and
colMaxs over compressed matrix blocks with shared DDC1 dictionaries.
Specifically, if the individual column groups have only partial overlap,
the shared dictionary contains a superset of column group distinct
values. Since aggregation functions like min and max are executed only
over the dictionary (without touching the compressed data), it led to
incorrect results as we find extreme values that do not actually exist
in the column group.
Three alternatives approaches could solve this: (1) drop shared
dictionaries, (2) execute colMins and colMax over the compressed data,
or (3) refactor the double array dictionary into a proper class
hierarchy and maintain additional meta data for shared dictionaries. We
decided for (3) in order to keep predictable performance, irrespective
of shared dictionaries and because this class hierarchy allows for
further improvements of shared dictionaries between any subsets of
column groups.
Additionally, this fix also cleanups incorrect estimates of the
individual column groups (because getValueSize was used in the estimates
as a number of values, although it gave the size in bytes) as well as
some of the Class-layout size estimation tests.
Closes #927.
---
dev/docs/Tasks.txt | 2 +-
.../runtime/compress/CompressedMatrixBlock.java | 5 +-
.../compress/CompressedMatrixBlockFactory.java | 59 ++++++----
.../sysds/runtime/compress/colgroup/ColGroup.java | 7 --
.../runtime/compress/colgroup/ColGroupDDC.java | 7 +-
.../runtime/compress/colgroup/ColGroupDDC1.java | 34 +++---
.../runtime/compress/colgroup/ColGroupDDC2.java | 39 ++++---
.../runtime/compress/colgroup/ColGroupOLE.java | 33 ++++--
.../runtime/compress/colgroup/ColGroupOffset.java | 43 ++++---
.../runtime/compress/colgroup/ColGroupRLE.java | 30 +++--
.../runtime/compress/colgroup/ColGroupSizes.java | 3 +-
.../runtime/compress/colgroup/ColGroupValue.java | 126 ++++++++-------------
.../runtime/compress/colgroup/Dictionary.java | 96 ++++++++++++++++
.../compress/colgroup/DictionaryShared.java | 79 +++++++++++++
.../component/compress/CompressedMatrixTest.java | 10 +-
.../component/compress/CompressedTestBase.java | 7 +-
.../compress/colgroup/JolEstimateTest.java | 8 +-
.../compress/colgroup/JolEstimateTestEmpty.java | 6 +-
18 files changed, 398 insertions(+), 196 deletions(-)
diff --git a/dev/docs/Tasks.txt b/dev/docs/Tasks.txt
index cd90a66..6b5dbb0 100644
--- a/dev/docs/Tasks.txt
+++ b/dev/docs/Tasks.txt
@@ -223,7 +223,7 @@ SYSTEMDS-270 Compressed Matrix Blocks
* 272 Simplify and speedup compression tests OK
* 273 Refactor compressed Matrix Block to simplify responsibilities OK
* 273a Redesign allocation of ColGroups in ColGroupFactory
- * 274 Make the DDC Compression dictionary share correctly
+ * 274 Make the DDC Compression dictionary share correctly OK
* 275 Include compressionSettings in DMLConfiguration
* 276 Allow Uncompressed Columns to be in sparse formats
* 277 Sampling based estimators fix
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlock.java
b/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlock.java
index 3ad65c5..1085afc 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlock.java
@@ -243,9 +243,10 @@ public class CompressedMatrixBlock extends
AbstractCompressedMatrixBlock {
if(_sharedDDC1Dict) {
boolean seenDDC1 = false;
for(ColGroup grp : _colGroups)
- if(grp.getNumCols() == 1 && grp.getCompType()
== CompressionType.DDC) {
+ if(grp.getNumCols() == 1 && grp instanceof
ColGroupDDC1) {
+ ColGroupDDC1 grpDDC = (ColGroupDDC1)
grp;
if(seenDDC1)
- total -= grp.getValuesSize();
+ total -=
grpDDC.getDictionarySize();
seenDDC1 = true;
}
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlockFactory.java
b/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlockFactory.java
index 9ee52ed..fdac0d3 100644
---
a/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlockFactory.java
+++
b/src/main/java/org/apache/sysds/runtime/compress/CompressedMatrixBlockFactory.java
@@ -22,6 +22,7 @@ package org.apache.sysds.runtime.compress;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
+import java.util.Map.Entry;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
@@ -33,6 +34,8 @@ import org.apache.sysds.runtime.compress.colgroup.ColGroup;
import org.apache.sysds.runtime.compress.colgroup.ColGroup.CompressionType;
import org.apache.sysds.runtime.compress.colgroup.ColGroupDDC1;
import org.apache.sysds.runtime.compress.colgroup.ColGroupFactory;
+import org.apache.sysds.runtime.compress.colgroup.Dictionary;
+import org.apache.sysds.runtime.compress.colgroup.DictionaryShared;
import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimator;
import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorFactory;
import org.apache.sysds.runtime.compress.estim.CompressedSizeInfo;
@@ -164,8 +167,7 @@ public class CompressedMatrixBlockFactory {
// --------------------------------------------------
// PHASE 4: Best-effort dictionary sharing for DDC1 single-col
groups
- // TODO FIX DDC Sharing
- double[] dict =
(!(compSettings.validCompressions.contains(CompressionType.DDC)) ||
+ Dictionary dict =
(!(compSettings.validCompressions.contains(CompressionType.DDC)) ||
!(compSettings.allowSharedDDCDictionary)) ? null :
createSharedDDC1Dictionary(colGroupList);
if(dict != null) {
applySharedDDC1Dictionary(colGroupList, dict);
@@ -215,44 +217,63 @@ public class CompressedMatrixBlockFactory {
/**
* Dictionary sharing between DDC ColGroups.
*
- * FYI DOES NOT WORK FOR ALL CASES!
* @param colGroups The List of all ColGroups.
* @return the shared value list for the DDC ColGroups.
*/
- private static double[] createSharedDDC1Dictionary(List<ColGroup>
colGroups) {
+ private static Dictionary createSharedDDC1Dictionary(List<ColGroup>
colGroups) {
// create joint dictionary
- HashSet<Double> tmp = new HashSet<>();
- int numQual = 0;
+ HashSet<Double> vals = new HashSet<>();
+ HashMap<Integer, Double> mins = new HashMap<>();
+ HashMap<Integer, Double> maxs = new HashMap<>();
+ int numDDC1 = 0;
for(final ColGroup grp : colGroups)
if(grp.getNumCols() == 1 && grp instanceof
ColGroupDDC1) {
final ColGroupDDC1 grpDDC1 = (ColGroupDDC1) grp;
- for(final double val : grpDDC1.getValues())
- tmp.add(val);
- numQual++;
+ final double[] values = grpDDC1.getValues();
+ double min = Double.POSITIVE_INFINITY;
+ double max = Double.NEGATIVE_INFINITY;
+ for(int i=0; i<values.length; i++) {
+ vals.add(values[i]);
+ min = Math.min(min, values[i]);
+ max = Math.max(max, values[i]);
+ }
+ mins.put(grpDDC1.getColIndex(0), min);
+ maxs.put(grpDDC1.getColIndex(0), max);
+ numDDC1++;
}
// abort shared dictionary creation if empty or too large
- int maxSize = tmp.contains(0d) ? 256 : 255;
- if(tmp.isEmpty() || tmp.size() > maxSize || numQual < 2)
+ int maxSize = vals.contains(0d) ? 256 : 255;
+ if(numDDC1 < 2 || vals.size() > maxSize)
return null;
- LOG.debug("Created shared directionary for " + numQual + " DDC1
single column groups.");
- // build consolidated dictionary
- return tmp.stream().mapToDouble(Double::doubleValue).toArray();
+ // build consolidated shared dictionary
+ double[] values =
vals.stream().mapToDouble(Double::doubleValue).toArray();
+ int[] colIndexes = new int[numDDC1];
+ double[] extrema = new double[2*numDDC1];
+ int pos = 0;
+ for( Entry<Integer, Double> e : mins.entrySet() ) {
+ colIndexes[pos] = e.getKey();
+ extrema[2*pos] = e.getValue();
+ extrema[2*pos+1] = maxs.get(e.getKey());
+ pos ++;
+ }
+ return new DictionaryShared(values, colIndexes, extrema);
}
- private static void applySharedDDC1Dictionary(List<ColGroup> colGroups,
double[] dict) {
+ private static void applySharedDDC1Dictionary(List<ColGroup> colGroups,
Dictionary dict) {
// create joint mapping table
HashMap<Double, Integer> map = new HashMap<>();
- for(int i = 0; i < dict.length; i++)
- map.put(dict[i], i);
-
+ double[] values = dict.getValues();
+ for(int i = 0; i < values.length; i++)
+ map.put(values[i], i);
+
// recode data of all relevant DDC1 groups
for(ColGroup grp : colGroups)
if(grp.getNumCols() == 1 && grp instanceof
ColGroupDDC1) {
ColGroupDDC1 grpDDC1 = (ColGroupDDC1) grp;
grpDDC1.recodeData(map);
- grpDDC1.setValues(dict);
+ grpDDC1.setDictionary(dict);
}
}
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroup.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroup.java
index 6d27dff..bcf15ee 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroup.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroup.java
@@ -248,13 +248,6 @@ public abstract class ColGroup implements Serializable {
public abstract double get(int r, int c);
/**
- * Get the number of values. contained inside the ColGroup.
- *
- * @return value at the row/column position
- */
- public abstract long getValuesSize();
-
- /**
* Multiply the slice of the matrix that this column group represents
by a vector on the right.
*
* @param vector vector to multiply by (tall vector)
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC.java
index f2cad3e..825836b 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC.java
@@ -168,12 +168,13 @@ public abstract class ColGroupDDC extends ColGroupValue {
protected final void postScaling(double[] vals, double[] c) {
final int ncol = getNumCols();
final int numVals = getNumValues();
+ double[] values = getValues();
for(int k = 0, valOff = 0; k < numVals; k++, valOff += ncol) {
double aval = vals[k];
for(int j = 0; j < ncol; j++) {
int colIx = _colIndexes[j];
- c[colIx] += aval * _values[valOff + j];
+ c[colIx] += aval * values[valOff + j];
}
}
}
@@ -275,8 +276,9 @@ public abstract class ColGroupDDC extends ColGroupValue {
// copy entire value tuple to output row
final int clen = getNumCols();
final int off = getCode(rowIx) * clen;
+ final double[] values = getValues();
for(int j = 0; j < clen; j++)
- buff[_colIndexes[j]] = _values[off + j];
+ buff[_colIndexes[j]] = values[off + j];
}
}
@@ -286,5 +288,4 @@ public abstract class ColGroupDDC extends ColGroupValue {
sb.append(super.toString());
return sb.toString();
}
-
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC1.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC1.java
index bf873c8..f29f740 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC1.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC1.java
@@ -59,7 +59,8 @@ public class ColGroupDDC1 extends ColGroupDDC {
int zeroIx = containsAllZeroValue();
if(zeroIx < 0) {
zeroIx = numVals;
- _values = Arrays.copyOf(_values, _values.length
+ numCols);
+ _dict = new Dictionary(Arrays.copyOf(
+ _dict.getValues(),
_dict.getValues().length + numCols));
}
Arrays.fill(_data, (byte) zeroIx);
}
@@ -98,12 +99,12 @@ public class ColGroupDDC1 extends ColGroupDDC {
@Override
protected double getData(int r) {
- return _values[(_data[r] & 0xFF)];
+ return _dict.getValue(_data[r] & 0xFF);
}
@Override
protected double getData(int r, int colIx) {
- return _values[(_data[r] & 0xFF) * getNumCols() + colIx];
+ return _dict.getValue((_data[r] & 0xFF) * getNumCols() + colIx);
}
@Override
@@ -119,9 +120,10 @@ public class ColGroupDDC1 extends ColGroupDDC {
public void recodeData(HashMap<Double, Integer> map) {
// prepare translation table
final int numVals = getNumValues();
+ final double[] values = getValues();
byte[] lookup = new byte[numVals];
for(int k = 0; k < numVals; k++)
- lookup[k] = map.get(_values[k]).byteValue();
+ lookup[k] = map.get(values[k]).byteValue();
// recode the data
for(int i = 0; i < _numRows; i++)
@@ -147,8 +149,9 @@ public class ColGroupDDC1 extends ColGroupDDC {
// write distinct values
if(!skipDict) {
- for(int i = 0; i < _values.length; i++)
- out.writeDouble(_values[i]);
+ final double[] values = getValues();
+ for(int i = 0; i < numCols*numVals; i++)
+ out.writeDouble(values[i]);
}
// write data
@@ -174,9 +177,10 @@ public class ColGroupDDC1 extends ColGroupDDC {
// read distinct values
if(!skipDict || numCols != 1) {
- _values = new double[numVals * numCols];
+ double[] values = new double[numVals * numCols];
for(int i = 0; i < numVals * numCols; i++)
- _values[i] = in.readDouble();
+ values[i] = in.readDouble();
+ _dict = new Dictionary(values);
}
// read data
@@ -191,7 +195,7 @@ public class ColGroupDDC1 extends ColGroupDDC {
// col indices
ret += 4 * _colIndexes.length;
// distinct values (groups of values)
- ret += 8 * _values.length;
+ ret += 8 * _dict.getValues().length;
// data
ret += 1 * _data.length;
@@ -206,9 +210,10 @@ public class ColGroupDDC1 extends ColGroupDDC {
@Override
public void decompressToBlock(MatrixBlock target, int rl, int ru) {
int ncol = getNumCols();
+ double[] values = getValues();
for(int i = rl; i < ru; i++)
for(int j = 0; j < ncol; j++)
- target.appendValue(i, _colIndexes[j],
_values[(_data[i] & 0xFF) * ncol + j]);
+ target.appendValue(i, _colIndexes[j],
values[(_data[i] & 0xFF) * ncol + j]);
// note: append ok because final sort per row
}
@@ -217,9 +222,10 @@ public class ColGroupDDC1 extends ColGroupDDC {
int nrow = getNumRows();
int ncol = getNumCols();
double[] c = target.getDenseBlockValues();
+ double[] values = getValues();
int nnz = 0;
for(int i = 0; i < nrow; i++)
- nnz += ((c[i] = _values[(_data[i] & 0xFF) * ncol +
colpos]) != 0) ? 1 : 0;
+ nnz += ((c[i] = values[(_data[i] & 0xFF) * ncol +
colpos]) != 0) ? 1 : 0;
target.setNonZeros(nnz);
}
@@ -241,12 +247,13 @@ public class ColGroupDDC1 extends ColGroupDDC {
public void countNonZerosPerRow(int[] rnnz, int rl, int ru) {
final int ncol = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// pre-aggregate nnz per value tuple
int[] counts = new int[numVals];
for(int k = 0, valOff = 0; k < numVals; k++, valOff += ncol)
for(int j = 0; j < ncol; j++)
- counts[k] += (_values[valOff + j] != 0) ? 1 : 0;
+ counts[k] += (values[valOff + j] != 0) ? 1 : 0;
// scan data and add counts to output rows
for(int i = rl; i < ru; i++)
@@ -338,6 +345,7 @@ public class ColGroupDDC1 extends ColGroupDDC {
protected void computeSum(MatrixBlock result, KahanFunction kplus) {
final int ncol = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// iterative over codes and count per code (guaranteed <=255)
int[] counts = getCounts();
@@ -347,7 +355,7 @@ public class ColGroupDDC1 extends ColGroupDDC {
for(int k = 0, valOff = 0; k < numVals; k++, valOff += ncol) {
int cntk = counts[k];
for(int j = 0; j < ncol; j++)
- kplus.execute3(kbuff, _values[valOff + j],
cntk);
+ kplus.execute3(kbuff, values[valOff + j], cntk);
}
result.quickSetValue(0, 0, kbuff._sum);
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC2.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC2.java
index ba28dbe..a0218a1 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC2.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupDDC2.java
@@ -59,7 +59,8 @@ public class ColGroupDDC2 extends ColGroupDDC {
int zeroIx = containsAllZeroValue();
if(zeroIx < 0) {
zeroIx = numVals;
- _values = Arrays.copyOf(_values, _values.length
+ numCols);
+ double[] values = _dict.getValues();
+ _dict = new Dictionary(Arrays.copyOf(values,
values.length + numCols));
}
Arrays.fill(_data, (char) zeroIx);
}
@@ -98,12 +99,12 @@ public class ColGroupDDC2 extends ColGroupDDC {
@Override
protected double getData(int r) {
- return _values[_data[r]];
+ return _dict.getValue(_data[r]);
}
@Override
protected double getData(int r, int colIx) {
- return _values[_data[r] * getNumCols() + colIx];
+ return _dict.getValue(_data[r] * getNumCols() + colIx);
}
@Override
@@ -129,8 +130,9 @@ public class ColGroupDDC2 extends ColGroupDDC {
out.writeInt(_colIndexes[i]);
// write distinct values
- for(int i = 0; i < _values.length; i++)
- out.writeDouble(_values[i]);
+ double[] values = getValues();
+ for(int i = 0; i < values.length; i++)
+ out.writeDouble(values[i]);
// write data
for(int i = 0; i < _numRows; i++)
@@ -149,10 +151,11 @@ public class ColGroupDDC2 extends ColGroupDDC {
_colIndexes[i] = in.readInt();
// read distinct values
- _values = new double[numVals * numCols];
+ double[] values = new double[numVals * numCols];
for(int i = 0; i < numVals * numCols; i++)
- _values[i] = in.readDouble();
-
+ values[i] = in.readDouble();
+ _dict = new Dictionary(values);
+
// read data
_data = new char[_numRows];
for(int i = 0; i < _numRows; i++)
@@ -165,7 +168,7 @@ public class ColGroupDDC2 extends ColGroupDDC {
// col indices
ret += 4 * _colIndexes.length;
// distinct values (groups of values)
- ret += 8 * _values.length;
+ ret += 8 * getValues().length;
// data
ret += 2 * _data.length;
@@ -181,9 +184,10 @@ public class ColGroupDDC2 extends ColGroupDDC {
@Override
public void decompressToBlock(MatrixBlock target, int rl, int ru) {
int ncol = getNumCols();
+ double[] values = getValues();
for(int i = rl; i < ru; i++)
for(int j = 0; j < ncol; j++)
- target.appendValue(i, _colIndexes[j],
_values[_data[i] * ncol + j]);
+ target.appendValue(i, _colIndexes[j],
values[_data[i] * ncol + j]);
// note: append ok because final sort per row
}
@@ -192,9 +196,10 @@ public class ColGroupDDC2 extends ColGroupDDC {
int nrow = getNumRows();
int ncol = getNumCols();
double[] c = target.getDenseBlockValues();
+ double[] values = getValues();
int nnz = 0;
for(int i = 0; i < nrow; i++)
- nnz += ((c[i] = _values[_data[i] * ncol + colpos]) !=
0) ? 1 : 0;
+ nnz += ((c[i] = values[_data[i] * ncol + colpos]) != 0)
? 1 : 0;
target.setNonZeros(nnz);
}
@@ -216,12 +221,13 @@ public class ColGroupDDC2 extends ColGroupDDC {
public void countNonZerosPerRow(int[] rnnz, int rl, int ru) {
final int ncol = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// pre-aggregate nnz per value tuple
int[] counts = new int[numVals];
for(int k = 0, valOff = 0; k < numVals; k++, valOff += ncol)
for(int j = 0; j < ncol; j++)
- counts[k] += (_values[valOff + j] != 0) ? 1 : 0;
+ counts[k] += (values[valOff + j] != 0) ? 1 : 0;
// scan data and add counts to output rows
for(int i = rl; i < ru; i++)
@@ -271,11 +277,12 @@ public class ColGroupDDC2 extends ColGroupDDC {
else // general case
{
// iterate over codes, compute all, and add to the
result
+ double[] values = getValues();
for(int i = 0; i < nrow; i++) {
double aval = a[i];
if(aval != 0)
for(int j = 0, valOff = _data[i] *
ncol; j < ncol; j++)
- c[_colIndexes[j]] += aval *
_values[valOff + j];
+ c[_colIndexes[j]] += aval *
values[valOff + j];
}
}
}
@@ -301,11 +308,12 @@ public class ColGroupDDC2 extends ColGroupDDC {
else // general case
{
// iterate over codes, compute all, and add to the
result
+ double[] values = getValues();
for(int i = 0; i < nrow; i++) {
double aval = a.getData(i, 0);
if(aval != 0)
for(int j = 0, valOff = _data[i] *
ncol; j < ncol; j++)
- c[_colIndexes[j]] += aval *
_values[valOff + j];
+ c[_colIndexes[j]] += aval *
values[valOff + j];
}
}
}
@@ -318,13 +326,14 @@ public class ColGroupDDC2 extends ColGroupDDC {
if(numVals < MAX_TMP_VALS) {
// iterative over codes and count per code
int[] counts = getCounts();
+ double[] values = getValues();
// post-scaling of pre-aggregate with distinct values
KahanObject kbuff = new
KahanObject(result.quickGetValue(0, 0), result.quickGetValue(0, 1));
for(int k = 0, valOff = 0; k < numVals; k++, valOff +=
ncol) {
int cntk = counts[k];
for(int j = 0; j < ncol; j++)
- kplus.execute3(kbuff, _values[valOff +
j], cntk);
+ kplus.execute3(kbuff, values[valOff +
j], cntk);
}
result.quickSetValue(0, 0, kbuff._sum);
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOLE.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOLE.java
index 405b379..fe07b18 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOLE.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOLE.java
@@ -119,6 +119,7 @@ public class ColGroupOLE extends ColGroupOffset {
final int blksz = BitmapEncoder.BITMAP_BLOCK_SZ;
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// cache blocking config and position array
int[] apos = skipScan(numVals, rl);
@@ -135,8 +136,8 @@ public class ColGroupOLE extends ColGroupOffset {
int pos = boff + bix + 1;
for(int i = pos; i < pos + len; i++)
for(int j = 0, rix = bi +
_data[i]; j < numCols; j++)
- if(_values[off + j] !=
0)
-
target.appendValue(rix, _colIndexes[j], _values[off + j]);
+ if(values[off + j] != 0)
+
target.appendValue(rix, _colIndexes[j], values[off + j]);
apos[k] += len + 1;
}
}
@@ -154,6 +155,7 @@ public class ColGroupOLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
final int n = getNumRows();
+ final double[] values = getValues();
// cache blocking config and position array
int[] apos = new int[numVals];
@@ -175,8 +177,8 @@ public class ColGroupOLE extends ColGroupOffset {
int pos = boff + bix + 1;
for(int i = pos; i < pos + len; i++)
for(int j = 0, rix = bi +
_data[i]; j < numCols; j++)
- if(_values[off + j] !=
0)
-
target.appendValue(rix, cix[j], _values[off + j]);
+ if(values[off + j] != 0)
+
target.appendValue(rix, cix[j], values[off + j]);
apos[k] += len + 1;
}
}
@@ -194,6 +196,7 @@ public class ColGroupOLE extends ColGroupOffset {
final int numVals = getNumValues();
final int n = getNumRows();
double[] c = target.getDenseBlockValues();
+ final double[] values = getValues();
// cache blocking config and position array
int[] apos = allocIVector(numVals, true);
@@ -211,7 +214,7 @@ public class ColGroupOLE extends ColGroupOffset {
int len = _data[boff + bix];
int pos = boff + bix + 1;
for(int i = pos; i < pos + len; i++) {
- c[bi + _data[i]] = _values[off +
colpos];
+ c[bi + _data[i]] = values[off + colpos];
nnz++;
}
apos[k] += len + 1;
@@ -258,7 +261,7 @@ public class ColGroupOLE extends ColGroupOffset {
// LOG.debug(this.toString());
// Note 0 is because the size can be calculated based on the
given values,
// And because the fourth argument is only needed in
estimation, not when an OLE ColGroup is created.
- return ColGroupSizes.estimateInMemorySizeOLE(getNumCols(),
_values.length, _data.length, 0);
+ return ColGroupSizes.estimateInMemorySizeOLE(getNumCols(),
getValues().length, _data.length, 0);
}
@Override
@@ -381,6 +384,7 @@ public class ColGroupOLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
final int n = getNumRows();
+ final double[] values = getValues();
if( numVals > 1 && _numRows > blksz) {
// cache blocking config (see matrix-vector mult for
explanation)
@@ -421,7 +425,7 @@ public class ColGroupOLE extends ColGroupOffset {
// step 3: scale partial results by values and write to
global output
for(int k = 0, valOff = 0; k < numVals; k++, valOff +=
numCols)
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += cvals[k] *
_values[valOff + j];
+ c[_colIndexes[j]] += cvals[k] *
values[valOff + j];
}
else {
// iterate over all values and their bitmaps
@@ -436,7 +440,7 @@ public class ColGroupOLE extends ColGroupOffset {
// scale partial results by values and write
results
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += vsum *
_values[valOff + j];
+ c[_colIndexes[j]] += vsum *
values[valOff + j];
}
}
}
@@ -447,6 +451,7 @@ public class ColGroupOLE extends ColGroupOffset {
double[] c = result.getDenseBlockValues();
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// iterate over all values and their bitmaps
for(int k = 0, valOff = 0; k < numVals; k++, valOff += numCols)
{
@@ -459,7 +464,7 @@ public class ColGroupOLE extends ColGroupOffset {
// scale partial results by values and write results
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += vsum * _values[valOff + j];
+ c[_colIndexes[j]] += vsum * values[valOff + j];
}
}
@@ -470,6 +475,7 @@ public class ColGroupOLE extends ColGroupOffset {
// iterate over all values and their bitmaps
final int numVals = getNumValues();
final int numCols = getNumCols();
+ final double[] values = getValues();
for(int k = 0; k < numVals; k++) {
int boff = _ptr[k];
@@ -483,7 +489,7 @@ public class ColGroupOLE extends ColGroupOffset {
// scale counts by all values
for(int j = 0; j < numCols; j++)
- kplus.execute3(kbuff, _values[valOff + j],
count);
+ kplus.execute3(kbuff, values[valOff + j],
count);
}
result.quickSetValue(0, 0, kbuff._sum);
@@ -575,6 +581,8 @@ public class ColGroupOLE extends ColGroupOffset {
// iterate over all values and their bitmaps
final int numVals = getNumValues();
final int numCols = getNumCols();
+ final double[] values = getValues();
+
for(int k = 0; k < numVals; k++) {
int boff = _ptr[k];
int blen = len(k);
@@ -588,7 +596,7 @@ public class ColGroupOLE extends ColGroupOffset {
// scale counts by all values
for(int j = 0; j < numCols; j++) {
kbuff.set(result.quickGetValue(0,
_colIndexes[j]), result.quickGetValue(1, _colIndexes[j]));
- kplus.execute3(kbuff, _values[valOff + j],
count);
+ kplus.execute3(kbuff, values[valOff + j],
count);
result.quickSetValue(0, _colIndexes[j],
kbuff._sum);
result.quickSetValue(1, _colIndexes[j],
kbuff._correction);
}
@@ -849,8 +857,9 @@ public class ColGroupOLE extends ColGroupOffset {
final int vcode = _vcodes[segIx];
if(vcode >= 0) {
// copy entire value tuple if necessary
+ final double[] values = getValues();
for(int j = 0, off = vcode * clen; j < clen;
j++)
- buff[_colIndexes[j]] = _values[off + j];
+ buff[_colIndexes[j]] = values[off + j];
// reset vcode to avoid scan on next segment
_vcodes[segIx] = -1;
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOffset.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOffset.java
index b51bd38..24cb0a4 100644
---
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOffset.java
+++
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupOffset.java
@@ -50,7 +50,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
public static final int WRITE_CACHE_BLKSZ = 2 *
BitmapEncoder.BITMAP_BLOCK_SZ;
public static boolean ALLOW_CACHE_CONSCIOUS_ROWSUMS = true;
- /** Bitmaps, one per uncompressed value in {@link #_values}. */
+ /** Bitmaps, one per uncompressed value tuple in {@link #_dict}. */
protected int[] _ptr; // bitmap offsets per value
protected char[] _data; // linearized bitmaps (variable length)
@@ -107,7 +107,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
return
ColGroupSizes.estimateInMemorySizeOffset(getNumCols(), _colIndexes.length, 0,
0);
}
else {
- return
ColGroupSizes.estimateInMemorySizeOffset(getNumCols(), _values.length,
_ptr.length, _data.length);
+ return
ColGroupSizes.estimateInMemorySizeOffset(getNumCols(), getValues().length,
_ptr.length, _data.length);
}
}
@@ -117,6 +117,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
final int numCols = getNumCols();
final int numVals = getNumValues();
int[] colIndices = getColIndices();
+ final double[] values = getValues();
// Run through the bitmaps for this column group
for(int i = 0; i < numVals; i++) {
@@ -131,7 +132,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
break;
for(int colIx = 0; colIx < numCols; colIx++)
- target.appendValue(row,
colIndices[colIx], _values[valOff + colIx]);
+ target.appendValue(row,
colIndices[colIx], values[valOff + colIx]);
}
}
}
@@ -141,6 +142,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
public void decompressToBlock(MatrixBlock target, int[]
colIndexTargets) {
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// Run through the bitmaps for this column group
for(int i = 0; i < numVals; i++) {
@@ -152,7 +154,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
for(int colIx = 0; colIx < numCols; colIx++) {
int origMatrixColIx =
getColIndex(colIx);
int targetColIx =
colIndexTargets[origMatrixColIx];
- target.quickSetValue(row, targetColIx,
_values[valOff + colIx]);
+ target.quickSetValue(row, targetColIx,
values[valOff + colIx]);
}
}
}
@@ -163,6 +165,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
public void decompressToBlock(MatrixBlock target, int colpos) {
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// Run through the bitmaps for this column group
for(int i = 0; i < numVals; i++) {
@@ -171,7 +174,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
while(decoder.hasNext()) {
int row = decoder.next();
- target.quickSetValue(row, 0, _values[valOff +
colpos]);
+ target.quickSetValue(row, 0, values[valOff +
colpos]);
}
}
}
@@ -188,13 +191,14 @@ public abstract class ColGroupOffset extends
ColGroupValue {
// find row index in value offset lists via scan
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
for(int i = 0; i < numVals; i++) {
Iterator<Integer> decoder = getIterator(i);
int valOff = i * numCols;
while(decoder.hasNext()) {
int row = decoder.next();
if(row == r)
- return _values[valOff + ix];
+ return values[valOff + ix];
else if(row > r)
break; // current value
}
@@ -205,20 +209,22 @@ public abstract class ColGroupOffset extends
ColGroupValue {
protected final void sumAllValues(double[] b, double[] c) {
final int numVals = getNumValues();
final int numCols = getNumCols();
+ final double[] values = getValues();
// vectMultiplyAdd over cols instead of dotProduct over vals
because
// usually more values than columns
for(int i = 0, off = 0; i < numCols; i++, off += numVals)
- LinearAlgebraUtils.vectMultiplyAdd(b[i], _values, c,
off, 0, numVals);
+ LinearAlgebraUtils.vectMultiplyAdd(b[i], values, c,
off, 0, numVals);
}
protected final double mxxValues(int bitmapIx, Builtin builtin) {
final int numCols = getNumCols();
final int valOff = bitmapIx * numCols;
- double val = (builtin
- .getBuiltinCode() == BuiltinCode.MAX) ?
Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
+ final double[] values = getValues();
+ double val = (builtin.getBuiltinCode() == BuiltinCode.MAX) ?
+ Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
for(int i = 0; i < numCols; i++)
- val = builtin.execute(val, _values[valOff + i]);
+ val = builtin.execute(val, values[valOff + i]);
return val;
}
@@ -267,10 +273,11 @@ public abstract class ColGroupOffset extends
ColGroupValue {
_colIndexes[i] = in.readInt();
// read distinct values
- _values = new double[numVals * numCols];
+ double[] values = new double[numVals * numCols];
for(int i = 0; i < numVals * numCols; i++)
- _values[i] = in.readDouble();
-
+ values[i] = in.readDouble();
+ _dict = new Dictionary(values);
+
// read bitmaps
int totalLen = in.readInt();
_ptr = new int[numVals + 1];
@@ -299,8 +306,9 @@ public abstract class ColGroupOffset extends ColGroupValue {
out.writeInt(_colIndexes[i]);
// write distinct values
- for(int i = 0; i < _values.length; i++)
- out.writeDouble(_values[i]);
+ double[] values = getValues();
+ for(int i = 0; i < numCols * numVals; i++)
+ out.writeDouble(values[i]);
// write bitmaps (lens and data, offset later recreated)
int totalLen = 0;
@@ -322,7 +330,7 @@ public abstract class ColGroupOffset extends ColGroupValue {
// col indices
ret += 4 * _colIndexes.length;
// distinct values (groups of values)
- ret += 8 * _values.length;
+ ret += 8 * getValues().length;
// actual bitmaps
ret += 4; // total length
for(int i = 0; i < getNumValues(); i++)
@@ -405,7 +413,8 @@ public abstract class ColGroupOffset extends ColGroupValue {
public IJV next() {
if(!hasNext())
throw new RuntimeException("No more offset
entries.");
- _buff.set(_rpos, _colIndexes[_cpos], (_vpos >=
getNumValues()) ? 0 : _values[_vpos * getNumCols() + _cpos]);
+ _buff.set(_rpos, _colIndexes[_cpos],
+ (_vpos >= getNumValues()) ? 0 :
_dict.getValue(_vpos * getNumCols() + _cpos));
getNextValue();
return _buff;
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupRLE.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupRLE.java
index de10bed..7aa8b53 100644
--- a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupRLE.java
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupRLE.java
@@ -98,6 +98,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int blksz = 128 * 1024;
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// position and start offset arrays
int[] astart = new int[numVals];
@@ -116,8 +117,8 @@ public class ColGroupRLE extends ColGroupOffset {
int len = _data[boff + bix + 1];
for(int i = Math.max(rl,
start); i < Math.min(start + len, ru); i++)
for(int j = 0; j <
numCols; j++)
- if(_values[off
+ j] != 0)
-
target.appendValue(i, _colIndexes[j], _values[off + j]);
+ if(values[off +
j] != 0)
+
target.appendValue(i, _colIndexes[j], values[off + j]);
start += len;
}
apos[k] = bix;
@@ -138,6 +139,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
final int n = getNumRows();
+ final double[] values = getValues();
// position and start offset arrays
int[] apos = new int[numVals];
@@ -163,8 +165,8 @@ public class ColGroupRLE extends ColGroupOffset {
int len = _data[boff + bix + 1];
for(int i = start; i < start +
len; i++)
for(int j = 0; j <
numCols; j++)
- if(_values[off
+ j] != 0)
-
target.appendValue(i, cix[j], _values[off + j]);
+ if(values[off +
j] != 0)
+
target.appendValue(i, cix[j], values[off + j]);
start += len;
}
apos[k] = bix;
@@ -185,6 +187,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int numVals = getNumValues();
final int n = getNumRows();
double[] c = target.getDenseBlockValues();
+ final double[] values = getValues();
// position and start offset arrays
int[] astart = new int[numVals];
@@ -205,7 +208,7 @@ public class ColGroupRLE extends ColGroupOffset {
for(; bix < blen & start < bimax; bix += 2) {
start += _data[boff + bix];
int len = _data[boff + bix + 1];
- Arrays.fill(c, start, start + len,
_values[off + colpos]);
+ Arrays.fill(c, start, start + len,
values[off + colpos]);
nnz += len;
start += len;
}
@@ -358,6 +361,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
final int n = getNumRows();
+ final double[] values = getValues();
if(numVals > 1 && _numRows > BitmapEncoder.BITMAP_BLOCK_SZ) {
final int blksz = ColGroupOffset.READ_CACHE_BLKSZ;
@@ -397,7 +401,7 @@ public class ColGroupRLE extends ColGroupOffset {
// step 3: scale partial results by values and write to
global output
for(int k = 0, valOff = 0; k < numVals; k++, valOff +=
numCols)
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += cvals[k] *
_values[valOff + j];
+ c[_colIndexes[j]] += cvals[k] *
values[valOff + j];
}
else {
@@ -417,7 +421,7 @@ public class ColGroupRLE extends ColGroupOffset {
// scale partial results by values and write
results
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += vsum *
_values[valOff + j];
+ c[_colIndexes[j]] += vsum *
values[valOff + j];
}
}
}
@@ -428,6 +432,7 @@ public class ColGroupRLE extends ColGroupOffset {
double[] c = result.getDenseBlockValues();
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
// iterate over all values and their bitmaps
for(int k = 0, valOff = 0; k < numVals; k++, valOff += numCols)
{
@@ -446,7 +451,7 @@ public class ColGroupRLE extends ColGroupOffset {
// scale partial results by values and write results
for(int j = 0; j < numCols; j++)
- c[_colIndexes[j]] += vsum * _values[valOff + j];
+ c[_colIndexes[j]] += vsum * values[valOff + j];
}
}
@@ -484,6 +489,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
for(int k = 0; k < numVals; k++) {
int boff = _ptr[k];
@@ -499,7 +505,7 @@ public class ColGroupRLE extends ColGroupOffset {
// scale counts by all values
for(int j = 0; j < numCols; j++)
- kplus.execute3(kbuff, _values[valOff + j],
count);
+ kplus.execute3(kbuff, values[valOff + j],
count);
}
result.quickSetValue(0, 0, kbuff._sum);
@@ -596,6 +602,7 @@ public class ColGroupRLE extends ColGroupOffset {
final int numCols = getNumCols();
final int numVals = getNumValues();
+ final double[] values = getValues();
for(int k = 0; k < numVals; k++) {
int boff = _ptr[k];
@@ -612,7 +619,7 @@ public class ColGroupRLE extends ColGroupOffset {
// scale counts by all values
for(int j = 0; j < numCols; j++) {
kbuff.set(result.quickGetValue(0,
_colIndexes[j]), result.quickGetValue(1, _colIndexes[j]));
- kplus.execute3(kbuff, _values[valOff + j],
count);
+ kplus.execute3(kbuff, values[valOff + j],
count);
result.quickSetValue(0, _colIndexes[j],
kbuff._sum);
result.quickSetValue(1, _colIndexes[j],
kbuff._correction);
}
@@ -839,8 +846,9 @@ public class ColGroupRLE extends ColGroupOffset {
final int vcode = _vcodes[segIx];
if(vcode >= 0) {
// copy entire value tuple if necessary
+ final double[] values = getValues();
for(int j = 0, off = vcode * clen; j < clen;
j++)
- buff[_colIndexes[j]] = _values[off + j];
+ buff[_colIndexes[j]] = values[off + j];
// reset vcode to avoid scan on next segment
_vcodes[segIx] = -1;
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupSizes.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupSizes.java
index c53f867..8809340 100644
---
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupSizes.java
+++
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupSizes.java
@@ -83,7 +83,8 @@ public class ColGroupSizes {
public static long estimateInMemorySizeGroupValue(int nrColumns, long
nrValues) {
long size = estimateInMemorySizeGroup(nrColumns);
- size += MemoryEstimates.doubleArrayCost(nrValues);
+ size += 24 //dictionary object
+ + MemoryEstimates.doubleArrayCost(nrValues);
return size;
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupValue.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupValue.java
index a1c120c..c65ca82 100644
---
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupValue.java
+++
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/ColGroupValue.java
@@ -38,6 +38,7 @@ import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.apache.sysds.runtime.matrix.data.Pair;
import org.apache.sysds.runtime.matrix.operators.AggregateUnaryOperator;
import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.utils.MemoryEstimates;
/**
* Base class for column groups encoded with value dictionary.
@@ -55,7 +56,7 @@ public abstract class ColGroupValue extends ColGroup {
};
/** Distinct values associated with individual bitmaps. */
- protected double[] _values; // linearized <numcol vals> <numcol vals>
+ protected Dictionary _dict;
public ColGroupValue() {
super();
@@ -77,7 +78,7 @@ public abstract class ColGroupValue extends ColGroup {
}
// extract and store distinct values (bitmaps handled by
subclasses)
- _values = ubm.getValues();
+ _dict = new Dictionary(ubm.getValues());
}
/**
@@ -89,16 +90,18 @@ public abstract class ColGroupValue extends ColGroup {
*/
protected ColGroupValue(int[] colIndices, int numRows, double[] values)
{
super(colIndices, numRows);
- _values = values;
+ _dict = new Dictionary(values);
}
@Override
public long estimateInMemorySize() {
- return
ColGroupSizes.estimateInMemorySizeGroupValue(_colIndexes.length,
getValuesSize());
+ return
ColGroupSizes.estimateInMemorySizeGroupValue(_colIndexes.length,
getNumValues());
}
- public long getValuesSize() {
- return (_values != null) ? 32 + _values.length * 8 : 0;
+ public long getDictionarySize() {
+ //NOTE: this estimate needs to be consistent with the estimate
above,
+ //so for now we use the (incorrect) double array size, not the
dictionary size
+ return (_dict != null) ?
MemoryEstimates.doubleArrayCost(_dict.getValues().length) : 0;
}
/**
@@ -107,27 +110,33 @@ public abstract class ColGroupValue extends ColGroup {
* @return the number of distinct sets of values associated with the
bitmaps in this column group
*/
public int getNumValues() {
- return _values.length / _colIndexes.length;
+ return _dict.getValues().length / _colIndexes.length;
}
public double[] getValues() {
- return _values;
+ return _dict.getValues();
}
public void setValues(double[] values) {
- _values = values;
+ _dict = new Dictionary(values);
}
public double getValue(int k, int col) {
- return _values[k * getNumCols() + col];
+ return _dict.getValues()[k * getNumCols() + col];
+ }
+
+ public void setDictionary(Dictionary dict) {
+ _dict = dict;
}
public MatrixBlock getValuesAsBlock() {
boolean containsZeros = (this instanceof ColGroupOffset) ?
((ColGroupOffset) this)._zeros : false;
- int rlen = containsZeros ? _values.length + 1 : _values.length;
+ final double[] values = getValues();
+ int vlen = values.length;
+ int rlen = containsZeros ? vlen + 1 : vlen;
MatrixBlock ret = new MatrixBlock(rlen, 1, false);
- for(int i = 0; i < _values.length; i++)
- ret.quickSetValue(i, 0, _values[i]);
+ for(int i = 0; i < vlen; i++)
+ ret.quickSetValue(i, 0, values[i]);
return ret;
}
@@ -169,50 +178,27 @@ public abstract class ColGroupValue extends ColGroup {
}
protected int containsAllZeroValue() {
- int numVals = getNumValues();
- int numCols = getNumCols();
- for(int i = 0, off = 0; i < numVals; i++, off += numCols) {
- boolean allZeros = true;
- for(int j = 0; j < numCols; j++)
- allZeros &= (_values[off + j] == 0);
- if(allZeros)
- return i;
- }
- return -1;
+ return _dict.hasZeroTuple(getNumCols());
}
- public final double sumValues(int valIx) {
- final int numCols = getNumCols();
- final int valOff = valIx * numCols;
- double val = 0.0;
- for(int i = 0; i < numCols; i++) {
- val += _values[valOff + i];
- }
-
- return val;
- }
-
- public final double sumValues(int valIx, KahanFunction kplus) {
- return sumValues(valIx, kplus, new KahanObject(0, 0));
+ protected final double[] sumAllValues(KahanFunction kplus, KahanObject
kbuff) {
+ return sumAllValues(kplus, kbuff, true);
}
public final double sumValues(int valIx, KahanFunction kplus,
KahanObject kbuff) {
final int numCols = getNumCols();
final int valOff = valIx * numCols;
+ final double[] values = _dict.getValues();
kbuff.set(0, 0);
for(int i = 0; i < numCols; i++)
- kplus.execute2(kbuff, _values[valOff + i]);
+ kplus.execute2(kbuff, values[valOff + i]);
return kbuff._sum;
}
- protected final double[] sumAllValues(KahanFunction kplus, KahanObject
kbuff) {
- return sumAllValues(kplus, kbuff, true);
- }
-
protected final double[] sumAllValues(KahanFunction kplus, KahanObject
kbuff, boolean allocNew) {
// quick path: sum
if(getNumCols() == 1 && kplus instanceof KahanPlus)
- return _values; // shallow copy of values
+ return _dict.getValues(); // shallow copy of values
// pre-aggregate value tuple
final int numVals = getNumValues();
@@ -226,11 +212,10 @@ public abstract class ColGroupValue extends ColGroup {
protected final double sumValues(int valIx, double[] b) {
final int numCols = getNumCols();
final int valOff = valIx * numCols;
+ final double[] values = _dict.getValues();
double val = 0;
- for(int i = 0; i < numCols; i++) {
- val += _values[valOff + i] * b[i];
- }
-
+ for(int i = 0; i < numCols; i++)
+ val += values[valOff + i] * b[i];
return val;
}
@@ -255,18 +240,14 @@ public abstract class ColGroupValue extends ColGroup {
*/
protected void computeMxx(MatrixBlock result, Builtin builtin, boolean
zeros) {
// init and 0-value handling
- double val = (builtin
- .getBuiltinCode() == BuiltinCode.MAX) ?
Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
+ double val = (builtin.getBuiltinCode() == BuiltinCode.MAX) ?
+ Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
if(zeros)
val = builtin.execute(val, 0);
// iterate over all values only
- final int numVals = getNumValues();
- final int numCols = getNumCols();
- for(int k = 0; k < numVals; k++)
- for(int j = 0, valOff = k * numCols; j < numCols; j++)
- val = builtin.execute(val, _values[valOff + j]);
-
+ val = _dict.aggregate(val, builtin);
+
// compute new partial aggregate
val = builtin.execute(val, result.quickGetValue(0, 0));
result.quickSetValue(0, 0, val);
@@ -280,23 +261,20 @@ public abstract class ColGroupValue extends ColGroup {
* @param zeros indicator if column group contains zero values
*/
protected void computeColMxx(MatrixBlock result, Builtin builtin,
boolean zeros) {
- final int numVals = getNumValues();
final int numCols = getNumCols();
// init and 0-value handling
double[] vals = new double[numCols];
- Arrays.fill(vals,
- (builtin.getBuiltinCode() == BuiltinCode.MAX) ?
Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY);
+ Arrays.fill(vals, (builtin.getBuiltinCode() == BuiltinCode.MAX)
?
+ Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY);
if(zeros) {
for(int j = 0; j < numCols; j++)
vals[j] = builtin.execute(vals[j], 0);
}
// iterate over all values only
- for(int k = 0; k < numVals; k++)
- for(int j = 0, valOff = k * numCols; j < numCols; j++)
- vals[j] = builtin.execute(vals[j],
_values[valOff + j]);
-
+ vals = _dict.aggregateCols(vals, builtin, _colIndexes);
+
// copy results to output
for(int j = 0; j < numCols; j++)
result.quickSetValue(0, _colIndexes[j], vals[j]);
@@ -312,24 +290,16 @@ public abstract class ColGroupValue extends ColGroup {
* @return transformed copy of value metadata for this column group
*/
protected double[] applyScalarOp(ScalarOperator op) {
- // scan over linearized values
- double[] ret = new double[_values.length];
- for(int i = 0; i < _values.length; i++) {
- ret[i] = op.executeScalar(_values[i]);
- }
- return ret;
+ return _dict.clone().apply(op).getValues();
}
protected double[] applyScalarOp(ScalarOperator op, double newVal, int
numCols) {
- // scan over linearized values
- double[] ret = new double[_values.length + numCols];
- for(int i = 0; i < _values.length; i++) {
- ret[i] = op.executeScalar(_values[i]);
- }
+ double[] values = _dict.getValues(); //allocate new array just
once
+ Dictionary tmp = new Dictionary(Arrays.copyOf(values,
values.length+numCols));
+ double[] ret = tmp.apply(op).getValues();
// add new value to the end
- Arrays.fill(ret, _values.length, _values.length + numCols,
newVal);
-
+ Arrays.fill(ret, values.length, values.length+numCols, newVal);
return ret;
}
@@ -429,10 +399,10 @@ public abstract class ColGroupValue extends ColGroup {
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(super.toString());
- sb.append(String.format("\n%15s%5d ", "Columns:",
this._colIndexes.length));
- sb.append(Arrays.toString(this._colIndexes));
- sb.append(String.format("\n%15s%5d ", "Values:",
this._values.length));
- sb.append(Arrays.toString(this._values));
+ sb.append(String.format("\n%15s%5d ", "Columns:",
_colIndexes.length));
+ sb.append(Arrays.toString(_colIndexes));
+ sb.append(String.format("\n%15s%5d ", "Values:",
_dict.getValues().length));
+ sb.append(Arrays.toString(_dict.getValues()));
return sb.toString();
}
}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/Dictionary.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/Dictionary.java
new file mode 100644
index 0000000..09506d1
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/compress/colgroup/Dictionary.java
@@ -0,0 +1,96 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.matrix.operators.ScalarOperator;
+import org.apache.sysds.utils.MemoryEstimates;
+
+/**
+ * This dictionary class aims to encapsulate the storage and operations over
+ * unique floating point values of a column group. The primary reason for its
+ * introduction was to provide an entry point for specialization such as shared
+ * dictionaries, which require additional information.
+ */
+public class Dictionary {
+ // linearized <numcol vals> <numcol vals>
+ protected final double[] _values;
+
+ public Dictionary(double[] values) {
+ _values = values;
+ }
+
+ public double[] getValues() {
+ return _values;
+ }
+
+ public double getValue(int i) {
+ return _values[i];
+ }
+
+ public long getInMemorySize() {
+ //object + values array
+ return 16 + MemoryEstimates.doubleArrayCost(_values.length);
+ }
+
+ public int hasZeroTuple(int ncol) {
+ int len = _values.length;
+ for(int i = 0, off = 0; i < len; i++, off += ncol) {
+ boolean allZeros = true;
+ for(int j = 0; j < ncol; j++)
+ allZeros &= (_values[off + j] == 0);
+ if(allZeros)
+ return i;
+ }
+ return -1;
+ }
+
+ public double aggregate(double init, Builtin fn) {
+ //full aggregate can disregard tuple boundaries
+ int len = _values.length;
+ double ret = init;
+ for(int i = 0; i < len; i++)
+ ret = fn.execute(ret, _values[i]);
+ return ret;
+ }
+
+ public double[] aggregateCols(double[] init, Builtin fn, int[] cols) {
+ int ncol = cols.length;
+ int vlen = _values.length / ncol;
+ double[] ret = init;
+ for(int k = 0; k < vlen; k++)
+ for(int j = 0, valOff = k * ncol; j < ncol; j++)
+ ret[j] = fn.execute(ret[j], _values[valOff +
j]);
+ return ret;
+ }
+
+ public Dictionary apply(ScalarOperator op) {
+ //in-place modification of the dictionary
+ int len = _values.length;
+ for(int i = 0; i < len; i++)
+ _values[i] = op.executeScalar(_values[i]);
+ return this; //fluent API
+ }
+
+ @Override
+ public Dictionary clone() {
+ return new Dictionary(_values.clone());
+ }
+}
diff --git
a/src/main/java/org/apache/sysds/runtime/compress/colgroup/DictionaryShared.java
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/DictionaryShared.java
new file mode 100644
index 0000000..62a6a18
--- /dev/null
+++
b/src/main/java/org/apache/sysds/runtime/compress/colgroup/DictionaryShared.java
@@ -0,0 +1,79 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.compress.colgroup;
+
+import org.apache.commons.lang3.ArrayUtils;
+import org.apache.sysds.runtime.functionobjects.Builtin;
+import org.apache.sysds.runtime.functionobjects.Builtin.BuiltinCode;
+import org.apache.sysds.utils.MemoryEstimates;
+
+/**
+ * This dictionary class aims to encapsulate the storage and operations over
+ * unique floating point values of a column group. The primary reason for its
+ * introduction was to provide an entry point for specialization such as shared
+ * dictionaries, which require additional information.
+ */
+public class DictionaryShared extends Dictionary {
+ protected final int[] _colIndexes;
+ // linearized <min/max> <min/max> of
+ // column groups that share the dictionary
+ protected final double[] _extrema;
+
+ public DictionaryShared(double[] values, int[] colIndexes, double[]
extrema) {
+ super(values);
+ _colIndexes = colIndexes;
+ _extrema = extrema;
+ }
+
+ @Override
+ public long getInMemorySize() {
+ return super.getInMemorySize()
+ + MemoryEstimates.intArrayCost(_colIndexes.length)
+ + MemoryEstimates.doubleArrayCost(_extrema.length);
+ }
+
+ @Override
+ public double aggregate(double init, Builtin fn) {
+ //full aggregate directly over extreme values
+ int len = _extrema.length;
+ int off = fn.getBuiltinCode() == BuiltinCode.MIN ? 0 : 1;
+ double ret = init;
+ for(int i = off; i < len; i+=2)
+ ret = fn.execute(ret, _extrema[i]);
+ return ret;
+ }
+
+ public double[] aggregateCols(double[] init, Builtin fn, int[] cols) {
+ int ncol = cols.length;
+ double[] ret = init;
+ int off = fn.getBuiltinCode() == BuiltinCode.MIN ? 0 : 1;
+ for(int i=0; i<ncol; i++) {
+ int pos = ArrayUtils.indexOf(_colIndexes, cols[i]);
+ ret[i] = fn.execute(ret[i], _extrema[2*pos+off]);
+ }
+ return ret;
+ }
+
+ @Override
+ public DictionaryShared clone() {
+ return new DictionaryShared(
+ getValues().clone(), _colIndexes.clone(),
_extrema.clone());
+ }
+}
diff --git
a/src/test/java/org/apache/sysds/test/component/compress/CompressedMatrixTest.java
b/src/test/java/org/apache/sysds/test/component/compress/CompressedMatrixTest.java
index bbff431..1ee405b 100644
---
a/src/test/java/org/apache/sysds/test/component/compress/CompressedMatrixTest.java
+++
b/src/test/java/org/apache/sysds/test/component/compress/CompressedMatrixTest.java
@@ -361,7 +361,6 @@ public class CompressedMatrixTest extends
AbstractCompressedUnaryTests {
return;
CompressionStatistics cStat = ((CompressedMatrixBlock)
cmb).getCompressionStatistics();
long colsEstimate = cStat.estimatedSizeCols;
- // long groupsEstimate = cStat.estimatedSizeColGroups;
long actualSize = cStat.size;
long originalSize = cStat.originalSize;
int allowedTolerance = 0;
@@ -372,8 +371,6 @@ public class CompressedMatrixTest extends
AbstractCompressedUnaryTests {
StringBuilder builder = new StringBuilder();
builder.append("\n\t" + String.format("%-40s - %12d",
"Actual compressed size: ", actualSize));
- // builder.append("\n\t"+String.format("%-40s -
%12d","<= estimated ColGroup compressed
- // size",groupsEstimate));
builder.append("\n\t" + String.format("%-40s - %12d
with tolerance: %5d",
"<= estimated isolated ColGroups: ",
colsEstimate,
@@ -410,9 +407,10 @@ public class CompressedMatrixTest extends
AbstractCompressedUnaryTests {
builder.append("\n\tcol groups sizes: " +
cStat.getGroupsSizesString());
builder.append("\n\t" + this.toString());
- assertTrue(builder.toString(), actualSize ==
JolEstimatedSize && actualSize <= originalSize);
- // assertTrue(builder.toString(), groupsEstimate <
actualSize && colsEstimate < groupsEstimate);
-
+ //NOTE: The Jol estimate is wrong for shared
dictionaries because
+ // it treats the object hierarchy as a tree and
not a graph
+ assertTrue(builder.toString(), actualSize <=
originalSize
+ &&
(compressionSettings.allowSharedDDCDictionary || actualSize ==
JolEstimatedSize));
}
catch(Exception e) {
e.printStackTrace();
diff --git
a/src/test/java/org/apache/sysds/test/component/compress/CompressedTestBase.java
b/src/test/java/org/apache/sysds/test/component/compress/CompressedTestBase.java
index 9a84f0e..c0668c6 100644
---
a/src/test/java/org/apache/sysds/test/component/compress/CompressedTestBase.java
+++
b/src/test/java/org/apache/sysds/test/component/compress/CompressedTestBase.java
@@ -67,11 +67,8 @@ public class CompressedTestBase extends TestBase {
protected static CompressionSettings[] usedCompressionSettings = new
CompressionSettings[] {
new
CompressionSettingsBuilder().setSamplingRatio(0.1).setAllowSharedDDCDictionary(false)
.setSeed(compressionSeed).setValidCompressions(DDCOnly).setInvestigateEstimate(true).create(),
- // TODO: DDC1 sharring does not work correctly in Aggregare Col
Max.
- // The other tests passes fine.
- // new
- //
CompressionSettingsBuilder().setSamplingRatio(0.1).setAllowSharedDDCDictionary(true).setSeed(compressionSeed).setValidCompressions(DDCOnly)
- // .create(),
+ new
CompressionSettingsBuilder().setSamplingRatio(0.1).setAllowSharedDDCDictionary(true)
+
.setSeed(compressionSeed).setValidCompressions(DDCOnly).setInvestigateEstimate(true).create(),
new
CompressionSettingsBuilder().setSamplingRatio(0.1).setSeed(compressionSeed).setValidCompressions(OLEOnly)
.setInvestigateEstimate(true).create(),
new
CompressionSettingsBuilder().setSamplingRatio(0.1).setSeed(compressionSeed).setValidCompressions(RLEOnly)
diff --git
a/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTest.java
b/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTest.java
index b34d061..120eb86 100644
---
a/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTest.java
+++
b/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTest.java
@@ -36,6 +36,7 @@ import
org.apache.sysds.runtime.compress.estim.CompressedSizeEstimator;
import org.apache.sysds.runtime.compress.estim.CompressedSizeEstimatorFactory;
import org.apache.sysds.runtime.compress.estim.CompressedSizeInfoColGroup;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.junit.Ignore;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
@@ -86,6 +87,7 @@ public abstract class JolEstimateTest {
}
@Test
+ @Ignore //TODO this method is a maintenance obstacle (e.g., why do we
expect int arrays in the number of rows?)
public void instanceSize() {
assertTrue("Failed Test, because ColGroup is null", cg != null);
try {
@@ -128,18 +130,14 @@ public abstract class JolEstimateTest {
ClassLayout cl = ClassLayout.parseInstance(ob,
l);
diff = cl.instanceSize();
jolEstimate += diff;
- // sb.append(cl.toPrintable());
sb.append(ob.getClass());
sb.append(" TOTAL MEM: " + jolEstimate + "
diff " + diff + "\n");
}
long estimate = cg.estimateInMemorySize();
String errorMessage = " estimate " + estimate + "
should be equal to JOL " + jolEstimate + "\n";
assertTrue(errorMessage + sb.toString() + "\n" +
cg.toString(), estimate == jolEstimate);
-
}
- catch(
-
- Exception e) {
+ catch(Exception e) {
e.printStackTrace();
assertTrue("Failed Test: " + e.getMessage(), false);
}
diff --git
a/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTestEmpty.java
b/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTestEmpty.java
index 982fca4..57053aa 100644
---
a/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTestEmpty.java
+++
b/src/test/java/org/apache/sysds/test/component/compress/colgroup/JolEstimateTestEmpty.java
@@ -34,6 +34,7 @@ import org.apache.sysds.runtime.compress.colgroup.ColGroupRLE;
import org.apache.sysds.runtime.compress.colgroup.ColGroupSizes;
import org.apache.sysds.runtime.compress.colgroup.ColGroupUncompressed;
import org.apache.sysds.runtime.compress.colgroup.ColGroupValue;
+import org.apache.sysds.runtime.compress.colgroup.Dictionary;
import org.apache.sysds.runtime.data.DenseBlockFP64;
import org.apache.sysds.runtime.matrix.data.MatrixBlock;
import org.junit.Test;
@@ -114,9 +115,12 @@ public class JolEstimateTestEmpty {
size += 20;
size += 4;
}
- if(fl.typeClass() ==
"org.apache.sysds.runtime.matrix.data.MatrixBlock") {
+ if(fl.typeClass().equals(MatrixBlock.class.getName())) {
size +=
MatrixBlock.estimateSizeDenseInMemory(0, 0);
}
+ else
if(fl.typeClass().equals(Dictionary.class.getName())) {
+ size += getWorstCaseMemory(Dictionary.class);
+ }
}
return size;
