From: Jeff King <peff@peff.net>
To: "René Scharfe" <l.s.r@web.de>
Cc: "Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
"Geert Jansen" <gerardu@amazon.com>,
"Junio C Hamano" <gitster@pobox.com>,
"git@vger.kernel.org" <git@vger.kernel.org>,
"Takuto Ikuta" <tikuta@chromium.org>
Subject: Re: [PATCH 8/9] sha1-file: use loose object cache for quick existence check
Date: Mon, 3 Dec 2018 17:04:24 -0500 [thread overview]
Message-ID: <20181203220424.GA11883@sigill.intra.peff.net> (raw)
In-Reply-To: <221cb2e4-a024-e301-2b3f-e37dcd93795e@web.de>
On Sun, Dec 02, 2018 at 11:52:50AM +0100, René Scharfe wrote:
> > 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:
> 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:
> 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
next prev parent reply other threads:[~2018-12-03 22:04 UTC|newest]
Thread overview: 99+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-25 18:38 [RFC PATCH] index-pack: improve performance on NFS Jansen, Geert
2018-10-26 0:21 ` Junio C Hamano
2018-10-26 20:38 ` Ævar Arnfjörð Bjarmason
2018-10-27 7:26 ` Junio C Hamano
2018-10-27 9:33 ` Jeff King
2018-10-27 11:22 ` Ævar Arnfjörð Bjarmason
2018-10-28 22:50 ` [PATCH 0/4] index-pack: optionally turn off SHA-1 collision checking Ævar Arnfjörð Bjarmason
2018-10-30 2:49 ` Geert Jansen
2018-10-30 9:04 ` Junio C Hamano
2018-10-30 18:43 ` [PATCH v2 0/3] index-pack: test updates Ævar Arnfjörð Bjarmason
2018-11-13 20:19 ` [PATCH v3] index-pack: add ability to disable SHA-1 collision check Ævar Arnfjörð Bjarmason
2018-11-14 7:09 ` Junio C Hamano
2018-11-14 12:40 ` Ævar Arnfjörð Bjarmason
2018-10-30 18:43 ` [PATCH v2 1/3] pack-objects test: modernize style Ævar Arnfjörð Bjarmason
2018-10-30 18:43 ` [PATCH v2 2/3] pack-objects tests: don't leave test .git corrupt at end Ævar Arnfjörð Bjarmason
2018-10-30 18:43 ` [PATCH v2 3/3] index-pack tests: don't leave test repo dirty " Ævar Arnfjörð Bjarmason
2018-10-28 22:50 ` [PATCH 1/4] pack-objects test: modernize style Ævar Arnfjörð Bjarmason
2018-10-28 22:50 ` [PATCH 2/4] pack-objects tests: don't leave test .git corrupt at end Ævar Arnfjörð Bjarmason
2018-10-28 22:50 ` [PATCH 3/4] index-pack tests: don't leave test repo dirty " Ævar Arnfjörð Bjarmason
2018-10-28 22:50 ` [PATCH 4/4] index-pack: add ability to disable SHA-1 collision check Ævar Arnfjörð Bjarmason
2018-10-29 15:04 ` [RFC PATCH] index-pack: improve performance on NFS Jeff King
2018-10-29 15:09 ` Jeff King
2018-10-29 19:36 ` Ævar Arnfjörð Bjarmason
2018-10-29 23:27 ` Jeff King
2018-11-07 22:55 ` Geert Jansen
2018-11-08 12:02 ` Jeff King
2018-11-08 20:58 ` Geert Jansen
2018-11-08 21:18 ` Jeff King
2018-11-08 21:55 ` Geert Jansen
2018-11-08 22:20 ` Ævar Arnfjörð Bjarmason
2018-11-09 10:11 ` Ævar Arnfjörð Bjarmason
2018-11-12 14:31 ` Jeff King
2018-11-12 14:46 ` [PATCH 0/9] caching loose objects Jeff King
2018-11-12 14:46 ` [PATCH 1/9] fsck: do not reuse child_process structs Jeff King
2018-11-12 15:26 ` Derrick Stolee
2018-11-12 14:47 ` [PATCH 2/9] submodule--helper: prefer strip_suffix() to ends_with() Jeff King
2018-11-12 18:23 ` Stefan Beller
2018-11-12 14:48 ` [PATCH 3/9] rename "alternate_object_database" to "object_directory" Jeff King
2018-11-12 15:30 ` Derrick Stolee
2018-11-12 15:36 ` Jeff King
2018-11-12 19:41 ` Ramsay Jones
2018-11-12 14:48 ` [PATCH 4/9] sha1_file_name(): overwrite buffer instead of appending Jeff King
2018-11-12 15:32 ` Derrick Stolee
2018-11-12 14:49 ` [PATCH 5/9] handle alternates paths the same as the main object dir Jeff King
2018-11-12 15:38 ` Derrick Stolee
2018-11-12 15:46 ` Jeff King
2018-11-12 15:50 ` Derrick Stolee
2018-11-12 14:50 ` [PATCH 6/9] sha1-file: use an object_directory for " Jeff King
2018-11-12 15:48 ` Derrick Stolee
2018-11-12 16:09 ` Jeff King
2018-11-12 19:04 ` Stefan Beller
2018-11-22 17:42 ` Jeff King
2018-11-12 18:48 ` Stefan Beller
2018-11-12 14:50 ` [PATCH 7/9] object-store: provide helpers for loose_objects_cache Jeff King
2018-11-12 19:24 ` René Scharfe
2018-11-12 20:16 ` Jeff King
2018-11-12 14:54 ` [PATCH 8/9] sha1-file: use loose object cache for quick existence check Jeff King
2018-11-12 16:00 ` Derrick Stolee
2018-11-12 16:01 ` Ævar Arnfjörð Bjarmason
2018-11-12 16:21 ` Jeff King
2018-11-12 22:18 ` Ævar Arnfjörð Bjarmason
2018-11-12 22:30 ` Ævar Arnfjörð Bjarmason
2018-11-13 10:02 ` Ævar Arnfjörð Bjarmason
2018-11-14 18:21 ` René Scharfe
2018-12-02 10:52 ` René Scharfe
2018-12-03 22:04 ` Jeff King [this message]
2018-12-04 21:45 ` René Scharfe
2018-12-05 4:46 ` Jeff King
2018-12-05 6:02 ` René Scharfe
2018-12-05 6:51 ` Jeff King
2018-12-05 8:15 ` Jeff King
2018-12-05 18:41 ` René Scharfe
2018-12-05 20:17 ` Jeff King
2018-11-12 22:44 ` Geert Jansen
2018-11-27 20:48 ` René Scharfe
2018-12-01 19:49 ` Jeff King
2018-11-12 14:55 ` [PATCH 9/9] fetch-pack: drop custom loose object cache Jeff King
2018-11-12 19:25 ` René Scharfe
2018-11-12 19:32 ` Ævar Arnfjörð Bjarmason
2018-11-12 20:07 ` Jeff King
2018-11-12 20:13 ` René Scharfe
2018-11-12 16:02 ` [PATCH 0/9] caching loose objects Derrick Stolee
2018-11-12 19:10 ` Stefan Beller
2018-11-09 13:43 ` [RFC PATCH] index-pack: improve performance on NFS Ævar Arnfjörð Bjarmason
2018-11-09 16:08 ` Duy Nguyen
2018-11-10 14:04 ` Ævar Arnfjörð Bjarmason
2018-11-12 14:34 ` Jeff King
2018-11-12 22:58 ` Geert Jansen
2018-10-27 14:04 ` Duy Nguyen
2018-10-29 15:18 ` Jeff King
2018-10-29 0:48 ` Junio C Hamano
2018-10-29 15:20 ` Jeff King
2018-10-29 18:43 ` Ævar Arnfjörð Bjarmason
2018-10-29 21:34 ` Geert Jansen
2018-10-29 21:50 ` Jeff King
2018-10-29 22:21 ` Geert Jansen
2018-10-29 22:27 ` Jeff King
2018-10-29 22:35 ` Stefan Beller
2018-10-29 23:29 ` Jeff King
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20181203220424.GA11883@sigill.intra.peff.net \
--to=peff@peff.net \
--cc=avarab@gmail.com \
--cc=gerardu@amazon.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=l.s.r@web.de \
--cc=tikuta@chromium.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).