diff options
author | Håvard Pettersen <havardpe@oath.com> | 2018-03-20 13:19:27 +0000 |
---|---|---|
committer | Håvard Pettersen <havardpe@oath.com> | 2018-03-20 14:17:40 +0000 |
commit | b3e69c77f2254628da5e0e5b7f701b5fe1f72edf (patch) | |
tree | 689a2855f66a7b98aed3a2581d952b5b65fa40de /eval | |
parent | e31b9616921f9046a1fabbe9fca9cf3a5d535279 (diff) |
added dense 'add dimension' optimizer
Diffstat (limited to 'eval')
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 |