make a specific inline version of sparse no-overlap join

2 files changed, 148 insertions, 8 deletions

diff --git a/eval/src/vespa/eval/eval/fast_value.hpp b/eval/src/vespa/eval/eval/fast_value.hpp
index f02d02489b8..2f0c9b6f6a8 100644
--- a/eval/src/vespa/eval/eval/fast_value.hpp
+++ b/eval/src/vespa/eval/eval/fast_value.hpp
@@ -140,6 +140,7 @@ struct IterateView : public Value::Index::View {
 
 //-----------------------------------------------------------------------------
 
+using JoinAddrSource = instruction::SparseJoinPlan::Source;
 // This is the class instructions will look for when optimizing sparse
 // operations by calling inline functions directly.
 
@@ -155,9 +156,15 @@ struct FastValueIndex final : Value::Index {
 
     template <typename LCT, typename RCT, typename OCT, typename Fun>
         static const Value &sparse_only_merge(const ValueType &res_type, const Fun &fun,
-                                         const FastValueIndex &lhs, const FastValueIndex &rhs,
-                                         ConstArrayRef<LCT> lhs_cells, ConstArrayRef<RCT> rhs_cells,
-                                         Stash &stash) __attribute((noinline));
+                const FastValueIndex &lhs, const FastValueIndex &rhs,
+                ConstArrayRef<LCT> lhs_cells, ConstArrayRef<RCT> rhs_cells,
+                Stash &stash) __attribute((noinline));
+
+    template <typename LCT, typename RCT, typename OCT, typename Fun>
+        static const Value &sparse_no_overlap_join(const ValueType &res_type, const Fun &fun,
+                const FastValueIndex &lhs, const FastValueIndex &rhs,
+                const std::vector<JoinAddrSource> &addr_sources,
+                ConstArrayRef<LCT> lhs_cells, ConstArrayRef<RCT> rhs_cells, Stash &stash);
 
     size_t size() const override { return map.size(); }
     std::unique_ptr<View> create_view(const std::vector<size_t> &dims) const override;
@@ -360,4 +367,49 @@ FastValueIndex::sparse_only_merge(const ValueType &res_type, const Fun &fun,
 
 //-----------------------------------------------------------------------------
 
+template <typename LCT, typename RCT, typename OCT, typename Fun>
+const Value &
+FastValueIndex::sparse_no_overlap_join(const ValueType &res_type, const Fun &fun,
+                                       const FastValueIndex &lhs, const FastValueIndex &rhs,
+                                       const std::vector<JoinAddrSource> &addr_sources,
+                                       ConstArrayRef<LCT> lhs_cells, ConstArrayRef<RCT> rhs_cells, Stash &stash)
+{
+    using HashedLabelRef = std::reference_wrapper<const FastSparseMap::HashedLabel>;
+    auto &result = stash.create<FastValue<OCT>>(res_type, res_type.count_mapped_dimensions(), 1, lhs.map.size()*rhs.map.size());
+    std::vector<HashedLabelRef> output_addr;
+    lhs.map.each_map_entry([&](auto lhs_subspace, auto)
+        {
+            auto l_addr = lhs.map.make_addr(lhs_subspace);
+            rhs.map.each_map_entry([&](auto rhs_subspace, auto)
+                {
+                    auto r_addr = rhs.map.make_addr(rhs_subspace);
+                    output_addr.clear();
+                    size_t l_idx = 0;
+                    size_t r_idx = 0;
+                    for (JoinAddrSource source : addr_sources) {
+                        switch (source) {
+                        case JoinAddrSource::LHS:
+                            output_addr.push_back(l_addr[l_idx++]);
+                            break;
+                        case JoinAddrSource::RHS:
+                            output_addr.push_back(r_addr[r_idx++]);
+                            break;
+                        default:
+                            abort();
+                        }
+                    }
+                    assert(l_idx == l_addr.size());
+                    assert(r_idx == r_addr.size());
+
+                    ConstArrayRef<HashedLabelRef> output_addr_ref(output_addr);
+                    auto idx = result.my_index.map.add_mapping(output_addr_ref);
+                    if (__builtin_expect((idx == result.my_cells.size), true)) {
+                        auto cell_value = fun(lhs_cells[lhs_subspace], rhs_cells[rhs_subspace]);
+                        result.my_cells.push_back_fast(cell_value);
+                    }
+                });
+        });
+    return result;
+}
+
 }
diff --git a/eval/src/vespa/eval/instruction/generic_join.cpp b/eval/src/vespa/eval/instruction/generic_join.cpp
index fb5f170c68e..eabe1c362e2 100644
--- a/eval/src/vespa/eval/instruction/generic_join.cpp
+++ b/eval/src/vespa/eval/instruction/generic_join.cpp
@@ -69,6 +69,90 @@ void my_mixed_join_op(State &state, uint64_t param_in) {
 
 //-----------------------------------------------------------------------------
 
+/** possible generic utility */
+template<typename T, typename U>
+const T *
+recognize_by_type_index(const U & object)
+{
+    if (std::type_index(typeid(object)) == std::type_index(typeid(T))) {
+        return static_cast<const T *>(&object);
+    }
+    return nullptr;
+}
+
+template<typename T, size_t N>
+class RecognizedValues
+{
+private:
+    std::array<const T *, N> _pointers;
+public:
+    RecognizedValues(std::array<const T *, N> && pointers)
+        : _pointers(std::move(pointers))
+    {}
+    bool all_converted() const {
+        for (auto p : _pointers) {
+            if (p == nullptr) return false;            
+        }
+        return true;
+    }
+    operator bool() const { return all_converted(); }
+    template<size_t idx> const T& get() const {
+        static_assert(idx < N);
+        return *_pointers[idx];
+    }
+};
+
+template<typename T, typename... Args>
+RecognizedValues<T, sizeof...(Args)>
+detect_type(const Args &... args)
+{
+    return RecognizedValues<T, sizeof...(Args)>({(recognize_by_type_index<T>(args))...});
+}
+
+//-----------------------------------------------------------------------------
+
+template <typename LCT, typename RCT, typename OCT, typename Fun>
+void my_sparse_no_overlap_join_op(State &state, uint64_t param_in) {
+    const auto &param = unwrap_param<JoinParam>(param_in);
+    const Value &lhs = state.peek(1);
+    const Value &rhs = state.peek(0);
+    auto lhs_cells = lhs.cells().typify<LCT>();
+    auto rhs_cells = rhs.cells().typify<RCT>();
+    const Value::Index &lhs_index = lhs.index();
+    const Value::Index &rhs_index = rhs.index();
+    if (auto indexes = detect_type<FastValueIndex>(lhs_index, rhs_index)) {
+        const auto &lhs_fast = indexes.get<0>();
+        const auto &rhs_fast = indexes.get<1>();
+        return state.pop_pop_push(
+                FastValueIndex::sparse_no_overlap_join<LCT,RCT,OCT,Fun>
+                        (param.res_type, Fun(param.function),
+                         lhs_fast, rhs_fast,
+                         param.sparse_plan.sources,
+                         lhs_cells, rhs_cells, state.stash));
+    }
+    Fun fun(param.function);
+    SparseJoinState sparse(param.sparse_plan, lhs.index(), rhs.index());
+    auto guess = lhs.index().size() * rhs.index().size();
+    assert(param.dense_plan.out_size == 1);
+    auto builder = param.factory.create_value_builder<OCT>(param.res_type, param.sparse_plan.sources.size(), 1, guess);
+    auto outer = sparse.first_index.create_view({});
+    assert(sparse.second_view_dims.empty());
+    auto inner = sparse.second_index.create_view({});
+    outer->lookup({});
+    while (outer->next_result(sparse.first_address, sparse.first_subspace)) {
+        inner->lookup({});
+        while (inner->next_result(sparse.second_only_address, sparse.second_subspace)) {
+            auto cell_value = fun(lhs_cells[sparse.lhs_subspace], rhs_cells[sparse.rhs_subspace]);
+            builder->add_subspace(sparse.full_address)[0] = cell_value;
+        }
+    }
+    auto &result = state.stash.create<std::unique_ptr<Value>>(builder->build(std::move(builder)));
+    const Value &result_ref = *(result.get());
+    state.pop_pop_push(result_ref);
+};
+
+//-----------------------------------------------------------------------------
+
 template <typename LCT, typename RCT, typename OCT, typename Fun>
 void my_sparse_full_overlap_join_op(State &state, uint64_t param_in) {
     const auto &param = unwrap_param<JoinParam>(param_in);
@@ -78,11 +162,9 @@ void my_sparse_full_overlap_join_op(State &state, uint64_t param_in) {
     auto rhs_cells = rhs.cells().typify<RCT>();
     const Value::Index &lhs_index = lhs.index();
     const Value::Index &rhs_index = rhs.index();
-    if ((std::type_index(typeid(lhs_index)) == std::type_index(typeid(FastValueIndex))) &&
-        (std::type_index(typeid(rhs_index)) == std::type_index(typeid(FastValueIndex))))
-    {
-        const FastValueIndex &lhs_fast = static_cast<const FastValueIndex&>(lhs_index);
-        const FastValueIndex &rhs_fast = static_cast<const FastValueIndex&>(rhs_index);
+    if (auto indexes = detect_type<FastValueIndex>(lhs_index, rhs_index)) {
+        const auto &lhs_fast = indexes.get<0>();
+        const auto &rhs_fast = indexes.get<1>();
         return (rhs_fast.map.size() < lhs_fast.map.size())
             ? state.pop_pop_push(FastValueIndex::sparse_full_overlap_join<RCT,LCT,OCT,SwapArgs2<Fun>>
                                  (param.res_type, SwapArgs2<Fun>(param.function), rhs_fast, lhs_fast, rhs_cells, lhs_cells, state.stash))
@@ -145,6 +227,12 @@ struct SelectGenericJoinOp {
         {
             return my_sparse_full_overlap_join_op<LCT,RCT,OCT,Fun>;
         }
+        if ((param.dense_plan.out_size == 1) &&
+            (param.sparse_plan.lhs_overlap.size() == 0) &&
+            (param.sparse_plan.rhs_overlap.size() == 0))
+        {
+            return my_sparse_no_overlap_join_op<LCT,RCT,OCT,Fun>;
+        }
         return my_mixed_join_op<LCT,RCT,OCT,Fun>;
     }
 };