From 4b5f82781293c2b79d2002e854cbe4b4edfe8d62 Mon Sep 17 00:00:00 2001 From: James Stone Date: Fri, 27 Oct 2023 11:22:58 -0700 Subject: [PATCH 1/4] remove unnecessary callback use for ArrayWithFind::find_action() --- src/realm/array.cpp | 34 ++- src/realm/array.hpp | 2 + src/realm/array_integer.cpp | 2 +- src/realm/array_integer.hpp | 16 +- src/realm/array_integer_tpl.hpp | 41 ++-- src/realm/array_with_find.cpp | 14 +- src/realm/array_with_find.hpp | 290 ++++++++++--------------- src/realm/query_conditions_tpl.hpp | 39 +++- src/realm/query_engine.cpp | 14 +- src/realm/query_engine.hpp | 23 +- src/realm/query_state.hpp | 16 +- src/realm/table.cpp | 5 +- test/benchmark-common-tasks/main.cpp | 107 +++++++++ test/large_tests/test_column_large.cpp | 10 +- 14 files changed, 359 insertions(+), 254 deletions(-) diff --git a/src/realm/array.cpp b/src/realm/array.cpp index e3c981049fb..3455c8db0c2 100644 --- a/src/realm/array.cpp +++ b/src/realm/array.cpp @@ -1032,7 +1032,7 @@ MemRef Array::create(Type type, bool context_flag, WidthType width_type, size_t template bool Array::find_vtable(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { - return ArrayWithFind(*this).find_optimized(value, start, end, baseindex, state, nullptr); + return ArrayWithFind(*this).find_optimized(value, start, end, baseindex, state); } @@ -1285,6 +1285,12 @@ bool QueryStateCount::match(size_t, Mixed) noexcept return (m_limit > m_match_count); } +bool QueryStateCount::match(size_t) noexcept +{ + ++m_match_count; + return (m_limit > m_match_count); +} + bool QueryStateFindFirst::match(size_t index, Mixed) noexcept { m_match_count++; @@ -1292,6 +1298,13 @@ bool QueryStateFindFirst::match(size_t index, Mixed) noexcept return false; } +bool QueryStateFindFirst::match(size_t index) noexcept +{ + ++m_match_count; + m_state = index; + return false; +} + template <> bool QueryStateFindAll>::match(size_t index, Mixed) noexcept { @@ -1303,6 +1316,16 @@ bool QueryStateFindAll>::match(size_t index, Mixed) noexcept return (m_limit > m_match_count); } +template <> +bool QueryStateFindAll>::match(size_t index) noexcept +{ + ++m_match_count; + int64_t key_value = (m_key_values ? m_key_values->get(index) : index) + m_key_offset; + m_keys.push_back(ObjKey(key_value)); + + return (m_limit > m_match_count); +} + template <> bool QueryStateFindAll::match(size_t index, Mixed) noexcept { @@ -1311,3 +1334,12 @@ bool QueryStateFindAll::match(size_t index, Mixed) noexcept return (m_limit > m_match_count); } + +template <> +bool QueryStateFindAll::match(size_t index) noexcept +{ + ++m_match_count; + m_keys.add(index); + + return (m_limit > m_match_count); +} diff --git a/src/realm/array.hpp b/src/realm/array.hpp index 1b26e0960fd..a5ec21f6239 100644 --- a/src/realm/array.hpp +++ b/src/realm/array.hpp @@ -70,6 +70,7 @@ class QueryStateFindAll : public QueryStateBase { { } bool match(size_t index, Mixed) noexcept final; + bool match(size_t index) noexcept final; private: T& m_keys; @@ -83,6 +84,7 @@ class QueryStateFindFirst : public QueryStateBase { { } bool match(size_t index, Mixed) noexcept final; + bool match(size_t index) noexcept final; }; class Array : public Node, public ArrayParent { diff --git a/src/realm/array_integer.cpp b/src/realm/array_integer.cpp index 1cb4f24a4e1..bf459b8161d 100644 --- a/src/realm/array_integer.cpp +++ b/src/realm/array_integer.cpp @@ -169,7 +169,7 @@ void ArrayIntNull::find_all(IntegerColumn* result, value_type value, size_t col_ bool ArrayIntNull::find(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const { - return find_impl(cond, value, start, end, state, nullptr); + return find_impl(cond, value, start, end, state); } size_t ArrayIntNull::find_first(value_type value, size_t begin, size_t end) const diff --git a/src/realm/array_integer.hpp b/src/realm/array_integer.hpp index f683c64f097..bc2d4fca595 100644 --- a/src/realm/array_integer.hpp +++ b/src/realm/array_integer.hpp @@ -68,8 +68,8 @@ class ArrayInteger : public Array, public ArrayPayload { { return false; } - template - bool find(value_type value, size_t start, size_t end, QueryStateBase* state, Callback callback) const; + template + bool find(value_type value, size_t start, size_t end, QueryStateBase* state) const; }; class ArrayIntNull : public Array, public ArrayPayload { @@ -125,8 +125,8 @@ class ArrayIntNull : public Array, public ArrayPayload { bool find(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const; - template - bool find(value_type value, size_t start, size_t end, QueryStateBase* state, Callback callback) const; + template + bool find(value_type value, size_t start, size_t end, QueryStateBase* state) const; // Wrappers for backwards compatibility and for simple use without // setting up state initialization etc @@ -147,11 +147,9 @@ class ArrayIntNull : public Array, public ArrayPayload { void replace_nulls_with(int64_t new_null); bool can_use_as_null(int64_t value) const; - template - bool find_impl(int cond, value_type value, size_t start, size_t end, QueryStateBase* state, - Callback callback) const; - template - bool find_impl(value_type value, size_t start, size_t end, QueryStateBase* state, Callback callback) const; + bool find_impl(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const; + template + bool find_impl(value_type value, size_t start, size_t end, QueryStateBase* state) const; }; diff --git a/src/realm/array_integer_tpl.hpp b/src/realm/array_integer_tpl.hpp index 442bba93745..9d96584ab3c 100644 --- a/src/realm/array_integer_tpl.hpp +++ b/src/realm/array_integer_tpl.hpp @@ -24,37 +24,34 @@ namespace realm { -template -bool ArrayInteger::find(value_type value, size_t start, size_t end, QueryStateBase* state, Callback callback) const +template +bool ArrayInteger::find(value_type value, size_t start, size_t end, QueryStateBase* state) const { - return ArrayWithFind(*this).find(value, start, end, 0, state, callback); + return ArrayWithFind(*this).find(value, start, end, 0, state); } -template -inline bool ArrayIntNull::find_impl(int cond, value_type value, size_t start, size_t end, QueryStateBase* state, - Callback callback) const +inline bool ArrayIntNull::find_impl(int cond, value_type value, size_t start, size_t end, QueryStateBase* state) const { switch (cond) { case cond_Equal: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); case cond_NotEqual: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); case cond_Greater: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); case cond_Less: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); case cond_None: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); case cond_LeftNotNull: - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); } REALM_ASSERT_DEBUG(false); return false; } -template -bool ArrayIntNull::find_impl(value_type opt_value, size_t start, size_t end, QueryStateBase* state, - Callback callback) const +template +bool ArrayIntNull::find_impl(value_type opt_value, size_t start, size_t end, QueryStateBase* state) const { int64_t null_value = Array::get(0); bool find_null = !bool(opt_value); @@ -79,7 +76,7 @@ bool ArrayIntNull::find_impl(value_type opt_value, size_t start, size_t end, Que } // Fall back to plain Array find. - return ArrayWithFind(*this).find(value, start2, end2, baseindex2, state, callback); + return ArrayWithFind(*this).find(value, start2, end2, baseindex2, state); } else { cond c; @@ -95,8 +92,7 @@ bool ArrayIntNull::find_impl(value_type opt_value, size_t start, size_t end, Que int64_t v = Array::get(i); bool value_is_null = (v == null_value); if (c(v, value, value_is_null, find_null)) { - util::Optional v2 = value_is_null ? util::none : util::make_optional(v); - if (!ArrayWithFind(*this).find_action(i + baseindex2, v2, state, callback)) { + if (!state->match(i + baseindex2)) { return false; // tell caller to stop aggregating/search } } @@ -109,7 +105,7 @@ template size_t ArrayIntNull::find_first(value_type value, size_t start, size_t end) const { QueryStateFindFirst state; - find_impl(value, start, end, &state, nullptr); + find_impl(value, start, end, &state); if (state.match_count() > 0) return to_size_t(state.m_state); @@ -117,11 +113,10 @@ size_t ArrayIntNull::find_first(value_type value, size_t start, size_t end) cons return not_found; } -template -inline bool ArrayIntNull::find(value_type value, size_t start, size_t end, QueryStateBase* state, - Callback callback) const +template +inline bool ArrayIntNull::find(value_type value, size_t start, size_t end, QueryStateBase* state) const { - return find_impl(value, start, end, state, callback); + return find_impl(value, start, end, state); } } // namespace realm diff --git a/src/realm/array_with_find.cpp b/src/realm/array_with_find.cpp index 6ce2bc4d362..e33513ef28e 100644 --- a/src/realm/array_with_find.cpp +++ b/src/realm/array_with_find.cpp @@ -29,7 +29,7 @@ void ArrayWithFind::find_all(IntegerColumn* result, int64_t value, size_t col_of end = m_array.m_size; QueryStateFindAll state(*result); - REALM_TEMPEX2(find_optimized, Equal, m_array.m_width, (value, begin, end, col_offset, &state, nullptr)); + REALM_TEMPEX2(find_optimized, Equal, m_array.m_width, (value, begin, end, col_offset, &state)); return; } @@ -39,22 +39,22 @@ bool ArrayWithFind::find(int cond, int64_t value, size_t start, size_t end, size QueryStateBase* state) const { if (cond == cond_Equal) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } if (cond == cond_NotEqual) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } if (cond == cond_Greater) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } if (cond == cond_Less) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } if (cond == cond_None) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } else if (cond == cond_LeftNotNull) { - return find(value, start, end, baseindex, state, nullptr); + return find(value, start, end, baseindex, state); } REALM_ASSERT_DEBUG(false); return false; diff --git a/src/realm/array_with_find.hpp b/src/realm/array_with_find.hpp index ec811a7b977..5d7790378f5 100644 --- a/src/realm/array_with_find.hpp +++ b/src/realm/array_with_find.hpp @@ -18,21 +18,19 @@ /* Searching: The main finding function is: - template - void find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState *state, Callback callback) const + template + void find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState *state) const cond: One of Equal, NotEqual, Greater, etc. classes - Action: One of act_ReturnFirst, act_FindAll, act_Max, act_CallbackIdx, etc, constants - Callback: Optional function to call for each search result. Will be called if action == act_CallbackIdx + Action: One of act_ReturnFirst, act_FindAll, act_Max, etc, constants - find() will call find_action_pattern() or find_action() that again calls match() for each search result which - optionally calls callback(): + find() will call find_action_pattern() or QueryStateBase::match() for each search result - find() -> find_action() -------> bool match() -> bool callback() + find() -----------> bool QueryStateBase::match() | ^ +-> find_action_pattern()----+ - If callback() returns false, find() will exit, otherwise it will keep searching remaining items in array. + If match() returns false, find() will exit, otherwise it will keep searching remaining items in array. */ #ifndef REALM_ARRAY_WITH_FIND_HPP @@ -98,49 +96,41 @@ class ArrayWithFind { // Main finding function - used for find_first, find_all, sum, max, min, etc. bool find(int cond, int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; - template - bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; void find_all(IntegerColumn* result, int64_t value, size_t col_offset = 0, size_t begin = 0, size_t end = size_t(-1)) const; // Non-SSE find for the four functions Equal/NotEqual/Less/Greater - template - bool compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; // Non-SSE find for Equal/NotEqual - template - inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; // Non-SSE find for Less/Greater - template - bool compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; - template - bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; - template - bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; - template - bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; // SSE find for the four functions Equal/NotEqual/Less/Greater #ifdef REALM_COMPILER_SSE - template - bool find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, size_t baseindex, - Callback callback) const; + template + bool find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, size_t baseindex) const; - template + template REALM_FORCEINLINE bool find_sse_intern(__m128i* action_data, __m128i* data, size_t items, QueryStateBase* state, - size_t baseindex, Callback callback) const; + size_t baseindex) const; #endif @@ -161,28 +151,22 @@ class ArrayWithFind { size_t first_set_bit64(int64_t v) const; // Find value greater/less in 64-bit chunk - only works for positive values - template - bool find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBase* state, size_t baseindex, - Callback callback) const; + template + bool find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBase* state, size_t baseindex) const; // Find value greater/less in 64-bit chunk - no constraints - template - bool find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, size_t baseindex, Callback callback) const; + template + bool find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, size_t baseindex) const; // Optimized implementation for release mode - template - bool find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; - // Called for each search result - template - bool find_action(size_t index, util::Optional value, QueryStateBase* state, Callback callback) const; + template + bool find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; private: const Array& m_array; bool find_action_pattern(size_t index, uint64_t pattern, QueryStateBase* state) const; - template - bool find_all_will_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const; + template + bool find_all_will_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; }; //************************************************************************************* // Finding code * @@ -190,27 +174,7 @@ class ArrayWithFind { /* -find() (calls find_optimized()) may call find_action for each search result. - -'index' tells the row index of a single match and 'value' tells its value. Return false to make Array-finder break -its search or return true to let it continue until 'end' or 'limit'. -*/ -template -bool ArrayWithFind::find_action(size_t index, util::Optional, QueryStateBase*, Callback callback) const -{ - return callback(index); -} - -// This function is used when there is no callback. Here we will just perform the action implemented in 'state'. -template <> -inline bool ArrayWithFind::find_action(size_t index, util::Optional value, - QueryStateBase* state, std::nullptr_t) const -{ - return state->match(index, value); -} - -/* -find() (calls find_optimized()) may call find_action_pattern before calling find_action. +find() (calls find_optimized()) may call find_action_pattern before calling QueryStateBase->match(). 'indexpattern' contains a 64-bit chunk of elements, each of 'width' bits in size where each element indicates a match if its lower bit is set, otherwise it indicates a non-match. 'index' tells the database row index of the @@ -336,31 +300,25 @@ uint64_t ArrayWithFind::cascade(uint64_t a) const } } -template +template REALM_NOINLINE bool ArrayWithFind::find_all_will_match(size_t start2, size_t end, size_t baseindex, - QueryStateBase* state, Callback callback) const + QueryStateBase* state) const { - size_t end2; - - if constexpr (!std::is_same_v) - end2 = end; - else { - REALM_ASSERT_DEBUG(state->match_count() < state->limit()); - size_t process = state->limit() - state->match_count(); - end2 = end - start2 > process ? start2 + process : end; - } + REALM_ASSERT_DEBUG(state->match_count() < state->limit()); + size_t process = state->limit() - state->match_count(); + size_t end2 = end - start2 > process ? start2 + process : end; for (; start2 < end2; start2++) - if (!find_action(start2 + baseindex, m_array.get(start2), state, callback)) + if (!state->match(start2 + baseindex)) return false; return true; } // This is the main finding function for Array. Other finding functions are just wrappers around this one. -// Search for 'value' using condition cond (Equal, NotEqual, Less, etc) and call find_action() or -// find_action_pattern() for each match. Break and return if find_action() returns false or 'end' is reached. -template -bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const +// Search for 'value' using condition cond (Equal, NotEqual, Less, etc) and call QueryStateBase->match() or +// find_action_pattern() for each match. Break and return if QueryStateBase->match() returns false or 'end' is +// reached. +template +bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { REALM_ASSERT_DEBUG(start <= m_array.m_size && (end <= m_array.m_size || end == size_t(-1)) && start <= end); @@ -383,7 +341,7 @@ bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size // optimization if all items are guaranteed to match (such as cond == NotEqual && value == 100 && m_ubound == 15) if (c.will_match(value, lbound, ubound)) { - return find_all_will_match(start2, end, baseindex, state, callback); + return find_all_will_match(start2, end, baseindex, state); } // finder cannot handle this bitwidth @@ -402,41 +360,41 @@ bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size __m128i* const b = reinterpret_cast<__m128i*>(round_down(m_array.m_data + end * bitwidth / 8, sizeof(__m128i))); - if (!compare(value, start2, + if (!compare(value, start2, (reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth), - baseindex, state, callback)) + baseindex, state)) return false; // Search aligned area with SSE if (b > a) { if (sseavx<42>()) { - if (!find_sse( + if (!find_sse( value, a, b - a, state, - baseindex + ((reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth)), callback)) + baseindex + ((reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth)))) return false; } else if (sseavx<30>()) { - if (!find_sse( + if (!find_sse( value, a, b - a, state, - baseindex + ((reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth)), callback)) + baseindex + ((reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth)))) return false; } } // Search remainder with compare_equality() - if (!compare(value, + if (!compare(value, (reinterpret_cast(b) - m_array.m_data) * 8 / no0(bitwidth), end, - baseindex, state, callback)) + baseindex, state)) return false; return true; } else { - return compare(value, start2, end, baseindex, state, callback); + return compare(value, start2, end, baseindex, state); } #else - return compare(value, start2, end, baseindex, state, callback); + return compare(value, start2, end, baseindex, state); #endif } @@ -515,9 +473,8 @@ int64_t ArrayWithFind::find_gtlt_magic(int64_t v) const return magic; } -template -bool ArrayWithFind::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBase* state, size_t baseindex, - Callback callback) const +template +bool ArrayWithFind::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBase* state, size_t baseindex) const { // Tests if a a chunk of values contains values that are greater (if gt == true) or less (if gt == false) than v. // Fast, but limited to work when all values in the chunk are positive. @@ -532,11 +489,11 @@ bool ArrayWithFind::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBas size_t p = 0; while (m) { if (find_action_pattern(baseindex, m >> (no0(width) - 1), state)) - break; // consumed, so do not call find_action() + break; // consumed, so do not call QueryStateBase->match() size_t t = first_set_bit64(m) / no0(width); p += t; - if (!find_action(p + baseindex, (chunk >> (p * width)) & mask1, state, callback)) + if (!state->match(p + baseindex, Mixed{int64_t((chunk >> (p * width)) & mask1)})) return false; if ((t + 1) * width == 64) @@ -550,15 +507,15 @@ bool ArrayWithFind::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBas } // clang-format off -template -bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, size_t baseindex, Callback callback) const +template +bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, size_t baseindex) const { // Find items in 'chunk' that are greater (if gt == true) or smaller (if gt == false) than 'v'. Fixme, __forceinline can make it crash in vS2010 - find out why if constexpr (width == 1) { for (size_t i = 0; i < 64; ++i) { int64_t v2 = static_cast(chunk & 0x1); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -569,7 +526,7 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, for (size_t i = 0; i < 32; ++i) { int64_t v2 = static_cast(chunk & 0x3); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -580,7 +537,7 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, for (size_t i = 0; i < 16; ++i) { int64_t v2 = static_cast(chunk & 0xf); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -591,7 +548,7 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, for (size_t i = 0; i < 8; ++i) { int64_t v2 = static_cast(static_cast(chunk & 0xff)); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -602,7 +559,7 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, for (size_t i = 0; i < 4; ++i) { int64_t v2 = static_cast(static_cast(chunk & 0xffff)); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -613,7 +570,7 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, for (size_t i = 0; i < 2; ++i) { int64_t v2 = static_cast(static_cast(chunk & 0xffffffff)); if (gt ? v2 > v : v2 < v) { - if (!find_action(i + baseindex, v2, state, callback)) { + if (!state->match(i + baseindex, v2)) { return false; } } @@ -623,20 +580,19 @@ bool ArrayWithFind::find_gtlt(int64_t v, uint64_t chunk, QueryStateBase* state, else if constexpr (width == 64) { int64_t v2 = static_cast(chunk); if (gt ? v2 > v : v2 < v) { - return find_action(baseindex, v2, state, callback); + return state->match(baseindex, v2); } } static_cast(state); - static_cast(callback); return true; } // clang-format on /// Find items in this Array that are equal (eq == true) or different (eq = false) from 'value' -template +template inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, - QueryStateBase* state, Callback callback) const + QueryStateBase* state) const { REALM_ASSERT_DEBUG(start <= m_array.m_size && (end <= m_array.m_size || end == size_t(-1)) && start <= end); @@ -644,7 +600,7 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t ee = ee > end ? end : ee; for (; start < ee; ++start) if (eq ? (m_array.get(start) == value) : (m_array.get(start) != value)) { - if (!find_action(start + baseindex, m_array.get(start), state, callback)) + if (!state->match(start + baseindex)) return false; } @@ -678,8 +634,9 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t if (a >= 64 / no0(width)) break; - if (!find_action(a + start + baseindex, m_array.get(start + a), state, callback)) + if (!state->match(a + start + baseindex)) { return false; + } auto shift = (t + 1) * width; if (shift < 64) v2 >>= shift; @@ -700,8 +657,9 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t while (start < end) { if (eq ? m_array.get(start) == value : m_array.get(start) != value) { - if (!find_action(start + baseindex, m_array.get(start), state, callback)) + if (!state->match(start + baseindex)) { return false; + } } ++start; } @@ -712,20 +670,18 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t // There exists a couple of find() functions that take more or less template arguments. Always call the one that // takes as most as possible to get best performance. -template -bool ArrayWithFind::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const +template +bool ArrayWithFind::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { - REALM_TEMPEX3(return find_optimized, cond, m_array.m_width, Callback, - (value, start, end, baseindex, state, callback)); + REALM_TEMPEX2(return find_optimized, cond, m_array.m_width, + (value, start, end, baseindex, state)); } #ifdef REALM_COMPILER_SSE // 'items' is the number of 16-byte SSE chunks. Returns index of packed element relative to first integer of first // chunk -template -bool ArrayWithFind::find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, size_t baseindex, - Callback callback) const +template +bool ArrayWithFind::find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, size_t baseindex) const { __m128i search = {0}; @@ -742,15 +698,14 @@ bool ArrayWithFind::find_sse(int64_t value, __m128i* data, size_t items, QuerySt search = _mm_set_epi64x(value, value); } - return find_sse_intern(data, &search, items, state, baseindex, callback); + return find_sse_intern(data, &search, items, state, baseindex); } // Compares packed action_data with packed data (equal, less, etc) and performs aggregate action (max, min, sum, // find_all, etc) on value inside action_data for first match, if any -template +template REALM_FORCEINLINE bool ArrayWithFind::find_sse_intern(__m128i* action_data, __m128i* data, size_t items, - QueryStateBase* state, size_t baseindex, - Callback callback) const + QueryStateBase* state, size_t baseindex) const { size_t i = 0; __m128i compare_result = {0}; @@ -811,8 +766,7 @@ REALM_FORCEINLINE bool ArrayWithFind::find_sse_intern(__m128i* action_data, __m1 size_t idx = first_set_bit(resmask) * 8 / no0(width); s += idx; - if (!find_action(s + baseindex, m_array.get_universal(reinterpret_cast(action_data), s), - state, callback)) + if (!state->match(s + baseindex)) return false; resmask >>= (idx + 1) * no0(width) / 8; ++s; @@ -823,9 +777,9 @@ REALM_FORCEINLINE bool ArrayWithFind::find_sse_intern(__m128i* action_data, __m1 } #endif // REALM_COMPILER_SSE -template +template bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, - QueryStateBase* state, Callback callback) const + QueryStateBase* state) const { cond c; REALM_ASSERT_3(start, <=, end); @@ -838,7 +792,7 @@ bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end // We can compare first element without checking for out-of-range v = m_array.get(start); if (c(v, foreign->get(start))) { - if (!find_action(start + baseindex, v, state, callback)) + if (!state->match(start + baseindex, v)) return false; } @@ -847,17 +801,17 @@ bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end if (start + 3 < end) { v = m_array.get(start); if (c(v, foreign->get(start))) - if (!find_action(start + baseindex, v, state, callback)) + if (!state->match(start + baseindex, v)) return false; v = m_array.get(start + 1); if (c(v, foreign->get(start + 1))) - if (!find_action(start + 1 + baseindex, v, state, callback)) + if (!state->match(start + 1 + baseindex, v)) return false; v = m_array.get(start + 2); if (c(v, foreign->get(start + 2))) - if (!find_action(start + 2 + baseindex, v, state, callback)) + if (!state->match(start + 2 + baseindex, v)) return false; start += 3; @@ -867,26 +821,26 @@ bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end } bool r; - REALM_TEMPEX3(r = compare_leafs, cond, m_array.m_width, Callback, - (foreign, start, end, baseindex, state, callback)) + REALM_TEMPEX2(r = compare_leafs, cond, m_array.m_width, + (foreign, start, end, baseindex, state)) return r; } -template +template bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, - QueryStateBase* state, Callback callback) const + QueryStateBase* state) const { size_t fw = foreign->m_width; bool r; - REALM_TEMPEX4(r = compare_leafs_4, cond, width, Callback, fw, (foreign, start, end, baseindex, state, callback)) + REALM_TEMPEX3(r = compare_leafs_4, cond, width, fw, (foreign, start, end, baseindex, state)) return r; } -template +template bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, - QueryStateBase* state, Callback callback) const + QueryStateBase* state) const { cond c; char* foreign_m_data = foreign->m_data; @@ -894,7 +848,7 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e if (width == 0 && foreign_width == 0) { if (c(0, 0)) { while (start < end) { - if (!find_action(start + baseindex, 0, state, callback)) + if (!state->match(start + baseindex, 0)) return false; start++; } @@ -915,7 +869,7 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e int64_t v = m_array.get_universal(m_array.m_data, start); int64_t fv = m_array.get_universal(foreign_m_data, start); if (c(v, fv)) { - if (!find_action(start + baseindex, v, state, callback)) + if (!state->match(start + baseindex, v)) return false; } start++; @@ -932,7 +886,7 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e __m128i* b = reinterpret_cast<__m128i*>(foreign_m_data + start * width / 8); bool continue_search = - find_sse_intern(a, b, 1, state, baseindex + start, callback); + find_sse_intern(a, b, 1, state, baseindex + start); if (!continue_search) return false; @@ -948,7 +902,7 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e int64_t fv = m_array.get_universal(foreign_m_data, start); if (c(v, fv)) { - if (!find_action(start + baseindex, v, state, callback)) + if (!state->match(start + baseindex, v)) return false; } @@ -959,29 +913,27 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e } -template -bool ArrayWithFind::compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const +template +bool ArrayWithFind::compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { bool ret = false; if (std::is_same::value) - ret = compare_equality(value, start, end, baseindex, state, callback); + ret = compare_equality(value, start, end, baseindex, state); else if (std::is_same::value) - ret = compare_equality(value, start, end, baseindex, state, callback); + ret = compare_equality(value, start, end, baseindex, state); else if (std::is_same::value) - ret = compare_relation(value, start, end, baseindex, state, callback); + ret = compare_relation(value, start, end, baseindex, state); else if (std::is_same::value) - ret = compare_relation(value, start, end, baseindex, state, callback); + ret = compare_relation(value, start, end, baseindex, state); else REALM_ASSERT_DEBUG(false); return ret; } -template -bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state, - Callback callback) const +template +bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { REALM_ASSERT(start <= m_array.m_size && (end <= m_array.m_size || end == size_t(-1)) && start <= end); uint64_t mask = (bitwidth == 64 ? ~0ULL @@ -992,13 +944,14 @@ bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, si ee = ee > end ? end : ee; for (; start < ee; start++) { if (gt ? (m_array.get(start) > value) : (m_array.get(start) < value)) { - if (!find_action(start + baseindex, m_array.get(start), state, callback)) + if (!state->match(start + baseindex, m_array.get(start))) return false; } } if (start >= end) - return true; // none found, continue (return true) regardless what find_action() would have returned on match + return true; // none found, continue (return true) regardless what QueryStateBase->match() would have returned + // on match const int64_t* p = reinterpret_cast(m_array.m_data + (start * bitwidth / 8)); const int64_t* const e = reinterpret_cast(m_array.m_data + (end * bitwidth / 8)) - 1; @@ -1024,16 +977,14 @@ bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, si upper = upper & v; if (!upper) { - idx = find_gtlt_fast( + idx = find_gtlt_fast( v, magic, state, - (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex, - callback); + (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex); } else - idx = find_gtlt( + idx = find_gtlt( value, v, state, - (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex, - callback); + (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex); if (!idx) return false; @@ -1044,10 +995,9 @@ bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, si // 24 ms while (p < e) { int64_t v = *p; - if (!find_gtlt( + if (!find_gtlt( value, v, state, - (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex, - callback)) + (p - reinterpret_cast(m_array.m_data)) * 8 * 8 / no0(bitwidth) + baseindex)) return false; ++p; } @@ -1060,7 +1010,7 @@ bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, si // Test unaligned end and/or values of width > 16 manually while (start < end) { if (gt ? m_array.get(start) > value : m_array.get(start) < value) { - if (!find_action(start + baseindex, m_array.get(start), state, callback)) + if (!state->match(start + baseindex)) return false; } ++start; diff --git a/src/realm/query_conditions_tpl.hpp b/src/realm/query_conditions_tpl.hpp index a4d5eb0049b..dd348422c57 100644 --- a/src/realm/query_conditions_tpl.hpp +++ b/src/realm/query_conditions_tpl.hpp @@ -33,8 +33,27 @@ class QueryStateSum : public QueryStateBase { using Type = T; using ResultType = typename aggregate_operations::Sum::ResultType; using QueryStateBase::QueryStateBase; - bool match(size_t, Mixed value) noexcept final + bool match(size_t index, Mixed value) noexcept final + { + if (m_source_column) { + REALM_ASSERT_DEBUG(value.is_null()); + value = m_source_column->get_any(index); + } + else { + static_cast(m_source_column); + } + if (!value.is_null()) { + auto v = value.get(); + if (!m_state.accumulate(v)) + return true; // no match, continue searching + ++m_match_count; + } + return (m_limit > m_match_count); + } + bool match(size_t index) noexcept final { + REALM_ASSERT(m_source_column); + Mixed value{m_source_column->get_any(index)}; if (!value.is_null()) { auto v = value.get(); if (!m_state.accumulate(v)) @@ -62,6 +81,24 @@ class QueryStateMinMax : public QueryStateBase { using QueryStateBase::QueryStateBase; bool match(size_t index, Mixed value) noexcept final { + if (m_source_column) { + REALM_ASSERT_DEBUG(value.is_null()); + value = m_source_column->get_any(index); + } + if (!value.is_null()) { + auto v = value.get(); + if (!m_state.accumulate(v)) { + return true; // no match, continue searching + } + ++m_match_count; + m_minmax_key = (m_key_values ? m_key_values->get(index) : index) + m_key_offset; + } + return m_limit > m_match_count; + } + bool match(size_t index) noexcept final + { + REALM_ASSERT(m_source_column); + Mixed value{m_source_column->get_any(index)}; if (!value.is_null()) { auto v = value.get(); if (!m_state.accumulate(v)) { diff --git a/src/realm/query_engine.cpp b/src/realm/query_engine.cpp index e24d243efa0..8d2c36c6290 100644 --- a/src/realm/query_engine.cpp +++ b/src/realm/query_engine.cpp @@ -97,7 +97,7 @@ size_t ParentNode::aggregate_local(QueryStateBase* st, size_t start, size_t end, // data type array to make array call match() directly on each match, like for integers. m_state = st; - m_source_column = source_column; + m_state->set_payload_column(source_column); size_t local_matches = 0; if (m_children.size() == 1) { @@ -134,11 +134,7 @@ size_t ParentNode::aggregate_local(QueryStateBase* st, size_t start, size_t end, // If index of first match in this node equals index of first match in all remaining nodes, we have a final // match if (m == r) { - Mixed val; - if (source_column) { - val = source_column->get_any(r); - } - bool cont = st->match(r, val); + bool cont = st->match(r); if (!cont) { return static_cast(-1); } @@ -151,11 +147,7 @@ size_t ParentNode::find_all_local(size_t start, size_t end) while (start < end) { start = find_first_local(start, end); if (start != not_found) { - Mixed val; - if (m_source_column) { - val = m_source_column->get_any(start); - } - bool cont = m_state->match(start, val); + bool cont = m_state->match(start); if (!cont) { return static_cast(-1); } diff --git a/src/realm/query_engine.hpp b/src/realm/query_engine.hpp index 0bf2fe4d5c2..c912fadff60 100644 --- a/src/realm/query_engine.hpp +++ b/src/realm/query_engine.hpp @@ -254,7 +254,6 @@ class ParentNode { std::unique_ptr m_child; std::vector m_children; mutable ColKey m_condition_column_key = ColKey(); // Column of search criteria - ArrayPayload* m_source_column = nullptr; double m_dD; // Average row distance between each local match at current position double m_dT = 1.0; // Time overhead of testing index i + 1 if we have just tested index i. > 1 for linear scans, 0 @@ -378,29 +377,10 @@ class IntegerNodeBase : public ColumnNodeBase { m_dT = .25; } - bool run_single() const - { - if (m_source_column == nullptr) - return true; - // Compare leafs to see if they are the same - auto leaf = dynamic_cast(m_source_column); - return leaf && leaf->get_ref() == m_leaf->get_ref(); - } - template size_t find_all_local(size_t start, size_t end) { - if (run_single()) { - m_leaf->template find(m_value, start, end, m_state, nullptr); - } - else { - auto callback = [this](size_t index) { - auto val = m_source_column->get_any(index); - return m_state->match(index, val); - }; - m_leaf->template find(m_value, start, end, m_state, callback); - } - + m_leaf->template find(m_value, start, end, m_state); return end; } @@ -410,7 +390,6 @@ class IntegerNodeBase : public ColumnNodeBase { describe_condition() + " " + util::serializer::print_value(this->m_value); } - // Search value: TConditionValue m_value; diff --git a/src/realm/query_state.hpp b/src/realm/query_state.hpp index 06f351d270e..26a7c8374c9 100644 --- a/src/realm/query_state.hpp +++ b/src/realm/query_state.hpp @@ -24,7 +24,7 @@ namespace realm { -enum Action { act_ReturnFirst, act_Sum, act_Max, act_Min, act_Count, act_FindAll, act_CallbackIdx, act_Average }; +enum Action { act_ReturnFirst, act_Sum, act_Max, act_Min, act_Count, act_FindAll, act_Average }; // Array::VTable only uses the first 4 conditions (enums) in an array of function pointers @@ -47,6 +47,11 @@ class QueryStateBase { // Called when we have a match. // The return value indicates if the query should continue. virtual bool match(size_t, Mixed) noexcept = 0; + // This version of match is called when m_source_column + // has been set to the current leaf so that we can get the value + // from the leaf if needed. Some consumers may not need the value + // such as when just counting the results in QueryStateCount. + virtual bool match(size_t index) noexcept = 0; virtual bool match_pattern(size_t, uint64_t) { @@ -63,9 +68,17 @@ class QueryStateBase { return m_limit; } + inline void set_payload_column(ArrayPayload* payload) noexcept + { + m_source_column = payload; + } + protected: size_t m_match_count = 0; size_t m_limit; + // Array leaf of column currently in use by the query engine + // the match index points to an index in this leaf. + ArrayPayload* m_source_column = nullptr; private: virtual void dyncast(); @@ -84,6 +97,7 @@ class QueryStateCount : public QueryStateBase { { } bool match(size_t, Mixed) noexcept final; + bool match(size_t index) noexcept final; size_t get_count() const noexcept { return m_match_count; diff --git a/src/realm/table.cpp b/src/realm/table.cpp index 6eb6199fd73..c22c1581f9c 100644 --- a/src/realm/table.cpp +++ b/src/realm/table.cpp @@ -2320,12 +2320,11 @@ void Table::aggregate(QueryStateBase& st, ColKey column_key) const cluster->init_leaf(column_key, &leaf); st.m_key_offset = cluster->get_offset(); st.m_key_values = cluster->get_key_array(); - + st.set_payload_column(&leaf); bool cont = true; size_t sz = leaf.size(); for (size_t local_index = 0; cont && local_index < sz; local_index++) { - auto v = leaf.get(local_index); - cont = st.match(local_index, v); + cont = st.match(local_index); } return IteratorControl::AdvanceToNext; }; diff --git a/test/benchmark-common-tasks/main.cpp b/test/benchmark-common-tasks/main.cpp index 5e287d56564..e1fd2de5543 100644 --- a/test/benchmark-common-tasks/main.cpp +++ b/test/benchmark-common-tasks/main.cpp @@ -597,6 +597,44 @@ struct BenchmarkMixedCaseInsensitiveEqual : public BenchmarkWithType { } }; +template +struct BenchmarkRangeForType : public BenchmarkWithType { + using Base = BenchmarkWithType; + using underlying_type = typename Type::underlying_type; + BenchmarkRangeForType() + : BenchmarkWithType() + { + BenchmarkWithType::set_name_with_prefix("QueryRange"); + } + + void before_all(DBRef group) override + { + BenchmarkWithType::before_all(group); + std::sort(this->needles.begin(), this->needles.end()); + } + + void operator()(DBRef) override + { + for (size_t i = 1; i < Base::needles.size(); i++) { + if constexpr (std::is_same_v) { + TableView results = Base::m_table->where() + .greater(Base::m_col, Base::needles[i - 1]) + .less(Base::m_col, Base::needles[i]) + .find_all(); + static_cast(results); + } + else { + TableView results = Base::m_table->where() + .greater(Base::m_col, Base::needles[i - 1].template get()) + .less(Base::m_col, Base::needles[i].template get()) + .find_all(); + static_cast(results); + } + } + } +}; + + struct BenchmarkWithTimestamps : Benchmark { std::multiset values; Timestamp needle; @@ -1117,6 +1155,25 @@ struct BenchmarkQueryChainedOrInts : BenchmarkWithIntsTable { } }; +struct BenchmarkQueryChainedOrIntsCount : BenchmarkQueryChainedOrInts { + const char* name() const + { + return "QueryChainedOrIntsCount"; + } + + void operator()(DBRef) + { + ConstTableRef table = m_table; + Query query = table->where(); + for (size_t i = 0; i < values_to_query.size(); ++i) { + query.Or().equal(m_col, values_to_query[i]); + } + size_t matches = query.count(); + REALM_ASSERT_EX(matches == num_queried_matches, matches, num_queried_matches, + values_to_query.size()); + } +}; + struct BenchmarkQueryChainedOrIntsIndexed : BenchmarkQueryChainedOrInts { const char* name() const { @@ -1166,6 +1223,52 @@ struct BenchmarkQueryIntEqualityIndexed : BenchmarkQueryIntEquality { } }; +struct BenchmarkForeignAggAvg : BenchmarkWithIntsTable { + ColKey m_double_col; + Random m_rand; + const size_t num_queried_matches = 1000; + const size_t num_rows = BASE_SIZE; + std::vector values_to_query; + + const char* name() const + { + return "QueryWithForeignAggAvg"; + } + + void before_all(DBRef group) + { + BenchmarkWithIntsTable::before_all(group); + WriteTransaction tr(group); + TableRef t = tr.get_table(name()); + m_double_col = t->add_column(type_Double, "double_col"); + std::vector keys; + t->create_objects(num_rows, keys); + REALM_ASSERT(num_rows > num_queried_matches); + Random r; + size_t i = 0; + for (auto e : *t) { + e.set(m_col, i).set(m_double_col, double(i)); + ++i; + } + for (i = 0; i < num_queried_matches; ++i) { + size_t ndx_to_match = (num_rows / num_queried_matches) * i; + values_to_query.push_back(t->get_object(ndx_to_match).get(m_col)); + } + tr.commit(); + } + + void operator()(DBRef) + { + ConstTableRef table = m_table; + for (size_t i = 0; i < 50; ++i) { + auto result = table->where() + .not_equal(m_col, values_to_query[m_rand.draw_int(0, values_to_query.size())]) + .avg(m_double_col); + REALM_ASSERT(result); + } + } +}; + struct BenchmarkQuery : BenchmarkWithStrings { const char* name() const { @@ -2377,8 +2480,10 @@ int benchmark_common_tasks_main() BENCH(BenchmarkQueryNotChainedOrStrings); BENCH(BenchmarkQueryChainedOrInts); BENCH(BenchmarkQueryChainedOrIntsIndexed); + BENCH(BenchmarkQueryChainedOrIntsCount); BENCH(BenchmarkQueryIntEquality); BENCH(BenchmarkQueryIntEqualityIndexed); + BENCH(BenchmarkForeignAggAvg); BENCH(BenchmarkIntVsDoubleColumns); BENCH(BenchmarkQueryStringOverLinks); BENCH(BenchmarkSubQuery); @@ -2397,6 +2502,8 @@ int benchmark_common_tasks_main() BENCH(BenchmarkMixedCaseInsensitiveEqual>); BENCH(BenchmarkMixedCaseInsensitiveEqual>); + BENCH(BenchmarkRangeForType>); + BENCH(BenchmarkQueryTimestampGreaterOverLinks); BENCH(BenchmarkQueryTimestampGreater); BENCH(BenchmarkQueryTimestampGreaterEqual); diff --git a/test/large_tests/test_column_large.cpp b/test/large_tests/test_column_large.cpp index 96624499eb6..86fde1461e2 100644 --- a/test/large_tests/test_column_large.cpp +++ b/test/large_tests/test_column_large.cpp @@ -211,7 +211,7 @@ TEST_IF(ColumnLarge_Less, TEST_DURATION >= 3) // LESS a.set(match, v[w] - 1); QueryStateFindFirst state; - a.find(v[w], from, to, &state, nullptr); + a.find(v[w], from, to, &state); size_t f = to_size_t(state.m_state); a.set(match, v[w]); if (match >= from && match < to) { @@ -226,7 +226,7 @@ TEST_IF(ColumnLarge_Less, TEST_DURATION >= 3) // GREATER a.set(match, v[w] + 1); QueryStateFindFirst state; - a.find(v[w], from, to, &state, nullptr); + a.find(v[w], from, to, &state); size_t f = to_size_t(state.m_state); a.set(match, v[w]); if (match >= from && match < to) { @@ -257,7 +257,7 @@ TEST_IF(ColumnLarge_Less, TEST_DURATION >= 3) accu.clear(); QueryStateFindAll state(accu); - a.find(v[w], from, to, &state, nullptr); + a.find(v[w], from, to, &state); a.set(match, v[w]); a.set(match + off, v[w]); @@ -284,7 +284,7 @@ TEST_IF(ColumnLarge_Less, TEST_DURATION >= 3) accu.clear(); QueryStateFindAll state(accu); - a.find(v[w], from, to, &state, nullptr); + a.find(v[w], from, to, &state); a.set(match, v[w]); a.set(match + off, v[w]); @@ -310,7 +310,7 @@ TEST_IF(ColumnLarge_Less, TEST_DURATION >= 3) accu.clear(); QueryStateFindAll state(accu); - a.find(v[w] + 1, from, to, &state, nullptr); + a.find(v[w] + 1, from, to, &state); a.set(match, v[w]); a.set(match + off, v[w]); From 2990d655d819249b66b85fa4c38797d3e9a72ee3 Mon Sep 17 00:00:00 2001 From: James Stone Date: Mon, 30 Oct 2023 14:51:26 -0700 Subject: [PATCH 2/4] remove find_action_pattern which hasn't been used in years --- src/realm/array_with_find.hpp | 53 +++++------------------------------ 1 file changed, 7 insertions(+), 46 deletions(-) diff --git a/src/realm/array_with_find.hpp b/src/realm/array_with_find.hpp index 5d7790378f5..142cf588839 100644 --- a/src/realm/array_with_find.hpp +++ b/src/realm/array_with_find.hpp @@ -24,13 +24,9 @@ Searching: The main finding function is: cond: One of Equal, NotEqual, Greater, etc. classes Action: One of act_ReturnFirst, act_FindAll, act_Max, etc, constants - find() will call find_action_pattern() or QueryStateBase::match() for each search result - - find() -----------> bool QueryStateBase::match() - | ^ - +-> find_action_pattern()----+ - - If match() returns false, find() will exit, otherwise it will keep searching remaining items in array. + find() will call QueryStateBase::match() for each search result If match() + returns false, find() will exit, otherwise it will keep searching remaining + items in array. */ #ifndef REALM_ARRAY_WITH_FIND_HPP @@ -164,7 +160,6 @@ class ArrayWithFind { private: const Array& m_array; - bool find_action_pattern(size_t index, uint64_t pattern, QueryStateBase* state) const; template bool find_all_will_match(size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; }; @@ -172,26 +167,6 @@ class ArrayWithFind { // Finding code * //************************************************************************************* - -/* -find() (calls find_optimized()) may call find_action_pattern before calling QueryStateBase->match(). - -'indexpattern' contains a 64-bit chunk of elements, each of 'width' bits in size where each element indicates a -match if its lower bit is set, otherwise it indicates a non-match. 'index' tells the database row index of the -first element. You must return true if you chose to 'consume' the chunk or false if not. If not, then Array-finder -will afterwards call match() successive times with pattern == false. - -Array-finder decides itself if - and when - it wants to pass you an indexpattern. It depends on array bit width, match -frequency, and whether the arithemetic and computations for the given search criteria makes it feasible to construct -such a pattern. -*/ -inline bool ArrayWithFind::find_action_pattern(size_t /*index*/, uint64_t /*pattern*/, QueryStateBase* /*st*/) const -{ - // return st->match_pattern(index, pattern); FIXME: Use for act_Count - return false; -} - - template uint64_t ArrayWithFind::cascade(uint64_t a) const { @@ -313,10 +288,10 @@ REALM_NOINLINE bool ArrayWithFind::find_all_will_match(size_t start2, size_t end return true; } -// This is the main finding function for Array. Other finding functions are just wrappers around this one. -// Search for 'value' using condition cond (Equal, NotEqual, Less, etc) and call QueryStateBase->match() or -// find_action_pattern() for each match. Break and return if QueryStateBase->match() returns false or 'end' is -// reached. +// This is the main finding function for Array. Other finding functions are just +// wrappers around this one. Search for 'value' using condition cond (Equal, +// NotEqual, Less, etc) and call QueryStateBase::match() for each match. Break and +// return if QueryStateBase::match() returns false or 'end' is reached. template bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { @@ -488,9 +463,6 @@ bool ArrayWithFind::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryStateBas : ((chunk - magic) & ~chunk & ~0ULL / no0(mask1) * (mask2 + 1)); size_t p = 0; while (m) { - if (find_action_pattern(baseindex, m >> (no0(width) - 1), state)) - break; // consumed, so do not call QueryStateBase->match() - size_t t = first_set_bit64(m) / no0(width); p += t; if (!state->match(p + baseindex, Mixed{int64_t((chunk >> (p * width)) & mask1)})) @@ -624,10 +596,6 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t size_t a = 0; while (eq ? test_zero(v2) : v2) { - - if (find_action_pattern(start + baseindex, cascade(v2), state)) - break; // consumed - size_t t = find_zero(v2); a += t; @@ -757,13 +725,6 @@ REALM_FORCEINLINE bool ArrayWithFind::find_sse_intern(__m128i* action_data, __m1 size_t s = i * sizeof(__m128i) * 8 / no0(width); while (resmask != 0) { - constexpr uint64_t upper = lower_bits() << (no0(width / 8) - 1); - uint64_t pattern = - resmask & - upper; // fixme, bits at wrong offsets. Only OK because we only use them in 'count' aggregate - if (find_action_pattern(s + baseindex, pattern, state)) - break; - size_t idx = first_set_bit(resmask) * 8 / no0(width); s += idx; if (!state->match(s + baseindex)) From badac29ffdb85cca2bf9fb9d601ad2add078b3e2 Mon Sep 17 00:00:00 2001 From: James Stone Date: Mon, 30 Oct 2023 14:55:46 -0700 Subject: [PATCH 3/4] add changeloge note --- CHANGELOG.md | 1 + 1 file changed, 1 insertion(+) diff --git a/CHANGELOG.md b/CHANGELOG.md index 099a59ebb81..72b1da698b1 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -19,6 +19,7 @@ ### Internals * REALM_[ATMU]SAN cmake flags no longer override compilation options and can be combined with Debug|RelWithDebInfo|etc. build types. Rel[ATMU]SAN build type shortcuts are now all slightly optimized debug-based builds with sanitizers. REALM_ASAN now works with msvc (2019/2022) builds. ([PR #6911](https://github.com/realm/realm-core/pull/6911)) +* Remove ArrayWithFind's ability to use a templated callback parameter. The QueryStateBase consumers now use an index and the array leaf to get the actual value if needed. This allows certain queries such as count() to not do as many lookups to the actual values and results in a small performance gain. Also remove `find_action_pattern()` which was unused for a long time. This reduction in templating throughout the query system produces a small (~100k) binary size reduction. ([#7095](https://github.com/realm/realm-core/pull/7095)) ---------------------------------------------- From 012b70b06e7f5751db6cc2da9778eaccbc1db91e Mon Sep 17 00:00:00 2001 From: James Stone Date: Tue, 31 Oct 2023 11:08:20 -0700 Subject: [PATCH 4/4] lint and address comments --- src/realm/array_with_find.hpp | 39 ++++++++++++++-------------- src/realm/query_conditions_tpl.hpp | 3 --- test/benchmark-common-tasks/main.cpp | 3 +-- 3 files changed, 20 insertions(+), 25 deletions(-) diff --git a/src/realm/array_with_find.hpp b/src/realm/array_with_find.hpp index 142cf588839..81d86d47e44 100644 --- a/src/realm/array_with_find.hpp +++ b/src/realm/array_with_find.hpp @@ -18,13 +18,12 @@ /* Searching: The main finding function is: - template + template void find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState *state) const cond: One of Equal, NotEqual, Greater, etc. classes - Action: One of act_ReturnFirst, act_FindAll, act_Max, etc, constants - find() will call QueryStateBase::match() for each search result If match() + find() will call QueryStateBase::match() for each search result. If match() returns false, find() will exit, otherwise it will keep searching remaining items in array. */ @@ -104,14 +103,16 @@ class ArrayWithFind { // Non-SSE find for Equal/NotEqual template - inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; + inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, + QueryStateBase* state) const; // Non-SSE find for Less/Greater template bool compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; template - bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; + bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, + QueryStateBase* state) const; template bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const; @@ -293,7 +294,8 @@ REALM_NOINLINE bool ArrayWithFind::find_all_will_match(size_t start2, size_t end // NotEqual, Less, etc) and call QueryStateBase::match() for each match. Break and // return if QueryStateBase::match() returns false or 'end' is reached. template -bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const +bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, + QueryStateBase* state) const { REALM_ASSERT_DEBUG(start <= m_array.m_size && (end <= m_array.m_size || end == size_t(-1)) && start <= end); @@ -335,9 +337,8 @@ bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size __m128i* const b = reinterpret_cast<__m128i*>(round_down(m_array.m_data + end * bitwidth / 8, sizeof(__m128i))); - if (!compare(value, start2, - (reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth), - baseindex, state)) + if (!compare(value, start2, (reinterpret_cast(a) - m_array.m_data) * 8 / no0(bitwidth), + baseindex, state)) return false; // Search aligned area with SSE @@ -358,9 +359,8 @@ bool ArrayWithFind::find_optimized(int64_t value, size_t start, size_t end, size } // Search remainder with compare_equality() - if (!compare(value, - (reinterpret_cast(b) - m_array.m_data) * 8 / no0(bitwidth), end, - baseindex, state)) + if (!compare(value, (reinterpret_cast(b) - m_array.m_data) * 8 / no0(bitwidth), end, + baseindex, state)) return false; return true; @@ -641,15 +641,15 @@ inline bool ArrayWithFind::compare_equality(int64_t value, size_t start, size_t template bool ArrayWithFind::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const { - REALM_TEMPEX2(return find_optimized, cond, m_array.m_width, - (value, start, end, baseindex, state)); + REALM_TEMPEX2(return find_optimized, cond, m_array.m_width, (value, start, end, baseindex, state)); } #ifdef REALM_COMPILER_SSE // 'items' is the number of 16-byte SSE chunks. Returns index of packed element relative to first integer of first // chunk template -bool ArrayWithFind::find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, size_t baseindex) const +bool ArrayWithFind::find_sse(int64_t value, __m128i* data, size_t items, QueryStateBase* state, + size_t baseindex) const { __m128i search = {0}; @@ -782,8 +782,7 @@ bool ArrayWithFind::compare_leafs(const Array* foreign, size_t start, size_t end } bool r; - REALM_TEMPEX2(r = compare_leafs, cond, m_array.m_width, - (foreign, start, end, baseindex, state)) + REALM_TEMPEX2(r = compare_leafs, cond, m_array.m_width, (foreign, start, end, baseindex, state)) return r; } @@ -846,8 +845,7 @@ bool ArrayWithFind::compare_leafs_4(const Array* foreign, size_t start, size_t e __m128i* a = reinterpret_cast<__m128i*>(m_array.m_data + start * width / 8); __m128i* b = reinterpret_cast<__m128i*>(foreign_m_data + start * width / 8); - bool continue_search = - find_sse_intern(a, b, 1, state, baseindex + start); + bool continue_search = find_sse_intern(a, b, 1, state, baseindex + start); if (!continue_search) return false; @@ -894,7 +892,8 @@ bool ArrayWithFind::compare(int64_t value, size_t start, size_t end, size_t base } template -bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryStateBase* state) const +bool ArrayWithFind::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, + QueryStateBase* state) const { REALM_ASSERT(start <= m_array.m_size && (end <= m_array.m_size || end == size_t(-1)) && start <= end); uint64_t mask = (bitwidth == 64 ? ~0ULL diff --git a/src/realm/query_conditions_tpl.hpp b/src/realm/query_conditions_tpl.hpp index dd348422c57..4a1a233fb90 100644 --- a/src/realm/query_conditions_tpl.hpp +++ b/src/realm/query_conditions_tpl.hpp @@ -39,9 +39,6 @@ class QueryStateSum : public QueryStateBase { REALM_ASSERT_DEBUG(value.is_null()); value = m_source_column->get_any(index); } - else { - static_cast(m_source_column); - } if (!value.is_null()) { auto v = value.get(); if (!m_state.accumulate(v)) diff --git a/test/benchmark-common-tasks/main.cpp b/test/benchmark-common-tasks/main.cpp index e1fd2de5543..e3cfa532fe4 100644 --- a/test/benchmark-common-tasks/main.cpp +++ b/test/benchmark-common-tasks/main.cpp @@ -1169,8 +1169,7 @@ struct BenchmarkQueryChainedOrIntsCount : BenchmarkQueryChainedOrInts { query.Or().equal(m_col, values_to_query[i]); } size_t matches = query.count(); - REALM_ASSERT_EX(matches == num_queried_matches, matches, num_queried_matches, - values_to_query.size()); + REALM_ASSERT_EX(matches == num_queried_matches, matches, num_queried_matches, values_to_query.size()); } };