From: Eric Wong <e@80x24.org>
To: "René Scharfe" <l.s.r@web.de>
Cc: git@vger.kernel.org, Jeff King <peff@peff.net>
Subject: Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache
Date: Tue, 6 Jul 2021 23:21:59 +0000 [thread overview]
Message-ID: <20210706232159.GB8624@dcvr> (raw)
In-Reply-To: <ab757bce-3b51-afac-312c-ea2e883cf0bf@web.de>
René Scharfe <l.s.r@web.de> wrote:
> Am 29.06.21 um 22:53 schrieb Eric Wong:
> > --- a/alloc.c
> > +++ b/alloc.c
> > @@ -14,6 +14,7 @@
> > #include "tree.h"
> > #include "commit.h"
> > #include "tag.h"
> > +#include "oidtree.h"
> > #include "alloc.h"
> >
> > #define BLOCKING 1024
> > @@ -123,6 +124,11 @@ void *alloc_commit_node(struct repository *r)
> > return c;
> > }
> >
> > +void *alloc_from_state(struct alloc_state *alloc_state, size_t n)
> > +{
> > + return alloc_node(alloc_state, n);
> > +}
> > +
>
> Why extend alloc.c instead of using mem-pool.c? (I don't know which fits
> better, but when you say "memory pool" and not use mem-pool.c I just have
> to ask..)
I didn't know mem-pool.c existed :x (And I've always known
about alloc.c).
Perhaps we could merge them in another series to avoid further
confusion.
> > +void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
> > +{
> > + struct oidtree_node *on;
> > +
> > + if (!ot->mempool)
> > + ot->mempool = allocate_alloc_state();
> > + if (!oid->algo)
> > + BUG("oidtree_insert requires oid->algo");
> > +
> > + on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
> > + oidcpy_with_padding((struct object_id *)on->n.k, oid);
> > +
> > + /*
> > + * n.b. we shouldn't get duplicates, here, but we'll have
> > + * a small leak that won't be freed until oidtree_destroy
> > + */
>
> Why shouldn't we get duplicates? That depends on the usage of oidtree,
> right? The current user is fine because we avoid reading the same loose
> object directory twice using the loose_objects_subdir_seen bitmap.
Yes, it reflects the current caller.
> The leak comes from the allocation above, which is not used in case we
> already have the key in the oidtree. So we need memory for all
> candidates, not just the inserted candidates. That's probably
> acceptable in most use cases.
Yes, I think the small, impossible-due-to-current-usage leak is
an acceptable trade off.
> We can do better by keeping track of the unnecessary allocation in
> struct oidtree and recycling it at the next insert attempt, however.
> That way we'd only waste at most one slot.
It'd involve maintaining a free list; which may be better
suited to being in alloc_state or mem_pool. That would also
increase the size of a struct *somewhere* and add a small
amount of code complexity, too.
> > + cb_insert(&ot->t, &on->n, sizeof(*oid));
> > +}
> > +
> > +int oidtree_contains(struct oidtree *ot, const struct object_id *oid)
> > +{
> > + struct object_id k = { 0 };
> > + size_t klen = sizeof(k);
> > + oidcpy_with_padding(&k, oid);
>
> Why initialize k; isn't oidcpy_with_padding() supposed to overwrite it
> completely?
Ah, I only added oidcpy_with_padding later into the development
of this patch.
> > +
> > + if (oid->algo == GIT_HASH_UNKNOWN) {
> > + k.algo = hash_algo_by_ptr(the_hash_algo);
> > + klen -= sizeof(oid->algo);
> > + }
>
> This relies on the order of the members hash and algo in struct
> object_id to find a matching hash if we don't actually know algo. It
> also relies on the absence of padding after algo. Would something like
> this make sense?
>
> BUILD_ASSERT_OR_ZERO(offsetof(struct object_id, algo) + sizeof(k.algo) == sizeof(k));
Maybe... I think a static assertion that object_id.hash be the
first element of "struct object_id" is definitely needed, at
least.
> And why set k.algo to some arbitrary value if we ignore it anyway? I.e.
> why not keep it GIT_HASH_UNKNOWN, as set by oidcpy_with_padding()?
Good point, shortening klen would've been all that was needed.
> > +void oidtree_each(struct oidtree *ot, const struct object_id *oid,
> > + size_t oidhexlen, oidtree_iter fn, void *arg)
> > +{
> > + size_t klen = oidhexlen / 2;
> > + struct oidtree_iter_data x = { 0 };
> > +
> > + x.fn = fn;
> > + x.arg = arg;
> > + x.algo = oid->algo;
> > + if (oidhexlen & 1) {
> > + x.last_byte = oid->hash[klen];
> > + x.last_nibble_at = &klen;
> > + }
> > + cb_each(&ot->t, (const uint8_t *)oid, klen, iter, &x);
> > +}
>
> Clamp oidhexlen at GIT_MAX_HEXSZ? Or die?
I think an assertion would be enough, here.
init_object_disambiguation already clamps to the_hash_algo->hexsz
next prev parent reply other threads:[~2021-07-06 23:22 UTC|newest]
Thread overview: 99+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-06-24 0:58 [PATCH] speed up alt_odb_usable() with many alternates Eric Wong
2021-06-27 2:47 ` [PATCH 0/5] optimizations for many odb alternates Eric Wong
2021-06-27 2:47 ` [PATCH 1/5] speed up alt_odb_usable() with many alternates Eric Wong
2021-06-27 2:47 ` [PATCH 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-06-27 2:47 ` [PATCH 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-06-27 10:23 ` René Scharfe
2021-06-28 23:09 ` Eric Wong
2021-06-27 2:47 ` [PATCH 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-06-27 2:47 ` [PATCH 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-06-29 14:42 ` Junio C Hamano
2021-06-29 20:17 ` Eric Wong
2021-06-29 20:53 ` [PATCH v2 0/5] optimizations for many alternates Eric Wong
2021-07-07 23:10 ` [PATCH v3 " Eric Wong
2021-07-07 23:10 ` [PATCH v3 1/5] speed up alt_odb_usable() with " Eric Wong
2021-07-08 0:20 ` Junio C Hamano
2021-07-08 1:14 ` Eric Wong
2021-07-08 4:30 ` Junio C Hamano
2021-07-07 23:10 ` [PATCH v3 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-07-08 4:57 ` Junio C Hamano
2021-07-07 23:10 ` [PATCH v3 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-07-07 23:10 ` [PATCH v3 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-07-07 23:10 ` [PATCH v3 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-06-29 20:53 ` [PATCH v2 1/5] speed up alt_odb_usable() with many alternates Eric Wong
2021-07-03 10:05 ` René Scharfe
2021-07-04 9:02 ` René Scharfe
2021-07-06 23:01 ` Eric Wong
2021-06-29 20:53 ` [PATCH v2 2/5] avoid strlen via strbuf_addstr in link_alt_odb_entry Eric Wong
2021-06-29 20:53 ` [PATCH v2 3/5] make object_directory.loose_objects_subdir_seen a bitmap Eric Wong
2021-06-29 20:53 ` [PATCH v2 4/5] oidcpy_with_padding: constify `src' arg Eric Wong
2021-06-29 20:53 ` [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache Eric Wong
2021-07-04 9:02 ` René Scharfe
2021-07-06 23:21 ` Eric Wong [this message]
2021-07-04 9:32 ` Ævar Arnfjörð Bjarmason
2021-07-07 23:12 ` Eric Wong
2021-08-06 15:31 ` Andrzej Hunt
2021-08-06 17:53 ` René Scharfe
2021-08-07 22:49 ` Eric Wong
2021-08-09 1:35 ` Carlo Arenas
2021-08-09 1:38 ` [PATCH/RFC 0/3] pedantic errors in next Carlo Marcelo Arenas Belón
2021-08-09 1:38 ` [PATCH/RFC 1/3] oidtree: avoid nested struct oidtree_node Carlo Marcelo Arenas Belón
2021-08-09 1:38 ` [PATCH/RFC 2/3] object-store: avoid extra ';' from KHASH_INIT Carlo Marcelo Arenas Belón
2021-08-09 15:53 ` Junio C Hamano
2021-08-09 1:38 ` [PATCH/RFC 3/3] ci: run a pedantic build as part of the GitHub workflow Carlo Marcelo Arenas Belón
2021-08-09 10:50 ` Bagas Sanjaya
2021-08-09 22:03 ` Carlo Arenas
2021-08-09 14:56 ` Phillip Wood
2021-08-09 22:48 ` Carlo Arenas
2021-08-10 15:24 ` Phillip Wood
2021-08-10 18:25 ` Junio C Hamano
2021-08-30 11:36 ` Ævar Arnfjörð Bjarmason
2021-08-31 20:28 ` Carlo Arenas
2021-08-31 20:51 ` Ævar Arnfjörð Bjarmason
2021-08-31 23:54 ` Carlo Arenas
2021-09-01 1:52 ` Jeff King
2021-09-01 17:55 ` Junio C Hamano
2021-08-30 11:40 ` Ævar Arnfjörð Bjarmason
2021-09-01 9:19 ` [RFC PATCH v2 0/4] developer: support pedantic Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 1/4] developer: retire USE_PARENS_AROUND_GETTEXT_N support Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 2/4] developer: enable pedantic by default Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 3/4] developer: add an alternative script for detecting broken N_() Carlo Marcelo Arenas Belón
2021-09-01 9:19 ` [RFC PATCH v2 4/4] developer: move detect-compiler out of the main directory Carlo Marcelo Arenas Belón
2021-09-01 10:10 ` [RFC PATCH v2 0/4] developer: support pedantic Jeff King
2021-09-01 11:25 ` [PATCH] gettext: remove optional non-standard parens in N_() definition Ævar Arnfjörð Bjarmason
2021-09-01 17:31 ` Eric Sunshine
2021-09-02 9:13 ` Jeff King
2021-09-02 19:19 ` Junio C Hamano
2021-09-01 11:27 ` [RFC PATCH v2 0/4] developer: support pedantic Ævar Arnfjörð Bjarmason
2021-09-01 18:03 ` Carlo Arenas
2021-09-03 17:02 ` [PATCH v3 0/3] support pedantic in developer mode Carlo Marcelo Arenas Belón
2021-09-03 17:02 ` [PATCH v3 1/3] gettext: remove optional non-standard parens in N_() definition Carlo Marcelo Arenas Belón
2021-09-10 15:39 ` Ævar Arnfjörð Bjarmason
2021-09-03 17:02 ` [PATCH v3 2/3] win32: allow building with pedantic mode enabled Carlo Marcelo Arenas Belón
2021-09-03 18:47 ` René Scharfe
2021-09-03 20:13 ` Carlo Marcelo Arenas Belón
2021-09-03 20:32 ` Junio C Hamano
2021-09-03 20:38 ` René Scharfe
2021-09-04 9:37 ` René Scharfe
2021-09-04 14:42 ` Carlo Arenas
2021-09-27 23:04 ` Jonathan Tan
2021-09-28 0:30 ` Carlo Arenas
2021-09-28 16:50 ` Jonathan Tan
2021-09-28 17:37 ` Junio C Hamano
2021-09-28 20:16 ` Jonathan Tan
2021-09-29 1:00 ` Carlo Arenas
2021-09-29 15:55 ` Junio C Hamano
2021-09-03 17:02 ` [PATCH v3 3/3] developer: enable pedantic by default Carlo Marcelo Arenas Belón
2021-09-05 7:54 ` [PATCH v3 0/3] support pedantic in developer mode Ævar Arnfjörð Bjarmason
2021-08-09 16:44 ` [PATCH/RFC 0/3] pedantic errors in next Junio C Hamano
2021-08-09 20:10 ` Eric Wong
2021-08-10 6:16 ` Carlo Marcelo Arenas Belón
2021-08-10 19:30 ` René Scharfe
2021-08-10 23:49 ` Carlo Arenas
2021-08-11 0:57 ` Carlo Arenas
2021-08-11 14:57 ` René Scharfe
2021-08-11 17:20 ` Junio C Hamano
2021-08-10 18:59 ` [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache René Scharfe
2021-08-10 19:40 ` René Scharfe
2021-08-14 20:00 ` [PATCH] oidtree: avoid unaligned access to crit-bit tree René Scharfe
2021-08-16 19:11 ` Junio C Hamano
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=20210706232159.GB8624@dcvr \
--to=e@80x24.org \
--cc=git@vger.kernel.org \
--cc=l.s.r@web.de \
--cc=peff@peff.net \
/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).