Re: [tarantool-patches] Re: [PATCH v6 1/3] box: refactor key_def_set_compare_func routine

[Vladimir Davydov <vdavydov.dev@gmail.com>]

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@gmail.com>
From: Vladimir Davydov <vdavydov.dev@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);
+		}
+	}
 }