[SYSTEMML-1045] Fix CSR block growth rate on resize (update-in-place)

So far, we used an aggressive 2x growth rate for CSR sparse
representations. In comparison to MCSR, this significantly affects
temporary memory requirements as this applies to the entire matrix not
just a single row. For update-in-place left indexing, the growth is
covered by the input + output memory requirements, which are roughly 2x
the input but not 3x as required for a rate of 2x. We now use a
conservative 1.1x rate. Furthermore, this patch also cleans up some
unnecessary redundancy of the related resizing logic and fixes incorrect
size computation (for small initial capacities).

Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: 
http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/af7d7f05
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/af7d7f05
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/af7d7f05

Branch: refs/heads/master
Commit: af7d7f05bc5e43cda129f72cb7cd4f1a2cffbb97
Parents: 3895443
Author: Matthias Boehm <mboe...@gmail.com>
Authored: Thu Oct 13 20:28:06 2016 -0700
Committer: Matthias Boehm <mboe...@gmail.com>
Committed: Thu Oct 13 20:28:06 2016 -0700

----------------------------------------------------------------------
 .../runtime/matrix/data/SparseBlockCSR.java     | 27 +++++++++++---------
 1 file changed, 15 insertions(+), 12 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/af7d7f05/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java
----------------------------------------------------------------------
diff --git 
a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java 
b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java
index a26a834..fe1dde7 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/SparseBlockCSR.java
@@ -691,14 +691,23 @@ public class SparseBlockCSR extends SparseBlock
        ///////////////////////////
        // private helper methods
        
+       private int newCapacity(int minsize) {
+               //compute new size until minsize reached
+               double tmpCap = _values.length;
+               while( tmpCap < minsize ) {
+                       tmpCap *= (tmpCap <= 1024) ? 
+                                       RESIZE_FACTOR1 : RESIZE_FACTOR2;
+               }
+                       
+               return (int)Math.min(tmpCap, Integer.MAX_VALUE);
+       }
+       
        /**
         * 
         */
        private void resize() {
-               //compute new size
-               double tmpCap = _values.length * RESIZE_FACTOR1;
-               int newCap = (int)Math.min(tmpCap, Integer.MAX_VALUE);
-               
+               //resize by at least by 1
+               int newCap = newCapacity(_values.length+1);
                resizeCopy(newCap);
        }
        
@@ -707,12 +716,7 @@ public class SparseBlockCSR extends SparseBlock
         * @param minsize
         */
        private void resize(int minsize) {
-               //compute new size until minsize reached
-               double tmpCap = _values.length;
-               while( tmpCap < minsize )
-                       tmpCap *= RESIZE_FACTOR1;
-               int newCap = (int)Math.min(tmpCap, Integer.MAX_VALUE);
-               
+               int newCap = newCapacity(minsize);
                resizeCopy(newCap);
        }
        
@@ -734,8 +738,7 @@ public class SparseBlockCSR extends SparseBlock
         */
        private void resizeAndInsert(int ix, int c, double v) {
                //compute new size
-               double tmpCap = _values.length * RESIZE_FACTOR1;
-               int newCap = (int)Math.min(tmpCap, Integer.MAX_VALUE);
+               int newCap = newCapacity(_values.length+1);
                
                int[] oldindexes = _indexes;
                double[] oldvalues = _values;

Reply via email to