From 718b455587a6e093abfdbe5a45dc40221abc90eb Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Sun, 21 Jan 2024 19:18:55 +0100 Subject: - Add and use getAsDouble method returning a Double object. It behaves similar to Map.get(key). null indicates no value present. Then you avoid 2 lookups to first check if a value is present, and then to fetch that value. This does wonders when it is backed by a map and hashCode/equals are relatively expensive. --- vespajlib/abi-spec.json | 4 ++++ .../src/main/java/com/yahoo/tensor/IndexedTensor.java | 11 +++++++++++ vespajlib/src/main/java/com/yahoo/tensor/MappedTensor.java | 3 +++ vespajlib/src/main/java/com/yahoo/tensor/MixedTensor.java | 10 ++++++++++ vespajlib/src/main/java/com/yahoo/tensor/Tensor.java | 2 ++ .../src/main/java/com/yahoo/tensor/functions/Join.java | 14 ++++++++------ .../src/main/java/com/yahoo/tensor/functions/Merge.java | 5 +++-- 7 files changed, 41 insertions(+), 8 deletions(-) diff --git a/vespajlib/abi-spec.json b/vespajlib/abi-spec.json index 4a65b00a6a4..6eb0aaf340e 100644 --- a/vespajlib/abi-spec.json +++ b/vespajlib/abi-spec.json @@ -912,6 +912,7 @@ "public com.yahoo.tensor.DirectIndexedAddress directAddress()", "public varargs float getFloat(long[])", "public double get(com.yahoo.tensor.TensorAddress)", + "public java.lang.Double getAsDouble(com.yahoo.tensor.TensorAddress)", "public boolean has(com.yahoo.tensor.TensorAddress)", "public abstract double get(long)", "public abstract float getFloat(long)", @@ -968,6 +969,7 @@ "public int sizeAsInt()", "public double get(com.yahoo.tensor.TensorAddress)", "public boolean has(com.yahoo.tensor.TensorAddress)", + "public java.lang.Double getAsDouble(com.yahoo.tensor.TensorAddress)", "public java.util.Iterator cellIterator()", "public java.util.Iterator valueIterator()", "public java.util.Map cells()", @@ -1048,6 +1050,7 @@ "public com.yahoo.tensor.TensorType type()", "public long size()", "public double get(com.yahoo.tensor.TensorAddress)", + "public java.lang.Double getAsDouble(com.yahoo.tensor.TensorAddress)", "public boolean has(com.yahoo.tensor.TensorAddress)", "public java.util.Iterator cellIterator()", "public java.util.Iterator valueIterator()", @@ -1174,6 +1177,7 @@ "public int sizeAsInt()", "public abstract double get(com.yahoo.tensor.TensorAddress)", "public abstract boolean has(com.yahoo.tensor.TensorAddress)", + "public abstract java.lang.Double getAsDouble(com.yahoo.tensor.TensorAddress)", "public abstract java.util.Iterator cellIterator()", "public abstract java.util.Iterator valueIterator()", "public abstract java.util.Map cells()", diff --git a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java index 5d384e0329b..f26174d9576 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/IndexedTensor.java @@ -119,6 +119,17 @@ public abstract class IndexedTensor implements Tensor { } } + @Override + public Double getAsDouble(TensorAddress address) { + try { + long index = toValueIndex(address, dimensionSizes, type); + if (index < 0 || size() <= index) return null; + return get(index); + } catch (IllegalArgumentException e) { + return null; + } + } + @Override public boolean has(TensorAddress address) { try { diff --git a/vespajlib/src/main/java/com/yahoo/tensor/MappedTensor.java b/vespajlib/src/main/java/com/yahoo/tensor/MappedTensor.java index 5471ea65b97..3e0df5f2261 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/MappedTensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/MappedTensor.java @@ -40,6 +40,9 @@ public class MappedTensor implements Tensor { @Override public boolean has(TensorAddress address) { return cells.containsKey(address); } + @Override + public Double getAsDouble(TensorAddress address) { return cells.get(address); } + @Override public Iterator cellIterator() { return new CellIteratorAdaptor(cells.entrySet().iterator()); } diff --git a/vespajlib/src/main/java/com/yahoo/tensor/MixedTensor.java b/vespajlib/src/main/java/com/yahoo/tensor/MixedTensor.java index cf6e737bf27..aab4a4e1297 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/MixedTensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/MixedTensor.java @@ -82,6 +82,16 @@ public class MixedTensor implements Tensor { return block.cells[denseOffset]; } + @Override + public Double getAsDouble(TensorAddress address) { + var block = index.blockOf(address); + int denseOffset = index.denseOffsetOf(address); + if (block == null || denseOffset < 0 || denseOffset >= block.cells.length) { + return null; + } + return block.cells[denseOffset]; + } + @Override public boolean has(TensorAddress address) { var block = index.blockOf(address); diff --git a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java index cff17fdfd7c..d034ac551f8 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/Tensor.java @@ -90,6 +90,8 @@ public interface Tensor { /** Returns true if this cell exists */ boolean has(TensorAddress address); + /** null = no value present. More efficient that if (t.has(key)) t.get(key) */ + Double getAsDouble(TensorAddress address); /** * Returns the cell of this in some undefined order. 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 7a336233de0..712e5528fc6 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Join.java @@ -129,8 +129,9 @@ public class Join extends PrimitiveTensorFunction i = a.cellIterator(); i.hasNext(); ) { Map.Entry aCell = i.next(); var key = aCell.getKey(); - if (b.has(key)) { - builder.cell(key, combinator.applyAsDouble(aCell.getValue(), b.get(key))); + Double bVal = b.getAsDouble(key); + if (bVal != null) { + builder.cell(key, combinator.applyAsDouble(aCell.getValue(), bVal)); } } return builder.build(); @@ -206,11 +207,12 @@ public class Join extends PrimitiveTensorFunction i = superspace.cellIterator(); i.hasNext(); ) { Map.Entry supercell = i.next(); TensorAddress subaddress = mapAddressToSubspace(supercell.getKey(), subspaceIndexes); - if (subspace.has(subaddress)) { - double subspaceValue = subspace.get(subaddress); + Double subspaceValue = subspace.getAsDouble(subaddress); + if (subspaceValue != null) { builder.cell(supercell.getKey(), - reversedArgumentOrder ? combinator.applyAsDouble(supercell.getValue(), subspaceValue) - : combinator.applyAsDouble(subspaceValue, supercell.getValue())); + reversedArgumentOrder + ? combinator.applyAsDouble(supercell.getValue(), subspaceValue) + : combinator.applyAsDouble(subspaceValue, supercell.getValue())); } } return builder.build(); diff --git a/vespajlib/src/main/java/com/yahoo/tensor/functions/Merge.java b/vespajlib/src/main/java/com/yahoo/tensor/functions/Merge.java index 59394785382..ddad91dc060 100644 --- a/vespajlib/src/main/java/com/yahoo/tensor/functions/Merge.java +++ b/vespajlib/src/main/java/com/yahoo/tensor/functions/Merge.java @@ -121,10 +121,11 @@ public class Merge extends PrimitiveTensorFunction i = a.cellIterator(); i.hasNext(); ) { Map.Entry aCell = i.next(); var key = aCell.getKey(); - if (! b.has(key)) { + Double bVal = b.getAsDouble(key); + if (bVal == null) { builder.cell(key, aCell.getValue()); } else if (combinator != null) { - builder.cell(key, combinator.applyAsDouble(aCell.getValue(), b.get(key))); + builder.cell(key, combinator.applyAsDouble(aCell.getValue(), bVal)); } } } -- cgit v1.2.3 From 850acefbc85b8bfdf0d6a434e8659f0461cc44bd Mon Sep 17 00:00:00 2001 From: Henning Baldersheim Date: Sun, 21 Jan 2024 19:36:09 +0100 Subject: Reorder tests as the indexed tests varies a lot when they are run last. Reason not known. --- .../com/yahoo/tensor/TensorFunctionBenchmark.java | 56 ++++++++++++---------- 1 file changed, 31 insertions(+), 25 deletions(-) diff --git a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java index 5c4d5f1ffcf..37c0fb87be0 100644 --- a/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java +++ b/vespajlib/src/test/java/com/yahoo/tensor/TensorFunctionBenchmark.java @@ -107,45 +107,51 @@ public class TensorFunctionBenchmark { public static void main(String[] args) { double time = 0; - // ---------------- Mapped with extra space (sidesteps current special-case optimizations): - // 7.8 ms - time = new TensorFunctionBenchmark().benchmark(1000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, true); - System.out.printf("Mapped vectors, x space time per join: %1$8.3f ms\n", time); - // 7.7 ms - time = new TensorFunctionBenchmark().benchmark(1000, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, true); - System.out.printf("Mapped matrix, x space time per join: %1$8.3f ms\n", time); + // ---------------- Indexed unbound: + 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); + time = new TensorFunctionBenchmark().benchmark(50000, 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: + 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); + + time = new TensorFunctionBenchmark().benchmark(50000, 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); // ---------------- Mapped: - // 2.1 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); - // 7.0 ms + time = new TensorFunctionBenchmark().benchmark(1000, 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): - // 14.5 ms time = new TensorFunctionBenchmark().benchmark(500, vectors(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, true); System.out.printf("Indexed vectors, x space time per join: %1$8.3f ms\n", time); - // 8.9 ms time = new TensorFunctionBenchmark().benchmark(500, matrix(100, 300, TensorType.Dimension.Type.indexedUnbound), TensorType.Dimension.Type.indexedUnbound, true); System.out.printf("Indexed matrix, x space time per join: %1$8.3f ms\n", time); - // ---------------- Indexed unbound: - // 0.14 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); - // 0.44 ms - time = new TensorFunctionBenchmark().benchmark(50000, 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); + // ---------------- Mapped with extra space (sidesteps current special-case optimizations): + time = new TensorFunctionBenchmark().benchmark(1000, vectors(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, true); + System.out.printf("Mapped vectors, x space time per join: %1$8.3f ms\n", time); + time = new TensorFunctionBenchmark().benchmark(1000, matrix(100, 300, TensorType.Dimension.Type.mapped), TensorType.Dimension.Type.mapped, true); + System.out.printf("Mapped matrix, x space time per join: %1$8.3f ms\n", time); + + /** 2.4Ghz Intel Core i9, Macbook Pro 2019 + * Indexed unbound vectors, time per join: 0,067 ms + * Indexed unbound matrix, time per join: 0,107 ms + * Indexed bound vectors, time per join: 0,068 ms + * Indexed bound matrix, time per join: 0,105 ms + * Mapped vectors, time per join: 1,780 ms + * Mapped matrix, time per join: 5,339 ms + * Indexed vectors, x space time per join: 6,398 ms + * Indexed matrix, x space time per join: 3,220 ms + * Mapped vectors, x space time per join: 13,026 ms + * Mapped matrix, x space time per join: 28,259 ms + */ - // ---------------- Indexed bound: - // 0.32 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); - // 0.44 ms - time = new TensorFunctionBenchmark().benchmark(50000, 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); } } -- cgit v1.2.3