From: Patrick Steinhardt Date: Fri, 23 Oct 2026 12:48:03 GMT Subject: [PATCH v2 4/6] odb/source-files: simplify directory duplication detection Message-ID: <20261023-pks-odb-files-reload-alternates-v2-4-30559d7ff43b@pks.im> In-Reply-To: <20261023-pks-odb-files-reload-alternates-v2-0-30559d7ff43b@pks.im> When loading alternates it may happen that we try to add the same alternate multiple times, either because "info/alternates" contains duplicate entries or because one of its alternates matches the primary object directory. We try to detect such duplicates via two mechanisms: - We have a hashmap of `struct odb_files_dir`, mapped by their absolute paths. If the path of an alternate is already present in this map we skip it. - We have another, explicit check to check whether the path of an alternate matches the primary object directory. We can simplify both of these mechanisms by turning the map into a strset, as we never access the values of the map. On the one hand this gives us simpler interfaces to access the set. And on the other hand this allows us to add two entries for the primary object directory: one for the real path, and one for the absolute path. Note that there is one gotcha though: when "core.ignorecase" is set then the expectation is that we deduplicate alternates case-insensitively. But we can also make that work rather easily by downcasing all paths we add in that case. Despite being significantly simpler, this also gives us a speedup because we don't have to resolve the realpath of the primary object directory on every call to `odb_files_dir_is_usable()` anymore. Using the same benchmark as in the preceding commit: Benchmark 1: ./git -C /tmp/repo cat-file --batch-check (rev = 5946a564cd~) (50 runs) mean ± σ min … max Wall Time 289.0 ms ± 2.2 ms 285.8 ms … 295.1 ms Memory 5.6 MiB ± 0.1 MiB 5.4 MiB … 5.7 MiB Benchmark 2: ./git -C /tmp/repo cat-file --batch-check (rev = 5946a564cd) (50 runs) mean ± σ min … max Wall Time 183.8 ms ± 1.2 ms 181.5 ms … 186.9 ms -36.4% (1.6x faster) Memory 5.6 MiB ± 0.1 MiB 5.3 MiB … 5.7 MiB -0.5% Benchmark 3: ./git -C /tmp/repo cat-file --batch-check (rev = HEAD~) (50 runs) mean ± σ min … max Wall Time 293.2 ms ± 2.7 ms 288.8 ms … 299.7 ms +1.5% Memory 5.9 MiB ± 0.1 MiB 5.7 MiB … 6.1 MiB +5.0% Benchmark 4: ./git -C /tmp/repo cat-file --batch-check (rev = HEAD) (50 runs) mean ± σ min … max Wall Time 266.5 ms ± 2.8 ms 262.6 ms … 276.7 ms -7.8% Memory 5.9 MiB ± 0.1 MiB 5.6 MiB … 6.1 MiB +5.1% Signed-off-by: Patrick Steinhardt --- odb/source-files.c | 103 +++++++++++++++++++---------------------------------- odb/source-files.h | 17 ++++----- 2 files changed, 43 insertions(+), 77 deletions(-) diff --git a/odb/source-files.c b/odb/source-files.c index d66949b7de..22e96828d2 100644 --- a/odb/source-files.c +++ b/odb/source-files.c @@ -72,7 +72,7 @@ static void odb_source_files_free(struct odb_source *source) odb_files_dir_free(files->dirs); files->dirs = next; } - hashmap_clear(&files->dirs_by_path); + strset_clear(&files->dir_paths); odb_source_release(&files->base); free(files); @@ -176,60 +176,15 @@ static int odb_source_files_create_on_disk(struct odb_source *source, return ret; } -/* - * NEEDSWORK: we're using "core.ignoreCase" to deduplicate alternates that - * _may_ be the same. This requires quite a bit of boilerplate for dubious - * benefit: - * - * - Duplicating alternates should really only lead to regressed performance. - * - * - We don't properly resolve symlinks or mointpoints, so we may still end - * up duplicating alternates. - * - * - The value may be lying, in which case we might deduplicate alternates - * that are in fact not mapping to the same directory. - * - * We should investigate whether we can remove this whole mechanism outright. - */ -static int odb_files_dir_paths_cmp(struct odb_source_files *files, - const char *a, const char *b) -{ - if (files->dirs_paths_icase < 0) { - int icase = 0; - repo_config_get_bool(files->base.odb->repo, "core.ignorecase", &icase); - files->dirs_paths_icase = icase; - } - - return files->dirs_paths_icase ? strcasecmp(a, b) : strcmp(a, b); -} - -static int odb_files_dir_by_path_cmp(const void *cb_data, - const struct hashmap_entry *entry, - const struct hashmap_entry *entry_or_key, - const void *keydata) -{ - struct odb_source_files *files = (struct odb_source_files *)cb_data; - const struct odb_files_dir *dir = container_of(entry, const struct odb_files_dir, by_path_entry); - const char *path = keydata; - - if (!path) - path = container_of(entry_or_key, const struct odb_files_dir, by_path_entry)->abspath; - - return odb_files_dir_paths_cmp(files, dir->abspath, path); -} - /* * Return non-zero iff the path is usable as an alternate object directory. */ static bool odb_files_dir_is_usable(struct odb_source_files *files, const char *path) { - struct strbuf normalized_objdir = STRBUF_INIT; - struct hashmap_entry key; + struct strbuf buf = STRBUF_INIT; bool usable = false; - strbuf_realpath(&normalized_objdir, files->base.path, 1); - /* Detect cases where alternate disappeared */ if (!is_directory(path)) { error(_("object directory %s does not exist; " @@ -239,28 +194,40 @@ static bool odb_files_dir_is_usable(struct odb_source_files *files, } /* - * Prevent the common mistake of listing the same - * thing twice, or object directory itself. + * Prevent the common mistake of listing the same thing twice, or + * object directory itself. */ - if (!hashmap_get_size(&files->dirs_by_path)) { + if (strset_empty(&files->dir_paths)) { + files->dir_paths_icase = 0; + repo_config_get_bool(files->base.odb->repo, "core.ignorecase", + &files->dir_paths_icase); + + strbuf_realpath(&buf, files->base.path, 1); + if (files->dir_paths_icase) + strbuf_tolower(&buf); + strset_add(&files->dir_paths, buf.buf); + for (struct odb_files_dir *dir = files->dirs; dir; dir = dir->next) { - hashmap_entry_init(&dir->by_path_entry, - strihash(dir->abspath)); - hashmap_add(&files->dirs_by_path, &dir->by_path_entry); + strbuf_reset(&buf); + strbuf_addstr(&buf, dir->abspath); + if (files->dir_paths_icase) + strbuf_tolower(&buf); + strset_add(&files->dir_paths, buf.buf); } } - if (!odb_files_dir_paths_cmp(files, path, normalized_objdir.buf)) - goto out; + strbuf_reset(&buf); + strbuf_addstr(&buf, path); + if (files->dir_paths_icase) + strbuf_tolower(&buf); - hashmap_entry_init(&key, strihash(path)); - if (hashmap_get(&files->dirs_by_path, &key, path)) + if (strset_contains(&files->dir_paths, buf.buf)) goto out; usable = true; out: - strbuf_release(&normalized_objdir); + strbuf_release(&buf); return usable; } @@ -365,11 +332,17 @@ static void add_alternate_recursively(struct odb_source_files *files, *files->dirs_tail = alternate; files->dirs_tail = &(alternate->next); - hashmap_entry_init(&alternate->by_path_entry, strihash(alternate->abspath)); - if (hashmap_get(&files->dirs_by_path, &alternate->by_path_entry, - alternate->abspath)) - BUG("object directory must not yet exist"); - hashmap_add(&files->dirs_by_path, &alternate->by_path_entry); + if (files->dir_paths_icase) { + struct strbuf path = STRBUF_INIT; + + strbuf_addstr(&path, alternate->abspath); + strbuf_tolower(&path); + strset_add(&files->dir_paths, path.buf); + + strbuf_release(&path); + } else { + strset_add(&files->dir_paths, alternate->abspath); + } /* recursively add alternates */ read_alternates(alternate->abspath, &alternates); @@ -1272,11 +1245,9 @@ struct odb_source_files *odb_source_files_new(struct object_database *odb, CALLOC_ARRAY(files, 1); odb_source_init(&files->base, odb, ODB_SOURCE_FILES, object_dir); - hashmap_init(&files->dirs_by_path, odb_files_dir_by_path_cmp, files, 0); - files->dirs_paths_icase = -1; - files->dirs = odb_files_dir_new(odb, object_dir, true); files->dirs_tail = &files->dirs->next; + strset_init(&files->dir_paths); files->base.free = odb_source_files_free; files->base.close = odb_source_files_close; diff --git a/odb/source-files.h b/odb/source-files.h index 837e890304..8695b6ee91 100644 --- a/odb/source-files.h +++ b/odb/source-files.h @@ -2,6 +2,7 @@ #define ODB_SOURCE_FILES_H #include "odb/source.h" +#include "strmap.h" struct odb_source_loose; struct odb_source_packed; @@ -18,12 +19,6 @@ struct odb_files_dir { /* List of alternate object directories. */ struct odb_files_dir *next; - /* - * Entry in the files source's map of directories, keyed by this - * directory's path. - */ - struct hashmap_entry by_path_entry; - /* The two sources derived from this object directory. */ struct odb_source_loose *loose; struct odb_source_packed *packed; @@ -55,17 +50,17 @@ struct odb_source_files { struct odb_files_dir **dirs_tail; /* - * Map of object directories, keyed by their respective paths. This - * map is used to detect the case where the same directory is - * registered multiple times. + * Set of directory paths that have already been linked into this + * source. This map is used to detect the case where the same directory + * is registered multiple times. */ - struct hashmap dirs_by_path; + struct strset dir_paths; /* * Whether directory paths shall be compared case-insensitively, as * determined by "core.ignoreCase". */ - int dirs_paths_icase; + int dir_paths_icase; }; /* Allocate and initialize a new object source. */ -- 2.56.0.307.g5fe7bd680c.dirty