From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <vdavydov.dev@gmail.com>
Date: Thu, 29 Nov 2018 20:50:57 +0300
From: Vladimir Davydov <vdavydov.dev@gmail.com>
Subject: Re: [tarantool-patches] [PATCH v5 2/9] lib: implement JSON tree
 class for json library
Message-ID: <20181129175057.gy4gqxdvej63f7sm@esperanza>
References: <cover.1543229303.git.kshcherbatov@tarantool.org>
 <02671a3d0a2236ecd6e12c0bc51b7f5e39272a2f.1543229303.git.kshcherbatov@tarantool.org>
 <e98d2d8f-7866-5b79-5bf7-e7f63eddbe08@tarantool.org>
 <20181129173816.kprfjhki5o7ytfbl@esperanza>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20181129173816.kprfjhki5o7ytfbl@esperanza>
To: Kirill Shcherbatov <kshcherbatov@tarantool.org>
Cc: tarantool-patches@freelists.org, Kostya Osipov <kostja@tarantool.org>
List-ID: <tarantool-patches.dev.tarantool.org>

On Thu, Nov 29, 2018 at 08:38:16PM +0300, Vladimir Davydov wrote:
> On Mon, Nov 26, 2018 at 03:53:03PM +0300, Kirill Shcherbatov wrote:
> > +int
> > +json_tree_add(struct json_tree *tree, struct json_token *parent,
> > +	      struct json_token *token)
> > +{
> > +	if (parent == NULL)
> > +		parent = &tree->root;
> > +	uint32_t rolling_hash =
> > +	       json_token_hash(token, parent->rolling_hash);
> > +	assert(json_tree_lookup(tree, parent, token) == NULL);
> > +	uint32_t insert_idx = (token->key.type == JSON_TOKEN_NUM) ?
> > +			      (uint32_t)token->key.num - 1 :
> > +			      parent->child_size;
> > +	if (insert_idx >= parent->child_size) {
> > +		uint32_t new_size =
> > +			parent->child_size == 0 ? 1 : 2 * parent->child_size;
> > +		while (insert_idx >= new_size)
> > +			new_size *= 2;
> > +		struct json_token **children =
> > +			realloc(parent->children, new_size*sizeof(void *));
> > +		if (unlikely(children == NULL))
> > +			return -1;
> > +		memset(children + parent->child_size, 0,
> > +		       (new_size - parent->child_size)*sizeof(void *));
> > +		parent->children = children;
> > +		parent->child_size = new_size;
> 
> Ouch, this looks much more complex than it was in the previous version.
> Please revert. Quoting myself:
> 
> } > +     if (insert_idx >= parent->children_count) {
> } > +             uint32_t new_size = insert_idx + 1;
> } 
> } We usually double the size with each allocation. If this is intentional,
> } please add a comment.
> 
> I didn't push you to change that. I just wanted you to add a comment
> saying that we can afford quadratic algorithmic complexity here, because
> this function is far from a hot path and we expect the tree to be rather
> small.

Come to think of it, don't bother. Doubling the array will probably
increases chances that the allocation will stay close to the node
itself, and it looks saner in a common sense. Let's please just rename
child_size to child_count_max and increase the initial allocation up to
say 8, OK?