added optimizer for fast non-transposing dense tensor renaming

7 files changed, 197 insertions, 4 deletions

diff --git a/eval/CMakeLists.txt b/eval/CMakeLists.txt
index 3e0c0a12a4f..38abfec3c8c 100644
--- a/eval/CMakeLists.txt
+++ b/eval/CMakeLists.txt
@@ -25,6 +25,7 @@ vespa_define_module(
     src/tests/eval/value_type
     src/tests/gp/ponder_nov2017
     src/tests/tensor/dense_dot_product_function
+    src/tests/tensor/dense_fast_rename_function
     src/tests/tensor/dense_tensor_address_combiner
     src/tests/tensor/dense_tensor_builder
     src/tests/tensor/dense_xw_product_function
diff --git a/eval/src/tests/tensor/dense_fast_rename_function/CMakeLists.txt b/eval/src/tests/tensor/dense_fast_rename_function/CMakeLists.txt
new file mode 100644
index 00000000000..a5c3b223ce5
--- /dev/null
+++ b/eval/src/tests/tensor/dense_fast_rename_function/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_fast_rename_function_test_app TEST
+    SOURCES
+    dense_fast_rename_function_test.cpp
+    DEPENDS
+    vespaeval
+)
+vespa_add_test(NAME eval_dense_fast_rename_function_test_app COMMAND eval_dense_fast_rename_function_test_app)
diff --git a/eval/src/tests/tensor/dense_fast_rename_function/dense_fast_rename_function_test.cpp b/eval/src/tests/tensor/dense_fast_rename_function/dense_fast_rename_function_test.cpp
new file mode 100644
index 00000000000..fab16f1e276
--- /dev/null
+++ b/eval/src/tests/tensor/dense_fast_rename_function/dense_fast_rename_function_test.cpp
@@ -0,0 +1,74 @@
+// 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_fast_rename_function.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("x5_u", spec({x(5)}, N()), "tensor(x[])")
+        .add("x_m", spec({x({"a", "b", "c"})}, N()))
+        .add("x5y3", spec({x(5),y(3)}, 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<DenseFastRenameFunction>();
+    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<DenseFastRenameFunction>();
+    EXPECT_TRUE(info.empty());
+}
+
+TEST("require that non-transposing dense renames are optimized") {
+    TEST_DO(verify_optimized("rename(x5,x,y)"));
+    TEST_DO(verify_optimized("rename(x5,x,a)"));
+    TEST_DO(verify_optimized("rename(x5y3,y,z)"));
+    TEST_DO(verify_optimized("rename(x5y3,x,a)"));
+    TEST_DO(verify_optimized("rename(x5y3,(x,y),(a,b))"));
+    TEST_DO(verify_optimized("rename(x5y3,(x,y),(z,zz))"));
+    TEST_DO(verify_optimized("rename(x5y3,(x,y),(y,z))"));
+    TEST_DO(verify_optimized("rename(x5y3,(y,x),(b,a))"));
+}
+
+TEST("require that transposing dense renames are not optimized") {
+    TEST_DO(verify_not_optimized("rename(x5y3,x,z)"));
+    TEST_DO(verify_not_optimized("rename(x5y3,y,a)"));
+    TEST_DO(verify_not_optimized("rename(x5y3,(x,y),(y,x))"));
+    TEST_DO(verify_not_optimized("rename(x5y3,(x,y),(b,a))"));
+    TEST_DO(verify_not_optimized("rename(x5y3,(y,x),(a,b))"));
+}
+
+TEST("require that abstract dense renames are not optimized") {
+    TEST_DO(verify_not_optimized("rename(x5_u,x,y)"));
+}
+
+TEST("require that non-dense renames are not optimized") {
+    TEST_DO(verify_not_optimized("rename(x_m,x,y)"));
+}
+
+TEST_MAIN() { TEST_RUN_ALL(); }
diff --git a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
index 5f8be58105a..7b4a502dd4d 100644
--- a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
+++ b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
@@ -9,6 +9,7 @@
 #include "dense/dense_tensor_builder.h"
 #include "dense/dense_dot_product_function.h"
 #include "dense/dense_xw_product_function.h"
+#include "dense/dense_fast_rename_function.h"
 #include "dense/vector_from_doubles_function.h"
 #include <vespa/eval/eval/value.h>
 #include <vespa/eval/eval/tensor_spec.h>
@@ -221,6 +222,7 @@ DefaultTensorEngine::optimize(const TensorFunction &expr, Stash &stash) const
         child.set(VectorFromDoublesFunction::optimize(child.get(), stash));
         child.set(DenseDotProductFunction::optimize(child.get(), stash));
         child.set(DenseXWProductFunction::optimize(child.get(), stash));
+        child.set(DenseFastRenameFunction::optimize(child.get(), stash));
         nodes.pop_back();
     }
     return root.get();
