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

[GSOC Patch v4 2/4] commit-graph: introduce commit_graph_data_slab

From
Abhishek Kumar <abhishekkumar8222@gmail.com>
Date
Jun 17, 2020, 09:14 UTC
Message-ID
<20200617091411.14650-3-abhishekkumar8222@gmail.com>
In-Reply-To
<20200617091411.14650-1-abhishekkumar8222@gmail.com>

The struct commit is used in many contexts. However, members `generation` and `graph_pos` are only used for commit-graph related operations and otherwise waste memory.

This wastage would have been more pronounced as we transition to generation number v2, which uses 64-bit generation number instead of current 32-bits.

As they are often accessed together, let's introduce struct commit_graph_data and move them to a commit_graph_data slab.

While the overall test suite runs just as fast as master, (series: 26m48s, master: 27m34s, faster by 2.87%), certain commands like `git merge-base --is-ancestor` were slowed by 40% as discovered by Szeder Gábor [1]. After minimizing commit-slab access, the slow down persists but is closer to 20%.

Derrick Stolee believes the slow down is attributable to the underlying algorithm rather than the slowness of commit-slab access [2] and we will follow-up in a later series.

[1]: https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/ [2]: https://lore.kernel.org/git/13db757a-9412-7f1e-805c-8a028c4ab2b1@gmail.com/

Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>
---

On linux.git with HEAD at 08bf1a27 (Merge tag 'powerpc-5.8-2' of git://git.kernel.org/pub/scm/linux/kernel/git/powerpc/linux, 2020-06-13):

`git merge-base --is-ancestor HEAD~50000 HEAD`
Time (master):    0.787s
Time (series):    0.927s
Change:           17.79%    (slower)
Max RSS (master): 177694kb
Max RSS (series): 177707kb
Change:           0.01%     (more)
`git gc`
Time (master):    3m55s
Time (series):    3m38s
Change:           7.23%     (faster)
Max RSS (master): 4889868kb
Max RSS (series): 4911960kb
Change:           0.45%     (more)

Earlier implementation of commit_graph_data_at() was incorrect, as we used to iterate from old slab count to new slab count - assuming all intermediate slabs are allocated. This is incorrect as the slabs are allocated only when there's a corresponding commit.

It now makes *two slab accesses* in the worst case, but it's okay since the worst case occurs once nearly every (512kb / 8b) commits.

 commit-graph.c | 78 +++++++++++++++++++++++++++++++++++++++++++-------
 commit-graph.h | 10 +++++++
 2 files changed, 78 insertions(+), 10 deletions(-)
diff --git a/commit-graph.c b/commit-graph.c
index 2ff042fbf4..8ad7d202b2 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -87,6 +87,58 @@ static int commit_pos_cmp(const void *va, const void *vb)
 	       commit_pos_at(&commit_pos, b);
 }
 
+define_commit_slab(commit_graph_data_slab, struct commit_graph_data);
+static struct commit_graph_data_slab commit_graph_data_slab =
+	COMMIT_SLAB_INIT(1, commit_graph_data_slab);
+
+uint32_t commit_graph_position(const struct commit *c)
+{
+	struct commit_graph_data *data =
+		commit_graph_data_slab_peek(&commit_graph_data_slab, c);
+
+	return data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;
+}
+
+uint32_t commit_graph_generation(const struct commit *c)
+{
+	struct commit_graph_data *data =
+		commit_graph_data_slab_peek(&commit_graph_data_slab, c);
+
+	if (!data)
+		return GENERATION_NUMBER_INFINITY;
+	else if (data->graph_pos == COMMIT_NOT_FROM_GRAPH)
+		return GENERATION_NUMBER_INFINITY;
+
+	return data->generation;
+}
+
+static struct commit_graph_data *commit_graph_data_at(const struct commit *c)
+{
+	unsigned int i, nth_slab;
+	struct commit_graph_data *data =
+		commit_graph_data_slab_peek(&commit_graph_data_slab, c);
+
+	if (data)
+		return data;
+
+	nth_slab = c->index / commit_graph_data_slab.slab_size;
+	data = commit_graph_data_slab_at(&commit_graph_data_slab, c);
+
+	/*
+	 * commit-slab initializes elements with zero, overwrite this with
+	 * COMMIT_NOT_FROM_GRAPH for graph_pos.
+	 *
+	 * We avoid initializing generation with checking if graph position
+	 * is not COMMIT_NOT_FROM_GRAPH.
+	 */
+	for (i = 0; i < commit_graph_data_slab.slab_size; i++) {
+		commit_graph_data_slab.slab[nth_slab][i].graph_pos =
+			COMMIT_NOT_FROM_GRAPH;
+	}
+
+	return data;
+}
+
 static int commit_gen_cmp(const void *va, const void *vb)
 {
 	const struct commit *a = *(const struct commit **)va;
@@ -1020,7 +1072,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 		else
 			packedDate[0] = 0;
 
-		packedDate[0] |= htonl((*list)->generation << 2);
+		packedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);
 
 		packedDate[1] = htonl((*list)->date);
 		hashwrite(f, packedDate, 8);
