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

[Jonathan Nieder <jrnieder@gmail.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.

> 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.