Skip to contentSkip to conversation

Move generation, graph_pos to a slab

PATCH Superseded Abhishek Kumar 4 participants 14 messages Jun 12, 2020 – Jun 17, 2020

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover Move generation, graph_pos to a slab

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.

While the overall test suite runs slightly faster than master (series: 27m10s, master: 27ms34s, faster by 2.35%), certain commands like git merge-base --is-ancestory are slowed by nearly 40% as discovered by SDEZER Gabor [1].

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 on that in a later series.

I did not mention maximum RSS in the commit messages as they were nearly identical (series: 68104kb, master: 68040kb, fewer by <0.1%). This leads me to conclude that either the test using maximum memory involves commit graph or did not involve the struct commit at all. The move to commit-slab reduces memory footprint for the cases where struct commit is used but members generation and graph position are not. Average RSS would have been a good and more representative measure, but unfortunately time(1) could not measure it on my system.

With this, I feel the patch will require minor fixes, if any. I am moving ahead with working the next step of "Implement Generation Number v2" that is proper handling of commit-graph format change.

Based on the discussions, I feel we should compute both generation number v1 and the date offset value with storing date offsets in a new chunk as the cost is mostly from walking the commits.

Abhishek Kumar (4):
alloc: introduce parsed_commits_count
commit-graph: introduce commit_graph_data_slab
commit: move members graph_pos, generation to a slab
commit-graph: minimize commit_graph_data_slab access

 alloc.c                         |   6 +-
 blame.c                         |   2 +-
 bloom.c                         |   7 +-
 commit-graph.c                  | 122 ++++++++++++++++++++++++--------
 commit-graph.h                  |  10 +++
 commit-reach.c                  |  69 +++++++++++-------
 commit.c                        |   8 ++-
 contrib/coccinelle/commit.cocci |  18 +++++
 revision.c                      |  20 +++---
 9 files changed, 188 insertions(+), 74 deletions(-)
Signature · 21 lines
2.27.0

Changes in v3:
- Introduce alloc commit to fix the failing diff-submodule test.
- Elaborate on performance and slow down noticed in the commit message.

Changes in v2:
- Introduce struct commit_graph_data.
- Merge `graph_pos`, `generation` slabs into a single,
  `commit_graph_data` slab.
- Use graph position for an intermediate check for generation, saving
  the cost of initializing generation numbers.
- Add an follow-up patch caching results of slab access in local
  variables.
- Move coccinelle transformation to commit.coccinelle instead of
  creating new scripts.
- Elaborate on removing default values from init_commit_node().
- Revert moving macro constants (e.g. COMMIT_NOT_FROM_GRAPH,
  GENERATION_NUMBER_ZERO) from commit.h to commit-graph.h

CI Build: https://travis-ci.com/github/abhishekkumar2718/git  
#1 lore raw

PATCH v3 1/4 alloc: introduce parsed_commits_count

Commit slab relies on uniqueness of commit->index to access data. As submodules are repositories on their own, alloc_commit_index() (which depends on repository->parsed_objects->commit_count) no longer returns unique values.

This would break tests once we move generation and graph_pos into a commit slab, as commits of supermodule and submodule can have the same index but must have different graph positions.

Let's introduce a counter variable, parsed_commits_count to keep track of parsed commits so far.

---

CI Build for the failing tests:
https://travis-ci.com/github/abhishekkumar2718/git/jobs/345413840

 alloc.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
alloc.c +3 -1
index 1c64c4dd16..29f0e3aa80 100644
@@ -101,7 +101,9 @@ void *alloc_object_node(struct repository *r)
 
 static unsigned int alloc_commit_index(struct repository *r)
 {
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;
+	return parsed_commits_count++;
 }
 
 void init_commit_node(struct repository *r, struct commit *c)
Signature · 1 line
2.27.0
#2 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

alloc.c void *alloc_object_node(struct repository *r) · line 107

Quoted 7 lines · Abhishek Kumar

static unsigned int alloc_commit_index(struct repository *r) {

alloc.c +3 -1
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;
+	return parsed_commits_count++;
 }

Hmph, ugly.

The need for this hack, which butchers the function that explicitly takes a repository as its parameter so that parsed commits can be counted per repository to not count commits per repository, makes the whole thing smell fishy.

There shouldn't be a reason why a commit in the superproject and another commit in the submodule need to be in the same commit graph in the first place.

Instead of breaking the function like this, the right "fix" may be to make the commit slab per repository, because the commit index are taken from the separate namespace per repository.

#3 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

Quoted 17 lines · Junio C Hamano

alloc.c void *alloc_object_node(struct repository *r) · line 107

Quoted 7 lines · Abhishek Kumar

static unsigned int alloc_commit_index(struct repository *r) {

alloc.c +3 -1
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;
+	return parsed_commits_count++;
 }

Hmph, ugly.

The need for this hack, which butchers the function that explicitly takes a repository as its parameter so that parsed commits can be counted per repository to not count commits per repository, makes the whole thing smell fishy.

Quoted 7 lines

There shouldn't be a reason why a commit in the superproject and another commit in the submodule need to be in the same commit graph in the first place.

Instead of breaking the function like this, the right "fix" may be to make the commit slab per repository, because the commit index are taken from the separate namespace per repository.

Given a commit object (i.e. "struct commit *"), currently there is no way to tell from which repository it came from. So from that point of view, we cannot identify which commit slab to use, unless we add a back-pointer that says from which repository each commit object came from, but that makes the commit object even heavier.