diff --git a/eval/src/vespa/eval/tensor/dense/CMakeLists.txt b/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
index 23cab0c5f79..73315b7a120 100644
--- a/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
+++ b/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
@@ -1,15 +1,16 @@
 # 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
-    direct_dense_tensor_builder.cpp
     dense_dot_product_function.cpp
-    dense_xw_product_function.cpp
+    dense_fast_rename_function.cpp
     dense_tensor.cpp
     dense_tensor_address_combiner.cpp
     dense_tensor_builder.cpp
     dense_tensor_cells_iterator.cpp
-    dense_tensor_view.cpp
     dense_tensor_reduce.cpp
-    vector_from_doubles_function.cpp
+    dense_tensor_view.cpp
+    dense_xw_product_function.cpp
+    direct_dense_tensor_builder.cpp
     mutable_dense_tensor_view.cpp
+    vector_from_doubles_function.cpp
 )
diff --git a/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.cpp b/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.cpp
new file mode 100644
index 00000000000..dda95d5a657
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.cpp
@@ -0,0 +1,84 @@
+// Copyright 2018 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "dense_fast_rename_function.h"
+#include "dense_tensor.h"
+#include "dense_tensor_view.h"
+#include <vespa/eval/eval/value.h>
+#include <vespa/eval/tensor/tensor.h>
+
+namespace vespalib::tensor {
+
+using CellsRef = DenseTensorView::CellsRef;
+using eval::Value;
+using eval::ValueType;
+using eval::TensorFunction;
+using eval::as;
+using namespace eval::tensor_function;
+
+namespace {
+
+CellsRef getCellsRef(const eval::Value &value) {
+    const DenseTensorView &denseTensor = static_cast<const DenseTensorView &>(value);
+    return denseTensor.cellsRef();
+}
+
+void my_fast_rename_op(eval::InterpretedFunction::State &state, uint64_t param) {
+    const ValueType *type = (const ValueType *)(param);
+    CellsRef cells = getCellsRef(state.peek(0));
+    state.pop_push(state.stash.create<DenseTensorView>(*type, cells));
+}
+
+bool is_concrete_dense_stable_rename(const ValueType &from_type, const ValueType &to_type,
+                                     const std::vector<vespalib::string> &from,
+                                     const std::vector<vespalib::string> &to)
+{
+    if (!from_type.is_dense() || from_type.is_abstract() ||
+        !to_type.is_dense() || to_type.is_abstract() ||
+        (from.size() != to.size()))
+    {
+        return false;
+    }
+    size_t npos = ValueType::Dimension::npos;
+    for (size_t i = 0; i < from.size(); ++i) {
+        size_t old_idx = from_type.dimension_index(from[i]);
+        size_t new_idx = to_type.dimension_index(to[i]);
+        if ((old_idx != new_idx) || (old_idx == npos)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+} // namespace vespalib::tensor::<unnamed>
+
+
+DenseFastRenameFunction::DenseFastRenameFunction(const eval::ValueType &result_type,
+                                                 const eval::TensorFunction &child)
+    : eval::tensor_function::Op1(result_type, child)
+{
+}
+
+DenseFastRenameFunction::~DenseFastRenameFunction()
+{
+}
+
+eval::InterpretedFunction::Instruction
+DenseFastRenameFunction::compile_self(Stash &) const
+{
+    return eval::InterpretedFunction::Instruction(my_fast_rename_op, (uint64_t)&(result_type()));
+}
+
+const TensorFunction &
+DenseFastRenameFunction::optimize(const eval::TensorFunction &expr, Stash &stash)
+{
+    if (auto rename = as<Rename>(expr)) {
+        const ValueType &from_type = rename->child().result_type();
+        const ValueType &to_type = expr.result_type();
+        if (is_concrete_dense_stable_rename(from_type, to_type, rename->from(), rename->to())) {
+            return stash.create<DenseFastRenameFunction>(to_type, rename->child());
+        }
+    }
+    return expr;
+}
+
+} // namespace vespalib::tensor
diff --git a/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.h b/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.h
new file mode 100644
index 00000000000..e7de8e95ff0
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.h
@@ -0,0 +1,23 @@
+// 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 for efficient non-transposing rename of a dense
+ * tensor.
+ **/
+class DenseFastRenameFunction : public eval::tensor_function::Op1
+{
+public:
+    DenseFastRenameFunction(const eval::ValueType &result_type,
+                            const eval::TensorFunction &child);
+    ~DenseFastRenameFunction();
+    eval::InterpretedFunction::Instruction compile_self(Stash &stash) const override;
+    static const eval::TensorFunction &optimize(const eval::TensorFunction &expr, Stash &stash);
+};
+
+} // namespace vespalib::tensor