dense simple expand function

7 files changed, 322 insertions, 0 deletions

diff --git a/eval/CMakeLists.txt b/eval/CMakeLists.txt
index eb09156445d..3a9aabc83ba 100644
--- a/eval/CMakeLists.txt
+++ b/eval/CMakeLists.txt
@@ -41,6 +41,7 @@ vespa_define_module(
     src/tests/tensor/dense_pow_as_map_optimizer
     src/tests/tensor/dense_remove_dimension_optimizer
     src/tests/tensor/dense_replace_type_function
+    src/tests/tensor/dense_simple_expand_function
     src/tests/tensor/dense_simple_join_function
     src/tests/tensor/dense_simple_map_function
     src/tests/tensor/dense_single_reduce_function
diff --git a/eval/src/tests/tensor/dense_simple_expand_function/CMakeLists.txt b/eval/src/tests/tensor/dense_simple_expand_function/CMakeLists.txt
new file mode 100644
index 00000000000..4e7409a6139
--- /dev/null
+++ b/eval/src/tests/tensor/dense_simple_expand_function/CMakeLists.txt
@@ -0,0 +1,9 @@
+# Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+vespa_add_executable(eval_dense_simple_expand_function_test_app TEST
+    SOURCES
+    dense_simple_expand_function_test.cpp
+    DEPENDS
+    vespaeval
+    gtest
+)
+vespa_add_test(NAME eval_dense_simple_expand_function_test_app COMMAND eval_dense_simple_expand_function_test_app)
diff --git a/eval/src/tests/tensor/dense_simple_expand_function/dense_simple_expand_function_test.cpp b/eval/src/tests/tensor/dense_simple_expand_function/dense_simple_expand_function_test.cpp
new file mode 100644
index 00000000000..4b870bc0153
--- /dev/null
+++ b/eval/src/tests/tensor/dense_simple_expand_function/dense_simple_expand_function_test.cpp
@@ -0,0 +1,130 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#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_simple_expand_function.h>
+#include <vespa/eval/eval/test/eval_fixture.h>
+#include <vespa/eval/eval/test/tensor_model.hpp>
+#include <vespa/vespalib/gtest/gtest.h>
+
+using namespace vespalib;
+using namespace vespalib::eval;
+using namespace vespalib::eval::test;
+using namespace vespalib::eval::tensor_function;
+using namespace vespalib::tensor;
+
+using Inner = DenseSimpleExpandFunction::Inner;
+
+const TensorEngine &prod_engine = DefaultTensorEngine::ref();
+
+EvalFixture::ParamRepo make_params() {
+    return EvalFixture::ParamRepo()
+        .add("a", spec(1.5))
+        .add("sparse", spec({x({"a"})}, N()))
+        .add("mixed", spec({y({"a"}),z(5)}, N()))
+        .add_vector("a", 5)
+        .add_vector("b", 3)
+        .add_cube("A", 1, "a", 5, "c", 1)
+        .add_cube("B", 1, "b", 3, "c", 1)
+        .add_matrix("a", 5, "c", 3)
+        .add_matrix("x", 3, "y", 2)
+        .add_cube("a", 1, "b", 1, "c", 1)
+        .add_cube("x", 1, "y", 1, "z", 1);
+}
+
+EvalFixture::ParamRepo param_repo = make_params();
+
+void verify_optimized(const vespalib::string &expr, Inner inner) {
+    EvalFixture slow_fixture(prod_engine, expr, param_repo, false);
+    EvalFixture fixture(prod_engine, expr, param_repo, true, true);
+    EXPECT_EQ(fixture.result(), EvalFixture::ref(expr, param_repo));
+    EXPECT_EQ(fixture.result(), slow_fixture.result());
+    auto info = fixture.find_all<DenseSimpleExpandFunction>();
+    ASSERT_EQ(info.size(), 1u);
+    EXPECT_TRUE(info[0]->result_is_mutable());
+    EXPECT_EQ(info[0]->inner(), inner);
+    ASSERT_EQ(fixture.num_params(), 2);
+    EXPECT_TRUE(!(fixture.get_param(0) == fixture.result()));
+    EXPECT_TRUE(!(fixture.get_param(1) == fixture.result()));
+}
+
+void verify_not_optimized(const vespalib::string &expr) {
+    EvalFixture slow_fixture(prod_engine, expr, param_repo, false);
+    EvalFixture fixture(prod_engine, expr, param_repo, true);
+    EXPECT_EQ(fixture.result(), EvalFixture::ref(expr, param_repo));
+    EXPECT_EQ(fixture.result(), slow_fixture.result());
+    auto info = fixture.find_all<DenseSimpleExpandFunction>();
+    EXPECT_TRUE(info.empty());
+}
+
+TEST(ExpandTest, simple_expand_is_optimized) {
+    verify_optimized("join(a5,b3,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(b3,a5,f(x,y)(x*y))", Inner::LHS);
+}
+
+TEST(ExpandTest, multiple_dimensions_are_supported) {
+    verify_optimized("join(a5,x3y2,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(x3y2,a5,f(x,y)(x*y))", Inner::LHS);
+    verify_optimized("join(a5c3,x3y2,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(x3y2,a5c3,f(x,y)(x*y))", Inner::LHS);
+}
+
+TEST(ExpandTest, trivial_dimensions_are_ignored) {
+    verify_optimized("join(A1a5c1,B1b3c1,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(B1b3c1,A1a5c1,f(x,y)(x*y))", Inner::LHS);
+}
+
+TEST(ExpandTest, simple_expand_handles_asymmetric_operations_correctly) {
+    verify_optimized("join(a5,b3,f(x,y)(x-y))", Inner::RHS);
+    verify_optimized("join(b3,a5,f(x,y)(x-y))", Inner::LHS);
+    verify_optimized("join(a5,b3,f(x,y)(x/y))", Inner::RHS);
+    verify_optimized("join(b3,a5,f(x,y)(x/y))", Inner::LHS);
+}
+
+TEST(ExpandTest, simple_expand_can_have_various_cell_types) {
+    verify_optimized("join(a5,b3f,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(a5f,b3,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(a5f,b3f,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(b3,a5f,f(x,y)(x*y))", Inner::LHS);
+    verify_optimized("join(b3f,a5,f(x,y)(x*y))", Inner::LHS);
+    verify_optimized("join(b3f,a5f,f(x,y)(x*y))", Inner::LHS);
+}
+
+TEST(ExpandTest, simple_expand_is_never_inplace) {
+    verify_optimized("join(@a5,@b3,f(x,y)(x*y))", Inner::RHS);
+    verify_optimized("join(@b3,@a5,f(x,y)(x*y))", Inner::LHS);
+}
+
+TEST(ExpandTest, interleaved_dimensions_are_not_optimized) {
+    verify_not_optimized("join(a5c3,b3,f(x,y)(x*y))");
+    verify_not_optimized("join(b3,a5c3,f(x,y)(x*y))");
+}
+
+TEST(ExpandTest, matching_dimensions_are_not_expanding) {
+    verify_not_optimized("join(a5c3,a5,f(x,y)(x*y))");
+    verify_not_optimized("join(a5,a5c3,f(x,y)(x*y))");
+}
+
+TEST(ExpandTest, scalar_is_not_expanding) {
+    verify_not_optimized("join(a5,a,f(x,y)(x*y))");
+}
+
+TEST(ExpandTest, unit_tensor_is_not_expanding) {
+    verify_not_optimized("join(a5,x1y1z1,f(x,y)(x+y))");
+    verify_not_optimized("join(x1y1z1,a5,f(x,y)(x+y))");
+    verify_not_optimized("join(a1b1c1,x1y1z1,f(x,y)(x+y))");
+}
+
+TEST(ExpandTest, sparse_expand_is_not_optimized) {
+    verify_not_optimized("join(a5,sparse,f(x,y)(x*y))");
+    verify_not_optimized("join(sparse,a5,f(x,y)(x*y))");
+}
+
+TEST(ExpandTest, mixed_expand_is_not_optimized) {
+    verify_not_optimized("join(a5,mixed,f(x,y)(x*y))");
+    verify_not_optimized("join(mixed,a5,f(x,y)(x*y))");
+}
+
+GTEST_MAIN_RUN_ALL_TESTS()
diff --git a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
index cb933c74754..ca14e40e4d0 100644
--- a/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
+++ b/eval/src/vespa/eval/tensor/default_tensor_engine.cpp
@@ -18,6 +18,7 @@
 #include "dense/dense_remove_dimension_optimizer.h"
 #include "dense/dense_lambda_peek_optimizer.h"
 #include "dense/dense_lambda_function.h"