Back when 14ba97f8 (alloc: allow arbitrary repositories for alloc functions, 2018-05-15) made the count per repository (which you are reverting with this patch), there must have been a reason why it did so. We know that commit slab code wants you to count globally and that is why you wrote this patch, but don't other parts of the code expect and rely on the commits being counted per repository? In other words, with this change, who are you breaking to help the commit slab code?

Cc'ing SZEDER who also have touched this and made the function static early last year.

Thanks.

#4 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

Quoted 8 lines · Junio C Hamano

Back when 14ba97f8 (alloc: allow arbitrary repositories for alloc functions, 2018-05-15) made the count per repository (which you are reverting with this patch), there must have been a reason why it did so. We know that commit slab code wants you to count globally and that is why you wrote this patch, but don't other parts of the code expect and rely on the commits being counted per repository? In other words, with this change, who are you breaking to help the commit slab code?

I did a bit more digging, as I had a bit of time after pushing today's integration result out, and it turns out that in the today's code, c->index is the only thing that uses this counter. It is set in init_commit_node() function, which is called from object.c when an in-core commit object is created. The callchain looks like this:

object_as_type(struct repository *, struct object *, enum object_type, int quiet)
-> init_commit_node(struct repository *, struct commit *)

       -> alloc_commit_index(struct repository *)

What is interesting is that object_as_type() takes the parameter "struct repository *" ONLY BECAUSE it needs to pass something to init_commit_node(), which in turn takes it ONLY BECAUSE the alloc_commit_index() wants one to be passed.

Since the ONLY reason why there needs a monotorically increasing counter of in-core commit objects is because we need to be able to index into the commit slab, and because we cannot make commit slabs per-repository due to the lack of backpointer from an in-core commit object to the repository it belongs to, reverting 14ba97f8 (alloc:
allow arbitrary repositories for alloc functions, 2018-05-15) is a reasonable thing to do, but then since the only reason the above three functions in the callchain take "struct repository *" is because the bottom-most alloc_commit_index() wants it WHEN IT DOES NOT USE IT, it would be good to get rid of the "struct repository" parameter from the functions involved in the callchain altogether.

Then we won't have to ask the "who are we breaking with this change" question. At that point it would be clear that everybody would be OK with a single counter to ensure uniqueness of in-core commit across all the in-core repository instances.

Thanks.

#5 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

In reply to Abhishek Kumar

Review

Quoted 7 lines · Abhishek Kumar

static unsigned int alloc_commit_index(struct repository *r) {

(quoted diff) +3 -1
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;
+	return parsed_commits_count++;
 }

I'll queue this as-is, together with the rest of the series, but with the following SQUASH??? to document why we are counting globally.

I do not think r->parsed_objects->*_count is used by anybody, and we probably can eventually get rid of these stats fields, and when that happens, we may want to lose the "struct repository *" pointer from the functions in the callchain, but not right now.

Thanks.

 alloc.c | 5 +++++
 1 file changed, 5 insertions(+)
alloc.c +5 -0
index 29f0e3aa80..ee92661b71 100644
@@ -99,6 +99,11 @@ void *alloc_object_node(struct repository *r)
 	return obj;
 }
 
+/*
+ * The returned count is to be used as an index into commit slabs,
+ * that are *NOT* maintained per repository, and that is why a single
+ * global counter is used.
+ */
 static unsigned int alloc_commit_index(struct repository *r)
 {
 	static unsigned int parsed_commits_count = 0;
Signature · 1 line
2.27.0-90-geebb51ba8c
#6 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

Quoted 43 lines · Junio C Hamano

Review

Quoted 7 lines · Abhishek Kumar

static unsigned int alloc_commit_index(struct repository *r) {

(quoted diff) +3 -1
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;
+	return parsed_commits_count++;
 }

I'll queue this as-is, together with the rest of the series, but with the following SQUASH??? to document why we are counting globally.

I do not think r->parsed_objects->*_count is used by anybody, and we probably can eventually get rid of these stats fields, and when that happens, we may want to lose the "struct repository *" pointer from the functions in the callchain, but not right now.

Thanks.

 alloc.c | 5 +++++
 1 file changed, 5 insertions(+)
alloc.c +5 -0
index 29f0e3aa80..ee92661b71 100644
@@ -99,6 +99,11 @@ void *alloc_object_node(struct repository *r)
 	return obj;
 }
 
