diff mbox series

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

Message ID 20200612184014.1226972-3-abhishekkumar8222@gmail.com (mailing list archive)
State New, archived
Headers show
Series Move generation, graph_pos to a slab | expand

Commit Message

Abhishek Kumar June 12, 2020, 6:40 p.m. UTC 
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/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>
---
 commit-graph.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 commit-graph.h | 10 ++++++++++
 2 files changed, 59 insertions(+)

Comments

SZEDER Gábor June 13, 2020, 6:53 a.m. UTC | #1 
On Sat, Jun 13, 2020 at 12:10:12AM +0530, Abhishek Kumar wrote:
> diff --git a/commit-graph.c b/commit-graph.c
> index 2ff042fbf4..91120ba3d3 100644
> --- a/commit-graph.c
> +++ b/commit-graph.c
> @@ -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)

  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.

> +{
> +	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-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.


> +				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;
> diff --git a/commit-graph.h b/commit-graph.h
> index 3ba0da1e5f..cc76757007 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;
> +};
> +
> +/* 

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

> + * 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
>
Abhishek Kumar June 17, 2020, 9:18 a.m. UTC | #2 
On Sat, Jun 13, 2020 at 08:53:39AM +0200, SZEDER Gábor wrote:
> On Sat, Jun 13, 2020 at 12:10:12AM +0530, Abhishek Kumar wrote:
> > diff --git a/commit-graph.c b/commit-graph.c
> > index 2ff042fbf4..91120ba3d3 100644
> > --- a/commit-graph.c
> > +++ b/commit-graph.c
> > @@ -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)
> 
>   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.
> 
> > +{
> > +	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-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.
> 

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/20200617091411.14650-1-abhishekkumar8222@gmail.com/T/#u

> 
> > +				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;
> > diff --git a/commit-graph.h b/commit-graph.h
> > index 3ba0da1e5f..cc76757007 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;
> > +};
> > +
> > +/* 
> 
> This line adds a trailing space which is then removed in next patch.
> Please don't add it in the first place.
> 
> > + * 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
> > 

Regards
Abhishek
diff mbox series

Patch

diff --git a/commit-graph.c b/commit-graph.c
index 2ff042fbf4..91120ba3d3 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -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;
diff --git a/commit-graph.h b/commit-graph.h
index 3ba0da1e5f..cc76757007 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