Split iterating into subspaces for performance

4 files changed, 74 insertions, 20 deletions

diff --git a/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
index 5e91679c412..d1523d6fcf9 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/IndexedTensorTestCase.java
@@ -56,10 +56,10 @@ public class IndexedTensorTestCase {
         assertEquals(emptyWithDimensions, emptyWithDimensionsFromString);
 
         IndexedTensor emptyWithDimensionsIndexed = (IndexedTensor)emptyWithDimensions;
-        assertEquals(0, emptyWithDimensionsIndexed.length(0));
-        assertEquals(0, emptyWithDimensionsIndexed.length(1));
+        assertEquals(0, emptyWithDimensionsIndexed.size(0));
+        assertEquals(0, emptyWithDimensionsIndexed.size(1));
     }
-
+    
     @Test
     public void testBoundBuilding() {
         TensorType type = new TensorType.Builder().indexed("v", vSize)
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java
new file mode 100644
index 00000000000..63dd4a4a644
--- /dev/null
+++ b/vespajlib/src/test/java/com/yahoo/tensor/JoinTestCase.java
@@ -0,0 +1,36 @@
+package com.yahoo.tensor;
+
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author bratseth
+ */
+public class JoinTestCase {
+    
+    /** Test the indexed subspace join optimization */
+    @Test
+    public void testJoinIndexedSubspace() {
+        Tensor t1, t2;
+        
+        t1 = Tensor.from("tensor(x[]):{{x:0}:1.0,{x:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:20.0,{x:1,y:1,z:0}:0.0}"),
+                     t1.multiply(t2));
+        t1 = Tensor.from("tensor(x[]):{{x:0}:1.0,{x:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:5.0,{x:1,y:1,z:0}:0.0}"),
+                     t2.divide(t1));
+
+        t1 = Tensor.from("tensor(y[]):{{y:0}:1.0,{y:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10.0,{x:1,y:1,z:0}:0.0}"),
+                     t1.multiply(t2));
+        t1 = Tensor.from("tensor(y[]):{{y:0}:1.0,{y:1}:2.0}");
+        t2 = Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10,{x:1,y:1,z:0}:0.0}");
+        assertEquals(Tensor.from("tensor(x[],y[],z[]):{{x:0,y:0,z:0}:6,{x:0,y:1,z:0}:0.0,{x:1,y:0,z:0}:10.0,{x:1,y:1,z:0}:0.0}"),
+                     t2.divide(t1));
+    }
+    
+}
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
index bbab92fc16d..a450e3ec9e7 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java
@@ -117,12 +117,12 @@ public class TensorFunctionBenchmark {
         // - After adding type: 300 ms
         // - After sorting dimensions: 100 ms
         // - After special-casing single space: 2.4 ms
-        time = new TensorFunctionBenchmark().benchmark(5000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
-        System.out.printf("Mapped vectors,          time per join: %1$8.3f ms\n", time);
+        //time = new TensorFunctionBenchmark().benchmark(5000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
+        //System.out.printf("Mapped vectors,          time per join: %1$8.3f ms\n", time);
         // Initial: 760 ms
         // - After special-casing subspace: 13 ms
-        time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
-        System.out.printf("Mapped matrix,           time per join: %1$8.3f ms\n", time);
+        //time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, false);
+        //System.out.printf("Mapped matrix,           time per join: %1$8.3f ms\n", time);
 
         // ---------------- Indexed (unbound) with extra space (sidesteps current special-case optimizations):
         // Initial: 1900 ms
@@ -139,21 +139,25 @@ public class TensorFunctionBenchmark {
         // - After special casing join: 3.6 ms
         // - After special-casing reduce: 0.80 ms
         // - After create IndexedTensor without builder: 0.4 ms
-        // - After double-array backing: 0.1 ms
-        time = new TensorFunctionBenchmark().benchmark(10000, vectors(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
+        // - After double-array backing: 0.09 ms
+        time = new TensorFunctionBenchmark().benchmark(50000, vectors(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
         System.out.printf("Indexed unbound vectors, time per join: %1$8.3f ms\n", time);
         // Initial: 3500 ms
         // - After special-casing subspace: 25 ms
-        // - After moving to iterators: 10 ms
+        // - After moving to iterators: 7.7 ms
+        // - After indexed subspace join algorithm: 6
+        // - After passing sized: 3.7 ms
         time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, false);
         System.out.printf("Indexed unbound matrix,  time per join: %1$8.3f ms\n", time);
 
         // ---------------- Indexed bound:
-        // Initial: 0.1 ms
-        time = new TensorFunctionBenchmark().benchmark(10000, vectors(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
+        // Initial: 0.09 ms
+        time = new TensorFunctionBenchmark().benchmark(50000, vectors(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
         System.out.printf("Indexed bound vectors,   time per join: %1$8.3f ms\n", time);
         // Initial: 25 ms
-        // - After moving to iterators: 10 ms
+        // - After moving to iterators: 7.7 ms
+        // - After indexed subspace join algorithm: 6
+        // - After passing sized: 3.7 ms
         time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.indexedBound), TensorType.Dimension.Type.indexedBound, false);
         System.out.printf("Indexed bound matrix,    time per join: %1$8.3f ms\n", time);
 
diff --git a/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java b/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
index aa220e93258..eaf26fd82cd 100644
--- a/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
+++ b/vespajlib/src/test/java/com/yahoo/tensor/TensorTestCase.java
@@ -79,11 +79,15 @@ public class TensorTestCase {
     @Test
     public void testOptimizedComputation() {
         assertEquals("Mapped vector",          42, (int)dotProduct(vector(Type.mapped), vectors(Type.mapped, 2)));
-        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(Type.indexedUnbound), vectors(Type.indexedUnbound, 2)));
-        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(Type.indexedBound), vectors(Type.indexedBound, 2)));
+        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(3, Type.indexedUnbound), vectors(5, Type.indexedUnbound, 2)));
+        assertEquals("Indexed unbound vector", 42, (int)dotProduct(vector(5, Type.indexedUnbound), vectors(3, Type.indexedUnbound, 2)));
+        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(3, Type.indexedBound), vectors(5, Type.indexedBound, 2)));
+        assertEquals("Indexed bound vector",   42, (int)dotProduct(vector(5, Type.indexedBound), vectors(3, Type.indexedBound, 2)));
         assertEquals("Mapped matrix",          42, (int)dotProduct(vector(Type.mapped), matrix(Type.mapped, 2)));
-        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(Type.indexedUnbound), matrix(Type.indexedUnbound, 2)));
-        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(Type.indexedBound), matrix(Type.indexedBound, 2)));
+        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(3, Type.indexedUnbound), matrix(5, Type.indexedUnbound, 2)));
+        assertEquals("Indexed unbound matrix", 42, (int)dotProduct(vector(5, Type.indexedUnbound), matrix(3, Type.indexedUnbound, 2)));
+        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(3, Type.indexedBound), matrix(5, Type.indexedBound, 2)));
+        assertEquals("Indexed bound matrix",   42, (int)dotProduct(vector(5, Type.indexedBound), matrix(3, Type.indexedBound, 2)));
         assertEquals("Mixed vector",           42, (int)dotProduct(vector(Type.mapped), vectors(Type.indexedUnbound, 2)));
         assertEquals("Mixed vector",           42, (int)dotProduct(vector(Type.mapped), vectors(Type.indexedUnbound, 2)));
         assertEquals("Mixed matrix",           42, (int)dotProduct(vector(Type.mapped), matrix(Type.indexedUnbound, 2)));
