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

[PATCH 7/7] commit-graph: write file format v2

From
Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>
Date
Feb 24, 2022, 20:38 UTC
Message-ID
<ade697c4d34a43d09db5be686591b2dc7d68f012.1645735117.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.1163.git.1645735117.gitgitgadget@gmail.com>
From: Derrick Stolee <derrickstolee@github.com>

The commit-graph file format v2 exists so we can modify the meaning of the Commit Data chunk to store corrected commit date offsets. Thus, we trigger the write to use this different file format only if the configured generation number version is 3.

The implementation needs to be careful of a few things to ensure we enable computing corrected commit dates and do not compute topological levels. We also still need the Generation Data Overflow chunk, but we compute the offsets into that chunk while writing the Commit Data chunk instead of the generation Data chunk.

Testing 'git merge-base v4.8 v4.9' in the Linux kernel with corrected commit dates, but the only difference being the file format (between generation number v2 and v3) we get these results:

Benchmark 1: generation number v2
  Time (mean ± σ):     144.4 ms ±   8.3 ms
  Range (min … max):   127.4 ms … 154.6 ms    20 runs
Benchmark 2: generation number v3
  Time (mean ± σ):     139.3 ms ±   7.3 ms
  Range (min … max):   125.1 ms … 148.1 ms    20 runs

This provides a 3.6% improvement, and the only reason is the reduced I/O. This test was run with hot caches, so I re-ran it in the cold-cache case, trying to demonstrate that this I/O cost is higher when reading directly from disk every time:

Benchmark 1: generation number v2
  Time (mean ± σ):     469.9 ms ±  14.8 ms
  Range (min … max):   434.5 ms … 494.4 ms    10 runs
Benchmark 2: generation number v3
  Time (mean ± σ):     413.4 ms ±  18.9 ms
  Range (min … max):   372.8 ms … 428.3 ms    10 runs
With cold caches, the improvement increases to 13.4%.
Signed-off-by: Derrick Stolee <derrickstolee@github.com>
---
 Documentation/config/commitgraph.txt |  4 ++-
 commit-graph.c                       | 46 +++++++++++++++++++++++++---
 commit.h                             |  1 +
 t/t5318-commit-graph.sh              | 25 ++++++++++++++-
 4 files changed, 69 insertions(+), 7 deletions(-)
diff --git a/Documentation/config/commitgraph.txt b/Documentation/config/commitgraph.txt
index 30604e4a4c2..79d57d06a67 100644
--- a/Documentation/config/commitgraph.txt
+++ b/Documentation/config/commitgraph.txt
@@ -1,7 +1,9 @@
 commitGraph.generationVersion::
 	Specifies the type of generation number version to use when writing
 	or reading the commit-graph file. If version 1 is specified, then
-	the corrected commit dates will not be written or read. Defaults to
+	the corrected commit dates will not be written or read. If version
+	3 is specified, then the commit-graph file will be slightly smaller,
+	but will be incompatible with some old versions of Git. Defaults to
 	2.
 
 commitGraph.maxNewFilters::
