[Tarantool-patches] [PATCH v2 0/2] reduce performance degradation introduced by JSON path indices

[Tarantool-patches] [PATCH v2 0/2] reduce performance degradation introduced by JSON path indices

[Serge Petrenko]

https://github.com/tarantool/tarantool/issues/4774
sp/gh-4774-multikey-refactoring

The patchset fixes two degradations found by measuring snapshot recovery time
for a 1.5G snapshot containing 30M tuples in a memtx space with a simple primary
key and one secondary key over 4 integer and one string field.

The first degradation manifests itself during snapshot recovery phase (the one
with "3.5M rows processed" messages) and is connected to `memtx_tuple_new`
slowdown due to unoptimised `tuple_field_map_create`.

First patch deals with this degradation and manages to restore almost all
performance lost since 1.10. (The patched version is only 11% slower than 1.10,
while the current master is 39% slower on this phase).

The second degradation appears during next snapshot recovery phase, secondary
index building. Here the degradation is rooted in slow tuple field access via
tuple_field_raw().

The second patch deals with this issue and manages to restore all the lost
performance. (The patched version is 10% faster(!) than 1.10 while the current
master is 27% slower).
To be honest, the increase in speed between 1.10 and the second patch must be
due to tuple comparison hints. Otherwise the patched version should be even with
1.10, since it uses literally the same code as 1.10 did (with minor changes).

Changes in v2:
  - win some more performance by accessing top level
    tuple format fields directly (bypass the json_tree_lookup)
  - instead of relying on offset_slot_hint in the second patch,
    rewrite tuple_field_raw so that it doesn't check for path
    this wins a whopping 24% of perf compared to the previous
    version.

Serge Petrenko (2):
  box: speed up tuple_field_map_create
  box:refactor tuple_field_raw to omit path checks

 src/box/tuple.h        | 29 ++++++++++++++--
 src/box/tuple_format.c | 75 ++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 102 insertions(+), 2 deletions(-)

-- 
2.24.3 (Apple Git-128)

[Tarantool-patches] [PATCH v2 1/2] box: speed up tuple_field_map_create

[Serge Petrenko]

Since the introduction of JSON path indices tuple_init_field_map, which
was quite a simple routine traversing a tuple and storing its field data
offsets in the field map, was renamed to tuple_field_map_create and
optimised for working with JSON path indices.

The main difference is that tuple format fields are now organised in a
tree rather than an array, and the tuple itself may have indexed fields,
which are not plain array members, but rather members of some sub-array
or map. This requires more complex iteration over tuple format fields
and additional tuple parsing.

All the changes were, however, unneeded for tuple formats not supporting
fields indexed by JSON paths.

Rework tuple_field_map_create so that it doesn't go through all the
unnecessary JSON path-related checks for simple cases and restore most
of the lost performance.

Below are some benchmark results for the same workload that pointed to
the degradation initially.
Snapshot recovery time on RelWithDebInfo build for a 1.5G snapshot
containing a single memtx space with one secondary index over 4 integer
and 1 string field:

        Version            | Time (s) | Difference relative to 1.10
---------------------------|----------|----------------------------
1.10 (the golden standard) |    28    |             -/-
2.x (degradation)          |    39    |            + 39%
2.x (patched)              |    31    |            + 11%

Profile shows that the main difference is in memtx_tuple_new due to
tuple_init_field_map/tuple_field_map_create performance difference.

Numbers below show cumulative time spent in tuple_init_field_map (1.10) /
tuple_field_map_create (unpatched) / tuple_field_map_create (patched).
2.44 s / 8.61 s / 3.19 s

More benchmark results can be seen at #4774

Part of #4774

wip. optimisation.
---
 src/box/tuple_format.c | 75 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)

diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c
index 9b817d3cf..6c9b2a255 100644
--- a/src/box/tuple_format.c
+++ b/src/box/tuple_format.c
@@ -852,6 +852,72 @@ tuple_format1_can_store_format2_tuples(struct tuple_format *format1,
 	return true;
 }
 
