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

On Tue, Aug 04, 2020 at 08:31:53AM -0400, Derrick Stolee wrote:

On 8/3/2020 2:57 PM, Taylor Blau wrote:

quoted

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

quoted

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