+/*
+ * The returned count is to be used as an index into commit slabs,
+ * that are *NOT* maintained per repository, and that is why a single
+ * global counter is used.
+ */
 static unsigned int alloc_commit_index(struct repository *r)
 {
 	static unsigned int parsed_commits_count = 0;
Signature · 1 line
2.27.0-90-geebb51ba8c

Thanks for taking a closer look. I have created an issue on gitgitgadget [1] to get rid of commit count and avoid passing repository to the functions anymore.

[1]: https://github.com/gitgitgadget/git/issues/657

Abhishek

#7 lore raw

Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count

In reply to Abhishek Kumar
Quoted 8 lines · Abhishek Kumar

Commit slab relies on uniqueness of commit->index to access data. As submodules are repositories on their own, alloc_commit_index() (which depends on repository->parsed_objects->commit_count) no longer returns unique values.

This would break tests once we move generation and graph_pos into a commit slab, as commits of supermodule and submodule can have the same index but must have different graph positions.

First, commits of supermodule and of submodule are in different graphs, so I don't see why they have to be in the same serialized commit-graph file.

Second, Git stores many different types of information on slab already. How comes that we have not had any problems till now?

There is contains_cache, commit_seen, indegree_slab, author_date_slab, commit_base, commit_pos, bloom_filter_slab, buffer_slab, commit_rev_name, commit_names, commit_name_slab, saved_parents, blame_suspects, commit_todo_item.

Quoted 3 lines

Let's introduce a counter variable, parsed_commits_count to keep track of parsed commits so far.

All right, thought it might be worth mentioning that it is a global variable, or rather a static variable in a function.

Quoted 7 lines

---

CI Build for the failing tests:
https://travis-ci.com/github/abhishekkumar2718/git/jobs/345413840

The failed tests are, from what I see:
- t4060-diff-submodule-option-diff-format.sh
- t4041-diff-submodule-option.sh
- t4059-diff-submodule-not-initialized.sh

Quoted 9 lines
  alloc.c | 4 +++-
  1 file changed, 3 insertions(+), 1 deletion(-)
alloc.c +0 -0
index 1c64c4dd16..29f0e3aa80 100644

alloc.c void *alloc_object_node(struct repository *r) · line 105

Quoted 6 lines
alloc.c +2 -1
@@ -101,7 +101,9 @@ void *alloc_object_node(struct repository *r)
 
  static unsigned int alloc_commit_index(struct repository *r)
  {
-	return r->parsed_objects->commit_count++;
+	static unsigned int parsed_commits_count = 0;
+	r->parsed_objects->commit_count++;

Do we use r->parsed_objects->commit_count anywhere?

alloc.c void *alloc_object_node(struct repository *r) · line 106

Quoted 1 line
alloc.c +1 -0
+	return parsed_commits_count++;

Does it matter that it is not thread safe, because it is not atomic? Shouldn't it be

  +	static _Atomic unsigned int parsed_commits_count = 0;

or

  +	static _Atomic unsigned int parsed_commits_count = ATOMIC_VAR_INIT(0);

(If it is allowed).

Quoted 4 lines
alloc.c +0 -0
  }
 
  void init_commit_node(struct repository *r, struct commit *c)
#8 lore raw

PATCH v3 2/4 commit-graph: introduce commit_graph_data_slab

In reply to Abhishek Kumar

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: 27m10s, master: 27m34s), certain commands like git merge-base --is-ancestor are slowed by nearly 40% as discovered by SDEZER Gabor [1].

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

[1]: https://lore.kernel.org/git/[email protected]/
[2]: https://lore.kernel.org/git/[email protected]/

---
 commit-graph.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 commit-graph.h | 10 ++++++++++
 2 files changed, 59 insertions(+)
commit-graph.c +49 -0
index 2ff042fbf4..91120ba3d3 100644
@@ -87,6 +87,55 @@ 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)
+{
+	uint32_t i = commit_graph_data_slab.slab_count, j;
+	uint32_t slab_size = commit_graph_data_slab.slab_size;
+	struct commit_graph_data *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 < commit_graph_data_slab.slab_count; i++) {
+		for (j = 0; j < slab_size; j++) {
+			commit_graph_data_slab[i][j].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;
commit-graph.h +10 -0
index 3ba0da1e5f..cc76757007 100644
@@ -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
Signature · 1 line
2.27.0
#9 lore raw

Re: [PATCH v3 2/4] commit-graph: introduce commit_graph_data_slab

Quoted 24 lines · Abhishek Kumar
commit-graph.c +16 -0
index 2ff042fbf4..91120ba3d3 100644
@@ -87,6 +87,55 @@ 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);

commit-graph.c static int commit_pos_cmp(const void *va, const void *vb) · line 115

Quoted 10 lines
commit-graph.c +10 -0
+
+	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)

commit-graph.c: At top level:
commit-graph.c:115:34: error: ‘commit_graph_data_at’ defined but not used [-Werror=unused-function]
static struct commit_graph_data *commit_graph_data_at(const struct commit *c)

                                    ^

Please make sure that each and every commit of your series can be built with DEVELOPER=1 and passes the test suite.

