Repository: incubator-systemml Updated Branches: refs/heads/master d0cae2318 -> 2137a7e4a
[SYSTEMML-821] Various cleanups OLE/RLE compressed column groups Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/b1dc0d5b Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/b1dc0d5b Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/b1dc0d5b Branch: refs/heads/master Commit: b1dc0d5bf17c61b949404bc7ea1a9e9f497ad627 Parents: d0cae23 Author: Matthias Boehm <[email protected]> Authored: Tue Aug 9 23:00:03 2016 -0700 Committer: Matthias Boehm <[email protected]> Committed: Thu Aug 11 11:52:09 2016 -0700 ---------------------------------------------------------------------- .../sysml/runtime/compress/ColGroupBitmap.java | 21 +- .../sysml/runtime/compress/ColGroupOLE.java | 254 ++++++++++--------- .../sysml/runtime/compress/ColGroupRLE.java | 211 ++++++++------- 3 files changed, 262 insertions(+), 224 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java index 0ab65f1..005673c 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupBitmap.java @@ -295,7 +295,7 @@ public abstract class ColGroupBitmap extends ColGroup * @param bitmapIx * @return */ - protected double sumValues(int bitmapIx) + protected final double sumValues(int bitmapIx) { final int numCols = getNumCols(); final int valOff = bitmapIx * numCols; @@ -308,7 +308,7 @@ public abstract class ColGroupBitmap extends ColGroup return val; } - protected double sumValues(int bitmapIx, double[] b) + protected final double sumValues(int bitmapIx, double[] b) { final int numCols = getNumCols(); final int valOff = bitmapIx * numCols; @@ -326,7 +326,7 @@ public abstract class ColGroupBitmap extends ColGroup * @param b * @param c */ - protected void sumAllValues(double[] b, double[] c) + protected final void sumAllValues(double[] b, double[] c) { final int numVals = getNumValues(); final int numCols = getNumCols(); @@ -337,6 +337,21 @@ public abstract class ColGroupBitmap extends ColGroup LinearAlgebraUtils.vectMultiplyAdd(b[i], _values, c, off, 0, numVals); } + + /** + * + * @param numVals + * @param sb + * @return + */ + protected final double[] preaggValues(int numVals, double[] b) { + double[] ret = new double[numVals]; + for( int k = 0; k < numVals; k++ ) + ret[k] = sumValues(k, b); + + return ret; + } + /** * Method for use by subclasses. Applies a scalar operation to the value * metadata stored in the superclass. http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java index 8a0285e..81d57dc 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupOLE.java @@ -84,13 +84,13 @@ public class ColGroupOLE extends ColGroupBitmap _skiplist = new int[numVals]; int rl = (getNumRows()/2/blksz)*blksz; for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = 0; - for( int i=0; i<rl && bufIx<bitmapLen; i+=blksz ) { - bufIx += _data[bitmapOff+bufIx] + 1; + int boff = _ptr[k]; + int blen = len(k); + int bix = 0; + for( int i=0; i<rl && bix<blen; i+=blksz ) { + bix += _data[boff+bix] + 1; } - _skiplist[k] = bufIx; + _skiplist[k] = bix; } } } @@ -125,13 +125,13 @@ public class ColGroupOLE extends ColGroupBitmap //cache conscious append via horizontal scans for( int bi=0; bi<n; bi+=blksz ) { for (int k = 0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; - if( bufIx >= bitmapLen ) + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; + if( bix >= blen ) continue; - int len = _data[bitmapOff+bufIx]; - int pos = bitmapOff+bufIx+1; + int len = _data[boff+bix]; + 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 ) @@ -168,13 +168,13 @@ public class ColGroupOLE extends ColGroupBitmap //cache conscious append via horizontal scans for( int bi=0; bi<n; bi+=blksz ) { for (int k = 0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; - if( bufIx >= bitmapLen ) + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; + if( bix >= blen ) continue; - int len = _data[bitmapOff+bufIx]; - int pos = bitmapOff+bufIx+1; + int len = _data[boff+bix]; + 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 ) @@ -207,13 +207,13 @@ public class ColGroupOLE extends ColGroupBitmap //cache conscious append via horizontal scans for( int bi=0; bi<n; bi+=blksz ) { for (int k = 0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; - if( bufIx >= bitmapLen ) + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; + if( bix >= blen ) continue; - int len = _data[bitmapOff+bufIx]; - int pos = bitmapOff+bufIx+1; + 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]; } @@ -289,30 +289,8 @@ public class ColGroupOLE extends ColGroupBitmap final int blksz2 = ColGroupBitmap.WRITE_CACHE_BLKSZ; //step 1: prepare position and value arrays - - //current pos / values per OLs - int[] apos = new int[numVals]; - double[] aval = new double[numVals]; - - //skip-scan to beginning for all OLs - if( rl > 0 ) { //rl aligned with blksz - int rskip = (getNumRows()/2/blksz)*blksz; - - for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int start = (rl>=rskip)?rskip:0; - int bufIx = (rl>=rskip)?_skiplist[k]:0; - for( int i=start; i<rl && bufIx<bitmapLen; i+=blksz ) { - bufIx += _data[bitmapOff+bufIx] + 1; - } - apos[k] = bufIx; - } - } - - //pre-aggregate values per OLs - for( int k = 0; k < numVals; k++ ) - aval[k] = sumValues(k, sb); + int[] apos = skipScan(numVals, rl); + double[] aval = preaggValues(numVals, sb); //step 2: cache conscious matrix-vector via horizontal scans for( int bi=rl; bi<ru; bi+=blksz2 ) @@ -321,24 +299,22 @@ public class ColGroupOLE extends ColGroupBitmap //horizontal segment scan, incl pos maintenance for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); + int boff = _ptr[k]; + int blen = len(k); double val = aval[k]; - int bufIx = apos[k]; + int bix = apos[k]; - for( int ii=bi; ii<bimax && bufIx<bitmapLen; ii+=blksz ) { + for( int ii=bi; ii<bimax && bix<blen; ii+=blksz ) { //prepare length, start, and end pos - int len = _data[bitmapOff+bufIx]; - int pos = bitmapOff+bufIx+1; + int len = _data[boff+bix]; + int pos = boff+bix+1; //compute partial results - //LinearAlgebraUtils.vectAdd(val, c, bitmaps, pos, ii, len); - for( int i=pos; i<pos+len; i++ ) - c[ii + _data[i]] += val; - bufIx += len + 1; + LinearAlgebraUtils.vectAdd(val, c, _data, pos, ii, len); + bix += len + 1; } - apos[k] = bufIx; + apos[k] = bix; } } } @@ -348,28 +324,28 @@ public class ColGroupOLE extends ColGroupBitmap for (int k = 0; k < numVals; k++) { //prepare value-to-add for entire value bitmap - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); + int boff = _ptr[k]; + int blen = len(k); double val = sumValues(k, sb); //iterate over bitmap blocks and add values if (val != 0) { - int offsetBase = 0; - int bufIx = 0; - int curBlckLen; + int bix = 0; + int off = 0; + int slen = -1; //scan to beginning offset if necessary if( rl > 0 ){ - for (; bufIx<bitmapLen & offsetBase<rl; bufIx += curBlckLen + 1, offsetBase += blksz) { - curBlckLen = _data[bitmapOff+bufIx]; + for (; bix<blen & off<rl; bix += slen+1, off += blksz) { + slen = _data[boff+bix]; } } //compute partial results - for (; bufIx<bitmapLen & offsetBase<ru; bufIx += curBlckLen + 1, offsetBase += blksz) { - curBlckLen = _data[bitmapOff+bufIx]; - for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) { - c[offsetBase + _data[bitmapOff+bufIx + blckIx]] += val; + for (; bix<blen & off<ru; bix += slen + 1, off += blksz) { + slen = _data[boff+bix]; + for (int blckIx = 1; blckIx <= slen; blckIx++) { + c[off + _data[boff+bix + blckIx]] += val; } } } @@ -406,22 +382,22 @@ public class ColGroupOLE extends ColGroupBitmap //horizontal segment scan, incl pos maintenance for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; double vsum = 0; - for( int ii=ai; ii<aimax && bufIx<bitmapLen; ii+=blksz ) { + for( int ii=ai; ii<aimax && bix<blen; ii+=blksz ) { //prepare length, start, and end pos - int len = _data[bitmapOff+bufIx]; - int pos = bitmapOff+bufIx+1; + int len = _data[boff+bix]; + int pos = boff+bix+1; //iterate over bitmap blocks and compute partial results (a[i]*1) vsum += LinearAlgebraUtils.vectSum(a, _data, ii, pos, len); - bufIx += len + 1; + bix += len + 1; } - apos[k] = bufIx; + apos[k] = bix; cvals[k] += vsum; } } @@ -436,13 +412,13 @@ public class ColGroupOLE extends ColGroupBitmap //iterate over all values and their bitmaps for (int k=0, valOff=0; k<numVals; k++, valOff+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); + int boff = _ptr[k]; + int blen = len(k); //iterate over bitmap blocks and add partial results double vsum = 0; - for (int bix=0, off=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1, off+=blksz) - vsum += LinearAlgebraUtils.vectSum(a, _data, off, bitmapOff+bix+1, _data[bitmapOff+bix]); + for (int bix=0, off=0; bix < blen; bix+=_data[boff+bix]+1, off+=blksz) + vsum += LinearAlgebraUtils.vectSum(a, _data, off, boff+bix+1, _data[boff+bix]); //scale partial results by values and write results for( int j = 0; j < numCols; j++ ) @@ -478,16 +454,16 @@ public class ColGroupOLE extends ColGroupBitmap final int numVals = getNumValues(); final int numCols = getNumCols(); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) + for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - int valOff = bitmapIx * numCols; + int boff = _ptr[k]; + int blen = len(k); + int valOff = k * numCols; //iterate over bitmap blocks and count partial lengths int count = 0; - for (int bix=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1) - count += _data[bitmapOff+bix]; + for (int bix=0; bix < blen; bix+=_data[boff+bix]+1) + count += _data[boff+bix]; //scale counts by all values for( int j = 0; j < numCols; j++ ) @@ -510,22 +486,21 @@ public class ColGroupOLE extends ColGroupBitmap final int numVals = getNumValues(); //iterate over all values and their bitmaps - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) + for (int k = 0; k < numVals; k++) { //prepare value-to-add for entire value bitmap - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - double val = sumValues(bitmapIx); + int boff = _ptr[k]; + int blen = len(k); + double val = sumValues(k); //iterate over bitmap blocks and add values if (val != 0) { - int offsetBase = 0; - int bufIx = 0; - int curBlckLen; - for (; bufIx < bitmapLen; bufIx += curBlckLen + 1, offsetBase += blksz) { - curBlckLen = _data[bitmapOff+bufIx]; - for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) { - int rix = offsetBase + _data[bitmapOff+bufIx + blckIx]; + int off = 0; + int slen; + for( int bix = 0; bix < blen; bix += slen + 1, off += blksz ) { + slen = _data[boff+bix]; + for (int i = 1; i <= slen; i++) { + int rix = off + _data[boff+bix + i]; kbuff.set(result.quickGetValue(rix, 0), result.quickGetValue(rix, 1)); kplus.execute2(kbuff, val); result.quickSetValue(rix, 0, kbuff._sum); @@ -547,16 +522,16 @@ public class ColGroupOLE extends ColGroupBitmap //iterate over all values and their bitmaps final int numVals = getNumValues(); final int numCols = getNumCols(); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) + for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - int valOff = bitmapIx * numCols; + int boff = _ptr[k]; + int blen = len(k); + int valOff = k * numCols; //iterate over bitmap blocks and count partial lengths int count = 0; - for (int bix=0; bix < bitmapLen; bix+=_data[bitmapOff+bix]+1) - count += _data[bitmapOff+bix]; + for (int bix=0; bix < blen; bix+=_data[boff+bix]+1) + count += _data[boff+bix]; //scale counts by all values for( int j = 0; j < numCols; j++ ) { @@ -585,20 +560,19 @@ public class ColGroupOLE extends ColGroupBitmap Arrays.fill(ret, true); //iterate over all values and their bitmaps - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) + for (int k = 0; k < numVals; k++) { //prepare value-to-add for entire value bitmap - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); + int boff = _ptr[k]; + int blen = len(k); //iterate over bitmap blocks and add values - int offsetBase = 0; - int bufIx = 0; - int curBlckLen; - for (; bufIx < bitmapLen; bufIx += curBlckLen + 1, offsetBase += blksz) { - curBlckLen = _data[bitmapOff+bufIx]; - for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) { - ret[offsetBase + _data[bitmapOff+bufIx + blckIx]] &= false; + int off = 0; + int slen; + for( int bix=0; bix < blen; bix+=slen+1, off+=blksz) { + slen = _data[boff+bix]; + for (int i = 1; i <= slen; i++) { + ret[off + _data[boff+bix + i]] &= false; } } } @@ -617,18 +591,52 @@ public class ColGroupOLE extends ColGroupBitmap for (int k = 0; k < numVals; k++) { //prepare value-to-add for entire value bitmap - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); + int boff = _ptr[k]; + int blen = len(k); //iterate over bitmap blocks and add values - int offsetBase = 0; - int curBlckLen; - for (int bufIx=0; bufIx<bitmapLen; bufIx+=curBlckLen+1, offsetBase+=blksz) { - curBlckLen = _data[bitmapOff+bufIx]; - for (int blckIx = 1; blckIx <= curBlckLen; blckIx++) { - rnnz[offsetBase + _data[bitmapOff+bufIx + blckIx]] += numCols; + int off = 0; + int slen; + for (int bix=0; bix<blen; bix+=slen+1, off+=blksz) { + slen = _data[boff+bix]; + for (int blckIx = 1; blckIx <= slen; blckIx++) { + rnnz[off + _data[boff+bix + blckIx]] += numCols; + } + } + } + } + + ///////////////////////////////// + // internal helper functions + + /** + * Scans to given row_lower position by exploiting any existing + * skip list and scanning segment length fields. Returns array + * of positions for all values; + * + * @param numVals + * @param rl + * @return + */ + private int[] skipScan(int numVals, int rl) { + int[] ret = new int[numVals]; + final int blksz = BitmapEncoder.BITMAP_BLOCK_SZ; + + if( rl > 0 ) { //rl aligned with blksz + int rskip = (getNumRows()/2/blksz)*blksz; + + for( int k = 0; k < numVals; k++ ) { + int boff = _ptr[k]; + int blen = len(k); + int start = (rl>=rskip)?rskip:0; + int bix = (rl>=rskip)?_skiplist[k]:0; + for( int i=start; i<rl && bix<blen; i+=blksz ) { + bix += _data[boff+bix] + 1; } + ret[k] = bix; } } + + return ret; } } http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/b1dc0d5b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java index 05d77f8..017a7d3 100644 --- a/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java +++ b/src/main/java/org/apache/sysml/runtime/compress/ColGroupRLE.java @@ -65,9 +65,9 @@ public class ColGroupRLE extends ColGroupBitmap final int numVals = ubm.getNumValues(); char[][] lbitmaps = new char[numVals][]; int totalLen = 0; - for( int i=0; i<numVals; i++ ) { - lbitmaps[i] = BitmapEncoder.genRLEBitmap(ubm.getOffsetsList(i)); - totalLen += lbitmaps[i].length; + for( int k=0; k<numVals; k++ ) { + lbitmaps[k] = BitmapEncoder.genRLEBitmap(ubm.getOffsetsList(k)); + totalLen += lbitmaps[k].length; } // compact bitmaps to linearized representation @@ -106,20 +106,20 @@ public class ColGroupRLE extends ColGroupBitmap for( int bi=0; bi<n; bi+=blksz ) { int bimax = Math.min(bi+blksz, n); for (int k=0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; int start = astart[k]; - for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) { - start += _data[bitmapOff + bufIx]; - int len = _data[bitmapOff + bufIx+1]; + for( ; bix<blen & start<bimax; bix+=2) { + start += _data[boff + bix]; + 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, _colIndexes[j], _values[off+j]); start += len; } - apos[k] = bufIx; + apos[k] = bix; astart[k] = start; } } @@ -154,22 +154,22 @@ public class ColGroupRLE extends ColGroupBitmap for( int bi=0; bi<n; bi+=blksz ) { int bimax = Math.min(bi+blksz, n); for (int k=0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; - if( bufIx >= bitmapLen ) + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; + if( bix >= blen ) continue; int start = astart[k]; - for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) { - start += _data[bitmapOff + bufIx]; - int len = _data[bitmapOff + bufIx+1]; + for( ; bix<blen & start<bimax; bix+=2) { + start += _data[boff + bix]; + 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]); start += len; } - apos[k] = bufIx; + apos[k] = bix; astart[k] = start; } } @@ -200,20 +200,20 @@ public class ColGroupRLE extends ColGroupBitmap for( int bi=0; bi<n; bi+=blksz ) { int bimax = Math.min(bi+blksz, n); for (int k=0, off=0; k < numVals; k++, off+=numCols) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; - if( bufIx >= bitmapLen ) + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; + if( bix >= blen ) continue; int start = astart[k]; - for( ; bufIx<bitmapLen & start<bimax; bufIx+=2) { - start += _data[bitmapOff + bufIx]; - int len = _data[bitmapOff + bufIx+1]; + for( ; bix<blen & start<bimax; bix+=2) { + start += _data[boff + bix]; + int len = _data[boff + bix+1]; for( int i=start; i<start+len; i++ ) c[i] = _values[off+colpos]; start += len; } - apos[k] = bufIx; + apos[k] = bix; astart[k] = start; } } @@ -253,34 +253,10 @@ public class ColGroupRLE extends ColGroupBitmap //step 1: prepare position and value arrays //current pos / values per RLE list - int[] apos = new int[numVals]; int[] astart = new int[numVals]; - double[] aval = new double[numVals]; - - //skip-scan to beginning for all OLs - if( rl > 0 ) { //rl aligned with blksz - for (int k = 0; k < numVals; k++) { - int boff = _ptr[k]; - int blen = len(k); - int bix = 0; - int start = 0; - while( bix<blen ) { - int lstart = _data[boff + bix]; //start - int llen = _data[boff + bix + 1]; //len - if( start+lstart+llen >= rl ) - break; - start += lstart + llen; - bix += 2; - } - apos[k] = bix; - astart[k] = start; - } - } + int[] apos = skipScan(numVals, rl, astart); + double[] aval = preaggValues(numVals, sb); - //pre-aggregate values per OLs - for( int k = 0; k < numVals; k++ ) - aval[k] = sumValues(k, sb); - //step 2: cache conscious matrix-vector via horizontal scans for( int bi=rl; bi<ru; bi+=blksz ) { @@ -376,21 +352,21 @@ public class ColGroupRLE extends ColGroupBitmap //horizontal scan, incl pos maintenance for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); - int bufIx = apos[k]; + int boff = _ptr[k]; + int blen = len(k); + int bix = apos[k]; int start = astart[k]; //compute partial results, not aligned - while( bufIx<bitmapLen & start<aimax ) { - start += _data[bitmapOff + bufIx]; - int len = _data[bitmapOff + bufIx+1]; + while( bix<blen & start<aimax ) { + start += _data[boff + bix]; + int len = _data[boff + bix+1]; cvals[k] += LinearAlgebraUtils.vectSum(a, start, len); start += len; - bufIx += 2; + bix += 2; } - apos[k] = bufIx; + apos[k] = bix; astart[k] = start; } } @@ -404,16 +380,16 @@ public class ColGroupRLE extends ColGroupBitmap else { //iterate over all values and their bitmaps - for (int bitmapIx=0, valOff=0; bitmapIx<numVals; bitmapIx++, valOff+=numCols) + for (int k=0, valOff=0; k<numVals; k++, valOff+=numCols) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); + int boff = _ptr[k]; + int blen = len(k); double vsum = 0; int curRunEnd = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - int curRunLen = _data[bitmapOff+bufIx + 1]; + for ( int bix = 0; bix < blen; bix+=2 ) { + int curRunStartOff = curRunEnd + _data[boff+bix]; + int curRunLen = _data[boff+bix+1]; vsum += LinearAlgebraUtils.vectSum(a, curRunStartOff, curRunLen); curRunEnd = curRunStartOff + curRunLen; } @@ -484,15 +460,15 @@ public class ColGroupRLE extends ColGroupBitmap final int numCols = getNumCols(); final int numVals = getNumValues(); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - int valOff = bitmapIx * numCols; + for (int k = 0; k < numVals; k++) { + int boff = _ptr[k]; + int blen = len(k); + int valOff = k * numCols; int curRunEnd = 0; int count = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1]; + for (int bix = 0; bix < blen; bix+=2) { + int curRunStartOff = curRunEnd + _data[boff+bix]; + curRunEnd = curRunStartOff + _data[boff+bix+1]; count += curRunEnd-curRunStartOff; } @@ -514,17 +490,17 @@ public class ColGroupRLE extends ColGroupBitmap KahanObject kbuff = new KahanObject(0, 0); final int numVals = getNumValues(); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - double val = sumValues(bitmapIx); + for (int k = 0; k < numVals; k++) { + int boff = _ptr[k]; + int blen = len(k); + double val = sumValues(k); if (val != 0.0) { int curRunStartOff = 0; int curRunEnd = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1]; + for (int bix = 0; bix < blen; bix+=2) { + curRunStartOff = curRunEnd + _data[boff+bix]; + curRunEnd = curRunStartOff + _data[boff+bix+1]; for (int rix = curRunStartOff; rix < curRunEnd; rix++) { kbuff.set(result.quickGetValue(rix, 0), result.quickGetValue(rix, 1)); kplus.execute2(kbuff, val); @@ -547,15 +523,15 @@ public class ColGroupRLE extends ColGroupBitmap final int numCols = getNumCols(); final int numVals = getNumValues(); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); - int valOff = bitmapIx * numCols; + for (int k = 0; k < numVals; k++) { + int boff = _ptr[k]; + int blen = len(k); + int valOff = k * numCols; int curRunEnd = 0; int count = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - int curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1]; + for (int bix=0; bix < blen; bix+=2) { + int curRunStartOff = curRunEnd + _data[boff+bix]; + curRunEnd = curRunStartOff + _data[boff+bix+1]; count += curRunEnd-curRunStartOff; } @@ -578,15 +554,15 @@ public class ColGroupRLE extends ColGroupBitmap //initialize everything with zero Arrays.fill(ret, true); - for (int bitmapIx = 0; bitmapIx < numVals; bitmapIx++) { - int bitmapOff = _ptr[bitmapIx]; - int bitmapLen = len(bitmapIx); + for (int k = 0; k < numVals; k++) { + int boff = _ptr[k]; + int blen = len(k); int curRunStartOff = 0; int curRunEnd = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1]; + for (int bix = 0; bix < blen; bix+=2) { + curRunStartOff = curRunEnd + _data[boff+bix]; + curRunEnd = curRunStartOff + _data[boff+bix + 1]; Arrays.fill(ret, curRunStartOff, curRunEnd, false); } } @@ -601,17 +577,56 @@ public class ColGroupRLE extends ColGroupBitmap final int numCols = getNumCols(); for (int k = 0; k < numVals; k++) { - int bitmapOff = _ptr[k]; - int bitmapLen = len(k); + int boff = _ptr[k]; + int blen = len(k); int curRunStartOff = 0; int curRunEnd = 0; - for (int bufIx = 0; bufIx < bitmapLen; bufIx += 2) { - curRunStartOff = curRunEnd + _data[bitmapOff+bufIx]; - curRunEnd = curRunStartOff + _data[bitmapOff+bufIx + 1]; + for (int bix = 0; bix < blen; bix+=2) { + curRunStartOff = curRunEnd + _data[boff+bix]; + curRunEnd = curRunStartOff + _data[boff+bix + 1]; for( int i=curRunStartOff; i<curRunEnd; i++ ) rnnz[i] += numCols; } } } + + ///////////////////////////////// + // internal helper functions + + + /** + * Scans to given row_lower position by scanning run length + * fields. Returns array of positions for all values and modifies + * given array of start positions for all values too. + * + * @param numVals + * @param rl + * @param astart + * @return + */ + private int[] skipScan(int numVals, int rl, int[] astart) { + int[] apos = new int[numVals]; + + if( rl > 0 ) { //rl aligned with blksz + for (int k = 0; k < numVals; k++) { + int boff = _ptr[k]; + int blen = len(k); + int bix = 0; + int start = 0; + while( bix<blen ) { + int lstart = _data[boff + bix]; //start + int llen = _data[boff + bix + 1]; //len + if( start+lstart+llen >= rl ) + break; + start += lstart + llen; + bix += 2; + } + apos[k] = bix; + astart[k] = start; + } + } + + return apos; + } }
