Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Apr 5, 2017, 21:26 UTC
Message-ID: <20170405212620.GG8741@aiede.mtv.corp.google.com>
In-Reply-To: <20170405195600.54801-2-git@jeffhostetler.com>

Hi,

git@jeffhostetler.com wrote:

> During status on a very large repo and there are many changes,
> a significant percentage of the total run time was spent
> reallocing the wt_status.changes array.

Nit: commit messages tend to use the present tense instead of the past
when describing Git's current behavior.  That makes it easier for
readers to tell whether you are describing the present or the distant
past.

> This change decreased the time in wt_status_collect_changes_worktree()
> from 125 seconds to 45 seconds on my very large repository.

Nice.

This is also just the right thing to do. The linear growth would produce potentially (potentially because you can be lucky and allocate in the first place somewhere with a lot of room) quadratic behavior as realloc copies the allocation to increasingly larger regions.

Show 19 quoted lines

> Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com>
> ---
>  string-list.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
>
> diff --git a/string-list.c b/string-list.c
> index 45016ad..cd4c4e0 100644
> --- a/string-list.c
> +++ b/string-list.c
> @@ -41,10 +41,8 @@ static int add_entry(int insert_at, struct string_list *list, const char *string
>  	if (exact_match)
>  		return -1 - index;
>  
> -	if (list->nr + 1 >= list->alloc) {
> -		list->alloc += 32;
> -		REALLOC_ARRAY(list->items, list->alloc);
> -	}
> +	if (list->nr + 1 >= list->alloc)
> +		ALLOC_GROW(list->items, list->nr+1, list->alloc);

This checks for >= but ALLOC_GROW only grows when the new size is >. The new code is less eager about growing than the old was, forcing me to look at the other code to find the correct invariant.

Fortunately (1) string_list_append_nodup already uses ALLOC_GROW the way this patch does and (2) REALLOC_ARRAY determines the meaning of list->alloc. The >= was just overeager and this is safe.

After removing the unnecessary 'if' as described by Stefan,
Reviewed-by: Jonathan Nieder <jrnieder@gmail.com>

Thanks.