Quoted 6 lines
commit-graph.c +6 -0
+{
+	uint32_t i = commit_graph_data_slab.slab_count, j;
+	uint32_t slab_size = commit_graph_data_slab.slab_size;
+	struct commit_graph_data *data =
+		commit_graph_data_slab_at(&commit_graph_data_slab, c);
+

commit-graph.c static int commit_pos_cmp(const void *va, const void *vb) · line 131

Quoted 10 lines
commit-graph.c +10 -0
+	/*
+	 * 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 < commit_graph_data_slab.slab_count; i++) {
+		for (j = 0; j < slab_size; j++) {
+			commit_graph_data_slab[i][j].graph_pos =

commit-graph.c: In function ‘commit_graph_data_at’:
commit-graph.c:131:26: error: subscripted value is neither array nor pointer nor vector

      commit_graph_data_slab[i][j].graph_pos =
                            ^

Once the next patch is applied Git can be built again, but then:

  $ ~/src/git/git -C webkit.git commit-graph write
  Finding commits for commit graph among packed objects: 100% (3984415/3984415), done.
  Expanding reachable commits in commit graph: 219420, done.
  Segmentation fault

Looking at it with a debugger:

Program received signal SIGSEGV, Segmentation fault. 0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0) at commit-graph.c:131
131 commit_graph_data_slab.slab[i][j].graph_pos =
(gdb) bt
#0 0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0)

      at commit-graph.c:131
  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)
      at commit-graph.c:1304
  #2  0x000000000050d37d in write_commit_graph (odb=0x9d3d80, pack_indexes=0x0, 
      commits=0x0, flags=COMMIT_GRAPH_WRITE_PROGRESS, 
      split_opts=0x98e730 <split_opts>) at commit-graph.c:2178
  #3  0x000000000042bb7e in graph_write (argc=0, argv=0x7fffffffe2f0)
      at builtin/commit-graph.c:242
  #4  0x000000000042bc8d in cmd_commit_graph (argc=1, argv=0x7fffffffe2f0, 
      prefix=0x0) at builtin/commit-graph.c:278
  #5  0x00000000004061d1 in run_builtin (p=0x97b950 <commands+528>, argc=2, 
      argv=0x7fffffffe2f0) at git.c:448
  #6  0x0000000000406521 in handle_builtin (argc=2, argv=0x7fffffffe2f0)
      at git.c:673
  #7  0x00000000004067c9 in run_argv (argcp=0x7fffffffe18c, argv=0x7fffffffe180)
      at git.c:740
  #8  0x0000000000406c3a in cmd_main (argc=2, argv=0x7fffffffe2f0) at git.c:871
  #9  0x00000000004cfbda in main (argc=5, argv=0x7fffffffe2d8)
      at common-main.c:52
  (gdb) p commit_graph_data_slab
  $1 = {
    slab_size = 65532, 
    stride = 1, 
    slab_count = 4, 
    slab = 0x4f68690
  }
  (gdb) p i
  $2 = 0
  (gdb) p commit_graph_data_slab.slab[i]
  $3 = (struct commit_graph_data *) 0x0
  (gdb) p c->index
  $4 = 213506
  (gdb) up
  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)
      at commit-graph.c:1304
  1304                    uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
  (gdb) p i
  $5 = 0

The way the loop variable 'i' is initialized and is used in the loop header suggests that you assume that all slabs with an index <slab_count are allocated. That's not the case, only those slabs are allocated that contain data associated with a commit that has already been looked at.

Quoted 15 lines
commit-graph.c +7 -0
+				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;
commit-graph.h +0 -0
index 3ba0da1e5f..cc76757007 100644

commit-graph.h void free_commit_graph(struct commit_graph *); · line 143

Quoted 9 lines
commit-graph.h +6 -0
@@ -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;
+};
+
+/* 

This line adds a trailing space which is then removed in next patch. Please don't add it in the first place.

Quoted 8 lines
commit-graph.h +4 -0
+ * 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
Signature · 1 line
2.27.0
#10 lore raw

Re: [PATCH v3 2/4] commit-graph: introduce commit_graph_data_slab

Quoted 120 lines · SZEDER Gábor
Quoted 24 lines · Abhishek Kumar
commit-graph.c +16 -0
index 2ff042fbf4..91120ba3d3 100644
@@ -87,6 +87,55 @@ 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);

commit-graph.c static int commit_pos_cmp(const void *va, const void *vb) · line 115

Quoted 10 lines
commit-graph.c +10 -0
+
+	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)

commit-graph.c: At top level:
commit-graph.c:115:34: error: ‘commit_graph_data_at’ defined but not used [-Werror=unused-function]
static struct commit_graph_data *commit_graph_data_at(const struct commit *c)

                                    ^

Please make sure that each and every commit of your series can be built with DEVELOPER=1 and passes the test suite.

Quoted 6 lines
commit-graph.c +6 -0
+{
+	uint32_t i = commit_graph_data_slab.slab_count, j;
+	uint32_t slab_size = commit_graph_data_slab.slab_size;
+	struct commit_graph_data *data =
+		commit_graph_data_slab_at(&commit_graph_data_slab, c);
+

commit-graph.c static int commit_pos_cmp(const void *va, const void *vb) · line 131

Quoted 10 lines
commit-graph.c +10 -0
+	/*
+	 * 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 < commit_graph_data_slab.slab_count; i++) {
+		for (j = 0; j < slab_size; j++) {
+			commit_graph_data_slab[i][j].graph_pos =

commit-graph.c: In function ‘commit_graph_data_at’:
commit-graph.c:131:26: error: subscripted value is neither array nor pointer nor vector

      commit_graph_data_slab[i][j].graph_pos =
                            ^

Once the next patch is applied Git can be built again, but then:

  $ ~/src/git/git -C webkit.git commit-graph write
  Finding commits for commit graph among packed objects: 100% (3984415/3984415), done.
  Expanding reachable commits in commit graph: 219420, done.
  Segmentation fault

Looking at it with a debugger:

Program received signal SIGSEGV, Segmentation fault. 0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0) at commit-graph.c:131
131 commit_graph_data_slab.slab[i][j].graph_pos =
(gdb) bt
#0 0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0)

      at commit-graph.c:131
  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)
      at commit-graph.c:1304
  #2  0x000000000050d37d in write_commit_graph (odb=0x9d3d80, pack_indexes=0x0, 
      commits=0x0, flags=COMMIT_GRAPH_WRITE_PROGRESS, 
      split_opts=0x98e730 <split_opts>) at commit-graph.c:2178
  #3  0x000000000042bb7e in graph_write (argc=0, argv=0x7fffffffe2f0)
      at builtin/commit-graph.c:242
  #4  0x000000000042bc8d in cmd_commit_graph (argc=1, argv=0x7fffffffe2f0, 
      prefix=0x0) at builtin/commit-graph.c:278
  #5  0x00000000004061d1 in run_builtin (p=0x97b950 <commands+528>, argc=2, 
      argv=0x7fffffffe2f0) at git.c:448
  #6  0x0000000000406521 in handle_builtin (argc=2, argv=0x7fffffffe2f0)
      at git.c:673
  #7  0x00000000004067c9 in run_argv (argcp=0x7fffffffe18c, argv=0x7fffffffe180)
      at git.c:740
  #8  0x0000000000406c3a in cmd_main (argc=2, argv=0x7fffffffe2f0) at git.c:871
  #9  0x00000000004cfbda in main (argc=5, argv=0x7fffffffe2d8)
      at common-main.c:52
  (gdb) p commit_graph_data_slab
  $1 = {
    slab_size = 65532, 
    stride = 1, 
    slab_count = 4, 
    slab = 0x4f68690
  }
  (gdb) p i
  $2 = 0
  (gdb) p commit_graph_data_slab.slab[i]
  $3 = (struct commit_graph_data *) 0x0
  (gdb) p c->index
  $4 = 213506
  (gdb) up
  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)
      at commit-graph.c:1304
  1304                    uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;
  (gdb) p i
  $5 = 0
Quoted 6 lines

The way the loop variable 'i' is initialized and is used in the loop header suggests that you assume that all slabs with an index <slab_count are allocated. That's not the case, only those slabs are allocated that contain data associated with a commit that has already been looked at.

Wait, so assuming there are no slabs before and I call commit_graph_data_slab_at(&commit_graph_data_slab, c) with an commit index that would be in fourth slab, the slab would look like:

commit_graph_data_slab.slab[] = {NULL, NULL, NULL, <address>}

That's new to me! Thanks for sharing this.

Hopefully this is fixed in the v4 series here [1].

[1]: https://lore.kernel.org/git/[email protected]/T/#u

Quoted 29 lines
Quoted 16 lines
commit-graph.c +7 -0
+				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;
commit-graph.h +0 -0
index 3ba0da1e5f..cc76757007 100644

commit-graph.h void free_commit_graph(struct commit_graph *); · line 143

Quoted 9 lines
commit-graph.h +6 -0
@@ -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;
+};
+
+/* 

This line adds a trailing space which is then removed in next patch. Please don't add it in the first place.

Quoted 8 lines
Quoted 8 lines
commit-graph.h +4 -0
+ * 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
Signature · 1 line
2.27.0

Regards
Abhishek

#11 lore raw

PATCH v3 3/4 commit: move members graph_pos, generation to a slab

In reply to Abhishek Kumar

We remove members graph_pos and generation from the struct commit. The default assignments in init_commit_node() are no longer valid, which is fine as the slab helpers return appropriate default values and the assignments are removed.

We will replace existing use of commit->generation and commit->graph_pos by commit_graph_data_slab helpers using `contrib/coccinelle/commit.cocci'.

commit_graph_generation() returns GENERATION_NUMBER_INFINITY if the graph position for commit is COMMIT_NOT_FROM_GRAPH.

While this is true when reading from a commit graph, no graph positions are associated with a commit when writing a commit graph. Therefore, the helper incorrectly returns GENERATION_NUMBER_INFINITY despite having a finite generation number. This is fixed by using generation number directly when writing a commit graph, namely in functions compute_generation_numbers() and write_graph_chunk_data().

---
 alloc.c                         |  2 -
 blame.c                         |  2 +-
 bloom.c                         |  6 +--
 commit-graph.c                  | 68 ++++++++++++++++++---------------
 commit-graph.h                  |  2 +-
 commit-reach.c                  | 50 ++++++++++++------------
 commit.c                        |  6 +--
 contrib/coccinelle/commit.cocci | 18 +++++++++
 revision.c                      | 16 ++++----
 9 files changed, 96 insertions(+), 74 deletions(-)
alloc.c +0 -2
index 29f0e3aa80..fe7d7345e1 100644
@@ -110,8 +110,6 @@ void init_commit_node(struct repository *r, struct commit *c)
 {
 	c->object.type = OBJ_COMMIT;
 	c->index = alloc_commit_index(r);
-	c->graph_pos = COMMIT_NOT_FROM_GRAPH;
-	c->generation = GENERATION_NUMBER_INFINITY;
 }
 
 void *alloc_commit_node(struct repository *r)
blame.c +1 -1
index da7e28800e..82fa16d658 100644
@@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,
 	if (!bd)
 		return 1;
 
-	if (origin->commit->generation == GENERATION_NUMBER_INFINITY)
+	if (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)
 		return 1;
 
 	filter = get_bloom_filter(r, origin->commit, 0);
bloom.c +3 -3
index 6c7611847a..3062aafaba 100644
@@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
 {
 	uint32_t lex_pos, start_index, end_index;
 
-	while (c->graph_pos < g->num_commits_in_base)
+	while (commit_graph_position(c) < g->num_commits_in_base)
 		g = g->base_graph;
 
 	/* The commit graph commit 'c' lives in doesn't carry bloom filters. */
 	if (!g->chunk_bloom_indexes)
 		return 0;
 
-	lex_pos = c->graph_pos - g->num_commits_in_base;
+	lex_pos = commit_graph_position(c) - g->num_commits_in_base;
 
 	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
 
@@ -193,7 +193,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,
 
 	if (!filter->data) {
 		load_commit_graph_info(r, c);
-		if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
+		if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&
 			r->objects->commit_graph->chunk_bloom_indexes) {
 			if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
 				return filter;
commit-graph.c +37 -31

192 lines not on this page · raw message

commit-graph.h +1 -1
index cc76757007..28f89cdf3e 100644
@@ -140,7 +140,7 @@ struct commit_graph_data {
 	uint32_t generation;
 };
 
-/* 
+/*
  * Commits should be parsed before accessing generation, graph positions.
  */
 uint32_t commit_graph_generation(const struct commit *);
commit-reach.c +25 -25

138 lines not on this page · raw message

commit.c +3 -3
index 87686a7055..ad9a76dcc6 100644
@@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r,
 	if (commit->maybe_tree || !commit->object.parsed)
 		return commit->maybe_tree;
 
-	if (commit->graph_pos != COMMIT_NOT_FROM_GRAPH)
+	if (commit_graph_position(commit) != COMMIT_NOT_FROM_GRAPH)
 		return get_commit_tree_in_graph(r, commit);
 
 	return NULL;
@@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void
 	const struct commit *a = a_, *b = b_;
 
 	/* newer commits first */
-	if (a->generation < b->generation)
+	if (commit_graph_generation(a) < commit_graph_generation(b))
 		return 1;
-	else if (a->generation > b->generation)
+	else if (commit_graph_generation(a) > commit_graph_generation(b))
 		return -1;
 
 	/* use date as a heuristic when generations are equal */
contrib/coccinelle/commit.cocci +18 -0
index 778e4704f6..af6dd4c20c 100644
@@ -32,3 +32,21 @@ expression c;
 - c->maybe_tree
 + repo_get_commit_tree(specify_the_right_repo_here, c)
   ...>}
+
+@@
+struct commit *c;
+expression E;
+@@
+(
+- c->generation = E;
++ commit_graph_data_at(c)->generation = E;
+|
+- c->graph_pos = E;
++ commit_graph_data_at(c)->graph_pos = E;
+|
+- c->generation
++ commit_graph_generation(c)
+|
+- c->graph_pos
++ commit_graph_position(c)
+)
revision.c +8 -8
index ebb4d2a0f2..8648d7c43c 100644
@@ -725,7 +725,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,
 	if (!revs->repo->objects->commit_graph)
 		return -1;
 
-	if (commit->generation == GENERATION_NUMBER_INFINITY)
+	if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)
 		return -1;
 
 	filter = get_bloom_filter(revs->repo, commit, 0);
