From: Jeff Hostetler Date: Wed, 05 Apr 2017 21:12:37 GMT Subject: Re: [PATCH v1 1/2] string-list: use ALLOC_GROW macro when reallocing string_list Message-ID: In-Reply-To: <20170405200954.jmjvuzwjploenbho@sigill.intra.peff.net> On 4/5/2017 4:09 PM, Jeff King wrote: > On Wed, Apr 05, 2017 at 07:55:59PM +0000, git@jeffhostetler.com wrote: > >> From: Jeff Hostetler >> >> 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. > > 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 >