Subject: Re: [PATCH 06/10] commit-graph.c: sort index into commits list

From: Taylor Blau <[email-masked]>
Date: Tue, 4 Aug 2020 16:10:06 -0400

On Tue, Aug 04, 2020 at 08:31:53AM -0400, Derrick Stolee wrote:
> On 8/3/2020 2:57 PM, Taylor Blau wrote:
> > For locality, 'compute_bloom_filters()' sorts the commits for which it
> > wants to compute Bloom filters in a preferred order (cf., 3d11275505
> > (commit-graph: examine commits by generation number, 2020-03-30) for
> > details).
> >
> > The subsequent patch will want to recover the new graph position of each
> > commit. Since the 'packed_commit_list' already stores a double-pointer,
> > avoid a 'COPY_ARRAY' and instead keep track of an index into the
> > original list. (Use an integer index instead of a memory address, since
> > this involves a needlessly confusing triple-pointer).
>
> It took me a little while to grok that we are switching from sorting
> a list of commit pointers to sorting a list of integers. However, that
> makes a lot of sense. It preserves the commit list sorted by OID for
> binary search, which you will need soon. Perhaps another change would
> need that at another time, too.

Yeah. I had to spend some additional time with this patch (at least back
when it was written in terms of 'struct commit ***'s) to convince myself
of its correctness, too.

I think that this is ultimately the right thing, and that it is probably
as simple as I can make it without refactoring the packed_commit_list,
which I think is squarely outside the scope of this (already-large)
series ;).

> > Alter the two sorting routines 'commit_pos_cmp' and 'commit_gen_cmp' to
> > take into account the packed_commit_list they are sorting with respect
> > to. Since 'compute_bloom_filters()' is the only caller for each of those
> > comparison functions, no other call-sites need updating.
>
> Parsing the changes to these functions is the most complicated, because
> of the int-to-commit indirection. I think they are correct and as easy
> to read as possible.
>
> -Stolee

Thanks,
Taylor