@@ -3320,7 +3320,7 @@ static void explore_to_depth(struct rev_info *revs,
 	struct topo_walk_info *info = revs->topo_walk_info;
 	struct commit *c;
 	while ((c = prio_queue_peek(&info->explore_queue)) &&
-	       c->generation >= gen_cutoff)
+	       commit_graph_generation(c) >= gen_cutoff)
 		explore_walk_step(revs);
 }
 
@@ -3336,7 +3336,7 @@ static void indegree_walk_step(struct rev_info *revs)
 	if (parse_commit_gently(c, 1) < 0)
 		return;
 
-	explore_to_depth(revs, c->generation);
+	explore_to_depth(revs, commit_graph_generation(c));
 
 	for (p = c->parents; p; p = p->next) {
 		struct commit *parent = p->item;
@@ -3360,7 +3360,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs,
 	struct topo_walk_info *info = revs->topo_walk_info;
 	struct commit *c;
 	while ((c = prio_queue_peek(&info->indegree_queue)) &&
-	       c->generation >= gen_cutoff)
+	       commit_graph_generation(c) >= gen_cutoff)
 		indegree_walk_step(revs);
 }
 
@@ -3420,8 +3420,8 @@ static void init_topo_walk(struct rev_info *revs)
 		test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
 		test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
 
