git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v3 4/6] odb/source-files: simplify directory duplication detection

From
Patrick Steinhardt <ps@pks.im>
Date
Oct 28, 2026, 07:11 UTC
Message-ID
<20261028-pks-odb-files-reload-alternates-v3-4-011ddb64b626@pks.im>
In-Reply-To
<20261028-pks-odb-files-reload-alternates-v3-0-011ddb64b626@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%

Rename `dirs_paths_icase` to `dir_paths_iscase` to match the naming of the newly added set.

Signed-off-by: Patrick Steinhardt <ps@pks.im>
---
 odb/source-files.c | 120 ++++++++++++++++++++++++-----------------------------
 odb/source-files.h |  17 +++-----
 2 files changed, 60 insertions(+), 77 deletions(-)
diff --git a/odb/source-files.c b/odb/source-files.c
index d66949b7de5..8b63d0eff2b 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,57 @@ 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.
+	 *
+	 * 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.
 	 */
-	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 +349,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 +1262,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 837e8903044..595a4e78eef 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 set 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.341.g393f52fd96.dirty
Previous: Patrick SteinhardtNext: Christian Couder
Message 31 of 38 in “odb/files: reload alternates on retry again”
  1. 0/4 odb/files: reload alternates on retry againPatrick Steinhardt, Oct 20, 2026
  2. 1/4 odb/source-files: rename alternates-related functionsPatrick Steinhardt, Oct 20, 2026
  3. 2/4 odb/source-files: reload alternates on retryPatrick Steinhardt, Oct 20, 2026
  4. Christian CouderOct 21, 2026
  5. Patrick SteinhardtOct 23, 2026
  6. 3/4 odb/source-files: avoid rechecking already-known alternatesPatrick Steinhardt, Oct 20, 2026
  7. 4/4 odb/source-files: only reload alternates when the file has changedPatrick Steinhardt, Oct 20, 2026
  8. Junio C HamanoOct 20, 2026
  9. Patrick SteinhardtOct 21, 2026
  10. 0/6 odb/files: reload alternates on retry againPatrick Steinhardt, Oct 23, 2026
  11. 1/6 odb/source-files: rename alternates-related functionsPatrick Steinhardt, Oct 23, 2026
  12. 2/6 odb/source-files: always load alternates via primary object directoryPatrick Steinhardt, Oct 23, 2026
  13. Christian CouderOct 27, 2026
  14. 3/6 odb/source-files: reload alternates on retryPatrick Steinhardt, Oct 23, 2026
  15. 4/6 odb/source-files: simplify directory duplication detectionPatrick Steinhardt, Oct 23, 2026
  16. Christian CouderOct 27, 2026
  17. Patrick SteinhardtOct 27, 2026
  18. 5/6 odb/source-files: avoid stat'ing already-known alternatesPatrick Steinhardt, Oct 23, 2026
  19. Christian CouderOct 27, 2026
  20. Patrick SteinhardtOct 27, 2026
  21. Christian CouderOct 27, 2026
  22. Patrick SteinhardtOct 28, 2026
  23. 6/6 odb/source-files: only reload alternates when the file has changedPatrick Steinhardt, Oct 23, 2026
  24. Christian CouderOct 27, 2026
  25. Patrick SteinhardtOct 27, 2026
  26. Christian CouderOct 27, 2026
  27. 0/6 odb/files: reload alternates on retry againPatrick Steinhardt, Oct 28, 2026
  28. 1/6 odb/source-files: rename alternates-related functionsPatrick Steinhardt, Oct 28, 2026
  29. 2/6 odb/source-files: always load alternates via primary object directoryPatrick Steinhardt, Oct 28, 2026
  30. 3/6 odb/source-files: reload alternates on retryPatrick Steinhardt, Oct 28, 2026
  31. 4/6 odb/source-files: simplify directory duplication detectionPatrick Steinhardt, Oct 28, 2026
  32. Christian CouderOct 28, 2026
  33. Patrick SteinhardtOct 28, 2026
  34. Junio C HamanoOct 28, 2026
  35. 5/6 odb/source-files: avoid stat'ing already-known alternatesPatrick Steinhardt, Oct 28, 2026
  36. 6/6 odb/source-files: only reload alternates when the file has changedPatrick Steinhardt, Oct 28, 2026
  37. Junio C HamanoOct 28, 2026
  38. Patrick SteinhardtOct 29, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.