@@ -100,7 +104,7 @@ public class TensorTestCase {
         Tensor matrixInKSpace = matrix(Type.mapped, 2).get(0).multiply(unitK);
         assertEquals("Generic computation implementation", 42, (int)dotProduct(vectorInJSpace, Collections.singletonList(matrixInKSpace)));
     }
-
+    
     private double dotProduct(Tensor tensor, List<Tensor> tensors) {
         double sum = 0;
         TensorFunction dotProductFunction = new Reduce(new Join(new ConstantTensor(tensor),
@@ -119,10 +123,17 @@ public class TensorTestCase {
     private Tensor vector(TensorType.Dimension.Type dimensionType) {
         return vectors(dimensionType, 1).get(0);
     }
+
+    private Tensor vector(int vectorSize, TensorType.Dimension.Type dimensionType) {
+        return vectors(vectorSize, dimensionType, 1).get(0);
+    }
     
     /** Create a list of vectors having a single dimension x */
     private List<Tensor> vectors(TensorType.Dimension.Type dimensionType, int vectorCount) {
-        int vectorSize = 3;
+        return vectors(3, dimensionType, vectorCount);
+    }
+
+    private List<Tensor> vectors(int vectorSize, TensorType.Dimension.Type dimensionType, int vectorCount) {
         List<Tensor> tensors = new ArrayList<>();
         TensorType type = vectorType(new TensorType.Builder(), "x", dimensionType, vectorSize);
         for (int i = 0; i < vectorCount; i++) {
@@ -140,7 +151,10 @@ public class TensorTestCase {
      * This matrix contains the same vectors as returned by createVectors, in a single list element for convenience.
      */
     private List<Tensor> matrix(TensorType.Dimension.Type dimensionType, int vectorCount) {
-        int vectorSize = 3;
+        return matrix(3, dimensionType, vectorCount);
+    }
+
+    private List<Tensor> matrix(int vectorSize, TensorType.Dimension.Type dimensionType, int vectorCount) {
         TensorType.Builder typeBuilder = new TensorType.Builder();
         typeBuilder.dimension("i", dimensionType == Type.indexedBound ? Type.indexedUnbound : dimensionType);
         vectorType(typeBuilder, "x", dimensionType, vectorSize);