+static int
+tuple_format_required_fields_validate(struct tuple_format *format,
+				      void *required_fields,
+				      uint32_t required_fields_sz);
+
+static int
+tuple_field_map_create_plain(struct tuple_format *format, const char *tuple,
+			     bool validate, struct field_map_builder *builder)
+{
+	struct region *region = &fiber()->gc;
+	const char *pos = tuple;
+	uint32_t defined_field_count = mp_decode_array(&pos);
+	if (validate && format->exact_field_count > 0 &&
+	    format->exact_field_count != defined_field_count) {
+		diag_set(ClientError, ER_EXACT_FIELD_COUNT,
+			 (unsigned) defined_field_count,
+			 (unsigned) format->exact_field_count);
+		return -1;
+	}
+	defined_field_count = MIN(defined_field_count,
+				  tuple_format_field_count(format));
+
+	void *required_fields = NULL;
+	uint32_t required_fields_sz = bitmap_size(format->total_field_count);
+
+	if (unlikely(defined_field_count == 0)) {
+		required_fields = format->required_fields;
+		goto end;
+	}
+
+	if (validate) {
+		required_fields = region_alloc(region, required_fields_sz);
+		memcpy(required_fields, format->required_fields,
+		       required_fields_sz);
+	}
+
+	struct tuple_field *field;
+	struct json_token **token = format->fields.root.children;
+	for (uint32_t i = 0; i < defined_field_count; i++, token++, mp_next(&pos)) {
+		field = json_tree_entry(*token, struct tuple_field, token);
+		if (validate) {
+			bool nullable = tuple_field_is_nullable(field);
+			if(!field_mp_type_is_compatible(field->type, pos,
+							nullable)) {
+				diag_set(ClientError, ER_FIELD_TYPE,
+					 tuple_field_path(field),
+					 field_type_strs[field->type]);
+				return -1;
+			}
+			bit_clear(required_fields, field->id);
+		}
+		if (field->offset_slot != TUPLE_OFFSET_SLOT_NIL &&
+		    field_map_builder_set_slot(builder, field->offset_slot,
+					       pos - tuple, MULTIKEY_NONE,
+					       0, NULL) != 0) {
+			return -1;
+		}
+	}
+
+end:
+	return validate ?
+	       tuple_format_required_fields_validate(format, required_fields,
+						     required_fields_sz) :
+	       0;
+}
+
 /** @sa declaration for details. */
 int
 tuple_field_map_create(struct tuple_format *format, const char *tuple,
@@ -864,6 +930,15 @@ tuple_field_map_create(struct tuple_format *format, const char *tuple,
 	if (tuple_format_field_count(format) == 0)
 		return 0; /* Nothing to initialize */
 
+	/*
+	 * In case tuple format doesn't contain fields accessed by JSON paths,
+	 * tuple field traversal may be simplified.
+	 */
+	if (format->fields_depth == 1) {
+		return tuple_field_map_create_plain(format, tuple, validate,
+						    builder);
+	}
+
 	uint32_t field_count;
 	struct tuple_format_iterator it;
 	uint8_t flags = validate ? TUPLE_FORMAT_ITERATOR_VALIDATE : 0;
-- 
2.24.3 (Apple Git-128)

[Tarantool-patches] [PATCH v2 2/2] box:refactor tuple_field_raw to omit path checks

[Serge Petrenko]

tuple_field_raw is an alias to tuple_field_raw_by_path with zero path.
This involves multiple path != NULL checks which aren't needed for tuple
field access by field number. The checks make this function rather slow
compared to its 1.10 counterpart (see results below).

In order to fix perf problems when JSON path indices aren't involved,
factor out the part of tuple_field_raw_by_path which is responsible for
direct field access by number and place it in tuple_field_raw.

This patch was tested by snapshot recovery part involving secondary
index building for a 1.5G snapshot with
one space and one secondary index over 4 integer and one string field.
Comparison table is below:

    Version    | time(seconds)  | Change relative to 1.10
---------------|----------------|------------------------
1.10           |      2:24      |           -/-
2.x(unpatched) |      3:03      |          + 27%
2.x (patched)  |      2:10      |          - 10%

Numbers below show cumulative time spent in tuple_compare_slowpath,
for 1.10 / 2.x(unpatched) / 2.x(patched) for 15, 19 and 14 second
profiles respectively: 13.9 / 17.8 / 12.5.

tuple_field_raw() isn't measured directly, since it's inlined, but all
its uses come from tuple_compare_slowpath.

As the results show, we manage to be even faster, than 1.10 used to be
in this test. This must be due to tuple comparison hints, which are
present only in 2.x.

Closes #4774
---
 src/box/tuple.h | 29 +++++++++++++++++++++++++++--
 1 file changed, 27 insertions(+), 2 deletions(-)

diff --git a/src/box/tuple.h b/src/box/tuple.h
index 755aee506..fd373fdbf 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -697,8 +697,33 @@ static inline const char *
 tuple_field_raw(struct tuple_format *format, const char *tuple,
 		const uint32_t *field_map, uint32_t field_no)
 {
-	return tuple_field_raw_by_path(format, tuple, field_map, field_no,
-				       NULL, 0, NULL, MULTIKEY_NONE);
+	if (likely(field_no < format->index_field_count)) {
+		int32_t offset_slot;
+		uint32_t offset = 0;
+		struct tuple_field *field;
+		if (field_no == 0) {
+			mp_decode_array(&tuple);
+			return tuple;
+		}
+		struct json_token *token = format->fields.root.children[field_no];
+		field = json_tree_entry(token, struct tuple_field, token);
+		offset_slot = field->offset_slot;
+		if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
+			goto parse;
+		offset = field_map_get_offset(field_map, offset_slot, MULTIKEY_NONE);
+		if (offset == 0)
+			return NULL;
+		tuple += offset;
+	} else {
+parse:
+		ERROR_INJECT(ERRINJ_TUPLE_FIELD, return NULL);
+		uint32_t field_count = mp_decode_array(&tuple);
+		if (unlikely(field_no >= field_count))
+			return NULL;
+		for ( ; field_no > 0; field_no--)
+			mp_next(&tuple);
+	}
+	return tuple;
 }
 
 /**
-- 
2.24.3 (Apple Git-128)

Re: [Tarantool-patches] [PATCH v2 1/2] box: speed up tuple_field_map_create

[Vladislav Shpilevoy]

Hi! Thanks for the patch!

On 30.11.2020 12:14, Serge Petrenko via Tarantool-patches wrote:
> Since the introduction of JSON path indices tuple_init_field_map, which
> was quite a simple routine traversing a tuple and storing its field data
> offsets in the field map, was renamed to tuple_field_map_create and
> optimised for working with JSON path indices.
> 
> The main difference is that tuple format fields are now organised in a
> tree rather than an array, and the tuple itself may have indexed fields,
> which are not plain array members, but rather members of some sub-array
> or map. This requires more complex iteration over tuple format fields
> and additional tuple parsing.
> 
> All the changes were, however, unneeded for tuple formats not supporting
> fields indexed by JSON paths.
> 
> Rework tuple_field_map_create so that it doesn't go through all the
> unnecessary JSON path-related checks for simple cases and restore most
> of the lost performance.
> 
> Below are some benchmark results for the same workload that pointed to
> the degradation initially.
> Snapshot recovery time on RelWithDebInfo build for a 1.5G snapshot
> containing a single memtx space with one secondary index over 4 integer
> and 1 string field:
> 
>         Version            | Time (s) | Difference relative to 1.10
> ---------------------------|----------|----------------------------
> 1.10 (the golden standard) |    28    |             -/-
> 2.x (degradation)          |    39    |            + 39%
> 2.x (patched)              |    31    |            + 11%
> 
> Profile shows that the main difference is in memtx_tuple_new due to
> tuple_init_field_map/tuple_field_map_create performance difference.
> 
> Numbers below show cumulative time spent in tuple_init_field_map (1.10) /
> tuple_field_map_create (unpatched) / tuple_field_map_create (patched).
> 2.44 s / 8.61 s / 3.19 s
> 
> More benchmark results can be seen at #4774
> 
> Part of #4774
> 
> wip. optimisation.

You may want to delete the last sentence.

Other than that, looks good.

Re: [Tarantool-patches] [PATCH v2 2/2] box:refactor tuple_field_raw to omit path checks

[Vladislav Shpilevoy]

Thanks for the patch!

Please, add a whitespace after 'box:' in the commit title.

The patch looks good. See one another possible opt below.
But the patch already is fine, and the opt is dubious - you
can ignore it if you think all is good already.

On 30.11.2020 12:14, Serge Petrenko wrote:
> tuple_field_raw is an alias to tuple_field_raw_by_path with zero path.
> This involves multiple path != NULL checks which aren't needed for tuple
> field access by field number. The checks make this function rather slow
> compared to its 1.10 counterpart (see results below).
> 
> In order to fix perf problems when JSON path indices aren't involved,
> factor out the part of tuple_field_raw_by_path which is responsible for
> direct field access by number and place it in tuple_field_raw.
> 
> This patch was tested by snapshot recovery part involving secondary
> index building for a 1.5G snapshot with
> one space and one secondary index over 4 integer and one string field.
> Comparison table is below:
> 
>     Version    | time(seconds)  | Change relative to 1.10
> ---------------|----------------|------------------------
> 1.10           |      2:24      |           -/-
> 2.x(unpatched) |      3:03      |          + 27%
> 2.x (patched)  |      2:10      |          - 10%
> 
> Numbers below show cumulative time spent in tuple_compare_slowpath,
> for 1.10 / 2.x(unpatched) / 2.x(patched) for 15, 19 and 14 second
> profiles respectively: 13.9 / 17.8 / 12.5.
> 
> tuple_field_raw() isn't measured directly, since it's inlined, but all
> its uses come from tuple_compare_slowpath.
> 
> As the results show, we manage to be even faster, than 1.10 used to be
> in this test. This must be due to tuple comparison hints, which are
> present only in 2.x.
> 
> Closes #4774
> ---
>  src/box/tuple.h | 29 +++++++++++++++++++++++++++--
>  1 file changed, 27 insertions(+), 2 deletions(-)
> 
> diff --git a/src/box/tuple.h b/src/box/tuple.h
> index 755aee506..fd373fdbf 100644
> --- a/src/box/tuple.h
> +++ b/src/box/tuple.h
> @@ -697,8 +697,33 @@ static inline const char *
>  tuple_field_raw(struct tuple_format *format, const char *tuple,
>  		const uint32_t *field_map, uint32_t field_no)
>  {
> -	return tuple_field_raw_by_path(format, tuple, field_map, field_no,
> -				       NULL, 0, NULL, MULTIKEY_NONE);
> +	if (likely(field_no < format->index_field_count)) {
> +		int32_t offset_slot;
> +		uint32_t offset = 0;
> +		struct tuple_field *field;
> +		if (field_no == 0) {
> +			mp_decode_array(&tuple);
> +			return tuple;
> +		}
> +		struct json_token *token = format->fields.root.children[field_no];
> +		field = json_tree_entry(token, struct tuple_field, token);
> +		offset_slot = field->offset_slot;
> +		if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
> +			goto parse;
> +		offset = field_map_get_offset(field_map, offset_slot, MULTIKEY_NONE);

What if we would remove multikey argument from field_map_get_offset,
and introduce a new function field_map_get_offset_mk?

field_map_get_offset would do a plain load_u32 without any ifs.
field_map_get_offset_mk would check multikey like now, but we won't
use it here.

> +		if (offset == 0)
> +			return NULL;> +		tuple += offset;
> +	} else {
> +parse:
> +		ERROR_INJECT(ERRINJ_TUPLE_FIELD, return NULL);
> +		uint32_t field_count = mp_decode_array(&tuple);
> +		if (unlikely(field_no >= field_count))
> +			return NULL;
> +		for ( ; field_no > 0; field_no--)
> +			mp_next(&tuple);
> +	}
> +	return tuple;
>  }
>  
>  /**

Re: [Tarantool-patches] [PATCH v2 1/2] box: speed up tuple_field_map_create

[Serge Petrenko]

02.12.2020 01:01, Vladislav Shpilevoy пишет:
> Hi! Thanks for the patch!
>
> On 30.11.2020 12:14, Serge Petrenko via Tarantool-patches wrote:
>> Since the introduction of JSON path indices tuple_init_field_map, which
>> was quite a simple routine traversing a tuple and storing its field data
>> offsets in the field map, was renamed to tuple_field_map_create and
>> optimised for working with JSON path indices.
>>
>> The main difference is that tuple format fields are now organised in a
>> tree rather than an array, and the tuple itself may have indexed fields,
>> which are not plain array members, but rather members of some sub-array
>> or map. This requires more complex iteration over tuple format fields
>> and additional tuple parsing.
>>
>> All the changes were, however, unneeded for tuple formats not supporting
>> fields indexed by JSON paths.
>>
>> Rework tuple_field_map_create so that it doesn't go through all the
>> unnecessary JSON path-related checks for simple cases and restore most
>> of the lost performance.
>>
>> Below are some benchmark results for the same workload that pointed to
>> the degradation initially.
>> Snapshot recovery time on RelWithDebInfo build for a 1.5G snapshot
>> containing a single memtx space with one secondary index over 4 integer
>> and 1 string field:
>>
>>          Version            | Time (s) | Difference relative to 1.10
>> ---------------------------|----------|----------------------------
>> 1.10 (the golden standard) |    28    |             -/-
>> 2.x (degradation)          |    39    |            + 39%
>> 2.x (patched)              |    31    |            + 11%
>>
>> Profile shows that the main difference is in memtx_tuple_new due to
>> tuple_init_field_map/tuple_field_map_create performance difference.
>>
>> Numbers below show cumulative time spent in tuple_init_field_map (1.10) /
>> tuple_field_map_create (unpatched) / tuple_field_map_create (patched).
>> 2.44 s / 8.61 s / 3.19 s
>>
>> More benchmark results can be seen at #4774
>>
>> Part of #4774
>>
>> wip. optimisation.
> You may want to delete the last sentence.

Thanks for the review!

I do. Fixed.

>
> Other than that, looks good.

-- 
Serge Petrenko

Re: [Tarantool-patches] [PATCH v2 2/2] box:refactor tuple_field_raw to omit path checks

[Serge Petrenko]

02.12.2020 01:03, Vladislav Shpilevoy пишет:
> Thanks for the patch!
>
> Please, add a whitespace after 'box:' in the commit title.


Thanks for the review!

Fixed.

>
> The patch looks good. See one another possible opt below.
> But the patch already is fine, and the opt is dubious - you
> can ignore it if you think all is good already.
>
> On 30.11.2020 12:14, Serge Petrenko wrote:
>> tuple_field_raw is an alias to tuple_field_raw_by_path with zero path.
>> This involves multiple path != NULL checks which aren't needed for tuple
>> field access by field number. The checks make this function rather slow
>> compared to its 1.10 counterpart (see results below).
>>
>> In order to fix perf problems when JSON path indices aren't involved,
>> factor out the part of tuple_field_raw_by_path which is responsible for
>> direct field access by number and place it in tuple_field_raw.
>>
>> This patch was tested by snapshot recovery part involving secondary
>> index building for a 1.5G snapshot with
>> one space and one secondary index over 4 integer and one string field.
>> Comparison table is below:
>>
>>      Version    | time(seconds)  | Change relative to 1.10
>> ---------------|----------------|------------------------
>> 1.10           |      2:24      |           -/-
>> 2.x(unpatched) |      3:03      |          + 27%
>> 2.x (patched)  |      2:10      |          - 10%
>>
>> Numbers below show cumulative time spent in tuple_compare_slowpath,
>> for 1.10 / 2.x(unpatched) / 2.x(patched) for 15, 19 and 14 second
>> profiles respectively: 13.9 / 17.8 / 12.5.
>>
>> tuple_field_raw() isn't measured directly, since it's inlined, but all
>> its uses come from tuple_compare_slowpath.
>>
>> As the results show, we manage to be even faster, than 1.10 used to be
>> in this test. This must be due to tuple comparison hints, which are
>> present only in 2.x.
>>
>> Closes #4774
>> ---
>>   src/box/tuple.h | 29 +++++++++++++++++++++++++++--
>>   1 file changed, 27 insertions(+), 2 deletions(-)
>>
>> diff --git a/src/box/tuple.h b/src/box/tuple.h
>> index 755aee506..fd373fdbf 100644
>> --- a/src/box/tuple.h
>> +++ b/src/box/tuple.h
>> @@ -697,8 +697,33 @@ static inline const char *
>>   tuple_field_raw(struct tuple_format *format, const char *tuple,
>>   		const uint32_t *field_map, uint32_t field_no)
>>   {
>> -	return tuple_field_raw_by_path(format, tuple, field_map, field_no,
>> -				       NULL, 0, NULL, MULTIKEY_NONE);
>> +	if (likely(field_no < format->index_field_count)) {
>> +		int32_t offset_slot;
>> +		uint32_t offset = 0;
>> +		struct tuple_field *field;
>> +		if (field_no == 0) {
>> +			mp_decode_array(&tuple);
>> +			return tuple;
>> +		}
>> +		struct json_token *token = format->fields.root.children[field_no];
>> +		field = json_tree_entry(token, struct tuple_field, token);
>> +		offset_slot = field->offset_slot;
>> +		if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
>> +			goto parse;
>> +		offset = field_map_get_offset(field_map, offset_slot, MULTIKEY_NONE);
> What if we would remove multikey argument from field_map_get_offset,
> and introduce a new function field_map_get_offset_mk?
>
> field_map_get_offset would do a plain load_u32 without any ifs.
> field_map_get_offset_mk would check multikey like now, but we won't
> use it here.

Ok. Tried the diff below. Tested 2 times. 1st time 2:13, 2nd time 2:06.

Average 2:09.5. Same as without the diff.


==================================

diff --git a/src/box/field_map.h b/src/box/field_map.h
index d8ef726a1..6e33e888d 100644
--- a/src/box/field_map.h
+++ b/src/box/field_map.h
@@ -172,6 +172,17 @@ field_map_get_offset(const uint32_t *field_map, 
int32_t offset_slot,
         return offset;
  }

+static inline uint32_t
+field_map_get_offset_plain(const uint32_t *field_map, int32_t offset_slot)
+{
+       /*
+        * Can not access field_map as a normal uint32 array
+        * because its alignment may be < 4 bytes. Need to use
+        * unaligned store-load operations explicitly.
+        */
+       uint32_t offset = load_u32(&field_map[offset_slot]);
+       return offset;
+}
  /**
   * Initialize field_map_builder.
   *
diff --git a/src/box/tuple.h b/src/box/tuple.h
index fd373fdbf..c79b0dd87 100644
--- a/src/box/tuple.h
+++ b/src/box/tuple.h
@@ -710,7 +710,7 @@ tuple_field_raw(struct tuple_format *format, const 
char *tuple,
                 offset_slot = field->offset_slot;
                 if (offset_slot == TUPLE_OFFSET_SLOT_NIL)
                         goto parse;
-               offset = field_map_get_offset(field_map, offset_slot, 
MULTIKEY_NONE);
+               offset = field_map_get_offset_plain(field_map, offset_slot);
                 if (offset == 0)
                         return NULL;
                 tuple += offset;

>
>> +		if (offset == 0)
>> +			return NULL;> +		tuple += offset;
>> +	} else {
>> +parse:
>> +		ERROR_INJECT(ERRINJ_TUPLE_FIELD, return NULL);
>> +		uint32_t field_count = mp_decode_array(&tuple);
>> +		if (unlikely(field_no >= field_count))
>> +			return NULL;
>> +		for ( ; field_no > 0; field_no--)
>> +			mp_next(&tuple);
>> +	}
>> +	return tuple;
>>   }
>>   
>>   /**

-- 
Serge Petrenko

Re: [Tarantool-patches] [PATCH v2 0/2] reduce performance degradation introduced by JSON path indices

[Vladislav Shpilevoy]

Thanks for the patchset!

LGTM. Please, proceed to the second review with Nikita.
Perhaps it would be simpler for him to review a clean
v3 version in a fresh email thread.