[GSoC,v3,0/4] Move generation, graph_pos to a slab

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.

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(-)

Comments

Jakub Narębski June 12, 2020, 9:26 p.m. UTC | #1

On 12.06.2020, Abhishek Kumar wrote:

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

> 
> 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`.

> 
> 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?

> 
> 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?

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

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

> 
> 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(-)
>