-		if (c->generation < info->min_generation)
-			info->min_generation = c->generation;
+		if (commit_graph_generation(c) < info->min_generation)
+			info->min_generation = commit_graph_generation(c);
 
 		*(indegree_slab_at(&info->indegree, c)) = 1;
 
@@ -3479,8 +3479,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 		if (parse_commit_gently(parent, 1) < 0)
 			continue;
 
-		if (parent->generation < info->min_generation) {
-			info->min_generation = parent->generation;
+		if (commit_graph_generation(parent) < info->min_generation) {
+			info->min_generation = commit_graph_generation(parent);
 			compute_indegrees_to_depth(revs, info->min_generation);
 		}
 
Signature · 1 line
2.27.0
#12 lore raw

PATCH v3 4/4 commit-graph: minimize commit_graph_data_slab access

In reply to Abhishek Kumar

In an earlier patch, multiple struct acccesses to graph_pos and generation were auto-converted to multiple method calls.

Since the values are fixed and commit-slab access costly, we would be better off with storing the values as a local variable and reuse it.

---
 bloom.c        |  5 +++--
 commit-graph.c | 40 ++++++++++++++++++++++------------
 commit-reach.c | 59 ++++++++++++++++++++++++++++++++------------------
 commit.c       |  6 +++--
 revision.c     | 12 ++++++----
 5 files changed, 79 insertions(+), 43 deletions(-)
bloom.c +3 -2
index 3062aafaba..6a7f2f2bdc 100644
@@ -33,15 +33,16 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,
 					struct commit *c)
 {
 	uint32_t lex_pos, start_index, end_index;
+	uint32_t graph_pos = commit_graph_position(c);
 
-	while (commit_graph_position(c) < g->num_commits_in_base)
+	while (graph_pos < g->num_commits_in_base)
 		g = g->base_graph;
 
 	/* The commit graph commit 'c' lives in doesn't carry bloom filters. */
 	if (!g->chunk_bloom_indexes)
 		return 0;
 
-	lex_pos = commit_graph_position(c) - g->num_commits_in_base;
+	lex_pos = graph_pos - g->num_commits_in_base;
 
 	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
 
commit-graph.c +26 -14
index cb4365e9b6..5d86d20459 100644
@@ -141,10 +141,12 @@ static int commit_gen_cmp(const void *va, const void *vb)
 	const struct commit *a = *(const struct commit **)va;
 	const struct commit *b = *(const struct commit **)vb;
 
+	uint32_t generation_a = commit_graph_generation(a);
+	uint32_t generation_b = commit_graph_generation(b);
 	/* lower generation commits first */
-	if (commit_graph_generation(a) < commit_graph_generation(b))
+	if (generation_a < generation_b)
 		return -1;
-	else if (commit_graph_generation(a) > commit_graph_generation(b))
+	else if (generation_a > generation_b)
 		return 1;
 
 	/* use date as a heuristic when generations are equal */
@@ -726,6 +728,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,
 static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)
 {
 	const unsigned char *commit_data;
+	struct commit_graph_data *graph_data;
 	uint32_t lex_index;
 
 	while (pos < g->num_commits_in_base)
@@ -733,8 +736,10 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,
 
 	lex_index = pos - g->num_commits_in_base;
 	commit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;
-	commit_graph_data_at(item)->graph_pos = pos;
-	commit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
+
+	graph_data = commit_graph_data_at(item);
+	graph_data->graph_pos = pos;
+	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 }
 
 static inline void set_commit_tree(struct commit *c, struct tree *t)
