[tarantool-patches] Re: [PATCH v6 1/3] box: refactor key_def_set_compare_func routine
Vladimir Davydov
vdavydov.dev at gmail.com
Tue Mar 19 22:38:37 MSK 2019
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,
> - true>;
> - } else {
> - return tuple_compare_with_key_sequential<true,
> - 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 at gmail.com>
From: Vladimir Davydov <vdavydov.dev at gmail.com>
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<false, false, false>,
- tuple_compare_slowpath<true, false, false>,
- tuple_compare_slowpath<false, true, false>,
- tuple_compare_slowpath<true, true, false>,
- tuple_compare_slowpath<false, false, true>,
- tuple_compare_slowpath<true, false, true>,
- tuple_compare_slowpath<false, true, true>,
- tuple_compare_slowpath<true, true, true>
-};
-
-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<true, true>;
- else
- return tuple_compare_sequential<true, false>;
- } 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<false, false> :
- 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<false, false, false>,
- tuple_compare_with_key_slowpath<true, false, false>,
- tuple_compare_with_key_slowpath<false, true, false>,
- tuple_compare_with_key_slowpath<true, true, false>,
- tuple_compare_with_key_slowpath<false, false, true>,
- tuple_compare_with_key_slowpath<true, false, true>,
- tuple_compare_with_key_slowpath<false, true, true>,
- tuple_compare_with_key_slowpath<true, true, true>
-};
-
-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<true,
- true>;
- } else {
- return tuple_compare_with_key_sequential<true,
- false>;
- }
- } 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<false, false> :
- 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<false, false> :
+ tuple_compare_slowpath<false, false, false>;
+ }
+ if (cmp_wk == NULL) {
+ cmp_wk = is_sequential ?
+ tuple_compare_with_key_sequential<false, false> :
+ tuple_compare_with_key_slowpath<false, false, false>;
+ }
+
+ def->tuple_compare = cmp;
+ def->tuple_compare_with_key = cmp_wk;
+}
+
+template<bool is_nullable, bool has_optional_parts>
+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
+ <is_nullable, has_optional_parts>;
+ def->tuple_compare_with_key = tuple_compare_with_key_sequential
+ <is_nullable, has_optional_parts>;
+ } else {
+ def->tuple_compare = tuple_compare_slowpath
+ <is_nullable, has_optional_parts, false>;
+ def->tuple_compare_with_key = tuple_compare_with_key_slowpath
+ <is_nullable, has_optional_parts, false>;
+ }
+}
+
+template<bool is_nullable, bool has_optional_parts>
+static void
+key_def_set_compare_func_json(struct key_def *def)
+{
+ assert(def->has_json_paths);
+ def->tuple_compare = tuple_compare_slowpath
+ <is_nullable, has_optional_parts, true>;
+ def->tuple_compare_with_key = tuple_compare_with_key_slowpath
+ <is_nullable, has_optional_parts, true>;
+}
+
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<true, true>(def);
+ } else if (def->is_nullable && !def->has_optional_parts) {
+ key_def_set_compare_func_plain<true, false>(def);
+ } else {
+ assert(!def->is_nullable && !def->has_optional_parts);
+ key_def_set_compare_func_plain<false, false>(def);
+ }
+ } else {
+ if (def->is_nullable && def->has_optional_parts) {
+ key_def_set_compare_func_json<true, true>(def);
+ } else if (def->is_nullable && !def->has_optional_parts) {
+ key_def_set_compare_func_json<true, false>(def);
+ } else {
+ assert(!def->is_nullable && !def->has_optional_parts);
+ key_def_set_compare_func_json<false, false>(def);
+ }
+ }
}
More information about the Tarantool-patches
mailing list