Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check
- From
Jeff King <peff@peff.net>
- Date
- Dec 3, 2018, 22:04 UTC
- Message-ID
- <20181203220424.GA11883@sigill.intra.peff.net>
- In-Reply-To
- <221cb2e4-a024-e301-2b3f-e37dcd93795e@web.de>
On Sun, Dec 02, 2018 at 11:52:50AM +0100, René Scharfe wrote:
Show 16 quoted lines
> > And for mu.git, a ~20k object repo: > > > > Test origin/master peff/jk/loose-cache avar/check-collisions-config > > ------------------------------------------------------------------------------------------------------------------------- > > 0008.2: index-pack with 256*1 loose objects 0.59(0.91+0.06) 0.58(0.93+0.03) -1.7% 0.57(0.89+0.04) -3.4% > > 0008.3: index-pack with 256*10 loose objects 0.59(0.91+0.07) 0.59(0.92+0.03) +0.0% 0.57(0.89+0.03) -3.4% > > 0008.4: index-pack with 256*100 loose objects 0.59(0.91+0.05) 0.81(1.13+0.04) +37.3% 0.58(0.91+0.04) -1.7% > > 0008.5: index-pack with 256*250 loose objects 0.59(0.91+0.05) 1.23(1.51+0.08) +108.5% 0.58(0.91+0.04) -1.7% > > 0008.6: index-pack with 256*500 loose objects 0.59(0.90+0.06) 1.96(2.20+0.12) +232.2% 0.58(0.91+0.04) -1.7% > > 0008.7: index-pack with 256*750 loose objects 0.59(0.92+0.05) 2.72(2.92+0.17) +361.0% 0.58(0.90+0.04) -1.7% > > 0008.8: index-pack with 256*1000 loose objects 0.59(0.90+0.06) 3.50(3.67+0.21) +493.2% 0.57(0.90+0.04) -3.4% > > OK, here's another theory: The cache scales badly with increasing > numbers of loose objects because it sorts the array 256 times as it is > filled. Loading it fully and sorting once would help, as would using > one array per subdirectory.
Yeah, that makes sense. This was actually how I had planned to do it originally, but then I ended up just reusing the existing single-array approach from the abbrev code.
I hadn't actually thought about the repeated sortings (but that definitely makes sense that they would hurt in these pathological cases), but more just that we get a 256x reduction in N for our binary search (in fact we already do this first-byte lookup-table trick for pack index lookups).
Your patch looks good to me. We may want to do one thing on top:
Show 10 quoted lines
> diff --git a/object-store.h b/object-store.h
> index 8dceed0f31..ee67a50980 100644
> --- a/object-store.h
> +++ b/object-store.h
> @@ -20,7 +20,7 @@ struct object_directory {
> * Be sure to call odb_load_loose_cache() before using.
> */
> char loose_objects_subdir_seen[256];
> - struct oid_array loose_objects_cache;
> + struct oid_array loose_objects_cache[256];The comment in the context there is warning callers to remember to load the cache first. Now that we have individual caches, might it make sense to change the interface a bit, and make these members private. I.e., something like:
struct oid_array *odb_loose_cache(struct object_directory *odb,
int subdir_nr)
{
if (!loose_objects_subdir_seen[subdir_nr])
odb_load_loose_cache(odb, subdir_nr); /* or just inline it here */return &odb->loose_objects_cache[subdir_nr]; }
That's harder to get wrong, and this:
Show 13 quoted lines
> diff --git a/sha1-file.c b/sha1-file.c
> index 05f63dfd4e..d2f5e65865 100644
> --- a/sha1-file.c
> +++ b/sha1-file.c
> @@ -933,7 +933,8 @@ static int quick_has_loose(struct repository *r,
> prepare_alt_odb(r);
> for (odb = r->objects->odb; odb; odb = odb->next) {
> odb_load_loose_cache(odb, subdir_nr);
> - if (oid_array_lookup(&odb->loose_objects_cache, &oid) >= 0)
> + if (oid_array_lookup(&odb->loose_objects_cache[subdir_nr],
> + &oid) >= 0)
> return 1;
> }becomes:
struct oid_array *cache = odb_loose_cache(odb, subdir_nr); if (oid_array_lookup(cache, &oid)) return 1;
(An even simpler interface would be a single function that computes subdir_nr and does the lookup itself, but that would not be enough for find_short_object_filename()).
-Peff