diff options
author | HÃ¥vard Pettersen <3535158+havardpe@users.noreply.github.com> | 2020-06-17 09:50:25 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-06-17 09:50:25 +0200 |
commit | d3b332d3d9772b4cdff30ad68c87d5a525c119eb (patch) | |
tree | 2514803cb6ed8673133c75b0a670fc26c1139c00 /eval | |
parent | 06912de51de4413cb6e6d2685d8ed4ca1117a9ed (diff) | |
parent | ccaf5050c9d9edb3535e5aa69171180e1d95287a (diff) |
Merge pull request #13604 from vespa-engine/havardpe/simple-expand-function
dense simple expand function
Diffstat (limited to 'eval')
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 ¶ms = *(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 ¶ms = 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(¶ms)); + return Instruction(op, (uint64_t)(¶ms)); +} + +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 |