Re: [PATCH v3 16/16] midx.c: improve cache locality in midx_pack_order_cmp()

On Thu, Mar 11, 2021 at 12:05:42PM -0500, Taylor Blau wrote:

From: Jeff King <redacted>

There is a lot of pointer dereferencing in the pre-image version of
'midx_pack_order_cmp()', which this patch gets rid of.

Instead of comparing the pack preferred-ness and then the pack id, both
of these checks are done at the same time by using the high-order bit of
the pack id to represent whether it's preferred. Then the pack id and
offset are compared as usual.

This produces the same result so long as there are less than 2^31 packs,
which seems like a likely assumption to make in practice.

Obviously this patch is brilliant. ;)

Did we record any numbers to show the improvement here? I don't think it
can be demonstrated with this series (since most of the code is dead),
but I recall that this was motivated by a noticeable slowdown.

I briefly wondered whether the complicated midx_pack_order_cmp() in
pack-revindex.c, which is used for the bsearch() there, could benefit
from the same speedup. It's only log(n), of course, instead of n*log(n),
but one might imagine making "n" calls to it. I don't think it makes
sense, though. The pointer dereferencing there is into the midx mmap
itself. Creating an auxiliary array would defeat the purpose.

-Peff