Re: [PATCH 00/20] pack-revindex: prepare for on-disk reverse index

From: Derrick Stolee <stolee@gmail.com>
Date: Jan 11, 2021, 12:07 UTC
Message-ID: <75ba9979-1a1f-de9f-c2cc-1433d30ed09d@gmail.com>
In-Reply-To: <cover.1610129796.git.me@ttaylorr.com>

On 1/8/2021 1:16 PM, Taylor Blau wrote: ...

Show 6 quoted lines

>   - First, a new API is proposed.
> 
>   - Then, uses of the old API are removed one by one and replaced with their
>     new counterparts.
> 
>   - Finally, without any callers remaining, the old API is removed.

This patch series has a clear layout that was easy to follow.

In a vacuum, the conversions from immediate struct member lookups to API calls seems like adding overhead to something that is done frequently in a loop. However, you do justify it:

Show 12 quoted lines

> Generating the reverse index in memory for repositories with large packs has two
> significant drawbacks:
> 
>   - It requires allocating sizeof(struct revindex_entry) per packed object.
> 
>   - It requires us to sort the entries by their pack offset. This is implemented
>     in sort_revindex() using a radix sort, but still takes considerable time (as
>     benchmarks found in the second series demonstrate).
> 
> Both of these can be addressed by storing the reverse index in a new '.rev' file
> alongside the packs. This file is written once (during pack creation), and does
> not require sorting when accessed, since it is stored in a sorted order.

Even if these method calls do add a bit of overhead to each access, it helps to not compute the table from scratch before any access is possible.

This will be particularly valuable for operations that use only a few position lookups, such as "is object A reachable from commit C?"

Operations that iterate through every object in a bitmap are more likely to notice a difference, but that will probably be visible in the next series.

My comments on this series are very minor.

I made only one comment about "if (method() < 0)" versus "if (method())" but that pattern appears in multiple patches. _If_ you decide to change that pattern, then I'm sure you can find all uses.

Reviewed-by: Derrick Stolee <dstolee@microsoft.com>

Thanks, -Stolee