From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from localhost (localhost [127.0.0.1]) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTP id CABA3220B1 for ; Mon, 22 Jul 2019 03:43:40 -0400 (EDT) Received: from turing.freelists.org ([127.0.0.1]) by localhost (turing.freelists.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id N1rQuQ2y76JX for ; Mon, 22 Jul 2019 03:43:40 -0400 (EDT) Received: from smtp49.i.mail.ru (smtp49.i.mail.ru [94.100.177.109]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by turing.freelists.org (Avenir Technologies Mail Multiplex) with ESMTPS id 6766E2204F for ; Mon, 22 Jul 2019 03:43:38 -0400 (EDT) From: Kirill Shcherbatov Subject: [tarantool-patches] [PATCH v1 1/1] sql: improve vdbe_field_ref fetcher Date: Mon, 22 Jul 2019 10:43:32 +0300 Message-Id: <978c68684414e4df06fa7b37697c3f348d96cf5b.1563781318.git.kshcherbatov@tarantool.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: tarantool-patches-bounce@freelists.org Errors-to: tarantool-patches-bounce@freelists.org Reply-To: tarantool-patches@freelists.org List-Help: List-Unsubscribe: List-software: Ecartis version 1.0.0 List-Id: tarantool-patches List-Subscribe: List-Owner: List-post: List-Archive: To: tarantool-patches@freelists.org, v.shpilevoy@tarantool.org Cc: Kirill Shcherbatov 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. 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/ck_constraint.c b/src/box/ck_constraint.c index 1cde27022..48890e5df 100644 --- a/src/box/ck_constraint.c +++ b/src/box/ck_constraint.c @@ -188,8 +188,10 @@ ck_constraint_on_replace_trigger(struct trigger *trigger, void *event) struct space *space = stmt->space; assert(space != NULL); - uint32_t field_ref_sz = sizeof(struct vdbe_field_ref) + - sizeof(uint32_t) * space->def->field_count; + uint32_t field_ref_extra_sz = + vbde_field_ref_extra_sizeof(space->def->field_count); + uint32_t field_ref_sz = + sizeof(struct vdbe_field_ref) + field_ref_extra_sz; struct vdbe_field_ref *field_ref = region_alloc(&fiber()->gc, field_ref_sz); if (field_ref == NULL) { 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) + + 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)); + 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 @@ -360,6 +360,8 @@ sqlSrcListDelete(struct sql *db, struct SrcList *list); * | struct vdbe_field_ref | * +-------------------------+ * | RESERVED MEMORY | + * | (slots) | + * | (slot_bitmap) | * +-------------------------+ */ struct vdbe_field_ref { @@ -371,11 +373,8 @@ struct vdbe_field_ref { uint32_t data_sz; /** Count of fields in tuple. */ uint32_t field_count; - /** - * Index of the rightmost initialized slot in slots - * array. - */ - uint32_t rightmost_slot; + /** Bitmap of initialized slots. */ + void *slot_bitmap; /** * Array of offsets of tuple fields. * Only values <= rightmost_slot are valid. @@ -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. + */ +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 @@ -234,8 +234,9 @@ allocateCursor( int nByte; VdbeCursor *pCx = 0; - nByte = - ROUND8(sizeof(VdbeCursor)) + sizeof(u32)*nField + + uint32_t field_ref_extra_sz = + ROUND8(vbde_field_ref_extra_sizeof(nField)); + nByte = ROUND8(sizeof(VdbeCursor)) + field_ref_extra_sz + (eCurType==CURTYPE_TARANTOOL ? ROUND8(sizeof(BtCursor)) : 0); assert(iCur>=0 && iCurnCursor); @@ -250,7 +251,8 @@ allocateCursor( pCx->nField = nField; if (eCurType==CURTYPE_TARANTOOL) { pCx->uc.pCursor = (BtCursor*) - &pMem->z[ROUND8(sizeof(VdbeCursor))+sizeof(u32)*nField]; + &pMem->z[ROUND8(sizeof(VdbeCursor))+ + field_ref_extra_sz]; sqlCursorZero(pCx->uc.pCursor); } } @@ -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)) { + 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) { - 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); + } + + 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; } /** @@ -643,37 +707,9 @@ vdbe_field_ref_fetch(struct vdbe_field_ref *field_ref, uint32_t fieldno, UPDATE_MAX_BLOBSIZE(dest_mem); return 0; } - - const char *data; - if (field_ref->rightmost_slot <= fieldno) { - uint32_t field_sz; - data = vdbe_field_ref_fast_fetch(field_ref, fieldno, - &field_sz); - if (data != NULL) { - /* - * Special case for tarantool spaces: for - * indexed fields a tuple field map can be - * used. Else there is no sense in - * tuple_field usage, because it makes - * foreach field { mp_next(); } to find - * a field. In such a case sql is - * better - it saves offsets to all fields - * visited in mp_next() cycle. - */ - uint32_t offset = (uint32_t)(data - field_ref->data); - slots[fieldno] = offset; - slots[fieldno + 1] = offset + field_sz; - } else { - uint32_t i = field_ref->rightmost_slot; - data = field_ref->data + slots[i]; - do { - mp_next(&data); - slots[++i] = (uint32_t)(data - field_ref->data); - } while (i <= fieldno); - field_ref->rightmost_slot = i; - } - } - + uint32_t field_sz; + const char *data = vdbe_field_ref_fast_fetch(field_ref, fieldno, + &field_sz); assert(sqlVdbeCheckMemInvariants(dest_mem) != 0); uint32_t dummy; data = field_ref->data + slots[fieldno]; -- 2.22.0