@@ -750,6 +755,7 @@ static int fill_commit_in_graph(struct repository *r,
 	uint32_t *parent_data_ptr;
 	uint64_t date_low, date_high;
 	struct commit_list **pptr;
+	struct commit_graph_data *graph_data;
 	const unsigned char *commit_data;
 	uint32_t lex_index;
 
@@ -763,7 +769,8 @@ static int fill_commit_in_graph(struct repository *r,
 	 * Store the "full" position, but then use the
 	 * "local" position for the rest of the calculation.
 	 */
-	commit_graph_data_at(item)->graph_pos = pos;
+	graph_data = commit_graph_data_at(item);
+	graph_data->graph_pos = pos;
 	lex_index = pos - g->num_commits_in_base;
 
 	commit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;
@@ -776,7 +783,7 @@ static int fill_commit_in_graph(struct repository *r,
 	date_low = get_be32(commit_data + g->hash_len + 12);
 	item->date = (timestamp_t)((date_high << 32) | date_low);
 
-	commit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
+	graph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;
 
 	pptr = &item->parents;
 
@@ -808,8 +815,9 @@ static int fill_commit_in_graph(struct repository *r,
 
 static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)
 {
-	if (commit_graph_position(item) != COMMIT_NOT_FROM_GRAPH) {
-		*pos = commit_graph_position(item);
+	uint32_t graph_pos = commit_graph_position(item);
+	if (graph_pos != COMMIT_NOT_FROM_GRAPH) {
+		*pos = graph_pos;
 		return 1;
 	} else {
 		struct commit_graph *cur_g = g;
@@ -864,12 +872,13 @@ static struct tree *load_tree_for_commit(struct repository *r,
 {
 	struct object_id oid;
 	const unsigned char *commit_data;
+	uint32_t graph_pos = commit_graph_position(c);
 
-	while (commit_graph_position(c) < g->num_commits_in_base)
+	while (graph_pos < g->num_commits_in_base)
 		g = g->base_graph;
 
 	commit_data = g->chunk_commit_data +
-			GRAPH_DATA_WIDTH * (commit_graph_position(c) - g->num_commits_in_base);
+			GRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base);
 
 	hashcpy(oid.hash, commit_data);
 	set_commit_tree(c, lookup_tree(r, &oid));
@@ -2296,6 +2305,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 		struct commit *graph_commit, *odb_commit;
 		struct commit_list *graph_parents, *odb_parents;
 		uint32_t max_generation = 0;
+		uint32_t generation;
 
 		display_progress(progress, i + 1);
 		hashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);
@@ -2334,8 +2344,9 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 					     oid_to_hex(&graph_parents->item->object.oid),
 					     oid_to_hex(&odb_parents->item->object.oid));
 
-			if (commit_graph_generation(graph_parents->item) > max_generation)
-				max_generation = commit_graph_generation(graph_parents->item);
+			generation = commit_graph_generation(graph_parents->item);
+			if (generation > max_generation)
+				max_generation = generation;
 
 			graph_parents = graph_parents->next;
 			odb_parents = odb_parents->next;
@@ -2365,10 +2376,11 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)
 		if (max_generation == GENERATION_NUMBER_MAX)
 			max_generation--;
 
-		if (commit_graph_generation(graph_commit) != max_generation + 1)
+		generation = commit_graph_generation(graph_commit);
+		if (generation != max_generation + 1)
 			graph_report(_("commit-graph generation for commit %s is %u != %u"),
 				     oid_to_hex(&cur_oid),
-				     commit_graph_generation(graph_commit),
+				     generation,
 				     max_generation + 1);
 
 		if (graph_commit->date != odb_commit->date)
commit-reach.c +38 -21

140 lines not on this page · raw message

commit.c +4 -2
index ad9a76dcc6..f85ade78ed 100644
@@ -729,11 +729,13 @@ int compare_commits_by_author_date(const void *a_, const void *b_,
 int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
 {
 	const struct commit *a = a_, *b = b_;
+	const uint32_t generation_a = commit_graph_generation(a),
+		       generation_b = commit_graph_generation(b);
 
 	/* newer commits first */
-	if (commit_graph_generation(a) < commit_graph_generation(b))
+	if (generation_a < generation_b)
 		return 1;
-	else if (commit_graph_generation(a) > commit_graph_generation(b))
+	else if (generation_a > generation_b)
 		return -1;
 
 	/* use date as a heuristic when generations are equal */
revision.c +8 -4
index 8648d7c43c..32be93f404 100644
@@ -3413,6 +3413,7 @@ static void init_topo_walk(struct rev_info *revs)
 	info->min_generation = GENERATION_NUMBER_INFINITY;
 	for (list = revs->commits; list; list = list->next) {
 		struct commit *c = list->item;
+		uint32_t generation;
 
 		if (parse_commit_gently(c, 1))
 			continue;
@@ -3420,8 +3421,9 @@ static void init_topo_walk(struct rev_info *revs)
 		test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);
 		test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);
 
-		if (commit_graph_generation(c) < info->min_generation)
-			info->min_generation = commit_graph_generation(c);
+		generation = commit_graph_generation(c);
+		if (generation < info->min_generation)
+			info->min_generation = generation;
 
 		*(indegree_slab_at(&info->indegree, c)) = 1;
 
@@ -3472,6 +3474,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 	for (p = commit->parents; p; p = p->next) {
 		struct commit *parent = p->item;
 		int *pi;
+		uint32_t generation;
 
 		if (parent->object.flags & UNINTERESTING)
 			continue;
@@ -3479,8 +3482,9 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)
 		if (parse_commit_gently(parent, 1) < 0)
 			continue;
 
-		if (commit_graph_generation(parent) < info->min_generation) {
-			info->min_generation = commit_graph_generation(parent);
+		generation = commit_graph_generation(parent);
+		if (generation < info->min_generation) {
+			info->min_generation = generation;
 			compute_indegrees_to_depth(revs, info->min_generation);
 		}
 
Signature · 1 line
2.27.0
#13 lore raw
In reply to Abhishek Kumar
Quoted 7 lines · Abhishek Kumar

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.

I think s/would have been/would be/1, but I am not native English speaker.

Quoted 5 lines

While the overall test suite runs slightly faster than master (series: 27m10s, master: 27ms34s, faster by 2.35%), certain commands like git merge-base --is-ancestory are slowed by nearly 40% as discovered by SDEZER Gabor [1].

First, the name is SZEDER Gábor.

Second, it would be nice to have some specific examples, like for example the results of running git merge-base --is-ancestory in specific repository, and from specific starting point.

It might be good idea to also show performance change for a command that handles large amount of commits but does not use the commit-graph, like for example git gc.

Quoted 4 lines

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 on that in a later series.

Would it be possible to show profiling results?

Quoted 9 lines

I did not mention maximum RSS in the commit messages as they were nearly identical (series: 68104kb, master: 68040kb, fewer by <0.1%). This leads me to conclude that either the test using maximum memory involves commit graph or did not involve the struct commit at all. The move to commit-slab reduces memory footprint for the cases where struct commit is used but members generation and graph position are not. Average RSS would have been a good and more representative measure, but unfortunately time(1) could not measure it on my system.

What operating system do you use?

Quoted 4 lines

With this, I feel the patch will require minor fixes, if any. I am moving ahead with working the next step of "Implement Generation Number v2" that is proper handling of commit-graph format change.

All right. It should be not a problem to rebase series on top of different implementation of [inline-able] helper function if it turns out that the move to slab serious affects negatively performance.

Quoted 4 lines

Based on the discussions, I feel we should compute both generation number v1 and the date offset value with storing date offsets in a new chunk as the cost is mostly from walking the commits.

Should we store offsets and corrected commit date on the slab, or just the corrected date (with offset applied)? We should be using corrected commit date only; offset can be recomputed if needed, e.g. when writing the commit-graph.

Quoted 18 lines

Abhishek Kumar (4):
alloc: introduce parsed_commits_count
commit-graph: introduce commit_graph_data_slab
commit: move members graph_pos, generation to a slab
commit-graph: minimize commit_graph_data_slab access

  alloc.c                         |   6 +-
  blame.c                         |   2 +-
  bloom.c                         |   7 +-
  commit-graph.c                  | 122 ++++++++++++++++++++++++--------
  commit-graph.h                  |  10 +++
  commit-reach.c                  |  69 +++++++++++-------
  commit.c                        |   8 ++-
  contrib/coccinelle/commit.cocci |  18 +++++
  revision.c                      |  20 +++---
  9 files changed, 188 insertions(+), 74 deletions(-)