[tarantool-patches] Re: [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

Hi! Thanks for the patch!

See 7 comments below.

On 22/07/2019 09:43, Kirill Shcherbatov wrote:
> An updated vdbe_field_ref fetcher class use a bitmap of
> initialized slots to use pre-calculated offsets when possible.
> This should speed-up SQL a bit.

1. Please, describe here the problem in more details. Otherwise
it is far from obvious what is wrong with the current version.

> 
> Closes #4267
> ---
> Branch: http://github.com/tarantool/tarantool/tree/kshch/gh-4267-full-power-of-vdbe-field-ref
> Issue: https://github.com/tarantool/tarantool/issues/4267
> 
>  src/box/ck_constraint.c |   6 +-
>  src/box/sql.c           |  16 ++++-
>  src/box/sql.h           |  16 +++--
>  src/box/sql/vdbe.c      | 128 +++++++++++++++++++++++++---------------
>  4 files changed, 112 insertions(+), 54 deletions(-)
> 
> diff --git a/src/box/sql.c b/src/box/sql.c
> index 4c9a4c15b..6c05518b3 100644
> --- a/src/box/sql.c
> +++ b/src/box/sql.c
> @@ -1226,6 +1226,14 @@ sql_ephemeral_space_new(Parse *parser, const char *name)
>  	return space;
>  }
>  
> +uint32_t
> +vbde_field_ref_extra_sizeof(uint32_t max_field_count)
> +{
> +	assert(max_field_count > 0);
> +	return (max_field_count) * sizeof(uint32_t) +

2. Why do you need parentheses for max_field_count?

> +	        bitmap_size(max_field_count + 1);
> +}
> +
>  /**
>   * Initialize a new vdbe_field_ref instance with given tuple
>   * data.
> @@ -1244,8 +1252,14 @@ vdbe_field_ref_create(struct vdbe_field_ref *field_ref, struct tuple *tuple,
>  
>  	const char *field0 = data;
>  	field_ref->field_count = mp_decode_array((const char **) &field0);
> +
> +	uint32_t slots_size = sizeof(uint32_t) * (field_ref->field_count + 1);
> +	field_ref->slot_bitmap = (char *)field_ref->slots + slots_size;
> +	memset(field_ref->slot_bitmap, 0,
> +	       bitmap_size(field_ref->field_count + 1));

3. Why +1?

> +
>  	field_ref->slots[0] = (uint32_t)(field0 - data);
> -	field_ref->rightmost_slot = 0;
> +	bit_set(field_ref->slot_bitmap, 0);
>  }
>  
>  void
> diff --git a/src/box/sql.h b/src/box/sql.h
> index 9ccecf28c..3ad31cb21 100644
> --- a/src/box/sql.h
> +++ b/src/box/sql.h
> @@ -383,6 +382,13 @@ struct vdbe_field_ref {
>  	uint32_t slots[1];
>  };
>  
> +/**
> + * Calculate the size of vdbe_field_ref structure
> + * that manages up to max_field_count fields.

4. But it is not size of the whole structure. Only size
of a tail memory block.

> + */
> +uint32_t
> +vbde_field_ref_extra_sizeof(uint32_t max_field_count);
> +
>  /**
>   * Initialize a new vdbe_field_ref instance with given tuple
>   * data.
> diff --git a/src/box/sql/vdbe.c b/src/box/sql/vdbe.c
> index 6a4a303b9..0148b0297 100644
> --- a/src/box/sql/vdbe.c
> +++ b/src/box/sql/vdbe.c
> @@ -597,6 +599,23 @@ mem_type_to_str(const struct Mem *p)
>  	}
>  }
>  
> +static uint32_t
> +vdbe_field_ref_closest_slotno(struct vdbe_field_ref *field_ref,
> +			      uint32_t fieldno)
> +{
> +	uint32_t sz = bitmap_size(field_ref->field_count);
> +	struct bit_iterator it;
> +	bit_iterator_init(&it, field_ref->slot_bitmap, sz, true);
> +	size_t prev, curr;
> +	for (prev = curr = bit_iterator_next(&it);
> +		curr < fieldno && curr < SIZE_MAX;
> +		curr = bit_iterator_next(&it)) {

5. The alignment is broken.

In addition, have you seen bit_iterator_init and bit_iterator_next?
They are huge. They do so many actions, that perhaps it would be
faster to decode MessagePack. Could you bench if it works really faster
now? The most notable improvement should be for the case, when
tuple fields are big complex objects (array, maps), and mp_next(&field)
becomes a really expensive operation.

I understand, that it is hard to microbench this in Lua or C, so I
propose to write a Lua bench, and to add time measurements right into
the C code
- before and after sql_prepare_and_execute;
- before and after vdbe_field_ref_fetch.

In Lua we will see ~ overall improvement (I hope),
around sql_prepare_and_execute we will see results not affected by
Lua, and around vdbe_field_ref_fetch we will see the true impact. 

> +		prev = curr;
> +	}
> +	assert(prev < SIZE_MAX);
> +	return prev;
> +}
> +
>  /**
>   * Try to get a current tuple field using its field map.
>   * @param field_ref The vdbe_field_ref instance to use.
> @@ -610,18 +629,63 @@ static const void *
>  vdbe_field_ref_fast_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno,
>  			  uint32_t *field_size)

6. I guess it is not a fast path anymore, because you moved all the paths
here, including the case when fieldno is not in the format. The function
should be renamed to something appropriate, please.

>  {
> -	if (field_ref->tuple == NULL)
> -		return NULL;
> -	struct tuple_format *format = tuple_format(field_ref->tuple);
> -	if (fieldno >= tuple_format_field_count(format) ||
> -	    tuple_format_field(format, fieldno)->offset_slot ==
> -	    TUPLE_OFFSET_SLOT_NIL)
> -		return NULL;
> -	const char *field = tuple_field(field_ref->tuple, fieldno);
> -	const char *end = field;
> -	mp_next(&end);
> -	*field_size = end - field;
> -	return field;
> +	struct tuple_format *format = field_ref->tuple != NULL ?
> +				      tuple_format(field_ref->tuple) : NULL;
> +	uint32_t format_field_count =
> +		 format != NULL ? tuple_format_field_count(format) : 0;
> +
> +	const char *field_begin = NULL, *field_end = NULL;
> +	if (bit_test(field_ref->slot_bitmap, fieldno)) {
> +		/*
> +		 * Current field has been already
> +		 * touched before.
> +		 */
> +		field_begin = field_ref->data + field_ref->slots[fieldno];
> +	} else {
> +		struct tuple_field *field =
> +			fieldno < format_field_count ?
> +			tuple_format_field(format, fieldno) : NULL;
> +		if (field != NULL &&
> +		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
> +			field_begin = tuple_field(field_ref->tuple, fieldno);
> +		} else {
> +			/*
> +			 * Lookup for the closest previously
> +			 * touched field.
> +			 */
> +			uint32_t prev =
> +				vdbe_field_ref_closest_slotno(field_ref,
> +							      fieldno);
> +			field_begin = field_ref->data + field_ref->slots[prev];
> +			for (; prev < fieldno; prev++)
> +				mp_next(&field_begin);
> +		}
> +		field_ref->slots[fieldno] =
> +			(uint32_t)(field_begin - field_ref->data);
> +		bit_set(field_ref->slot_bitmap, fieldno);
> +	}

7. The blocks above and below are basically the same. Please, move one of them to
a function, and use it here.

> +
> +	if (bit_test(field_ref->slot_bitmap, fieldno + 1)) {
> +		/* Next field has been already touched before. */
> +		field_end = field_ref->data + field_ref->slots[fieldno + 1];
> +	} else {
> +		struct tuple_field *field =
> +			fieldno + 1 < format_field_count ?
> +			tuple_format_field(format, fieldno + 1) : NULL;
> +		if (field != NULL &&
> +		    field->offset_slot != TUPLE_OFFSET_SLOT_NIL) {
> +			field_end = tuple_field(field_ref->tuple, fieldno + 1);
> +		} else {
> +			field_end = field_begin;
> +			mp_next(&field_end);
> +		}
> +		field_ref->slots[fieldno + 1] =
> +			(uint32_t)(field_end - field_ref->data);
> +		bit_set(field_ref->slot_bitmap, fieldno + 1);
> +	}
> +
> +	*field_size = field_end - field_begin;
> +	return field_begin;
>  }
>  
>  /**