From cbdd44218aa2333f625e61cf3445e6db885fa1dc Mon Sep 17 00:00:00 2001 From: Håvard Pettersen Date: Thu, 22 Feb 2018 13:54:31 +0000 Subject: added optimizer for fast non-transposing dense tensor renaming --- eval/CMakeLists.txt | 1 + .../dense_fast_rename_function/CMakeLists.txt | 8 +++ .../dense_fast_rename_function_test.cpp | 74 +++++++++++++++++++ .../vespa/eval/tensor/default_tensor_engine.cpp | 2 + eval/src/vespa/eval/tensor/dense/CMakeLists.txt | 9 +-- .../tensor/dense/dense_fast_rename_function.cpp | 84 ++++++++++++++++++++++ .../eval/tensor/dense/dense_fast_rename_function.h | 23 ++++++ 7 files changed, 197 insertions(+), 4 deletions(-) create mode 100644 eval/src/tests/tensor/dense_fast_rename_function/CMakeLists.txt create mode 100644 eval/src/tests/tensor/dense_fast_rename_function/dense_fast_rename_function_test.cpp create mode 100644 eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.cpp create mode 100644 eval/src/vespa/eval/tensor/dense/dense_fast_rename_function.h (limited to 'eval') 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 +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +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(); + 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(); + 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 #include @@ -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 +#include + +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(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(*type, cells)); +} + +bool is_concrete_dense_stable_rename(const ValueType &from_type, const ValueType &to_type, + const std::vector &from, + const std::vector &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:: + + +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(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(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 + +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 -- cgit v1.2.3