* [PATCH v2 0/4] box: introduce hint option for memtx tree index @ 2019-02-13 9:32 Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov ` (3 more replies) 0 siblings, 4 replies; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov Reworked memtx tree to use 'tuple hints'. Introduced special functions for retrieve tuple hints for a particular key_def. Hint is an integer that can be used for tuple comparison optimization: if a hint of one tuple is less than a hint of another then the first tuple is definitely less than the second; only if hints are equal tuple_compare must be called for getting comparison result. Hints are only useful when: * they are precalculated and stored along with the tuple; calculation is not cheap (cheaper than tuple_compare btw) but precalculated hints allow to compare tuples without even fetching tuple data. * first part of key_def is 'string', 'unsigned' or 'integer' * since hint is calculated using only the first part of key_def (and only first several characters if it is a string) this part must be different with high probability for every tuple pair. Enabled hint option improve performance on average by 15%; Select operations are significantly accelerated (there are scenarios in which the difference reaches 200-250%). Changes in version 2: -- Splitted patch to parts in other way to decrease diff -- Hints are not index option anymore, but default where possible -- Removed hints for numeric types http://github.com/tarantool/tarantool/tree/kshch/gh-3961-tuple-hints https://github.com/tarantool/tarantool/issues/3961 Alexandr Lyapunov (1): box: introduce tuple compare hint for string index Kirill Shcherbatov (3): box: move memtx_tree implementation to source file box: rework memtx_tree to store arbitrary nodes box: rename memtx_tree.c to memtx_tree_impl.h src/box/CMakeLists.txt | 2 +- src/box/key_def.c | 1 + src/box/key_def.h | 44 ++ src/box/memtx_tree.h | 68 +-- src/box/memtx_tree_decl.c | 207 +++++++++ src/box/{memtx_tree.c => memtx_tree_impl.h} | 490 +++++++++++++++----- src/box/tuple_compare.cc | 101 ++++ src/box/tuple_compare.h | 7 + src/coll.c | 45 ++ src/coll.h | 4 + 10 files changed, 787 insertions(+), 182 deletions(-) create mode 100644 src/box/memtx_tree_decl.c rename src/box/{memtx_tree.c => memtx_tree_impl.h} (55%) -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 1/4] box: move memtx_tree implementation to source file 2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov @ 2019-02-13 9:32 ` Kirill Shcherbatov 2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov 2019-02-21 13:26 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov ` (2 subsequent siblings) 3 siblings, 2 replies; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov Refactored memtx_tree code so that memtx_tree.h contained only the signature of the tree object constructor memtx_tree_index_new, while all implementation details were in memtx_tree.c. This will further allow to template the implementation details. Needed for #3961 --- src/box/memtx_tree.c | 62 ++++++++++++++++++++++++++++++++++++++-- src/box/memtx_tree.h | 68 ++------------------------------------------ 2 files changed, 63 insertions(+), 67 deletions(-) diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c index f851fb869..2e8adb682 100644 --- a/src/box/memtx_tree.c +++ b/src/box/memtx_tree.c @@ -39,6 +39,64 @@ #include <third_party/qsort_arg.h> #include <small/mempool.h> +/** + * Struct that is used as a key in BPS tree definition. + */ +struct memtx_tree_key_data { + /** Sequence of msgpacked search fields. */ + const char *key; + /** Number of msgpacked search fields. */ + uint32_t part_count; +}; + +/** + * BPS tree element vs key comparator. + * Defined in header in order to allow compiler to inline it. + * @param tuple - tuple to compare. + * @param key_data - key to compare with. + * @param def - key definition. + * @retval 0 if tuple == key in terms of def. + * @retval <0 if tuple < key in terms of def. + * @retval >0 if tuple > key in terms of def. + */ +static int +memtx_tree_compare_key(const struct tuple *tuple, + const struct memtx_tree_key_data *key_data, + struct key_def *def) +{ + return tuple_compare_with_key(tuple, key_data->key, + key_data->part_count, def); +} + +#define BPS_TREE_NAME memtx_tree +#define BPS_TREE_BLOCK_SIZE (512) +#define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE +#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg) +#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg) +#define bps_tree_elem_t struct tuple * +#define bps_tree_key_t struct memtx_tree_key_data * +#define bps_tree_arg_t struct key_def * + +#include "salad/bps_tree.h" + +#undef BPS_TREE_NAME +#undef BPS_TREE_BLOCK_SIZE +#undef BPS_TREE_EXTENT_SIZE +#undef BPS_TREE_COMPARE +#undef BPS_TREE_COMPARE_KEY +#undef bps_tree_elem_t +#undef bps_tree_key_t +#undef bps_tree_arg_t + +struct memtx_tree_index { + struct index base; + struct memtx_tree tree; + struct tuple **build_array; + size_t build_array_size, build_array_alloc_size; + struct memtx_gc_task gc_task; + struct memtx_tree_iterator gc_iterator; +}; + /* {{{ Utilities. *************************************************/ static int @@ -683,7 +741,7 @@ static const struct index_vtab memtx_tree_index_vtab = { /* .end_build = */ memtx_tree_index_end_build, }; -struct memtx_tree_index * +struct index * memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) { if (!mempool_is_initialized(&memtx->tree_iterator_pool)) { @@ -707,5 +765,5 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) struct key_def *cmp_def = memtx_tree_index_cmp_def(index); memtx_tree_create(&index->tree, cmp_def, memtx_index_extent_alloc, memtx_index_extent_free, memtx); - return index; + return &index->base; } diff --git a/src/box/memtx_tree.h b/src/box/memtx_tree.h index bbc8b2419..edeaebab9 100644 --- a/src/box/memtx_tree.h +++ b/src/box/memtx_tree.h @@ -30,78 +30,16 @@ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ -#include <stddef.h> -#include <stdint.h> - -#include "index.h" -#include "memtx_engine.h" #if defined(__cplusplus) extern "C" { #endif /* defined(__cplusplus) */ +struct index; +struct index_def; struct memtx_engine; -/** - * Struct that is used as a key in BPS tree definition. - */ -struct memtx_tree_key_data -{ - /** Sequence of msgpacked search fields */ - const char *key; - /** Number of msgpacked search fields */ - uint32_t part_count; -}; - -/** - * BPS tree element vs key comparator. - * Defined in header in order to allow compiler to inline it. - * @param tuple - tuple to compare. - * @param key_data - key to compare with. - * @param def - key definition. - * @retval 0 if tuple == key in terms of def. - * @retval <0 if tuple < key in terms of def. - * @retval >0 if tuple > key in terms of def. - */ -static inline int -memtx_tree_compare_key(const struct tuple *tuple, - const struct memtx_tree_key_data *key_data, - struct key_def *def) -{ - return tuple_compare_with_key(tuple, key_data->key, - key_data->part_count, def); -} - -#define BPS_TREE_NAME memtx_tree -#define BPS_TREE_BLOCK_SIZE (512) -#define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE -#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg) -#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg) -#define bps_tree_elem_t struct tuple * -#define bps_tree_key_t struct memtx_tree_key_data * -#define bps_tree_arg_t struct key_def * - -#include "salad/bps_tree.h" - -#undef BPS_TREE_NAME -#undef BPS_TREE_BLOCK_SIZE -#undef BPS_TREE_EXTENT_SIZE -#undef BPS_TREE_COMPARE -#undef BPS_TREE_COMPARE_KEY -#undef bps_tree_elem_t -#undef bps_tree_key_t -#undef bps_tree_arg_t - -struct memtx_tree_index { - struct index base; - struct memtx_tree tree; - struct tuple **build_array; - size_t build_array_size, build_array_alloc_size; - struct memtx_gc_task gc_task; - struct memtx_tree_iterator gc_iterator; -}; - -struct memtx_tree_index * +struct index * memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def); #if defined(__cplusplus) -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 1/4] box: move memtx_tree implementation to source file 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov @ 2019-02-14 13:57 ` Konstantin Osipov 2019-02-21 13:26 ` Vladimir Davydov 1 sibling, 0 replies; 13+ messages in thread From: Konstantin Osipov @ 2019-02-14 13:57 UTC (permalink / raw) To: tarantool-patches; +Cc: vdavydov.dev, Kirill Shcherbatov * Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/13 13:03]: > Refactored memtx_tree code so that memtx_tree.h contained only > the signature of the tree object constructor memtx_tree_index_new, > while all implementation details were in memtx_tree.c. > This will further allow to template the implementation details. > > Needed for #3961 This patch is OK to push. I am not sure if any of the following patches will be in, but hiding more details in the implementation is always a good thing. -- Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 http://tarantool.io - www.twitter.com/kostja_osipov ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v2 1/4] box: move memtx_tree implementation to source file 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov 2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov @ 2019-02-21 13:26 ` Vladimir Davydov 1 sibling, 0 replies; 13+ messages in thread From: Vladimir Davydov @ 2019-02-21 13:26 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja The subject line prefix should be 'memtx:' I think. On Wed, Feb 13, 2019 at 12:32:25PM +0300, Kirill Shcherbatov wrote: > Refactored memtx_tree code so that memtx_tree.h contained only > the signature of the tree object constructor memtx_tree_index_new, > while all implementation details were in memtx_tree.c. > This will further allow to template the implementation details. > > Needed for #3961 > --- > src/box/memtx_tree.c | 62 ++++++++++++++++++++++++++++++++++++++-- > src/box/memtx_tree.h | 68 ++------------------------------------------ > 2 files changed, 63 insertions(+), 67 deletions(-) The patch is good, but I think we shouldn't stop at memtx_tree and do the same for other memtx indexes - hash, bitset, rtree. Please do it in the scope of this patch. ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes 2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov @ 2019-02-13 9:32 ` Kirill Shcherbatov 2019-02-21 15:01 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov 3 siblings, 1 reply; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov Reworked memtx_tree class to use arbitrary containers as a tree nodes. This makes possible to implement tuple hints in subsequent patches. The memtx_tree.c is currently used in a header manner. This is to ensure that functional changes in the patch do not mix with refactoring, that will be finished in the next commit. Needed for #3961 --- src/box/CMakeLists.txt | 2 +- src/box/memtx_tree.c | 498 ++++++++++++++++++++++++++------------ src/box/memtx_tree_decl.c | 84 +++++++ 3 files changed, 434 insertions(+), 150 deletions(-) create mode 100644 src/box/memtx_tree_decl.c diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt index 5521e489e..dc8cc2cd5 100644 --- a/src/box/CMakeLists.txt +++ b/src/box/CMakeLists.txt @@ -64,7 +64,7 @@ add_library(box STATIC index_def.c iterator_type.c memtx_hash.c - memtx_tree.c + memtx_tree_decl.c memtx_rtree.c memtx_bitset.c engine.c diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c index 2e8adb682..0874b7dc8 100644 --- a/src/box/memtx_tree.c +++ b/src/box/memtx_tree.c @@ -1,5 +1,5 @@ /* - * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file. + * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file. * * Redistribution and use in source and binary forms, with or * without modification, are permitted provided that the following @@ -28,72 +28,156 @@ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ -#include "memtx_tree.h" -#include "memtx_engine.h" -#include "space.h" -#include "schema.h" /* space_cache_find() */ -#include "errinj.h" -#include "memory.h" -#include "fiber.h" -#include "tuple.h" -#include <third_party/qsort_arg.h> + +#if defined(__cplusplus) +extern "C" { +#endif /* defined(__cplusplus) */ + #include <small/mempool.h> +#include <third_party/qsort_arg.h> +#include "memtx_engine.h" +#include "schema.h" -/** - * Struct that is used as a key in BPS tree definition. - */ -struct memtx_tree_key_data { - /** Sequence of msgpacked search fields. */ - const char *key; - /** Number of msgpacked search fields. */ - uint32_t part_count; -}; +#ifndef MEMTX_TREE_NAME +#error "MEMTX_TREE_NAME must be defined" +#endif + +#ifndef memtx_tree_elem +#error "memtx_tree_elem must be defined" +#endif + +#ifndef memtx_tree_key +#error "memtx_tree_key must be defined" +#endif + +#ifndef MEMTX_TREE_ELEM_CMP +#error "MEMTX_TREE_ELEM_CMP must be defined" +#endif + +#ifndef MEMTX_TREE_ELEM_WITH_KEY_CMP +#error "MEMTX_TREE_ELEM_WITH_KEY_CMP must be defined" +#endif + +#ifndef MEMTX_TREE_ELEM_SET +#error "MEMTX_TREE_ELEM_SET must be defined" +#endif + +#ifndef MEMTX_TREE_KEY_SET +#error "MEMTX_TREE_KEY_SET must be defined" +#endif + +#ifndef MEMTX_TREE_ELEM_GET +#error "MEMTX_TREE_ELEM_GET must be defined" +#endif + +#ifndef MEMTX_TREE_KEY_GET +#error "MEMTX_TREE_KEY_GET must be defined" +#endif /** - * BPS tree element vs key comparator. - * Defined in header in order to allow compiler to inline it. - * @param tuple - tuple to compare. - * @param key_data - key to compare with. - * @param def - key definition. - * @retval 0 if tuple == key in terms of def. - * @retval <0 if tuple < key in terms of def. - * @retval >0 if tuple > key in terms of def. + * The size of the biggest memtx tree iterator. Used with + * mempool_create. This is the size of the block that will be + * allocated for each iterator. */ -static int -memtx_tree_compare_key(const struct tuple *tuple, - const struct memtx_tree_key_data *key_data, - struct key_def *def) -{ - return tuple_compare_with_key(tuple, key_data->key, - key_data->part_count, def); -} +#define MEMTX_TREE_ITERATOR_SIZE (152) -#define BPS_TREE_NAME memtx_tree +#define bps_tree_elem_t memtx_tree_elem +#define bps_tree_key_t memtx_tree_key * +#define bps_tree_arg_t struct key_def * +#define BPS_TREE_NAME CONCAT3(MEMTX_TREE_NAME, _, tree) #define BPS_TREE_BLOCK_SIZE (512) #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE -#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg) -#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg) -#define bps_tree_elem_t struct tuple * -#define bps_tree_key_t struct memtx_tree_key_data * -#define bps_tree_arg_t struct key_def * +#define BPS_TREE_COMPARE(a, b, arg) MEMTX_TREE_ELEM_CMP(&a, &b, arg) +#define BPS_TREE_COMPARE_KEY(a, b, arg) MEMTX_TREE_ELEM_WITH_KEY_CMP(&a, b, arg) +#define BPS_TREE_NO_DEBUG #include "salad/bps_tree.h" +#undef bps_tree_elem_t +#undef bps_tree_key_t +#undef bps_tree_arg_t #undef BPS_TREE_NAME #undef BPS_TREE_BLOCK_SIZE #undef BPS_TREE_EXTENT_SIZE #undef BPS_TREE_COMPARE #undef BPS_TREE_COMPARE_KEY -#undef bps_tree_elem_t -#undef bps_tree_key_t -#undef bps_tree_arg_t +#undef BPS_TREE_NO_DEBUG + +#define memtx_tree CONCAT3(MEMTX_TREE_NAME, _, tree) +#define _tree_api_name(postfix) CONCAT5(MEMTX_TREE_NAME, _, tree, _, postfix) +#define memtx_tree_iterator _tree_api_name(iterator) +#define memtx_tree_iterator_is_invalid _tree_api_name(iterator_is_invalid) +#define memtx_tree_iterator_first _tree_api_name(iterator_first) +#define memtx_tree_iterator_last _tree_api_name(iterator_last) +#define memtx_tree_iterator_get_elem _tree_api_name(iterator_get_elem) +#define memtx_tree_iterator_next _tree_api_name(iterator_next) +#define memtx_tree_iterator_prev _tree_api_name(iterator_prev) +#define memtx_tree_iterator_freeze _tree_api_name(iterator_freeze) +#define memtx_tree_iterator_destroy _tree_api_name(iterator_destroy) +#define memtx_tree_create _tree_api_name(create) +#define memtx_tree_build _tree_api_name(build) +#define memtx_tree_destroy _tree_api_name(destroy) +#define memtx_tree_find _tree_api_name(find) +#define memtx_tree_insert _tree_api_name(insert) +#define memtx_tree_delete _tree_api_name(delete) +#define memtx_tree_size _tree_api_name(size) +#define memtx_tree_mem_used _tree_api_name(mem_used) +#define memtx_tree_random _tree_api_name(random) +#define memtx_tree_invalid_iterator _tree_api_name(invalid_iterator) +#define memtx_tree_lower_bound _tree_api_name(lower_bound) +#define memtx_tree_upper_bound _tree_api_name(upper_bound) +#define memtx_tree_lower_bound_elem _tree_api_name(lower_bound_elem) +#define memtx_tree_upper_bound_elem _tree_api_name(upper_bound_elem) + +#undef _api_name +#define _api_name(postfix) CONCAT3(MEMTX_TREE_NAME, _, postfix) +#define memtx_tree_index _api_name(index) +#define memtx_tree_qcompare _api_name(qcompare) +#define tree_iterator _api_name(iterator) +#define tree_iterator_free _api_name(iterator_free) +#define tree_iterator_cast _api_name(iterator_cast) +#define tree_iterator_dummie _api_name(iterator_dummie) +#define tree_iterator_next _api_name(iterator_next) +#define tree_iterator_prev _api_name(iterator_prev) +#define tree_iterator_next_equal _api_name(iterator_next_equal) +#define tree_iterator_prev_equal _api_name(iterator_prev_equal) +#define tree_iterator_set_next_method _api_name(iterator_set_next_method) +#define tree_iterator_start _api_name(iterator_start) +#define memtx_tree_index_cmp_def _api_name(index_cmp_def) +#define memtx_tree_index_free _api_name(index_free) +#define memtx_tree_index_gc_run _api_name(index_gc_run) +#define memtx_tree_index_gc_free _api_name(index_gc_free) +#define memtx_tree_index_gc_vtab _api_name(index_gc_vtab) +#define memtx_tree_index_destroy _api_name(index_destroy) +#define memtx_tree_index_update_def _api_name(index_update_def) +#define memtx_tree_index_depends_on_pk _api_name(index_depends_on_pk) +#define memtx_tree_index_size _api_name(index_size) +#define memtx_tree_index_bsize _api_name(index_bsize) +#define memtx_tree_index_random _api_name(index_random) +#define memtx_tree_index_count _api_name(index_count) +#define memtx_tree_index_get _api_name(index_get) +#define memtx_tree_index_insert_tuple _api_name(index_insert_tuple) +#define memtx_tree_index_delete_tuple _api_name(index_delete_tuple) +#define memtx_tree_index_replace _api_name(index_replace) +#define memtx_tree_index_create_iterator _api_name(index_create_iterator) +#define memtx_tree_index_begin_build _api_name(index_begin_build) +#define memtx_tree_index_build_next _api_name(index_build_next) +#define memtx_tree_index_reserve _api_name(index_reserve) +#define memtx_tree_index_end_build _api_name(index_end_build) +#define tree_snapshot_iterator _api_name(snapshot_iterator) +#define tree_snapshot_iterator_free _api_name(snapshot_iterator_free) +#define tree_snapshot_iterator_next _api_name(snapshot_iterator_next) +#define memtx_tree_index_create_snapshot_iterator\ + _api_name(index_create_snapshot_iterator) +#define memtx_tree_index_vtab _api_name(index_vtab) +#define memtx_tree_index_new _api_name(index_new) struct memtx_tree_index { struct index base; - struct memtx_tree tree; - struct tuple **build_array; + memtx_tree_elem *build_array; size_t build_array_size, build_array_alloc_size; struct memtx_gc_task gc_task; + struct memtx_tree tree; struct memtx_tree_iterator gc_iterator; }; @@ -102,8 +186,8 @@ struct memtx_tree_index { static int memtx_tree_qcompare(const void* a, const void *b, void *c) { - return tuple_compare(*(struct tuple **)a, - *(struct tuple **)b, (struct key_def *)c); + return MEMTX_TREE_ELEM_CMP((memtx_tree_elem *)a, + (memtx_tree_elem *)b, c); } /* {{{ MemtxTree Iterators ****************************************/ @@ -113,17 +197,21 @@ struct tree_iterator { struct index_def *index_def; struct memtx_tree_iterator tree_iterator; enum iterator_type type; - struct memtx_tree_key_data key_data; - struct tuple *current_tuple; + memtx_tree_key key_data; + memtx_tree_elem current; /** Memory pool the iterator was allocated from. */ struct mempool *pool; }; +static_assert(sizeof(struct tree_iterator) <= MEMTX_TREE_ITERATOR_SIZE, + "tree_iterator must be less or equal than " + "MEMTX_TREE_ITERATOR_SIZE"); + static void tree_iterator_free(struct iterator *iterator); static inline struct tree_iterator * -tree_iterator(struct iterator *it) +tree_iterator_cast(struct iterator *it) { assert(it->free == tree_iterator_free); return (struct tree_iterator *) it; @@ -132,9 +220,10 @@ tree_iterator(struct iterator *it) static void tree_iterator_free(struct iterator *iterator) { - struct tree_iterator *it = tree_iterator(iterator); - if (it->current_tuple != NULL) - tuple_unref(it->current_tuple); + struct tree_iterator *it = tree_iterator_cast(iterator); + struct tuple *tuple = MEMTX_TREE_ELEM_GET(&it->current); + if (tuple != NULL) + tuple_unref(tuple); mempool_free(it->pool, it); } @@ -149,25 +238,28 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret) static int tree_iterator_next(struct iterator *iterator, struct tuple **ret) { - struct tuple **res; - struct tree_iterator *it = tree_iterator(iterator); - assert(it->current_tuple != NULL); - struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); - if (check == NULL || *check != it->current_tuple) + struct tree_iterator *it = tree_iterator_cast(iterator); + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); + memtx_tree_elem *check = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + if (check == NULL || + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) { it->tree_iterator = - memtx_tree_upper_bound_elem(it->tree, it->current_tuple, - NULL); - else + memtx_tree_upper_bound_elem(it->tree, it->current, NULL); + } else { memtx_tree_iterator_next(it->tree, &it->tree_iterator); - tuple_unref(it->current_tuple); - it->current_tuple = NULL; - res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + } + tuple_unref(MEMTX_TREE_ELEM_GET(&it->current)); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); if (res == NULL) { iterator->next = tree_iterator_dummie; + memset(&it->current, 0, sizeof(it->current)); *ret = NULL; } else { - *ret = it->current_tuple = *res; - tuple_ref(it->current_tuple); + *ret = MEMTX_TREE_ELEM_GET(res); + tuple_ref(*ret); + it->current = *res; } return 0; } @@ -175,23 +267,27 @@ tree_iterator_next(struct iterator *iterator, struct tuple **ret) static int tree_iterator_prev(struct iterator *iterator, struct tuple **ret) { - struct tree_iterator *it = tree_iterator(iterator); - assert(it->current_tuple != NULL); - struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); - if (check == NULL || *check != it->current_tuple) + struct tree_iterator *it = tree_iterator_cast(iterator); + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); + memtx_tree_elem *check = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + if (check == NULL || + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) { it->tree_iterator = - memtx_tree_lower_bound_elem(it->tree, it->current_tuple, - NULL); + memtx_tree_lower_bound_elem(it->tree, it->current, NULL); + } memtx_tree_iterator_prev(it->tree, &it->tree_iterator); - tuple_unref(it->current_tuple); - it->current_tuple = NULL; - struct tuple **res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + tuple_unref(MEMTX_TREE_ELEM_GET(&it->current)); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); if (!res) { iterator->next = tree_iterator_dummie; + memset(&it->current, 0, sizeof(it->current)); *ret = NULL; } else { - *ret = it->current_tuple = *res; - tuple_ref(it->current_tuple); + *ret = MEMTX_TREE_ELEM_GET(res); + tuple_ref(*ret); + it->current = *res; } return 0; } @@ -199,28 +295,31 @@ tree_iterator_prev(struct iterator *iterator, struct tuple **ret) static int tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret) { - struct tree_iterator *it = tree_iterator(iterator); - assert(it->current_tuple != NULL); - struct tuple **check = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); - if (check == NULL || *check != it->current_tuple) + struct tree_iterator *it = tree_iterator_cast(iterator); + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); + memtx_tree_elem *check = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + if (check == NULL || + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) { it->tree_iterator = - memtx_tree_upper_bound_elem(it->tree, it->current_tuple, - NULL); - else + memtx_tree_upper_bound_elem(it->tree, it->current, NULL); + } else { memtx_tree_iterator_next(it->tree, &it->tree_iterator); - tuple_unref(it->current_tuple); - it->current_tuple = NULL; - struct tuple **res = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); + } + tuple_unref(MEMTX_TREE_ELEM_GET(&it->current)); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); /* Use user key def to save a few loops. */ - if (!res || memtx_tree_compare_key(*res, &it->key_data, - it->index_def->key_def) != 0) { + if (!res || + MEMTX_TREE_ELEM_WITH_KEY_CMP(res, &it->key_data, + it->index_def->key_def) != 0) { iterator->next = tree_iterator_dummie; + memset(&it->current, 0, sizeof(it->current)); *ret = NULL; } else { - *ret = it->current_tuple = *res; - tuple_ref(it->current_tuple); + *ret = MEMTX_TREE_ELEM_GET(res); + tuple_ref(*ret); + it->current = *res; } return 0; } @@ -228,27 +327,30 @@ tree_iterator_next_equal(struct iterator *iterator, struct tuple **ret) static int tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret) { - struct tree_iterator *it = tree_iterator(iterator); - assert(it->current_tuple != NULL); - struct tuple **check = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); - if (check == NULL || *check != it->current_tuple) + struct tree_iterator *it = tree_iterator_cast(iterator); + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); + memtx_tree_elem *check = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); + if (check == NULL || + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) { it->tree_iterator = - memtx_tree_lower_bound_elem(it->tree, it->current_tuple, - NULL); + memtx_tree_lower_bound_elem(it->tree, it->current, NULL); + } memtx_tree_iterator_prev(it->tree, &it->tree_iterator); - tuple_unref(it->current_tuple); - it->current_tuple = NULL; - struct tuple **res = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); + tuple_unref(MEMTX_TREE_ELEM_GET(&it->current)); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); /* Use user key def to save a few loops. */ - if (!res || memtx_tree_compare_key(*res, &it->key_data, - it->index_def->key_def) != 0) { + if (!res || + MEMTX_TREE_ELEM_WITH_KEY_CMP(res, &it->key_data, + it->index_def->key_def) != 0) { iterator->next = tree_iterator_dummie; + memset(&it->current, 0, sizeof(it->current)); *ret = NULL; } else { - *ret = it->current_tuple = *res; - tuple_ref(it->current_tuple); + *ret = MEMTX_TREE_ELEM_GET(res); + tuple_ref(*ret); + it->current = *res; } return 0; } @@ -256,7 +358,7 @@ tree_iterator_prev_equal(struct iterator *iterator, struct tuple **ret) static void tree_iterator_set_next_method(struct tree_iterator *it) { - assert(it->current_tuple != NULL); + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); switch (it->type) { case ITER_EQ: it->base.next = tree_iterator_next_equal; @@ -285,13 +387,15 @@ static int tree_iterator_start(struct iterator *iterator, struct tuple **ret) { *ret = NULL; - struct tree_iterator *it = tree_iterator(iterator); + struct tree_iterator *it = tree_iterator_cast(iterator); it->base.next = tree_iterator_dummie; const struct memtx_tree *tree = it->tree; enum iterator_type type = it->type; bool exact = false; - assert(it->current_tuple == NULL); - if (it->key_data.key == 0) { + assert(MEMTX_TREE_ELEM_GET(&it->current) == NULL); + uint32_t part_count; + const char *key = MEMTX_TREE_KEY_GET(&it->key_data, &part_count); + if (key == NULL) { if (iterator_type_is_reverse(it->type)) it->tree_iterator = memtx_tree_iterator_last(tree); else @@ -327,12 +431,13 @@ tree_iterator_start(struct iterator *iterator, struct tuple **ret) } } - struct tuple **res = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); if (!res) return 0; - *ret = it->current_tuple = *res; - tuple_ref(it->current_tuple); + *ret = MEMTX_TREE_ELEM_GET(res); + tuple_ref(*ret); + it->current = *res; tree_iterator_set_next_method(it); return 0; } @@ -386,7 +491,8 @@ memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done) unsigned int loops = 0; while (!memtx_tree_iterator_is_invalid(itr)) { - struct tuple *tuple = *memtx_tree_iterator_get_elem(tree, itr); + memtx_tree_elem *res = memtx_tree_iterator_get_elem(tree, itr); + struct tuple *tuple = MEMTX_TREE_ELEM_GET(res);; memtx_tree_iterator_next(tree, itr); tuple_unref(tuple); if (++loops >= YIELD_LOOPS) { @@ -466,8 +572,8 @@ static int memtx_tree_index_random(struct index *base, uint32_t rnd, struct tuple **result) { struct memtx_tree_index *index = (struct memtx_tree_index *)base; - struct tuple **res = memtx_tree_random(&index->tree, rnd); - *result = res != NULL ? *res : NULL; + memtx_tree_elem *res = memtx_tree_random(&index->tree, rnd); + *result = res != NULL ? MEMTX_TREE_ELEM_GET(res) : NULL; return 0; } @@ -487,26 +593,50 @@ memtx_tree_index_get(struct index *base, const char *key, assert(base->def->opts.is_unique && part_count == base->def->key_def->part_count); struct memtx_tree_index *index = (struct memtx_tree_index *)base; - struct memtx_tree_key_data key_data; - key_data.key = key; - key_data.part_count = part_count; - struct tuple **res = memtx_tree_find(&index->tree, &key_data); - *result = res != NULL ? *res : NULL; + memtx_tree_key key_data; + struct key_def *cmp_def = memtx_tree_index_cmp_def(index); + MEMTX_TREE_KEY_SET(&key_data, key, part_count, cmp_def); + memtx_tree_elem *res = memtx_tree_find(&index->tree, &key_data); + *result = res != NULL ? MEMTX_TREE_ELEM_GET(res) : NULL; return 0; } +static int +memtx_tree_index_insert_tuple(struct index *base, struct tuple *tuple, + struct tuple **replaced) +{ + struct memtx_tree_index *index = (struct memtx_tree_index *)base; + memtx_tree_elem data; + MEMTX_TREE_ELEM_SET(&data, tuple, index->tree.arg); + memtx_tree_elem data_replaced; + memset(&data_replaced, 0, sizeof(data_replaced)); + int rc = memtx_tree_insert(&index->tree, data, &data_replaced); + if (replaced != NULL) + *replaced = MEMTX_TREE_ELEM_GET(&data_replaced); + return rc; +} + +static void +memtx_tree_index_delete_tuple(struct index *base, struct tuple *tuple) +{ + struct memtx_tree_index *index = (struct memtx_tree_index *)base; + memtx_tree_elem data; + MEMTX_TREE_ELEM_SET(&data, tuple, index->tree.arg); + memtx_tree_delete(&index->tree, data); +} + static int memtx_tree_index_replace(struct index *base, struct tuple *old_tuple, struct tuple *new_tuple, enum dup_replace_mode mode, struct tuple **result) { - struct memtx_tree_index *index = (struct memtx_tree_index *)base; if (new_tuple) { struct tuple *dup_tuple = NULL; /* Try to optimistically replace the new_tuple. */ - int tree_res = memtx_tree_insert(&index->tree, - new_tuple, &dup_tuple); + int tree_res = + memtx_tree_index_insert_tuple(base, new_tuple, + &dup_tuple); if (tree_res) { diag_set(OutOfMemory, MEMTX_EXTENT_SIZE, "memtx_tree_index", "replace"); @@ -516,9 +646,9 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple, uint32_t errcode = replace_check_dup(old_tuple, dup_tuple, mode); if (errcode) { - memtx_tree_delete(&index->tree, new_tuple); + memtx_tree_index_delete_tuple(base, new_tuple); if (dup_tuple) - memtx_tree_insert(&index->tree, dup_tuple, 0); + memtx_tree_index_insert_tuple(base, dup_tuple, 0); struct space *sp = space_cache_find(base->def->space_id); if (sp != NULL) diag_set(ClientError, errcode, base->def->name, @@ -530,9 +660,8 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple, return 0; } } - if (old_tuple) { - memtx_tree_delete(&index->tree, old_tuple); - } + if (old_tuple) + memtx_tree_index_delete_tuple(base, old_tuple); *result = old_tuple; return 0; } @@ -571,12 +700,12 @@ memtx_tree_index_create_iterator(struct index *base, enum iterator_type type, it->base.next = tree_iterator_start; it->base.free = tree_iterator_free; it->type = type; - it->key_data.key = key; - it->key_data.part_count = part_count; + struct key_def *cmp_def = memtx_tree_index_cmp_def(index); + MEMTX_TREE_KEY_SET(&it->key_data, key, part_count, cmp_def); it->index_def = base->def; it->tree = &index->tree; it->tree_iterator = memtx_tree_invalid_iterator(); - it->current_tuple = NULL; + memset(&it->current, 0, sizeof(it->current)); return (struct iterator *)it; } @@ -594,8 +723,8 @@ memtx_tree_index_reserve(struct index *base, uint32_t size_hint) struct memtx_tree_index *index = (struct memtx_tree_index *)base; if (size_hint < index->build_array_alloc_size) return 0; - struct tuple **tmp = (struct tuple **)realloc(index->build_array, - size_hint * sizeof(*tmp)); + memtx_tree_elem *tmp = + realloc(index->build_array, size_hint * sizeof(*tmp)); if (tmp == NULL) { diag_set(OutOfMemory, size_hint * sizeof(*tmp), "memtx_tree_index", "reserve"); @@ -611,20 +740,20 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple) { struct memtx_tree_index *index = (struct memtx_tree_index *)base; if (index->build_array == NULL) { - index->build_array = (struct tuple **)malloc(MEMTX_EXTENT_SIZE); + index->build_array = (memtx_tree_elem *)malloc(MEMTX_EXTENT_SIZE); if (index->build_array == NULL) { diag_set(OutOfMemory, MEMTX_EXTENT_SIZE, "memtx_tree_index", "build_next"); return -1; } index->build_array_alloc_size = - MEMTX_EXTENT_SIZE / sizeof(struct tuple*); + MEMTX_EXTENT_SIZE / sizeof(index->build_array[0]); } assert(index->build_array_size <= index->build_array_alloc_size); if (index->build_array_size == index->build_array_alloc_size) { index->build_array_alloc_size = index->build_array_alloc_size + index->build_array_alloc_size / 2; - struct tuple **tmp = (struct tuple **) + memtx_tree_elem *tmp = realloc(index->build_array, index->build_array_alloc_size * sizeof(*tmp)); if (tmp == NULL) { @@ -634,7 +763,8 @@ memtx_tree_index_build_next(struct index *base, struct tuple *tuple) } index->build_array = tmp; } - index->build_array[index->build_array_size++] = tuple; + MEMTX_TREE_ELEM_SET(&index->build_array[index->build_array_size++], + tuple, memtx_tree_index_cmp_def(index)); return 0; } @@ -644,10 +774,9 @@ memtx_tree_index_end_build(struct index *base) struct memtx_tree_index *index = (struct memtx_tree_index *)base; struct key_def *cmp_def = memtx_tree_index_cmp_def(index); qsort_arg(index->build_array, index->build_array_size, - sizeof(struct tuple *), - memtx_tree_qcompare, cmp_def); + sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def); memtx_tree_build(&index->tree, index->build_array, - index->build_array_size); + index->build_array_size); free(index->build_array); index->build_array = NULL; @@ -678,12 +807,12 @@ tree_snapshot_iterator_next(struct snapshot_iterator *iterator, uint32_t *size) assert(iterator->free == tree_snapshot_iterator_free); struct tree_snapshot_iterator *it = (struct tree_snapshot_iterator *)iterator; - struct tuple **res = memtx_tree_iterator_get_elem(it->tree, - &it->tree_iterator); + memtx_tree_elem *res = + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); if (res == NULL) return NULL; memtx_tree_iterator_next(it->tree, &it->tree_iterator); - return tuple_data_range(*res, size); + return tuple_data_range(MEMTX_TREE_ELEM_GET(res), size); } /** @@ -746,7 +875,7 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) { if (!mempool_is_initialized(&memtx->tree_iterator_pool)) { mempool_create(&memtx->tree_iterator_pool, cord_slab_cache(), - sizeof(struct tree_iterator)); + MEMTX_TREE_ITERATOR_SIZE); } struct memtx_tree_index *index = @@ -767,3 +896,74 @@ memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) memtx_index_extent_free, memtx); return &index->base; } + +#undef _tree_api_name +#undef memtx_tree +#undef memtx_tree_iterator +#undef memtx_tree_iterator_is_invalid +#undef memtx_tree_iterator_first +#undef memtx_tree_iterator_last +#undef memtx_tree_iterator_get_elem +#undef memtx_tree_iterator_next +#undef memtx_tree_iterator_prev +#undef memtx_tree_iterator_freeze +#undef memtx_tree_iterator_destroy +#undef memtx_tree_create +#undef memtx_tree_build +#undef memtx_tree_destroy +#undef memtx_tree_find +#undef memtx_tree_insert +#undef memtx_tree_delete +#undef memtx_tree_size +#undef memtx_tree_mem_used +#undef memtx_tree_random +#undef memtx_tree_invalid_iterator +#undef memtx_tree_lower_bound +#undef memtx_tree_upper_bound +#undef memtx_tree_lower_bound_elem +#undef memtx_tree_upper_bound_elem + +#undef _api_name +#undef memtx_tree_index +#undef memtx_tree_qcompare +#undef tree_iterator +#undef tree_iterator_free +#undef tree_iterator_cast +#undef tree_iterator_dummie +#undef tree_iterator_next +#undef tree_iterator_prev +#undef tree_iterator_next_equal +#undef tree_iterator_prev_equal +#undef tree_iterator_set_next_method +#undef tree_iterator_start +#undef memtx_tree_index_cmp_def +#undef memtx_tree_index_free +#undef memtx_tree_index_gc_run +#undef memtx_tree_index_gc_free +#undef memtx_tree_index_gc_vtab +#undef memtx_tree_index_destroy +#undef memtx_tree_index_update_def +#undef memtx_tree_index_depends_on_pk +#undef memtx_tree_index_size +#undef memtx_tree_index_bsize +#undef memtx_tree_index_random +#undef memtx_tree_index_count +#undef memtx_tree_index_get +#undef memtx_tree_index_insert_tuple +#undef memtx_tree_index_delete_tuple +#undef memtx_tree_index_replace +#undef memtx_tree_index_create_iterator +#undef memtx_tree_index_begin_build +#undef memtx_tree_index_build_next +#undef memtx_tree_index_reserve +#undef memtx_tree_index_end_build +#undef tree_snapshot_iterator +#undef tree_snapshot_iterator_free +#undef tree_snapshot_iterator_next +#undef tree_index_create_snapshot_iterator +#undef memtx_tree_index_vtab +#undef memtx_tree_index_new + +#if defined(__cplusplus) +} /* extern "C" */ +#endif /* defined(__cplusplus) */ diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c new file mode 100644 index 000000000..03e0e0ed7 --- /dev/null +++ b/src/box/memtx_tree_decl.c @@ -0,0 +1,84 @@ +/* + * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * 1. Redistributions of source code must retain the above + * copyright notice, this list of conditions and the + * following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL + * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR + * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +#include <stdbool.h> +#include <stdint.h> +#include "tuple_compare.h" +#include "memtx_tree.h" + +/* {{{ Memtx tree of tuples class. ******************************/ + +/** Struct that is used as a key in BPS tree definition. */ +struct memtx_tuple_tree_key_data { + /** Sequence of msgpacked search fields. */ + const char *key; + /** Number of msgpacked search fields. */ + uint32_t part_count; +}; + +#define MEMTX_TREE_NAME memtx_tuple_tree +#define memtx_tree_elem struct tuple * +#define memtx_tree_key struct memtx_tuple_tree_key_data +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ + tuple_compare(*elem_a_ptr, *elem_b_ptr, key_def) +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ + tuple_compare_with_key(*elem_ptr, (key_ptr)->key, \ + (key_ptr)->part_count, key_def) +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ + ({(void)key_def; *elem_ptr = tuple;}) +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ + ({(void)key_def; (key_ptr)->key = key_val; \ + (key_ptr)->part_count = part_count_val;}) +#define MEMTX_TREE_ELEM_GET(elem_ptr) (*(elem_ptr)) +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) + +#include "memtx_tree.c" + +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_KEY_GET +#undef MEMTX_TREE_ELEM_GET +#undef MEMTX_TREE_KEY_SET +#undef MEMTX_TREE_ELEM_SET +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP +#undef MEMTX_TREE_ELEM_CMP +#undef MEMTX_TREE_ELEM_EQUAL +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_NAME + +/* }}} */ + +struct index * +memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) +{ + return memtx_tuple_tree_index_new(memtx, def); +} -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes 2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov @ 2019-02-21 15:01 ` Vladimir Davydov 0 siblings, 0 replies; 13+ messages in thread From: Vladimir Davydov @ 2019-02-21 15:01 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches, kostja On Wed, Feb 13, 2019 at 12:32:26PM +0300, Kirill Shcherbatov wrote: > Reworked memtx_tree class to use arbitrary containers as a tree > nodes. This makes possible to implement tuple hints in subsequent > patches. > > The memtx_tree.c is currently used in a header manner. This is to > ensure that functional changes in the patch do not mix with > refactoring, that will be finished in the next commit. > > Needed for #3961 > --- > src/box/CMakeLists.txt | 2 +- > src/box/memtx_tree.c | 498 ++++++++++++++++++++++++++------------ > src/box/memtx_tree_decl.c | 84 +++++++ > 3 files changed, 434 insertions(+), 150 deletions(-) > create mode 100644 src/box/memtx_tree_decl.c > > diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt > index 5521e489e..dc8cc2cd5 100644 > --- a/src/box/CMakeLists.txt > +++ b/src/box/CMakeLists.txt > @@ -64,7 +64,7 @@ add_library(box STATIC > index_def.c > iterator_type.c > memtx_hash.c > - memtx_tree.c > + memtx_tree_decl.c > memtx_rtree.c > memtx_bitset.c > engine.c > diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c > index 2e8adb682..0874b7dc8 100644 > --- a/src/box/memtx_tree.c > +++ b/src/box/memtx_tree.c > @@ -1,5 +1,5 @@ > /* > - * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file. > + * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file. > * > * Redistribution and use in source and binary forms, with or > * without modification, are permitted provided that the following > @@ -28,72 +28,156 @@ > * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > * SUCH DAMAGE. > */ > -#include "memtx_tree.h" > -#include "memtx_engine.h" > -#include "space.h" > -#include "schema.h" /* space_cache_find() */ > -#include "errinj.h" > -#include "memory.h" > -#include "fiber.h" > -#include "tuple.h" > -#include <third_party/qsort_arg.h> Why touch header inclusions? > + > +#if defined(__cplusplus) > +extern "C" { > +#endif /* defined(__cplusplus) */ > + This isn't needed in a header like this. > #include <small/mempool.h> > +#include <third_party/qsort_arg.h> > +#include "memtx_engine.h" > +#include "schema.h" > > -/** > - * Struct that is used as a key in BPS tree definition. > - */ > -struct memtx_tree_key_data { > - /** Sequence of msgpacked search fields. */ > - const char *key; > - /** Number of msgpacked search fields. */ > - uint32_t part_count; > -}; > +#ifndef MEMTX_TREE_NAME > +#error "MEMTX_TREE_NAME must be defined" > +#endif > + > +#ifndef memtx_tree_elem > +#error "memtx_tree_elem must be defined" > +#endif > + > +#ifndef memtx_tree_key > +#error "memtx_tree_key must be defined" > +#endif Let's please use _t suffix for types (memtx_tree_elem_t, memtx_tree_key_t). > + > +#ifndef MEMTX_TREE_ELEM_CMP > +#error "MEMTX_TREE_ELEM_CMP must be defined" > +#endif > + > +#ifndef MEMTX_TREE_ELEM_WITH_KEY_CMP > +#error "MEMTX_TREE_ELEM_WITH_KEY_CMP must be defined" > +#endif May be, call these MEMTX_TREE_COMPARE and MEMTX_TREE_COMPARE_KEY to match BPS tree macros? > + > +#ifndef MEMTX_TREE_ELEM_SET > +#error "MEMTX_TREE_ELEM_SET must be defined" > +#endif > + > +#ifndef MEMTX_TREE_KEY_SET > +#error "MEMTX_TREE_KEY_SET must be defined" > +#endif > + > +#ifndef MEMTX_TREE_ELEM_GET > +#error "MEMTX_TREE_ELEM_GET must be defined" > +#endif > + > +#ifndef MEMTX_TREE_KEY_GET > +#error "MEMTX_TREE_KEY_GET must be defined" > +#endif Please add a comment to each of the macros describing what it is supposed to do. > > /** > - * BPS tree element vs key comparator. > - * Defined in header in order to allow compiler to inline it. > - * @param tuple - tuple to compare. > - * @param key_data - key to compare with. > - * @param def - key definition. > - * @retval 0 if tuple == key in terms of def. > - * @retval <0 if tuple < key in terms of def. > - * @retval >0 if tuple > key in terms of def. > + * The size of the biggest memtx tree iterator. Used with > + * mempool_create. This is the size of the block that will be > + * allocated for each iterator. > */ > -static int > -memtx_tree_compare_key(const struct tuple *tuple, > - const struct memtx_tree_key_data *key_data, > - struct key_def *def) > -{ > - return tuple_compare_with_key(tuple, key_data->key, > - key_data->part_count, def); > -} > +#define MEMTX_TREE_ITERATOR_SIZE (152) Take a look at struct memtx_engine: /** Memory pool for tree index iterator. */ struct mempool tree_iterator_pool; /** Memory pool for rtree index iterator. */ struct mempool rtree_iterator_pool; /** Memory pool for hash index iterator. */ struct mempool hash_iterator_pool; /** Memory pool for bitset index iterator. */ struct mempool bitset_iterator_pool; This looks ugly. Let's use this trick with static iterator size for all index types. Please do it in a separate patch. > > -#define BPS_TREE_NAME memtx_tree > +#define bps_tree_elem_t memtx_tree_elem > +#define bps_tree_key_t memtx_tree_key * > +#define bps_tree_arg_t struct key_def * > +#define BPS_TREE_NAME CONCAT3(MEMTX_TREE_NAME, _, tree) > #define BPS_TREE_BLOCK_SIZE (512) > #define BPS_TREE_EXTENT_SIZE MEMTX_EXTENT_SIZE > -#define BPS_TREE_COMPARE(a, b, arg) tuple_compare(a, b, arg) > -#define BPS_TREE_COMPARE_KEY(a, b, arg) memtx_tree_compare_key(a, b, arg) > -#define bps_tree_elem_t struct tuple * > -#define bps_tree_key_t struct memtx_tree_key_data * > -#define bps_tree_arg_t struct key_def * > +#define BPS_TREE_COMPARE(a, b, arg) MEMTX_TREE_ELEM_CMP(&a, &b, arg) > +#define BPS_TREE_COMPARE_KEY(a, b, arg) MEMTX_TREE_ELEM_WITH_KEY_CMP(&a, b, arg) > +#define BPS_TREE_NO_DEBUG > > #include "salad/bps_tree.h" > > +#undef bps_tree_elem_t > +#undef bps_tree_key_t > +#undef bps_tree_arg_t > #undef BPS_TREE_NAME > #undef BPS_TREE_BLOCK_SIZE > #undef BPS_TREE_EXTENT_SIZE > #undef BPS_TREE_COMPARE > #undef BPS_TREE_COMPARE_KEY > -#undef bps_tree_elem_t > -#undef bps_tree_key_t > -#undef bps_tree_arg_t > +#undef BPS_TREE_NO_DEBUG > + > +#define memtx_tree CONCAT3(MEMTX_TREE_NAME, _, tree) > +#define _tree_api_name(postfix) CONCAT5(MEMTX_TREE_NAME, _, tree, _, postfix) Why not _api_name? > +#define memtx_tree_iterator _tree_api_name(iterator) > +#define memtx_tree_iterator_is_invalid _tree_api_name(iterator_is_invalid) > +#define memtx_tree_iterator_first _tree_api_name(iterator_first) > +#define memtx_tree_iterator_last _tree_api_name(iterator_last) > +#define memtx_tree_iterator_get_elem _tree_api_name(iterator_get_elem) > +#define memtx_tree_iterator_next _tree_api_name(iterator_next) > +#define memtx_tree_iterator_prev _tree_api_name(iterator_prev) > +#define memtx_tree_iterator_freeze _tree_api_name(iterator_freeze) > +#define memtx_tree_iterator_destroy _tree_api_name(iterator_destroy) > +#define memtx_tree_create _tree_api_name(create) > +#define memtx_tree_build _tree_api_name(build) > +#define memtx_tree_destroy _tree_api_name(destroy) > +#define memtx_tree_find _tree_api_name(find) > +#define memtx_tree_insert _tree_api_name(insert) > +#define memtx_tree_delete _tree_api_name(delete) > +#define memtx_tree_size _tree_api_name(size) > +#define memtx_tree_mem_used _tree_api_name(mem_used) > +#define memtx_tree_random _tree_api_name(random) > +#define memtx_tree_invalid_iterator _tree_api_name(invalid_iterator) > +#define memtx_tree_lower_bound _tree_api_name(lower_bound) > +#define memtx_tree_upper_bound _tree_api_name(upper_bound) > +#define memtx_tree_lower_bound_elem _tree_api_name(lower_bound_elem) > +#define memtx_tree_upper_bound_elem _tree_api_name(upper_bound_elem) > + > +#undef _api_name BPS tree should undef all macros it defines on its own. Please fix it in a separate patch. > +#define _api_name(postfix) CONCAT3(MEMTX_TREE_NAME, _, postfix) > +#define memtx_tree_index _api_name(index) > +#define memtx_tree_qcompare _api_name(qcompare) > +#define tree_iterator _api_name(iterator) > +#define tree_iterator_free _api_name(iterator_free) > +#define tree_iterator_cast _api_name(iterator_cast) > +#define tree_iterator_dummie _api_name(iterator_dummie) > +#define tree_iterator_next _api_name(iterator_next) > +#define tree_iterator_prev _api_name(iterator_prev) > +#define tree_iterator_next_equal _api_name(iterator_next_equal) > +#define tree_iterator_prev_equal _api_name(iterator_prev_equal) > +#define tree_iterator_set_next_method _api_name(iterator_set_next_method) > +#define tree_iterator_start _api_name(iterator_start) > +#define memtx_tree_index_cmp_def _api_name(index_cmp_def) > +#define memtx_tree_index_free _api_name(index_free) > +#define memtx_tree_index_gc_run _api_name(index_gc_run) > +#define memtx_tree_index_gc_free _api_name(index_gc_free) > +#define memtx_tree_index_gc_vtab _api_name(index_gc_vtab) > +#define memtx_tree_index_destroy _api_name(index_destroy) > +#define memtx_tree_index_update_def _api_name(index_update_def) > +#define memtx_tree_index_depends_on_pk _api_name(index_depends_on_pk) > +#define memtx_tree_index_size _api_name(index_size) > +#define memtx_tree_index_bsize _api_name(index_bsize) > +#define memtx_tree_index_random _api_name(index_random) > +#define memtx_tree_index_count _api_name(index_count) > +#define memtx_tree_index_get _api_name(index_get) > +#define memtx_tree_index_insert_tuple _api_name(index_insert_tuple) > +#define memtx_tree_index_delete_tuple _api_name(index_delete_tuple) > +#define memtx_tree_index_replace _api_name(index_replace) > +#define memtx_tree_index_create_iterator _api_name(index_create_iterator) > +#define memtx_tree_index_begin_build _api_name(index_begin_build) > +#define memtx_tree_index_build_next _api_name(index_build_next) > +#define memtx_tree_index_reserve _api_name(index_reserve) > +#define memtx_tree_index_end_build _api_name(index_end_build) > +#define tree_snapshot_iterator _api_name(snapshot_iterator) > +#define tree_snapshot_iterator_free _api_name(snapshot_iterator_free) > +#define tree_snapshot_iterator_next _api_name(snapshot_iterator_next) > +#define memtx_tree_index_create_snapshot_iterator\ > + _api_name(index_create_snapshot_iterator) > +#define memtx_tree_index_vtab _api_name(index_vtab) > +#define memtx_tree_index_new _api_name(index_new) I'd undef _api_name right here, because we don't need it anywhere else. > > struct memtx_tree_index { > struct index base; > - struct memtx_tree tree; > - struct tuple **build_array; > + memtx_tree_elem *build_array; > size_t build_array_size, build_array_alloc_size; > struct memtx_gc_task gc_task; > + struct memtx_tree tree; Nit: pointless change (moving 'tree' member). > struct memtx_tree_iterator gc_iterator; > }; > > @@ -102,8 +186,8 @@ struct memtx_tree_index { > static int > memtx_tree_qcompare(const void* a, const void *b, void *c) > { > - return tuple_compare(*(struct tuple **)a, > - *(struct tuple **)b, (struct key_def *)c); > + return MEMTX_TREE_ELEM_CMP((memtx_tree_elem *)a, > + (memtx_tree_elem *)b, c); > } > > /* {{{ MemtxTree Iterators ****************************************/ > @@ -113,17 +197,21 @@ struct tree_iterator { > struct index_def *index_def; > struct memtx_tree_iterator tree_iterator; > enum iterator_type type; > - struct memtx_tree_key_data key_data; > - struct tuple *current_tuple; > + memtx_tree_key key_data; > + memtx_tree_elem current; > /** Memory pool the iterator was allocated from. */ > struct mempool *pool; > }; > > +static_assert(sizeof(struct tree_iterator) <= MEMTX_TREE_ITERATOR_SIZE, > + "tree_iterator must be less or equal than " > + "MEMTX_TREE_ITERATOR_SIZE"); > + > static void > tree_iterator_free(struct iterator *iterator); > > static inline struct tree_iterator * > -tree_iterator(struct iterator *it) > +tree_iterator_cast(struct iterator *it) > { > assert(it->free == tree_iterator_free); > return (struct tree_iterator *) it; > @@ -132,9 +220,10 @@ tree_iterator(struct iterator *it) > static void > tree_iterator_free(struct iterator *iterator) > { > - struct tree_iterator *it = tree_iterator(iterator); > - if (it->current_tuple != NULL) > - tuple_unref(it->current_tuple); > + struct tree_iterator *it = tree_iterator_cast(iterator); > + struct tuple *tuple = MEMTX_TREE_ELEM_GET(&it->current); > + if (tuple != NULL) > + tuple_unref(tuple); > mempool_free(it->pool, it); > } > > @@ -149,25 +238,28 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret) > static int > tree_iterator_next(struct iterator *iterator, struct tuple **ret) > { > - struct tuple **res; > - struct tree_iterator *it = tree_iterator(iterator); > - assert(it->current_tuple != NULL); > - struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); > - if (check == NULL || *check != it->current_tuple) > + struct tree_iterator *it = tree_iterator_cast(iterator); > + assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL); > + memtx_tree_elem *check = > + memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator); > + if (check == NULL || > + MEMTX_TREE_ELEM_GET(check) != MEMTX_TREE_ELEM_GET(&it->current)) { AFAIU this check isn't quite correct: we want to make sure that it->current and check refer to the same tree element. So in case of a multikey index it isn't enough to just check the tuples they refer to - you also need to check the key offsets. > diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c > new file mode 100644 > index 000000000..03e0e0ed7 > --- /dev/null > +++ b/src/box/memtx_tree_decl.c > @@ -0,0 +1,84 @@ > +/* > + * Copyright 2010-2019, Tarantool AUTHORS, please see AUTHORS file. > + * > + * Redistribution and use in source and binary forms, with or > + * without modification, are permitted provided that the following > + * conditions are met: > + * > + * 1. Redistributions of source code must retain the above > + * copyright notice, this list of conditions and the > + * following disclaimer. > + * > + * 2. Redistributions in binary form must reproduce the above > + * copyright notice, this list of conditions and the following > + * disclaimer in the documentation and/or other materials > + * provided with the distribution. > + * > + * THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND > + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED > + * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL > + * <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, > + * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL > + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF > + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR > + * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF > + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF > + * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF > + * SUCH DAMAGE. > + */ > +#include <stdbool.h> > +#include <stdint.h> > +#include "tuple_compare.h" > +#include "memtx_tree.h" > + > +/* {{{ Memtx tree of tuples class. ******************************/ > + > +/** Struct that is used as a key in BPS tree definition. */ > +struct memtx_tuple_tree_key_data { > + /** Sequence of msgpacked search fields. */ > + const char *key; > + /** Number of msgpacked search fields. */ > + uint32_t part_count; > +}; > + > +#define MEMTX_TREE_NAME memtx_tuple_tree I don't quite like the name, because all memtx indexes store tuples, eventually. May be, memtx_simple_tree or memtx_basic_tree? > +#define memtx_tree_elem struct tuple * > +#define memtx_tree_key struct memtx_tuple_tree_key_data > +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ > + tuple_compare(*elem_a_ptr, *elem_b_ptr, key_def) > +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ > + tuple_compare_with_key(*elem_ptr, (key_ptr)->key, \ > + (key_ptr)->part_count, key_def) > +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ > + ({(void)key_def; *elem_ptr = tuple;}) > +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ > + ({(void)key_def; (key_ptr)->key = key_val; \ > + (key_ptr)->part_count = part_count_val;}) > +#define MEMTX_TREE_ELEM_GET(elem_ptr) (*(elem_ptr)) > +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ > + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) > + > +#include "memtx_tree.c" > + > +#undef memtx_tree_key > +#undef memtx_tree_elem > +#undef MEMTX_TREE_KEY_GET > +#undef MEMTX_TREE_ELEM_GET > +#undef MEMTX_TREE_KEY_SET > +#undef MEMTX_TREE_ELEM_SET > +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP > +#undef MEMTX_TREE_ELEM_CMP > +#undef MEMTX_TREE_ELEM_EQUAL This one is never defined. > +#undef memtx_tree_key > +#undef memtx_tree_elem You undef those twice. > +#undef MEMTX_TREE_NAME > + > +/* }}} */ > + > +struct index * > +memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) > +{ > + return memtx_tuple_tree_index_new(memtx, def); > +} ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h 2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov @ 2019-02-13 9:32 ` Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov 3 siblings, 0 replies; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Kirill Shcherbatov File meta_tree.c that implements the template class memtx_tree, renamed to memes_tree_impl.h due to the fact that the inclusion of code in header files is more common. Needed for #3961 --- src/box/memtx_tree_decl.c | 2 +- src/box/{memtx_tree.c => memtx_tree_impl.h} | 0 2 files changed, 1 insertion(+), 1 deletion(-) rename src/box/{memtx_tree.c => memtx_tree_impl.h} (100%) diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c index 03e0e0ed7..084a0594f 100644 --- a/src/box/memtx_tree_decl.c +++ b/src/box/memtx_tree_decl.c @@ -60,7 +60,7 @@ struct memtx_tuple_tree_key_data { #define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) -#include "memtx_tree.c" +#include "memtx_tree_impl.h" #undef memtx_tree_key #undef memtx_tree_elem diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree_impl.h similarity index 100% rename from src/box/memtx_tree.c rename to src/box/memtx_tree_impl.h -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov ` (2 preceding siblings ...) 2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov @ 2019-02-13 9:32 ` Kirill Shcherbatov 2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov 2019-02-15 18:34 ` Kirill Shcherbatov 3 siblings, 2 replies; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-13 9:32 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Alexandr Lyapunov From: Alexandr Lyapunov <aleks@tarantool.org> Implement functions for retrieving tuple hints for a particular key_def. Hint is an integer that can be used for tuple comparison optimization: if a hint of one tuple is less than a hint of another then the first tuple is definitely less than the second; only if hints are equal tuple_compare must be called for getting comparison result. Hints are calculated using only the first part of key_def. Hints are only useful when: * they are precalculated and stored along with the tuple; calculation is not cheap (cheaper than tuple_compare btw) but precalculated hints allow to compare tuples without even fetching tuple data. * first part of key_def is 'string'(for now) * since hint is calculated using only the first part of key_def (and only first several characters if it is a string) this part must be different with high probability for every tuple pair. Part of #3961 --- src/box/key_def.c | 1 + src/box/key_def.h | 44 ++++++++++++++ src/box/memtx_tree_decl.c | 123 ++++++++++++++++++++++++++++++++++++++ src/box/tuple_compare.cc | 101 +++++++++++++++++++++++++++++++ src/box/tuple_compare.h | 7 +++ src/coll.c | 45 ++++++++++++++ src/coll.h | 4 ++ 7 files changed, 325 insertions(+) diff --git a/src/box/key_def.c b/src/box/key_def.c index 9411ade39..ceca1ebee 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def) def->tuple_compare_with_key = tuple_compare_with_key_create(def); tuple_hash_func_set(def); tuple_extract_key_set(def); + tuple_hint_set(def); } static void diff --git a/src/box/key_def.h b/src/box/key_def.h index bf3e63b6d..a2a0bbecb 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -153,6 +153,13 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple, typedef uint32_t (*key_hash_t)(const char *key, struct key_def *key_def); +/** @copydoc tuple_hint() */ +typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple, + struct key_def *key_def); + +/** @copydoc key_hint() */ +typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def); + /* Definition of a multipart key. */ struct key_def { /** @see tuple_compare() */ @@ -167,6 +174,10 @@ struct key_def { tuple_hash_t tuple_hash; /** @see key_hash() */ key_hash_t key_hash; + /** @see tuple_hint() */ + tuple_hint_t tuple_hint; + /** @see key_hint() */ + key_hint_t key_hint; /** * Minimal part count which always is unique. For example, * if a secondary index is unique, then @@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key, return key_def->tuple_compare_with_key(tuple, key, part_count, key_def); } +/** + * Get a comparison hint of a tuple. + * Hint is such a function h(tuple) in terms of particular key_def that + * has follows rules: + * if h(t1) < h(t2) then t1 < t2; + * if h(t1) > h(t2) then t1 > t2; + * if t1 == t2 then h(t1) == h(t2); + * These rules means that instead of direct tuple vs tuple (or tuple vs key) + * comparison one may compare theirs hints first; and only if theirs hints + * are equal compare the tuples themselves. + * @param tuple - tuple to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +tuple_hint(const struct tuple *tuple, struct key_def *key_def) +{ + return key_def->tuple_hint(tuple, key_def); +} + +/** + * Get a comparison hint of a key. + * @See tuple_hint for hint term definition. + * @param key - key to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +key_hint(const char *key, struct key_def *key_def) +{ + return key_def->key_hint(key, key_def); +} + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c index 084a0594f..264241832 100644 --- a/src/box/memtx_tree_decl.c +++ b/src/box/memtx_tree_decl.c @@ -77,8 +77,131 @@ struct memtx_tuple_tree_key_data { /* }}} */ +/* {{{ Memtx hinted and hint_only tree class. *******************/ + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. +*/ +struct memtx_hinted_tree_key_data { + /** Sequence of msgpacked search fields. */ + const char *key; + /** Number of msgpacked search fields. */ + uint32_t part_count; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_key_data_set(). + */ + uint64_t hint; +}; + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. + */ +struct memtx_hinted_tree_data { + /** Tuple this node is representing. */ + struct tuple *tuple; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_data_set(). + */ + uint64_t hint; +}; + +/** + * Compare memtx_hinted_tree records. + */ +static int +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_data *b, + struct key_def *key_def) +{ + if (a->hint != b->hint) + return a->hint < b->hint ? -1 : 1; + return tuple_compare(a->tuple, b->tuple, key_def); +} + +/** + * Compare memtx_hinted_tree record with key. + */ +static int +memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_key_data *key, + struct key_def *key_def) +{ + if (a->hint != key->hint) + return a->hint < key->hint ? -1 : 1; + return tuple_compare_with_key(a->tuple, key->key, key->part_count, + key_def); +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree record + * with tuple and recalculate internal hint field. + */ +static void +memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data, + struct tuple *tuple, struct key_def *key_def) +{ + data->tuple = tuple; + data->hint = tuple != NULL ? tuple_hint(tuple, key_def) : 0; +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree key with + * key raw and part count and recalculate internal hint field. + */ +static void +memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data, + const char *key, uint32_t part_count, + struct key_def *key_def) +{ + key_data->key = key; + key_data->part_count = part_count; + key_data->hint = key != NULL && part_count > 0 ? + key_hint(key, key_def) : 0; +} + +#define MEMTX_TREE_NAME memtx_hinted_tree +#define memtx_tree_elem struct memtx_hinted_tree_data +#define memtx_tree_key struct memtx_hinted_tree_key_data +#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \ + ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple) +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ + memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def) +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ + memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def) +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ + memtx_hinted_tree_data_set(elem_ptr, tuple, key_def) +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ + memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \ + key_def) +#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple) +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) + +#include "memtx_tree_impl.h" + +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_KEY_GET +#undef MEMTX_TREE_ELEM_GET +#undef MEMTX_TREE_KEY_SET +#undef MEMTX_TREE_ELEM_SET +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP +#undef MEMTX_TREE_ELEM_CMP +#undef MEMTX_TREE_ELEM_EQUAL +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_NAME + +/* }}} */ + struct index * memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) { + if (def->cmp_def->parts->type == FIELD_TYPE_STRING) + return memtx_hinted_tree_index_new(memtx, def); return memtx_tuple_tree_index_new(memtx, def); } diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index ded802c7d..744901d70 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -1321,4 +1321,105 @@ tuple_compare_with_key_create(const struct key_def *def) compare_with_key_slowpath_funcs[cmp_func_idx]; } +static uint64_t +key_hint_default(const char *key, struct key_def *key_def) +{ + (void)key; + (void)key_def; + return 0; +} + +static uint64_t +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def) +{ + (void)tuple; + (void)key_def; + return 0; +} + +static uint64_t +key_hint_string(const char *key, struct key_def *key_def) +{ + assert(key != NULL); + (void)key_def; + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + uint32_t len; + const unsigned char *str = + (const unsigned char *)mp_decode_str(&key, &len); + uint64_t result = 0; + /* + * Map the sequence of characters in the hint's bytes in + * the reverse order: the first character will be mapped + * in the highest byte of the number, etc. + * One additional bit encodes the presence of the next + * sign. + * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0 + * The sequence constructed in this way provides a + * comparison transitivity of strings no longer than 7 + * bytes. + */ + uint32_t process_len = MIN(len, sizeof(char) - 1); + for (uint32_t i = 0; i < process_len; i++) { + result <<= CHAR_BIT + 1; + result |= UCHAR_MAX + 1; + result |= str[i]; + } + /* + * If the length of the string is less than the 64-bit + * hint can accommodate, the insignificant positions are + * filled with 0. + */ + result <<= (CHAR_BIT + 1) * (sizeof(char) - 1 - process_len); + return result; +} + +static uint64_t +tuple_hint_string(const struct tuple *tuple, struct key_def *key_def) +{ + const char *field = tuple_field_by_part(tuple, key_def->parts); + return field != NULL ? key_hint_string(field, key_def) : 0; +} + +static uint64_t +key_hint_string_coll(const char *key, struct key_def *key_def) +{ + assert(key != NULL); + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + assert(key_def->parts->coll != NULL); + uint32_t len; + const char *str = mp_decode_str(&key, &len); + return key_def->parts->coll->hint(str, len, key_def->parts->coll); +} + +static uint64_t +tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def) +{ + const char *field = tuple_field_by_part(tuple, key_def->parts); + return field != NULL ? key_hint_string_coll(field, key_def) : 0; +} + +void +tuple_hint_set(struct key_def *def) +{ + def->key_hint = key_hint_default; + def->tuple_hint = tuple_hint_default; + if (key_part_is_nullable(def->parts)) + return; + if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) { + def->key_hint = key_hint_string_coll; + def->tuple_hint = tuple_hint_string_coll; + return; + } + switch (def->parts->type) { + case FIELD_TYPE_STRING: + def->key_hint = key_hint_string; + def->tuple_hint = tuple_hint_string; + break; + default: + break; + }; +} + /* }}} tuple_compare_with_key */ diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h index e3a63204f..405460086 100644 --- a/src/box/tuple_compare.h +++ b/src/box/tuple_compare.h @@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def); tuple_compare_with_key_t tuple_compare_with_key_create(const struct key_def *key_def); +/** + * Initialize tuple_hint() and key_hint() functions for the key_def. + * @param key_def key definition to set up. + */ +void +tuple_hint_set(struct key_def *key_def); + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/coll.c b/src/coll.c index 6d9c44dbf..5bb46a94f 100644 --- a/src/coll.c +++ b/src/coll.c @@ -33,6 +33,7 @@ #include "third_party/PMurHash.h" #include "diag.h" #include "assoc.h" +#include "limits.h" #include <unicode/ucol.h> #include <trivia/config.h> @@ -133,6 +134,48 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, return s_len; } +/** Get a compare hint of a string using ICU collation. */ +static uint64_t +coll_icu_hint(const char *s, size_t s_len, struct coll *coll) +{ + UCharIterator itr; + uiter_setUTF8(&itr, s, s_len); + uint8_t buf[7]; + uint32_t state[2] = {0, 0}; + UErrorCode status = U_ZERO_ERROR; + int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf, + sizeof(buf), &status); + assert(got >= 0 && got <= 7); + uint64_t result = 0; + for (int32_t i = 0; i < got; i++) { + result <<= 9; + result |= 0x100; + result |= buf[i]; + } + result <<= 9 * (7 - got); + return result; +} + +/** + * Get a compare hint of a string using BINARY collation. + * Works similar to key_hint_string, read it's comment for more + * details. + */ +static uint64_t +coll_bin_hint(const char *s, size_t s_len, struct coll *coll) +{ + (void)coll; + uint64_t result = 0; + uint32_t process_len = MIN(s_len, sizeof(char) - 1); + for (uint32_t i = 0; i < process_len; i++) { + result <<= CHAR_BIT; + result |= UCHAR_MAX + 1; + result |= s[i]; + } + result <<= (CHAR_BIT + 1) * (sizeof(char) - 1 - process_len); + return result; +} + /** * Set up ICU collator and init cmp and hash members of collation. * @param coll Collation to set up. @@ -242,6 +285,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def) } coll->cmp = coll_icu_cmp; coll->hash = coll_icu_hash; + coll->hint = coll_icu_hint; return 0; } @@ -332,6 +376,7 @@ coll_new(const struct coll_def *def) coll->collator = NULL; coll->cmp = coll_bin_cmp; coll->hash = coll_bin_hash; + coll->hint = coll_bin_hint; break; default: unreachable(); diff --git a/src/coll.h b/src/coll.h index 9c725712a..53133dae3 100644 --- a/src/coll.h +++ b/src/coll.h @@ -47,6 +47,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t, typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, struct coll *coll); +typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll); + struct UCollator; /** @@ -61,6 +63,8 @@ struct coll { /** String comparator. */ coll_cmp_f cmp; coll_hash_f hash; + /** The pointer to routine calculating tuple hint. */ + coll_hint_f hint; /** Reference counter. */ int refs; /** -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov @ 2019-02-14 14:09 ` Konstantin Osipov 2019-02-15 18:34 ` Kirill Shcherbatov 1 sibling, 0 replies; 13+ messages in thread From: Konstantin Osipov @ 2019-02-14 14:09 UTC (permalink / raw) To: tarantool-patches; +Cc: vdavydov.dev, Alexandr Lyapunov * Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/13 13:03]: > From: Alexandr Lyapunov <aleks@tarantool.org> > diff --git a/src/box/key_def.c b/src/box/key_def.c > index 9411ade39..ceca1ebee 100644 > --- a/src/box/key_def.c > +++ b/src/box/key_def.c > @@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def) > def->tuple_compare_with_key = tuple_compare_with_key_create(def); > tuple_hash_func_set(def); > tuple_extract_key_set(def); > + tuple_hint_set(def); I think the name of the function is confusing. The name suggests that it says a tuple hint, whereas it sets a function which evaluates the hint. Please prepare a separate patch which renames existing functions tuple_hash_func_set and tuple_extract_key_set to key_def_set_{tuple_extract_key_func|tuple_hash_func|tuple_hint_func}. > +/** @copydoc tuple_hint() */ > +typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple, > + struct key_def *key_def); The func typedef should end with _f not with _t. > + > +/** @copydoc key_hint() */ > +typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def); Same here. > +static int > +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a, > + struct memtx_hinted_tree_data *b, > + struct key_def *key_def) > +{ > + if (a->hint != b->hint) > + return a->hint < b->hint ? -1 : 1; > + return tuple_compare(a->tuple, b->tuple, key_def); > +} Looks like we need null-aware hints as well, to preserve online null -> not null alter semantics. -- Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 http://tarantool.io - www.twitter.com/kostja_osipov ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov 2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov @ 2019-02-15 18:34 ` Kirill Shcherbatov 2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov 2019-02-19 15:02 ` Kirill Shcherbatov 1 sibling, 2 replies; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-15 18:34 UTC (permalink / raw) To: tarantool-patches, kostja, vdavydov.dev; +Cc: Alexandr Lyapunov Hi! I've implemented Kostya's concepts for compatible hints for UINT/INT. Also fixed nullability troubles. Now alter looks fine for me. I've thought about number/integer convertions, but such alter would not pass, I guess. ========================================= Implement functions for retrieving tuple hints for a particular key_def. Hint is an integer that can be used for tuple comparison optimization: if a hint of one tuple is less than a hint of another then the first tuple is definitely less than the second; only if hints are equal tuple_compare must be called for getting comparison result. Hints are calculated using only the first part of key_def. Hints are only useful when: * they are precalculated and stored along with the tuple; calculation is not cheap (cheaper than tuple_compare btw) but precalculated hints allow to compare tuples without even fetching tuple data. * first part of key_def is 'string'(for now) * since hint is calculated using only the first part of key_def (and only first several characters if it is a string) this part must be different with high probability for every tuple pair. Part of #3961 --- src/box/key_def.c | 1 + src/box/key_def.h | 44 +++++++++ src/box/memtx_tree_decl.c | 125 ++++++++++++++++++++++++++ src/box/tuple_compare.cc | 182 ++++++++++++++++++++++++++++++++++++++ src/box/tuple_compare.h | 7 ++ src/coll.c | 45 ++++++++++ src/coll.h | 4 + 7 files changed, 408 insertions(+) diff --git a/src/box/key_def.c b/src/box/key_def.c index 9411ade39..ceca1ebee 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def) def->tuple_compare_with_key = tuple_compare_with_key_create(def); tuple_hash_func_set(def); tuple_extract_key_set(def); + tuple_hint_set(def); } static void diff --git a/src/box/key_def.h b/src/box/key_def.h index bf3e63b6d..a2a0bbecb 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -153,6 +153,13 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple, typedef uint32_t (*key_hash_t)(const char *key, struct key_def *key_def); +/** @copydoc tuple_hint() */ +typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple, + struct key_def *key_def); + +/** @copydoc key_hint() */ +typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def); + /* Definition of a multipart key. */ struct key_def { /** @see tuple_compare() */ @@ -167,6 +174,10 @@ struct key_def { tuple_hash_t tuple_hash; /** @see key_hash() */ key_hash_t key_hash; + /** @see tuple_hint() */ + tuple_hint_t tuple_hint; + /** @see key_hint() */ + key_hint_t key_hint; /** * Minimal part count which always is unique. For example, * if a secondary index is unique, then @@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key, return key_def->tuple_compare_with_key(tuple, key, part_count, key_def); } +/** + * Get a comparison hint of a tuple. + * Hint is such a function h(tuple) in terms of particular key_def that + * has follows rules: + * if h(t1) < h(t2) then t1 < t2; + * if h(t1) > h(t2) then t1 > t2; + * if t1 == t2 then h(t1) == h(t2); + * These rules means that instead of direct tuple vs tuple (or tuple vs key) + * comparison one may compare theirs hints first; and only if theirs hints + * are equal compare the tuples themselves. + * @param tuple - tuple to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +tuple_hint(const struct tuple *tuple, struct key_def *key_def) +{ + return key_def->tuple_hint(tuple, key_def); +} + +/** + * Get a comparison hint of a key. + * @See tuple_hint for hint term definition. + * @param key - key to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +key_hint(const char *key, struct key_def *key_def) +{ + return key_def->key_hint(key, key_def); +} + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c index 084a0594f..55016148b 100644 --- a/src/box/memtx_tree_decl.c +++ b/src/box/memtx_tree_decl.c @@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data { /* }}} */ +/* {{{ Memtx hinted and hint_only tree class. *******************/ + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. +*/ +struct memtx_hinted_tree_key_data { + /** Sequence of msgpacked search fields. */ + const char *key; + /** Number of msgpacked search fields. */ + uint32_t part_count; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_key_data_set(). + */ + uint64_t hint; +}; + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. + */ +struct memtx_hinted_tree_data { + /** Tuple this node is representing. */ + struct tuple *tuple; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_data_set(). + */ + uint64_t hint; +}; + +/** + * Compare memtx_hinted_tree records. + */ +static int +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_data *b, + struct key_def *key_def) +{ + if (a->hint != b->hint) + return a->hint < b->hint ? -1 : 1; + return tuple_compare(a->tuple, b->tuple, key_def); +} + +/** + * Compare memtx_hinted_tree record with key. + */ +static int +memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_key_data *key, + struct key_def *key_def) +{ + if (a->hint != key->hint) + return a->hint < key->hint ? -1 : 1; + return tuple_compare_with_key(a->tuple, key->key, key->part_count, + key_def); +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree record + * with tuple and recalculate internal hint field. + */ +static void +memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data, + struct tuple *tuple, struct key_def *key_def) +{ + data->tuple = tuple; + data->hint = tuple_hint(tuple, key_def); +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree key with + * key raw and part count and recalculate internal hint field. + */ +static void +memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data, + const char *key, uint32_t part_count, + struct key_def *key_def) +{ + key_data->key = key; + key_data->part_count = part_count; + key_data->hint = key != NULL && part_count > 0 ? + key_hint(key, key_def) : 0; +} + +#define MEMTX_TREE_NAME memtx_hinted_tree +#define memtx_tree_elem struct memtx_hinted_tree_data +#define memtx_tree_key struct memtx_hinted_tree_key_data +#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \ + ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple) +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ + memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def) +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ + memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def) +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ + memtx_hinted_tree_data_set(elem_ptr, tuple, key_def) +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ + memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \ + key_def) +#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple) +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) + +#include "memtx_tree_impl.h" + +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_KEY_GET +#undef MEMTX_TREE_ELEM_GET +#undef MEMTX_TREE_KEY_SET +#undef MEMTX_TREE_ELEM_SET +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP +#undef MEMTX_TREE_ELEM_CMP +#undef MEMTX_TREE_ELEM_EQUAL +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_NAME + +/* }}} */ + struct index * memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) { + if (def->cmp_def->parts->type == FIELD_TYPE_STRING || + def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED || + def->cmp_def->parts->type == FIELD_TYPE_INTEGER) + return memtx_hinted_tree_index_new(memtx, def); return memtx_tuple_tree_index_new(memtx, def); } diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index ded802c7d..6ebf625a4 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -1321,4 +1321,186 @@ tuple_compare_with_key_create(const struct key_def *def) compare_with_key_slowpath_funcs[cmp_func_idx]; } +static uint64_t +key_hint_default(const char *key, struct key_def *key_def) +{ + (void)key; + (void)key_def; + return 0; +} + +static uint64_t +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def) +{ + (void)tuple; + (void)key_def; + return 0; +} + +template<bool is_nullable> +static uint64_t +key_hint_uint(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(mp_typeof(*key) == MP_UINT); + uint64_t val = mp_decode_uint(&key); + if (val > INT64_MAX) + return INT64_MAX; + return val - (uint64_t)INT64_MIN; +} + +template<bool is_nullable> +static uint64_t +tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_uint<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_int(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + if (mp_typeof(*key) == MP_UINT) { + return key_hint_uint<is_nullable>(key, key_def); + } else { + assert(key_def->parts->type == FIELD_TYPE_INTEGER); + assert(mp_typeof(*key) == MP_INT); + int64_t val = mp_decode_int(&key); + return (uint64_t)val - (uint64_t)INT64_MIN; + } +} + +template<bool is_nullable> +static uint64_t +tuple_hint_int(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_int<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_string(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + uint32_t len; + const unsigned char *str = + (const unsigned char *)mp_decode_str(&key, &len); + uint64_t result = 0; + /* + * Map the sequence of characters in the hint's bytes in + * the reverse order: the first character will be mapped + * in the highest byte of the number, etc. + * One additional bit encodes the presence of the next + * sign. + * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0 + * The sequence constructed in this way provides a + * comparison transitivity of strings no longer than 7 + * bytes. + */ + uint32_t process_len = MIN(len, 7); + for (uint32_t i = 0; i < process_len; i++) { + result <<= 9; + result |= 0x100; + result |= str[i]; + } + /* + * If the length of the string is less than the 64-bit + * hint can accommodate, the insignificant positions are + * filled with 0. + */ + result <<= 9 * (7 - process_len); + return result; +} + +template<bool is_nullable> +static uint64_t +tuple_hint_string(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_string<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_string_coll(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + assert(key_def->parts->coll != NULL); + uint32_t len; + const char *str = mp_decode_str(&key, &len); + return key_def->parts->coll->hint(str, len, key_def->parts->coll); +} + +template<bool is_nullable> +static uint64_t +tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_string_coll<is_nullable>(field, key_def); +} + +void +tuple_hint_set(struct key_def *def) +{ + def->key_hint = key_hint_default; + def->tuple_hint = tuple_hint_default; + bool is_nullable = key_part_is_nullable(def->parts); + if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL) { + def->key_hint = is_nullable ? key_hint_string_coll<true> : + key_hint_string_coll<false>; + def->tuple_hint = is_nullable ? tuple_hint_string_coll<true> : + tuple_hint_string_coll<false>; + return; + } + switch (def->parts->type) { + case FIELD_TYPE_UNSIGNED: + def->key_hint = is_nullable ? key_hint_uint<true> : + key_hint_uint<false>; + def->tuple_hint = is_nullable ? tuple_hint_uint<true> : + tuple_hint_uint<false>; + break; + case FIELD_TYPE_INTEGER: + def->key_hint = is_nullable ? key_hint_int<true> : + key_hint_int<false>; + def->tuple_hint = is_nullable ? tuple_hint_int<true> : + tuple_hint_int<false>; + break; + case FIELD_TYPE_STRING: + def->key_hint = is_nullable ? key_hint_string<true> : + key_hint_string<false>; + def->tuple_hint = is_nullable ? tuple_hint_string<true> : + tuple_hint_string<false>; + break; + default: + break; + }; +} + /* }}} tuple_compare_with_key */ diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h index e3a63204f..405460086 100644 --- a/src/box/tuple_compare.h +++ b/src/box/tuple_compare.h @@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def); tuple_compare_with_key_t tuple_compare_with_key_create(const struct key_def *key_def); +/** + * Initialize tuple_hint() and key_hint() functions for the key_def. + * @param key_def key definition to set up. + */ +void +tuple_hint_set(struct key_def *key_def); + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/coll.c b/src/coll.c index 6d9c44dbf..0e7c8ec92 100644 --- a/src/coll.c +++ b/src/coll.c @@ -33,6 +33,7 @@ #include "third_party/PMurHash.h" #include "diag.h" #include "assoc.h" +#include "limits.h" #include <unicode/ucol.h> #include <trivia/config.h> @@ -133,6 +134,48 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, return s_len; } +/** Get a compare hint of a string using ICU collation. */ +static uint64_t +coll_icu_hint(const char *s, size_t s_len, struct coll *coll) +{ + UCharIterator itr; + uiter_setUTF8(&itr, s, s_len); + uint8_t buf[7]; + uint32_t state[2] = {0, 0}; + UErrorCode status = U_ZERO_ERROR; + int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf, + sizeof(buf), &status); + assert(got >= 0 && got <= 7); + uint64_t result = 0; + for (int32_t i = 0; i < got; i++) { + result <<= 9; + result |= 0x100; + result |= buf[i]; + } + result <<= 9 * (7 - got); + return result; +} + +/** + * Get a compare hint of a string using BINARY collation. + * Works similar to key_hint_string, read it's comment for more + * details. + */ +static uint64_t +coll_bin_hint(const char *s, size_t s_len, struct coll *coll) +{ + (void)coll; + uint64_t result = 0; + uint32_t process_len = MIN(s_len, 7); + for (uint32_t i = 0; i < process_len; i++) { + result <<= 9; + result |= 0x100; + result |= s[i]; + } + result <<= 9 * (7 - process_len); + return result; +} + /** * Set up ICU collator and init cmp and hash members of collation. * @param coll Collation to set up. @@ -242,6 +285,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def) } coll->cmp = coll_icu_cmp; coll->hash = coll_icu_hash; + coll->hint = coll_icu_hint; return 0; } @@ -332,6 +376,7 @@ coll_new(const struct coll_def *def) coll->collator = NULL; coll->cmp = coll_bin_cmp; coll->hash = coll_bin_hash; + coll->hint = coll_bin_hint; break; default: unreachable(); diff --git a/src/coll.h b/src/coll.h index 9c725712a..53133dae3 100644 --- a/src/coll.h +++ b/src/coll.h @@ -47,6 +47,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t, typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, struct coll *coll); +typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll); + struct UCollator; /** @@ -61,6 +63,8 @@ struct coll { /** String comparator. */ coll_cmp_f cmp; coll_hash_f hash; + /** The pointer to routine calculating tuple hint. */ + coll_hint_f hint; /** Reference counter. */ int refs; /** -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-15 18:34 ` Kirill Shcherbatov @ 2019-02-19 15:01 ` Konstantin Osipov 2019-02-19 15:02 ` Kirill Shcherbatov 1 sibling, 0 replies; 13+ messages in thread From: Konstantin Osipov @ 2019-02-19 15:01 UTC (permalink / raw) To: tarantool-patches; +Cc: vdavydov.dev, Alexandr Lyapunov * Kirill Shcherbatov <kshcherbatov@tarantool.org> [19/02/15 21:36]: > Hi! I've implemented Kostya's concepts for compatible hints for UINT/INT. > Also fixed nullability troubles. Now alter looks fine for me. > I've thought about number/integer convertions, but such alter would not pass, > I guess. > Do you have tests for this or have you checked that specific tests exist? E.g. when tuple hint is used *and* we change nullability back and forth. BTW, have you checked changes in collation, do they work? -- Konstantin Osipov, Moscow, Russia, +7 903 626 22 32 http://tarantool.io - www.twitter.com/kostja_osipov ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-15 18:34 ` Kirill Shcherbatov 2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov @ 2019-02-19 15:02 ` Kirill Shcherbatov 2019-02-21 16:06 ` Vladimir Davydov 1 sibling, 1 reply; 13+ messages in thread From: Kirill Shcherbatov @ 2019-02-19 15:02 UTC (permalink / raw) To: tarantool-patches, Vladimir Davydov Hm, it looks like introduced before collation hint for binary collation is a not working. (I've dropped icu_bin_hint for now) This is a particular case in which there is no collator object, so we can do without hints at all in this case. ==================================================== Implement functions for retrieving tuple hints for a particular key_def. Hint is an integer that can be used for tuple comparison optimization: if a hint of one tuple is less than a hint of another then the first tuple is definitely less than the second; only if hints are equal tuple_compare must be called for getting comparison result. Hints are calculated using only the first part of key_def. Hints are only useful when: * they are precalculated and stored along with the tuple; calculation is not cheap (cheaper than tuple_compare btw) but precalculated hints allow to compare tuples without even fetching tuple data. * first part of key_def is 'string'(for now) * since hint is calculated using only the first part of key_def (and only first several characters if it is a string) this part must be different with high probability for every tuple pair. Closes #3961 --- src/box/key_def.c | 1 + src/box/key_def.h | 44 +++++++++ src/box/memtx_tree_decl.c | 125 ++++++++++++++++++++++++++ src/box/tuple_compare.cc | 185 ++++++++++++++++++++++++++++++++++++++ src/box/tuple_compare.h | 7 ++ src/coll.c | 24 +++++ src/coll.h | 4 + 7 files changed, 390 insertions(+) diff --git a/src/box/key_def.c b/src/box/key_def.c index 9411ade39..ceca1ebee 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -135,6 +135,7 @@ key_def_set_cmp(struct key_def *def) def->tuple_compare_with_key = tuple_compare_with_key_create(def); tuple_hash_func_set(def); tuple_extract_key_set(def); + tuple_hint_set(def); } static void diff --git a/src/box/key_def.h b/src/box/key_def.h index bf3e63b6d..a2a0bbecb 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -153,6 +153,13 @@ typedef uint32_t (*tuple_hash_t)(const struct tuple *tuple, typedef uint32_t (*key_hash_t)(const char *key, struct key_def *key_def); +/** @copydoc tuple_hint() */ +typedef uint64_t (*tuple_hint_t)(const struct tuple *tuple, + struct key_def *key_def); + +/** @copydoc key_hint() */ +typedef uint64_t (*key_hint_t)(const char *key, struct key_def *key_def); + /* Definition of a multipart key. */ struct key_def { /** @see tuple_compare() */ @@ -167,6 +174,10 @@ struct key_def { tuple_hash_t tuple_hash; /** @see key_hash() */ key_hash_t key_hash; + /** @see tuple_hint() */ + tuple_hint_t tuple_hint; + /** @see key_hint() */ + key_hint_t key_hint; /** * Minimal part count which always is unique. For example, * if a secondary index is unique, then @@ -551,6 +562,39 @@ tuple_compare_with_key(const struct tuple *tuple, const char *key, return key_def->tuple_compare_with_key(tuple, key, part_count, key_def); } +/** + * Get a comparison hint of a tuple. + * Hint is such a function h(tuple) in terms of particular key_def that + * has follows rules: + * if h(t1) < h(t2) then t1 < t2; + * if h(t1) > h(t2) then t1 > t2; + * if t1 == t2 then h(t1) == h(t2); + * These rules means that instead of direct tuple vs tuple (or tuple vs key) + * comparison one may compare theirs hints first; and only if theirs hints + * are equal compare the tuples themselves. + * @param tuple - tuple to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +tuple_hint(const struct tuple *tuple, struct key_def *key_def) +{ + return key_def->tuple_hint(tuple, key_def); +} + +/** + * Get a comparison hint of a key. + * @See tuple_hint for hint term definition. + * @param key - key to get hint of. + * @param key_def - key_def that defines which comparison is used. + * @return the hint. + */ +static inline uint64_t +key_hint(const char *key, struct key_def *key_def) +{ + return key_def->key_hint(key, key_def); +} + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c index 084a0594f..55016148b 100644 --- a/src/box/memtx_tree_decl.c +++ b/src/box/memtx_tree_decl.c @@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data { /* }}} */ +/* {{{ Memtx hinted and hint_only tree class. *******************/ + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. +*/ +struct memtx_hinted_tree_key_data { + /** Sequence of msgpacked search fields. */ + const char *key; + /** Number of msgpacked search fields. */ + uint32_t part_count; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_key_data_set(). + */ + uint64_t hint; +}; + +/** + * Struct that is used as a key in BPS tree definition in + * memtx_hint_only_tree and memtx_hinted_tree. + */ +struct memtx_hinted_tree_data { + /** Tuple this node is representing. */ + struct tuple *tuple; + /** + * Compare hint. Is calculated automatically on 'set' + * operation with memtx_hinted_tree_data_set(). + */ + uint64_t hint; +}; + +/** + * Compare memtx_hinted_tree records. + */ +static int +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_data *b, + struct key_def *key_def) +{ + if (a->hint != b->hint) + return a->hint < b->hint ? -1 : 1; + return tuple_compare(a->tuple, b->tuple, key_def); +} + +/** + * Compare memtx_hinted_tree record with key. + */ +static int +memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a, + struct memtx_hinted_tree_key_data *key, + struct key_def *key_def) +{ + if (a->hint != key->hint) + return a->hint < key->hint ? -1 : 1; + return tuple_compare_with_key(a->tuple, key->key, key->part_count, + key_def); +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree record + * with tuple and recalculate internal hint field. + */ +static void +memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data, + struct tuple *tuple, struct key_def *key_def) +{ + data->tuple = tuple; + data->hint = tuple_hint(tuple, key_def); +} + +/** + * Initialize memtx_hinted_tree or memtx_hint_only_tree key with + * key raw and part count and recalculate internal hint field. + */ +static void +memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data, + const char *key, uint32_t part_count, + struct key_def *key_def) +{ + key_data->key = key; + key_data->part_count = part_count; + key_data->hint = key != NULL && part_count > 0 ? + key_hint(key, key_def) : 0; +} + +#define MEMTX_TREE_NAME memtx_hinted_tree +#define memtx_tree_elem struct memtx_hinted_tree_data +#define memtx_tree_key struct memtx_hinted_tree_key_data +#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \ + ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple) +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ + memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def) +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ + memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def) +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ + memtx_hinted_tree_data_set(elem_ptr, tuple, key_def) +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ + memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \ + key_def) +#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple) +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) + +#include "memtx_tree_impl.h" + +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_KEY_GET +#undef MEMTX_TREE_ELEM_GET +#undef MEMTX_TREE_KEY_SET +#undef MEMTX_TREE_ELEM_SET +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP +#undef MEMTX_TREE_ELEM_CMP +#undef MEMTX_TREE_ELEM_EQUAL +#undef memtx_tree_key +#undef memtx_tree_elem +#undef MEMTX_TREE_NAME + +/* }}} */ + struct index * memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) { + if (def->cmp_def->parts->type == FIELD_TYPE_STRING || + def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED || + def->cmp_def->parts->type == FIELD_TYPE_INTEGER) + return memtx_hinted_tree_index_new(memtx, def); return memtx_tuple_tree_index_new(memtx, def); } diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index ded802c7d..5845235ff 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -1321,4 +1321,189 @@ tuple_compare_with_key_create(const struct key_def *def) compare_with_key_slowpath_funcs[cmp_func_idx]; } +static uint64_t +key_hint_default(const char *key, struct key_def *key_def) +{ + (void)key; + (void)key_def; + return 0; +} + +static uint64_t +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def) +{ + (void)tuple; + (void)key_def; + return 0; +} + +template<bool is_nullable> +static uint64_t +key_hint_uint(const char *key, struct key_def *key_def) +{ + (void)key_def; + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(mp_typeof(*key) == MP_UINT); + uint64_t val = mp_decode_uint(&key); + if (val > INT64_MAX) + return INT64_MAX; + return val - (uint64_t)INT64_MIN; +} + +template<bool is_nullable> +static uint64_t +tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_uint<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_int(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + if (mp_typeof(*key) == MP_UINT) { + return key_hint_uint<is_nullable>(key, key_def); + } else { + assert(key_def->parts->type == FIELD_TYPE_INTEGER); + assert(mp_typeof(*key) == MP_INT); + int64_t val = mp_decode_int(&key); + return (uint64_t)val - (uint64_t)INT64_MIN; + } +} + +template<bool is_nullable> +static uint64_t +tuple_hint_int(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_int<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_string(const char *key, struct key_def *key_def) +{ + (void)key_def; + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + uint32_t len; + const unsigned char *str = + (const unsigned char *)mp_decode_str(&key, &len); + uint64_t result = 0; + /* + * Map the sequence of characters in the hint's bytes in + * the reverse order: the first character will be mapped + * in the highest byte of the number, etc. + * One additional bit encodes the presence of the next + * sign. + * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0 + * The sequence constructed in this way provides a + * comparison transitivity of strings no longer than 7 + * bytes. + */ + uint32_t process_len = MIN(len, 7); + for (uint32_t i = 0; i < process_len; i++) { + result <<= 9; + result |= 0x100; + result |= str[i]; + } + /* + * If the length of the string is less than the 64-bit + * hint can accommodate, the insignificant positions are + * filled with 0. + */ + result <<= 9 * (7 - process_len); + return result; +} + +template<bool is_nullable> +static uint64_t +tuple_hint_string(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_string<is_nullable>(field, key_def); +} + +template<bool is_nullable> +static uint64_t +key_hint_string_coll(const char *key, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + if (is_nullable && mp_typeof(*key) == MP_NIL) + return 0; + assert(key_def->parts->type == FIELD_TYPE_STRING); + assert(mp_typeof(*key) == MP_STR); + assert(key_def->parts->coll != NULL); + uint32_t len; + const char *str = mp_decode_str(&key, &len); + return key_def->parts->coll->hint(str, len, key_def->parts->coll); +} + +template<bool is_nullable> +static uint64_t +tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def) +{ + assert(key_part_is_nullable(key_def->parts) == is_nullable); + const char *field = tuple_field_by_part(tuple, key_def->parts); + if (is_nullable && field == NULL) + return 0; + return key_hint_string_coll<is_nullable>(field, key_def); +} + +void +tuple_hint_set(struct key_def *def) +{ + def->key_hint = key_hint_default; + def->tuple_hint = tuple_hint_default; + bool is_nullable = key_part_is_nullable(def->parts); + if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL && + def->parts->coll->type != COLL_TYPE_BINARY) { + def->key_hint = is_nullable ? key_hint_string_coll<true> : + key_hint_string_coll<false>; + def->tuple_hint = is_nullable ? tuple_hint_string_coll<true> : + tuple_hint_string_coll<false>; + return; + } + switch (def->parts->type) { + case FIELD_TYPE_UNSIGNED: + def->key_hint = is_nullable ? key_hint_uint<true> : + key_hint_uint<false>; + def->tuple_hint = is_nullable ? tuple_hint_uint<true> : + tuple_hint_uint<false>; + break; + case FIELD_TYPE_INTEGER: + def->key_hint = is_nullable ? key_hint_int<true> : + key_hint_int<false>; + def->tuple_hint = is_nullable ? tuple_hint_int<true> : + tuple_hint_int<false>; + break; + case FIELD_TYPE_STRING: + def->key_hint = is_nullable ? key_hint_string<true> : + key_hint_string<false>; + def->tuple_hint = is_nullable ? tuple_hint_string<true> : + tuple_hint_string<false>; + break; + default: + break; + }; +} + /* }}} tuple_compare_with_key */ diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h index e3a63204f..405460086 100644 --- a/src/box/tuple_compare.h +++ b/src/box/tuple_compare.h @@ -67,6 +67,13 @@ tuple_compare_create(const struct key_def *key_def); tuple_compare_with_key_t tuple_compare_with_key_create(const struct key_def *key_def); +/** + * Initialize tuple_hint() and key_hint() functions for the key_def. + * @param key_def key definition to set up. + */ +void +tuple_hint_set(struct key_def *key_def); + #if defined(__cplusplus) } /* extern "C" */ #endif /* defined(__cplusplus) */ diff --git a/src/coll.c b/src/coll.c index 6d9c44dbf..922f03944 100644 --- a/src/coll.c +++ b/src/coll.c @@ -133,6 +133,28 @@ coll_bin_hash(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, return s_len; } +/** Get a compare hint of a string using ICU collation. */ +static uint64_t +coll_icu_hint(const char *s, size_t s_len, struct coll *coll) +{ + UCharIterator itr; + uiter_setUTF8(&itr, s, s_len); + uint8_t buf[7]; + uint32_t state[2] = {0, 0}; + UErrorCode status = U_ZERO_ERROR; + int32_t got = ucol_nextSortKeyPart(coll->collator, &itr, state, buf, + sizeof(buf), &status); + assert(got >= 0 && got <= 7); + uint64_t result = 0; + for (int32_t i = 0; i < got; i++) { + result <<= 9; + result |= 0x100; + result |= buf[i]; + } + result <<= 9 * (7 - got); + return result; +} + /** * Set up ICU collator and init cmp and hash members of collation. * @param coll Collation to set up. @@ -242,6 +264,7 @@ coll_icu_init_cmp(struct coll *coll, const struct coll_def *def) } coll->cmp = coll_icu_cmp; coll->hash = coll_icu_hash; + coll->hint = coll_icu_hint; return 0; } @@ -332,6 +355,7 @@ coll_new(const struct coll_def *def) coll->collator = NULL; coll->cmp = coll_bin_cmp; coll->hash = coll_bin_hash; + coll->hint = NULL; break; default: unreachable(); diff --git a/src/coll.h b/src/coll.h index 9c725712a..53133dae3 100644 --- a/src/coll.h +++ b/src/coll.h @@ -47,6 +47,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t, typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph, uint32_t *pcarry, struct coll *coll); +typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll); + struct UCollator; /** @@ -61,6 +63,8 @@ struct coll { /** String comparator. */ coll_cmp_f cmp; coll_hash_f hash; + /** The pointer to routine calculating tuple hint. */ + coll_hint_f hint; /** Reference counter. */ int refs; /** -- 2.20.1 ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [tarantool-patches] Re: [PATCH v2 4/4] box: introduce tuple compare hint for string index 2019-02-19 15:02 ` Kirill Shcherbatov @ 2019-02-21 16:06 ` Vladimir Davydov 0 siblings, 0 replies; 13+ messages in thread From: Vladimir Davydov @ 2019-02-21 16:06 UTC (permalink / raw) To: Kirill Shcherbatov; +Cc: tarantool-patches On Tue, Feb 19, 2019 at 06:02:55PM +0300, Kirill Shcherbatov wrote: > diff --git a/src/box/memtx_tree_decl.c b/src/box/memtx_tree_decl.c > index 084a0594f..55016148b 100644 > --- a/src/box/memtx_tree_decl.c > +++ b/src/box/memtx_tree_decl.c > @@ -77,8 +77,133 @@ struct memtx_tuple_tree_key_data { > > /* }}} */ > > +/* {{{ Memtx hinted and hint_only tree class. *******************/ There's no hint_only tree anymore. Please update the comments. > + > +/** > + * Struct that is used as a key in BPS tree definition in > + * memtx_hint_only_tree and memtx_hinted_tree. > +*/ > +struct memtx_hinted_tree_key_data { > + /** Sequence of msgpacked search fields. */ > + const char *key; > + /** Number of msgpacked search fields. */ > + uint32_t part_count; > + /** > + * Compare hint. Is calculated automatically on 'set' Comparison hint. 'Is' isn't necessary - could be simply Calculated ... > + * operation with memtx_hinted_tree_key_data_set(). > + */ > + uint64_t hint; > +}; > + > +/** > + * Struct that is used as a key in BPS tree definition in > + * memtx_hint_only_tree and memtx_hinted_tree. > + */ > +struct memtx_hinted_tree_data { > + /** Tuple this node is representing. */ represents > + struct tuple *tuple; > + /** > + * Compare hint. Is calculated automatically on 'set' > + * operation with memtx_hinted_tree_data_set(). > + */ > + uint64_t hint; > +}; > + > +/** > + * Compare memtx_hinted_tree records. > + */ > +static int > +memtx_hinted_tree_data_cmp(struct memtx_hinted_tree_data *a, > + struct memtx_hinted_tree_data *b, > + struct key_def *key_def) > +{ > + if (a->hint != b->hint) > + return a->hint < b->hint ? -1 : 1; > + return tuple_compare(a->tuple, b->tuple, key_def); > +} > + > +/** > + * Compare memtx_hinted_tree record with key. > + */ > +static int > +memtx_hinted_tree_data_cmp_with_key(struct memtx_hinted_tree_data *a, > + struct memtx_hinted_tree_key_data *key, > + struct key_def *key_def) > +{ > + if (a->hint != key->hint) > + return a->hint < key->hint ? -1 : 1; > + return tuple_compare_with_key(a->tuple, key->key, key->part_count, > + key_def); > +} > + > +/** > + * Initialize memtx_hinted_tree or memtx_hint_only_tree record > + * with tuple and recalculate internal hint field. > + */ > +static void > +memtx_hinted_tree_data_set(struct memtx_hinted_tree_data *data, > + struct tuple *tuple, struct key_def *key_def) > +{ > + data->tuple = tuple; > + data->hint = tuple_hint(tuple, key_def); > +} > + > +/** > + * Initialize memtx_hinted_tree or memtx_hint_only_tree key with > + * key raw and part count and recalculate internal hint field. > + */ > +static void > +memtx_hinted_tree_key_data_set(struct memtx_hinted_tree_key_data *key_data, > + const char *key, uint32_t part_count, > + struct key_def *key_def) All these functions aren't used anywhere except in MEMTX_TREE_ macros, and they're pretty short. Worth inlining them there? > +{ > + key_data->key = key; > + key_data->part_count = part_count; > + key_data->hint = key != NULL && part_count > 0 ? No need to check both part_count and key. Either of them is enough. > + key_hint(key, key_def) : 0; > +} > + > +#define MEMTX_TREE_NAME memtx_hinted_tree > +#define memtx_tree_elem struct memtx_hinted_tree_data > +#define memtx_tree_key struct memtx_hinted_tree_key_data > +#define MEMTX_TREE_ELEM_EQUAL(elem_a_ptr, elem_b_ptr) \ > + ((elem_a_ptr)->tuple == (elem_b_ptr)->tuple) This macro isn't required as far as I recall. > +#define MEMTX_TREE_ELEM_CMP(elem_a_ptr, elem_b_ptr, key_def) \ > + memtx_hinted_tree_data_cmp(elem_a_ptr, elem_b_ptr, key_def) > +#define MEMTX_TREE_ELEM_WITH_KEY_CMP(elem_ptr, key_ptr, key_def) \ > + memtx_hinted_tree_data_cmp_with_key(elem_ptr, key_ptr, key_def) > +#define MEMTX_TREE_ELEM_SET(elem_ptr, tuple, key_def) \ > + memtx_hinted_tree_data_set(elem_ptr, tuple, key_def) > +#define MEMTX_TREE_KEY_SET(key_ptr, key_val, part_count_val, key_def) \ > + memtx_hinted_tree_key_data_set(key_ptr, key_val, part_count_val, \ > + key_def) > +#define MEMTX_TREE_ELEM_GET(elem_ptr) ((elem_ptr)->tuple) > +#define MEMTX_TREE_KEY_GET(key_ptr, part_count_ptr) \ > + ({*part_count_ptr = (key_ptr)->part_count; (key_ptr)->key;}) > + > +#include "memtx_tree_impl.h" > + > +#undef memtx_tree_key > +#undef memtx_tree_elem > +#undef MEMTX_TREE_KEY_GET > +#undef MEMTX_TREE_ELEM_GET > +#undef MEMTX_TREE_KEY_SET > +#undef MEMTX_TREE_ELEM_SET > +#undef MEMTX_TREE_ELEM_WITH_KEY_CMP > +#undef MEMTX_TREE_ELEM_CMP > +#undef MEMTX_TREE_ELEM_EQUAL > +#undef memtx_tree_key > +#undef memtx_tree_elem > +#undef MEMTX_TREE_NAME > + > +/* }}} */ > + > struct index * > memtx_tree_index_new(struct memtx_engine *memtx, struct index_def *def) > { > + if (def->cmp_def->parts->type == FIELD_TYPE_STRING || > + def->cmp_def->parts->type == FIELD_TYPE_UNSIGNED || > + def->cmp_def->parts->type == FIELD_TYPE_INTEGER) > + return memtx_hinted_tree_index_new(memtx, def); > return memtx_tuple_tree_index_new(memtx, def); > } > diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc > index ded802c7d..5845235ff 100644 > --- a/src/box/tuple_compare.cc > +++ b/src/box/tuple_compare.cc > @@ -1321,4 +1321,189 @@ tuple_compare_with_key_create(const struct key_def *def) > compare_with_key_slowpath_funcs[cmp_func_idx]; > } I think all the hints should be defined in new files tuple_hint.{h,cc} > > +static uint64_t > +key_hint_default(const char *key, struct key_def *key_def) > +{ > + (void)key; > + (void)key_def; > + return 0; > +} > + > +static uint64_t > +tuple_hint_default(const struct tuple *tuple, struct key_def *key_def) > +{ > + (void)tuple; > + (void)key_def; > + return 0; > +} > + > +template<bool is_nullable> I doubt we need to use templates here, but OK, let them be. > +static uint64_t > +key_hint_uint(const char *key, struct key_def *key_def) > +{ > + (void)key_def; > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + if (is_nullable && mp_typeof(*key) == MP_NIL) > + return 0; > + assert(mp_typeof(*key) == MP_UINT); > + uint64_t val = mp_decode_uint(&key); > + if (val > INT64_MAX) > + return INT64_MAX; > + return val - (uint64_t)INT64_MIN; > +} > + > +template<bool is_nullable> > +static uint64_t > +tuple_hint_uint(const struct tuple *tuple, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + const char *field = tuple_field_by_part(tuple, key_def->parts); > + if (is_nullable && field == NULL) > + return 0; > + return key_hint_uint<is_nullable>(field, key_def); > +} > + > +template<bool is_nullable> > +static uint64_t > +key_hint_int(const char *key, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + if (is_nullable && mp_typeof(*key) == MP_NIL) > + return 0; > + if (mp_typeof(*key) == MP_UINT) { > + return key_hint_uint<is_nullable>(key, key_def); > + } else { > + assert(key_def->parts->type == FIELD_TYPE_INTEGER); This assertion should be in the beginning of this function, no? Please also add assertions checking part->type to other hint functions. > + assert(mp_typeof(*key) == MP_INT); > + int64_t val = mp_decode_int(&key); > + return (uint64_t)val - (uint64_t)INT64_MIN; > + } > +} > + > +template<bool is_nullable> > +static uint64_t > +tuple_hint_int(const struct tuple *tuple, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + const char *field = tuple_field_by_part(tuple, key_def->parts); > + if (is_nullable && field == NULL) > + return 0; > + return key_hint_int<is_nullable>(field, key_def); > +} > + > +template<bool is_nullable> > +static uint64_t > +key_hint_string(const char *key, struct key_def *key_def) > +{ > + (void)key_def; > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + if (is_nullable && mp_typeof(*key) == MP_NIL) > + return 0; > + assert(key_def->parts->type == FIELD_TYPE_STRING); > + assert(mp_typeof(*key) == MP_STR); > + uint32_t len; > + const unsigned char *str = > + (const unsigned char *)mp_decode_str(&key, &len); > + uint64_t result = 0; > + /* > + * Map the sequence of characters in the hint's bytes in > + * the reverse order: the first character will be mapped > + * in the highest byte of the number, etc. > + * One additional bit encodes the presence of the next > + * sign. > + * 0bCHARBYTEU CHARBYTEU CHARBYTEU ... CHARBYTE0 > + * The sequence constructed in this way provides a > + * comparison transitivity of strings no longer than 7 > + * bytes. Still I don't understand why we need this transformation and why simply using a sequence of bytes constituting the string isn't enough. Could you give an example? > + */ > + uint32_t process_len = MIN(len, 7); > + for (uint32_t i = 0; i < process_len; i++) { > + result <<= 9; > + result |= 0x100; > + result |= str[i]; > + } > + /* > + * If the length of the string is less than the 64-bit > + * hint can accommodate, the insignificant positions are > + * filled with 0. > + */ > + result <<= 9 * (7 - process_len); > + return result; > +} > + > +template<bool is_nullable> > +static uint64_t > +tuple_hint_string(const struct tuple *tuple, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + const char *field = tuple_field_by_part(tuple, key_def->parts); > + if (is_nullable && field == NULL) > + return 0; > + return key_hint_string<is_nullable>(field, key_def); > +} > + > +template<bool is_nullable> > +static uint64_t > +key_hint_string_coll(const char *key, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + if (is_nullable && mp_typeof(*key) == MP_NIL) > + return 0; > + assert(key_def->parts->type == FIELD_TYPE_STRING); > + assert(mp_typeof(*key) == MP_STR); > + assert(key_def->parts->coll != NULL); > + uint32_t len; > + const char *str = mp_decode_str(&key, &len); > + return key_def->parts->coll->hint(str, len, key_def->parts->coll); > +} > + > +template<bool is_nullable> > +static uint64_t > +tuple_hint_string_coll(const struct tuple *tuple, struct key_def *key_def) > +{ > + assert(key_part_is_nullable(key_def->parts) == is_nullable); > + const char *field = tuple_field_by_part(tuple, key_def->parts); > + if (is_nullable && field == NULL) > + return 0; > + return key_hint_string_coll<is_nullable>(field, key_def); > +} > + > +void > +tuple_hint_set(struct key_def *def) Should be called key_def_set_hint_func. Please rename. > +{ > + def->key_hint = key_hint_default; > + def->tuple_hint = tuple_hint_default; > + bool is_nullable = key_part_is_nullable(def->parts); > + if (def->parts->type == FIELD_TYPE_STRING && def->parts->coll != NULL && > + def->parts->coll->type != COLL_TYPE_BINARY) { > + def->key_hint = is_nullable ? key_hint_string_coll<true> : > + key_hint_string_coll<false>; > + def->tuple_hint = is_nullable ? tuple_hint_string_coll<true> : > + tuple_hint_string_coll<false>; > + return; > + } > + switch (def->parts->type) { > + case FIELD_TYPE_UNSIGNED: > + def->key_hint = is_nullable ? key_hint_uint<true> : > + key_hint_uint<false>; > + def->tuple_hint = is_nullable ? tuple_hint_uint<true> : > + tuple_hint_uint<false>; > + break; > + case FIELD_TYPE_INTEGER: > + def->key_hint = is_nullable ? key_hint_int<true> : > + key_hint_int<false>; > + def->tuple_hint = is_nullable ? tuple_hint_int<true> : > + tuple_hint_int<false>; > + break; > + case FIELD_TYPE_STRING: > + def->key_hint = is_nullable ? key_hint_string<true> : > + key_hint_string<false>; > + def->tuple_hint = is_nullable ? tuple_hint_string<true> : > + tuple_hint_string<false>; > + break; > + default: > + break; > + }; > +} ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2019-02-21 16:06 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-02-13 9:32 [PATCH v2 0/4] box: introduce hint option for memtx tree index Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 1/4] box: move memtx_tree implementation to source file Kirill Shcherbatov 2019-02-14 13:57 ` [tarantool-patches] " Konstantin Osipov 2019-02-21 13:26 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 2/4] box: rework memtx_tree to store arbitrary nodes Kirill Shcherbatov 2019-02-21 15:01 ` Vladimir Davydov 2019-02-13 9:32 ` [PATCH v2 3/4] box: rename memtx_tree.c to memtx_tree_impl.h Kirill Shcherbatov 2019-02-13 9:32 ` [PATCH v2 4/4] box: introduce tuple compare hint for string index Kirill Shcherbatov 2019-02-14 14:09 ` [tarantool-patches] " Konstantin Osipov 2019-02-15 18:34 ` Kirill Shcherbatov 2019-02-19 15:01 ` [tarantool-patches] " Konstantin Osipov 2019-02-19 15:02 ` Kirill Shcherbatov 2019-02-21 16:06 ` Vladimir Davydov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox