diff options
10 files changed, 400 insertions, 112 deletions
diff --git a/searchlib/src/main/java/com/yahoo/searchlib/rankingexpression/evaluation/TensorValue.java b/searchlib/src/main/java/com/yahoo/searchlib/rankingexpression/evaluation/TensorValue.java index 6b67fca791d..6d038113691 100644 --- a/searchlib/src/main/java/com/yahoo/searchlib/rankingexpression/evaluation/TensorValue.java +++ b/searchlib/src/main/java/com/yahoo/searchlib/rankingexpression/evaluation/TensorValue.java @@ -23,16 +23,9 @@ public class TensorValue extends Value { /** The tensor value of this */ private final Tensor value; - private final Optional<TensorType> type; - + public TensorValue(Tensor value) { this.value = value; - this.type = Optional.empty(); - } - - public TensorValue(Tensor value, TensorType type) { - this.value = value; - this.type = Optional.of(type); } @Override @@ -97,10 +90,6 @@ public class TensorValue extends Value { public Tensor asTensor() { return value; } - public Optional<TensorType> getType() { - return type; - } - @Override public Value compare(TruthOperator operator, Value argument) { return new TensorValue(compareTensor(operator, asTensor(argument, operator.toString()))); @@ -150,18 +139,13 @@ public class TensorValue extends Value { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; - TensorValue that = (TensorValue) o; - - if (!type.equals(that.type)) return false; - if (!value.equals(that.value)) return false; - - return true; + TensorValue other = (TensorValue) o; + return value.equals(other.value); } @Override public int hashCode() { - int result = value.hashCode(); - result = 31 * result + type.hashCode(); - return result; + return value.hashCode(); } + } diff --git a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java index 4091fd97a16..1719a4ecc7a 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java @@ -12,6 +12,7 @@ import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Optional; +import java.util.Set; /** * An indexed (dense) tensor backed by a double array. @@ -60,6 +61,20 @@ public class IndexedTensor implements Tensor { return new ValueIterator(); } + /** + * Returns an iterator over value iterators where the outer iterator is over each unique value of the dimensions + * given and the inner iterator is over each unique value of the rest of the dimensions, in the same order as + * other iterator. + * + * @param dimensions the names of the dimensions of the superspace + * @param dimensionSizes the size of each dimension in the space we are returning values for, containing + * one value per dimension of this tensor (in order). Each size may be the same or smaller + * than the corresponding size of this tensor + */ + public Iterator<SubspaceIterator> subspaceIterator(Set<String> dimensions, int[] dimensionSizes) { + return new SuperspaceIterator(dimensions, dimensionSizes); + } + /** * Returns the value at the given indexes * @@ -82,7 +97,13 @@ public class IndexedTensor implements Tensor { return Double.NaN; } } - + + /** Returns the value at these indexes */ + private double get(Indexes indexes) { + return values[toValueIndex(indexes.indexesForReading(), dimensionSizes)]; + } + + // TODO: Change to get private static int toValueIndex(int[] indexes, int[] dimensionSizes) { if (indexes.length == 1) return indexes[0]; // for speed if (indexes.length == 0) return 0; // for speed @@ -92,7 +113,8 @@ public class IndexedTensor implements Tensor { valueIndex += productOfDimensionsAfter(i, dimensionSizes) * indexes[i]; return valueIndex; } - + + // TODO: Change to get private static int toValueIndex(TensorAddress address, int[] dimensionSizes) { if (address.labels().isEmpty()) return 0; @@ -113,11 +135,11 @@ public class IndexedTensor implements Tensor { public TensorType type() { return type; } /** - * Returns the lenght of this in the nth dimension + * Returns the length of this in the nth dimension * * @throws IndexOutOfBoundsException if the index is larger than the number of dimensions in this tensor minus one */ - public int length(int dimension) { + public int size(int dimension) { return dimensionSizes[dimension]; } @@ -127,30 +149,15 @@ public class IndexedTensor implements Tensor { return values.length == 0 ? Collections.emptyMap() : Collections.singletonMap(TensorAddress.empty, values[0]); ImmutableMap.Builder<TensorAddress, Double> builder = new ImmutableMap.Builder<>(); - int[] tensorIndexes = new int[dimensionSizes.length]; + Indexes indexes = new Indexes(dimensionSizes, values.length); for (int i = 0; i < values.length; i++) { - builder.put(new TensorAddress(tensorIndexes), values[i]); + builder.put(indexes.toAddress(), values[i]); if (i < values.length -1) - next(tensorIndexes); + indexes.next(); } return builder.build(); } - private void next(int[] tensorIndexes) { - nextRecursively(tensorIndexes.length - 1, tensorIndexes); - } - - // TODO: Tail recursion -> loop - private void nextRecursively(int dimension, int[] tensorIndexes) { - if (tensorIndexes[dimension] + 1 == dimensionSizes[dimension]) { - tensorIndexes[dimension] = 0; - nextRecursively(dimension - 1, tensorIndexes); - } - else { - tensorIndexes[dimension]++; - } - } - @Override public int hashCode() { return Arrays.hashCode(values); } @@ -190,9 +197,9 @@ public class IndexedTensor implements Tensor { " for " + type); for (int i = 0; i < dimensionSizes.length; i++ ) { Optional<Integer> size = type.dimensions().get(i).size(); - if (size.isPresent() && size.get() != dimensionSizes[i]) - throw new IllegalArgumentException("Size of " + type.dimensions() + " must be " + size.get() + - ", not " + dimensionSizes[i]); + if (size.isPresent() && size.get() < dimensionSizes[i]) + throw new IllegalArgumentException("Size of " + type.dimensions() + " is " + dimensionSizes[i] + + " but cannot be larger than " + size.get()); } return new BoundBuilder(type, dimensionSizes); @@ -397,71 +404,251 @@ public class IndexedTensor implements Tensor { } + // TODO: Generalize to vector cell iterator? private final class CellIterator implements Iterator<Map.Entry<TensorAddress, Double>> { - private int cursor = 0; - private final int[] tensorIndexes = new int[dimensionSizes.length]; + private int count = 0; + private final Indexes indexes = new Indexes(dimensionSizes, values.length); @Override public boolean hasNext() { - return cursor < values.length; + return count < indexes.size(); } @Override public Map.Entry<TensorAddress, Double> next() { - if ( ! hasNext()) throw new NoSuchElementException(); + if ( ! hasNext()) throw new NoSuchElementException("No cell at " + indexes); - Map.Entry<TensorAddress, Double> current = new Cell(new TensorAddress(tensorIndexes), values[cursor]); + Map.Entry<TensorAddress, Double> current = new Cell(indexes.toAddress(), values[count]); // TODO: Correct to get(indexes) - cursor++; + count++; if (hasNext()) - IndexedTensor.this.next(tensorIndexes); + indexes.next(); return current; } - private class Cell implements Map.Entry<TensorAddress, Double> { + } - private final TensorAddress address; - private final Double value; - - private Cell(TensorAddress address, Double value) { - this.address = address; - this.value = value; - } - - @Override - public TensorAddress getKey() { return address; } + private class Cell implements Map.Entry<TensorAddress, Double> { - @Override - public Double getValue() { return value; } + private final TensorAddress address; + private final Double value; - @Override - public Double setValue(Double value) { - throw new UnsupportedOperationException("A tensor cannot be modified"); - } + private Cell(TensorAddress address, Double value) { + this.address = address; + this.value = value; + } + + @Override + public TensorAddress getKey() { return address; } + @Override + public Double getValue() { return value; } + + @Override + public Double setValue(Double value) { + throw new UnsupportedOperationException("A tensor cannot be modified"); } } private final class ValueIterator implements Iterator<Double> { - private int cursor = 0; + private int count = 0; @Override public boolean hasNext() { - return cursor < values.length; + return count < values.length; } @Override public Double next() { try { - return values[cursor++]; + return values[count++]; } catch (IndexOutOfBoundsException e) { - throw new NoSuchElementException("No element at position " + cursor); + throw new NoSuchElementException("No element at position " + count); + } + } + + } + + private final class SuperspaceIterator implements Iterator<SubspaceIterator> { + + private final Indexes superindexes; + + /** true at indexes whose dimension subspaces iterate over */ + private final boolean[] subdimensionIndexes; + + /** + * The sizes of the space we'll return values of, one value for each dimension of this tensor, + * which may be equal to or smaller than the sizes of this tensor + */ + private final int[] dimensionSizes; + + private int count = 0; + + private SuperspaceIterator(Set<String> superdimensionNames, int[] dimensionSizes) { + this.dimensionSizes = dimensionSizes; + + boolean[] superdimensionIndexes = new boolean[dimensionSizes.length]; // for outer iterator + subdimensionIndexes = new boolean [dimensionSizes.length]; // for inner iterator + for (int i = 0; i < type.dimensions().size(); i++ ) { + boolean superDimension = superdimensionNames.contains(type.dimensions().get(i).name()); + superdimensionIndexes[i] = superDimension; + subdimensionIndexes[i] = ! superDimension; + } + + superindexes = new Indexes(dimensionSizes, superdimensionIndexes); + } + + @Override + public boolean hasNext() { + return count < superindexes.size(); + } + + @Override + public SubspaceIterator next() { + if ( ! hasNext()) throw new NoSuchElementException("No cell at " + superindexes); + SubspaceIterator subspace = new SubspaceIterator(subdimensionIndexes, superindexes.indexesCopy(), dimensionSizes); + count++; + if (hasNext()) + superindexes.next(); + return subspace; + } + + } + + /** + * An iterator over a subspace of this tensor. This is exposed to allow clients to query the size. + */ + public final class SubspaceIterator implements Iterator<Map.Entry<TensorAddress, Double>> { + + private final Indexes indexes; + private int count = 0; + + /** + * Creates a new subspace iterator + * + * @param dimensionIndexes a boolean array with a true entry for dimensions we should iterate over and false + * entries for all other dimensions + * @param address the address of the first cell of this subspace. + */ + private SubspaceIterator(boolean[] dimensionIndexes, int[] address, int[] dimensionSizes) { + this.indexes = new Indexes(dimensionSizes, dimensionIndexes, address); + } + + /** Returns the total number of cells in this subspace */ + public int size() { + return indexes.size(); + } + + @Override + public boolean hasNext() { return count < indexes.size(); } + + @Override + public Map.Entry<TensorAddress, Double> next() { + if ( ! hasNext()) throw new NoSuchElementException("No cell at " + indexes); + + Map.Entry<TensorAddress, Double> current = new Cell(indexes.toAddress(), get(indexes)); + + count++; + if (hasNext()) + indexes.next(); + + return current; + } + + } + + /** An array of indexes into this tensor which are able to find the next index in the value order */ + private static class Indexes { + + private final int size; + private final int[] indexes; + + private final int[] dimensionSizes; + + /** Only mutate (take next in) the dimension indexes which are true */ + private final boolean[] iteratingDimensions; + + private Indexes(int[] dimensionSizes, int size) { + this(dimensionSizes, trueArray(dimensionSizes.length), size); + } + + private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions) { + this(dimensionSizes, iteratingDimensions, computeSize(dimensionSizes, iteratingDimensions)); + } + + private Indexes(int[] dimensionSizes, boolean[] iteratingDimensionIndexes, int size) { + this(dimensionSizes, iteratingDimensionIndexes, new int[dimensionSizes.length], size); + } + + private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions, int[] initialIndexes) { + this(dimensionSizes, iteratingDimensions, initialIndexes, computeSize(dimensionSizes, iteratingDimensions)); + } + + private Indexes(int[] dimensionSizes, boolean[] iteratingDimensions, int[] initialIndexes, int size) { + this.dimensionSizes = dimensionSizes; + this.iteratingDimensions = iteratingDimensions; + this.indexes = initialIndexes; + this.size = size; + } + + private static boolean[] trueArray(int size) { + boolean[] array = new boolean[size]; + Arrays.fill(array, true); + return array; + } + + private static int computeSize(int[] dimensionSizes, boolean[] iteratingDimensions) { + int size = 1; + for (int dimensionIndex = 0; dimensionIndex < dimensionSizes.length; dimensionIndex++) + if (iteratingDimensions[dimensionIndex]) + size *= dimensionSizes[dimensionIndex]; + return size; + } + + private static boolean anyTrue(boolean[] values) { + for (boolean value : values) + if (value) return true; + return false; + } + + /** Returns the number of values this will iterate over - i.e the product if the iterating dimension sizes */ + public int size() { + return size; + } + + private void next() { + int currentDimension = indexes.length - 1; + while ( ! iteratingDimensions[currentDimension] || + indexes[currentDimension] + 1 == dimensionSizes[currentDimension]) { + if ( iteratingDimensions[currentDimension]) + indexes[currentDimension--] = 0; // carry over + else // leave this dimension as-is + currentDimension--; } + indexes[currentDimension]++; + } + + /** Returns the address of the current position of these indexes */ + private TensorAddress toAddress() { + // TODO: We may avoid the array copy by issuing a one-time-use address? + return new TensorAddress(indexes); + } + + private int[] indexesCopy() { + return Arrays.copyOf(indexes, indexes.length); + } + + /** Returns a copy of the indexes of this which must not be modified */ + private int[] indexesForReading() { return indexes; } + + @Override + public String toString() { + return "indexes " + Arrays.toString(indexes); } } diff --git a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java index 260c48ace7f..6f655fd5860 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java @@ -73,8 +73,6 @@ public interface Tensor { if (type().dimensions().size() > 0) throw new IllegalStateException("This tensor is not dimensionless. Dimensions: " + type().dimensions().size()); if (size() == 0) return Double.NaN; - if (size() > 1) - throw new IllegalStateException("This tensor does not have a single value, it has " + size()); return valueIterator().next(); } @@ -213,9 +211,7 @@ public interface Tensor { /** Returns true if the two given tensors are mathematically equivalent, that is whether both have the same content */ static boolean equals(Tensor a, Tensor b) { - if (a == b) return true; - if ( ! a.cells().equals(b.cells())) return false; - return true; + return a == b || a.cells().equals(b.cells()); } // ----------------- Factories @@ -250,9 +246,8 @@ public interface Tensor { } interface Builder { - + /** Creates a suitable builder for the given type */ - // TODO: Create version of this which takes size info and use it when possible static Builder of(TensorType type) { boolean containsIndexed = type.dimensions().stream().anyMatch(d -> d.isIndexed()); boolean containsMapped = type.dimensions().stream().anyMatch( d -> ! d.isIndexed()); @@ -263,7 +258,19 @@ public interface Tensor { else // indexed or empty return IndexedTensor.Builder.of(type); } - + + /** Creates a suitable builder for the given type */ + static Builder of(TensorType type, int[] dimensionSizes) { + boolean containsIndexed = type.dimensions().stream().anyMatch(d -> d.isIndexed()); + boolean containsMapped = type.dimensions().stream().anyMatch( d -> ! d.isIndexed()); + if (containsIndexed && containsMapped) + throw new IllegalArgumentException("Combining indexed and mapped dimensions is not supported yet"); + if (containsMapped) + return MappedTensor.Builder.of(type); + else // indexed or empty + return IndexedTensor.Builder.of(type, dimensionSizes); + } + /** Returns the type this is building */ TensorType type(); diff --git a/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java b/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java index 0c726efc047..e829f4c909b 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/TensorType.java @@ -53,6 +53,9 @@ public class TensorType { return TensorTypeParser.fromSpec(specString); } + /** Returns true if all dimensions of this are indexed */ + public boolean isIndexed() { return dimensions().stream().allMatch(d -> d.isIndexed()); } + private static final boolean supportsMixedTypes = false; /** @@ -176,7 +179,7 @@ public class TensorType { // both are indexed bound IndexedBoundDimension thisIb = (IndexedBoundDimension)this; IndexedBoundDimension otherIb = (IndexedBoundDimension)other.get(); - return thisIb.size().get() > otherIb.size().get() ? thisIb : otherIb; + return thisIb.size().get() < otherIb.size().get() ? thisIb : otherIb; } @Override diff --git a/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java b/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java index 19b4ad39af3..df4ae4ec534 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java @@ -2,18 +2,20 @@ package com.yahoo.tensor.functions; import com.google.common.annotations.Beta; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableMap; import com.yahoo.tensor.IndexedTensor; -import com.yahoo.tensor.MappedTensor; import com.yahoo.tensor.Tensor; import com.yahoo.tensor.TensorAddress; import com.yahoo.tensor.TensorType; import com.yahoo.tensor.evaluation.EvaluationContext; +import java.util.Arrays; +import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Objects; +import java.util.Optional; +import java.util.Set; import java.util.function.DoubleBinaryOperator; /** @@ -69,7 +71,7 @@ public class Join extends PrimitiveTensorFunction { TensorType joinedType = a.type().combineWith(b.type()); // Choose join algorithm - if (a.type().equals(b.type()) && a.type().dimensions().size() == 1 && a.type().dimensions().get(0).isIndexed()) + if (hasSingleIndexedDimension(a) && hasSingleIndexedDimension(b) && a.type().dimensions().get(0).name().equals(b.type().dimensions().get(0).name())) return indexedVectorJoin((IndexedTensor)a, (IndexedTensor)b, joinedType); else if (joinedType.dimensions().size() == a.type().dimensions().size() && joinedType.dimensions().size() == b.type().dimensions().size()) return singleSpaceJoin(a, b, joinedType); @@ -81,8 +83,12 @@ public class Join extends PrimitiveTensorFunction { return generalJoin(a, b, joinedType); } + private boolean hasSingleIndexedDimension(Tensor tensor) { + return tensor.type().dimensions().size() == 1 && tensor.type().dimensions().get(0).isIndexed(); + } + private Tensor indexedVectorJoin(IndexedTensor a, IndexedTensor b, TensorType type) { - int joinedLength = Math.min(a.length(0), b.length(0)); + int joinedLength = Math.min(a.size(0), b.size(0)); Iterator<Double> aIterator = a.valueIterator(); Iterator<Double> bIterator = b.valueIterator(); IndexedTensor.Builder builder = IndexedTensor.Builder.of(type, new int[] { joinedLength}); @@ -105,6 +111,42 @@ public class Join extends PrimitiveTensorFunction { /** Join a tensor into a superspace */ private Tensor subspaceJoin(Tensor subspace, Tensor superspace, TensorType joinedType, boolean reversedArgumentOrder) { + if (subspace.type().isIndexed() && superspace.type().isIndexed()) + return indexedSubspaceJoin((IndexedTensor) subspace, (IndexedTensor) superspace, joinedType, reversedArgumentOrder); + else + return generalSubspaceJoin(subspace, superspace, joinedType, reversedArgumentOrder); + } + + private Tensor indexedSubspaceJoin(IndexedTensor subspace, IndexedTensor superspace, TensorType joinedType, boolean reversedArgumentOrder) { + if (subspace.size() == 0 || superspace.size() == 0) // special case empty here to avoid doing it when finding sizes + return Tensor.Builder.of(joinedType, new int[joinedType.dimensions().size()]).build(); + + // Find size of joined tensor + int[] joinedSizes = new int[joinedType.dimensions().size()]; + for (int i = 0; i < joinedSizes.length; i++) { + Optional<Integer> subspaceIndex = subspace.type().indexOfDimension(joinedType.dimensions().get(i).name()); + if (subspaceIndex.isPresent()) + joinedSizes[i] = Math.min(superspace.size(i), subspace.size(subspaceIndex.get())); + else + joinedSizes[i] = superspace.size(i); + } + + Tensor.Builder builder = Tensor.Builder.of(joinedType, joinedSizes); + + // Find dimensions which are only in the supertype + Set<String> superDimensionNames = new HashSet<>(superspace.type().dimensionNames()); + superDimensionNames.removeAll(subspace.type().dimensionNames()); + + for (Iterator<IndexedTensor.SubspaceIterator> i = superspace.subspaceIterator(superDimensionNames, joinedSizes); i.hasNext(); ) { + IndexedTensor.SubspaceIterator subspaceInSuper = i.next(); + joinSubspaces(subspace.valueIterator(), subspace.size(), + subspaceInSuper, subspaceInSuper.size(), + reversedArgumentOrder, builder); + } + return builder.build(); + } + + private Tensor generalSubspaceJoin(Tensor subspace, Tensor superspace, TensorType joinedType, boolean reversedArgumentOrder) { int[] subspaceIndexes = subspaceIndexes(superspace.type(), subspace.type()); Tensor.Builder builder = Tensor.Builder.of(joinedType); for (Iterator<Map.Entry<TensorAddress, Double>> i = superspace.cellIterator(); i.hasNext(); ) { @@ -112,13 +154,26 @@ public class Join extends PrimitiveTensorFunction { TensorAddress subaddress = mapAddressToSubspace(supercell.getKey(), subspaceIndexes); double subspaceValue = subspace.get(subaddress); if ( ! Double.isNaN(subspaceValue)) - builder.cell(supercell.getKey(), + builder.cell(supercell.getKey(), reversedArgumentOrder ? combinator.applyAsDouble(supercell.getValue(), subspaceValue) : combinator.applyAsDouble(subspaceValue, supercell.getValue())); } return builder.build(); } - + + private void joinSubspaces(Iterator<Double> subspace, int subspaceSize, + Iterator<Map.Entry<TensorAddress, Double>> superspace, int superspaceSize, + boolean reversedArgumentOrder, Tensor.Builder builder) { + int joinedLength = Math.min(subspaceSize, superspaceSize); + for (int i = 0; i < joinedLength; i++) { + Double subvalue = subspace.next(); + Map.Entry<TensorAddress, Double> supercell = superspace.next(); + builder.cell(supercell.getKey(), + reversedArgumentOrder ? combinator.applyAsDouble(supercell.getValue(), subvalue) + : combinator.applyAsDouble(subvalue, supercell.getValue())); + } + } + /** Returns the indexes in the superspace type which should be retained to create the subspace type */ private int[] subspaceIndexes(TensorType supertype, TensorType subtype) { int[] subspaceIndexes = new int[subtype.dimensions().size()]; diff --git a/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java b/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java index 7595d18fb18..d18d628f12f 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Reduce.java @@ -2,9 +2,7 @@ package com.yahoo.tensor.functions; import com.google.common.annotations.Beta; import com.google.common.collect.ImmutableList; -import com.google.common.collect.ImmutableMap; import com.yahoo.tensor.IndexedTensor; -import com.yahoo.tensor.MappedTensor; import com.yahoo.tensor.Tensor; import com.yahoo.tensor.TensorAddress; import com.yahoo.tensor.TensorType; @@ -149,7 +147,7 @@ public class Reduce extends PrimitiveTensorFunction { private Tensor reduceIndexedVector(IndexedTensor argument) { ValueAggregator valueAggregator = ValueAggregator.ofType(aggregator); - for (int i = 0; i < argument.length(0); i++) + for (int i = 0; i < argument.size(0); i++) valueAggregator.aggregate(argument.get(i)); return Tensor.Builder.of(TensorType.empty).cell((valueAggregator.aggregatedValue())).build(); } 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); |