From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Tue, 19 Mar 2019 22:38:37 +0300 From: Vladimir Davydov Subject: Re: [tarantool-patches] Re: [PATCH v6 1/3] box: refactor key_def_set_compare_func routine Message-ID: <20190319193837.4xy4eb35yatxuwic@esperanza> References: <34cf8ed7af4b1da74a89a260562abe08526cd4e8.1552478226.git.kshcherbatov@tarantool.org> <20190314070447.dpdu3aocinfiwrtr@esperanza> <9b725e11-1fe7-6cad-d810-5181056cde9d@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <9b725e11-1fe7-6cad-d810-5181056cde9d@tarantool.org> To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org List-ID: On Fri, Mar 15, 2019 at 01:20:11PM +0300, Kirill Shcherbatov wrote: > +#define COMPARE_SLOWPATH(...) \ > + {tuple_compare_slowpath<__VA_ARGS__>, \ > + tuple_compare_with_key_slowpath<__VA_ARGS__>, \ > + __VA_ARGS__, false} > + > +#define COMPARE_SEQUENTIAL(...) \ > + {tuple_compare_sequential<__VA_ARGS__>, \ > + tuple_compare_with_key_sequential<__VA_ARGS__>, \ > + __VA_ARGS__, false, true} > + > +static struct { > + tuple_compare_t tuple_compare; > + tuple_compare_with_key_t tuple_compare_with_key; > + bool is_nullable; > + bool has_optional_parts; > + bool has_json_paths; > + bool is_sequential; > +} cmp_arr[] = { > + COMPARE_SLOWPATH(false, false, false), > + COMPARE_SLOWPATH(true, false, false), > + COMPARE_SLOWPATH(false, true, false), > + COMPARE_SLOWPATH(true, true, false), > + COMPARE_SLOWPATH(false, false, true), > + COMPARE_SLOWPATH(true, false, true), > + COMPARE_SLOWPATH(false, true, true), > + COMPARE_SLOWPATH(true, true, true), > + COMPARE_SEQUENTIAL(false, false), > + COMPARE_SEQUENTIAL(true, false), > + COMPARE_SEQUENTIAL(false, true), > + COMPARE_SEQUENTIAL(true, true), > }; > > -static tuple_compare_with_key_t > -tuple_compare_with_key_create(const struct key_def *def) > +#undef COMPARE_SLOWPATH > +#undef COMPARE_SEQUENTIAL > + > +/* }}} tuple_compare_with_key */ > + > +void > +key_def_set_compare_func(struct key_def *def) > { > - int cmp_func_idx = (def->is_nullable ? 1 : 0) + > - 2 * (def->has_optional_parts ? 1 : 0) + > - 4 * (def->has_json_paths ? 1 : 0); > - if (def->is_nullable) { > - if (key_def_is_sequential(def)) { > - if (def->has_optional_parts) { > - return tuple_compare_with_key_sequential - true>; > - } else { > - return tuple_compare_with_key_sequential - false>; > + def->tuple_compare = NULL; > + def->tuple_compare_with_key = NULL; > + if (!def->is_nullable && !key_def_has_collation(def) && > + !def->has_json_paths) { > + /* Precalculated comparators don't use collation */ > + for (uint32_t k = 0; k < sizeof(precompiled_cmp_arr) / > + sizeof(precompiled_cmp_arr[0]); k++) { > + uint32_t i = 0; > + for (; i < def->part_count; i++) { > + if (def->parts[i].fieldno != > + precompiled_cmp_arr[k].p[i * 2] || > + def->parts[i].type != > + precompiled_cmp_arr[k].p[i * 2 + 1]) > + break; > + } > + if (i == def->part_count && > + precompiled_cmp_arr[k].p[i * 2] == UINT32_MAX) { > + def->tuple_compare = precompiled_cmp_arr[k].f; > + break; > } > - } else { > - return compare_with_key_slowpath_funcs[cmp_func_idx]; > } > - } > - assert(! def->has_optional_parts); > - if (!key_def_has_collation(def) && !def->has_json_paths) { > - /* Precalculated comparators don't use collation */ > - for (uint32_t k = 0; > - k < sizeof(cmp_wk_arr) / sizeof(cmp_wk_arr[0]); > - k++) { > - > + for (uint32_t k = 0; k < sizeof(precompiled_cmp_wk_arr) / > + sizeof(precompiled_cmp_wk_arr[0]); k++) { > uint32_t i = 0; > for (; i < def->part_count; i++) { > if (def->parts[i].fieldno != > - cmp_wk_arr[k].p[i * 2] || > - def->parts[i].type != > - cmp_wk_arr[k].p[i * 2 + 1]) { > + precompiled_cmp_wk_arr[k].p[i * 2] || > + def->parts[i].type != > + precompiled_cmp_wk_arr[k].p[i * 2 + 1]) > break; > + } > + if (i == def->part_count) { > + def->tuple_compare_with_key = > + precompiled_cmp_wk_arr[k].f; > + break; > + } > + } > + } > + if (def->tuple_compare == NULL || def->tuple_compare_with_key == NULL) { > + for (uint32_t k = 0; k < sizeof(cmp_arr) / > + sizeof(cmp_arr[0]); k++) { > + if (def->is_nullable == cmp_arr[k].is_nullable && > + def->has_optional_parts == > + cmp_arr[k].has_optional_parts && > + def->has_json_paths == cmp_arr[k].has_json_paths && > + key_def_is_sequential(def) == > + cmp_arr[k].is_sequential) { > + if (def->tuple_compare == NULL) { > + def->tuple_compare = > + cmp_arr[k].tuple_compare; > } > + if (def->tuple_compare_with_key == NULL) { > + def->tuple_compare_with_key = > + cmp_arr[k]. > + tuple_compare_with_key; > + } > + break; > } > - if (i == def->part_count) > - return cmp_wk_arr[k].f; > } > } All these unnamed booleans and variadic macros and linear search over them look mind-boggling IMO. I understand that this approach is kinda generic, but it just looks ugly. In fact, I don't see any point in such a generalization at this point at all. See, although we'll have four parameters - is_nullable, has_optional_parts, has_json_paths, and is_multikey - they are not independent: - has_optional_parts depends on is_nullable - is_multikey depends on has_json_paths So the number of combination is far not staggering, and I don't see any new parameters coming in the near future. So I dropped this patch and instead split key_def_set_compare_func into sub-functions by key_def types. You will find the patch below. It should be trivial to add hinted comparators and multikey support on top of it without introducing deep if-else hiearchies or excessive code repetition. --- >From 829c811cdeb98bd8e5cb91edf2197f0c340d55ed Mon Sep 17 00:00:00 2001 Message-Id: <829c811cdeb98bd8e5cb91edf2197f0c340d55ed.1553024132.git.vdavydov.dev@gmail.com> From: Vladimir Davydov Date: Tue, 19 Mar 2019 20:27:42 +0300 Subject: [PATCH] tuple_compare: cleanup key_def virtual func setter Over time key_def virtual func setter code has turned into a complete mess: now it's an incomprehensible mix of if-else blocks, linear array search, and devious array indexing. What is worse, it's duplicated by tuple_compare_create and tuple_compare_with_key_create. Adding yet another parameter to key_def templates, which is needed to implement multi-key indexes, is literally impossible. This patch attempts to alleviate the situation by splitting code paths for pre-compiled, plain, and json indexes plus merging tuple_compare and tuple_compare_with_key setters. --- src/box/tuple_compare.cc | 211 +++++++++++++++++++++++------------------------ 1 file changed, 105 insertions(+), 106 deletions(-) diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index dfe30b19..19b396e2 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -1005,55 +1005,6 @@ static const comparator_signature cmp_arr[] = { #undef COMPARATOR -static const tuple_compare_t compare_slowpath_funcs[] = { - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath, - tuple_compare_slowpath -}; - -static tuple_compare_t -tuple_compare_create(const struct key_def *def) -{ - int cmp_func_idx = (def->is_nullable ? 1 : 0) + - 2 * (def->has_optional_parts ? 1 : 0) + - 4 * (def->has_json_paths ? 1 : 0); - if (def->is_nullable) { - if (key_def_is_sequential(def)) { - if (def->has_optional_parts) - return tuple_compare_sequential; - else - return tuple_compare_sequential; - } else { - return compare_slowpath_funcs[cmp_func_idx]; - } - } - assert(! def->has_optional_parts); - if (!key_def_has_collation(def) && !def->has_json_paths) { - /* Precalculated comparators don't use collation */ - for (uint32_t k = 0; - k < sizeof(cmp_arr) / sizeof(cmp_arr[0]); k++) { - uint32_t i = 0; - for (; i < def->part_count; i++) - if (def->parts[i].fieldno != - cmp_arr[k].p[i * 2] || - def->parts[i].type != - cmp_arr[k].p[i * 2 + 1]) - break; - if (i == def->part_count && - cmp_arr[k].p[i * 2] == UINT32_MAX) - return cmp_arr[k].f; - } - } - return key_def_is_sequential(def) ? - tuple_compare_sequential : - compare_slowpath_funcs[cmp_func_idx]; -} - /* }}} tuple_compare */ /* {{{ tuple_compare_with_key */ @@ -1233,66 +1184,114 @@ static const comparator_with_key_signature cmp_wk_arr[] = { #undef KEY_COMPARATOR -static const tuple_compare_with_key_t compare_with_key_slowpath_funcs[] = { - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath, - tuple_compare_with_key_slowpath -}; - -static tuple_compare_with_key_t -tuple_compare_with_key_create(const struct key_def *def) -{ - int cmp_func_idx = (def->is_nullable ? 1 : 0) + - 2 * (def->has_optional_parts ? 1 : 0) + - 4 * (def->has_json_paths ? 1 : 0); - if (def->is_nullable) { - if (key_def_is_sequential(def)) { - if (def->has_optional_parts) { - return tuple_compare_with_key_sequential; - } else { - return tuple_compare_with_key_sequential; - } - } else { - return compare_with_key_slowpath_funcs[cmp_func_idx]; - } - } - assert(! def->has_optional_parts); - if (!key_def_has_collation(def) && !def->has_json_paths) { - /* Precalculated comparators don't use collation */ - for (uint32_t k = 0; - k < sizeof(cmp_wk_arr) / sizeof(cmp_wk_arr[0]); - k++) { - - uint32_t i = 0; - for (; i < def->part_count; i++) { - if (def->parts[i].fieldno != - cmp_wk_arr[k].p[i * 2] || - def->parts[i].type != - cmp_wk_arr[k].p[i * 2 + 1]) { - break; - } - } - if (i == def->part_count) - return cmp_wk_arr[k].f; - } - } - return key_def_is_sequential(def) ? - tuple_compare_with_key_sequential : - compare_with_key_slowpath_funcs[cmp_func_idx]; -} - /* }}} tuple_compare_with_key */ +static void +key_def_set_compare_func_fast(struct key_def *def) +{ + assert(!def->is_nullable); + assert(!def->has_optional_parts); + assert(!def->has_json_paths); + assert(!key_def_has_collation(def)); + + tuple_compare_t cmp = NULL; + tuple_compare_with_key_t cmp_wk = NULL; + bool is_sequential = key_def_is_sequential(def); + + /* + * Use pre-compiled comparators if available, otherwise + * fall back on generic comparators. + */ + for (uint32_t k = 0; k < lengthof(cmp_arr); k++) { + uint32_t i = 0; + for (; i < def->part_count; i++) + if (def->parts[i].fieldno != cmp_arr[k].p[i * 2] || + def->parts[i].type != cmp_arr[k].p[i * 2 + 1]) + break; + if (i == def->part_count && cmp_arr[k].p[i * 2] == UINT32_MAX) { + cmp = cmp_arr[k].f; + break; + } + } + for (uint32_t k = 0; k < lengthof(cmp_wk_arr); k++) { + uint32_t i = 0; + for (; i < def->part_count; i++) { + if (def->parts[i].fieldno != cmp_wk_arr[k].p[i * 2] || + def->parts[i].type != cmp_wk_arr[k].p[i * 2 + 1]) + break; + } + if (i == def->part_count) { + cmp_wk = cmp_wk_arr[k].f; + break; + } + } + if (cmp == NULL) { + cmp = is_sequential ? + tuple_compare_sequential : + tuple_compare_slowpath; + } + if (cmp_wk == NULL) { + cmp_wk = is_sequential ? + tuple_compare_with_key_sequential : + tuple_compare_with_key_slowpath; + } + + def->tuple_compare = cmp; + def->tuple_compare_with_key = cmp_wk; +} + +template +static void +key_def_set_compare_func_plain(struct key_def *def) +{ + assert(!def->has_json_paths); + if (key_def_is_sequential(def)) { + def->tuple_compare = tuple_compare_sequential + ; + def->tuple_compare_with_key = tuple_compare_with_key_sequential + ; + } else { + def->tuple_compare = tuple_compare_slowpath + ; + def->tuple_compare_with_key = tuple_compare_with_key_slowpath + ; + } +} + +template +static void +key_def_set_compare_func_json(struct key_def *def) +{ + assert(def->has_json_paths); + def->tuple_compare = tuple_compare_slowpath + ; + def->tuple_compare_with_key = tuple_compare_with_key_slowpath + ; +} + void key_def_set_compare_func(struct key_def *def) { - def->tuple_compare = tuple_compare_create(def); - def->tuple_compare_with_key = tuple_compare_with_key_create(def); + if (!key_def_has_collation(def) && + !def->is_nullable && !def->has_json_paths) { + key_def_set_compare_func_fast(def); + } else if (!def->has_json_paths) { + if (def->is_nullable && def->has_optional_parts) { + key_def_set_compare_func_plain(def); + } else if (def->is_nullable && !def->has_optional_parts) { + key_def_set_compare_func_plain(def); + } else { + assert(!def->is_nullable && !def->has_optional_parts); + key_def_set_compare_func_plain(def); + } + } else { + if (def->is_nullable && def->has_optional_parts) { + key_def_set_compare_func_json(def); + } else if (def->is_nullable && !def->has_optional_parts) { + key_def_set_compare_func_json(def); + } else { + assert(!def->is_nullable && !def->has_optional_parts); + key_def_set_compare_func_json(def); + } + } }