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

From: Jeff King <peff@peff.net>
Date: Mar 29, 2021, 12:59 UTC
Message-ID: <YGHPINrwIZ1mKK+y@coredump.intra.peff.net>
In-Reply-To: <550e785f10ba14f166958501c007b75a04052a0d.1615482270.git.me@ttaylorr.com>

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

Show 12 quoted lines

> From: Jeff King <peff@peff.net>
> 
> 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