diff --git a/commit-graph.c b/commit-graph.c
index 366fc4d6e41..82f7401b283 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1035,6 +1035,7 @@ struct write_commit_graph_context {
 	struct progress *progress;
 	int progress_done;
 	uint64_t progress_cnt;
+	int version;
 
 	char *base_graph_name;
 	int num_commit_graphs_before;
@@ -1118,12 +1119,14 @@ static int write_graph_chunk_data(struct hashfile *f,
 	struct commit **list = ctx->commits.list;
 	struct commit **last = ctx->commits.list + ctx->commits.nr;
 	uint32_t num_extra_edges = 0;
+	int num_generation_data_overflows = 0;
 
 	while (list < last) {
 		struct commit_list *parent;
 		struct object_id *tree;
 		int edge_value;
 		uint32_t packedDate[2];
+		uint32_t generation_data;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
 		if (repo_parse_commit_no_graph(ctx->r, *list))
@@ -1203,7 +1206,18 @@ static int write_graph_chunk_data(struct hashfile *f,
 		else
 			packedDate[0] = 0;
 
-		packedDate[0] |= htonl(*topo_level_slab_at(ctx->topo_levels, *list) << 2);
+		if (ctx->version == GRAPH_VERSION_1)
+			generation_data = *topo_level_slab_at(ctx->topo_levels, *list);
+		else {
+			generation_data = commit_graph_data_at(*list)->generation - (*list)->date;
+			if (generation_data > GENERATION_NUMBER_V3_OFFSET_MAX) {
+				generation_data = CORRECTED_COMMIT_DATE_OFFSET_OVERFLOW_V3 |
+						  num_generation_data_overflows;
+				num_generation_data_overflows++;
+			}
+		}
+
+		packedDate[0] |= htonl(generation_data << 2);
 
 		packedDate[1] = htonl((*list)->date);
 		hashwrite(f, packedDate, 8);
@@ -1243,12 +1257,16 @@ static int write_graph_chunk_generation_data_overflow(struct hashfile *f,
 {
 	struct write_commit_graph_context *ctx = data;
 	int i;
+	timestamp_t offset_max = ctx->version >= 2 ?
+					GENERATION_NUMBER_V3_OFFSET_MAX :
+					GENERATION_NUMBER_V2_OFFSET_MAX;
+
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];
 		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
 		display_progress(ctx->progress, ++ctx->progress_cnt);
 
-		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX) {
+		if (offset > offset_max) {
 			hashwrite_be32(f, offset >> 32);
 			hashwrite_be32(f, (uint32_t) offset);
 		}
@@ -1474,6 +1492,13 @@ static void compute_topological_levels(struct write_commit_graph_context *ctx)
 	int i;
 	struct commit_list *list = NULL;
 
+	/*
+	 * Skip topological levels if file format version is two or more,
+	 * since the Commit Data chunk uses corrected commit date offsets.
+	 */
+	if (ctx->version >= 2)
+		return;
+
 	if (ctx->report_progress)
 		ctx->progress = start_delayed_progress(
 					_("Computing commit graph topological levels"),
@@ -1526,6 +1551,9 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 {
 	int i;
 	struct commit_list *list = NULL;
+	timestamp_t offset_max = ctx->version >= 2 ?
+					GENERATION_NUMBER_V3_OFFSET_MAX :
+					GENERATION_NUMBER_V2_OFFSET_MAX;
 
 	if (ctx->report_progress)
 		ctx->progress = start_delayed_progress(
@@ -1585,7 +1613,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 	for (i = 0; i < ctx->commits.nr; i++) {
 		struct commit *c = ctx->commits.list[i];
 		timestamp_t offset = commit_graph_data_at(c)->generation - c->date;
-		if (offset > GENERATION_NUMBER_V2_OFFSET_MAX)
+		if (offset > offset_max)
 			ctx->num_generation_data_overflows++;
 	}
 	stop_progress(&ctx->progress);
@@ -1908,7 +1936,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 	add_chunk(cf, GRAPH_CHUNKID_DATA, (hashsz + 16) * ctx->commits.nr,
 		  write_graph_chunk_data);
 
-	if (ctx->write_generation_data)
+	if (ctx->write_generation_data && ctx->version == GRAPH_VERSION_1)
 		add_chunk(cf, GRAPH_CHUNKID_GENERATION_DATA,
 			  sizeof(uint32_t) * ctx->commits.nr,
 			  write_graph_chunk_generation_data);
@@ -1936,7 +1964,7 @@ static int write_commit_graph_file(struct write_commit_graph_context *ctx)
 
 	hashwrite_be32(f, GRAPH_SIGNATURE);
 
-	hashwrite_u8(f, GRAPH_VERSION_1);
+	hashwrite_u8(f, ctx->version);
 	hashwrite_u8(f, oid_version());
 	hashwrite_u8(f, get_num_chunks(cf));
 	hashwrite_u8(f, ctx->num_commit_graphs_after - 1);
@@ -2317,6 +2345,14 @@ int write_commit_graph(struct object_directory *odb,
 	ctx->write_generation_data = (get_configured_generation_version(r) == 2);
 	ctx->num_generation_data_overflows = 0;
 
+	if (get_configured_generation_version(r) == 3)
+		ctx->version = GRAPH_VERSION_2;
+	else
+		ctx->version = GRAPH_VERSION_1;
+
+	if (ctx->version >= GRAPH_VERSION_2)
+		ctx->write_generation_data = 1;
+
 	bloom_settings.bits_per_entry = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_BITS_PER_ENTRY",
 						      bloom_settings.bits_per_entry);
 	bloom_settings.num_hashes = git_env_ulong("GIT_TEST_BLOOM_SETTINGS_NUM_HASHES",
diff --git a/commit.h b/commit.h
index 38cc5426615..a668b5cdec0 100644
--- a/commit.h
+++ b/commit.h
@@ -15,6 +15,7 @@
 #define GENERATION_NUMBER_V1_MAX 0x3FFFFFFF
 #define GENERATION_NUMBER_ZERO 0
 #define GENERATION_NUMBER_V2_OFFSET_MAX ((1ULL << 31) - 1)
+#define GENERATION_NUMBER_V3_OFFSET_MAX ((1ULL << 29) - 1)
 
 struct commit_list {
 	struct commit *item;
diff --git a/t/t5318-commit-graph.sh b/t/t5318-commit-graph.sh
index a14a13e5f7b..77e130ef63e 100755
--- a/t/t5318-commit-graph.sh
+++ b/t/t5318-commit-graph.sh
@@ -110,8 +110,13 @@ graph_read_expect() {
 	then
 		OPTIONS=" read_generation_data"
 	fi
+	VERSION=1
+	if test $GENERATION_VERSION -gt 2
+	then
+		VERSION=2
+	fi
 	cat >expect <<- EOF
-	header: 43475048 1 $(test_oid oid_version) $NUM_CHUNKS 0
+	header: 43475048 $VERSION $(test_oid oid_version) $NUM_CHUNKS 0
 	num_commits: $1
 	chunks: oid_fanout oid_lookup commit_metadata$OPTIONAL
 	options:$OPTIONS
@@ -343,6 +348,15 @@ test_expect_success 'build graph using --reachable' '
 graph_git_behavior 'append graph, commit 8 vs merge 1' full commits/8 merge/1
 graph_git_behavior 'append graph, commit 8 vs merge 2' full commits/8 merge/2
 
+test_expect_success 'write file format v2 with generation number v3' '
+	cd "$TRASH_DIRECTORY/full" &&
+	git -c commitGraph.generationVersion=3 commit-graph write --reachable &&
+	graph_read_expect "11" "extra_edges" 3
+'
+
+graph_git_behavior 'graph v2, commit 8 vs merge 1' full commits/8 merge/1
+graph_git_behavior 'graph v2, commit 8 vs merge 2' full commits/8 merge/2
+
 test_expect_success 'setup bare repo' '
 	cd "$TRASH_DIRECTORY" &&
 	git clone --bare --no-local full bare &&
@@ -880,6 +894,15 @@ test_expect_success TIME_IS_64BIT,TIME_T_IS_64BIT 'set up and verify repo with g
 
 graph_git_behavior 'generation data overflow chunk repo' repo left right
 
+test_expect_success TIME_IS_64BIT,TIME_T_IS_64BIT 'set up and verify repo with generation data overflow chunk (v3)' '
+	cd "$TRASH_DIRECTORY/repo" &&
+	git -c commitGraph.generationVersion=3 commit-graph write --reachable &&
+	graph_read_expect 10 "generation_data_overflow" 3 &&
+	git commit-graph verify
+'
+
+graph_git_behavior 'generation data overflow chunk repo' repo left right
+
 # Do not add tests at the end of this file, unless they require 64-bit
 # timestamps, since this portion of the script is only executed when
 # time data types have 64 bits.

-- 
gitgitgadget
Previous: Derrick StoleeNext: Junio C Hamano
Message 47 of 70 in “Commit-graph: Generation Number v2 Fixes, v3 implementation”
  1. 0/7 Commit-graph: Generation Number v2 Fixes, v3 implementationDerrick Stolee via GitGitGadget, Feb 24, 2022
  2. 2/7 commit-graph: fix ordering bug in generation numbersDerrick Stolee via GitGitGadget, Feb 24, 2022
  3. Junio C HamanoFeb 24, 2022
  4. Derrick StoleeFeb 25, 2022
  5. Junio C HamanoFeb 25, 2022
  6. 1/7 test-read-graph: include extra post-parse infoDerrick Stolee via GitGitGadget, Feb 24, 2022
  7. 3/7 commit-graph: start parsing generation v2 (again)Derrick Stolee via GitGitGadget, Feb 24, 2022
  8. Patrick SteinhardtFeb 28, 2022
  9. Derrick StoleeFeb 28, 2022
  10. Patrick SteinhardtFeb 28, 2022
  11. Derrick StoleeFeb 28, 2022
  12. Patrick SteinhardtMar 1, 2022
  13. Patrick SteinhardtMar 1, 2022
  14. Derrick StoleeMar 1, 2022
  15. Patrick SteinhardtMar 1, 2022
  16. Derrick StoleeMar 1, 2022
  17. Patrick SteinhardtMar 2, 2022
  18. Derrick StoleeMar 2, 2022
  19. Junio C HamanoMar 2, 2022
  20. Derrick StoleeMar 2, 2022
  21. Junio C HamanoMar 2, 2022
  22. Patrick SteinhardtMar 3, 2022
  23. Derrick StoleeMar 3, 2022
  24. Derrick StoleeMar 4, 2022
  25. Patrick SteinhardtMar 7, 2022
  26. Derrick StoleeMar 7, 2022
  27. Junio C HamanoMar 7, 2022
  28. Patrick SteinhardtMar 10, 2022
  29. Derrick StoleeMar 10, 2022
  30. 4/7 commit-graph: fix generation number v2 overflow valuesDerrick Stolee via GitGitGadget, Feb 24, 2022
  31. Junio C HamanoFeb 24, 2022
  32. Derrick StoleeFeb 25, 2022
  33. Junio C HamanoFeb 25, 2022
  34. 5/7 commit-graph: document file format v2Derrick Stolee via GitGitGadget, Feb 24, 2022
  35. Junio C HamanoFeb 24, 2022
  36. Ævar Arnfjörð BjarmasonFeb 25, 2022
  37. Derrick StoleeFeb 28, 2022
  38. Ævar Arnfjörð BjarmasonFeb 28, 2022
  39. Derrick StoleeFeb 28, 2022
  40. Ævar Arnfjörð BjarmasonFeb 28, 2022
  41. Derrick StoleeMar 1, 2022
  42. Ævar Arnfjörð BjarmasonMar 1, 2022
  43. Derrick StoleeMar 1, 2022
  44. 6/7 commit-graph: parse file format v2Derrick Stolee via GitGitGadget, Feb 24, 2022
  45. Junio C HamanoFeb 24, 2022
  46. Derrick StoleeFeb 25, 2022
  47. 7/7 commit-graph: write file format v2Derrick Stolee via GitGitGadget, Feb 24, 2022
  48. Junio C HamanoFeb 24, 2022
  49. Junio C HamanoFeb 24, 2022
  50. Derrick StoleeFeb 25, 2022
  51. 0/4 Commit-graph: Generation Number v2 FixesDerrick Stolee via GitGitGadget, Feb 28, 2022
  52. 1/4 test-read-graph: include extra post-parse infoDerrick Stolee via GitGitGadget, Feb 28, 2022
  53. Ævar Arnfjörð BjarmasonFeb 28, 2022
  54. 2/4 commit-graph: fix ordering bug in generation numbersDerrick Stolee via GitGitGadget, Feb 28, 2022
  55. Ævar Arnfjörð BjarmasonFeb 28, 2022
  56. 3/4 commit-graph: start parsing generation v2 (again)Derrick Stolee via GitGitGadget, Feb 28, 2022
  57. Ævar Arnfjörð BjarmasonFeb 28, 2022
  58. Derrick StoleeFeb 28, 2022
  59. 4/4 commit-graph: fix generation number v2 overflow valuesDerrick Stolee via GitGitGadget, Feb 28, 2022
  60. Ævar Arnfjörð BjarmasonFeb 28, 2022
  61. Ævar Arnfjörð BjarmasonMar 1, 2022
  62. 0/5 Commit-graph: Generation Number v2 FixesDerrick Stolee via GitGitGadget, Mar 1, 2022
  63. 3/5 commit-graph: fix ordering bug in generation numbersDerrick Stolee via GitGitGadget, Mar 1, 2022
  64. Junio C HamanoMar 1, 2022
  65. Junio C HamanoMar 1, 2022
  66. Derrick StoleeMar 2, 2022
  67. 5/5 commit-graph: fix generation number v2 overflow valuesDerrick Stolee via GitGitGadget, Mar 1, 2022
  68. 4/5 commit-graph: start parsing generation v2 (again)Derrick Stolee via GitGitGadget, Mar 1, 2022
  69. 1/5 test-read-graph: include extra post-parse infoDerrick Stolee via GitGitGadget, Mar 1, 2022
  70. 2/5 t5318: extract helpers to lib-commit-graph.shDerrick Stolee via GitGitGadget, Mar 1, 2022

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.