| Message ID | 20200604072759.19142-2-abhishekkumar8222@gmail.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | Move generation, graph_pos to a slab | expand |
On 6/4/2020 3:27 AM, Abhishek Kumar wrote: > The struct member generation refers to "generation number" (or more > broadly, a reachablity index value) used by commit-graph to reduce time > taken to walk commits. However, generation is not useful in other > contexts and bloats the struct. > > Let's move it to a commit-slab and shrink the struct by four bytes. > > Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com> > --- > commit-graph.c | 27 +++++++++++++++++++++++++++ > commit-graph.h | 5 +++++ > commit.h | 3 --- > 3 files changed, 32 insertions(+), 3 deletions(-) > > diff --git a/commit-graph.c b/commit-graph.c > index e3420ddcbf..63f419048d 100644 > --- a/commit-graph.c > +++ b/commit-graph.c > @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb) > commit_pos_at(&commit_pos, b); > } > > +define_commit_slab(generation_slab, uint32_t); > +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); > + > +uint32_t generation(const struct commit *c) > +{ > + uint32_t *gen = generation_slab_peek(&generation_slab, c); > + > + return gen ? *gen : GENERATION_NUMBER_INFINITY; > +} This is good: if we don't have the value, then use INFINITY. In the header file, perhaps include a warning comment that a caller _must_ first parse the commit or else we have no guarantee that the generation slab is populated. This matches the current expectations before accessing the generation member. > +static void set_generation(const struct commit *c, const uint32_t generation) > +{ > + unsigned int i = generation_slab.slab_count; > + uint32_t *gen = generation_slab_at(&generation_slab, c); > + > + /* > + * commit-slab initializes with zero, overwrite this with > + * GENERATION_NUMBER_INFINITY > + */ > + for (; i < generation_slab.slab_count; ++i) { > + memset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY, > + generation_slab.slab_size * sizeof(uint32_t)); > + } Here is an example where combining the graph_pos and generation slabs into one would be helpful. The only reason the generation would be INFINITY is if graph_pos is COMMIT_NOT_FROM_GRAPH. If the two values are side-by-side, we could just check graph_pos first and return INFINITY instead of paying this initialization cost as the slab grows. I would also like to avoid initializing the slab if there is no commit-graph present. I wonder if we can populate the slab while parsing the commit-graph and check here if the slab is NULL before doing any other logic? (I'm not sure if this is possible, but it would be nice.) > diff --git a/commit-graph.h b/commit-graph.h > index 4212766a4f..653bd041ad 100644 > --- a/commit-graph.h > +++ b/commit-graph.h > @@ -8,6 +8,10 @@ > #include "object-store.h" > #include "oidset.h" > > +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > +#define GENERATION_NUMBER_MAX 0x3FFFFFFF > +#define GENERATION_NUMBER_ZERO 0 > + > #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH" > #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD" > #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS" > @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *); > */ > void disable_commit_graph(struct repository *r); > > +uint32_t generation(const struct commit *c); > #endif > diff --git a/commit.h b/commit.h > index 1b2dea5d85..cc610400d5 100644 > --- a/commit.h > +++ b/commit.h > @@ -11,9 +11,6 @@ > #include "commit-slab.h" > > #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF > -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > -#define GENERATION_NUMBER_MAX 0x3FFFFFFF > -#define GENERATION_NUMBER_ZERO 0 I appreciate that you are able to relocate these constants to a more appropriate location. Thanks, -Stolee
Abhishek Kumar <abhishekkumar8222@gmail.com> writes: > The struct member generation refers to "generation number" (or more > broadly, a reachablity index value) used by commit-graph to reduce time > taken to walk commits. However, generation is not useful in other > contexts and bloats the struct. > > Let's move it to a commit-slab and shrink the struct by four bytes. > > Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com> > --- > commit-graph.c | 27 +++++++++++++++++++++++++++ > commit-graph.h | 5 +++++ > commit.h | 3 --- > 3 files changed, 32 insertions(+), 3 deletions(-) > > diff --git a/commit-graph.c b/commit-graph.c > index e3420ddcbf..63f419048d 100644 > --- a/commit-graph.c > +++ b/commit-graph.c > @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb) > commit_pos_at(&commit_pos, b); > } > > +define_commit_slab(generation_slab, uint32_t); > +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); > + > +uint32_t generation(const struct commit *c) > +{ > + uint32_t *gen = generation_slab_peek(&generation_slab, c); > + > + return gen ? *gen : GENERATION_NUMBER_INFINITY; > +} > + > +static void set_generation(const struct commit *c, const uint32_t generation) > +{ > + unsigned int i = generation_slab.slab_count; > + uint32_t *gen = generation_slab_at(&generation_slab, c); > + > + /* > + * commit-slab initializes with zero, overwrite this with > + * GENERATION_NUMBER_INFINITY > + */ > + for (; i < generation_slab.slab_count; ++i) { Style: favor post-increment over pre-increment when there is no difference, especially when updating the loop control in for() loop. > + memset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY, > + generation_slab.slab_size * sizeof(uint32_t)); > + } > + > + *gen = generation; > +} > + > 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 4212766a4f..653bd041ad 100644 > --- a/commit-graph.h > +++ b/commit-graph.h > @@ -8,6 +8,10 @@ > #include "object-store.h" > #include "oidset.h" > > +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > +#define GENERATION_NUMBER_MAX 0x3FFFFFFF > +#define GENERATION_NUMBER_ZERO 0 > + Makes sense to move it from commit.h, I guess. > #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH" > #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD" > #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS" > @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *); > */ > void disable_commit_graph(struct repository *r); > > +uint32_t generation(const struct commit *c); > #endif > diff --git a/commit.h b/commit.h > index 1b2dea5d85..cc610400d5 100644 > --- a/commit.h > +++ b/commit.h > @@ -11,9 +11,6 @@ > #include "commit-slab.h" > > #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF > -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > -#define GENERATION_NUMBER_MAX 0x3FFFFFFF > -#define GENERATION_NUMBER_ZERO 0 > > struct commit_list { > struct commit *item;
Abhishek Kumar <abhishekkumar8222@gmail.com> writes: > The struct member generation refers to "generation number" (or more Again, a minor thing: 'generation'. > broadly, a reachablity index value) used by commit-graph to reduce time > taken to walk commits. However, generation is not useful in other > contexts and bloats the struct. > > Let's move it to a commit-slab and shrink the struct by four bytes. It looks like the description is from earlier version of the commit, before it was split -- because this commit does not remove 'generation' member from the 'struct commit', actually. This commit is about creating helper functions. > > Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com> > --- > commit-graph.c | 27 +++++++++++++++++++++++++++ > commit-graph.h | 5 +++++ > commit.h | 3 --- > 3 files changed, 32 insertions(+), 3 deletions(-) > > diff --git a/commit-graph.c b/commit-graph.c > index e3420ddcbf..63f419048d 100644 > --- a/commit-graph.c > +++ b/commit-graph.c > @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb) > commit_pos_at(&commit_pos, b); > } > > +define_commit_slab(generation_slab, uint32_t); > +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); All right, we need this for the following helper functions to work. We might want to encapsulate all commit-graph data together, in a single struct (e.g. as 'struct commit_graph_data' instead of uint32_t here). On the other hand other data is stored on slab often as separate scalar data (contains_cache, commit_seen, indegree_slab, author_date_slab, commit_base, commit_pos), but not always; sometimes it is a struct (bloom_filter_slab, buffer_slab, commit_rev_name), sometimes it is an array (commit_depth, ref_bitmap, commit_weight), and sometimes it is an array/list of structs or pointer to struct (commit_names, commit_name_slab, saved_parents, blame_suspects, commit_todo_item). > + > +uint32_t generation(const struct commit *c) > +{ > + uint32_t *gen = generation_slab_peek(&generation_slab, c); > + > + return gen ? *gen : GENERATION_NUMBER_INFINITY; > +} All right, this is a synthetic getter using the fact that commits outside the commit-graph should get GENERATION_NUMBER_INFINITY (because [effective] commit-graph is closed under reachability, is full DAG). Should we have something like that for 'graph_pos' and COMMIT_NOT_FROM_GRAPH? > + > +static void set_generation(const struct commit *c, const uint32_t generation) > +{ > + unsigned int i = generation_slab.slab_count; > + uint32_t *gen = generation_slab_at(&generation_slab, c); > + > + /* > + * commit-slab initializes with zero, overwrite this with > + * GENERATION_NUMBER_INFINITY > + */ > + for (; i < generation_slab.slab_count; ++i) { > + memset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY, > + generation_slab.slab_size * sizeof(uint32_t)); > + } > + > + *gen = generation; > +} All right. I wonder if putting 'generation' and 'graph_pos' on the slab together, gathered in 'struct commit_graph_data' would make this helper more complex... > + > 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 4212766a4f..653bd041ad 100644 > --- a/commit-graph.h > +++ b/commit-graph.h > @@ -8,6 +8,10 @@ > #include "object-store.h" > #include "oidset.h" > > +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > +#define GENERATION_NUMBER_MAX 0x3FFFFFFF > +#define GENERATION_NUMBER_ZERO 0 > + > #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH" > #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD" > #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS" > @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *); > */ > void disable_commit_graph(struct repository *r); > > +uint32_t generation(const struct commit *c); > #endif > diff --git a/commit.h b/commit.h > index 1b2dea5d85..cc610400d5 100644 > --- a/commit.h > +++ b/commit.h > @@ -11,9 +11,6 @@ > #include "commit-slab.h" > > #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF > -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF > -#define GENERATION_NUMBER_MAX 0x3FFFFFFF > -#define GENERATION_NUMBER_ZERO 0 > > struct commit_list { > struct commit *item; Why this change? Best,
diff --git a/commit-graph.c b/commit-graph.c index e3420ddcbf..63f419048d 100644 --- a/commit-graph.c +++ b/commit-graph.c @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb) commit_pos_at(&commit_pos, b); } +define_commit_slab(generation_slab, uint32_t); +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab); + +uint32_t generation(const struct commit *c) +{ + uint32_t *gen = generation_slab_peek(&generation_slab, c); + + return gen ? *gen : GENERATION_NUMBER_INFINITY; +} + +static void set_generation(const struct commit *c, const uint32_t generation) +{ + unsigned int i = generation_slab.slab_count; + uint32_t *gen = generation_slab_at(&generation_slab, c); + + /* + * commit-slab initializes with zero, overwrite this with + * GENERATION_NUMBER_INFINITY + */ + for (; i < generation_slab.slab_count; ++i) { + memset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY, + generation_slab.slab_size * sizeof(uint32_t)); + } + + *gen = generation; +} + 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 4212766a4f..653bd041ad 100644 --- a/commit-graph.h +++ b/commit-graph.h @@ -8,6 +8,10 @@ #include "object-store.h" #include "oidset.h" +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF +#define GENERATION_NUMBER_MAX 0x3FFFFFFF +#define GENERATION_NUMBER_ZERO 0 + #define GIT_TEST_COMMIT_GRAPH "GIT_TEST_COMMIT_GRAPH" #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD "GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD" #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS "GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS" @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *); */ void disable_commit_graph(struct repository *r); +uint32_t generation(const struct commit *c); #endif diff --git a/commit.h b/commit.h index 1b2dea5d85..cc610400d5 100644 --- a/commit.h +++ b/commit.h @@ -11,9 +11,6 @@ #include "commit-slab.h" #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF -#define GENERATION_NUMBER_MAX 0x3FFFFFFF -#define GENERATION_NUMBER_ZERO 0 struct commit_list { struct commit *item;
The struct member generation refers to "generation number" (or more broadly, a reachablity index value) used by commit-graph to reduce time taken to walk commits. However, generation is not useful in other contexts and bloats the struct. Let's move it to a commit-slab and shrink the struct by four bytes. Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com> --- commit-graph.c | 27 +++++++++++++++++++++++++++ commit-graph.h | 5 +++++ commit.h | 3 --- 3 files changed, 32 insertions(+), 3 deletions(-)