added dense 'add dimension' optimizer

8 files changed, 206 insertions, 0 deletions

diff --git a/eval/CMakeLists.txt b/eval/CMakeLists.txt
index f1f559a129d..3db05c09613 100644
--- a/eval/CMakeLists.txt
+++ b/eval/CMakeLists.txt
@@ -25,6 +25,7 @@ vespa_define_module(
     src/tests/eval/value_cache
     src/tests/eval/value_type
     src/tests/gp/ponder_nov2017
+    src/tests/tensor/dense_add_dimension_optimizer
     src/tests/tensor/dense_dot_product_function
     src/tests/tensor/dense_fast_rename_optimizer
     src/tests/tensor/dense_inplace_join_function
diff --git a/eval/src/tests/tensor/dense_add_dimension_optimizer/CMakeLists.txt b/eval/src/tests/tensor/dense_add_dimension_optimizer/CMakeLists.txt
new file mode 100644
index 00000000000..1bc9f93b1a2
--- /dev/null
+++ b/eval/src/tests/tensor/dense_add_dimension_optimizer/CMakeLists.txt
@@ -0,0 +1,8 @@
+# Copyright 2018 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(eval_dense_add_dimension_optimizer_test_app TEST
+    SOURCES
+    dense_add_dimension_optimizer_test.cpp
+    DEPENDS
+    vespaeval
+)
+vespa_add_test(NAME eval_dense_add_dimension_optimizer_test_app COMMAND eval_dense_add_dimension_optimizer_test_app)
diff --git a/eval/src/tests/tensor/dense_add_dimension_optimizer/dense_add_dimension_optimizer_test.cpp b/eval/src/tests/tensor/dense_add_dimension_optimizer/dense_add_dimension_optimizer_test.cpp
new file mode 100644
index 00000000000..ce321b7c3c3
--- /dev/null
+++ b/eval/src/tests/tensor/dense_add_dimension_optimizer/dense_add_dimension_optimizer_test.cpp
@@ -0,0 +1,107 @@
+// Copyright 2018 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include <vespa/vespalib/testkit/test_kit.h>
+#include <vespa/eval/eval/tensor_function.h>
+#include <vespa/eval/eval/simple_tensor.h>
+#include <vespa/eval/eval/simple_tensor_engine.h>
+#include <vespa/eval/tensor/default_tensor_engine.h>
+#include <vespa/eval/tensor/dense/dense_replace_type_function.h>
+#include <vespa/eval/tensor/dense/dense_fast_rename_optimizer.h>
+#include <vespa/eval/tensor/dense/dense_tensor.h>
+#include <vespa/eval/eval/test/tensor_model.hpp>
+#include <vespa/eval/eval/test/eval_fixture.h>
+
+#include <vespa/vespalib/util/stringfmt.h>
+#include <vespa/vespalib/util/stash.h>
+
+using namespace vespalib;
+using namespace vespalib::eval;
+using namespace vespalib::eval::test;
+using namespace vespalib::tensor;
+using namespace vespalib::eval::tensor_function;
+
+const TensorEngine &prod_engine = DefaultTensorEngine::ref();
+
+EvalFixture::ParamRepo make_params() {
+    return EvalFixture::ParamRepo()
+        .add("x5", spec({x(5)}, N()))
+        .add("x5y1", spec({x(5),y(1)}, N()))
+        .add("y1z1", spec({y(1),z(1)}, N()))
+        .add("x5_u", spec({x(5)}, N()), "tensor(x[])")
+        .add("x_m", spec({x({"a"})}, N()));
+}
+EvalFixture::ParamRepo param_repo = make_params();
+
+void verify_optimized(const vespalib::string &expr) {
+    EvalFixture fixture(prod_engine, expr, param_repo, true);
+    EXPECT_EQUAL(fixture.result(), EvalFixture::ref(expr, param_repo));
+    auto info = fixture.find_all<DenseReplaceTypeFunction>();
+    EXPECT_EQUAL(info.size(), 1u);
+}
+
+void verify_not_optimized(const vespalib::string &expr) {
+    EvalFixture fixture(prod_engine, expr, param_repo, true);
+    EXPECT_EQUAL(fixture.result(), EvalFixture::ref(expr, param_repo));
+    auto info = fixture.find_all<DenseReplaceTypeFunction>();
+    EXPECT_TRUE(info.empty());
+}
+
+TEST("require that dimension addition can be optimized") {
+    TEST_DO(verify_optimized("join(x5,tensor(y[1])(1),f(a,b)(a*b))"));
+    TEST_DO(verify_optimized("join(tensor(y[1])(1),x5,f(a,b)(a*b))"));
+    TEST_DO(verify_optimized("x5*tensor(y[1])(1)"));
+    TEST_DO(verify_optimized("tensor(y[1])(1)*x5"));
+    TEST_DO(verify_optimized("x5y1*tensor(z[1])(1)"));
+    TEST_DO(verify_optimized("tensor(z[1])(1)*x5y1"));
+}
+
+TEST("require that multi-dimension addition can be optimized") {
+    TEST_DO(verify_optimized("x5*tensor(a[1],b[1],c[1])(1)"));
+}
+
+TEST("require that dimension addition can be chained (and compacted)") {
+    TEST_DO(verify_optimized("tensor(z[1])(1)*x5*tensor(y[1])(1)"));
+}
+
+TEST("require that constant dimension addition is optimized") {
+    TEST_DO(verify_optimized("tensor(x[1])(1)*tensor(y[1])(1)"));
+    TEST_DO(verify_optimized("tensor(x[1])(1.1)*tensor(y[1])(1)"));
+    TEST_DO(verify_optimized("tensor(x[1])(1)*tensor(y[1])(1.1)"));
+    TEST_DO(verify_optimized("tensor(x[2])(1)*tensor(y[1])(1)"));
+    TEST_DO(verify_optimized("tensor(x[1])(1)*tensor(y[2])(1)"));
+}
+
+TEST("require that non-canonical dimension addition is not optimized") {
+    TEST_DO(verify_not_optimized("x5+tensor(y[1])(0)"));
+    TEST_DO(verify_not_optimized("tensor(y[1])(0)+x5"));
+    TEST_DO(verify_not_optimized("x5-tensor(y[1])(0)"));
+    TEST_DO(verify_not_optimized("x5/tensor(y[1])(1)"));
+    TEST_DO(verify_not_optimized("tensor(y[1])(1)/x5"));
+}
+
+TEST("require that dimension addition with overlapping dimensions is not optimized") {
+    TEST_DO(verify_not_optimized("x5*tensor(x[1],y[1])(1)"));
+    TEST_DO(verify_not_optimized("tensor(x[1],y[1])(1)*x5"));
+    TEST_DO(verify_not_optimized("x5y1*tensor(y[1],z[1])(1)"));
+    TEST_DO(verify_not_optimized("tensor(y[1],z[1])(1)*x5y1"));
+}
+
+TEST("require that dimension addition with inappropriate dimensions is not optimized") {
+    TEST_DO(verify_not_optimized("x5_u*tensor(y[1])(1)"));
+    TEST_DO(verify_not_optimized("tensor(y[1])(1)*x5_u"));
+    TEST_DO(verify_not_optimized("x_m*tensor(y[1])(1)"));
+    TEST_DO(verify_not_optimized("tensor(y[1])(1)*x_m"));
+}
+
+TEST("require that dimension addition optimization requires unit constant tensor") {
+    TEST_DO(verify_not_optimized("x5*tensor(y[1])(0.9)"));
+    TEST_DO(verify_not_optimized("tensor(y[1])(1.1)*x5"));
+    TEST_DO(verify_not_optimized("x5*tensor(y[1],z[2])(1)"));
+    TEST_DO(verify_not_optimized("tensor(y[1],z[2])(1)*x5"));
+    TEST_DO(verify_not_optimized("x5*y1z1"));
+    TEST_DO(verify_not_optimized("y1z1*x5"));
+    TEST_DO(verify_not_optimized("tensor(x[1])(1.1)*tensor(y[1])(1.1)"));
+    TEST_DO(verify_not_optimized("tensor(x[2])(1)*tensor(y[2])(1)"));
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/eval/src/vespa/eval/eval/tensor_function.h b/eval/src/vespa/eval/eval/tensor_function.h
index a1d733e482b..628943e51b2 100644
--- a/eval/src/vespa/eval/eval/tensor_function.h
+++ b/eval/src/vespa/eval/eval/tensor_function.h
@@ -172,6 +172,7 @@ private:
     const Value &_value;
 public:
     ConstValue(const Value &value_in) : Leaf(value_in.type()), _value(value_in) {}
+    const Value &value() const { return _value; }
     bool result_is_mutable() const override { return false; }
     InterpretedFunction::Instruction compile_self(Stash &stash) const final override;
     void visit_self(vespalib::ObjectVisitor &visitor) const override;
diff --git a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
index 7f49fbc4acd..20296ac5032 100644
--- a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
+++ b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
@@ -10,6 +10,7 @@
 #include "dense/dense_dot_product_function.h"
 #include "dense/dense_xw_product_function.h"
 #include "dense/dense_fast_rename_optimizer.h"
+#include "dense/dense_add_dimension_optimizer.h"
 #include "dense/dense_remove_dimension_optimizer.h"
 #include "dense/dense_inplace_join_function.h"
 #include "dense/dense_inplace_map_function.h"
@@ -230,6 +231,7 @@ DefaultTensorEngine::optimize(const TensorFunction &expr, Stash &stash) const
         child.set(DenseDotProductFunction::optimize(child.get(), stash));
         child.set(DenseXWProductFunction::optimize(child.get(), stash));
         child.set(DenseFastRenameOptimizer::optimize(child.get(), stash));
+        child.set(DenseAddDimensionOptimizer::optimize(child.get(), stash));
         child.set(DenseRemoveDimensionOptimizer::optimize(child.get(), stash));
         child.set(DenseInplaceMapFunction::optimize(child.get(), stash));
         child.set(DenseInplaceJoinFunction::optimize(child.get(), stash));
diff --git a/eval/src/vespa/eval/tensor/dense/CMakeLists.txt b/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
index 49675158ad7..2cca7f9b6d0 100644
--- a/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
+++ b/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
@@ -1,6 +1,7 @@
 # Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
 vespa_add_library(eval_tensor_dense OBJECT
     SOURCES
+    dense_add_dimension_optimizer.cpp
     dense_dot_product_function.cpp
     dense_fast_rename_optimizer.cpp
     dense_inplace_join_function.cpp
diff --git a/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.cpp b/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.cpp
new file mode 100644
index 00000000000..9baaa596d9f
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.cpp
@@ -0,0 +1,69 @@
+// Copyright 2018 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "dense_add_dimension_optimizer.h"
+#include "dense_replace_type_function.h"
+#include <vespa/eval/eval/value_type.h>
+#include <vespa/eval/eval/operation.h>
+#include <vespa/eval/eval/value.h>
+
+namespace vespalib::tensor {
+
+using eval::ValueType;
+using eval::TensorFunction;
+using eval::as;
+using namespace eval::tensor_function;
+using namespace eval::operation;
+
+namespace {
+
+bool is_concrete_dense_tensor(const ValueType &type) {
+    return (type.is_dense() && !type.is_abstract());
+}
+
+bool not_overlapping(const ValueType &a, const ValueType &b) {
+    size_t npos = ValueType::Dimension::npos;
+    for (const auto &dim: b.dimensions()) {
+        if (a.dimension_index(dim.name) != npos) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool is_unit_constant(const TensorFunction &node) {
+    if (auto const_value = as<ConstValue>(node)) {
+        for (const auto &dim: node.result_type().dimensions()) {
+            if (dim.size != 1) {
+                return false;
+            }
+        }
+        return (const_value->value().as_double() == 1.0);
+    }
+    return false;
+}
+
+} // namespace vespalib::tensor::<unnamed>
+
+const TensorFunction &
+DenseAddDimensionOptimizer::optimize(const eval::TensorFunction &expr, Stash &stash)
+{
+    if (auto join = as<Join>(expr)) {
+        const TensorFunction &lhs = join->lhs();
+        const TensorFunction &rhs = join->rhs();
+        if ((join->function() == Mul::f) &&
+            is_concrete_dense_tensor(lhs.result_type()) &&
+            is_concrete_dense_tensor(rhs.result_type()) &&
+            not_overlapping(lhs.result_type(), rhs.result_type()))
+        {
+            if (is_unit_constant(lhs)) {
+                return DenseReplaceTypeFunction::create_compact(expr.result_type(), rhs, stash);
+            }
+            if (is_unit_constant(rhs)) {
+                return DenseReplaceTypeFunction::create_compact(expr.result_type(), lhs, stash);
+            }
+        }
+    }
+    return expr;
+}
+
+} // namespace vespalib::tensor
diff --git a/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.h b/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.h
new file mode 100644
index 00000000000..4b5cf296292
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_add_dimension_optimizer.h
@@ -0,0 +1,17 @@
+// Copyright 2018 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#pragma once
+
+#include <vespa/eval/eval/tensor_function.h>
+
+namespace vespalib::tensor {
+
+/**
+ * Tensor function optimizer for efficient adding of dimensions with
+ * size 1 for dense tensors.
+ **/
+struct DenseAddDimensionOptimizer {
+    static const eval::TensorFunction &optimize(const eval::TensorFunction &expr, Stash &stash);
+};
+
+} // namespace vespalib::tensor