René Scharfe [off-list ref] wrote:
Am 29.06.21 um 22:53 schrieb Eric Wong:
quoted
With many alternates, the duplicate check in alt_odb_usable()
wastes many cycles doing repeated fspathcmp() on every existing
alternate. Use a khash to speed up lookups by odb->path.
Since the kh_put_* API uses the supplied key without
duplicating it, we also take advantage of it to replace both
xstrdup() and strbuf_release() in link_alt_odb_entry() with
strbuf_detach() to avoid the allocation and copy.
In a test repository with 50K alternates and each of those 50K
alternates having one alternate each (for a total of 100K total
alternates); this speeds up lookup of a non-existent blob from
over 16 minutes to roughly 2.7 seconds on my busy workstation.
Yay for hashmaps! :)
quoted
Note: all underlying git object directories were small and
unpacked with only loose objects and no packs. Having to load
packs increases times significantly.
Signed-off-by: Eric Wong <redacted>
---
object-file.c | 33 ++++++++++++++++++++++-----------
object-store.h | 17 +++++++++++++++++
object.c | 2 ++
3 files changed, 41 insertions(+), 11 deletions(-)
diff --git a/object-file.c b/object-file.c
index f233b440b2..304af3a172 100644
--- a/object-file.c
+++ b/object-file.c
@@ -517,9 +517,9 @@ const char *loose_object_path(struct repository *r, struct strbuf *buf,
*/
static int alt_odb_usable(struct raw_object_store *o,
struct strbuf *path,
- const char *normalized_objdir)
+ const char *normalized_objdir, khiter_t *pos)
{
- struct object_directory *odb;
+ int r;
/* Detect cases where alternate disappeared */
if (!is_directory(path->buf)) {@@ -533,14 +533,22 @@ static int alt_odb_usable(struct raw_object_store *o,
* Prevent the common mistake of listing the same
* thing twice, or object directory itself.
*/
- for (odb = o->odb; odb; odb = odb->next) {
- if (!fspathcmp(path->buf, odb->path))
- return 0;
+ if (!o->odb_by_path) {
+ khiter_t p;
+
+ o->odb_by_path = kh_init_odb_path_map();
+ assert(!o->odb->next);
+ p = kh_put_odb_path_map(o->odb_by_path, o->odb->path, &r);
So on the first run you not just create the hashmap, but you also
pre-populate it with the main object directory. Makes sense. The
hashmap wouldn't even be created in repositories without alternates.
quoted
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
Our other callers don't handle a negative return code because it would
indicate an allocation failure, and in our version we use ALLOC_ARRAY,
which dies on error. So you don't need that check here, but we better
clarify that in khash.h.
quoted
+ assert(r == 1); /* never used */
+ kh_value(o->odb_by_path, p) = o->odb;
}
if (!fspathcmp(path->buf, normalized_objdir))
return 0;
-
- return 1;
+ *pos = kh_put_odb_path_map(o->odb_by_path, path->buf, &r);
+ if (r < 0) die_errno(_("kh_put_odb_path_map"));
Dito.
quoted
+ /* r: 0 = exists, 1 = never used, 2 = deleted */
+ return r == 0 ? 0 : 1;
The comment indicates that khash would be nicer to use if it had an
enum for the kh_put return values. Perhaps, but that should be done in
another series.
Agreed for another series. I've also found myself wishing khash
used enums. But I'm also not sure how much changing of 3rd
party code we should be doing...
I like the solution in oidset.c to make this more readable, though: Call
the return value "added" instead of "r" and then a "return !added;"
makes sense without additional comments.
quoted
}
/*
diff --git a/object-store.h b/object-store.h
index ec32c23dcb..20c1cedb75 100644
--- a/object-store.h
+++ b/object-store.h
@@ -7,6 +7,8 @@
#include "oid-array.h"
#include "strbuf.h"
#include "thread-utils.h"
+#include "khash.h"
+#include "dir.h"
struct object_directory {
struct object_directory *next;@@ -30,6 +32,19 @@ struct object_directory {
char *path;
};
+static inline int odb_path_eq(const char *a, const char *b)
+{
+ return !fspathcmp(a, b);
+}
This is not specific to the object store. It could be called fspatheq
and live in dir.h. Or dir.c -- a surprising amount of code seems to
necessary for that negation (https://godbolt.org/z/MY7Wda3a7). Anyway,
it's just an idea for another series.
No JS here for godbolt, but there's also a bunch of "!fspathcmp"
here that could probably be changed to fspatheq.
quoted
+
+static inline int odb_path_hash(const char *str)
+{
+ return ignore_case ? strihash(str) : __ac_X31_hash_string(str);
+}
The internal Attractive Chaos (__ac_*) macros should be left confined
to khash.h, I think. Its alias kh_str_hash_func would be better
suited here.
Do we want to use the K&R hash function here at all, though? If we
use FNV-1 when ignoring case, why not also use it (i.e. strhash) when
respecting it? At least that's done in builtin/sparse-checkout.c,
dir.c and merge-recursive.c. This is just handwaving and yammering
about lack of symmetry, but I do wonder how your performance numbers
look with strhash. If it's fine then we could package this up as
fspathhash..
Yeah, I think fspathhash should be path_hash in merge-recursive.c
(and path_hash eliminated).
I don't have performance numbers, and I doubt hash function
performance is much overhead, here. I used X31 since it was
local to khash.
I would prefer we only have one non-cryptographic hash
implementation to reduce cognitive overhead, so maybe we can
drop X31 entirely for FNV-1. I'd also prefer we only have khash
or hashmap, not both.
And I also wonder how it looks if you use strihash unconditionally.
I guess case collisions are usually rare and branching based on a
global variable may be more expensive than case folding.
*shrug* I'll let somebody with more appropriate systems do
benchmarks, there. But it could be an easy switch once
fspathhash is in place.