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 43CB627008 for ; Mon, 6 Aug 2018 08:27:08 -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 QjeWrAs80X1h for ; Mon, 6 Aug 2018 08:27:07 -0400 (EDT) Received: from smtpng2.m.smailru.net (smtpng2.m.smailru.net [94.100.179.3]) (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 72A3F27D4D for ; Mon, 6 Aug 2018 08:27:07 -0400 (EDT) From: Kirill Shcherbatov Subject: [tarantool-patches] [PATCH v1 2/5] box: introduce slot_cache in key_part Date: Mon, 6 Aug 2018 15:26:59 +0300 Message-Id: <14a46618ad51e12394c1f578adbd8874b49ce93c.1533558332.git.kshcherbatov@tarantool.org> In-Reply-To: References: In-Reply-To: References: 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 Cc: v.shpilevoy@tarantool.org, Kirill Shcherbatov Same key_part could be used in different formats multiple times, so different field->offset_slot would be allocated. In most scenarios we work with series of tuples of same format, and (in general) format lookup for field would be expensive operation for JSON-paths defined in key_part. New slot_cache field in key_part structure and epoch-based mechanism to validate it actuality should be effective approach to improve performance. New routine tuple_field_by_part use tuple and key_part to access field that allows to rework and speedup all scenarios of access tuple data by index. This also allows to work with JSON-path key_parts later. Part of #1012. --- src/box/key_def.c | 2 ++ src/box/key_def.h | 4 ++++ src/box/memtx_bitset.c | 4 ++-- src/box/memtx_rtree.c | 2 +- src/box/tuple_bloom.c | 8 ++++---- src/box/tuple_compare.cc | 48 +++++++++++++++++--------------------------- src/box/tuple_extract_key.cc | 13 +++--------- src/box/tuple_format.c | 43 +++++++++++++++++++++++++++++++++++++++ src/box/tuple_format.h | 15 ++++++++++++++ src/box/tuple_hash.cc | 28 ++++++++++++-------------- src/box/tuple_hash.h | 5 +++-- src/box/vy_stmt.h | 2 +- 12 files changed, 109 insertions(+), 65 deletions(-) diff --git a/src/box/key_def.c b/src/box/key_def.c index ee09dc9..8a4262b 100644 --- a/src/box/key_def.c +++ b/src/box/key_def.c @@ -258,6 +258,8 @@ key_def_set_part(struct key_def *def, uint32_t part_no, uint32_t fieldno, def->parts[part_no].type = type; def->parts[part_no].coll = coll; def->parts[part_no].coll_id = coll_id; + def->parts[part_no].slot_cache = TUPLE_OFFSET_SLOT_NIL; + def->parts[part_no].format_epoch = 0; column_mask_set_fieldno(&def->column_mask, fieldno); /** * When all parts are set, initialize the tuple diff --git a/src/box/key_def.h b/src/box/key_def.h index aecbe03..42c054c 100644 --- a/src/box/key_def.h +++ b/src/box/key_def.h @@ -74,6 +74,10 @@ struct key_part { struct coll *coll; /** True if a part can store NULLs. */ bool is_nullable; + /** Format epoch for slot_cache. */ + uint64_t format_epoch; + /** Cache for corresponding tuple_format slot_offset. */ + int32_t slot_cache; }; struct key_def; diff --git a/src/box/memtx_bitset.c b/src/box/memtx_bitset.c index a665f1a..e9b5f6a 100644 --- a/src/box/memtx_bitset.c +++ b/src/box/memtx_bitset.c @@ -283,8 +283,8 @@ memtx_bitset_index_replace(struct index *base, struct tuple *old_tuple, } if (new_tuple != NULL) { - const char *field; - field = tuple_field(new_tuple, base->def->key_def->parts[0].fieldno); + const char *field = + tuple_field_by_part(new_tuple, base->def->key_def, 0); uint32_t key_len; const void *key = make_key(field, &key_len); #ifndef OLD_GOOD_BITSET diff --git a/src/box/memtx_rtree.c b/src/box/memtx_rtree.c index 0b12cda..fd6334f 100644 --- a/src/box/memtx_rtree.c +++ b/src/box/memtx_rtree.c @@ -112,7 +112,7 @@ extract_rectangle(struct rtree_rect *rect, const struct tuple *tuple, struct index_def *index_def) { assert(index_def->key_def->part_count == 1); - const char *elems = tuple_field(tuple, index_def->key_def->parts[0].fieldno); + const char *elems = tuple_field_by_part(tuple, index_def->key_def, 0); unsigned dimension = index_def->opts.dimension; uint32_t count = mp_decode_array(&elems); return mp_decode_rect(rect, dimension, elems, count, "Field"); diff --git a/src/box/tuple_bloom.c b/src/box/tuple_bloom.c index ffad151..3de83bc 100644 --- a/src/box/tuple_bloom.c +++ b/src/box/tuple_bloom.c @@ -85,8 +85,8 @@ tuple_bloom_builder_add(struct tuple_bloom_builder *builder, uint32_t total_size = 0; for (uint32_t i = 0; i < key_def->part_count; i++) { - total_size += tuple_hash_key_part(&h, &carry, tuple, - &key_def->parts[i]); + total_size += + tuple_hash_key_part(&h, &carry, tuple, key_def, i); if (i < hashed_parts) { /* * This part is already in the bloom, proceed @@ -183,8 +183,8 @@ tuple_bloom_maybe_has(const struct tuple_bloom *bloom, uint32_t total_size = 0; for (uint32_t i = 0; i < key_def->part_count; i++) { - total_size += tuple_hash_key_part(&h, &carry, tuple, - &key_def->parts[i]); + total_size += + tuple_hash_key_part(&h, &carry, tuple, key_def, i); uint32_t hash = PMurHash32_Result(h, carry, total_size); if (!bloom_maybe_has(&bloom->parts[i], hash)) return false; diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc index e53afba..6d34c60 100644 --- a/src/box/tuple_compare.cc +++ b/src/box/tuple_compare.cc @@ -432,9 +432,8 @@ tuple_common_key_parts(const struct tuple *tuple_a, { uint32_t i; for (i = 0; i < key_def->part_count; i++) { - const struct key_part *part = &key_def->parts[i]; - const char *field_a = tuple_field(tuple_a, part->fieldno); - const char *field_b = tuple_field(tuple_b, part->fieldno); + const char *field_a = tuple_field_by_part(tuple_a, key_def, i); + const char *field_b = tuple_field_by_part(tuple_b, key_def, i); enum mp_type a_type = field_a != NULL ? mp_typeof(*field_a) : MP_NIL; enum mp_type b_type = field_b != NULL ? @@ -442,8 +441,9 @@ tuple_common_key_parts(const struct tuple *tuple_a, if (a_type == MP_NIL && b_type == MP_NIL) continue; if (a_type == MP_NIL || b_type == MP_NIL || - tuple_compare_field_with_hint(field_a, a_type, - field_b, b_type, part->type, part->coll) != 0) + tuple_compare_field_with_hint(field_a, a_type, field_b, + b_type, key_def->parts[i].type, + key_def->parts[i].coll) != 0) break; } return i; @@ -457,7 +457,7 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b, assert(!has_optional_parts || is_nullable); assert(is_nullable == key_def->is_nullable); assert(has_optional_parts == key_def->has_optional_parts); - const struct key_part *part = key_def->parts; + struct key_part *part = (struct key_part *)key_def->parts; const char *tuple_a_raw = tuple_data(tuple_a); const char *tuple_b_raw = tuple_data(tuple_b); if (key_def->part_count == 1 && part->fieldno == 0) { @@ -484,10 +484,6 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b, } bool was_null_met = false; - const struct tuple_format *format_a = tuple_format(tuple_a); - const struct tuple_format *format_b = tuple_format(tuple_b); - const uint32_t *field_map_a = tuple_field_map(tuple_a); - const uint32_t *field_map_b = tuple_field_map(tuple_b); const struct key_part *end; const char *field_a, *field_b; enum mp_type a_type, b_type; @@ -497,11 +493,10 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b, else end = part + key_def->part_count; - for (; part < end; part++) { - field_a = tuple_field_raw(format_a, tuple_a_raw, field_map_a, - part->fieldno); - field_b = tuple_field_raw(format_b, tuple_b_raw, field_map_b, - part->fieldno); + uint32_t i = 0; + for (; part < end; part++, i++) { + field_a = tuple_field_by_part(tuple_a, key_def, i); + field_b = tuple_field_by_part(tuple_b, key_def, i); assert(has_optional_parts || (field_a != NULL && field_b != NULL)); if (! is_nullable) { @@ -547,11 +542,9 @@ tuple_compare_slowpath(const struct tuple *tuple_a, const struct tuple *tuple_b, * extended parts only. */ end = key_def->parts + key_def->part_count; - for (; part < end; ++part) { - field_a = tuple_field_raw(format_a, tuple_a_raw, field_map_a, - part->fieldno); - field_b = tuple_field_raw(format_b, tuple_b_raw, field_map_b, - part->fieldno); + for (; part < end; ++part, ++i) { + field_a = tuple_field_by_part(tuple_a, key_def, i); + field_b = tuple_field_by_part(tuple_b, key_def, i); /* * Extended parts are primary, and they can not * be absent or be NULLs. @@ -576,15 +569,11 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key, assert(has_optional_parts == key_def->has_optional_parts); assert(key != NULL || part_count == 0); assert(part_count <= key_def->part_count); - const struct key_part *part = key_def->parts; - const struct tuple_format *format = tuple_format(tuple); - const char *tuple_raw = tuple_data(tuple); - const uint32_t *field_map = tuple_field_map(tuple); + struct key_part *part = (struct key_part *)key_def->parts; enum mp_type a_type, b_type; + uint32_t i = 0; if (likely(part_count == 1)) { - const char *field; - field = tuple_field_raw(format, tuple_raw, field_map, - part->fieldno); + const char *field = tuple_field_by_part(tuple, key_def, i); if (! is_nullable) { return tuple_compare_field(field, key, part->type, part->coll); @@ -607,10 +596,9 @@ tuple_compare_with_key_slowpath(const struct tuple *tuple, const char *key, const struct key_part *end = part + part_count; int rc; - for (; part < end; ++part, mp_next(&key)) { + for (; part < end; ++i, ++part, mp_next(&key)) { const char *field; - field = tuple_field_raw(format, tuple_raw, field_map, - part->fieldno); + field = tuple_field_by_part(tuple, key_def, i); if (! is_nullable) { rc = tuple_compare_field(field, key, part->type, part->coll); diff --git a/src/box/tuple_extract_key.cc b/src/box/tuple_extract_key.cc index 880abb6..bbd87f5 100644 --- a/src/box/tuple_extract_key.cc +++ b/src/box/tuple_extract_key.cc @@ -101,18 +101,13 @@ tuple_extract_key_slowpath(const struct tuple *tuple, assert(contains_sequential_parts == key_def_contains_sequential_parts(key_def)); assert(mp_sizeof_nil() == 1); - const char *data = tuple_data(tuple); uint32_t part_count = key_def->part_count; uint32_t bsize = mp_sizeof_array(part_count); - const struct tuple_format *format = tuple_format(tuple); - const uint32_t *field_map = tuple_field_map(tuple); - const char *tuple_end = data + tuple->bsize; + const char *tuple_end = tuple_data(tuple) + tuple->bsize; /* Calculate the key size. */ for (uint32_t i = 0; i < part_count; ++i) { - const char *field = - tuple_field_raw(format, data, field_map, - key_def->parts[i].fieldno); + const char *field = tuple_field_by_part(tuple, key_def, i); if (has_optional_parts && field == NULL) { bsize += mp_sizeof_nil(); continue; @@ -152,9 +147,7 @@ tuple_extract_key_slowpath(const struct tuple *tuple, } char *key_buf = mp_encode_array(key, part_count); for (uint32_t i = 0; i < part_count; ++i) { - const char *field = - tuple_field_raw(format, data, field_map, - key_def->parts[i].fieldno); + const char *field = tuple_field_by_part(tuple, key_def, i); if (has_optional_parts && field == NULL) { key_buf = mp_encode_nil(key_buf); continue; diff --git a/src/box/tuple_format.c b/src/box/tuple_format.c index 2e19d2e..40cd48a 100644 --- a/src/box/tuple_format.c +++ b/src/box/tuple_format.c @@ -29,12 +29,15 @@ * SUCH DAMAGE. */ #include "json/path.h" +#include "tuple.h" #include "tuple_format.h" /** Global table of tuple formats */ struct tuple_format **tuple_formats; static intptr_t recycled_format_ids = FORMAT_ID_NIL; +static uint64_t format_epoch = 1; + static uint32_t formats_size = 0, formats_capacity = 0; static const struct tuple_field tuple_field_default = { @@ -69,6 +72,7 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, format->fields[i] = tuple_field_default; int current_slot = 0; + bool format_epoch_changed = false; /* extract field type info */ for (uint16_t key_no = 0; key_no < key_count; ++key_no) { @@ -135,6 +139,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, is_sequential == false && part->fieldno > 0) { field->offset_slot = --current_slot; + if (part->slot_cache != field->offset_slot) + format_epoch_changed = true; } } } @@ -148,6 +154,8 @@ tuple_format_create(struct tuple_format *format, struct key_def * const *keys, return -1; } format->field_map_size = field_map_size; + if (format_epoch_changed) + format->epoch = ++format_epoch; return 0; } @@ -233,6 +241,7 @@ tuple_format_alloc(struct key_def * const *keys, uint16_t key_count, format->dict = dict; tuple_dictionary_ref(dict); } + format->epoch = format_epoch; format->refs = 0; format->id = FORMAT_ID_NIL; format->field_count = field_count; @@ -542,6 +551,40 @@ tuple_field_go_to_key(const char **field, const char *key, int len) return -1; } +const char * +tuple_field_by_part(const struct tuple *tuple, const struct key_def *def, + uint32_t idx) +{ + struct key_part *part = (struct key_part *)&def->parts[idx]; + const struct tuple_format *format = tuple_format(tuple); + const char *data = tuple_data(tuple); + const uint32_t *field_map = tuple_field_map(tuple); + + uint32_t field_no = part->fieldno; + if (likely(field_no < format->index_field_count)) { + assert(format->epoch > 0); + int32_t offset_slot = TUPLE_OFFSET_SLOT_NIL; + if (part->format_epoch != format->epoch) { + offset_slot = format->fields[field_no].offset_slot; + if (format->epoch > part->format_epoch) { + part->slot_cache = offset_slot; + part->format_epoch = format->epoch; + } + } + if (offset_slot != TUPLE_OFFSET_SLOT_NIL) { + return field_map[offset_slot] != 0 ? + data + field_map[offset_slot] : NULL; + } + } + ERROR_INJECT(ERRINJ_TUPLE_FIELD, return NULL); + uint32_t field_count = mp_decode_array(&data); + if (unlikely(field_no >= field_count)) + return NULL; + for (uint32_t k = 0; k < field_no; k++) + mp_next(&data); + return data; +} + int tuple_field_raw_by_path(struct tuple_format *format, const char *tuple, const uint32_t *field_map, const char *path, diff --git a/src/box/tuple_format.h b/src/box/tuple_format.h index c7dc48f..3cb1284 100644 --- a/src/box/tuple_format.h +++ b/src/box/tuple_format.h @@ -115,6 +115,8 @@ struct tuple_field { * Tuple format describes how tuple is stored and information about its fields */ struct tuple_format { + /** Tuple format epoch. */ + uint64_t epoch; /** Virtual function table */ struct tuple_format_vtab vtab; /** Pointer to engine-specific data. */ @@ -324,6 +326,19 @@ tuple_init_field_map(const struct tuple_format *format, uint32_t *field_map, const char *tuple); /** + * Get a field refereed by multipart index @def part @idx in + * @tuple. + * + * @param tuple object containing data to lookup. + * @param key_def multipart index to use. + * @param idx index of part to use. + * @retval field data if field exists or NULL + */ +const char * +tuple_field_by_part(const struct tuple *tuple, const struct key_def *def, + uint32_t idx); + +/** * Get a field at the specific position in this MessagePack array. * Returns a pointer to MessagePack data. * @param format tuple format diff --git a/src/box/tuple_hash.cc b/src/box/tuple_hash.cc index dee9be3..7e4f3e6 100644 --- a/src/box/tuple_hash.cc +++ b/src/box/tuple_hash.cc @@ -157,7 +157,7 @@ struct TupleHash uint32_t h = HASH_SEED; uint32_t carry = 0; uint32_t total_size = 0; - const char *field = tuple_field(tuple, key_def->parts->fieldno); + const char *field = tuple_field_by_part(tuple, key_def, 0); TupleFieldHash:: hash(&field, &h, &carry, &total_size); return PMurHash32_Result(h, carry, total_size); @@ -169,7 +169,7 @@ struct TupleHash { static uint32_t hash(const struct tuple *tuple, const struct key_def *key_def) { - const char *field = tuple_field(tuple, key_def->parts->fieldno); + const char *field = tuple_field_by_part(tuple, key_def, 0); uint64_t val = mp_decode_uint(&field); if (likely(val <= UINT32_MAX)) return val; @@ -310,12 +310,12 @@ tuple_hash_null(uint32_t *ph1, uint32_t *pcarry) uint32_t tuple_hash_key_part(uint32_t *ph1, uint32_t *pcarry, const struct tuple *tuple, - const struct key_part *part) + const struct key_def *key_def, uint32_t i) { - const char *field = tuple_field(tuple, part->fieldno); + const char *field = tuple_field_by_part(tuple, key_def, i); if (field == NULL) return tuple_hash_null(ph1, pcarry); - return tuple_hash_field(ph1, pcarry, &field, part->coll); + return tuple_hash_field(ph1, pcarry, &field, key_def->parts[i].coll); } template @@ -326,31 +326,29 @@ tuple_hash_slowpath(const struct tuple *tuple, const struct key_def *key_def) uint32_t h = HASH_SEED; uint32_t carry = 0; uint32_t total_size = 0; - uint32_t prev_fieldno = key_def->parts[0].fieldno; - const char *field = tuple_field(tuple, key_def->parts[0].fieldno); + const struct key_part *part = &key_def->parts[0]; + uint32_t prev_fieldno = part->fieldno; + const char *field = tuple_field_by_part(tuple, key_def, 0); const char *end = (char *)tuple + tuple_size(tuple); if (has_optional_parts && field == NULL) { total_size += tuple_hash_null(&h, &carry); } else { - total_size += tuple_hash_field(&h, &carry, &field, - key_def->parts[0].coll); + total_size += tuple_hash_field(&h, &carry, &field, part->coll); } for (uint32_t part_id = 1; part_id < key_def->part_count; part_id++) { /* If parts of key_def are not sequential we need to call * tuple_field. Otherwise, tuple is hashed sequentially without * need of tuple_field */ - if (prev_fieldno + 1 != key_def->parts[part_id].fieldno) { - field = tuple_field(tuple, key_def->parts[part_id].fieldno); - } + if (prev_fieldno + 1 != part->fieldno) + field = tuple_field_by_part(tuple, key_def, part_id); if (has_optional_parts && (field == NULL || field >= end)) { total_size += tuple_hash_null(&h, &carry); } else { total_size += - tuple_hash_field(&h, &carry, &field, - key_def->parts[part_id].coll); + tuple_hash_field(&h, &carry, &field, part->coll); } - prev_fieldno = key_def->parts[part_id].fieldno; + prev_fieldno = part->fieldno; } return PMurHash32_Result(h, carry, total_size); diff --git a/src/box/tuple_hash.h b/src/box/tuple_hash.h index aab8f54..90f80a8 100644 --- a/src/box/tuple_hash.h +++ b/src/box/tuple_hash.h @@ -64,7 +64,8 @@ tuple_hash_field(uint32_t *ph1, uint32_t *pcarry, const char **field, * @param ph1 - pointer to running hash * @param pcarry - pointer to carry * @param tuple - tuple to hash - * @param part - key part + * @param key_def - key definition + * @param i - index of part to hash * @return size of processed data * * This function updates @ph1 and @pcarry. @@ -72,7 +73,7 @@ tuple_hash_field(uint32_t *ph1, uint32_t *pcarry, const char **field, uint32_t tuple_hash_key_part(uint32_t *ph1, uint32_t *pcarry, const struct tuple *tuple, - const struct key_part *part); + const struct key_def *key_def, uint32_t i); /** * Calculates a common hash value for a tuple diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h index e53f98c..0b485ad 100644 --- a/src/box/vy_stmt.h +++ b/src/box/vy_stmt.h @@ -665,7 +665,7 @@ static inline bool vy_tuple_key_contains_null(const struct tuple *tuple, const struct key_def *def) { for (uint32_t i = 0; i < def->part_count; ++i) { - const char *field = tuple_field(tuple, def->parts[i].fieldno); + const char *field = tuple_field_by_part(tuple, def, i); if (field == NULL || mp_typeof(*field) == MP_NIL) return true; } -- 2.7.4