+#include "dense/dense_simple_expand_function.h"
 #include "dense/dense_simple_join_function.h"
 #include "dense/dense_number_join_function.h"
 #include "dense/dense_pow_as_map_optimizer.h"
@@ -288,6 +289,7 @@ DefaultTensorEngine::optimize(const TensorFunction &expr, Stash &stash) const
         }
         while (!nodes.empty()) {
             const Child &child = nodes.back().get();
+            child.set(DenseSimpleExpandFunction::optimize(child.get(), stash));
             child.set(DenseAddDimensionOptimizer::optimize(child.get(), stash));
             child.set(DenseRemoveDimensionOptimizer::optimize(child.get(), stash));
             child.set(VectorFromDoublesFunction::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 c33d6f5cbcf..c4b8138148c 100644
--- a/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
+++ b/eval/src/vespa/eval/tensor/dense/CMakeLists.txt
@@ -15,6 +15,7 @@ vespa_add_library(eval_tensor_dense OBJECT
     dense_pow_as_map_optimizer.cpp
     dense_remove_dimension_optimizer.cpp
     dense_replace_type_function.cpp
+    dense_simple_expand_function.cpp
     dense_simple_join_function.cpp
     dense_simple_map_function.cpp
     dense_single_reduce_function.cpp
diff --git a/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.cpp b/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.cpp
new file mode 100644
index 00000000000..d45e0d936a9
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.cpp
@@ -0,0 +1,141 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+#include "dense_simple_expand_function.h"
+#include "dense_tensor_view.h"
+#include <vespa/vespalib/objects/objectvisitor.h>
+#include <vespa/eval/eval/value.h>
+#include <vespa/eval/eval/operation.h>
+#include <vespa/eval/eval/inline_operation.h>
+#include <vespa/vespalib/util/typify.h>
+#include <optional>
+#include <algorithm>
+
+namespace vespalib::tensor {
+
+using vespalib::ArrayRef;
+
+using eval::Value;
+using eval::ValueType;
+using eval::TensorFunction;
+using eval::TensorEngine;
+using eval::TypifyCellType;
+using eval::as;
+
+using namespace eval::operation;
+using namespace eval::tensor_function;
+
+using Inner = DenseSimpleExpandFunction::Inner;
+
+using op_function = eval::InterpretedFunction::op_function;
+using Instruction = eval::InterpretedFunction::Instruction;
+using State = eval::InterpretedFunction::State;
+
+namespace {
+
+struct ExpandParams {
+    const ValueType &result_type;
+    size_t result_size;
+    join_fun_t function;
+    ExpandParams(const ValueType &result_type_in, size_t result_size_in, join_fun_t function_in)
+        : result_type(result_type_in), result_size(result_size_in), function(function_in) {}
+};
+
+template <typename LCT, typename RCT, typename Fun, bool rhs_inner>
+void my_simple_expand_op(State &state, uint64_t param) {
+    using ICT = typename std::conditional<rhs_inner,RCT,LCT>::type;
+    using OCT = typename std::conditional<rhs_inner,LCT,RCT>::type;
+    using DCT = typename eval::UnifyCellTypes<ICT,OCT>::type;
+    using OP = typename std::conditional<rhs_inner,SwapArgs2<Fun>,Fun>::type;
+    const ExpandParams &params = *(ExpandParams*)param;
+    OP my_op(params.function);
+    auto inner_cells = DenseTensorView::typify_cells<ICT>(state.peek(rhs_inner ? 0 : 1));
+    auto outer_cells = DenseTensorView::typify_cells<OCT>(state.peek(rhs_inner ? 1 : 0));
+    auto dst_cells = state.stash.create_array<DCT>(params.result_size);
+    DCT *dst = dst_cells.begin();
+    for (OCT outer_cell: outer_cells) {
+        apply_op2_vec_num(dst, inner_cells.begin(), outer_cell, inner_cells.size(), my_op);
+        dst += inner_cells.size();
+    }
+    state.pop_pop_push(state.stash.create<DenseTensorView>(params.result_type, TypedCells(dst_cells)));
+}
+
+//-----------------------------------------------------------------------------
+
+struct MyGetFun {
+    template <typename R1, typename R2, typename R3, typename R4> static auto invoke() {
+        return my_simple_expand_op<R1, R2, R3, R4::value>;
+    }
+};
+
+using MyTypify = TypifyValue<TypifyCellType,TypifyOp2,TypifyBool>;
+
+//-----------------------------------------------------------------------------
+
+std::vector<ValueType::Dimension> strip_trivial(const std::vector<ValueType::Dimension> &dim_list) {
+    std::vector<ValueType::Dimension> result;
+    std::copy_if(dim_list.begin(), dim_list.end(), std::back_inserter(result),
+                 [](const auto &dim){ return (dim.size != 1); });
+    return result;
+}
+
+std::optional<Inner> detect_simple_expand(const TensorFunction &lhs, const TensorFunction &rhs) {
+    std::vector<ValueType::Dimension> a = strip_trivial(lhs.result_type().dimensions());
+    std::vector<ValueType::Dimension> b = strip_trivial(rhs.result_type().dimensions());
+    if (a.empty() || b.empty()) {
+        return std::nullopt;
+    } else if (a.back().name < b.front().name) {
+        return Inner::RHS;
+    } else if (b.back().name < a.front().name) {
+        return Inner::LHS;
+    } else {
+        return std::nullopt;
+    }
+}
+
+} // namespace vespalib::tensor::<unnamed>
+
+//-----------------------------------------------------------------------------
+
+DenseSimpleExpandFunction::DenseSimpleExpandFunction(const ValueType &result_type,
+                                                     const TensorFunction &lhs,
+                                                     const TensorFunction &rhs,
+                                                     join_fun_t function_in,
+                                                     Inner inner_in)
+    : Join(result_type, lhs, rhs, function_in),
+      _inner(inner_in)
+{
+}
+
+DenseSimpleExpandFunction::~DenseSimpleExpandFunction() = default;
+
+Instruction
+DenseSimpleExpandFunction::compile_self(const TensorEngine &, Stash &stash) const
+{
+    size_t result_size = result_type().dense_subspace_size();
+    const ExpandParams &params = stash.create<ExpandParams>(result_type(), result_size, function());
+    auto op = typify_invoke<4,MyTypify,MyGetFun>(lhs().result_type().cell_type(),
+                                                 rhs().result_type().cell_type(),
+                                                 function(), (_inner == Inner::RHS));
+    static_assert(sizeof(uint64_t) == sizeof(&params));
+    return Instruction(op, (uint64_t)(&params));
+}
+
+const TensorFunction &
+DenseSimpleExpandFunction::optimize(const TensorFunction &expr, Stash &stash)
+{
+    if (auto join = as<Join>(expr)) {
+        const TensorFunction &lhs = join->lhs();
+        const TensorFunction &rhs = join->rhs();
+        if (lhs.result_type().is_dense() && rhs.result_type().is_dense()) {
+            if (std::optional<Inner> inner = detect_simple_expand(lhs, rhs)) {
+                assert(expr.result_type().dense_subspace_size() ==
+                       (lhs.result_type().dense_subspace_size() *
+                        rhs.result_type().dense_subspace_size()));
+                return stash.create<DenseSimpleExpandFunction>(join->result_type(), lhs, rhs, join->function(), inner.value());
+            }
+        }
+    }
+    return expr;
+}
+
+} // namespace vespalib::tensor
diff --git a/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.h b/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.h
new file mode 100644
index 00000000000..b4b303901a7
--- /dev/null
+++ b/eval/src/vespa/eval/tensor/dense/dense_simple_expand_function.h
@@ -0,0 +1,38 @@
+// Copyright Verizon Media. 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 simple expanding join operations on dense
+ * tensors. An expanding operation is a join between tensors resulting
+ * in a larger tensor where the input tensors have no matching
+ * dimensions (trivial dimensions are ignored). A simple expanding
+ * operation is an expanding operation where all the dimensions of one
+ * input is nested inside all the dimensions from the other input
+ * within the result (trivial dimensions are again ignored).
+ **/
+class DenseSimpleExpandFunction : public eval::tensor_function::Join
+{
+    using Super = eval::tensor_function::Join;
+public:
+    enum class Inner : uint8_t { LHS, RHS };
+    using join_fun_t = ::vespalib::eval::tensor_function::join_fun_t;
+private:
+    Inner _inner;
+public:
+    DenseSimpleExpandFunction(const eval::ValueType &result_type,
+                              const TensorFunction &lhs,
+                              const TensorFunction &rhs,
+                              join_fun_t function_in,
+                              Inner inner_in);
+    ~DenseSimpleExpandFunction() override;
+    Inner inner() const { return _inner; }
+    eval::InterpretedFunction::Instruction compile_self(const eval::TensorEngine &engine, Stash &stash) const override;
+    static const eval::TensorFunction &optimize(const eval::TensorFunction &expr, Stash &stash);
+};
+
+} // namespace vespalib::tensor