Re: [PATCH 4/4] mark_parents_uninteresting(): avoid most allocation

[Derrick Stolee <stolee@gmail.com>]

On 5/14/2018 9:09 AM, Jeff King wrote:
> On Mon, May 14, 2018 at 08:47:33AM -0400, Derrick Stolee wrote:
>
>> On 5/11/2018 2:03 PM, Jeff King wrote:
>>> Commit 941ba8db57 (Eliminate recursion in setting/clearing
>>> marks in commit list, 2012-01-14) used a clever double-loop
>>> to avoid allocations for single-parent chains of history.
>>> However, it did so only when following parents of parents
>>> (which was an uncommon case), and _always_ incurred at least
>>> one allocation to populate the list of pending parents in
>>> the first place.
>>>
>>> We can turn this into zero-allocation in the common case by
>>> iterating directly over the initial parent list, and then
>>> following up on any pending items we might have discovered.
>> This change appears to improve performance, but I was unable to measure any
>> difference between this commit and the one ahead, even when merging
>> ds/generation-numbers (which significantly reduces the other costs). I was
>> testing 'git status' and 'git rev-list --boundary master...origin/master' in
>> the Linux repo with my copy of master 70,000+ commits behind origin/master.
> I think you'd want to go the other way: this is marking uninteresting
> commits, so you'd want origin/master..master, which would make those 70k
> commits uninteresting.

Thanks for the tip. Running 'git rev-list origin/master..master' 100 
times gave the following times, on average (with ds/generation-numbers):

PATCH 3/4: 0.19 s
PATCH 4/4: 0.16 s
     Rel %: -16%

>
> I still doubt it will create that much difference, though. It's
> more or less saving a single malloc per commit we traverse. Certainly
> without the .commits file that's a drop in the bucket compared to
> inflating the object data, but I wouldn't be surprised if we end up with
> a few mallocs even after your patches.
>
> Anyway, thanks for poking at it. :)
>
> -Peff