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 30C1D26A7C for ; Mon, 4 Jun 2018 07:21:13 -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 i8eRKSV56kOA for ; Mon, 4 Jun 2018 07:21:13 -0400 (EDT) Received: from smtp15.mail.ru (smtp15.mail.ru [94.100.176.133]) (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 DF53026A7B for ; Mon, 4 Jun 2018 07:21:12 -0400 (EDT) Subject: [tarantool-patches] Re: [PATCH v2 1/1] box: create bigrefs for tuples References: <9c250cefbee4375f722235eaf234b734bf98b83d.1527867534.git.imeevma@gmail.com> From: Vladislav Shpilevoy Message-ID: <8844c62d-284e-3461-d5cb-969dedbe5348@tarantool.org> Date: Mon, 4 Jun 2018 14:21:10 +0300 MIME-Version: 1.0 In-Reply-To: <9c250cefbee4375f722235eaf234b734bf98b83d.1527867534.git.imeevma@gmail.com> Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit 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, imeevma@tarantool.org Hello. Thanks for the patch! It is almost perfect! See 6 comments below. On 01/06/2018 18:41, imeevma@tarantool.org wrote: > Due to limitation of reference counters for tuple being only > 65535 it was possible to reach this limitation. This patch > increases capacity of reference counters to 4 billions. > > Closes #3224 > --- > Branch: https://github.com/tarantool/tarantool/tree/imeevma/gh-3224-tuple-bigrefs > Issue: https://github.com/tarantool/tarantool/issues/3224 > > src/box/errcode.h | 2 +- > src/box/lua/tuple.c | 5 +- > src/box/port.c | 8 +-- > src/box/tuple.c | 164 +++++++++++++++++++++++++++++++++++++++++++++-- > src/box/tuple.h | 63 ++++++++++-------- > test/box/misc.result | 39 ++++++----- > test/box/select.result | 30 +++++++-- > test/box/select.test.lua | 15 ++++- > 8 files changed, 257 insertions(+), 69 deletions(-) > > diff --git a/src/box/tuple.c b/src/box/tuple.c > index 014f374..f59b27e 100644 > --- a/src/box/tuple.c > +++ b/src/box/tuple.c> + > +/** > + * Try to decrease allocated memory if it is possible. Free memory when > + * size == 0. > + */ > +static inline void > +tuple_bigrefs_compact(void) > +{ > + if (bigrefs.size == 0) { > + tuple_bigrefs_destroy(); > + return; > + } > + if (bigrefs.capacity == TUPLE_BIGREF_MIN_CAPACITY || > + bigrefs.size > bigrefs.capacity / TUPLE_BIGREF_FACTOR) > + return; > + uint16_t size = bigrefs.size; > + uint16_t reserved = 0; > + uint16_t capacity = bigrefs.capacity; > + while(size > 0 && reserved <= capacity / TUPLE_BIGREF_FACTOR) { > + if (bigrefs.refs[reserved] != 0) > + --size; > + reserved++; > + } 1. Why do you iterate from the beginning? As far as I remember, we have decided to iterate from the end. Here you try to find such the biggest index, that refs[index] != 0. So when you iterate from the beginning, you always need to go through capacity, but when you iterate from the end, it is enough to stop on the first non-zero element. And here you use reserved both as a count and as an index. It is incorrect: count is 1-based value, index is 0 based. > + if (reserved < TUPLE_BIGREF_MIN_CAPACITY) > + reserved = TUPLE_BIGREF_MIN_CAPACITY; > + if (reserved > capacity / TUPLE_BIGREF_FACTOR) > + return; > + while(reserved <= capacity / TUPLE_BIGREF_FACTOR) > + capacity /= TUPLE_BIGREF_MIN_CAPACITY; 2. I see that capacity is always a power of 2. And you can calculate the capacity as a next power of 2 starting from 'reserved'. See this algorithm: http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2Float, paragraph "Round up to the next highest power of 2". It has O(1) as I can see versus O(N) with N - bit count in your algorithm. > + uint32_t *refs = (uint32_t *) realloc(bigrefs.refs, capacity * > + sizeof(*bigrefs.refs)); > + if (refs == NULL) > + panic("failed to reallocate %zu bytes: Cannot allocate"\ > + " memory.", capacity * sizeof(*bigrefs.refs)); > + bigrefs.refs = refs; > + bigrefs.capacity = capacity; > +} > + > diff --git a/src/box/tuple.h b/src/box/tuple.h > index e2384dd..6921124 100644 > --- a/src/box/tuple.h > +++ b/src/box/tuple.h > @@ -307,8 +306,16 @@ box_tuple_upsert(const box_tuple_t *tuple, const char *expr, const > */ > struct PACKED tuple > { > - /** reference counter */ > - uint16_t refs; > + union { > + /** reference counter */ > + uint16_t refs; > + struct { > + /** index of big reference counter */ > + uint16_t ref_index : 15; > + /** big reference flag */ > + bool is_bigref : 1; 3. Please. Start a sentence with a capital letter, and finish with dot. I see comments in other struct tuple fields, but they are incorrect too. Lets fix them alongside. > + }; > + }; > /** format identifier */ > uint16_t format_id; > /** > @@ -774,26 +781,36 @@ tuple_field_uuid(const struct tuple *tuple, int fieldno, > return 0; > } > > -enum { TUPLE_REF_MAX = UINT16_MAX }; > +enum { TUPLE_REF_MAX = UINT16_MAX >> 1 }; > + > +/** > + * Increase tuple big reference counter. > + * @param tuple Tuple to reference. > + */ > +void > +tuple_ref_slow(struct tuple *tuple); > > /** > * Increment tuple reference counter. > * @param tuple Tuple to reference. > - * @retval 0 Success. > - * @retval -1 Too many refs error. > */ > -static inline int > +static inline void > tuple_ref(struct tuple *tuple) > { > - if (tuple->refs + 1 > TUPLE_REF_MAX) { > - diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); > - return -1; > - } > - tuple->refs++; > - return 0; > + if (tuple->is_bigref || tuple->refs == TUPLE_REF_MAX) 4. Is it the same as 'tuple->refs >= TUPLE_REF_MAX'? I would prefer that because single check is better than two. Tuple_ref is very hot path and must be very optimized. Maybe we should even wrap this condition with unlikely() macro. if (unlikely(tuple->refs >= TUPLE_REF_MAX)) ref_slow else ref_fast > + tuple_ref_slow(tuple); > + else > + tuple->refs++; > } > > /** > + * Decrease tuple big reference counter. > + * @param tuple Tuple to reference. > + */ > +void > +tuple_unref_slow(struct tuple *tuple); > + > +/** > * Decrement tuple reference counter. If it has reached zero, free the tuple. > * > * @pre tuple->refs + count >= 0 > @@ -802,6 +819,10 @@ static inline void > tuple_unref(struct tuple *tuple) > { > assert(tuple->refs - 1 >= 0); > + if (tuple->is_bigref) { 5. Same. Lets do if (unlikely(tuple->is_bigref)) { unref_slow ... } > + tuple_unref_slow(tuple); > + return; > + } > > tuple->refs--; > > @@ -813,22 +834,15 @@ extern struct tuple *box_tuple_last; > > /** > * Convert internal `struct tuple` to public `box_tuple_t`. > - * \retval tuple on success > - * \retval NULL on error, check diag > + * \retval tuple > * \post \a tuple ref counted until the next call. > - * \post tuple_ref() doesn't fail at least once > * \sa tuple_ref > */ > static inline box_tuple_t * > tuple_bless(struct tuple *tuple) > { > assert(tuple != NULL); > - /* Ensure tuple can be referenced at least once after return */ > - if (tuple->refs + 2 > TUPLE_REF_MAX) { > - diag_set(ClientError, ER_TUPLE_REF_OVERFLOW); > - return NULL; > - } > - tuple->refs++; > + tuple_ref(tuple); > /* Remove previous tuple */ > if (likely(box_tuple_last != NULL)) > tuple_unref(box_tuple_last); /* do not throw */ > @@ -856,8 +870,7 @@ tuple_to_buf(const struct tuple *tuple, char *buf, size_t size); > static inline void > tuple_ref_xc(struct tuple *tuple) 6. Lets remove tuple_ref_xc now. 'XC' here means 'eXCeption on an error'. No an error is impossible, so tuple_ref_xc === tuple_ref. > { > - if (tuple_ref(tuple)) > - diag_raise(); > + tuple_ref(tuple); > } >