@@ -1251,9 +1303,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 					_("Computing commit graph generation numbers"),
 					ctx->commits.nr);
 	for (i = 0; i < ctx->commits.nr; i++) {
+		uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
+
 		display_progress(ctx->progress, i + 1);
-		if (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&
-		    ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)
+		if (generation != GENERATION_NUMBER_INFINITY &&
+		    generation != GENERATION_NUMBER_ZERO)
 			continue;
 
 		commit_list_insert(ctx->commits.list[i], &list);
@@ -1264,22 +1318,26 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)
 			uint32_t max_generation = 0;
 
 			for (parent = current->parents; parent; parent = parent->next) {
-				if (parent->item->generation == GENERATION_NUMBER_INFINITY ||
-				    parent->item->generation == GENERATION_NUMBER_ZERO) {
+				generation = commit_graph_data_at(parent->item)->generation;
+
+				if (generation == GENERATION_NUMBER_INFINITY ||
+				    generation == GENERATION_NUMBER_ZERO) {
 					all_parents_computed = 0;
 					commit_list_insert(parent->item, &list);
 					break;
-				} else if (parent->item->generation > max_generation) {
-					max_generation = parent->item->generation;
+				} else if (generation > max_generation) {
+					max_generation = generation;
 				}
 			}
 
 			if (all_parents_computed) {
-				current->generation = max_generation + 1;
+				struct commit_graph_data *data = commit_graph_data_at(current);
+
+				data->generation = max_generation + 1;
 				pop_commit(&list);
 
-				if (current->generation > GENERATION_NUMBER_MAX)
-					current->generation = GENERATION_NUMBER_MAX;
+				if (data->generation > GENERATION_NUMBER_MAX)
+					data->generation = GENERATION_NUMBER_MAX;
 			}
 		}
 	}
diff --git a/commit-graph.h b/commit-graph.h
index 3ba0da1e5f..28f89cdf3e 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -135,4 +135,14 @@ void free_commit_graph(struct commit_graph *);
  */
 void disable_commit_graph(struct repository *r);
 
+struct commit_graph_data {
+	uint32_t graph_pos;
+	uint32_t generation;
+};
+
+/*
+ * Commits should be parsed before accessing generation, graph positions.
+ */
+uint32_t commit_graph_generation(const struct commit *);
+uint32_t commit_graph_position(const struct commit *);
 #endif

-- 
2.27.0
Previous: Abhishek KumarNext: Abhishek Kumar
Message 35 of 39 in “Move generation, graph_pos to a slab”
  1. 0/3 Move generation, graph_pos to a slabAbhishek Kumar, Jun 4, 2020
  2. 1/3 commit: introduce helpers for generation slabAbhishek Kumar, Jun 4, 2020
  3. Derrick StoleeJun 4, 2020
  4. Junio C HamanoJun 4, 2020
  5. Jakub NarębskiJun 5, 2020
  6. 3/3 commit: convert commit->graph_pos to a slabAbhishek Kumar, Jun 4, 2020
  7. Jakub NarębskiJun 7, 2020
  8. 2/3 commit: convert commit->generation to a slabAbhishek Kumar, Jun 4, 2020
  9. Derrick StoleeJun 4, 2020
  10. Junio C HamanoJun 4, 2020
  11. Jakub NarębskiJun 6, 2020
  12. Derrick StoleeJun 4, 2020
  13. Junio C HamanoJun 4, 2020
  14. SZEDER GáborJun 7, 2020
  15. Abhishek KumarJun 8, 2020
  16. SZEDER GáborJun 8, 2020
  17. Derrick StoleeJun 8, 2020
  18. SZEDER GáborJun 8, 2020
  19. Jakub NarębskiJun 8, 2020
  20. Jakub NarębskiJun 5, 2020
  21. 0/4 Move generation, graph_pos to a slabAbhishek Kumar, Jun 7, 2020
  22. 1/4 commit-graph: introduce commit_graph_data_slabAbhishek Kumar, Jun 7, 2020
  23. Taylor BlauJun 15, 2020
  24. 2/4 commit: move members graph_pos, generation to a slabAbhishek Kumar, Jun 7, 2020
  25. SZEDER GáborJun 8, 2020
  26. Derrick StoleeJun 8, 2020
  27. 3/4 commit-graph: use generation directly when writing commit-graphAbhishek Kumar, Jun 7, 2020
  28. Jakub NarębskiJun 8, 2020
  29. Taylor BlauJun 15, 2020
  30. 4/4 commit-graph: minimize commit_graph_data_slab accessAbhishek Kumar, Jun 7, 2020
  31. Jakub NarębskiJun 8, 2020
  32. Taylor BlauJun 15, 2020
  33. 0/4 Move generation, graph_pos to a slabAbhishek Kumar, Jun 17, 2020
  34. 1/4 object: drop parsed_object_pool->commit_countAbhishek Kumar, Jun 17, 2020
  35. 2/4 commit-graph: introduce commit_graph_data_slabAbhishek Kumar, Jun 17, 2020
  36. 3/4 commit: move members graph_pos, generation to a slabAbhishek Kumar, Jun 17, 2020
  37. 4/4 commit-graph: minimize commit_graph_data_slab accessAbhishek Kumar, Jun 17, 2020
  38. Derrick StoleeJun 19, 2020
  39. Junio C HamanoJun 19, 2020

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.