Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list
- From
- Jeff Hostetler <git@jeffhostetler.com>
- Date
- Apr 5, 2017, 21:12 UTC
- Message-ID
- <e805dfdd-12a4-cb70-d4e6-b5af915d29b5@jeffhostetler.com>
- In-Reply-To
- <20170405200954.jmjvuzwjploenbho@sigill.intra.peff.net>
On 4/5/2017 4:09 PM, Jeff King wrote:
Show 18 quoted lines
> On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote: > >> From: Jeff Hostetler <jeffhost@microsoft.com> >> >> Use ALLOC_GROW() macro when reallocing a string_list array >> rather than simply increasing it by 32. This is a performance >> optimization. >> >> 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. >> >> This change decreased the time in wt_status_collect_changes_worktree() >> from 125 seconds to 45 seconds on my very large repository. > > Oof. Looks like the original was quadratic. I'm surprised this didn't > bite us more often. I guess we don't usually use string-lists for big > lists.
To be fair, I was playing with a repo with 3M files and I think realloc() is more efficient on Linux, so I'm not surprised that we haven't seen it even with repos the size of linux.git.
Show 9 quoted lines
> > Aside from the redundant size-check that Stefan pointed out, the patch > looks obviously correct. I grepped for "alloc +=" and "alloc =.*+' to > see if there were any other cases, but didn't find any. Obviously that > is dependent on calling the variable "alloc", but that is normal for us > (and it does turn up a number of cases that do allocate correctly). > > -Peff >