From: "René Scharfe" <l.s.r@web.de>
To: Jeff King <peff@peff.net>
Cc: "Git List" <git@vger.kernel.org>,
"Ævar Arnfjörð Bjarmason" <avarab@gmail.com>,
"Ramsay Jones" <ramsay@ramsayjones.plus.com>,
"Johannes Schindelin" <johannes.schindelin@gmx.de>,
"Junio C Hamano" <gitster@pobox.com>
Subject: Re: [PATCH 2/2] fsck: use oidset for skiplist
Date: Sat, 11 Aug 2018 22:59:57 +0200 [thread overview]
Message-ID: <f69e08d7-b29d-a9b7-b6d4-5294c4379133@web.de> (raw)
In-Reply-To: <20180811172350.GA2689@sigill.intra.peff.net>
Am 11.08.2018 um 19:23 schrieb Jeff King:
> On Sat, Aug 11, 2018 at 01:02:48PM -0400, Jeff King wrote:
>
>> - we could probably improve the speed of oidset. Two things I notice
>> about its implementation:
> Before any optimizations, my best-of-five timing for:
>
> git cat-file --batch-all-objects --unordered --buffer \
> --batch-check='%(objectname)' >/dev/null
>
> in git.git was:
>
> real 0m0.434s
> user 0m0.414s
> sys 0m0.020s
>
> That's enumerating every object in the repo but not doing much more than
> de-duping the names and printing them.
> So a single hash lookup per
> object does not seem to be measurable. And thus teaching oidset_insert()
> to do a single hash lookup for check-and-insert is unlikely to help us.
> On top of that, I tried using a pool to store the set entries:
> That drops my best-of-five to:
>
> real 0m0.300s
> user 0m0.288s
> sys 0m0.012s
>
> which is over a 25% speedup. So that does seem worth pursuing.
> For reference, the oid_array code path for cat-file is still:
>
> real 0m0.161s
> user 0m0.157s
> sys 0m0.004s
>
> but that's not completely apples to apples. The oidset code is also
> iterating the packfiles in a different order and generating a revidx
> (which I know is about 25ms in this repo). So a better test would
> actually swap one data structure out for the other with no other changes
> (I just happened to have this test handy, and really wanted to know
> whether the mem_pool stuff would help).
If the current oidset implementation is so bad, why not replace it with
one based on oid_array? ;-)
Intuitively I'd try a hashmap with no payload and open addressing via
sha1hash(), which should reduce memory allocations quite a bit -- no
need to store hash codes and next pointers, only an array of object IDs
with a fill rate of 50% or so. Deletions are a bit awkward with that
scheme, though; they could perhaps be implemented as insertions into a
second hashmap.
Balancing might become a problem. Your cat-file example should be fine,
but someone could decide to add only hashes with a certain prefix to
their skiplist, and lookups would lopsided.
But first we'd need something like test-sha1-array for oidset and
some kind of performance tests based on these helpers, right?
René
next prev parent reply other threads:[~2018-08-11 21:00 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-11 15:39 [PATCH 1/2] fsck: use strbuf_getline() to read skiplist file René Scharfe
2018-08-11 15:47 ` [PATCH 2/2] fsck: use oidset for skiplist René Scharfe
2018-08-11 16:54 ` Ævar Arnfjörð Bjarmason
2018-08-25 18:49 ` René Scharfe
2018-08-11 17:02 ` Jeff King
2018-08-11 17:23 ` Jeff King
2018-08-11 20:59 ` René Scharfe [this message]
2018-08-13 17:15 ` René Scharfe
2018-08-14 1:58 ` Jeff King
2018-08-14 2:03 ` Jeff King
2018-08-26 11:37 ` René Scharfe
2018-08-27 23:03 ` Jeff King
2018-10-01 19:15 ` René Scharfe
2018-10-01 20:26 ` Jeff King
2018-10-02 19:05 ` René Scharfe
2018-10-02 19:19 ` Jeff King
2018-08-13 17:15 ` René Scharfe
2018-08-14 2:01 ` Jeff King
2018-08-11 20:48 ` Ramsay Jones
2018-08-25 18:49 ` René Scharfe
2018-08-13 18:43 ` Junio C Hamano
2018-08-13 20:26 ` René Scharfe
2018-08-13 21:07 ` Junio C Hamano
2018-08-13 23:09 ` René Scharfe
2018-08-11 16:48 ` [PATCH 1/2] fsck: use strbuf_getline() to read skiplist file Jeff King
2018-08-11 21:00 ` René Scharfe
2018-08-25 18:50 ` [PATCH v2 " René Scharfe
2018-08-27 23:00 ` Jeff King
2018-08-25 18:50 ` [PATCH v2 2/2] fsck: use oidset for skiplist René Scharfe
2018-08-27 7:37 ` Ævar Arnfjörð Bjarmason
2018-08-27 15:23 ` René Scharfe
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
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f69e08d7-b29d-a9b7-b6d4-5294c4379133@web.de \
--to=l.s.r@web.de \
--cc=avarab@gmail.com \
--cc=git@vger.kernel.org \
--cc=gitster@pobox.com \
--cc=johannes.schindelin@gmx.de \
--cc=peff@peff.net \
--cc=ramsay@ramsayjones.plus.com \
/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.
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 NNTP newsgroup(s).