{"thread":{"id":"53611","subject":"[GSoC Patch 0/3] Move generation, graph_pos to a slab","startedAt":"2020-06-04T07:29:59Z","lastAt":"2020-06-19T17:44:40Z","messageCount":39,"participants":["Abhishek Kumar","Derrick Stolee","Junio C Hamano","Jakub Narębski","SZEDER Gábor","Taylor Blau"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"399100","messageId":"20200604072759.19142-1-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":null,"subject":"[GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-04T07:27:56Z","receivedAt":"2020-06-04T07:29:59Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct commit is used in many contexts. However, members generation\nand graph_pos are only used for commit-graph related operations and\notherwise waste memory.\n\nThis wastage would have been more pronounced as transistion to\ngeneration number v2, which uses 64-bit generation number instead of\ncurrent 32-bits.\n\nThe third patch (\"commit: convert commit->graph_pos to a slab\",\n2020-06-04) is currently failing diff-submodule related tests (t4041,\nt4059 and t4060) for gcc [1]. I am going to send a second version soon,\nfixing that.\n\n[1]: https://travis-ci.com/github/abhishekkumar2718/git/jobs/343441189\n\nAbhishek Kumar (3):\n commit: introduce helpers for generation slab\n commit: convert commit->generation to a slab\n commit: convert commit->graph_pos to a slab\n\n alloc.c | 2 -\n blame.c | 2 +-\n bloom.c | 6 +-\n commit-graph.c | 116 +++++++++++++++++++++-------\n commit-graph.h | 8 ++\n commit-reach.c | 50 ++++++------\n commit.c | 6 +-\n commit.h | 6 --\n contrib/coccinelle/generation.cocci | 12 +++\n contrib/coccinelle/graph_pos.cocci | 12 +++\n revision.c | 16 ++--\n 11 files changed, 158 insertions(+), 78 deletions(-)\n create mode 100644 contrib/coccinelle/generation.cocci\n create mode 100644 contrib/coccinelle/graph_pos.cocci\n\n-- \n2.27.0\n\n"},{"id":"399101","messageId":"20200604072759.19142-2-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"[GSoC Patch 1/3] commit: introduce helpers for generation slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-04T07:27:57Z","receivedAt":"2020-06-04T07:30:01Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct member generation refers to \"generation number\" (or more\nbroadly, a reachablity index value) used by commit-graph to reduce time\ntaken to walk commits. However, generation is not useful in other\ncontexts and bloats the struct.\n\nLet's move it to a commit-slab and shrink the struct by four bytes.\n\nSigned-off-by: Abhishek Kumar \n---\n commit-graph.c | 27 +++++++++++++++++++++++++++\n commit-graph.h | 5 +++++\n commit.h | 3 ---\n 3 files changed, 32 insertions(+), 3 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex e3420ddcbf..63f419048d 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb)\n \t commit_pos_at(&commit_pos, b);\n }\n \n+define_commit_slab(generation_slab, uint32_t);\n+static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n+\n+uint32_t generation(const struct commit *c)\n+{\n+\tuint32_t *gen = generation_slab_peek(&generation_slab, c);\n+\n+\treturn gen ? *gen : GENERATION_NUMBER_INFINITY;\n+}\n+\n+static void set_generation(const struct commit *c, const uint32_t generation)\n+{\n+\tunsigned int i = generation_slab.slab_count;\n+\tuint32_t *gen = generation_slab_at(&generation_slab, c);\n+\n+\t/*\n+\t * commit-slab initializes with zero, overwrite this with\n+\t * GENERATION_NUMBER_INFINITY\n+\t */\n+\tfor (; i < generation_slab.slab_count; ++i) {\n+\t\tmemset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY,\n+\t\t generation_slab.slab_size * sizeof(uint32_t));\n+\t}\n+\n+\t*gen = generation;\n+}\n+\n static int commit_gen_cmp(const void *va, const void *vb)\n {\n \tconst struct commit *a = *(const struct commit **)va;\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 4212766a4f..653bd041ad 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -8,6 +8,10 @@\n #include \"object-store.h\"\n #include \"oidset.h\"\n \n+#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n+#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n+#define GENERATION_NUMBER_ZERO 0\n+\n #define GIT_TEST_COMMIT_GRAPH \"GIT_TEST_COMMIT_GRAPH\"\n #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD \"GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD\"\n #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS \"GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\"\n@@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *);\n */\n void disable_commit_graph(struct repository *r);\n \n+uint32_t generation(const struct commit *c);\n #endif\ndiff --git a/commit.h b/commit.h\nindex 1b2dea5d85..cc610400d5 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -11,9 +11,6 @@\n #include \"commit-slab.h\"\n \n #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n-#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n-#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n-#define GENERATION_NUMBER_ZERO 0\n \n struct commit_list {\n \tstruct commit *item;\n-- \n2.27.0\n\n"},{"id":"399102","messageId":"20200604072759.19142-4-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"[GSoC Patch 3/3] commit: convert commit->graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-04T07:27:59Z","receivedAt":"2020-06-04T07:30:08Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The member graph_pos refers to the integer position used to identify a\ncommit in commit-graph files. However, graph_pos is not useful in other\ncontexts and bloats the struct.\n\nLet's move it to a commit-slab and shrink the struct by four bytes.\n\nExisting references to graph_pos are replaced using\n'contrib/coccinelle/graph_pos.cocci'.\n\nSigned-off-by: Abhishek Kumar \n---\n alloc.c | 1 -\n bloom.c | 6 ++--\n commit-graph.c | 50 +++++++++++++++++++++++-------\n commit-graph.h | 3 ++\n commit.c | 2 +-\n commit.h | 2 --\n contrib/coccinelle/graph_pos.cocci | 12 +++++++\n 7 files changed, 58 insertions(+), 18 deletions(-)\n create mode 100644 contrib/coccinelle/graph_pos.cocci\n\ndiff --git a/alloc.c b/alloc.c\nindex cbed187094..f37fb3b8b6 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -108,7 +108,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n {\n \tc->object.type = OBJ_COMMIT;\n \tc->index = alloc_commit_index(r);\n-\tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n }\n \n void *alloc_commit_node(struct repository *r)\ndiff --git a/bloom.c b/bloom.c\nindex 9b86aa3f59..5bee5bb0c1 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n {\n \tuint32_t lex_pos, start_index, end_index;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (graph_pos(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n \tif (!g->chunk_bloom_indexes)\n \t\treturn 0;\n \n-\tlex_pos = c->graph_pos - g->num_commits_in_base;\n+\tlex_pos = graph_pos(c) - g->num_commits_in_base;\n \n \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n \n@@ -188,7 +188,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \n \tif (!filter->data) {\n \t\tload_commit_graph_info(r, c);\n-\t\tif (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&\n+\t\tif (graph_pos(c) != COMMIT_NOT_FROM_GRAPH &&\n \t\t\tr->objects->commit_graph->chunk_bloom_indexes) {\n \t\t\tif (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))\n \t\t\t\treturn filter;\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 9ce7d4acb1..7ff460b442 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -87,6 +87,34 @@ static int commit_pos_cmp(const void *va, const void *vb)\n \t commit_pos_at(&commit_pos, b);\n }\n \n+define_commit_slab(graph_pos_slab, uint32_t);\n+static struct graph_pos_slab graph_pos_slab = COMMIT_SLAB_INIT(1, graph_pos_slab);\n+\n+uint32_t graph_pos(const struct commit *c)\n+{\n+\tuint32_t *pos = graph_pos_slab_peek(&graph_pos_slab, c);\n+\n+\treturn pos ? *pos : COMMIT_NOT_FROM_GRAPH;\n+}\n+\n+static void set_graph_pos(const struct commit *c, const uint32_t position)\n+{\n+\tunsigned int i = graph_pos_slab.slab_count;\n+\tuint32_t *pos = graph_pos_slab_at(&graph_pos_slab, c);\n+\n+\t/*\n+\t * commit-slab initializes with zero, overwrite this with\n+\t * COMMIT_NOT_FROM_GRAPH\n+\t */\n+\tfor (; i < graph_pos_slab.slab_count; ++i)\n+\t{\n+\t\tmemset(graph_pos_slab.slab[i], COMMIT_NOT_FROM_GRAPH,\n+\t\t graph_pos_slab.slab_size * sizeof(uint32_t));\n+\t}\n+\n+\t*pos = position;\n+}\n+\n define_commit_slab(generation_slab, uint32_t);\n static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n \n@@ -697,7 +725,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n \tc = lookup_commit(r, &oid);\n \tif (!c)\n \t\tdie(_(\"could not find commit %s\"), oid_to_hex(&oid));\n-\tc->graph_pos = pos;\n+\tset_graph_pos(c, pos);\n \treturn &commit_list_insert(c, pptr)->next;\n }\n \n@@ -711,7 +739,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n-\titem->graph_pos = pos;\n+\tset_graph_pos(item, pos);\n \tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n }\n \n@@ -741,7 +769,7 @@ static int fill_commit_in_graph(struct repository *r,\n \t * Store the \"full\" position, but then use the\n \t * \"local\" position for the rest of the calculation.\n \t */\n-\titem->graph_pos = pos;\n+\tset_graph_pos(item, pos);\n \tlex_index = pos - g->num_commits_in_base;\n \n \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n@@ -786,8 +814,8 @@ static int fill_commit_in_graph(struct repository *r,\n \n static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n {\n-\tif (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {\n-\t\t*pos = item->graph_pos;\n+\tif (graph_pos(item) != COMMIT_NOT_FROM_GRAPH) {\n+\t\t*pos = graph_pos(item);\n \t\treturn 1;\n \t} else {\n \t\tstruct commit_graph *cur_g = g;\n@@ -843,11 +871,11 @@ static struct tree *load_tree_for_commit(struct repository *r,\n \tstruct object_id oid;\n \tconst unsigned char *commit_data;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (graph_pos(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \tcommit_data = g->chunk_commit_data +\n-\t\t\tGRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);\n+\t\t\tGRAPH_DATA_WIDTH * (graph_pos(c) - g->num_commits_in_base);\n \n \thashcpy(oid.hash, commit_data);\n \tset_commit_tree(c, lookup_tree(r, &oid));\n@@ -861,7 +889,7 @@ static struct tree *get_commit_tree_in_graph_one(struct repository *r,\n {\n \tif (c->maybe_tree)\n \t\treturn c->maybe_tree;\n-\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\tif (graph_pos(c) == COMMIT_NOT_FROM_GRAPH)\n \t\tBUG(\"get_commit_tree_in_graph_one called from non-commit-graph commit\");\n \n \treturn load_tree_for_commit(r, g, (struct commit *)c);\n@@ -1247,7 +1275,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\tcontinue;\n \t\tif (ctx->split) {\n \t\t\tif ((!parse_commit(commit) &&\n-\t\t\t commit->graph_pos == COMMIT_NOT_FROM_GRAPH) ||\n+\t\t\t graph_pos(commit) == COMMIT_NOT_FROM_GRAPH) ||\n \t\t\t flags == COMMIT_GRAPH_SPLIT_REPLACE)\n \t\t\t\tadd_missing_parents(ctx, commit);\n \t\t} else if (!parse_commit_no_graph(commit))\n@@ -1493,7 +1521,7 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n \t\t\tif (ctx->split) {\n \t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n-\t\t\t\tif (!c || c->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t\t\tif (!c || graph_pos(c) != COMMIT_NOT_FROM_GRAPH)\n \t\t\t\t\tcontinue;\n \t\t\t}\n \n@@ -1527,7 +1555,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n-\t\t ctx->commits.list[ctx->commits.nr]->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t graph_pos(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n \t\t\tcontinue;\n \n \t\tif (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 653bd041ad..3cb59ba336 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -8,6 +8,7 @@\n #include \"object-store.h\"\n #include \"oidset.h\"\n \n+#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n #define GENERATION_NUMBER_MAX 0x3FFFFFFF\n #define GENERATION_NUMBER_ZERO 0\n@@ -142,4 +143,6 @@ void free_commit_graph(struct commit_graph *);\n void disable_commit_graph(struct repository *r);\n \n uint32_t generation(const struct commit *c);\n+\n+uint32_t graph_pos(const struct commit *c);\n #endif\ndiff --git a/commit.c b/commit.c\nindex 8dad0f8446..da6de08b2b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r,\n \tif (commit->maybe_tree || !commit->object.parsed)\n \t\treturn commit->maybe_tree;\n \n-\tif (commit->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\tif (graph_pos(commit) != COMMIT_NOT_FROM_GRAPH)\n \t\treturn get_commit_tree_in_graph(r, commit);\n \n \treturn NULL;\ndiff --git a/commit.h b/commit.h\nindex 01e1c4c3eb..0b10464a10 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -10,8 +10,6 @@\n #include \"pretty.h\"\n #include \"commit-slab.h\"\n \n-#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n-\n struct commit_list {\n \tstruct commit *item;\n \tstruct commit_list *next;\ndiff --git a/contrib/coccinelle/graph_pos.cocci b/contrib/coccinelle/graph_pos.cocci\nnew file mode 100644\nindex 0000000000..0929164bdf\n--- /dev/null\n+++ b/contrib/coccinelle/graph_pos.cocci\n@@ -0,0 +1,12 @@\n+@@\n+struct commit *c;\n+expression E;\n+@@\n+- c->graph_pos = E\n++ set_graph_pos(c, E)\n+\n+@@\n+struct commit *c;\n+@@\n+- c->graph_pos\n++ graph_pos(c)\n-- \n2.27.0\n\n"},{"id":"399103","messageId":"20200604072759.19142-3-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"[GSoC Patch 2/3] commit: convert commit->generation to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-04T07:27:58Z","receivedAt":"2020-06-04T07:30:10Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"In this commit, we will use the generation slab helpers introduced in\nlast commit and replace existing uses of commit->generation using\n'contrib/coccinelle/generation.cocci'\n\nSigned-off-by: Abhishek Kumar \n---\n alloc.c | 1 -\n blame.c | 2 +-\n commit-graph.c | 39 +++++++++++-----------\n commit-reach.c | 50 ++++++++++++++---------------\n commit.c | 4 +--\n commit.h | 1 -\n contrib/coccinelle/generation.cocci | 12 +++++++\n revision.c | 16 ++++-----\n 8 files changed, 68 insertions(+), 57 deletions(-)\n create mode 100644 contrib/coccinelle/generation.cocci\n\ndiff --git a/alloc.c b/alloc.c\nindex 1c64c4dd16..cbed187094 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -109,7 +109,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n \tc->object.type = OBJ_COMMIT;\n \tc->index = alloc_commit_index(r);\n \tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n-\tc->generation = GENERATION_NUMBER_INFINITY;\n }\n \n void *alloc_commit_node(struct repository *r)\ndiff --git a/blame.c b/blame.c\nindex da7e28800e..50e6316076 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,\n \tif (!bd)\n \t\treturn 1;\n \n-\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (generation(origin->commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn 1;\n \n \tfilter = get_bloom_filter(r, origin->commit, 0);\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 63f419048d..9ce7d4acb1 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -120,9 +120,9 @@ static int commit_gen_cmp(const void *va, const void *vb)\n \tconst struct commit *b = *(const struct commit **)vb;\n \n \t/* lower generation commits first */\n-\tif (a->generation < b->generation)\n+\tif (generation(a) < generation(b))\n \t\treturn -1;\n-\telse if (a->generation > b->generation)\n+\telse if (generation(a) > generation(b))\n \t\treturn 1;\n \n \t/* use date as a heuristic when generations are equal */\n@@ -712,7 +712,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n \titem->graph_pos = pos;\n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n }\n \n static inline void set_commit_tree(struct commit *c, struct tree *t)\n@@ -754,7 +754,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n \titem->date = (timestamp_t)((date_high << 32) | date_low);\n \n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n \n \tpptr = &item->parents;\n \n@@ -1048,7 +1048,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\telse\n \t\t\tpackedDate[0] = 0;\n \n-\t\tpackedDate[0] |= htonl((*list)->generation << 2);\n+\t\tpackedDate[0] |= htonl(generation((*list)) << 2);\n \n \t\tpackedDate[1] = htonl((*list)->date);\n \t\thashwrite(f, packedDate, 8);\n@@ -1280,8 +1280,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->commits.nr);\n \tfor (i = 0; i < ctx->commits.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n-\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n+\t\tif (generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n+\t\t generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n \t\t\tcontinue;\n \n \t\tcommit_list_insert(ctx->commits.list[i], &list);\n@@ -1292,22 +1292,23 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\tuint32_t max_generation = 0;\n \n \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n-\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n-\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n+\t\t\t\tif (generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t generation(parent->item) == GENERATION_NUMBER_ZERO) {\n \t\t\t\t\tall_parents_computed = 0;\n \t\t\t\t\tcommit_list_insert(parent->item, &list);\n \t\t\t\t\tbreak;\n-\t\t\t\t} else if (parent->item->generation > max_generation) {\n-\t\t\t\t\tmax_generation = parent->item->generation;\n+\t\t\t\t} else if (generation(parent->item) > max_generation) {\n+\t\t\t\t\tmax_generation = generation(parent->item);\n \t\t\t\t}\n \t\t\t}\n \n \t\t\tif (all_parents_computed) {\n-\t\t\t\tcurrent->generation = max_generation + 1;\n+\t\t\t\tset_generation(current, max_generation + 1);\n \t\t\t\tpop_commit(&list);\n \n-\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n-\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n+\t\t\t\tif (generation(current) > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tset_generation(current,\n+\t\t\t\t\t\t GENERATION_NUMBER_MAX);\n \t\t\t}\n \t\t}\n \t}\n@@ -2314,8 +2315,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n \n-\t\t\tif (graph_parents->item->generation > max_generation)\n-\t\t\t\tmax_generation = graph_parents->item->generation;\n+\t\t\tif (generation(graph_parents->item) > max_generation)\n+\t\t\t\tmax_generation = generation(graph_parents->item);\n \n \t\t\tgraph_parents = graph_parents->next;\n \t\t\todb_parents = odb_parents->next;\n@@ -2325,7 +2326,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\tgraph_report(_(\"commit-graph parent list for commit %s terminates early\"),\n \t\t\t\t oid_to_hex(&cur_oid));\n \n-\t\tif (!graph_commit->generation) {\n+\t\tif (!generation(graph_commit)) {\n \t\t\tif (generation_zero == GENERATION_NUMBER_EXISTS)\n \t\t\t\tgraph_report(_(\"commit-graph has generation number zero for commit %s, but non-zero elsewhere\"),\n \t\t\t\t\t oid_to_hex(&cur_oid));\n@@ -2345,10 +2346,10 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tif (max_generation == GENERATION_NUMBER_MAX)\n \t\t\tmax_generation--;\n \n-\t\tif (graph_commit->generation != max_generation + 1)\n+\t\tif (generation(graph_commit) != max_generation + 1)\n \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n \t\t\t\t oid_to_hex(&cur_oid),\n-\t\t\t\t graph_commit->generation,\n+\t\t\t\t generation(graph_commit),\n \t\t\t\t max_generation + 1);\n \n \t\tif (graph_commit->date != odb_commit->date)\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 4ca7e706a1..77c980054a 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -59,13 +59,13 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \n-\t\tif (min_generation && commit->generation > last_gen)\n+\t\tif (min_generation && generation(commit) > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit->generation, last_gen,\n+\t\t\t generation(commit), last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit->generation;\n+\t\tlast_gen = generation(commit);\n \n-\t\tif (commit->generation < min_generation)\n+\t\tif (generation(commit) < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -176,7 +176,7 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\trepo_parse_commit(r, array[i]);\n \tfor (i = 0; i < cnt; i++) {\n \t\tstruct commit_list *common;\n-\t\tuint32_t min_generation = array[i]->generation;\n+\t\tuint32_t min_generation = generation(array[i]);\n \n \t\tif (redundant[i])\n \t\t\tcontinue;\n@@ -186,8 +186,8 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\t\tfilled_index[filled] = j;\n \t\t\twork[filled++] = array[j];\n \n-\t\t\tif (array[j]->generation < min_generation)\n-\t\t\t\tmin_generation = array[j]->generation;\n+\t\t\tif (generation(array[j]) < min_generation)\n+\t\t\t\tmin_generation = generation(array[j]);\n \t\t}\n \t\tcommon = paint_down_to_common(r, array[i], filled,\n \t\t\t\t\t work, min_generation);\n@@ -323,16 +323,16 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tfor (i = 0; i < nr_reference; i++) {\n \t\tif (repo_parse_commit(r, reference[i]))\n \t\t\treturn ret;\n-\t\tif (reference[i]->generation < min_generation)\n-\t\t\tmin_generation = reference[i]->generation;\n+\t\tif (generation(reference[i]) < min_generation)\n+\t\t\tmin_generation = generation(reference[i]);\n \t}\n \n-\tif (commit->generation > min_generation)\n+\tif (generation(commit) > min_generation)\n \t\treturn ret;\n \n \tbases = paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t commit->generation);\n+\t\t\t\t generation(commit));\n \tif (commit->object.flags & PARENT2)\n \t\tret = 1;\n \tclear_commit_marks(commit, all_flags);\n@@ -467,7 +467,7 @@ static enum contains_result contains_test(struct commit *candidate,\n \t/* Otherwise, we don't know; prepare to recurse */\n \tparse_commit_or_die(candidate);\n \n-\tif (candidate->generation < cutoff)\n+\tif (generation(candidate) < cutoff)\n \t\treturn CONTAINS_NO;\n \n \treturn CONTAINS_UNKNOWN;\n@@ -492,8 +492,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tfor (p = want; p; p = p->next) {\n \t\tstruct commit *c = p->item;\n \t\tload_commit_graph_info(the_repository, c);\n-\t\tif (c->generation < cutoff)\n-\t\t\tcutoff = c->generation;\n+\t\tif (generation(c) < cutoff)\n+\t\t\tcutoff = generation(c);\n \t}\n \n \tresult = contains_test(candidate, want, cache, cutoff);\n@@ -544,9 +544,9 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \tconst struct commit *a = *(const struct commit * const *)_a;\n \tconst struct commit *b = *(const struct commit * const *)_b;\n \n-\tif (a->generation < b->generation)\n+\tif (generation(a) < generation(b))\n \t\treturn -1;\n-\tif (a->generation > b->generation)\n+\tif (generation(a) > generation(b))\n \t\treturn 1;\n \treturn 0;\n }\n@@ -585,7 +585,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\tlist[nr_commits] = (struct commit *)from_one;\n \t\tif (parse_commit(list[nr_commits]) ||\n-\t\t list[nr_commits]->generation < min_generation) {\n+\t\t generation(list[nr_commits]) < min_generation) {\n \t\t\tresult = 0;\n \t\t\tgoto cleanup;\n \t\t}\n@@ -621,7 +621,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\t\t\t\tif (parse_commit(parent->item) ||\n \t\t\t\t\t parent->item->date < min_commit_date ||\n-\t\t\t\t\t parent->item->generation < min_generation)\n+\t\t\t\t\t generation(parent->item) < min_generation)\n \t\t\t\t\t\tcontinue;\n \n \t\t\t\t\tcommit_list_insert(parent->item, &stack);\n@@ -665,8 +665,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (from_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = from_iter->item->date;\n \n-\t\t\tif (from_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = from_iter->item->generation;\n+\t\t\tif (generation(from_iter->item) < min_generation)\n+\t\t\t\tmin_generation = generation(from_iter->item);\n \t\t}\n \n \t\tfrom_iter = from_iter->next;\n@@ -677,8 +677,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (to_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\t\tif (to_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = to_iter->item->generation;\n+\t\t\tif (generation(to_iter->item) < min_generation)\n+\t\t\t\tmin_generation = generation(to_iter->item);\n \t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n@@ -721,8 +721,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \t\tstruct commit *c = *item;\n \n \t\tparse_commit(c);\n-\t\tif (c->generation < min_generation)\n-\t\t\tmin_generation = c->generation;\n+\t\tif (generation(c) < min_generation)\n+\t\t\tmin_generation = generation(c);\n \n \t\tif (!(c->object.flags & PARENT1)) {\n \t\t\tc->object.flags |= PARENT1;\n@@ -755,7 +755,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \n \t\t\tparse_commit(p);\n \n-\t\t\tif (p->generation < min_generation)\n+\t\t\tif (generation(p) < min_generation)\n \t\t\t\tcontinue;\n \n \t\t\tif (p->object.flags & PARENT2)\ndiff --git a/commit.c b/commit.c\nindex 87686a7055..8dad0f8446 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void\n \tconst struct commit *a = a_, *b = b_;\n \n \t/* newer commits first */\n-\tif (a->generation < b->generation)\n+\tif (generation(a) < generation(b))\n \t\treturn 1;\n-\telse if (a->generation > b->generation)\n+\telse if (generation(a) > generation(b))\n \t\treturn -1;\n \n \t/* use date as a heuristic when generations are equal */\ndiff --git a/commit.h b/commit.h\nindex cc610400d5..01e1c4c3eb 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -34,7 +34,6 @@ struct commit {\n \t */\n \tstruct tree *maybe_tree;\n \tuint32_t graph_pos;\n-\tuint32_t generation;\n \tunsigned int index;\n };\n \ndiff --git a/contrib/coccinelle/generation.cocci b/contrib/coccinelle/generation.cocci\nnew file mode 100644\nindex 0000000000..da13c44856\n--- /dev/null\n+++ b/contrib/coccinelle/generation.cocci\n@@ -0,0 +1,12 @@\n+@@\n+struct commit *c;\n+expression E;\n+@@\n+- c->generation = E\n++ set_generation(c, E)\n+\n+@@\n+struct commit *c;\n+@@\n+- c->generation\n++ generation(c)\ndiff --git a/revision.c b/revision.c\nindex 60cca8c0b9..d76382007c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -720,7 +720,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \tif (!revs->repo->objects->commit_graph)\n \t\treturn -1;\n \n-\tif (commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n \tfilter = get_bloom_filter(revs->repo, commit, 0);\n@@ -3314,7 +3314,7 @@ static void explore_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->explore_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t generation(c) >= gen_cutoff)\n \t\texplore_walk_step(revs);\n }\n \n@@ -3330,7 +3330,7 @@ static void indegree_walk_step(struct rev_info *revs)\n \tif (parse_commit_gently(c, 1) < 0)\n \t\treturn;\n \n-\texplore_to_depth(revs, c->generation);\n+\texplore_to_depth(revs, generation(c));\n \n \tfor (p = c->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n@@ -3354,7 +3354,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t generation(c) >= gen_cutoff)\n \t\tindegree_walk_step(revs);\n }\n \n@@ -3414,8 +3414,8 @@ static void init_topo_walk(struct rev_info *revs)\n \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n \n-\t\tif (c->generation < info->min_generation)\n-\t\t\tinfo->min_generation = c->generation;\n+\t\tif (generation(c) < info->min_generation)\n+\t\t\tinfo->min_generation = generation(c);\n \n \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n \n@@ -3473,8 +3473,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-\t\tif (parent->generation < info->min_generation) {\n-\t\t\tinfo->min_generation = parent->generation;\n+\t\tif (generation(parent) < info->min_generation) {\n+\t\t\tinfo->min_generation = generation(parent);\n \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n \t\t}\n \n-- \n2.27.0\n\n"},{"id":"399111","messageId":"b850637d-a7ca-e8f9-5009-657096ea2975@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-04T14:22:27Z","receivedAt":"2020-06-04T14:22:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> The struct commit is used in many contexts. However, members generation\n> and graph_pos are only used for commit-graph related operations and\n> otherwise waste memory.\n> \n> This wastage would have been more pronounced as transistion to\n> generation number v2, which uses 64-bit generation number instead of\n> current 32-bits.\n\nThanks! This is an important step, and will already improve\nperformance in subtle ways.\n\n> The third patch (\"commit: convert commit->graph_pos to a slab\",\n> 2020-06-04) is currently failing diff-submodule related tests (t4041,\n> t4059 and t4060) for gcc [1]. I am going to send a second version soon,\n> fixing that.\n> \n> [1]: https://travis-ci.com/github/abhishekkumar2718/git/jobs/343441189\n> \n> Abhishek Kumar (3):\n> commit: introduce helpers for generation slab\n> commit: convert commit->generation to a slab\n> commit: convert commit->graph_pos to a slab\n\nIf we have a commit-graph file, then we have graph_pos\nand generation both coming from that file. Perhaps it\nwould be better to combine the data into a single slab\nthat stores a \"struct commit_graph_data\" or something?\n\nThis would change only the slab definitions, since you\nalready do a good job of wrapping the slab access in\nmethods.\n\n> alloc.c | 2 -\n> blame.c | 2 +-\n> bloom.c | 6 +-\n> commit-graph.c | 116 +++++++++++++++++++++-------\n> commit-graph.h | 8 ++\n> commit-reach.c | 50 ++++++------\n> commit.c | 6 +-\n> commit.h | 6 --\n> contrib/coccinelle/generation.cocci | 12 +++\n> contrib/coccinelle/graph_pos.cocci | 12 +++\n> revision.c | 16 ++--\n> 11 files changed, 158 insertions(+), 78 deletions(-)\n> create mode 100644 contrib/coccinelle/generation.cocci\n> create mode 100644 contrib/coccinelle/graph_pos.cocci\n\nI appreciate the Coccinelle scripts to help identify\nautomatic fixes for other topics in-flight. However,\nI wonder if they would be better placed inside the\nexisting commit.cocci file?\n\nThanks,\n-Stolee\n"},{"id":"399112","messageId":"9a15c7ba-8b55-099a-3c59-b5e7ff6124f6@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-3-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 2/3] commit: convert commit->generation to a slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-04T14:27:39Z","receivedAt":"2020-06-04T14:27:43Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> In this commit, we will use the generation slab helpers introduced in\n> last commit and replace existing uses of commit->generation using\n> 'contrib/coccinelle/generation.cocci'\n> @@ -1048,7 +1048,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n> \t\telse\n> \t\t\tpackedDate[0] = 0;\n> \n> -\t\tpackedDate[0] |= htonl((*list)->generation << 2);\n> +\t\tpackedDate[0] |= htonl(generation((*list)) << 2);\n\nnit: We no longer need the extra parens around *list.\n\n> @@ -3414,8 +3414,8 @@ static void init_topo_walk(struct rev_info *revs)\n> \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n> \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n> \n> -\t\tif (c->generation < info->min_generation)\n> -\t\t\tinfo->min_generation = c->generation;\n> +\t\tif (generation(c) < info->min_generation)\n> +\t\t\tinfo->min_generation = generation(c);\n\nA pattern I've noticed in several places is that the struct\nmember is accessed multiple times in the same method body,\nand this is auto-converted to multiple method calls. However,\nthese values are fixed, so it would be better to store the\nvalue as a local variable and reuse that variable instead.\n\nThis is one of the shortcomings of the Coccinelle transformation,\nso you'll need to manually inspect each of the diff fragments to\nsee if we can reduce the number of method calls. It might be\nhelpful to do that as a follow-up, so we can see that this patch\nis generated by the Coccinelle script, and then a later patch can\nbe scrutinized more carefully when you are doing manual code\nmanipulation.\n\nThanks,\n-Stolee\n"},{"id":"399114","messageId":"be28ab7b-0ae4-2cc5-7f2b-92075de3723a@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-2-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 1/3] commit: introduce helpers for generation slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-04T14:36:49Z","receivedAt":"2020-06-04T14:36:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> The struct member generation refers to \"generation number\" (or more\n> broadly, a reachablity index value) used by commit-graph to reduce time\n> taken to walk commits. However, generation is not useful in other\n> contexts and bloats the struct.\n> \n> Let's move it to a commit-slab and shrink the struct by four bytes.\n> \n> Signed-off-by: Abhishek Kumar \n> ---\n> commit-graph.c | 27 +++++++++++++++++++++++++++\n> commit-graph.h | 5 +++++\n> commit.h | 3 ---\n> 3 files changed, 32 insertions(+), 3 deletions(-)\n> \n> diff --git a/commit-graph.c b/commit-graph.c\n> index e3420ddcbf..63f419048d 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb)\n> \t commit_pos_at(&commit_pos, b);\n> }\n> \n> +define_commit_slab(generation_slab, uint32_t);\n> +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n> +\n> +uint32_t generation(const struct commit *c)\n> +{\n> +\tuint32_t *gen = generation_slab_peek(&generation_slab, c);\n> +\n> +\treturn gen ? *gen : GENERATION_NUMBER_INFINITY;\n> +}\n\nThis is good: if we don't have the value, then use INFINITY.\nIn the header file, perhaps include a warning comment that a\ncaller _must_ first parse the commit or else we have no guarantee\nthat the generation slab is populated. This matches the current\nexpectations before accessing the generation member.\n\n> +static void set_generation(const struct commit *c, const uint32_t generation)\n> +{\n> +\tunsigned int i = generation_slab.slab_count;\n> +\tuint32_t *gen = generation_slab_at(&generation_slab, c);\n> +\n> +\t/*\n> +\t * commit-slab initializes with zero, overwrite this with\n> +\t * GENERATION_NUMBER_INFINITY\n> +\t */\n> +\tfor (; i < generation_slab.slab_count; ++i) {\n> +\t\tmemset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY,\n> +\t\t generation_slab.slab_size * sizeof(uint32_t));\n> +\t}\n\nHere is an example where combining the graph_pos and generation\nslabs into one would be helpful. The only reason the generation\nwould be INFINITY is if graph_pos is COMMIT_NOT_FROM_GRAPH. If\nthe two values are side-by-side, we could just check graph_pos\nfirst and return INFINITY instead of paying this initialization\ncost as the slab grows.\n\nI would also like to avoid initializing the slab if there is\nno commit-graph present. I wonder if we can populate the slab\nwhile parsing the commit-graph and check here if the slab is\nNULL before doing any other logic? (I'm not sure if this is\npossible, but it would be nice.)\n\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 4212766a4f..653bd041ad 100644\n> --- a/commit-graph.h\n> +++ b/commit-graph.h\n> @@ -8,6 +8,10 @@\n> #include \"object-store.h\"\n> #include \"oidset.h\"\n> \n> +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> +#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> +#define GENERATION_NUMBER_ZERO 0\n> +\n> #define GIT_TEST_COMMIT_GRAPH \"GIT_TEST_COMMIT_GRAPH\"\n> #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD \"GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD\"\n> #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS \"GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\"\n> @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *);\n> */\n> void disable_commit_graph(struct repository *r);\n> \n> +uint32_t generation(const struct commit *c);\n> #endif\n> diff --git a/commit.h b/commit.h\n> index 1b2dea5d85..cc610400d5 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -11,9 +11,6 @@\n> #include \"commit-slab.h\"\n> \n> #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n> -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> -#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> -#define GENERATION_NUMBER_ZERO 0\n\nI appreciate that you are able to relocate these constants to\na more appropriate location.\n\nThanks,\n-Stolee\n\n\n"},{"id":"399128","messageId":"xmqqk10mpwdy.fsf@gitster.c.googlers.com","threadId":"53611","inReplyTo":"20200604072759.19142-2-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 1/3] commit: introduce helpers for generation slab","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-04T17:35:05Z","receivedAt":"2020-06-04T17:35:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Abhishek Kumar writes:\n\n> The struct member generation refers to \"generation number\" (or more\n> broadly, a reachablity index value) used by commit-graph to reduce time\n> taken to walk commits. However, generation is not useful in other\n> contexts and bloats the struct.\n>\n> Let's move it to a commit-slab and shrink the struct by four bytes.\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> commit-graph.c | 27 +++++++++++++++++++++++++++\n> commit-graph.h | 5 +++++\n> commit.h | 3 ---\n> 3 files changed, 32 insertions(+), 3 deletions(-)\n>\n> diff --git a/commit-graph.c b/commit-graph.c\n> index e3420ddcbf..63f419048d 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb)\n> \t commit_pos_at(&commit_pos, b);\n> }\n> \n> +define_commit_slab(generation_slab, uint32_t);\n> +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n> +\n> +uint32_t generation(const struct commit *c)\n> +{\n> +\tuint32_t *gen = generation_slab_peek(&generation_slab, c);\n> +\n> +\treturn gen ? *gen : GENERATION_NUMBER_INFINITY;\n> +}\n> +\n> +static void set_generation(const struct commit *c, const uint32_t generation)\n> +{\n> +\tunsigned int i = generation_slab.slab_count;\n> +\tuint32_t *gen = generation_slab_at(&generation_slab, c);\n> +\n> +\t/*\n> +\t * commit-slab initializes with zero, overwrite this with\n> +\t * GENERATION_NUMBER_INFINITY\n> +\t */\n> +\tfor (; i < generation_slab.slab_count; ++i) {\n\nStyle: favor post-increment over pre-increment when there is no\ndifference, especially when updating the loop control in for() loop.\n\n> +\t\tmemset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY,\n> +\t\t generation_slab.slab_size * sizeof(uint32_t));\n> +\t}\n> +\n> +\t*gen = generation;\n> +}\n> +\n> static int commit_gen_cmp(const void *va, const void *vb)\n> {\n> \tconst struct commit *a = *(const struct commit **)va;\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 4212766a4f..653bd041ad 100644\n> --- a/commit-graph.h\n> +++ b/commit-graph.h\n> @@ -8,6 +8,10 @@\n> #include \"object-store.h\"\n> #include \"oidset.h\"\n> \n> +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> +#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> +#define GENERATION_NUMBER_ZERO 0\n> +\n\nMakes sense to move it from commit.h, I guess.\n\n> #define GIT_TEST_COMMIT_GRAPH \"GIT_TEST_COMMIT_GRAPH\"\n> #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD \"GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD\"\n> #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS \"GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\"\n> @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *);\n> */\n> void disable_commit_graph(struct repository *r);\n> \n> +uint32_t generation(const struct commit *c);\n> #endif\n> diff --git a/commit.h b/commit.h\n> index 1b2dea5d85..cc610400d5 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -11,9 +11,6 @@\n> #include \"commit-slab.h\"\n> \n> #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n> -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> -#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> -#define GENERATION_NUMBER_ZERO 0\n> \n> struct commit_list {\n> \tstruct commit *item;\n"},{"id":"399130","messageId":"xmqqftbapvpi.fsf@gitster.c.googlers.com","threadId":"53611","inReplyTo":"20200604072759.19142-3-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 2/3] commit: convert commit->generation to a slab","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-04T17:49:45Z","receivedAt":"2020-06-04T17:49:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Abhishek Kumar writes:\n\n> In this commit, we will use the generation slab helpers introduced in\n> last commit and replace existing uses of commit->generation using\n> 'contrib/coccinelle/generation.cocci'\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> alloc.c | 1 -\n> blame.c | 2 +-\n> commit-graph.c | 39 +++++++++++-----------\n> commit-reach.c | 50 ++++++++++++++---------------\n> commit.c | 4 +--\n> commit.h | 1 -\n> contrib/coccinelle/generation.cocci | 12 +++++++\n> revision.c | 16 ++++-----\n> 8 files changed, 68 insertions(+), 57 deletions(-)\n> create mode 100644 contrib/coccinelle/generation.cocci\n>\n> diff --git a/alloc.c b/alloc.c\n> index 1c64c4dd16..cbed187094 100644\n> --- a/alloc.c\n> +++ b/alloc.c\n> @@ -109,7 +109,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n> \tc->object.type = OBJ_COMMIT;\n> \tc->index = alloc_commit_index(r);\n> \tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n> -\tc->generation = GENERATION_NUMBER_INFINITY;\n> }\n> \n> void *alloc_commit_node(struct repository *r)\n> diff --git a/blame.c b/blame.c\n> index da7e28800e..50e6316076 100644\n> --- a/blame.c\n> +++ b/blame.c\n> @@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,\n> \tif (!bd)\n> \t\treturn 1;\n> \n> -\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n> +\tif (generation(origin->commit) == GENERATION_NUMBER_INFINITY)\n\nHmmmm, as C is not all that object-oriented that lets us say \"commit\nobjects have generation() method\", a plain vanilla function whose\nname is generation() is a bit overly vague. The field name this\nhelper function replaces, .generation, is very localized to a commit\n\"object\" and does not have such a problem.\n\nWe probably need to choose a better name in the previous step to fix\nit.\n\n"},{"id":"399145","messageId":"xmqqbllypvfj.fsf@gitster.c.googlers.com","threadId":"53611","inReplyTo":"b850637d-a7ca-e8f9-5009-657096ea2975@gmail.com","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-04T17:55:44Z","receivedAt":"2020-06-04T17:55:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> If we have a commit-graph file, then we have graph_pos\n> and generation both coming from that file. Perhaps it\n> would be better to combine the data into a single slab\n> that stores a \"struct commit_graph_data\" or something?\n\nExcellent.\n"},{"id":"399208","messageId":"85ftb9wd5j.fsf@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-05T19:00:56Z","receivedAt":"2020-06-05T19:01:03Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> The struct commit is used in many contexts. However, members generation\n> and graph_pos are only used for commit-graph related operations and\n> otherwise waste memory.\n\nVery minor nitpick: this sentence would read better if the names of\n`generation` and `graph_pos` fields (but especially the 'generation')\nwere quoted.\n\n>\n> This wastage would have been more pronounced as transistion to\n> generation number v2, which uses 64-bit generation number instead of\n> current 32-bits.\n\nGood. Moving reachability index value into a commit slab was one of\nprerequisites to switching to the generation number v2, see [2]\n\n[2]: https://public-inbox.org/git/cfa2c367-5cd7-add5-0293-caa75b103f34@gmail.com/t/#u\n\nThe other prerequisite was proper handling of commit-graph format\nchange, either by using \"metadata chunk\" as more flexible replacement of\nmishandled format version field in the commit-graph file header, or as\nproposed in [3] (and subsequent posts), removing \"CDAT\" chunk and\nreplacing it with \"CDA2\" chunk.\n\n[3]: https://public-inbox.org/git/xmqq369z7i1b.fsf@gitster.c.googlers.com/t/#u\n\n\nAlso, we should probably stop mishandling the format version field, that\nis do not error out [4] when commit-graph version of the file does not\nmatch version supported by git code running the command, but just simply\nnot use the commit-graph (like it is done for Bloom filter chunks).\n\n[4]: https://github.com/git/git/blob/master/commit-graph.c#L253\n\n>\n> The third patch (\"commit: convert commit->graph_pos to a slab\",\n> 2020-06-04) is currently failing diff-submodule related tests (t4041,\n> t4059 and t4060) for gcc [1]. I am going to send a second version soon,\n> fixing that.\n>\n> [1]: https://travis-ci.com/github/abhishekkumar2718/git/jobs/343441189\n>\n> Abhishek Kumar (3):\n> commit: introduce helpers for generation slab\n> commit: convert commit->generation to a slab\n> commit: convert commit->graph_pos to a slab\n>\n> alloc.c | 2 -\n> blame.c | 2 +-\n> bloom.c | 6 +-\n> commit-graph.c | 116 +++++++++++++++++++++-------\n> commit-graph.h | 8 ++\n> commit-reach.c | 50 ++++++------\n> commit.c | 6 +-\n> commit.h | 6 --\n> contrib/coccinelle/generation.cocci | 12 +++\n> contrib/coccinelle/graph_pos.cocci | 12 +++\n\nIt is nice to see the use of Coccinelle scripts.\n\n> revision.c | 16 ++--\n> 11 files changed, 158 insertions(+), 78 deletions(-)\n> create mode 100644 contrib/coccinelle/generation.cocci\n> create mode 100644 contrib/coccinelle/graph_pos.cocci\n\nBest,\n-- \nJakub Narębski\n"},{"id":"399221","messageId":"857dwlw102.fsf@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-2-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 1/3] commit: introduce helpers for generation slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-05T23:23:25Z","receivedAt":"2020-06-05T23:23:31Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> The struct member generation refers to \"generation number\" (or more\n\nAgain, a minor thing: 'generation'.\n\n> broadly, a reachablity index value) used by commit-graph to reduce time\n> taken to walk commits. However, generation is not useful in other\n> contexts and bloats the struct.\n>\n> Let's move it to a commit-slab and shrink the struct by four bytes.\n\nIt looks like the description is from earlier version of the commit,\nbefore it was split -- because this commit does not remove 'generation'\nmember from the 'struct commit', actually.\n\nThis commit is about creating helper functions.\n\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> commit-graph.c | 27 +++++++++++++++++++++++++++\n> commit-graph.h | 5 +++++\n> commit.h | 3 ---\n> 3 files changed, 32 insertions(+), 3 deletions(-)\n>\n> diff --git a/commit-graph.c b/commit-graph.c\n> index e3420ddcbf..63f419048d 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -87,6 +87,33 @@ static int commit_pos_cmp(const void *va, const void *vb)\n> \t commit_pos_at(&commit_pos, b);\n> }\n> \n> +define_commit_slab(generation_slab, uint32_t);\n> +static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n\nAll right, we need this for the following helper functions to work.\n\nWe might want to encapsulate all commit-graph data together, in a single\nstruct (e.g. as 'struct commit_graph_data' instead of uint32_t here).\n\nOn the other hand other data is stored on slab often as separate\nscalar data (contains_cache, commit_seen, indegree_slab,\nauthor_date_slab, commit_base, commit_pos), but not always; sometimes it\nis a struct (bloom_filter_slab, buffer_slab, commit_rev_name), sometimes\nit is an array (commit_depth, ref_bitmap, commit_weight), and sometimes\nit is an array/list of structs or pointer to struct (commit_names,\ncommit_name_slab, saved_parents, blame_suspects, commit_todo_item).\n\n> +\n> +uint32_t generation(const struct commit *c)\n> +{\n> +\tuint32_t *gen = generation_slab_peek(&generation_slab, c);\n> +\n> +\treturn gen ? *gen : GENERATION_NUMBER_INFINITY;\n> +}\n\nAll right, this is a synthetic getter using the fact that commits\noutside the commit-graph should get GENERATION_NUMBER_INFINITY (because\n[effective] commit-graph is closed under reachability, is full DAG).\n\nShould we have something like that for 'graph_pos' and\nCOMMIT_NOT_FROM_GRAPH?\n\n> +\n> +static void set_generation(const struct commit *c, const uint32_t generation)\n> +{\n> +\tunsigned int i = generation_slab.slab_count;\n> +\tuint32_t *gen = generation_slab_at(&generation_slab, c);\n> +\n> +\t/*\n> +\t * commit-slab initializes with zero, overwrite this with\n> +\t * GENERATION_NUMBER_INFINITY\n> +\t */\n> +\tfor (; i < generation_slab.slab_count; ++i) {\n> +\t\tmemset(generation_slab.slab[i], GENERATION_NUMBER_INFINITY,\n> +\t\t generation_slab.slab_size * sizeof(uint32_t));\n> +\t}\n> +\n> +\t*gen = generation;\n> +}\n\nAll right. I wonder if putting 'generation' and 'graph_pos' on the slab\ntogether, gathered in 'struct commit_graph_data' would make this helper\nmore complex...\n\n> +\n> static int commit_gen_cmp(const void *va, const void *vb)\n> {\n> \tconst struct commit *a = *(const struct commit **)va;\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 4212766a4f..653bd041ad 100644\n> --- a/commit-graph.h\n> +++ b/commit-graph.h\n> @@ -8,6 +8,10 @@\n> #include \"object-store.h\"\n> #include \"oidset.h\"\n> \n> +#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> +#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> +#define GENERATION_NUMBER_ZERO 0\n> +\n> #define GIT_TEST_COMMIT_GRAPH \"GIT_TEST_COMMIT_GRAPH\"\n> #define GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD \"GIT_TEST_COMMIT_GRAPH_DIE_ON_LOAD\"\n> #define GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS \"GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\"\n> @@ -137,4 +141,5 @@ void free_commit_graph(struct commit_graph *);\n> */\n> void disable_commit_graph(struct repository *r);\n> \n> +uint32_t generation(const struct commit *c);\n> #endif\n> diff --git a/commit.h b/commit.h\n> index 1b2dea5d85..cc610400d5 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -11,9 +11,6 @@\n> #include \"commit-slab.h\"\n> \n> #define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n> -#define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> -#define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> -#define GENERATION_NUMBER_ZERO 0\n> \n> struct commit_list {\n> \tstruct commit *item;\n\nWhy this change?\n\nBest,\n-- \nJakub Narębski\n"},{"id":"399234","messageId":"85lfkzvolh.fsf@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-3-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 2/3] commit: convert commit->generation to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-06T22:03:38Z","receivedAt":"2020-06-06T22:06:12Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> In this commit, we will use the generation slab helpers introduced in\n> last commit and replace existing uses of commit->generation using\n> 'contrib/coccinelle/generation.cocci'\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> alloc.c | 1 -\n> blame.c | 2 +-\n> commit-graph.c | 39 +++++++++++-----------\n> commit-reach.c | 50 ++++++++++++++---------------\n> commit.c | 4 +--\n> commit.h | 1 -\n> contrib/coccinelle/generation.cocci | 12 +++++++\n> revision.c | 16 ++++-----\n> 8 files changed, 68 insertions(+), 57 deletions(-)\n> create mode 100644 contrib/coccinelle/generation.cocci\n>\n\nFor easier review I have changed the order of files, grouping together\ndifferent categories of changes.\n\n\nFirst category is removing commit->generation and related changes:\n\n> diff --git a/commit.h b/commit.h\n> index cc610400d5..01e1c4c3eb 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -34,7 +34,6 @@ struct commit {\n> \t */\n> \tstruct tree *maybe_tree;\n> \tuint32_t graph_pos;\n> -\tuint32_t generation;\n> \tunsigned int index;\n> };\n> \n\nThis is quite straightforward.\n\n> diff --git a/alloc.c b/alloc.c\n> index 1c64c4dd16..cbed187094 100644\n> --- a/alloc.c\n> +++ b/alloc.c\n> @@ -109,7 +109,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n> \tc->object.type = OBJ_COMMIT;\n> \tc->index = alloc_commit_index(r);\n> \tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n> -\tc->generation = GENERATION_NUMBER_INFINITY;\n> }\n> \n> void *alloc_commit_node(struct repository *r)\n\nBut this change might need a more detailed write-up in the commit\nmessage.\n\nIf I understand it correctly, this is function is used by generic commit\nallocator, and given commit object may not need generation number. That\nis why the default value of GENERATION_NUMBER_INFINITY is handled by new\n\"getters\" and \"setters\", i.e. generation() and set_generation() -- which\nare called only if commit-graph is present, I think.\n\nThe generation() returns GENERATION_NUMBER_INFINITY for commits not in\ngeneration_slab, assuming that for all commits in the commit graph it\nwould be filled by commit-graph parsing -- just like init_commit_node()\nwould initialize commit->generation to this value.\n\nBecause _at() (including generation_slab_at()) extends array\nif necessary, we want all data on generation_slab to be correctly\ninitialized to GENERATION_NUMBER_INFINITY, just like init_commit_node()\nwould do it, because generation() \"getter\" cannot. The commit might be\npresent on generation_slab just because allocation is done in chunks\n(slabs).\n\n\nSecond category is semantic patch that generates the rest of changes\n(which could be adjusted manually in subsequent commits).\n\n> diff --git a/contrib/coccinelle/generation.cocci b/contrib/coccinelle/generation.cocci\n> new file mode 100644\n> index 0000000000..da13c44856\n> --- /dev/null\n> +++ b/contrib/coccinelle/generation.cocci\n> @@ -0,0 +1,12 @@\n> +@@\n> +struct commit *c;\n> +expression E;\n> +@@\n> +- c->generation = E\n> ++ set_generation(c, E)\n> +\n> +@@\n> +struct commit *c;\n> +@@\n> +- c->generation\n> ++ generation(c)\n\nI wonder if Coccinelle is able to automatically discard extra\nparentheses (the problem noticed by Stolee in his reply) with the\nfollowing chunk:\n\n +@@\n +struct commit *c;\n +@@\n +- (c)->generation\n ++ generation(c)\n\n\nThird category is all the changes that are just straight mechanical\nchanges being the result of applying the Coccinelle patch.\n\n> diff --git a/blame.c b/blame.c\n> index da7e28800e..50e6316076 100644\n> --- a/blame.c\n> +++ b/blame.c\n> @@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,\n> \tif (!bd)\n> \t\treturn 1;\n> \n> -\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n> +\tif (generation(origin->commit) == GENERATION_NUMBER_INFINITY)\n> \t\treturn 1;\n> \n> \tfilter = get_bloom_filter(r, origin->commit, 0);\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 63f419048d..9ce7d4acb1 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -120,9 +120,9 @@ static int commit_gen_cmp(const void *va, const void *vb)\n> \tconst struct commit *b = *(const struct commit **)vb;\n> \n> \t/* lower generation commits first */\n> -\tif (a->generation < b->generation)\n> +\tif (generation(a) < generation(b))\n> \t\treturn -1;\n> -\telse if (a->generation > b->generation)\n> +\telse if (generation(a) > generation(b))\n> \t\treturn 1;\n> \n> \t/* use date as a heuristic when generations are equal */\n> @@ -712,7 +712,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n> \tlex_index = pos - g->num_commits_in_base;\n> \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n> \titem->graph_pos = pos;\n> -\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n> +\tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n> }\n> \n> static inline void set_commit_tree(struct commit *c, struct tree *t)\n> @@ -754,7 +754,7 @@ static int fill_commit_in_graph(struct repository *r,\n> \tdate_low = get_be32(commit_data + g->hash_len + 12);\n> \titem->date = (timestamp_t)((date_high << 32) | date_low);\n> \n> -\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n> +\tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n> \n> \tpptr = &item->parents;\n> \n> @@ -1048,7 +1048,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n> \t\telse\n> \t\t\tpackedDate[0] = 0;\n> \n> -\t\tpackedDate[0] |= htonl((*list)->generation << 2);\n> +\t\tpackedDate[0] |= htonl(generation((*list)) << 2);\n> \n> \t\tpackedDate[1] = htonl((*list)->date);\n> \t\thashwrite(f, packedDate, 8);\n> @@ -1280,8 +1280,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\t\t\tctx->commits.nr);\n> \tfor (i = 0; i < ctx->commits.nr; i++) {\n> \t\tdisplay_progress(ctx->progress, i + 1);\n> -\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n> -\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n> +\t\tif (generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n> +\t\t generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n> \t\t\tcontinue;\n> \n> \t\tcommit_list_insert(ctx->commits.list[i], &list);\n> @@ -1292,22 +1292,23 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\tuint32_t max_generation = 0;\n> \n> \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n> -\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n> -\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n> +\t\t\t\tif (generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n> +\t\t\t\t generation(parent->item) == GENERATION_NUMBER_ZERO) {\n> \t\t\t\t\tall_parents_computed = 0;\n> \t\t\t\t\tcommit_list_insert(parent->item, &list);\n> \t\t\t\t\tbreak;\n> -\t\t\t\t} else if (parent->item->generation > max_generation) {\n> -\t\t\t\t\tmax_generation = parent->item->generation;\n> +\t\t\t\t} else if (generation(parent->item) > max_generation) {\n> +\t\t\t\t\tmax_generation = generation(parent->item);\n> \t\t\t\t}\n> \t\t\t}\n\nHere generation(parent->item) is called three times, which is probably\ncost effective to save the value to the local variable (as Stolee\nnoticed).\n\n> \n> \t\t\tif (all_parents_computed) {\n> -\t\t\t\tcurrent->generation = max_generation + 1;\n> +\t\t\t\tset_generation(current, max_generation + 1);\n> \t\t\t\tpop_commit(&list);\n> \n> -\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n> -\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n> +\t\t\t\tif (generation(current) > GENERATION_NUMBER_MAX)\n> +\t\t\t\t\tset_generation(current,\n> +\t\t\t\t\t\t GENERATION_NUMBER_MAX);\n> \t\t\t}\n> \t\t}\n> \t}\n> @@ -2314,8 +2315,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n> \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n> \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n> \n> -\t\t\tif (graph_parents->item->generation > max_generation)\n> -\t\t\t\tmax_generation = graph_parents->item->generation;\n> +\t\t\tif (generation(graph_parents->item) > max_generation)\n> +\t\t\t\tmax_generation = generation(graph_parents->item);\n> \n> \t\t\tgraph_parents = graph_parents->next;\n> \t\t\todb_parents = odb_parents->next;\n> @@ -2325,7 +2326,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n> \t\t\tgraph_report(_(\"commit-graph parent list for commit %s terminates early\"),\n> \t\t\t\t oid_to_hex(&cur_oid));\n> \n> -\t\tif (!graph_commit->generation) {\n> +\t\tif (!generation(graph_commit)) {\n> \t\t\tif (generation_zero == GENERATION_NUMBER_EXISTS)\n> \t\t\t\tgraph_report(_(\"commit-graph has generation number zero for commit %s, but non-zero elsewhere\"),\n> \t\t\t\t\t oid_to_hex(&cur_oid));\n> @@ -2345,10 +2346,10 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n> \t\tif (max_generation == GENERATION_NUMBER_MAX)\n> \t\t\tmax_generation--;\n> \n> -\t\tif (graph_commit->generation != max_generation + 1)\n> +\t\tif (generation(graph_commit) != max_generation + 1)\n> \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n> \t\t\t\t oid_to_hex(&cur_oid),\n> -\t\t\t\t graph_commit->generation,\n> +\t\t\t\t generation(graph_commit),\n> \t\t\t\t max_generation + 1);\n> \n> \t\tif (graph_commit->date != odb_commit->date)\n> diff --git a/commit-reach.c b/commit-reach.c\n> index 4ca7e706a1..77c980054a 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -59,13 +59,13 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n> \t\tstruct commit_list *parents;\n> \t\tint flags;\n> \n> -\t\tif (min_generation && commit->generation > last_gen)\n> +\t\tif (min_generation && generation(commit) > last_gen)\n> \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n> -\t\t\t commit->generation, last_gen,\n> +\t\t\t generation(commit), last_gen,\n> \t\t\t oid_to_hex(&commit->object.oid));\n> -\t\tlast_gen = commit->generation;\n> +\t\tlast_gen = generation(commit);\n> \n> -\t\tif (commit->generation < min_generation)\n> +\t\tif (generation(commit) < min_generation)\n> \t\t\tbreak;\n\nHere generation(commit) is called three times (two times in the\nexceptional case).\n\n> \n> \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n> @@ -176,7 +176,7 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n> \t\trepo_parse_commit(r, array[i]);\n> \tfor (i = 0; i < cnt; i++) {\n> \t\tstruct commit_list *common;\n> -\t\tuint32_t min_generation = array[i]->generation;\n> +\t\tuint32_t min_generation = generation(array[i]);\n> \n> \t\tif (redundant[i])\n> \t\t\tcontinue;\n> @@ -186,8 +186,8 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n> \t\t\tfilled_index[filled] = j;\n> \t\t\twork[filled++] = array[j];\n> \n> -\t\t\tif (array[j]->generation < min_generation)\n> -\t\t\t\tmin_generation = array[j]->generation;\n> +\t\t\tif (generation(array[j]) < min_generation)\n> +\t\t\t\tmin_generation = generation(array[j]);\n> \t\t}\n> \t\tcommon = paint_down_to_common(r, array[i], filled,\n> \t\t\t\t\t work, min_generation);\n> @@ -323,16 +323,16 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n> \tfor (i = 0; i < nr_reference; i++) {\n> \t\tif (repo_parse_commit(r, reference[i]))\n> \t\t\treturn ret;\n> -\t\tif (reference[i]->generation < min_generation)\n> -\t\t\tmin_generation = reference[i]->generation;\n> +\t\tif (generation(reference[i]) < min_generation)\n> +\t\t\tmin_generation = generation(reference[i]);\n> \t}\n> \n> -\tif (commit->generation > min_generation)\n> +\tif (generation(commit) > min_generation)\n> \t\treturn ret;\n> \n> \tbases = paint_down_to_common(r, commit,\n> \t\t\t\t nr_reference, reference,\n> -\t\t\t\t commit->generation);\n> +\t\t\t\t generation(commit));\n> \tif (commit->object.flags & PARENT2)\n> \t\tret = 1;\n> \tclear_commit_marks(commit, all_flags);\n> @@ -467,7 +467,7 @@ static enum contains_result contains_test(struct commit *candidate,\n> \t/* Otherwise, we don't know; prepare to recurse */\n> \tparse_commit_or_die(candidate);\n> \n> -\tif (candidate->generation < cutoff)\n> +\tif (generation(candidate) < cutoff)\n> \t\treturn CONTAINS_NO;\n> \n> \treturn CONTAINS_UNKNOWN;\n> @@ -492,8 +492,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n> \tfor (p = want; p; p = p->next) {\n> \t\tstruct commit *c = p->item;\n> \t\tload_commit_graph_info(the_repository, c);\n> -\t\tif (c->generation < cutoff)\n> -\t\t\tcutoff = c->generation;\n> +\t\tif (generation(c) < cutoff)\n> +\t\t\tcutoff = generation(c);\n> \t}\n> \n> \tresult = contains_test(candidate, want, cache, cutoff);\n> @@ -544,9 +544,9 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n> \tconst struct commit *a = *(const struct commit * const *)_a;\n> \tconst struct commit *b = *(const struct commit * const *)_b;\n> \n> -\tif (a->generation < b->generation)\n> +\tif (generation(a) < generation(b))\n> \t\treturn -1;\n> -\tif (a->generation > b->generation)\n> +\tif (generation(a) > generation(b))\n> \t\treturn 1;\n> \treturn 0;\n> }\n> @@ -585,7 +585,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> \n> \t\tlist[nr_commits] = (struct commit *)from_one;\n> \t\tif (parse_commit(list[nr_commits]) ||\n> -\t\t list[nr_commits]->generation < min_generation) {\n> +\t\t generation(list[nr_commits]) < min_generation) {\n> \t\t\tresult = 0;\n> \t\t\tgoto cleanup;\n> \t\t}\n> @@ -621,7 +621,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n> \n> \t\t\t\t\tif (parse_commit(parent->item) ||\n> \t\t\t\t\t parent->item->date < min_commit_date ||\n> -\t\t\t\t\t parent->item->generation < min_generation)\n> +\t\t\t\t\t generation(parent->item) < min_generation)\n> \t\t\t\t\t\tcontinue;\n> \n> \t\t\t\t\tcommit_list_insert(parent->item, &stack);\n> @@ -665,8 +665,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> \t\t\tif (from_iter->item->date < min_commit_date)\n> \t\t\t\tmin_commit_date = from_iter->item->date;\n> \n> -\t\t\tif (from_iter->item->generation < min_generation)\n> -\t\t\t\tmin_generation = from_iter->item->generation;\n> +\t\t\tif (generation(from_iter->item) < min_generation)\n> +\t\t\t\tmin_generation = generation(from_iter->item);\n> \t\t}\n> \n> \t\tfrom_iter = from_iter->next;\n> @@ -677,8 +677,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n> \t\t\tif (to_iter->item->date < min_commit_date)\n> \t\t\t\tmin_commit_date = to_iter->item->date;\n> \n> -\t\t\tif (to_iter->item->generation < min_generation)\n> -\t\t\t\tmin_generation = to_iter->item->generation;\n> +\t\t\tif (generation(to_iter->item) < min_generation)\n> +\t\t\t\tmin_generation = generation(to_iter->item);\n> \t\t}\n> \n> \t\tto_iter->item->object.flags |= PARENT2;\n> @@ -721,8 +721,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> \t\tstruct commit *c = *item;\n> \n> \t\tparse_commit(c);\n> -\t\tif (c->generation < min_generation)\n> -\t\t\tmin_generation = c->generation;\n> +\t\tif (generation(c) < min_generation)\n> +\t\t\tmin_generation = generation(c);\n> \n> \t\tif (!(c->object.flags & PARENT1)) {\n> \t\t\tc->object.flags |= PARENT1;\n> @@ -755,7 +755,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n> \n> \t\t\tparse_commit(p);\n> \n> -\t\t\tif (p->generation < min_generation)\n> +\t\t\tif (generation(p) < min_generation)\n> \t\t\t\tcontinue;\n> \n> \t\t\tif (p->object.flags & PARENT2)\n> diff --git a/commit.c b/commit.c\n> index 87686a7055..8dad0f8446 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void\n> \tconst struct commit *a = a_, *b = b_;\n> \n> \t/* newer commits first */\n> -\tif (a->generation < b->generation)\n> +\tif (generation(a) < generation(b))\n> \t\treturn 1;\n> -\telse if (a->generation > b->generation)\n> +\telse if (generation(a) > generation(b))\n> \t\treturn -1;\n> \n> \t/* use date as a heuristic when generations are equal */\n> diff --git a/revision.c b/revision.c\n> index 60cca8c0b9..d76382007c 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -720,7 +720,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n> \tif (!revs->repo->objects->commit_graph)\n> \t\treturn -1;\n> \n> -\tif (commit->generation == GENERATION_NUMBER_INFINITY)\n> +\tif (generation(commit) == GENERATION_NUMBER_INFINITY)\n> \t\treturn -1;\n> \n> \tfilter = get_bloom_filter(revs->repo, commit, 0);\n> @@ -3314,7 +3314,7 @@ static void explore_to_depth(struct rev_info *revs,\n> \tstruct topo_walk_info *info = revs->topo_walk_info;\n> \tstruct commit *c;\n> \twhile ((c = prio_queue_peek(&info->explore_queue)) &&\n> -\t c->generation >= gen_cutoff)\n> +\t generation(c) >= gen_cutoff)\n> \t\texplore_walk_step(revs);\n> }\n> \n> @@ -3330,7 +3330,7 @@ static void indegree_walk_step(struct rev_info *revs)\n> \tif (parse_commit_gently(c, 1) < 0)\n> \t\treturn;\n> \n> -\texplore_to_depth(revs, c->generation);\n> +\texplore_to_depth(revs, generation(c));\n> \n> \tfor (p = c->parents; p; p = p->next) {\n> \t\tstruct commit *parent = p->item;\n> @@ -3354,7 +3354,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs,\n> \tstruct topo_walk_info *info = revs->topo_walk_info;\n> \tstruct commit *c;\n> \twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n> -\t c->generation >= gen_cutoff)\n> +\t generation(c) >= gen_cutoff)\n> \t\tindegree_walk_step(revs);\n> }\n> \n> @@ -3414,8 +3414,8 @@ static void init_topo_walk(struct rev_info *revs)\n> \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n> \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n> \n> -\t\tif (c->generation < info->min_generation)\n> -\t\t\tinfo->min_generation = c->generation;\n> +\t\tif (generation(c) < info->min_generation)\n> +\t\t\tinfo->min_generation = generation(c);\n> \n> \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n> \n> @@ -3473,8 +3473,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n> \t\tif (parse_commit_gently(parent, 1) < 0)\n> \t\t\tcontinue;\n> \n> -\t\tif (parent->generation < info->min_generation) {\n> -\t\t\tinfo->min_generation = parent->generation;\n> +\t\tif (generation(parent) < info->min_generation) {\n> +\t\t\tinfo->min_generation = generation(parent);\n> \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n> \t\t}\n\nBest,\n--\nJakub Narębski\n"},{"id":"399242","messageId":"85zh9ft6qi.fsf@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-4-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch 3/3] commit: convert commit->graph_pos to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-07T12:12:21Z","receivedAt":"2020-06-07T12:15:43Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> The member graph_pos refers to the integer position used to identify a\n> commit in commit-graph files. However, graph_pos is not useful in other\n> contexts and bloats the struct.\n>\n> Let's move it to a commit-slab and shrink the struct by four bytes.\n>\n> Existing references to graph_pos are replaced using\n> 'contrib/coccinelle/graph_pos.cocci'.\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> alloc.c | 1 -\n> bloom.c | 6 ++--\n> commit-graph.c | 50 +++++++++++++++++++++++-------\n> commit-graph.h | 3 ++\n> commit.c | 2 +-\n> commit.h | 2 --\n> contrib/coccinelle/graph_pos.cocci | 12 +++++++\n> 7 files changed, 58 insertions(+), 18 deletions(-)\n> create mode 100644 contrib/coccinelle/graph_pos.cocci\n\nI have reordered the chunks to make it easier to review.\n\n> diff --git a/commit.h b/commit.h\n> index 01e1c4c3eb..0b10464a10 100644\n> --- a/commit.h\n> +++ b/commit.h\n> @@ -10,8 +10,6 @@\n> #include \"pretty.h\"\n> #include \"commit-slab.h\"\n> \n> -#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n> -\n> struct commit_list {\n> \tstruct commit *item;\n> \tstruct commit_list *next;\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 653bd041ad..3cb59ba336 100644\n> --- a/commit-graph.h\n> +++ b/commit-graph.h\n> @@ -8,6 +8,7 @@\n> #include \"object-store.h\"\n> #include \"oidset.h\"\n> \n> +#define COMMIT_NOT_FROM_GRAPH 0xFFFFFFFF\n> #define GENERATION_NUMBER_INFINITY 0xFFFFFFFF\n> #define GENERATION_NUMBER_MAX 0x3FFFFFFF\n> #define GENERATION_NUMBER_ZERO 0\n\nThose two chunks move COMMIT_NOT_FROM_GRAPH from commit.h to\ncommit-graph.h, because it is no longer needed in init_commit_node()\nfrom alloc.c. On the other hand the remaining commit-graph #define-s\nwere moved in first commit in series.\n\n\nWhat I DO NOT SEE in this commit is actual *removal* of `graph_pos`\nfield from the `struct commit`, i.e.:\n\n diff --git a/commit.h b/commit.h\n index cc610400d5..01e1c4c3eb 100644\n --- a/commit.h\n +++ b/commit.h\n @@ -34,6 +34,5 @@ struct commit {\n \t */\n \tstruct tree *maybe_tree;\n -\tuint32_t graph_pos;\n \tunsigned int index;\n };\n \n\n\n> diff --git a/alloc.c b/alloc.c\n> index cbed187094..f37fb3b8b6 100644\n> --- a/alloc.c\n> +++ b/alloc.c\n> @@ -108,7 +108,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n> {\n> \tc->object.type = OBJ_COMMIT;\n> \tc->index = alloc_commit_index(r);\n> -\tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n> }\n>\n> void *alloc_commit_node(struct repository *r)\n\nThis removes commit->graph_pos initialization from init_commit_node(),\nand thus from alloc_commit_node(); the handling of COMMIT_NOT_FROM_GRAPH\nis moved to setter and getter \"methods\", see below.\n\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 9ce7d4acb1..7ff460b442 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -87,6 +87,34 @@ static int commit_pos_cmp(const void *va, const void *vb)\n> \t commit_pos_at(&commit_pos, b);\n> }\n> \n> +define_commit_slab(graph_pos_slab, uint32_t);\n> +static struct graph_pos_slab graph_pos_slab = COMMIT_SLAB_INIT(1, graph_pos_slab);\n> +\n> +uint32_t graph_pos(const struct commit *c)\n> +{\n> +\tuint32_t *pos = graph_pos_slab_peek(&graph_pos_slab, c);\n> +\n> +\treturn pos ? *pos : COMMIT_NOT_FROM_GRAPH;\n> +}\n> +\n> +static void set_graph_pos(const struct commit *c, const uint32_t position)\n> +{\n> +\tunsigned int i = graph_pos_slab.slab_count;\n> +\tuint32_t *pos = graph_pos_slab_at(&graph_pos_slab, c);\n> +\n> +\t/*\n> +\t * commit-slab initializes with zero, overwrite this with\n> +\t * COMMIT_NOT_FROM_GRAPH\n> +\t */\n> +\tfor (; i < graph_pos_slab.slab_count; ++i)\n> +\t{\n> +\t\tmemset(graph_pos_slab.slab[i], COMMIT_NOT_FROM_GRAPH,\n> +\t\t graph_pos_slab.slab_size * sizeof(uint32_t));\n> +\t}\n> +\n> +\t*pos = position;\n> +}\n> +\n> define_commit_slab(generation_slab, uint32_t);\n> static struct generation_slab generation_slab = COMMIT_SLAB_INIT(1, generation_slab);\n> \n[...]\n> @@ -142,4 +143,6 @@ void free_commit_graph(struct commit_graph *);\n> void disable_commit_graph(struct repository *r);\n> \n> uint32_t generation(const struct commit *c);\n> +\n> +uint32_t graph_pos(const struct commit *c);\n> #endif\n\n\nI wonder why those helper functions: graph_pos() and set_graph_pos()\nwere not introduced in the 1st patch of this series, together with\ngeneration() and set_generation().\n\nThe same comments as for previous patch apply: if graph_pos was not\nexplicitely set, we want for it to be COMMIT_NOT_FROM_GRAPH (like\ninit_commit_node() did before this change). If it is not on\ncommit-slab, it is not set -- this is handled by graph_pos() function.\nHowever we allocate memory on slab in chunks, and set_graph_pos()\nensures that those extra allocated `graph_pos` values on commit-slab are\nproperly initialized to COMMIT_NOT_FROM_GRAPH, like init_commit_node()\ndid.\n\n\nNote that we always have COMMIT_NOT_FROM_GRAPH for `graph_pos` if and\nonly if there is GENERATION_NUMBER_INFINITY for `generation`, so perhaps\nputting those two together in `struct commit_graph_info` would make\nsense. But whether doing more work in \"setter\" set_*() functions or\ndoing extra conditional in \"getter\" *() would give better performance\nneeds (micro-)benchmarking.\n\n\n> diff --git a/contrib/coccinelle/graph_pos.cocci b/contrib/coccinelle/graph_pos.cocci\n> new file mode 100644\n> index 0000000000..0929164bdf\n> --- /dev/null\n> +++ b/contrib/coccinelle/graph_pos.cocci\n> @@ -0,0 +1,12 @@\n> +@@\n> +struct commit *c;\n> +expression E;\n> +@@\n> +- c->graph_pos = E\n> ++ set_graph_pos(c, E)\n> +\n> +@@\n> +struct commit *c;\n> +@@\n> +- c->graph_pos\n> ++ graph_pos(c)\n\nThis is semantic patch that generates the rest of changes. (If any of\nthose needs manual improvement, it is better left for a separate \"manual\nfixup\" patch, in my opinion.)\n\n> diff --git a/bloom.c b/bloom.c\n> index 9b86aa3f59..5bee5bb0c1 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n> {\n> \tuint32_t lex_pos, start_index, end_index;\n> \n> -\twhile (c->graph_pos < g->num_commits_in_base)\n> +\twhile (graph_pos(c) < g->num_commits_in_base)\n> \t\tg = g->base_graph;\n> \n> \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n> \tif (!g->chunk_bloom_indexes)\n> \t\treturn 0;\n> \n> -\tlex_pos = c->graph_pos - g->num_commits_in_base;\n> +\tlex_pos = graph_pos(c) - g->num_commits_in_base;\n> \n> \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n>\n\nHere graph_pos(c) is used twice.\n\nIt probably needs to be checked (with benchmark) if it matters.\n\n\n> @@ -188,7 +188,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \n> \tif (!filter->data) {\n> \t\tload_commit_graph_info(r, c);\n> -\t\tif (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&\n> +\t\tif (graph_pos(c) != COMMIT_NOT_FROM_GRAPH &&\n> \t\t\tr->objects->commit_graph->chunk_bloom_indexes) {\n> \t\t\tif (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))\n> \t\t\t\treturn filter;\n\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 9ce7d4acb1..7ff460b442 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -697,7 +725,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n> \tc = lookup_commit(r, &oid);\n> \tif (!c)\n> \t\tdie(_(\"could not find commit %s\"), oid_to_hex(&oid));\n> -\tc->graph_pos = pos;\n> +\tset_graph_pos(c, pos);\n> \treturn &commit_list_insert(c, pptr)->next;\n> }\n> \n> @@ -711,7 +739,7 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n> \n> \tlex_index = pos - g->num_commits_in_base;\n> \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n> -\titem->graph_pos = pos;\n> +\tset_graph_pos(item, pos);\n> \tset_generation(item, get_be32(commit_data + g->hash_len + 8) >> 2);\n> }\n> \n> @@ -741,7 +769,7 @@ static int fill_commit_in_graph(struct repository *r,\n> \t * Store the \"full\" position, but then use the\n> \t * \"local\" position for the rest of the calculation.\n> \t */\n> -\titem->graph_pos = pos;\n> +\tset_graph_pos(item, pos);\n> \tlex_index = pos - g->num_commits_in_base;\n> \n> \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n\n> @@ -786,8 +814,8 @@ static int fill_commit_in_graph(struct repository *r,\n> \n> static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n> {\n> -\tif (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {\n> -\t\t*pos = item->graph_pos;\n> +\tif (graph_pos(item) != COMMIT_NOT_FROM_GRAPH) {\n> +\t\t*pos = graph_pos(item);\n> \t\treturn 1;\n\nHere graph_pos(item) is used twice.\n\n> \t} else {\n> \t\tstruct commit_graph *cur_g = g;\n> @@ -843,11 +871,11 @@ static struct tree *load_tree_for_commit(struct repository *r,\n> \tstruct object_id oid;\n> \tconst unsigned char *commit_data;\n> \n> -\twhile (c->graph_pos < g->num_commits_in_base)\n> +\twhile (graph_pos(c) < g->num_commits_in_base)\n> \t\tg = g->base_graph;\n> \n> \tcommit_data = g->chunk_commit_data +\n> -\t\t\tGRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);\n> +\t\t\tGRAPH_DATA_WIDTH * (graph_pos(c) - g->num_commits_in_base);\n> \n> \thashcpy(oid.hash, commit_data);\n> \tset_commit_tree(c, lookup_tree(r, &oid));\n\nHere graph_pos(c) is used twice.\n\n> @@ -861,7 +889,7 @@ static struct tree *get_commit_tree_in_graph_one(struct repository *r,\n> {\n> \tif (c->maybe_tree)\n> \t\treturn c->maybe_tree;\n> -\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n> +\tif (graph_pos(c) == COMMIT_NOT_FROM_GRAPH)\n> \t\tBUG(\"get_commit_tree_in_graph_one called from non-commit-graph commit\");\n> \n> \treturn load_tree_for_commit(r, g, (struct commit *)c);\n> @@ -1247,7 +1275,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n> \t\t\tcontinue;\n> \t\tif (ctx->split) {\n> \t\t\tif ((!parse_commit(commit) &&\n> -\t\t\t commit->graph_pos == COMMIT_NOT_FROM_GRAPH) ||\n> +\t\t\t graph_pos(commit) == COMMIT_NOT_FROM_GRAPH) ||\n> \t\t\t flags == COMMIT_GRAPH_SPLIT_REPLACE)\n> \t\t\t\tadd_missing_parents(ctx, commit);\n> \t\t} else if (!parse_commit_no_graph(commit))\n> @@ -1493,7 +1521,7 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n> \t\t\tif (ctx->split) {\n> \t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n> \n> -\t\t\t\tif (!c || c->graph_pos != COMMIT_NOT_FROM_GRAPH)\n> +\t\t\t\tif (!c || graph_pos(c) != COMMIT_NOT_FROM_GRAPH)\n> \t\t\t\t\tcontinue;\n> \t\t\t}\n> \n> @@ -1527,7 +1555,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n> \t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n> \n> \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n> -\t\t ctx->commits.list[ctx->commits.nr]->graph_pos != COMMIT_NOT_FROM_GRAPH)\n> +\t\t graph_pos(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n> \t\t\tcontinue;\n> \n> \t\tif (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)\n> diff --git a/commit.c b/commit.c\n> index 8dad0f8446..da6de08b2b 100644\n> --- a/commit.c\n> +++ b/commit.c\n> @@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r,\n> \tif (commit->maybe_tree || !commit->object.parsed)\n> \t\treturn commit->maybe_tree;\n> \n> -\tif (commit->graph_pos != COMMIT_NOT_FROM_GRAPH)\n> +\tif (graph_pos(commit) != COMMIT_NOT_FROM_GRAPH)\n> \t\treturn get_commit_tree_in_graph(r, commit);\n> \n> \treturn NULL;\n\nBest,\n-- \nJakub Narębski\n"},{"id":"399255","messageId":"20200607193237.699335-1-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v2 0/4] Move generation, graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-07T19:32:33Z","receivedAt":"2020-06-07T19:34:33Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct commit is used in many contexts. However, members\n`generation` and `graph_pos` are only used for commit graph related\noperations and otherwise waste memory.\n\nThis wastage would have been more pronounced as we transition to\ngeneration number v2, which uses 64-bite generation number instead of\ncurrent 32-bits.\n\nAbhishek Kumar (4):\n commit-graph: introduce commit_graph_data_slab\n commit: move members graph_pos, generation to a slab\n commit-graph: use generation directly when writing commit-graph\n commit-graph: minimize commit_graph_data_slab access\n\n alloc.c | 2 -\n blame.c | 2 +-\n bloom.c | 7 +-\n commit-graph.c | 127 ++++++++++++++++++++++++--------\n commit-graph.h | 10 +++\n commit-reach.c | 69 ++++++++++-------\n commit.c | 8 +-\n contrib/coccinelle/commit.cocci | 18 +++++\n revision.c | 20 +++--\n 9 files changed, 190 insertions(+), 73 deletions(-)\n\n-- \n2.27.0\n\nThanks to Dr. Stolee, Dr. Narebski and Junio for their excellent\nsuggestions.\n\nChanges in v2:\n- Introduce struct commit_graph_data.\n- Merge `graph_pos`, `generation` slabs into a single,\n `commit_graph_data` slab.\n- Use graph position for an intermediate check for generation, saving\n the cost of initializing generation numbers.\n- Add an follow-up patch caching results of slab access in local\n variables.\n- Move coccinelle transformation to commit.coccinelle instead of\n creating new scripts.\n- Elaborate on removing default values from init_commit_node().\n- Revert moving macro constants (e.g. COMMIT_NOT_FROM_GRAPH,\n GENERATION_NUMBER_ZERO) from commit.h to commit-graph.h\n\nAbout the failing diff-submodule related tests, I came up with a\nplausible explanation but could be wrong on this:\n\nCommit slabs rely on uniqueness of commit->index to access data. But\nsubmodules are repositories on their own, alloc_commit_index(), which\nrelies on repository->parsed_objects->commit_count no longer returns\nunique values.\n\nA commit belong to super repo and another belonging to submodule might\nhave the same index but different generation and graph positions.\n\nThis could be fixed by defining commit index as maximum of commit index\nof all repositories + 1 but I have no idea how that would impact other\ncode.\n\nThoughts on this?\n\nRegards\nAbhishek\n"},{"id":"399256","messageId":"20200607193237.699335-2-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v2 1/4] commit-graph: introduce commit_graph_data_slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-07T19:32:34Z","receivedAt":"2020-06-07T19:34:37Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct commit is used in many contexts. However, members\n`generation` and `graph_pos` are only used for commit-graph related\noperations and otherwise waste memory.\n\nAs they are often accessed together, let's introduce struct\ncommit_graph_data and move them to a commit_graph_data slab.\n\nSigned-off-by: Abhishek Kumar \n---\n commit-graph.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++\n commit-graph.h | 10 ++++++++++\n 2 files changed, 59 insertions(+)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex e3420ddcbf..7d887a6a2c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -87,6 +87,55 @@ static int commit_pos_cmp(const void *va, const void *vb)\n \t commit_pos_at(&commit_pos, b);\n }\n \n+define_commit_slab(commit_graph_data_slab, struct commit_graph_data);\n+static struct commit_graph_data_slab commit_graph_data_slab =\n+\tCOMMIT_SLAB_INIT(1, commit_graph_data_slab);\n+\n+uint32_t commit_graph_position(const struct commit *c)\n+{\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n+\n+\treturn data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;\n+}\n+\n+uint32_t commit_graph_generation(const struct commit *c)\n+{\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n+\n+\tif (!data)\n+\t\treturn GENERATION_NUMBER_INFINITY;\n+\tif (data->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\treturn GENERATION_NUMBER_INFINITY;\n+\n+\treturn data->generation;\n+}\n+\n+static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\n+{\n+\tuint32_t i = commit_graph_data_slab.slab_count, j;\n+\tuint32_t slab_size = commit_graph_data_slab.slab_size;\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_at(&commit_graph_data_slab, c);\n+\n+\t/*\n+\t * commit-slab initializes elements with zero, overwrite this with\n+\t * COMMIT_NOT_FROM_GRAPH for graph_pos.\n+\t *\n+\t * We avoid the cost of initializing `generation` as generation\n+\t * number would be GENERATION_NUMBER_INFINITY if graph position\n+\t * is COMMIT_NOT_FROM_GRAPH.\n+\t */\n+\tfor (; i < commit_graph_data_slab.slab_count; i++) {\n+\t\tfor (j = 0; j < slab_size; j++) {\n+\t\t\tcommit_graph_data_slab.slab[i][j].graph_pos = COMMIT_NOT_FROM_GRAPH;\n+\t\t}\n+\t}\n+\n+\treturn data;\n+}\n+\n static int commit_gen_cmp(const void *va, const void *vb)\n {\n \tconst struct commit *a = *(const struct commit **)va;\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 4212766a4f..9d22f98f44 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -137,4 +137,14 @@ void free_commit_graph(struct commit_graph *);\n */\n void disable_commit_graph(struct repository *r);\n \n+struct commit_graph_data {\n+\tuint32_t graph_pos;\n+\tuint32_t generation;\n+};\n+\n+/* \n+ * Commits should be parsed before accessing generation, graph positions.\n+ */\n+uint32_t commit_graph_generation(const struct commit *);\n+uint32_t commit_graph_position(const struct commit *);\n #endif\n-- \n2.27.0\n\n"},{"id":"399257","messageId":"20200607193237.699335-3-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v2 2/4] commit: move members graph_pos, generation to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-07T19:32:35Z","receivedAt":"2020-06-07T19:34:43Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"We remove members `graph_pos` and `generation` from the struct commit.\nThe default assignments in init_commit_node() are no longer valid,\nwhich is fine as the slab helpers return appropriate default values and\nthe assignments are removed.\n\nWe will replace existing use of commit->generation and commit->graph_pos\nby commit_graph_data slab helpers using\n`contrib/coccinelle/commit.cocci'.\n\nSigned-off-by: Abhishek Kumar \n---\n alloc.c | 2 --\n blame.c | 2 +-\n bloom.c | 6 ++--\n commit-graph.c | 60 ++++++++++++++++-----------------\n commit-graph.h | 2 +-\n commit-reach.c | 50 +++++++++++++--------------\n commit.c | 6 ++--\n contrib/coccinelle/commit.cocci | 18 ++++++++++\n revision.c | 16 ++++-----\n 9 files changed, 89 insertions(+), 73 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 1c64c4dd16..f37fb3b8b6 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -108,8 +108,6 @@ void init_commit_node(struct repository *r, struct commit *c)\n {\n \tc->object.type = OBJ_COMMIT;\n \tc->index = alloc_commit_index(r);\n-\tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n-\tc->generation = GENERATION_NUMBER_INFINITY;\n }\n \n void *alloc_commit_node(struct repository *r)\ndiff --git a/blame.c b/blame.c\nindex da7e28800e..82fa16d658 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,\n \tif (!bd)\n \t\treturn 1;\n \n-\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn 1;\n \n \tfilter = get_bloom_filter(r, origin->commit, 0);\ndiff --git a/bloom.c b/bloom.c\nindex 9b86aa3f59..df62e3763d 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n {\n \tuint32_t lex_pos, start_index, end_index;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (commit_graph_position(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n \tif (!g->chunk_bloom_indexes)\n \t\treturn 0;\n \n-\tlex_pos = c->graph_pos - g->num_commits_in_base;\n+\tlex_pos = commit_graph_position(c) - g->num_commits_in_base;\n \n \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n \n@@ -188,7 +188,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \n \tif (!filter->data) {\n \t\tload_commit_graph_info(r, c);\n-\t\tif (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&\n+\t\tif (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&\n \t\t\tr->objects->commit_graph->chunk_bloom_indexes) {\n \t\t\tif (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))\n \t\t\t\treturn filter;\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 7d887a6a2c..f7cca4def4 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -142,9 +142,9 @@ static int commit_gen_cmp(const void *va, const void *vb)\n \tconst struct commit *b = *(const struct commit **)vb;\n \n \t/* lower generation commits first */\n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn -1;\n-\telse if (a->generation > b->generation)\n+\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn 1;\n \n \t/* use date as a heuristic when generations are equal */\n@@ -719,7 +719,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n \tc = lookup_commit(r, &oid);\n \tif (!c)\n \t\tdie(_(\"could not find commit %s\"), oid_to_hex(&oid));\n-\tc->graph_pos = pos;\n+\tcommit_graph_data_at(c)->graph_pos = pos;\n \treturn &commit_list_insert(c, pptr)->next;\n }\n \n@@ -733,8 +733,8 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n-\titem->graph_pos = pos;\n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tcommit_graph_data_at(item)->graph_pos = pos;\n+\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n }\n \n static inline void set_commit_tree(struct commit *c, struct tree *t)\n@@ -763,7 +763,7 @@ static int fill_commit_in_graph(struct repository *r,\n \t * Store the \"full\" position, but then use the\n \t * \"local\" position for the rest of the calculation.\n \t */\n-\titem->graph_pos = pos;\n+\tcommit_graph_data_at(item)->graph_pos = pos;\n \tlex_index = pos - g->num_commits_in_base;\n \n \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n@@ -776,7 +776,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n \titem->date = (timestamp_t)((date_high << 32) | date_low);\n \n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n \n \tpptr = &item->parents;\n \n@@ -808,8 +808,8 @@ static int fill_commit_in_graph(struct repository *r,\n \n static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n {\n-\tif (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {\n-\t\t*pos = item->graph_pos;\n+\tif (commit_graph_position(item) != COMMIT_NOT_FROM_GRAPH) {\n+\t\t*pos = commit_graph_position(item);\n \t\treturn 1;\n \t} else {\n \t\tstruct commit_graph *cur_g = g;\n@@ -865,11 +865,11 @@ static struct tree *load_tree_for_commit(struct repository *r,\n \tstruct object_id oid;\n \tconst unsigned char *commit_data;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (commit_graph_position(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \tcommit_data = g->chunk_commit_data +\n-\t\t\tGRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);\n+\t\t\tGRAPH_DATA_WIDTH * (commit_graph_position(c) - g->num_commits_in_base);\n \n \thashcpy(oid.hash, commit_data);\n \tset_commit_tree(c, lookup_tree(r, &oid));\n@@ -883,7 +883,7 @@ static struct tree *get_commit_tree_in_graph_one(struct repository *r,\n {\n \tif (c->maybe_tree)\n \t\treturn c->maybe_tree;\n-\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\tif (commit_graph_position(c) == COMMIT_NOT_FROM_GRAPH)\n \t\tBUG(\"get_commit_tree_in_graph_one called from non-commit-graph commit\");\n \n \treturn load_tree_for_commit(r, g, (struct commit *)c);\n@@ -1070,7 +1070,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\telse\n \t\t\tpackedDate[0] = 0;\n \n-\t\tpackedDate[0] |= htonl((*list)->generation << 2);\n+\t\tpackedDate[0] |= htonl(commit_graph_generation((*list)) << 2);\n \n \t\tpackedDate[1] = htonl((*list)->date);\n \t\thashwrite(f, packedDate, 8);\n@@ -1269,7 +1269,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\tcontinue;\n \t\tif (ctx->split) {\n \t\t\tif ((!parse_commit(commit) &&\n-\t\t\t commit->graph_pos == COMMIT_NOT_FROM_GRAPH) ||\n+\t\t\t commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||\n \t\t\t flags == COMMIT_GRAPH_SPLIT_REPLACE)\n \t\t\t\tadd_missing_parents(ctx, commit);\n \t\t} else if (!parse_commit_no_graph(commit))\n@@ -1302,8 +1302,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\t\t\tctx->commits.nr);\n \tfor (i = 0; i < ctx->commits.nr; i++) {\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n-\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n+\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n+\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n \t\t\tcontinue;\n \n \t\tcommit_list_insert(ctx->commits.list[i], &list);\n@@ -1314,22 +1314,22 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\tuint32_t max_generation = 0;\n \n \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n-\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n-\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n+\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n \t\t\t\t\tall_parents_computed = 0;\n \t\t\t\t\tcommit_list_insert(parent->item, &list);\n \t\t\t\t\tbreak;\n-\t\t\t\t} else if (parent->item->generation > max_generation) {\n-\t\t\t\t\tmax_generation = parent->item->generation;\n+\t\t\t\t} else if (commit_graph_generation(parent->item) > max_generation) {\n+\t\t\t\t\tmax_generation = commit_graph_generation(parent->item);\n \t\t\t\t}\n \t\t\t}\n \n \t\t\tif (all_parents_computed) {\n-\t\t\t\tcurrent->generation = max_generation + 1;\n+\t\t\t\tcommit_graph_data_at(current)->generation = max_generation + 1;\n \t\t\t\tpop_commit(&list);\n \n-\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n-\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n+\t\t\t\tif (commit_graph_generation(current) > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tcommit_graph_data_at(current)->generation = GENERATION_NUMBER_MAX;\n \t\t\t}\n \t\t}\n \t}\n@@ -1514,7 +1514,7 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n \t\t\tif (ctx->split) {\n \t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n-\t\t\t\tif (!c || c->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t\t\tif (!c || commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)\n \t\t\t\t\tcontinue;\n \t\t\t}\n \n@@ -1548,7 +1548,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n-\t\t ctx->commits.list[ctx->commits.nr]->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n \t\t\tcontinue;\n \n \t\tif (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)\n@@ -2336,8 +2336,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n \n-\t\t\tif (graph_parents->item->generation > max_generation)\n-\t\t\t\tmax_generation = graph_parents->item->generation;\n+\t\t\tif (commit_graph_generation(graph_parents->item) > max_generation)\n+\t\t\t\tmax_generation = commit_graph_generation(graph_parents->item);\n \n \t\t\tgraph_parents = graph_parents->next;\n \t\t\todb_parents = odb_parents->next;\n@@ -2347,7 +2347,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\tgraph_report(_(\"commit-graph parent list for commit %s terminates early\"),\n \t\t\t\t oid_to_hex(&cur_oid));\n \n-\t\tif (!graph_commit->generation) {\n+\t\tif (!commit_graph_generation(graph_commit)) {\n \t\t\tif (generation_zero == GENERATION_NUMBER_EXISTS)\n \t\t\t\tgraph_report(_(\"commit-graph has generation number zero for commit %s, but non-zero elsewhere\"),\n \t\t\t\t\t oid_to_hex(&cur_oid));\n@@ -2367,10 +2367,10 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tif (max_generation == GENERATION_NUMBER_MAX)\n \t\t\tmax_generation--;\n \n-\t\tif (graph_commit->generation != max_generation + 1)\n+\t\tif (commit_graph_generation(graph_commit) != max_generation + 1)\n \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n \t\t\t\t oid_to_hex(&cur_oid),\n-\t\t\t\t graph_commit->generation,\n+\t\t\t\t commit_graph_generation(graph_commit),\n \t\t\t\t max_generation + 1);\n \n \t\tif (graph_commit->date != odb_commit->date)\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 9d22f98f44..2d1fecf481 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -142,7 +142,7 @@ struct commit_graph_data {\n \tuint32_t generation;\n };\n \n-/* \n+/*\n * Commits should be parsed before accessing generation, graph positions.\n */\n uint32_t commit_graph_generation(const struct commit *);\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 4ca7e706a1..3b2f863f5f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -59,13 +59,13 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \n-\t\tif (min_generation && commit->generation > last_gen)\n+\t\tif (min_generation && commit_graph_generation(commit) > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit->generation, last_gen,\n+\t\t\t commit_graph_generation(commit), last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit->generation;\n+\t\tlast_gen = commit_graph_generation(commit);\n \n-\t\tif (commit->generation < min_generation)\n+\t\tif (commit_graph_generation(commit) < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -176,7 +176,7 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\trepo_parse_commit(r, array[i]);\n \tfor (i = 0; i < cnt; i++) {\n \t\tstruct commit_list *common;\n-\t\tuint32_t min_generation = array[i]->generation;\n+\t\tuint32_t min_generation = commit_graph_generation(array[i]);\n \n \t\tif (redundant[i])\n \t\t\tcontinue;\n@@ -186,8 +186,8 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\t\tfilled_index[filled] = j;\n \t\t\twork[filled++] = array[j];\n \n-\t\t\tif (array[j]->generation < min_generation)\n-\t\t\t\tmin_generation = array[j]->generation;\n+\t\t\tif (commit_graph_generation(array[j]) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(array[j]);\n \t\t}\n \t\tcommon = paint_down_to_common(r, array[i], filled,\n \t\t\t\t\t work, min_generation);\n@@ -323,16 +323,16 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tfor (i = 0; i < nr_reference; i++) {\n \t\tif (repo_parse_commit(r, reference[i]))\n \t\t\treturn ret;\n-\t\tif (reference[i]->generation < min_generation)\n-\t\t\tmin_generation = reference[i]->generation;\n+\t\tif (commit_graph_generation(reference[i]) < min_generation)\n+\t\t\tmin_generation = commit_graph_generation(reference[i]);\n \t}\n \n-\tif (commit->generation > min_generation)\n+\tif (commit_graph_generation(commit) > min_generation)\n \t\treturn ret;\n \n \tbases = paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t commit->generation);\n+\t\t\t\t commit_graph_generation(commit));\n \tif (commit->object.flags & PARENT2)\n \t\tret = 1;\n \tclear_commit_marks(commit, all_flags);\n@@ -467,7 +467,7 @@ static enum contains_result contains_test(struct commit *candidate,\n \t/* Otherwise, we don't know; prepare to recurse */\n \tparse_commit_or_die(candidate);\n \n-\tif (candidate->generation < cutoff)\n+\tif (commit_graph_generation(candidate) < cutoff)\n \t\treturn CONTAINS_NO;\n \n \treturn CONTAINS_UNKNOWN;\n@@ -492,8 +492,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tfor (p = want; p; p = p->next) {\n \t\tstruct commit *c = p->item;\n \t\tload_commit_graph_info(the_repository, c);\n-\t\tif (c->generation < cutoff)\n-\t\t\tcutoff = c->generation;\n+\t\tif (commit_graph_generation(c) < cutoff)\n+\t\t\tcutoff = commit_graph_generation(c);\n \t}\n \n \tresult = contains_test(candidate, want, cache, cutoff);\n@@ -544,9 +544,9 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \tconst struct commit *a = *(const struct commit * const *)_a;\n \tconst struct commit *b = *(const struct commit * const *)_b;\n \n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn -1;\n-\tif (a->generation > b->generation)\n+\tif (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn 1;\n \treturn 0;\n }\n@@ -585,7 +585,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\tlist[nr_commits] = (struct commit *)from_one;\n \t\tif (parse_commit(list[nr_commits]) ||\n-\t\t list[nr_commits]->generation < min_generation) {\n+\t\t commit_graph_generation(list[nr_commits]) < min_generation) {\n \t\t\tresult = 0;\n \t\t\tgoto cleanup;\n \t\t}\n@@ -621,7 +621,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\t\t\t\tif (parse_commit(parent->item) ||\n \t\t\t\t\t parent->item->date < min_commit_date ||\n-\t\t\t\t\t parent->item->generation < min_generation)\n+\t\t\t\t\t commit_graph_generation(parent->item) < min_generation)\n \t\t\t\t\t\tcontinue;\n \n \t\t\t\t\tcommit_list_insert(parent->item, &stack);\n@@ -665,8 +665,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (from_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = from_iter->item->date;\n \n-\t\t\tif (from_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = from_iter->item->generation;\n+\t\t\tif (commit_graph_generation(from_iter->item) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(from_iter->item);\n \t\t}\n \n \t\tfrom_iter = from_iter->next;\n@@ -677,8 +677,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (to_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\t\tif (to_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = to_iter->item->generation;\n+\t\t\tif (commit_graph_generation(to_iter->item) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(to_iter->item);\n \t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n@@ -721,8 +721,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \t\tstruct commit *c = *item;\n \n \t\tparse_commit(c);\n-\t\tif (c->generation < min_generation)\n-\t\t\tmin_generation = c->generation;\n+\t\tif (commit_graph_generation(c) < min_generation)\n+\t\t\tmin_generation = commit_graph_generation(c);\n \n \t\tif (!(c->object.flags & PARENT1)) {\n \t\t\tc->object.flags |= PARENT1;\n@@ -755,7 +755,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \n \t\t\tparse_commit(p);\n \n-\t\t\tif (p->generation < min_generation)\n+\t\t\tif (commit_graph_generation(p) < min_generation)\n \t\t\t\tcontinue;\n \n \t\t\tif (p->object.flags & PARENT2)\ndiff --git a/commit.c b/commit.c\nindex 87686a7055..ad9a76dcc6 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r,\n \tif (commit->maybe_tree || !commit->object.parsed)\n \t\treturn commit->maybe_tree;\n \n-\tif (commit->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\tif (commit_graph_position(commit) != COMMIT_NOT_FROM_GRAPH)\n \t\treturn get_commit_tree_in_graph(r, commit);\n \n \treturn NULL;\n@@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void\n \tconst struct commit *a = a_, *b = b_;\n \n \t/* newer commits first */\n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn 1;\n-\telse if (a->generation > b->generation)\n+\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn -1;\n \n \t/* use date as a heuristic when generations are equal */\ndiff --git a/contrib/coccinelle/commit.cocci b/contrib/coccinelle/commit.cocci\nindex 778e4704f6..af6dd4c20c 100644\n--- a/contrib/coccinelle/commit.cocci\n+++ b/contrib/coccinelle/commit.cocci\n@@ -32,3 +32,21 @@ expression c;\n - c->maybe_tree\n + repo_get_commit_tree(specify_the_right_repo_here, c)\n ...>}\n+\n+@@\n+struct commit *c;\n+expression E;\n+@@\n+(\n+- c->generation = E;\n++ commit_graph_data_at(c)->generation = E;\n+|\n+- c->graph_pos = E;\n++ commit_graph_data_at(c)->graph_pos = E;\n+|\n+- c->generation\n++ commit_graph_generation(c)\n+|\n+- c->graph_pos\n++ commit_graph_position(c)\n+)\ndiff --git a/revision.c b/revision.c\nindex 60cca8c0b9..cb1b200e9f 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -720,7 +720,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \tif (!revs->repo->objects->commit_graph)\n \t\treturn -1;\n \n-\tif (commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n \tfilter = get_bloom_filter(revs->repo, commit, 0);\n@@ -3314,7 +3314,7 @@ static void explore_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->explore_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t commit_graph_generation(c) >= gen_cutoff)\n \t\texplore_walk_step(revs);\n }\n \n@@ -3330,7 +3330,7 @@ static void indegree_walk_step(struct rev_info *revs)\n \tif (parse_commit_gently(c, 1) < 0)\n \t\treturn;\n \n-\texplore_to_depth(revs, c->generation);\n+\texplore_to_depth(revs, commit_graph_generation(c));\n \n \tfor (p = c->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n@@ -3354,7 +3354,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t commit_graph_generation(c) >= gen_cutoff)\n \t\tindegree_walk_step(revs);\n }\n \n@@ -3414,8 +3414,8 @@ static void init_topo_walk(struct rev_info *revs)\n \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n \n-\t\tif (c->generation < info->min_generation)\n-\t\t\tinfo->min_generation = c->generation;\n+\t\tif (commit_graph_generation(c) < info->min_generation)\n+\t\t\tinfo->min_generation = commit_graph_generation(c);\n \n \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n \n@@ -3473,8 +3473,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-\t\tif (parent->generation < info->min_generation) {\n-\t\t\tinfo->min_generation = parent->generation;\n+\t\tif (commit_graph_generation(parent) < info->min_generation) {\n+\t\t\tinfo->min_generation = commit_graph_generation(parent);\n \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n \t\t}\n \n-- \n2.27.0\n\n"},{"id":"399258","messageId":"20200607193237.699335-4-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v2 3/4] commit-graph: use generation directly when writing commit-graph","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-07T19:32:36Z","receivedAt":"2020-06-07T19:34:48Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"commit_graph_generation() returns GENERATION_NUMBER_INFINITY if the\ngraph position for commit is COMMIT_NOT_FROM_GRAPH.\n\nWhile this is true when reading from a commit graph, no graph positions\nare associated with a commit when writing a commit graph. Therefore, the\nhelper incorrectly returns GENERATION_NUMBER_INFINITY despite having a\nfinite generation number.\n\nLet's fix this by using generation number directly when writing a commit\ngraph.\n\nSigned-off-by: Abhishek Kumar \n---\n commit-graph.c | 13 ++++++++-----\n 1 file changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex f7cca4def4..0dc79e7c90 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1070,7 +1070,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\telse\n \t\t\tpackedDate[0] = 0;\n \n-\t\tpackedDate[0] |= htonl(commit_graph_generation((*list)) << 2);\n+\t\tpackedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);\n \n \t\tpackedDate[1] = htonl((*list)->date);\n \t\thashwrite(f, packedDate, 8);\n@@ -1301,9 +1301,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\t\t\t_(\"Computing commit graph generation numbers\"),\n \t\t\t\t\tctx->commits.nr);\n \tfor (i = 0; i < ctx->commits.nr; i++) {\n+\t\tuint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n+\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n-\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n+\t\tif (generation != GENERATION_NUMBER_INFINITY &&\n+\t\t generation != GENERATION_NUMBER_ZERO)\n \t\t\tcontinue;\n \n \t\tcommit_list_insert(ctx->commits.list[i], &list);\n@@ -1314,8 +1316,9 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\tuint32_t max_generation = 0;\n \n \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n-\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n-\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n+\n+\t\t\t\tif (generation == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t generation == GENERATION_NUMBER_ZERO) {\n \t\t\t\t\tall_parents_computed = 0;\n \t\t\t\t\tcommit_list_insert(parent->item, &list);\n \t\t\t\t\tbreak;\n-- \n2.27.0\n\n"},{"id":"399259","messageId":"20200607193237.699335-5-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v2 4/4] commit-graph: minimize commit_graph_data_slab access","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-07T19:32:37Z","receivedAt":"2020-06-07T19:34:53Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"In an earlier patch, multiple struct acccesses to `graph_pos` and\n`generation` were auto-converted to multiple method calls.\n\nSince the values are fixed and commit-slab access costly, we would be\nbetter off with storing the values as a local variable and reuse it.\n\nSigned-off-by: Abhishek Kumar \n\n[1]: https://lore.kernel.org/git/9a15c7ba-8b55-099a-3c59-b5e7ff6124f6@gmail.com/\n---\n bloom.c | 5 +++--\n commit-graph.c | 55 +++++++++++++++++++++++++++++-----------------\n commit-reach.c | 59 ++++++++++++++++++++++++++++++++------------------\n commit.c | 6 +++--\n revision.c | 12 ++++++----\n 5 files changed, 88 insertions(+), 49 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex df62e3763d..568ebd75e7 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -33,15 +33,16 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n \t\t\t\t\tstruct commit *c)\n {\n \tuint32_t lex_pos, start_index, end_index;\n+\tuint32_t graph_pos = commit_graph_position(c);\n \n-\twhile (commit_graph_position(c) < g->num_commits_in_base)\n+\twhile (graph_pos < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n \tif (!g->chunk_bloom_indexes)\n \t\treturn 0;\n \n-\tlex_pos = commit_graph_position(c) - g->num_commits_in_base;\n+\tlex_pos = graph_pos - g->num_commits_in_base;\n \n \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n \ndiff --git a/commit-graph.c b/commit-graph.c\nindex 0dc79e7c90..5b10d1da2c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -141,10 +141,12 @@ static int commit_gen_cmp(const void *va, const void *vb)\n \tconst struct commit *a = *(const struct commit **)va;\n \tconst struct commit *b = *(const struct commit **)vb;\n \n+\tuint32_t generation_a = commit_graph_generation(a);\n+\tuint32_t generation_b = commit_graph_generation(b);\n \t/* lower generation commits first */\n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tif (generation_a < generation_b)\n \t\treturn -1;\n-\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n+\telse if (generation_a > generation_b)\n \t\treturn 1;\n \n \t/* use date as a heuristic when generations are equal */\n@@ -726,6 +728,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)\n {\n \tconst unsigned char *commit_data;\n+\tstruct commit_graph_data *graph_data;\n \tuint32_t lex_index;\n \n \twhile (pos < g->num_commits_in_base)\n@@ -733,8 +736,10 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n-\tcommit_graph_data_at(item)->graph_pos = pos;\n-\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\n+\tgraph_data = commit_graph_data_at(item);\n+\tgraph_data->graph_pos = pos;\n+\tgraph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n }\n \n static inline void set_commit_tree(struct commit *c, struct tree *t)\n@@ -750,6 +755,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tuint32_t *parent_data_ptr;\n \tuint64_t date_low, date_high;\n \tstruct commit_list **pptr;\n+\tstruct commit_graph_data *graph_data;\n \tconst unsigned char *commit_data;\n \tuint32_t lex_index;\n \n@@ -763,7 +769,8 @@ static int fill_commit_in_graph(struct repository *r,\n \t * Store the \"full\" position, but then use the\n \t * \"local\" position for the rest of the calculation.\n \t */\n-\tcommit_graph_data_at(item)->graph_pos = pos;\n+\tgraph_data = commit_graph_data_at(item);\n+\tgraph_data->graph_pos = pos;\n \tlex_index = pos - g->num_commits_in_base;\n \n \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n@@ -776,7 +783,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n \titem->date = (timestamp_t)((date_high << 32) | date_low);\n \n-\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tgraph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n \n \tpptr = &item->parents;\n \n@@ -808,8 +815,9 @@ static int fill_commit_in_graph(struct repository *r,\n \n static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n {\n-\tif (commit_graph_position(item) != COMMIT_NOT_FROM_GRAPH) {\n-\t\t*pos = commit_graph_position(item);\n+\tuint32_t graph_pos = commit_graph_position(item);\n+\tif (graph_pos != COMMIT_NOT_FROM_GRAPH) {\n+\t\t*pos = graph_pos;\n \t\treturn 1;\n \t} else {\n \t\tstruct commit_graph *cur_g = g;\n@@ -864,12 +872,13 @@ static struct tree *load_tree_for_commit(struct repository *r,\n {\n \tstruct object_id oid;\n \tconst unsigned char *commit_data;\n+\tuint32_t graph_pos = commit_graph_position(c);\n \n-\twhile (commit_graph_position(c) < g->num_commits_in_base)\n+\twhile (graph_pos < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \tcommit_data = g->chunk_commit_data +\n-\t\t\tGRAPH_DATA_WIDTH * (commit_graph_position(c) - g->num_commits_in_base);\n+\t\t\tGRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base);\n \n \thashcpy(oid.hash, commit_data);\n \tset_commit_tree(c, lookup_tree(r, &oid));\n@@ -1301,7 +1310,7 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\t\t\t_(\"Computing commit graph generation numbers\"),\n \t\t\t\t\tctx->commits.nr);\n \tfor (i = 0; i < ctx->commits.nr; i++) {\n-\t\tuint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n+\t\tuint32_t generation = commit_graph_generation(ctx->commits.list[i]);\n \n \t\tdisplay_progress(ctx->progress, i + 1);\n \t\tif (generation != GENERATION_NUMBER_INFINITY &&\n@@ -1316,23 +1325,26 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\tuint32_t max_generation = 0;\n \n \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n+\t\t\t\tgeneration = commit_graph_generation(parent->item);\n \n \t\t\t\tif (generation == GENERATION_NUMBER_INFINITY ||\n \t\t\t\t generation == GENERATION_NUMBER_ZERO) {\n \t\t\t\t\tall_parents_computed = 0;\n \t\t\t\t\tcommit_list_insert(parent->item, &list);\n \t\t\t\t\tbreak;\n-\t\t\t\t} else if (commit_graph_generation(parent->item) > max_generation) {\n-\t\t\t\t\tmax_generation = commit_graph_generation(parent->item);\n+\t\t\t\t} else if (generation > max_generation) {\n+\t\t\t\t\tmax_generation = generation;\n \t\t\t\t}\n \t\t\t}\n \n \t\t\tif (all_parents_computed) {\n-\t\t\t\tcommit_graph_data_at(current)->generation = max_generation + 1;\n+\t\t\t\tstruct commit_graph_data *graph_data = commit_graph_data_at(current);\n+\n+\t\t\t\tgraph_data->generation = max_generation + 1;\n \t\t\t\tpop_commit(&list);\n \n-\t\t\t\tif (commit_graph_generation(current) > GENERATION_NUMBER_MAX)\n-\t\t\t\t\tcommit_graph_data_at(current)->generation = GENERATION_NUMBER_MAX;\n+\t\t\t\tif (graph_data->generation > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tgraph_data->generation = GENERATION_NUMBER_MAX;\n \t\t\t}\n \t\t}\n \t}\n@@ -2301,6 +2313,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tstruct commit *graph_commit, *odb_commit;\n \t\tstruct commit_list *graph_parents, *odb_parents;\n \t\tuint32_t max_generation = 0;\n+\t\tuint32_t generation;\n \n \t\tdisplay_progress(progress, i + 1);\n \t\thashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);\n@@ -2339,8 +2352,9 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n \n-\t\t\tif (commit_graph_generation(graph_parents->item) > max_generation)\n-\t\t\t\tmax_generation = commit_graph_generation(graph_parents->item);\n+\t\t\tgeneration = commit_graph_generation(graph_parents->item);\n+\t\t\tif (generation > max_generation)\n+\t\t\t\tmax_generation = generation;\n \n \t\t\tgraph_parents = graph_parents->next;\n \t\t\todb_parents = odb_parents->next;\n@@ -2370,10 +2384,11 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tif (max_generation == GENERATION_NUMBER_MAX)\n \t\t\tmax_generation--;\n \n-\t\tif (commit_graph_generation(graph_commit) != max_generation + 1)\n+\t\tgeneration = commit_graph_generation(graph_commit);\n+\t\tif (generation != max_generation + 1)\n \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n \t\t\t\t oid_to_hex(&cur_oid),\n-\t\t\t\t commit_graph_generation(graph_commit),\n+\t\t\t\t generation,\n \t\t\t\t max_generation + 1);\n \n \t\tif (graph_commit->date != odb_commit->date)\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 3b2f863f5f..f5e5c0a32b 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -58,14 +58,15 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n+\t\tuint32_t generation = commit_graph_generation(commit);\n \n-\t\tif (min_generation && commit_graph_generation(commit) > last_gen)\n+\t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit_graph_generation(commit), last_gen,\n+\t\t\t generation, last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit_graph_generation(commit);\n+\t\tlast_gen = generation;\n \n-\t\tif (commit_graph_generation(commit) < min_generation)\n+\t\tif (generation < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -181,13 +182,15 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\tif (redundant[i])\n \t\t\tcontinue;\n \t\tfor (j = filled = 0; j < cnt; j++) {\n+\t\t\tuint32_t curr_generation;\n \t\t\tif (i == j || redundant[j])\n \t\t\t\tcontinue;\n \t\t\tfilled_index[filled] = j;\n \t\t\twork[filled++] = array[j];\n \n-\t\t\tif (commit_graph_generation(array[j]) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(array[j]);\n+\t\t\tcurr_generation = commit_graph_generation(array[j]);\n+\t\t\tif (curr_generation < min_generation)\n+\t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tcommon = paint_down_to_common(r, array[i], filled,\n \t\t\t\t\t work, min_generation);\n@@ -316,23 +319,26 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n {\n \tstruct commit_list *bases;\n \tint ret = 0, i;\n-\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tuint32_t generation, min_generation = GENERATION_NUMBER_INFINITY;\n \n \tif (repo_parse_commit(r, commit))\n \t\treturn ret;\n \tfor (i = 0; i < nr_reference; i++) {\n \t\tif (repo_parse_commit(r, reference[i]))\n \t\t\treturn ret;\n-\t\tif (commit_graph_generation(reference[i]) < min_generation)\n-\t\t\tmin_generation = commit_graph_generation(reference[i]);\n+\n+\t\tgeneration = commit_graph_generation(reference[i]);\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n \t}\n \n-\tif (commit_graph_generation(commit) > min_generation)\n+\tgeneration = commit_graph_generation(commit);\n+\tif (generation > min_generation)\n \t\treturn ret;\n \n \tbases = paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t commit_graph_generation(commit));\n+\t\t\t\t generation);\n \tif (commit->object.flags & PARENT2)\n \t\tret = 1;\n \tclear_commit_marks(commit, all_flags);\n@@ -490,10 +496,12 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tconst struct commit_list *p;\n \n \tfor (p = want; p; p = p->next) {\n+\t\tuint32_t generation;\n \t\tstruct commit *c = p->item;\n \t\tload_commit_graph_info(the_repository, c);\n-\t\tif (commit_graph_generation(c) < cutoff)\n-\t\t\tcutoff = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < cutoff)\n+\t\t\tcutoff = generation;\n \t}\n \n \tresult = contains_test(candidate, want, cache, cutoff);\n@@ -544,9 +552,12 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \tconst struct commit *a = *(const struct commit * const *)_a;\n \tconst struct commit *b = *(const struct commit * const *)_b;\n \n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tuint32_t generation_a = commit_graph_generation(a);\n+\tuint32_t generation_b = commit_graph_generation(b);\n+\n+\tif (generation_a < generation_b)\n \t\treturn -1;\n-\tif (commit_graph_generation(a) > commit_graph_generation(b))\n+\tif (generation_a > generation_b)\n \t\treturn 1;\n \treturn 0;\n }\n@@ -662,11 +673,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\tadd_object_array(&from_iter->item->object, NULL, &from_objs);\n \n \t\tif (!parse_commit(from_iter->item)) {\n+\t\t\tuint32_t generation;\n \t\t\tif (from_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = from_iter->item->date;\n \n-\t\t\tif (commit_graph_generation(from_iter->item) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(from_iter->item);\n+\t\t\tgeneration = commit_graph_generation(from_iter->item);\n+\t\t\tif (generation < min_generation)\n+\t\t\t\tmin_generation = generation;\n \t\t}\n \n \t\tfrom_iter = from_iter->next;\n@@ -674,11 +687,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \n \twhile (to_iter) {\n \t\tif (!parse_commit(to_iter->item)) {\n+\t\t\tuint32_t generation;\n \t\t\tif (to_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\t\tif (commit_graph_generation(to_iter->item) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(to_iter->item);\n+\t\t\tgeneration = commit_graph_generation(to_iter->item);\n+\t\t\tif (generation < min_generation)\n+\t\t\t\tmin_generation = generation;\n \t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n@@ -718,11 +733,13 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n \tfor (item = to; item < to_last; item++) {\n+\t\tuint32_t generation;\n \t\tstruct commit *c = *item;\n \n \t\tparse_commit(c);\n-\t\tif (commit_graph_generation(c) < min_generation)\n-\t\t\tmin_generation = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n \n \t\tif (!(c->object.flags & PARENT1)) {\n \t\t\tc->object.flags |= PARENT1;\ndiff --git a/commit.c b/commit.c\nindex ad9a76dcc6..f85ade78ed 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -729,11 +729,13 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n+\tconst uint32_t generation_a = commit_graph_generation(a),\n+\t\t generation_b = commit_graph_generation(b);\n \n \t/* newer commits first */\n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tif (generation_a < generation_b)\n \t\treturn 1;\n-\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n+\telse if (generation_a > generation_b)\n \t\treturn -1;\n \n \t/* use date as a heuristic when generations are equal */\ndiff --git a/revision.c b/revision.c\nindex cb1b200e9f..c257089808 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3407,6 +3407,7 @@ static void init_topo_walk(struct rev_info *revs)\n \tinfo->min_generation = GENERATION_NUMBER_INFINITY;\n \tfor (list = revs->commits; list; list = list->next) {\n \t\tstruct commit *c = list->item;\n+\t\tuint32_t generation;\n \n \t\tif (parse_commit_gently(c, 1))\n \t\t\tcontinue;\n@@ -3414,8 +3415,9 @@ static void init_topo_walk(struct rev_info *revs)\n \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n \n-\t\tif (commit_graph_generation(c) < info->min_generation)\n-\t\t\tinfo->min_generation = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < info->min_generation)\n+\t\t\tinfo->min_generation = generation;\n \n \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n \n@@ -3466,6 +3468,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \tfor (p = commit->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n \t\tint *pi;\n+\t\tuint32_t generation;\n \n \t\tif (parent->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n@@ -3473,8 +3476,9 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-\t\tif (commit_graph_generation(parent) < info->min_generation) {\n-\t\t\tinfo->min_generation = commit_graph_generation(parent);\n+\t\tgeneration = commit_graph_generation(parent);\n+\t\tif (generation < info->min_generation) {\n+\t\t\tinfo->min_generation = generation;\n \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n \t\t}\n \n-- \n2.27.0\n\n"},{"id":"399260","messageId":"20200607195347.GA8232@szeder.dev","threadId":"53611","inReplyTo":"b850637d-a7ca-e8f9-5009-657096ea2975@gmail.com","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-07T19:53:47Z","receivedAt":"2020-06-07T19:53:59Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n> On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> > The struct commit is used in many contexts. However, members generation\n> > and graph_pos are only used for commit-graph related operations and\n> > otherwise waste memory.\n> > \n> > This wastage would have been more pronounced as transistion to\n> > generation number v2, which uses 64-bit generation number instead of\n> > current 32-bits.\n> \n> Thanks! This is an important step, and will already improve\n> performance in subtle ways.\n\nWhile the reduced memory footprint of each commit object might improve\nperformance, accessing graph position and generation numbers in a\ncommit-slab is more expensive than direct field accesses in 'struct\ncommit' instances. Consequently, these patches increase the runtime\nof 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\nrepository from 0.630s to 0.940s.\n\n\n> > create mode 100644 contrib/coccinelle/generation.cocci\n> > create mode 100644 contrib/coccinelle/graph_pos.cocci\n> \n> I appreciate the Coccinelle scripts to help identify\n> automatic fixes for other topics in-flight. However,\n> I wonder if they would be better placed inside the\n> existing commit.cocci file?\n\nWe add Coccinelle scripts to avoid undesirable code patterns entering\nour code base. That, however, is not the case here: this is a\none-time conversion, and at the end of this series 'struct commit'\nwon't have a 'generation' field anymore, so once it's merged the\ncompiler will catch any new 'commit->generation' accesses. Therefore\nI don't think that these Coccinelle scripts should be added at all.\n\n"},{"id":"399271","messageId":"20200608054827.GA2054@Abhishek-Arch","threadId":"53611","inReplyTo":"20200607195347.GA8232@szeder.dev","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-08T05:48:27Z","receivedAt":"2020-06-08T05:50:15Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Sun, Jun 07, 2020 at 09:53:47PM +0200, SZEDER Gábor wrote:\n> On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n> > On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> > > The struct commit is used in many contexts. However, members generation\n> > > and graph_pos are only used for commit-graph related operations and\n> > > otherwise waste memory.\n> > > \n> > > This wastage would have been more pronounced as transistion to\n> > > generation number v2, which uses 64-bit generation number instead of\n> > > current 32-bits.\n> > \n> > Thanks! This is an important step, and will already improve\n> > performance in subtle ways.\n> \n> While the reduced memory footprint of each commit object might improve\n> performance, accessing graph position and generation numbers in a\n> commit-slab is more expensive than direct field accesses in 'struct\n> commit' instances. Consequently, these patches increase the runtime\n> of 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\n> repository from 0.630s to 0.940s.\n> \n\nThank you for checking performance. Performance penalty was something we\nhad discussed here [1]. \n\nCaching the commit slab results in local variables helped wonderfully in v2 [2].\nFor example, the runtime of 'git merge-base --is-ancestor HEAD~50000 HEAD'\nin the linux repository increased from 0.762 to 0.767s. Since this is a\nchange of <1%, it is *no longer* a performance regression in my opinion.\n\n[1]: https://lore.kernel.org/git/9a15c7ba-8b55-099a-3c59-b5e7ff6124f6@gmail.com/\n[2]: https://lore.kernel.org/git/20200607193237.699335-5-abhishekkumar8222@gmail.com/\n\n> \n> > > create mode 100644 contrib/coccinelle/generation.cocci\n> > > create mode 100644 contrib/coccinelle/graph_pos.cocci\n> > \n> > I appreciate the Coccinelle scripts to help identify\n> > automatic fixes for other topics in-flight. However,\n> > I wonder if they would be better placed inside the\n> > existing commit.cocci file?\n> \n> We add Coccinelle scripts to avoid undesirable code patterns entering\n> our code base. That, however, is not the case here: this is a\n> one-time conversion, and at the end of this series 'struct commit'\n> won't have a 'generation' field anymore, so once it's merged the\n> compiler will catch any new 'commit->generation' accesses. Therefore\n> I don't think that these Coccinelle scripts should be added at all.\n> \n\nAlright, that makes sense to me. Will remove in a subsequent version.\n\nThanks\nAbhishek\n"},{"id":"399282","messageId":"20200608082636.GC8232@szeder.dev","threadId":"53611","inReplyTo":"20200607193237.699335-3-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v2 2/4] commit: move members graph_pos, generation to a slab","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-08T08:26:36Z","receivedAt":"2020-06-08T08:26:42Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, Jun 08, 2020 at 01:02:35AM +0530, Abhishek Kumar wrote:\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 7d887a6a2c..f7cca4def4 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n\n> @@ -1302,8 +1302,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\t\t\tctx->commits.nr);\n> \tfor (i = 0; i < ctx->commits.nr; i++) {\n> \t\tdisplay_progress(ctx->progress, i + 1);\n> -\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n> -\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n> +\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n> +\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n> \t\t\tcontinue;\n> \n> \t\tcommit_list_insert(ctx->commits.list[i], &list);\n> @@ -1314,22 +1314,22 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\tuint32_t max_generation = 0;\n> \n> \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n> -\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n> -\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n> +\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n> +\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n> \t\t\t\t\tall_parents_computed = 0;\n> \t\t\t\t\tcommit_list_insert(parent->item, &list);\n> \t\t\t\t\tbreak;\n> -\t\t\t\t} else if (parent->item->generation > max_generation) {\n> -\t\t\t\t\tmax_generation = parent->item->generation;\n> +\t\t\t\t} else if (commit_graph_generation(parent->item) > max_generation) {\n> +\t\t\t\t\tmax_generation = commit_graph_generation(parent->item);\n> \t\t\t\t}\n> \t\t\t}\n> \n> \t\t\tif (all_parents_computed) {\n> -\t\t\t\tcurrent->generation = max_generation + 1;\n> +\t\t\t\tcommit_graph_data_at(current)->generation = max_generation + 1;\n> \t\t\t\tpop_commit(&list);\n> \n> -\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n> -\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n> +\t\t\t\tif (commit_graph_generation(current) > GENERATION_NUMBER_MAX)\n> +\t\t\t\t\tcommit_graph_data_at(current)->generation = GENERATION_NUMBER_MAX;\n> \t\t\t}\n> \t\t}\n> \t}\n\nSomething about these conversions is not right, as they send\ncompute_generation_numbers() into an endless loop, and\n't5318-commit-graph.sh' hangs because of this.\n\n"},{"id":"399283","messageId":"20200608083615.GD8232@szeder.dev","threadId":"53611","inReplyTo":"20200608054827.GA2054@Abhishek-Arch","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-08T08:36:15Z","receivedAt":"2020-06-08T08:36:21Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, Jun 08, 2020 at 11:18:27AM +0530, Abhishek Kumar wrote:\n> On Sun, Jun 07, 2020 at 09:53:47PM +0200, SZEDER Gábor wrote:\n> > On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n> > > On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> > > > The struct commit is used in many contexts. However, members generation\n> > > > and graph_pos are only used for commit-graph related operations and\n> > > > otherwise waste memory.\n> > > > \n> > > > This wastage would have been more pronounced as transistion to\n> > > > generation number v2, which uses 64-bit generation number instead of\n> > > > current 32-bits.\n> > > \n> > > Thanks! This is an important step, and will already improve\n> > > performance in subtle ways.\n> > \n> > While the reduced memory footprint of each commit object might improve\n> > performance, accessing graph position and generation numbers in a\n> > commit-slab is more expensive than direct field accesses in 'struct\n> > commit' instances. Consequently, these patches increase the runtime\n> > of 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\n> > repository from 0.630s to 0.940s.\n> > \n> \n> Thank you for checking performance. Performance penalty was something we\n> had discussed here [1]. \n> \n> Caching the commit slab results in local variables helped wonderfully in v2 [2].\n> For example, the runtime of 'git merge-base --is-ancestor HEAD~50000 HEAD'\n> in the linux repository increased from 0.762 to 0.767s. Since this is a\n> change of <1%, it is *no longer* a performance regression in my opinion.\n\nInteresting, I measured 0.870s with v2, still a notable increase from\n0.630s.\n\n"},{"id":"399290","messageId":"c9333a2d-a0d7-0fe4-e485-7d28b703506a@gmail.com","threadId":"53611","inReplyTo":"20200608082636.GC8232@szeder.dev","subject":"Re: [GSOC Patch v2 2/4] commit: move members graph_pos, generation to a slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-08T12:35:35Z","receivedAt":"2020-06-08T12:35:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/8/2020 4:26 AM, SZEDER Gábor wrote:\n> On Mon, Jun 08, 2020 at 01:02:35AM +0530, Abhishek Kumar wrote:\n>> diff --git a/commit-graph.c b/commit-graph.c\n>> index 7d887a6a2c..f7cca4def4 100644\n>> --- a/commit-graph.c\n>> +++ b/commit-graph.c\n> \n>> @@ -1302,8 +1302,8 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n>> \t\t\t\t\tctx->commits.nr);\n>> \tfor (i = 0; i < ctx->commits.nr; i++) {\n>> \t\tdisplay_progress(ctx->progress, i + 1);\n>> -\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n>> -\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n>> +\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n>> +\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n>> \t\t\tcontinue;\n>> \n>> \t\tcommit_list_insert(ctx->commits.list[i], &list);\n>> @@ -1314,22 +1314,22 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n>> \t\t\tuint32_t max_generation = 0;\n>> \n>> \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n>> -\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n>> -\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n>> +\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n>> +\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n>> \t\t\t\t\tall_parents_computed = 0;\n>> \t\t\t\t\tcommit_list_insert(parent->item, &list);\n>> \t\t\t\t\tbreak;\n>> -\t\t\t\t} else if (parent->item->generation > max_generation) {\n>> -\t\t\t\t\tmax_generation = parent->item->generation;\n>> +\t\t\t\t} else if (commit_graph_generation(parent->item) > max_generation) {\n>> +\t\t\t\t\tmax_generation = commit_graph_generation(parent->item);\n>> \t\t\t\t}\n>> \t\t\t}\n>> \n>> \t\t\tif (all_parents_computed) {\n>> -\t\t\t\tcurrent->generation = max_generation + 1;\n>> +\t\t\t\tcommit_graph_data_at(current)->generation = max_generation + 1;\n>> \t\t\t\tpop_commit(&list);\n>> \n>> -\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n>> -\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n>> +\t\t\t\tif (commit_graph_generation(current) > GENERATION_NUMBER_MAX)\n>> +\t\t\t\t\tcommit_graph_data_at(current)->generation = GENERATION_NUMBER_MAX;\n>> \t\t\t}\n>> \t\t}\n>> \t}\n> \n> Something about these conversions is not right, as they send\n> compute_generation_numbers() into an endless loop, and\n> 't5318-commit-graph.sh' hangs because of this.\n\nAbhishek responded off-list, but it's worth having the discussion\nhere, too.\n\nWhile the next patch fixes the bug introduced here, we strive to\nhave every patch compile and pass all tests on all platforms. It\ncan be hard to verify that last \"all platforms\" condition, but\nwe can run (most) tests on each of our patches using the following:\n\n$ git rebase -x \"make -j12 DEVELOPER=1 && (cd t && prove -j8 t[0-8]*.sh)\" \n\nThanks, Szeder, for finding this issue in the patch.\n\nLooking at this patch and patch 3, I think you should just squash that patch\ninto this one, since the code you are removing in patch 3 was added by this\none. Add a paragraph in your commit message that details why we need to use\ncommit_graph_data_at() directly in write_graph_chunk_data() and\ncompute_generation_numbers().\n\nThanks,\n-Stolee\n"},{"id":"399293","messageId":"13db757a-9412-7f1e-805c-8a028c4ab2b1@gmail.com","threadId":"53611","inReplyTo":"20200608083615.GD8232@szeder.dev","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-08T13:45:12Z","receivedAt":"2020-06-08T13:45:18Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/8/2020 4:36 AM, SZEDER Gábor wrote:\n> On Mon, Jun 08, 2020 at 11:18:27AM +0530, Abhishek Kumar wrote:\n>> On Sun, Jun 07, 2020 at 09:53:47PM +0200, SZEDER Gábor wrote:\n>>> On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n>>>> On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n>>>>> The struct commit is used in many contexts. However, members generation\n>>>>> and graph_pos are only used for commit-graph related operations and\n>>>>> otherwise waste memory.\n>>>>>\n>>>>> This wastage would have been more pronounced as transistion to\n>>>>> generation number v2, which uses 64-bit generation number instead of\n>>>>> current 32-bits.\n>>>>\n>>>> Thanks! This is an important step, and will already improve\n>>>> performance in subtle ways.\n>>>\n>>> While the reduced memory footprint of each commit object might improve\n>>> performance, accessing graph position and generation numbers in a\n>>> commit-slab is more expensive than direct field accesses in 'struct\n>>> commit' instances. Consequently, these patches increase the runtime\n>>> of 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\n>>> repository from 0.630s to 0.940s.\n>>>\n>>\n>> Thank you for checking performance. Performance penalty was something we\n>> had discussed here [1]. \n>>\n>> Caching the commit slab results in local variables helped wonderfully in v2 [2].\n>> For example, the runtime of 'git merge-base --is-ancestor HEAD~50000 HEAD'\n>> in the linux repository increased from 0.762 to 0.767s. Since this is a\n>> change of <1%, it is *no longer* a performance regression in my opinion.\n> \n> Interesting, I measured 0.870s with v2, still a notable increase from\n> 0.630s.\n\nThis is an interesting point. The --is-ancestor is critical to the\nperformance issue (as measured on my machine).\n\nFor \"git merge-base HEAD~50000 HEAD\" on the Linux repo, I get\n\nv2.27.0:\nreal 0m0.515s\nuser 0m0.467s\nsys 0m0.048s\n\nv2 series:\nreal 0m0.534s\nuser 0m0.481s\nsys 0m0.053s\n\nWith \"--is-ancestor\" I see the following:\n\nv2.27.0:\nreal 0m0.591s\nuser 0m0.539s\nsys 0m0.052s\n\nv2 series:\nreal 0m0.773s\nuser 0m0.733s\nsys 0m0.040s\n\nThe --is-ancestor option [1] says\n\n Check if the first is an ancestor of the second\n , and exit with status 0 if true, or with status\n 1 if not. Errors are signaled by a non-zero status that\n is not 1.\n\n[1] https://git-scm.com/docs/git-merge-base#Documentation/git-merge-base.txt---is-ancestor\n\nThis _should_ be faster than \"git branch --contains HEAD~50000\",\nbut it is much much slower:\n\n$ time git branch --contains HEAD~50000\nreal 0m0.068s\nuser 0m0.061s\nsys 0m0.008s\n\nSo, there is definitely something going on that slows the\n\"--is-ancestor\" path in this case. But, the solution is not\nto halt the current patch (which likely has memory footprint\nbenefits when dealing with a lot of tree and blob objects)\nand instead fix the underlying algorithm.\n\nLet's add that to the list of things to do.\n\n>>> create mode 100644 contrib/coccinelle/generation.cocci\n>>> create mode 100644 contrib/coccinelle/graph_pos.cocci\n>>\n>> I appreciate the Coccinelle scripts to help identify\n>> automatic fixes for other topics in-flight. However,\n>> I wonder if they would be better placed inside the\n>> existing commit.cocci file?\n>\n> We add Coccinelle scripts to avoid undesirable code patterns entering\n> our code base. That, however, is not the case here: this is a\n> one-time conversion, and at the end of this series 'struct commit'\n> won't have a 'generation' field anymore, so once it's merged the\n> compiler will catch any new 'commit->generation' accesses. Therefore\n> I don't think that these Coccinelle scripts should be added at all.\n\nI disagree. We _also_ add Coccinelle scripts when doing one-time\nrefactors to avoid logical merge conflicts with other topics in\nflight. If someone else is working on a parallel topic that adds\nreferences to graph_pos or generation member, then the scripts provide\nan easy way for the maintainer to update those references in the merge\ncommit. Alternatively, the contributor could rebase on top of this\nseries and run the scripts themselves to fix their patches before\nsubmission.\n\nFor example, this was done carefully in the sha->object_id\nconversion using contrib/coccinelle/object_id.cocci.\n\nThanks,\n-Stolee\n"},{"id":"399298","messageId":"85o8pttwft.fsf@gmail.com","threadId":"53611","inReplyTo":"20200608083615.GD8232@szeder.dev","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-08T15:21:42Z","receivedAt":"2020-06-08T15:21:49Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"SZEDER Gábor writes:\n> On Mon, Jun 08, 2020 at 11:18:27AM +0530, Abhishek Kumar wrote:\n>> On Sun, Jun 07, 2020 at 09:53:47PM +0200, SZEDER Gábor wrote:\n>>> On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n>>>> On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n\n>>>>> The struct commit is used in many contexts. However, members generation\n>>>>> and graph_pos are only used for commit-graph related operations and\n>>>>> otherwise waste memory.\n>>>>> \n>>>>> This wastage would have been more pronounced as transistion to\n>>>>> generation number v2, which uses 64-bit generation number instead of\n>>>>> current 32-bits.\n>>>> \n>>>> Thanks! This is an important step, and will already improve\n>>>> performance in subtle ways.\n>>> \n>>> While the reduced memory footprint of each commit object might improve\n>>> performance, accessing graph position and generation numbers in a\n>>> commit-slab is more expensive than direct field accesses in 'struct\n>>> commit' instances. Consequently, these patches increase the runtime\n>>> of 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\n>>> repository from 0.630s to 0.940s. \n>> \n>> Thank you for checking performance. Performance penalty was something we\n>> had discussed here [1]. \n>> \n>> Caching the commit slab results in local variables helped wonderfully in v2 [2].\n>> For example, the runtime of 'git merge-base --is-ancestor HEAD~50000 HEAD'\n>> in the linux repository increased from 0.762 to 0.767s. Since this is a\n>> change of <1%, it is *no longer* a performance regression in my opinion.\n>>\n>> [1]: https://lore.kernel.org/git/9a15c7ba-8b55-099a-3c59-b5e7ff6124f6@gmail.com/\n>> [2]: https://lore.kernel.org/git/20200607193237.699335-5-abhishekkumar8222@gmail.com/\n>\n> Interesting, I measured 0.870s with v2, still a notable increase from\n> 0.630s [a change of +38%].\n\nI wonder what might be the cause for this difference. Is it difference\nin hardware (faster memory, larger CPU cache?), difference in operating\nsystem, or difference in position of HEAD?\n\nOn one hand it is large relative difference. On the other hand it is\nalmost unnoticeable absolute difference of 0.25s.\n\n\nI also wonder how the performance changes (with moving commit-graph data\nto the slab) for commands that do not use this data, like e.g.:\n\n $ git -o core.commitGraph=false merge-base --is-ancestor HEAD~50000 HEAD\n\nor\n\n $ git gc\n\n\nSidenote: I think the performance changes should be mentioned at least\nin the cover letter for the series, if not in commit message(s).\n\nBest,\n-- \nJakub Narębski\n"},{"id":"399301","messageId":"85d069ttm8.fsf@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v2 0/4] Move generation, graph_pos to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-08T16:22:39Z","receivedAt":"2020-06-08T16:22:48Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> The struct commit is used in many contexts. However, members\n> `generation` and `graph_pos` are only used for commit graph related\n> operations and otherwise waste memory.\n>\n> This wastage would have been more pronounced as we transition to\n> generation number v2, which uses 64-bite generation number instead of\n> current 32-bits.\n\nIt would be nice (though not required) to have some specific data:\nbenchmarks with time and memory (RSS maybe?) of Git commands using\ncommit-graph and those not using it, before and after this patch series.\nMaybe time to run the test suite, or the perf suite...\n\nBut this is not a show stopper, in my opinion.\n\nBest,\n\n Jakub Narębski\n\n\n> Abhishek Kumar (4):\n> commit-graph: introduce commit_graph_data_slab\n> commit: move members graph_pos, generation to a slab\n> commit-graph: use generation directly when writing commit-graph\n> commit-graph: minimize commit_graph_data_slab access\n>\n> alloc.c | 2 -\n> blame.c | 2 +-\n> bloom.c | 7 +-\n> commit-graph.c | 127 ++++++++++++++++++++++++--------\n> commit-graph.h | 10 +++\n> commit-reach.c | 69 ++++++++++-------\n> commit.c | 8 +-\n> contrib/coccinelle/commit.cocci | 18 +++++\n> revision.c | 20 +++--\n> 9 files changed, 190 insertions(+), 73 deletions(-)\n"},{"id":"399302","messageId":"85zh9dsemi.fsf@gmail.com","threadId":"53611","inReplyTo":"20200607193237.699335-4-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v2 3/4] commit-graph: use generation directly when writing commit-graph","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-08T16:31:49Z","receivedAt":"2020-06-08T16:31:55Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Abhishek Kumar writes:\n\n> commit_graph_generation() returns GENERATION_NUMBER_INFINITY if the\n> graph position for commit is COMMIT_NOT_FROM_GRAPH.\n>\n> While this is true when reading from a commit graph, no graph positions\n> are associated with a commit when writing a commit graph. Therefore, the\n> helper incorrectly returns GENERATION_NUMBER_INFINITY despite having a\n> finite generation number.\n>\n> Let's fix this by using generation number directly when writing a commit\n> graph.\n\nI think that to avoid having non-working patch (which can cause problems\nwhen bisecting), it would be a better idea to switch the order of\npatches 2 and 3. This way we won't have incorrect behaviour.\n\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> commit-graph.c | 13 ++++++++-----\n> 1 file changed, 8 insertions(+), 5 deletions(-)\n>\n> diff --git a/commit-graph.c b/commit-graph.c\n> index f7cca4def4..0dc79e7c90 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -1070,7 +1070,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n> \t\telse\n> \t\t\tpackedDate[0] = 0;\n> \n> -\t\tpackedDate[0] |= htonl(commit_graph_generation((*list)) << 2);\n> +\t\tpackedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);\n>\n\nAll right.\n\n> \t\tpackedDate[1] = htonl((*list)->date);\n> \t\thashwrite(f, packedDate, 8);\n> @@ -1301,9 +1301,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\t\t\t_(\"Computing commit graph generation numbers\"),\n> \t\t\t\t\tctx->commits.nr);\n> \tfor (i = 0; i < ctx->commits.nr; i++) {\n> +\t\tuint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n> +\n> \t\tdisplay_progress(ctx->progress, i + 1);\n> -\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n> -\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n> +\t\tif (generation != GENERATION_NUMBER_INFINITY &&\n> +\t\t generation != GENERATION_NUMBER_ZERO)\n> \t\t\tcontinue;\n>\n\nAll right; this also introduces local variable to avoid accessing the\nslab twice^W four times...\n\n> \t\tcommit_list_insert(ctx->commits.list[i], &list);\n> @@ -1314,8 +1316,9 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> \t\t\tuint32_t max_generation = 0;\n> \n> \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n> -\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n> -\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n> +\n> +\t\t\t\tif (generation == GENERATION_NUMBER_INFINITY ||\n> +\t\t\t\t generation == GENERATION_NUMBER_ZERO) {\n> \t\t\t\t\tall_parents_computed = 0;\n> \t\t\t\t\tcommit_list_insert(parent->item, &list);\n> \t\t\t\t\tbreak;\n\n... which is then used here.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"399303","messageId":"20200608164637.GE8232@szeder.dev","threadId":"53611","inReplyTo":"13db757a-9412-7f1e-805c-8a028c4ab2b1@gmail.com","subject":"Re: [GSoC Patch 0/3] Move generation, graph_pos to a slab","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-08T16:46:37Z","receivedAt":"2020-06-08T16:46:45Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, Jun 08, 2020 at 09:45:12AM -0400, Derrick Stolee wrote:\n> On 6/8/2020 4:36 AM, SZEDER Gábor wrote:\n> > On Mon, Jun 08, 2020 at 11:18:27AM +0530, Abhishek Kumar wrote:\n> >> On Sun, Jun 07, 2020 at 09:53:47PM +0200, SZEDER Gábor wrote:\n> >>> On Thu, Jun 04, 2020 at 10:22:27AM -0400, Derrick Stolee wrote:\n> >>>> On 6/4/2020 3:27 AM, Abhishek Kumar wrote:\n> >>>>> The struct commit is used in many contexts. However, members generation\n> >>>>> and graph_pos are only used for commit-graph related operations and\n> >>>>> otherwise waste memory.\n> >>>>>\n> >>>>> This wastage would have been more pronounced as transistion to\n> >>>>> generation number v2, which uses 64-bit generation number instead of\n> >>>>> current 32-bits.\n> >>>>\n> >>>> Thanks! This is an important step, and will already improve\n> >>>> performance in subtle ways.\n> >>>\n> >>> While the reduced memory footprint of each commit object might improve\n> >>> performance, accessing graph position and generation numbers in a\n> >>> commit-slab is more expensive than direct field accesses in 'struct\n> >>> commit' instances. Consequently, these patches increase the runtime\n> >>> of 'git merge-base --is-ancestor HEAD~50000 HEAD' in the linux\n> >>> repository from 0.630s to 0.940s.\n> >>>\n> >>\n> >> Thank you for checking performance. Performance penalty was something we\n> >> had discussed here [1]. \n> >>\n> >> Caching the commit slab results in local variables helped wonderfully in v2 [2].\n> >> For example, the runtime of 'git merge-base --is-ancestor HEAD~50000 HEAD'\n> >> in the linux repository increased from 0.762 to 0.767s. Since this is a\n> >> change of <1%, it is *no longer* a performance regression in my opinion.\n> > \n> > Interesting, I measured 0.870s with v2, still a notable increase from\n> > 0.630s.\n> \n> This is an interesting point. The --is-ancestor is critical to the\n> performance issue (as measured on my machine).\n> \n> For \"git merge-base HEAD~50000 HEAD\" on the Linux repo, I get\n> \n> v2.27.0:\n> real 0m0.515s\n> user 0m0.467s\n> sys 0m0.048s\n> \n> v2 series:\n> real 0m0.534s\n> user 0m0.481s\n> sys 0m0.053s\n\nI, too, see similarly small differences in this case.\n\n> With \"--is-ancestor\" I see the following:\n> \n> v2.27.0:\n> real 0m0.591s\n> user 0m0.539s\n> sys 0m0.052s\n> \n> v2 series:\n> real 0m0.773s\n> user 0m0.733s\n> sys 0m0.040s\n> \n> The --is-ancestor option [1] says\n> \n> Check if the first is an ancestor of the second\n> , and exit with status 0 if true, or with status\n> 1 if not. Errors are signaled by a non-zero status that\n> is not 1.\n> \n> [1] https://git-scm.com/docs/git-merge-base#Documentation/git-merge-base.txt---is-ancestor\n> \n> This _should_ be faster than \"git branch --contains HEAD~50000\",\n> but it is much much slower:\n> \n> $ time git branch --contains HEAD~50000\n> real 0m0.068s\n> user 0m0.061s\n> sys 0m0.008s\n> \n> So, there is definitely something going on that slows the\n> \"--is-ancestor\" path in this case. But, the solution is not\n> to halt the current patch (which likely has memory footprint\n> benefits when dealing with a lot of tree and blob objects)\n> and instead fix the underlying algorithm.\n\nOther, more common cases are affected as well, notably the simple 'git\nrev-list --topo-order':\n\n performance: 1.226479734 s: git command: /home/szeder/src/git/BUILDS/v2.27.0/bin/git rev-list --topo-order HEAD\n max RSS: 162400k\n \n performance: 1.741309536 s: git command: /home/szeder/src/git/git rev-list --topo-order HEAD\n max RSS: 169556k\n\nIs the supposed memory footprint reduction that large to justify this\nruntime increase?\n\n> Let's add that to the list of things to do.\n\nAnd to the commit messages.\n\n> >>> create mode 100644 contrib/coccinelle/generation.cocci\n> >>> create mode 100644 contrib/coccinelle/graph_pos.cocci\n> >>\n> >> I appreciate the Coccinelle scripts to help identify\n> >> automatic fixes for other topics in-flight. However,\n> >> I wonder if they would be better placed inside the\n> >> existing commit.cocci file?\n> >\n> > We add Coccinelle scripts to avoid undesirable code patterns entering\n> > our code base. That, however, is not the case here: this is a\n> > one-time conversion, and at the end of this series 'struct commit'\n> > won't have a 'generation' field anymore, so once it's merged the\n> > compiler will catch any new 'commit->generation' accesses. Therefore\n> > I don't think that these Coccinelle scripts should be added at all.\n> \n> I disagree. We _also_ add Coccinelle scripts when doing one-time\n> refactors to avoid logical merge conflicts with other topics in\n> flight. If someone else is working on a parallel topic that adds\n> references to graph_pos or generation member, then the scripts provide\n> an easy way for the maintainer to update those references in the merge\n> commit. Alternatively, the contributor could rebase on top of this\n> series and run the scripts themselves to fix their patches before\n> submission.\n> \n> For example, this was done carefully in the sha->object_id\n> conversion using contrib/coccinelle/object_id.cocci.\n\n'object_id.cocci' is not about sha->object_id conversions, but about\navoiding undesirable code patterns, e.g. we prefer oideq() over\n!oidcmp(), and the compiler, of course, can't help to catch that.\nCoccinelle scripts used for actual sha->object_id transformations were\nnot added to 'object_id.cocci', but were recorded only in the commit\nmessages for reference, see e.g. 9b56149996 (merge-recursive: convert\nstruct merge_file_info to object_id, 2016-06-24) and a couple of its\nancestors.\n\n"},{"id":"399791","messageId":"20200615162455.GA71506@syl.local","threadId":"53611","inReplyTo":"20200607193237.699335-1-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v2 0/4] Move generation, graph_pos to a slab","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-06-15T16:24:55Z","receivedAt":"2020-06-15T16:25:01Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Abhishek,\n\nI am so excited that you are working on this, and welcome to Git! This\nchange will make a meaningful difference for us at GitHub (who use\ncommit graphs extensively), and it sounds like they will even make a\nlarger difference with your later changes.\n\nI was out of the office last week, and so I hadn't gotten a chance to\nreview the first version of this series, but I'll review v2 now...\n\nOn Mon, Jun 08, 2020 at 01:02:33AM +0530, Abhishek Kumar wrote:\n> The struct commit is used in many contexts. However, members\n> `generation` and `graph_pos` are only used for commit graph related\n> operations and otherwise waste memory.\n\nThanks,\nTaylor\n"},{"id":"399792","messageId":"20200615162759.GB71506@syl.local","threadId":"53611","inReplyTo":"20200607193237.699335-2-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v2 1/4] commit-graph: introduce commit_graph_data_slab","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-06-15T16:27:59Z","receivedAt":"2020-06-15T16:28:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Jun 08, 2020 at 01:02:34AM +0530, Abhishek Kumar wrote:\n> The struct commit is used in many contexts. However, members\n> `generation` and `graph_pos` are only used for commit-graph related\n> operations and otherwise waste memory.\n>\n> As they are often accessed together, let's introduce struct\n> commit_graph_data and move them to a commit_graph_data slab.\n>\n> Signed-off-by: Abhishek Kumar \n> ---\n> commit-graph.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++\n> commit-graph.h | 10 ++++++++++\n> 2 files changed, 59 insertions(+)\n>\n> diff --git a/commit-graph.c b/commit-graph.c\n> index e3420ddcbf..7d887a6a2c 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -87,6 +87,55 @@ static int commit_pos_cmp(const void *va, const void *vb)\n> \t commit_pos_at(&commit_pos, b);\n> }\n>\n> +define_commit_slab(commit_graph_data_slab, struct commit_graph_data);\n> +static struct commit_graph_data_slab commit_graph_data_slab =\n> +\tCOMMIT_SLAB_INIT(1, commit_graph_data_slab);\n> +\n> +uint32_t commit_graph_position(const struct commit *c)\n> +{\n> +\tstruct commit_graph_data *data =\n> +\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n> +\n> +\treturn data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;\n> +}\n> +\n> +uint32_t commit_graph_generation(const struct commit *c)\n> +{\n> +\tstruct commit_graph_data *data =\n> +\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n> +\n> +\tif (!data)\n> +\t\treturn GENERATION_NUMBER_INFINITY;\n> +\tif (data->graph_pos == COMMIT_NOT_FROM_GRAPH)\n> +\t\treturn GENERATION_NUMBER_INFINITY;\n> +\n> +\treturn data->generation;\n> +}\n> +\n> +static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\n> +{\n> +\tuint32_t i = commit_graph_data_slab.slab_count, j;\n> +\tuint32_t slab_size = commit_graph_data_slab.slab_size;\n> +\tstruct commit_graph_data *data =\n> +\t\tcommit_graph_data_slab_at(&commit_graph_data_slab, c);\n> +\n> +\t/*\n> +\t * commit-slab initializes elements with zero, overwrite this with\n> +\t * COMMIT_NOT_FROM_GRAPH for graph_pos.\n> +\t *\n> +\t * We avoid the cost of initializing `generation` as generation\n> +\t * number would be GENERATION_NUMBER_INFINITY if graph position\n> +\t * is COMMIT_NOT_FROM_GRAPH.\n> +\t */\n> +\tfor (; i < commit_graph_data_slab.slab_count; i++) {\n> +\t\tfor (j = 0; j < slab_size; j++) {\n> +\t\t\tcommit_graph_data_slab.slab[i][j].graph_pos = COMMIT_NOT_FROM_GRAPH;\n> +\t\t}\n> +\t}\n> +\n> +\treturn data;\n> +}\n> +\n\nIt looks like this function ('commit_graph_data_at') is unused in this\npatch. No big deal, especially since I can see that you are using it in\nthe second patch, but I think that you should remove it from this patch\nand instead introduce it there.\n\nIn fact, this causes a build error (with 'make DEVELOPER=1') because of\n'-Wunused-function'. It's good practice to \"git rebase -x 'make\nDEVELOPER=1' origin/master\" before sending.\n\n> static int commit_gen_cmp(const void *va, const void *vb)\n> {\n> \tconst struct commit *a = *(const struct commit **)va;\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 4212766a4f..9d22f98f44 100644\n> --- a/commit-graph.h\n> +++ b/commit-graph.h\n> @@ -137,4 +137,14 @@ void free_commit_graph(struct commit_graph *);\n> */\n> void disable_commit_graph(struct repository *r);\n>\n> +struct commit_graph_data {\n> +\tuint32_t graph_pos;\n> +\tuint32_t generation;\n> +};\n> +\n> +/*\n> + * Commits should be parsed before accessing generation, graph positions.\n> + */\n> +uint32_t commit_graph_generation(const struct commit *);\n> +uint32_t commit_graph_position(const struct commit *);\n> #endif\n> --\n> 2.27.0\n\nThanks,\nTaylor\n"},{"id":"399793","messageId":"20200615163159.GC71506@syl.local","threadId":"53611","inReplyTo":"85zh9dsemi.fsf@gmail.com","subject":"Re: [GSOC Patch v2 3/4] commit-graph: use generation directly when writing commit-graph","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-06-15T16:31:59Z","receivedAt":"2020-06-15T16:32:03Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Jun 08, 2020 at 06:31:49PM +0200, Jakub Narębski wrote:\n> Abhishek Kumar writes:\n>\n> > commit_graph_generation() returns GENERATION_NUMBER_INFINITY if the\n> > graph position for commit is COMMIT_NOT_FROM_GRAPH.\n> >\n> > While this is true when reading from a commit graph, no graph positions\n> > are associated with a commit when writing a commit graph. Therefore, the\n> > helper incorrectly returns GENERATION_NUMBER_INFINITY despite having a\n> > finite generation number.\n> >\n> > Let's fix this by using generation number directly when writing a commit\n> > graph.\n>\n> I think that to avoid having non-working patch (which can cause problems\n> when bisecting), it would be a better idea to switch the order of\n> patches 2 and 3. This way we won't have incorrect behaviour.\n\nYup... agreed (with the additional caveat that the unused function in\nthe first patch also be moved into this new--larger--patch).\n\n> >\n> > Signed-off-by: Abhishek Kumar \n> > ---\n> > commit-graph.c | 13 ++++++++-----\n> > 1 file changed, 8 insertions(+), 5 deletions(-)\n> >\n> > diff --git a/commit-graph.c b/commit-graph.c\n> > index f7cca4def4..0dc79e7c90 100644\n> > --- a/commit-graph.c\n> > +++ b/commit-graph.c\n> > @@ -1070,7 +1070,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n> > \t\telse\n> > \t\t\tpackedDate[0] = 0;\n> >\n> > -\t\tpackedDate[0] |= htonl(commit_graph_generation((*list)) << 2);\n> > +\t\tpackedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);\n> >\n>\n> All right.\n>\n> > \t\tpackedDate[1] = htonl((*list)->date);\n> > \t\thashwrite(f, packedDate, 8);\n> > @@ -1301,9 +1301,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> > \t\t\t\t\t_(\"Computing commit graph generation numbers\"),\n> > \t\t\t\t\tctx->commits.nr);\n> > \tfor (i = 0; i < ctx->commits.nr; i++) {\n> > +\t\tuint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n> > +\n> > \t\tdisplay_progress(ctx->progress, i + 1);\n> > -\t\tif (commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_INFINITY &&\n> > -\t\t commit_graph_generation(ctx->commits.list[i]) != GENERATION_NUMBER_ZERO)\n> > +\t\tif (generation != GENERATION_NUMBER_INFINITY &&\n> > +\t\t generation != GENERATION_NUMBER_ZERO)\n> > \t\t\tcontinue;\n> >\n>\n> All right; this also introduces local variable to avoid accessing the\n> slab twice^W four times...\n>\n> > \t\tcommit_list_insert(ctx->commits.list[i], &list);\n> > @@ -1314,8 +1316,9 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n> > \t\t\tuint32_t max_generation = 0;\n> >\n> > \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n> > -\t\t\t\tif (commit_graph_generation(parent->item) == GENERATION_NUMBER_INFINITY ||\n> > -\t\t\t\t commit_graph_generation(parent->item) == GENERATION_NUMBER_ZERO) {\n> > +\n> > +\t\t\t\tif (generation == GENERATION_NUMBER_INFINITY ||\n> > +\t\t\t\t generation == GENERATION_NUMBER_ZERO) {\n> > \t\t\t\t\tall_parents_computed = 0;\n> > \t\t\t\t\tcommit_list_insert(parent->item, &list);\n> > \t\t\t\t\tbreak;\n>\n> ... which is then used here.\n>\n> Best,\n> --\n> Jakub Narębski\nThanks,\nTaylor\n"},{"id":"399962","messageId":"20200617091411.14650-1-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200604072759.19142-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v4 0/4] Move generation, graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:14:07Z","receivedAt":"2020-06-17T09:16:18Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct commit is used in many contexts. However, members\n`generation` and `graph_pos` are only used for commit graph related\noperations and otherwise waste memory.\n\nThis wastage would have been more pronounced as we transition to\ngeneration nuber v2, which uses 64-bit generation number instead of\ncurrent 32-bits.\n\nWhile the overall test suite runs as fast as master\n(series: 26m48s, master: 27m34s, faster by 2.87%), certain commands\nlike `git merge-base --is-ancestor` were slowed by 40% as discovered\nby Szeder Gábor [1]. After minimizing commit-slab access, the slow down\npersists but is closer to 20%.\n\nDerrick Stolee believes the slow down is attributable to the underlying\nalgorithm rather than the slowness of commit-slab access [2] and we will\nfollow-up in a later series.\n\nAbhishek Kumar (4):\n object: drop parsed_object_pool->commit_count\n commit-graph: introduce commit_graph_data_slab\n commit: move members graph_pos, generation to a slab\n commit-graph: minimize commit_graph_data_slab access\n\n alloc.c | 18 +++--\n alloc.h | 2 +-\n blame.c | 2 +-\n blob.c | 2 +-\n bloom.c | 7 +-\n builtin/commit-graph.c | 2 +-\n builtin/fsck.c | 2 +-\n commit-graph.c | 130 ++++++++++++++++++++++++--------\n commit-graph.h | 10 +++\n commit-reach.c | 69 ++++++++++-------\n commit.c | 12 +--\n commit.h | 2 -\n contrib/coccinelle/commit.cocci | 18 +++++\n object.c | 4 +-\n object.h | 3 +-\n refs.c | 2 +-\n revision.c | 20 +++--\n t/helper/test-reach.c | 2 +-\n tag.c | 2 +-\n tree.c | 2 +-\n 20 files changed, 217 insertions(+), 94 deletions(-)\n\n-- \n2.27.0\n\nChanges in v4:\n- Fix segfault while initializing commit_graph_data_slab.\n- Fix the \"commit index should have unique values\" more cleanly\n\nChanges in v3:\n- Introduce alloc commit to fix the failing diff-submodule test.\n- Elaborate on perforamnce and the slow down in commit message\n\nChanges in v2:\n- Introduce struct commit_graph_data\n- Merge `graph_pos`, `generation` slabs into a single,\n `commit_graph_data` slab.\n- Use graph position for an intermediate check for generation, saving\n the cost of initializing generation numbers.\n- Add an follow-up patch caching results of slab access in local\n variables.\n- Move coccinelle transformation to commit.coccinelle instead of\n creating new scripts.\n- Elaborate on removing default values from init_commit_node().\n- Revert moving macro constants (e.g. COMMIT_NOT_FROM_GRAPH,\n GENERATION_NUMBER_ZERO0 from commit.h to commit-graph.h\n"},{"id":"399963","messageId":"20200617091411.14650-2-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200617091411.14650-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v4 1/4] object: drop parsed_object_pool->commit_count","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:14:08Z","receivedAt":"2020-06-17T09:16:25Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"14ba97f8 (alloc: allow arbitrary repositories for alloc functions,\n2018-05-15) introduced parsed_object_pool->commit_count to keep count of\ncommits per repository and was used to assign commit->index.\n\nHowever, commit-slab code requires commit->index values to be unique\nand a global count would be correct, rather than a per-repo count.\n\nLet's introduce a static counter variable, `parsed_commits_count` to\nkeep track of parsed commits so far.\n\nAs commit_count has no use anymore, let's also drop it from the struct.\n\nSigned-off-by: Abhishek Kumar \n---\n alloc.c | 16 +++++++++++-----\n alloc.h | 2 +-\n blob.c | 2 +-\n builtin/commit-graph.c | 2 +-\n builtin/fsck.c | 2 +-\n commit.c | 4 ++--\n object.c | 4 ++--\n object.h | 3 +--\n refs.c | 2 +-\n t/helper/test-reach.c | 2 +-\n tag.c | 2 +-\n tree.c | 2 +-\n 12 files changed, 24 insertions(+), 19 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 1c64c4dd16..99fa934b32 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -99,15 +99,21 @@ void *alloc_object_node(struct repository *r)\n \treturn obj;\n }\n \n-static unsigned int alloc_commit_index(struct repository *r)\n+/*\n+ * The returned count is to be used as an index into commit slabs,\n+ * that are *NOT* maintained per repository, and that is why a single\n+ * global counter is used.\n+ */\n+static unsigned int alloc_commit_index(void)\n {\n-\treturn r->parsed_objects->commit_count++;\n+\tstatic unsigned int parsed_commits_count;\n+\treturn parsed_commits_count++;\n }\n \n-void init_commit_node(struct repository *r, struct commit *c)\n+void init_commit_node(struct commit *c)\n {\n \tc->object.type = OBJ_COMMIT;\n-\tc->index = alloc_commit_index(r);\n+\tc->index = alloc_commit_index();\n \tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n \tc->generation = GENERATION_NUMBER_INFINITY;\n }\n@@ -115,7 +121,7 @@ void init_commit_node(struct repository *r, struct commit *c)\n void *alloc_commit_node(struct repository *r)\n {\n \tstruct commit *c = alloc_node(r->parsed_objects->commit_state, sizeof(struct commit));\n-\tinit_commit_node(r, c);\n+\tinit_commit_node(c);\n \treturn c;\n }\n \ndiff --git a/alloc.h b/alloc.h\nindex ed1071c11e..371d388b55 100644\n--- a/alloc.h\n+++ b/alloc.h\n@@ -9,7 +9,7 @@ struct repository;\n \n void *alloc_blob_node(struct repository *r);\n void *alloc_tree_node(struct repository *r);\n-void init_commit_node(struct repository *r, struct commit *c);\n+void init_commit_node(struct commit *c);\n void *alloc_commit_node(struct repository *r);\n void *alloc_tag_node(struct repository *r);\n void *alloc_object_node(struct repository *r);\ndiff --git a/blob.c b/blob.c\nindex 36f9abda19..182718aba9 100644\n--- a/blob.c\n+++ b/blob.c\n@@ -10,7 +10,7 @@ struct blob *lookup_blob(struct repository *r, const struct object_id *oid)\n \tstruct object *obj = lookup_object(r, oid);\n \tif (!obj)\n \t\treturn create_object(r, oid, alloc_blob_node(r));\n-\treturn object_as_type(r, obj, OBJ_BLOB, 0);\n+\treturn object_as_type(obj, OBJ_BLOB, 0);\n }\n \n int parse_blob_buffer(struct blob *item, void *buffer, unsigned long size)\ndiff --git a/builtin/commit-graph.c b/builtin/commit-graph.c\nindex 75455da138..f6797e2a9f 100644\n--- a/builtin/commit-graph.c\n+++ b/builtin/commit-graph.c\n@@ -154,7 +154,7 @@ static int read_one_commit(struct oidset *commits, struct progress *progress,\n \t\t\t NULL, 0);\n \tif (!result)\n \t\treturn error(_(\"invalid object: %s\"), hash);\n-\telse if (object_as_type(the_repository, result, OBJ_COMMIT, 1))\n+\telse if (object_as_type(result, OBJ_COMMIT, 1))\n \t\toidset_insert(commits, &result->oid);\n \n \tdisplay_progress(progress, oidset_size(commits));\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex f02cbdb439..b2cef01389 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -241,7 +241,7 @@ static void mark_unreachable_referents(const struct object_id *oid)\n \t\tenum object_type type = oid_object_info(the_repository,\n \t\t\t\t\t\t\t&obj->oid, NULL);\n \t\tif (type > 0)\n-\t\t\tobject_as_type(the_repository, obj, type, 0);\n+\t\t\tobject_as_type(obj, type, 0);\n \t}\n \n \toptions.walk = mark_used;\ndiff --git a/commit.c b/commit.c\nindex 87686a7055..b30875e66b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -37,7 +37,7 @@ struct commit *lookup_commit_reference_gently(struct repository *r,\n \n \tif (!obj)\n \t\treturn NULL;\n-\treturn object_as_type(r, obj, OBJ_COMMIT, quiet);\n+\treturn object_as_type(obj, OBJ_COMMIT, quiet);\n }\n \n struct commit *lookup_commit_reference(struct repository *r, const struct object_id *oid)\n@@ -62,7 +62,7 @@ struct commit *lookup_commit(struct repository *r, const struct object_id *oid)\n \tstruct object *obj = lookup_object(r, oid);\n \tif (!obj)\n \t\treturn create_object(r, oid, alloc_commit_node(r));\n-\treturn object_as_type(r, obj, OBJ_COMMIT, 0);\n+\treturn object_as_type(obj, OBJ_COMMIT, 0);\n }\n \n struct commit *lookup_commit_reference_by_name(const char *name)\ndiff --git a/object.c b/object.c\nindex 794c86650e..3257518656 100644\n--- a/object.c\n+++ b/object.c\n@@ -157,13 +157,13 @@ void *create_object(struct repository *r, const struct object_id *oid, void *o)\n \treturn obj;\n }\n \n-void *object_as_type(struct repository *r, struct object *obj, enum object_type type, int quiet)\n+void *object_as_type(struct object *obj, enum object_type type, int quiet)\n {\n \tif (obj->type == type)\n \t\treturn obj;\n \telse if (obj->type == OBJ_NONE) {\n \t\tif (type == OBJ_COMMIT)\n-\t\t\tinit_commit_node(r, (struct commit *) obj);\n+\t\t\tinit_commit_node((struct commit *) obj);\n \t\telse\n \t\t\tobj->type = type;\n \t\treturn obj;\ndiff --git a/object.h b/object.h\nindex b22328b838..532d7d7f28 100644\n--- a/object.h\n+++ b/object.h\n@@ -15,7 +15,6 @@ struct parsed_object_pool {\n \tstruct alloc_state *commit_state;\n \tstruct alloc_state *tag_state;\n \tstruct alloc_state *object_state;\n-\tunsigned commit_count;\n \n \t/* parent substitutions from .git/info/grafts and .git/shallow */\n \tstruct commit_graft **grafts;\n@@ -121,7 +120,7 @@ struct object *lookup_object(struct repository *r, const struct object_id *oid);\n \n void *create_object(struct repository *r, const struct object_id *oid, void *obj);\n \n-void *object_as_type(struct repository *r, struct object *obj, enum object_type type, int quiet);\n+void *object_as_type(struct object *obj, enum object_type type, int quiet);\n \n /*\n * Returns the object, having parsed it to find out what it is.\ndiff --git a/refs.c b/refs.c\nindex 224ff66c7b..1f551dd279 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -339,7 +339,7 @@ enum peel_status peel_object(const struct object_id *name, struct object_id *oid\n \n \tif (o->type == OBJ_NONE) {\n \t\tint type = oid_object_info(the_repository, name, NULL);\n-\t\tif (type < 0 || !object_as_type(the_repository, o, type, 0))\n+\t\tif (type < 0 || !object_as_type(o, type, 0))\n \t\t\treturn PEEL_INVALID;\n \t}\n \ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex a0272178b7..ccf837cb33 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -67,7 +67,7 @@ int cmd__reach(int ac, const char **av)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\n \t\t\t buf.buf, oid_to_hex(&oid));\n \n-\t\tc = object_as_type(r, peeled, OBJ_COMMIT, 0);\n+\t\tc = object_as_type(peeled, OBJ_COMMIT, 0);\n \n \t\tif (!c)\n \t\t\tdie(\"failed to load commit for input %s resulting in oid %s\\n\",\ndiff --git a/tag.c b/tag.c\nindex 71b544467e..1ed2684e45 100644\n--- a/tag.c\n+++ b/tag.c\n@@ -103,7 +103,7 @@ struct tag *lookup_tag(struct repository *r, const struct object_id *oid)\n \tstruct object *obj = lookup_object(r, oid);\n \tif (!obj)\n \t\treturn create_object(r, oid, alloc_tag_node(r));\n-\treturn object_as_type(r, obj, OBJ_TAG, 0);\n+\treturn object_as_type(obj, OBJ_TAG, 0);\n }\n \n static timestamp_t parse_tag_date(const char *buf, const char *tail)\ndiff --git a/tree.c b/tree.c\nindex 1466bcc6a8..e76517f6b1 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -200,7 +200,7 @@ struct tree *lookup_tree(struct repository *r, const struct object_id *oid)\n \tstruct object *obj = lookup_object(r, oid);\n \tif (!obj)\n \t\treturn create_object(r, oid, alloc_tree_node(r));\n-\treturn object_as_type(r, obj, OBJ_TREE, 0);\n+\treturn object_as_type(obj, OBJ_TREE, 0);\n }\n \n int parse_tree_buffer(struct tree *item, void *buffer, unsigned long size)\n-- \n2.27.0\n\n"},{"id":"399964","messageId":"20200617091411.14650-3-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200617091411.14650-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v4 2/4] commit-graph: introduce commit_graph_data_slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:14:09Z","receivedAt":"2020-06-17T09:16:26Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"The struct commit is used in many contexts. However, members\n`generation` and `graph_pos` are only used for commit-graph related\noperations and otherwise waste memory.\n\nThis wastage would have been more pronounced as we transition to\ngeneration number v2, which uses 64-bit generation number instead of\ncurrent 32-bits.\n\nAs they are often accessed together, let's introduce struct\ncommit_graph_data and move them to a commit_graph_data slab.\n\nWhile the overall test suite runs just as fast as master,\n(series: 26m48s, master: 27m34s, faster by 2.87%), certain commands\nlike `git merge-base --is-ancestor` were slowed by 40% as discovered\nby Szeder Gábor [1]. After minimizing commit-slab access, the slow down\npersists but is closer to 20%.\n\nDerrick Stolee believes the slow down is attributable to the underlying\nalgorithm rather than the slowness of commit-slab access [2] and we will\nfollow-up in a later series.\n\n[1]: https://lore.kernel.org/git/20200607195347.GA8232@szeder.dev/\n[2]: https://lore.kernel.org/git/13db757a-9412-7f1e-805c-8a028c4ab2b1@gmail.com/\n\nSigned-off-by: Abhishek Kumar \n---\n\nOn linux.git with HEAD at 08bf1a27 (Merge tag 'powerpc-5.8-2' of\ngit://git.kernel.org/pub/scm/linux/kernel/git/powerpc/linux,\n2020-06-13):\n\n`git merge-base --is-ancestor HEAD~50000 HEAD`\nTime (master): 0.787s\nTime (series): 0.927s\nChange: 17.79% (slower)\n\nMax RSS (master): 177694kb\nMax RSS (series): 177707kb\nChange: 0.01% (more)\n\n`git gc`\nTime (master): 3m55s\nTime (series): 3m38s\nChange: 7.23% (faster)\n\nMax RSS (master): 4889868kb\nMax RSS (series): 4911960kb\nChange: 0.45% (more)\n\nEarlier implementation of commit_graph_data_at() was incorrect, as we\nused to iterate from old slab count to new slab count - assuming all\nintermediate slabs are allocated. This is incorrect as the slabs are\nallocated only when there's a corresponding commit.\n\nIt now makes *two slab accesses* in the worst case, but it's okay since\nthe worst case occurs once nearly every (512kb / 8b) commits.\n\n commit-graph.c | 78 +++++++++++++++++++++++++++++++++++++++++++-------\n commit-graph.h | 10 +++++++\n 2 files changed, 78 insertions(+), 10 deletions(-)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 2ff042fbf4..8ad7d202b2 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -87,6 +87,58 @@ static int commit_pos_cmp(const void *va, const void *vb)\n \t commit_pos_at(&commit_pos, b);\n }\n \n+define_commit_slab(commit_graph_data_slab, struct commit_graph_data);\n+static struct commit_graph_data_slab commit_graph_data_slab =\n+\tCOMMIT_SLAB_INIT(1, commit_graph_data_slab);\n+\n+uint32_t commit_graph_position(const struct commit *c)\n+{\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n+\n+\treturn data ? data->graph_pos : COMMIT_NOT_FROM_GRAPH;\n+}\n+\n+uint32_t commit_graph_generation(const struct commit *c)\n+{\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n+\n+\tif (!data)\n+\t\treturn GENERATION_NUMBER_INFINITY;\n+\telse if (data->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\t\treturn GENERATION_NUMBER_INFINITY;\n+\n+\treturn data->generation;\n+}\n+\n+static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\n+{\n+\tunsigned int i, nth_slab;\n+\tstruct commit_graph_data *data =\n+\t\tcommit_graph_data_slab_peek(&commit_graph_data_slab, c);\n+\n+\tif (data)\n+\t\treturn data;\n+\n+\tnth_slab = c->index / commit_graph_data_slab.slab_size;\n+\tdata = commit_graph_data_slab_at(&commit_graph_data_slab, c);\n+\n+\t/*\n+\t * commit-slab initializes elements with zero, overwrite this with\n+\t * COMMIT_NOT_FROM_GRAPH for graph_pos.\n+\t *\n+\t * We avoid initializing generation with checking if graph position\n+\t * is not COMMIT_NOT_FROM_GRAPH.\n+\t */\n+\tfor (i = 0; i < commit_graph_data_slab.slab_size; i++) {\n+\t\tcommit_graph_data_slab.slab[nth_slab][i].graph_pos =\n+\t\t\tCOMMIT_NOT_FROM_GRAPH;\n+\t}\n+\n+\treturn data;\n+}\n+\n static int commit_gen_cmp(const void *va, const void *vb)\n {\n \tconst struct commit *a = *(const struct commit **)va;\n@@ -1020,7 +1072,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,\n \t\telse\n \t\t\tpackedDate[0] = 0;\n \n-\t\tpackedDate[0] |= htonl((*list)->generation << 2);\n+\t\tpackedDate[0] |= htonl(commit_graph_data_at(*list)->generation << 2);\n \n \t\tpackedDate[1] = htonl((*list)->date);\n \t\thashwrite(f, packedDate, 8);\n@@ -1251,9 +1303,11 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\t\t\t_(\"Computing commit graph generation numbers\"),\n \t\t\t\t\tctx->commits.nr);\n \tfor (i = 0; i < ctx->commits.nr; i++) {\n+\t\tuint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n+\n \t\tdisplay_progress(ctx->progress, i + 1);\n-\t\tif (ctx->commits.list[i]->generation != GENERATION_NUMBER_INFINITY &&\n-\t\t ctx->commits.list[i]->generation != GENERATION_NUMBER_ZERO)\n+\t\tif (generation != GENERATION_NUMBER_INFINITY &&\n+\t\t generation != GENERATION_NUMBER_ZERO)\n \t\t\tcontinue;\n \n \t\tcommit_list_insert(ctx->commits.list[i], &list);\n@@ -1264,22 +1318,26 @@ static void compute_generation_numbers(struct write_commit_graph_context *ctx)\n \t\t\tuint32_t max_generation = 0;\n \n \t\t\tfor (parent = current->parents; parent; parent = parent->next) {\n-\t\t\t\tif (parent->item->generation == GENERATION_NUMBER_INFINITY ||\n-\t\t\t\t parent->item->generation == GENERATION_NUMBER_ZERO) {\n+\t\t\t\tgeneration = commit_graph_data_at(parent->item)->generation;\n+\n+\t\t\t\tif (generation == GENERATION_NUMBER_INFINITY ||\n+\t\t\t\t generation == GENERATION_NUMBER_ZERO) {\n \t\t\t\t\tall_parents_computed = 0;\n \t\t\t\t\tcommit_list_insert(parent->item, &list);\n \t\t\t\t\tbreak;\n-\t\t\t\t} else if (parent->item->generation > max_generation) {\n-\t\t\t\t\tmax_generation = parent->item->generation;\n+\t\t\t\t} else if (generation > max_generation) {\n+\t\t\t\t\tmax_generation = generation;\n \t\t\t\t}\n \t\t\t}\n \n \t\t\tif (all_parents_computed) {\n-\t\t\t\tcurrent->generation = max_generation + 1;\n+\t\t\t\tstruct commit_graph_data *data = commit_graph_data_at(current);\n+\n+\t\t\t\tdata->generation = max_generation + 1;\n \t\t\t\tpop_commit(&list);\n \n-\t\t\t\tif (current->generation > GENERATION_NUMBER_MAX)\n-\t\t\t\t\tcurrent->generation = GENERATION_NUMBER_MAX;\n+\t\t\t\tif (data->generation > GENERATION_NUMBER_MAX)\n+\t\t\t\t\tdata->generation = GENERATION_NUMBER_MAX;\n \t\t\t}\n \t\t}\n \t}\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 3ba0da1e5f..28f89cdf3e 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -135,4 +135,14 @@ void free_commit_graph(struct commit_graph *);\n */\n void disable_commit_graph(struct repository *r);\n \n+struct commit_graph_data {\n+\tuint32_t graph_pos;\n+\tuint32_t generation;\n+};\n+\n+/*\n+ * Commits should be parsed before accessing generation, graph positions.\n+ */\n+uint32_t commit_graph_generation(const struct commit *);\n+uint32_t commit_graph_position(const struct commit *);\n #endif\n-- \n2.27.0\n\n"},{"id":"399965","messageId":"20200617091411.14650-4-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200617091411.14650-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v4 3/4] commit: move members graph_pos, generation to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:14:10Z","receivedAt":"2020-06-17T09:16:33Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"We remove members `graph_pos` and `generation` from the struct commit.\nThe default assignments in init_commit_node() are no longer valid,\nwhich is fine as the slab helpers return appropriate default values and\nthe assignments are removed.\n\nWe will replace existing use of commit->generation and commit->graph_pos\nby commit_graph_data_slab helpers using\n`contrib/coccinelle/commit.cocci'.\n\nSigned-off-by: Abhishek Kumar \n---\n alloc.c | 2 --\n blame.c | 2 +-\n bloom.c | 6 ++--\n commit-graph.c | 40 +++++++++++++-------------\n commit-reach.c | 50 ++++++++++++++++-----------------\n commit.c | 6 ++--\n commit.h | 2 --\n contrib/coccinelle/commit.cocci | 18 ++++++++++++\n revision.c | 16 +++++------\n 9 files changed, 78 insertions(+), 64 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 99fa934b32..957a0af362 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -114,8 +114,6 @@ void init_commit_node(struct commit *c)\n {\n \tc->object.type = OBJ_COMMIT;\n \tc->index = alloc_commit_index();\n-\tc->graph_pos = COMMIT_NOT_FROM_GRAPH;\n-\tc->generation = GENERATION_NUMBER_INFINITY;\n }\n \n void *alloc_commit_node(struct repository *r)\ndiff --git a/blame.c b/blame.c\nindex da7e28800e..82fa16d658 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -1272,7 +1272,7 @@ static int maybe_changed_path(struct repository *r,\n \tif (!bd)\n \t\treturn 1;\n \n-\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (commit_graph_generation(origin->commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn 1;\n \n \tfilter = get_bloom_filter(r, origin->commit, 0);\ndiff --git a/bloom.c b/bloom.c\nindex 6c7611847a..3062aafaba 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -34,14 +34,14 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n {\n \tuint32_t lex_pos, start_index, end_index;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (commit_graph_position(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n \tif (!g->chunk_bloom_indexes)\n \t\treturn 0;\n \n-\tlex_pos = c->graph_pos - g->num_commits_in_base;\n+\tlex_pos = commit_graph_position(c) - g->num_commits_in_base;\n \n \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n \n@@ -193,7 +193,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \n \tif (!filter->data) {\n \t\tload_commit_graph_info(r, c);\n-\t\tif (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&\n+\t\tif (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&\n \t\t\tr->objects->commit_graph->chunk_bloom_indexes) {\n \t\t\tif (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))\n \t\t\t\treturn filter;\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 8ad7d202b2..14cc7e931c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -145,9 +145,9 @@ static int commit_gen_cmp(const void *va, const void *vb)\n \tconst struct commit *b = *(const struct commit **)vb;\n \n \t/* lower generation commits first */\n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn -1;\n-\telse if (a->generation > b->generation)\n+\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn 1;\n \n \t/* use date as a heuristic when generations are equal */\n@@ -722,7 +722,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n \tc = lookup_commit(r, &oid);\n \tif (!c)\n \t\tdie(_(\"could not find commit %s\"), oid_to_hex(&oid));\n-\tc->graph_pos = pos;\n+\tcommit_graph_data_at(c)->graph_pos = pos;\n \treturn &commit_list_insert(c, pptr)->next;\n }\n \n@@ -736,8 +736,8 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n-\titem->graph_pos = pos;\n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tcommit_graph_data_at(item)->graph_pos = pos;\n+\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n }\n \n static inline void set_commit_tree(struct commit *c, struct tree *t)\n@@ -766,7 +766,7 @@ static int fill_commit_in_graph(struct repository *r,\n \t * Store the \"full\" position, but then use the\n \t * \"local\" position for the rest of the calculation.\n \t */\n-\titem->graph_pos = pos;\n+\tcommit_graph_data_at(item)->graph_pos = pos;\n \tlex_index = pos - g->num_commits_in_base;\n \n \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n@@ -779,7 +779,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n \titem->date = (timestamp_t)((date_high << 32) | date_low);\n \n-\titem->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n \n \tpptr = &item->parents;\n \n@@ -811,8 +811,8 @@ static int fill_commit_in_graph(struct repository *r,\n \n static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n {\n-\tif (item->graph_pos != COMMIT_NOT_FROM_GRAPH) {\n-\t\t*pos = item->graph_pos;\n+\tif (commit_graph_position(item) != COMMIT_NOT_FROM_GRAPH) {\n+\t\t*pos = commit_graph_position(item);\n \t\treturn 1;\n \t} else {\n \t\tstruct commit_graph *cur_g = g;\n@@ -868,11 +868,11 @@ static struct tree *load_tree_for_commit(struct repository *r,\n \tstruct object_id oid;\n \tconst unsigned char *commit_data;\n \n-\twhile (c->graph_pos < g->num_commits_in_base)\n+\twhile (commit_graph_position(c) < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \tcommit_data = g->chunk_commit_data +\n-\t\t\tGRAPH_DATA_WIDTH * (c->graph_pos - g->num_commits_in_base);\n+\t\t\tGRAPH_DATA_WIDTH * (commit_graph_position(c) - g->num_commits_in_base);\n \n \thashcpy(oid.hash, commit_data);\n \tset_commit_tree(c, lookup_tree(r, &oid));\n@@ -886,7 +886,7 @@ static struct tree *get_commit_tree_in_graph_one(struct repository *r,\n {\n \tif (c->maybe_tree)\n \t\treturn c->maybe_tree;\n-\tif (c->graph_pos == COMMIT_NOT_FROM_GRAPH)\n+\tif (commit_graph_position(c) == COMMIT_NOT_FROM_GRAPH)\n \t\tBUG(\"get_commit_tree_in_graph_one called from non-commit-graph commit\");\n \n \treturn load_tree_for_commit(r, g, (struct commit *)c);\n@@ -1271,7 +1271,7 @@ static void close_reachable(struct write_commit_graph_context *ctx)\n \t\t\tcontinue;\n \t\tif (ctx->split) {\n \t\t\tif ((!parse_commit(commit) &&\n-\t\t\t commit->graph_pos == COMMIT_NOT_FROM_GRAPH) ||\n+\t\t\t commit_graph_position(commit) == COMMIT_NOT_FROM_GRAPH) ||\n \t\t\t flags == COMMIT_GRAPH_SPLIT_REPLACE)\n \t\t\t\tadd_missing_parents(ctx, commit);\n \t\t} else if (!parse_commit_no_graph(commit))\n@@ -1516,7 +1516,7 @@ static uint32_t count_distinct_commits(struct write_commit_graph_context *ctx)\n \t\t\tif (ctx->split) {\n \t\t\t\tstruct commit *c = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n-\t\t\t\tif (!c || c->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t\t\tif (!c || commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH)\n \t\t\t\t\tcontinue;\n \t\t\t}\n \n@@ -1550,7 +1550,7 @@ static void copy_oids_to_commits(struct write_commit_graph_context *ctx)\n \t\tctx->commits.list[ctx->commits.nr] = lookup_commit(ctx->r, &ctx->oids.list[i]);\n \n \t\tif (ctx->split && flags != COMMIT_GRAPH_SPLIT_REPLACE &&\n-\t\t ctx->commits.list[ctx->commits.nr]->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\t\t commit_graph_position(ctx->commits.list[ctx->commits.nr]) != COMMIT_NOT_FROM_GRAPH)\n \t\t\tcontinue;\n \n \t\tif (ctx->split && flags == COMMIT_GRAPH_SPLIT_REPLACE)\n@@ -2337,8 +2337,8 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n \n-\t\t\tif (graph_parents->item->generation > max_generation)\n-\t\t\t\tmax_generation = graph_parents->item->generation;\n+\t\t\tif (commit_graph_generation(graph_parents->item) > max_generation)\n+\t\t\t\tmax_generation = commit_graph_generation(graph_parents->item);\n \n \t\t\tgraph_parents = graph_parents->next;\n \t\t\todb_parents = odb_parents->next;\n@@ -2348,7 +2348,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\tgraph_report(_(\"commit-graph parent list for commit %s terminates early\"),\n \t\t\t\t oid_to_hex(&cur_oid));\n \n-\t\tif (!graph_commit->generation) {\n+\t\tif (!commit_graph_generation(graph_commit)) {\n \t\t\tif (generation_zero == GENERATION_NUMBER_EXISTS)\n \t\t\t\tgraph_report(_(\"commit-graph has generation number zero for commit %s, but non-zero elsewhere\"),\n \t\t\t\t\t oid_to_hex(&cur_oid));\n@@ -2368,10 +2368,10 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tif (max_generation == GENERATION_NUMBER_MAX)\n \t\t\tmax_generation--;\n \n-\t\tif (graph_commit->generation != max_generation + 1)\n+\t\tif (commit_graph_generation(graph_commit) != max_generation + 1)\n \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n \t\t\t\t oid_to_hex(&cur_oid),\n-\t\t\t\t graph_commit->generation,\n+\t\t\t\t commit_graph_generation(graph_commit),\n \t\t\t\t max_generation + 1);\n \n \t\tif (graph_commit->date != odb_commit->date)\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 4ca7e706a1..3b2f863f5f 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -59,13 +59,13 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n \t\tstruct commit_list *parents;\n \t\tint flags;\n \n-\t\tif (min_generation && commit->generation > last_gen)\n+\t\tif (min_generation && commit_graph_generation(commit) > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit->generation, last_gen,\n+\t\t\t commit_graph_generation(commit), last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit->generation;\n+\t\tlast_gen = commit_graph_generation(commit);\n \n-\t\tif (commit->generation < min_generation)\n+\t\tif (commit_graph_generation(commit) < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -176,7 +176,7 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\trepo_parse_commit(r, array[i]);\n \tfor (i = 0; i < cnt; i++) {\n \t\tstruct commit_list *common;\n-\t\tuint32_t min_generation = array[i]->generation;\n+\t\tuint32_t min_generation = commit_graph_generation(array[i]);\n \n \t\tif (redundant[i])\n \t\t\tcontinue;\n@@ -186,8 +186,8 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\t\tfilled_index[filled] = j;\n \t\t\twork[filled++] = array[j];\n \n-\t\t\tif (array[j]->generation < min_generation)\n-\t\t\t\tmin_generation = array[j]->generation;\n+\t\t\tif (commit_graph_generation(array[j]) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(array[j]);\n \t\t}\n \t\tcommon = paint_down_to_common(r, array[i], filled,\n \t\t\t\t\t work, min_generation);\n@@ -323,16 +323,16 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n \tfor (i = 0; i < nr_reference; i++) {\n \t\tif (repo_parse_commit(r, reference[i]))\n \t\t\treturn ret;\n-\t\tif (reference[i]->generation < min_generation)\n-\t\t\tmin_generation = reference[i]->generation;\n+\t\tif (commit_graph_generation(reference[i]) < min_generation)\n+\t\t\tmin_generation = commit_graph_generation(reference[i]);\n \t}\n \n-\tif (commit->generation > min_generation)\n+\tif (commit_graph_generation(commit) > min_generation)\n \t\treturn ret;\n \n \tbases = paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t commit->generation);\n+\t\t\t\t commit_graph_generation(commit));\n \tif (commit->object.flags & PARENT2)\n \t\tret = 1;\n \tclear_commit_marks(commit, all_flags);\n@@ -467,7 +467,7 @@ static enum contains_result contains_test(struct commit *candidate,\n \t/* Otherwise, we don't know; prepare to recurse */\n \tparse_commit_or_die(candidate);\n \n-\tif (candidate->generation < cutoff)\n+\tif (commit_graph_generation(candidate) < cutoff)\n \t\treturn CONTAINS_NO;\n \n \treturn CONTAINS_UNKNOWN;\n@@ -492,8 +492,8 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tfor (p = want; p; p = p->next) {\n \t\tstruct commit *c = p->item;\n \t\tload_commit_graph_info(the_repository, c);\n-\t\tif (c->generation < cutoff)\n-\t\t\tcutoff = c->generation;\n+\t\tif (commit_graph_generation(c) < cutoff)\n+\t\t\tcutoff = commit_graph_generation(c);\n \t}\n \n \tresult = contains_test(candidate, want, cache, cutoff);\n@@ -544,9 +544,9 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \tconst struct commit *a = *(const struct commit * const *)_a;\n \tconst struct commit *b = *(const struct commit * const *)_b;\n \n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn -1;\n-\tif (a->generation > b->generation)\n+\tif (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn 1;\n \treturn 0;\n }\n@@ -585,7 +585,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\tlist[nr_commits] = (struct commit *)from_one;\n \t\tif (parse_commit(list[nr_commits]) ||\n-\t\t list[nr_commits]->generation < min_generation) {\n+\t\t commit_graph_generation(list[nr_commits]) < min_generation) {\n \t\t\tresult = 0;\n \t\t\tgoto cleanup;\n \t\t}\n@@ -621,7 +621,7 @@ int can_all_from_reach_with_flag(struct object_array *from,\n \n \t\t\t\t\tif (parse_commit(parent->item) ||\n \t\t\t\t\t parent->item->date < min_commit_date ||\n-\t\t\t\t\t parent->item->generation < min_generation)\n+\t\t\t\t\t commit_graph_generation(parent->item) < min_generation)\n \t\t\t\t\t\tcontinue;\n \n \t\t\t\t\tcommit_list_insert(parent->item, &stack);\n@@ -665,8 +665,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (from_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = from_iter->item->date;\n \n-\t\t\tif (from_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = from_iter->item->generation;\n+\t\t\tif (commit_graph_generation(from_iter->item) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(from_iter->item);\n \t\t}\n \n \t\tfrom_iter = from_iter->next;\n@@ -677,8 +677,8 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t\tif (to_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\t\tif (to_iter->item->generation < min_generation)\n-\t\t\t\tmin_generation = to_iter->item->generation;\n+\t\t\tif (commit_graph_generation(to_iter->item) < min_generation)\n+\t\t\t\tmin_generation = commit_graph_generation(to_iter->item);\n \t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n@@ -721,8 +721,8 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \t\tstruct commit *c = *item;\n \n \t\tparse_commit(c);\n-\t\tif (c->generation < min_generation)\n-\t\t\tmin_generation = c->generation;\n+\t\tif (commit_graph_generation(c) < min_generation)\n+\t\t\tmin_generation = commit_graph_generation(c);\n \n \t\tif (!(c->object.flags & PARENT1)) {\n \t\t\tc->object.flags |= PARENT1;\n@@ -755,7 +755,7 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \n \t\t\tparse_commit(p);\n \n-\t\t\tif (p->generation < min_generation)\n+\t\t\tif (commit_graph_generation(p) < min_generation)\n \t\t\t\tcontinue;\n \n \t\t\tif (p->object.flags & PARENT2)\ndiff --git a/commit.c b/commit.c\nindex b30875e66b..ed0917a2c7 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -339,7 +339,7 @@ struct tree *repo_get_commit_tree(struct repository *r,\n \tif (commit->maybe_tree || !commit->object.parsed)\n \t\treturn commit->maybe_tree;\n \n-\tif (commit->graph_pos != COMMIT_NOT_FROM_GRAPH)\n+\tif (commit_graph_position(commit) != COMMIT_NOT_FROM_GRAPH)\n \t\treturn get_commit_tree_in_graph(r, commit);\n \n \treturn NULL;\n@@ -731,9 +731,9 @@ int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void\n \tconst struct commit *a = a_, *b = b_;\n \n \t/* newer commits first */\n-\tif (a->generation < b->generation)\n+\tif (commit_graph_generation(a) < commit_graph_generation(b))\n \t\treturn 1;\n-\telse if (a->generation > b->generation)\n+\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n \t\treturn -1;\n \n \t/* use date as a heuristic when generations are equal */\ndiff --git a/commit.h b/commit.h\nindex 1b2dea5d85..e901538909 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -36,8 +36,6 @@ struct commit {\n \t * or get_commit_tree_oid().\n \t */\n \tstruct tree *maybe_tree;\n-\tuint32_t graph_pos;\n-\tuint32_t generation;\n \tunsigned int index;\n };\n \ndiff --git a/contrib/coccinelle/commit.cocci b/contrib/coccinelle/commit.cocci\nindex 778e4704f6..af6dd4c20c 100644\n--- a/contrib/coccinelle/commit.cocci\n+++ b/contrib/coccinelle/commit.cocci\n@@ -32,3 +32,21 @@ expression c;\n - c->maybe_tree\n + repo_get_commit_tree(specify_the_right_repo_here, c)\n ...>}\n+\n+@@\n+struct commit *c;\n+expression E;\n+@@\n+(\n+- c->generation = E;\n++ commit_graph_data_at(c)->generation = E;\n+|\n+- c->graph_pos = E;\n++ commit_graph_data_at(c)->graph_pos = E;\n+|\n+- c->generation\n++ commit_graph_generation(c)\n+|\n+- c->graph_pos\n++ commit_graph_position(c)\n+)\ndiff --git a/revision.c b/revision.c\nindex ebb4d2a0f2..8648d7c43c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -725,7 +725,7 @@ static int check_maybe_different_in_bloom_filter(struct rev_info *revs,\n \tif (!revs->repo->objects->commit_graph)\n \t\treturn -1;\n \n-\tif (commit->generation == GENERATION_NUMBER_INFINITY)\n+\tif (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY)\n \t\treturn -1;\n \n \tfilter = get_bloom_filter(revs->repo, commit, 0);\n@@ -3320,7 +3320,7 @@ static void explore_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->explore_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t commit_graph_generation(c) >= gen_cutoff)\n \t\texplore_walk_step(revs);\n }\n \n@@ -3336,7 +3336,7 @@ static void indegree_walk_step(struct rev_info *revs)\n \tif (parse_commit_gently(c, 1) < 0)\n \t\treturn;\n \n-\texplore_to_depth(revs, c->generation);\n+\texplore_to_depth(revs, commit_graph_generation(c));\n \n \tfor (p = c->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n@@ -3360,7 +3360,7 @@ static void compute_indegrees_to_depth(struct rev_info *revs,\n \tstruct topo_walk_info *info = revs->topo_walk_info;\n \tstruct commit *c;\n \twhile ((c = prio_queue_peek(&info->indegree_queue)) &&\n-\t c->generation >= gen_cutoff)\n+\t commit_graph_generation(c) >= gen_cutoff)\n \t\tindegree_walk_step(revs);\n }\n \n@@ -3420,8 +3420,8 @@ static void init_topo_walk(struct rev_info *revs)\n \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n \n-\t\tif (c->generation < info->min_generation)\n-\t\t\tinfo->min_generation = c->generation;\n+\t\tif (commit_graph_generation(c) < info->min_generation)\n+\t\t\tinfo->min_generation = commit_graph_generation(c);\n \n \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n \n@@ -3479,8 +3479,8 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-\t\tif (parent->generation < info->min_generation) {\n-\t\t\tinfo->min_generation = parent->generation;\n+\t\tif (commit_graph_generation(parent) < info->min_generation) {\n+\t\t\tinfo->min_generation = commit_graph_generation(parent);\n \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n \t\t}\n \n-- \n2.27.0\n\n"},{"id":"399966","messageId":"20200617091411.14650-5-abhishekkumar8222@gmail.com","threadId":"53611","inReplyTo":"20200617091411.14650-1-abhishekkumar8222@gmail.com","subject":"[GSOC Patch v4 4/4] commit-graph: minimize commit_graph_data_slab access","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:14:11Z","receivedAt":"2020-06-17T09:16:36Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"In an earlier patch, multiple struct acccesses to `graph_pos` and\n`generation` were auto-converted to multiple method calls.\n\nSince the values are fixed and commit-slab access costly, we would be\nbetter off with storing the values as a local variable and reusing it.\n\nSigned-off-by: Abhishek Kumar \n---\n bloom.c | 5 +++--\n commit-graph.c | 40 ++++++++++++++++++++++------------\n commit-reach.c | 59 ++++++++++++++++++++++++++++++++------------------\n commit.c | 6 +++--\n revision.c | 12 ++++++----\n 5 files changed, 79 insertions(+), 43 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 3062aafaba..6a7f2f2bdc 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -33,15 +33,16 @@ static int load_bloom_filter_from_graph(struct commit_graph *g,\n \t\t\t\t\tstruct commit *c)\n {\n \tuint32_t lex_pos, start_index, end_index;\n+\tuint32_t graph_pos = commit_graph_position(c);\n \n-\twhile (commit_graph_position(c) < g->num_commits_in_base)\n+\twhile (graph_pos < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \t/* The commit graph commit 'c' lives in doesn't carry bloom filters. */\n \tif (!g->chunk_bloom_indexes)\n \t\treturn 0;\n \n-\tlex_pos = commit_graph_position(c) - g->num_commits_in_base;\n+\tlex_pos = graph_pos - g->num_commits_in_base;\n \n \tend_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);\n \ndiff --git a/commit-graph.c b/commit-graph.c\nindex 14cc7e931c..fdd1c4fa7c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -144,10 +144,12 @@ static int commit_gen_cmp(const void *va, const void *vb)\n \tconst struct commit *a = *(const struct commit **)va;\n \tconst struct commit *b = *(const struct commit **)vb;\n \n+\tuint32_t generation_a = commit_graph_generation(a);\n+\tuint32_t generation_b = commit_graph_generation(b);\n \t/* lower generation commits first */\n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tif (generation_a < generation_b)\n \t\treturn -1;\n-\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n+\telse if (generation_a > generation_b)\n \t\treturn 1;\n \n \t/* use date as a heuristic when generations are equal */\n@@ -729,6 +731,7 @@ static struct commit_list **insert_parent_or_die(struct repository *r,\n static void fill_commit_graph_info(struct commit *item, struct commit_graph *g, uint32_t pos)\n {\n \tconst unsigned char *commit_data;\n+\tstruct commit_graph_data *graph_data;\n \tuint32_t lex_index;\n \n \twhile (pos < g->num_commits_in_base)\n@@ -736,8 +739,10 @@ static void fill_commit_graph_info(struct commit *item, struct commit_graph *g,\n \n \tlex_index = pos - g->num_commits_in_base;\n \tcommit_data = g->chunk_commit_data + GRAPH_DATA_WIDTH * lex_index;\n-\tcommit_graph_data_at(item)->graph_pos = pos;\n-\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\n+\tgraph_data = commit_graph_data_at(item);\n+\tgraph_data->graph_pos = pos;\n+\tgraph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n }\n \n static inline void set_commit_tree(struct commit *c, struct tree *t)\n@@ -753,6 +758,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tuint32_t *parent_data_ptr;\n \tuint64_t date_low, date_high;\n \tstruct commit_list **pptr;\n+\tstruct commit_graph_data *graph_data;\n \tconst unsigned char *commit_data;\n \tuint32_t lex_index;\n \n@@ -766,7 +772,8 @@ static int fill_commit_in_graph(struct repository *r,\n \t * Store the \"full\" position, but then use the\n \t * \"local\" position for the rest of the calculation.\n \t */\n-\tcommit_graph_data_at(item)->graph_pos = pos;\n+\tgraph_data = commit_graph_data_at(item);\n+\tgraph_data->graph_pos = pos;\n \tlex_index = pos - g->num_commits_in_base;\n \n \tcommit_data = g->chunk_commit_data + (g->hash_len + 16) * lex_index;\n@@ -779,7 +786,7 @@ static int fill_commit_in_graph(struct repository *r,\n \tdate_low = get_be32(commit_data + g->hash_len + 12);\n \titem->date = (timestamp_t)((date_high << 32) | date_low);\n \n-\tcommit_graph_data_at(item)->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n+\tgraph_data->generation = get_be32(commit_data + g->hash_len + 8) >> 2;\n \n \tpptr = &item->parents;\n \n@@ -811,8 +818,9 @@ static int fill_commit_in_graph(struct repository *r,\n \n static int find_commit_in_graph(struct commit *item, struct commit_graph *g, uint32_t *pos)\n {\n-\tif (commit_graph_position(item) != COMMIT_NOT_FROM_GRAPH) {\n-\t\t*pos = commit_graph_position(item);\n+\tuint32_t graph_pos = commit_graph_position(item);\n+\tif (graph_pos != COMMIT_NOT_FROM_GRAPH) {\n+\t\t*pos = graph_pos;\n \t\treturn 1;\n \t} else {\n \t\tstruct commit_graph *cur_g = g;\n@@ -867,12 +875,13 @@ static struct tree *load_tree_for_commit(struct repository *r,\n {\n \tstruct object_id oid;\n \tconst unsigned char *commit_data;\n+\tuint32_t graph_pos = commit_graph_position(c);\n \n-\twhile (commit_graph_position(c) < g->num_commits_in_base)\n+\twhile (graph_pos < g->num_commits_in_base)\n \t\tg = g->base_graph;\n \n \tcommit_data = g->chunk_commit_data +\n-\t\t\tGRAPH_DATA_WIDTH * (commit_graph_position(c) - g->num_commits_in_base);\n+\t\t\tGRAPH_DATA_WIDTH * (graph_pos - g->num_commits_in_base);\n \n \thashcpy(oid.hash, commit_data);\n \tset_commit_tree(c, lookup_tree(r, &oid));\n@@ -2299,6 +2308,7 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tstruct commit *graph_commit, *odb_commit;\n \t\tstruct commit_list *graph_parents, *odb_parents;\n \t\tuint32_t max_generation = 0;\n+\t\tuint32_t generation;\n \n \t\tdisplay_progress(progress, i + 1);\n \t\thashcpy(cur_oid.hash, g->chunk_oid_lookup + g->hash_len * i);\n@@ -2337,8 +2347,9 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\t\t\t\t oid_to_hex(&graph_parents->item->object.oid),\n \t\t\t\t\t oid_to_hex(&odb_parents->item->object.oid));\n \n-\t\t\tif (commit_graph_generation(graph_parents->item) > max_generation)\n-\t\t\t\tmax_generation = commit_graph_generation(graph_parents->item);\n+\t\t\tgeneration = commit_graph_generation(graph_parents->item);\n+\t\t\tif (generation > max_generation)\n+\t\t\t\tmax_generation = generation;\n \n \t\t\tgraph_parents = graph_parents->next;\n \t\t\todb_parents = odb_parents->next;\n@@ -2368,10 +2379,11 @@ int verify_commit_graph(struct repository *r, struct commit_graph *g, int flags)\n \t\tif (max_generation == GENERATION_NUMBER_MAX)\n \t\t\tmax_generation--;\n \n-\t\tif (commit_graph_generation(graph_commit) != max_generation + 1)\n+\t\tgeneration = commit_graph_generation(graph_commit);\n+\t\tif (generation != max_generation + 1)\n \t\t\tgraph_report(_(\"commit-graph generation for commit %s is %u != %u\"),\n \t\t\t\t oid_to_hex(&cur_oid),\n-\t\t\t\t commit_graph_generation(graph_commit),\n+\t\t\t\t generation,\n \t\t\t\t max_generation + 1);\n \n \t\tif (graph_commit->date != odb_commit->date)\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 3b2f863f5f..f5e5c0a32b 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -58,14 +58,15 @@ static struct commit_list *paint_down_to_common(struct repository *r,\n \t\tstruct commit *commit = prio_queue_get(&queue);\n \t\tstruct commit_list *parents;\n \t\tint flags;\n+\t\tuint32_t generation = commit_graph_generation(commit);\n \n-\t\tif (min_generation && commit_graph_generation(commit) > last_gen)\n+\t\tif (min_generation && generation > last_gen)\n \t\t\tBUG(\"bad generation skip %8x > %8x at %s\",\n-\t\t\t commit_graph_generation(commit), last_gen,\n+\t\t\t generation, last_gen,\n \t\t\t oid_to_hex(&commit->object.oid));\n-\t\tlast_gen = commit_graph_generation(commit);\n+\t\tlast_gen = generation;\n \n-\t\tif (commit_graph_generation(commit) < min_generation)\n+\t\tif (generation < min_generation)\n \t\t\tbreak;\n \n \t\tflags = commit->object.flags & (PARENT1 | PARENT2 | STALE);\n@@ -181,13 +182,15 @@ static int remove_redundant(struct repository *r, struct commit **array, int cnt\n \t\tif (redundant[i])\n \t\t\tcontinue;\n \t\tfor (j = filled = 0; j < cnt; j++) {\n+\t\t\tuint32_t curr_generation;\n \t\t\tif (i == j || redundant[j])\n \t\t\t\tcontinue;\n \t\t\tfilled_index[filled] = j;\n \t\t\twork[filled++] = array[j];\n \n-\t\t\tif (commit_graph_generation(array[j]) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(array[j]);\n+\t\t\tcurr_generation = commit_graph_generation(array[j]);\n+\t\t\tif (curr_generation < min_generation)\n+\t\t\t\tmin_generation = curr_generation;\n \t\t}\n \t\tcommon = paint_down_to_common(r, array[i], filled,\n \t\t\t\t\t work, min_generation);\n@@ -316,23 +319,26 @@ int repo_in_merge_bases_many(struct repository *r, struct commit *commit,\n {\n \tstruct commit_list *bases;\n \tint ret = 0, i;\n-\tuint32_t min_generation = GENERATION_NUMBER_INFINITY;\n+\tuint32_t generation, min_generation = GENERATION_NUMBER_INFINITY;\n \n \tif (repo_parse_commit(r, commit))\n \t\treturn ret;\n \tfor (i = 0; i < nr_reference; i++) {\n \t\tif (repo_parse_commit(r, reference[i]))\n \t\t\treturn ret;\n-\t\tif (commit_graph_generation(reference[i]) < min_generation)\n-\t\t\tmin_generation = commit_graph_generation(reference[i]);\n+\n+\t\tgeneration = commit_graph_generation(reference[i]);\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n \t}\n \n-\tif (commit_graph_generation(commit) > min_generation)\n+\tgeneration = commit_graph_generation(commit);\n+\tif (generation > min_generation)\n \t\treturn ret;\n \n \tbases = paint_down_to_common(r, commit,\n \t\t\t\t nr_reference, reference,\n-\t\t\t\t commit_graph_generation(commit));\n+\t\t\t\t generation);\n \tif (commit->object.flags & PARENT2)\n \t\tret = 1;\n \tclear_commit_marks(commit, all_flags);\n@@ -490,10 +496,12 @@ static enum contains_result contains_tag_algo(struct commit *candidate,\n \tconst struct commit_list *p;\n \n \tfor (p = want; p; p = p->next) {\n+\t\tuint32_t generation;\n \t\tstruct commit *c = p->item;\n \t\tload_commit_graph_info(the_repository, c);\n-\t\tif (commit_graph_generation(c) < cutoff)\n-\t\t\tcutoff = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < cutoff)\n+\t\t\tcutoff = generation;\n \t}\n \n \tresult = contains_test(candidate, want, cache, cutoff);\n@@ -544,9 +552,12 @@ static int compare_commits_by_gen(const void *_a, const void *_b)\n \tconst struct commit *a = *(const struct commit * const *)_a;\n \tconst struct commit *b = *(const struct commit * const *)_b;\n \n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tuint32_t generation_a = commit_graph_generation(a);\n+\tuint32_t generation_b = commit_graph_generation(b);\n+\n+\tif (generation_a < generation_b)\n \t\treturn -1;\n-\tif (commit_graph_generation(a) > commit_graph_generation(b))\n+\tif (generation_a > generation_b)\n \t\treturn 1;\n \treturn 0;\n }\n@@ -662,11 +673,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\tadd_object_array(&from_iter->item->object, NULL, &from_objs);\n \n \t\tif (!parse_commit(from_iter->item)) {\n+\t\t\tuint32_t generation;\n \t\t\tif (from_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = from_iter->item->date;\n \n-\t\t\tif (commit_graph_generation(from_iter->item) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(from_iter->item);\n+\t\t\tgeneration = commit_graph_generation(from_iter->item);\n+\t\t\tif (generation < min_generation)\n+\t\t\t\tmin_generation = generation;\n \t\t}\n \n \t\tfrom_iter = from_iter->next;\n@@ -674,11 +687,13 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \n \twhile (to_iter) {\n \t\tif (!parse_commit(to_iter->item)) {\n+\t\t\tuint32_t generation;\n \t\t\tif (to_iter->item->date < min_commit_date)\n \t\t\t\tmin_commit_date = to_iter->item->date;\n \n-\t\t\tif (commit_graph_generation(to_iter->item) < min_generation)\n-\t\t\t\tmin_generation = commit_graph_generation(to_iter->item);\n+\t\t\tgeneration = commit_graph_generation(to_iter->item);\n+\t\t\tif (generation < min_generation)\n+\t\t\t\tmin_generation = generation;\n \t\t}\n \n \t\tto_iter->item->object.flags |= PARENT2;\n@@ -718,11 +733,13 @@ struct commit_list *get_reachable_subset(struct commit **from, int nr_from,\n \tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n \n \tfor (item = to; item < to_last; item++) {\n+\t\tuint32_t generation;\n \t\tstruct commit *c = *item;\n \n \t\tparse_commit(c);\n-\t\tif (commit_graph_generation(c) < min_generation)\n-\t\t\tmin_generation = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < min_generation)\n+\t\t\tmin_generation = generation;\n \n \t\tif (!(c->object.flags & PARENT1)) {\n \t\t\tc->object.flags |= PARENT1;\ndiff --git a/commit.c b/commit.c\nindex ed0917a2c7..43d29a800d 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -729,11 +729,13 @@ int compare_commits_by_author_date(const void *a_, const void *b_,\n int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)\n {\n \tconst struct commit *a = a_, *b = b_;\n+\tconst uint32_t generation_a = commit_graph_generation(a),\n+\t\t generation_b = commit_graph_generation(b);\n \n \t/* newer commits first */\n-\tif (commit_graph_generation(a) < commit_graph_generation(b))\n+\tif (generation_a < generation_b)\n \t\treturn 1;\n-\telse if (commit_graph_generation(a) > commit_graph_generation(b))\n+\telse if (generation_a > generation_b)\n \t\treturn -1;\n \n \t/* use date as a heuristic when generations are equal */\ndiff --git a/revision.c b/revision.c\nindex 8648d7c43c..32be93f404 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -3413,6 +3413,7 @@ static void init_topo_walk(struct rev_info *revs)\n \tinfo->min_generation = GENERATION_NUMBER_INFINITY;\n \tfor (list = revs->commits; list; list = list->next) {\n \t\tstruct commit *c = list->item;\n+\t\tuint32_t generation;\n \n \t\tif (parse_commit_gently(c, 1))\n \t\t\tcontinue;\n@@ -3420,8 +3421,9 @@ static void init_topo_walk(struct rev_info *revs)\n \t\ttest_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED);\n \t\ttest_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE);\n \n-\t\tif (commit_graph_generation(c) < info->min_generation)\n-\t\t\tinfo->min_generation = commit_graph_generation(c);\n+\t\tgeneration = commit_graph_generation(c);\n+\t\tif (generation < info->min_generation)\n+\t\t\tinfo->min_generation = generation;\n \n \t\t*(indegree_slab_at(&info->indegree, c)) = 1;\n \n@@ -3472,6 +3474,7 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \tfor (p = commit->parents; p; p = p->next) {\n \t\tstruct commit *parent = p->item;\n \t\tint *pi;\n+\t\tuint32_t generation;\n \n \t\tif (parent->object.flags & UNINTERESTING)\n \t\t\tcontinue;\n@@ -3479,8 +3482,9 @@ static void expand_topo_walk(struct rev_info *revs, struct commit *commit)\n \t\tif (parse_commit_gently(parent, 1) < 0)\n \t\t\tcontinue;\n \n-\t\tif (commit_graph_generation(parent) < info->min_generation) {\n-\t\t\tinfo->min_generation = commit_graph_generation(parent);\n+\t\tgeneration = commit_graph_generation(parent);\n+\t\tif (generation < info->min_generation) {\n+\t\t\tinfo->min_generation = generation;\n \t\t\tcompute_indegrees_to_depth(revs, info->min_generation);\n \t\t}\n \n-- \n2.27.0\n\n"},{"id":"400121","messageId":"d5131361-2945-3daa-d91c-67761908b8ef@gmail.com","threadId":"53611","inReplyTo":"20200617091411.14650-1-abhishekkumar8222@gmail.com","subject":"Re: [GSOC Patch v4 0/4] Move generation, graph_pos to a slab","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-19T13:59:38Z","receivedAt":"2020-06-19T13:59:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/17/2020 5:14 AM, Abhishek Kumar wrote:\n> The struct commit is used in many contexts. However, members\n> `generation` and `graph_pos` are only used for commit graph related\n> operations and otherwise waste memory.\n> \n> This wastage would have been more pronounced as we transition to\n> generation nuber v2, which uses 64-bit generation number instead of\n> current 32-bits.\n\nThanks, Szeder (CC'd) for the quality review in the previous\nversions. I manually built and tested all of the patches here\nand verified they passed all tests.\n\nI think this series is in good shape.\n\nThanks,\n-Stolee\n\n\n"},{"id":"400155","messageId":"xmqq7dw3hrwf.fsf@gitster.c.googlers.com","threadId":"53611","inReplyTo":"d5131361-2945-3daa-d91c-67761908b8ef@gmail.com","subject":"Re: [GSOC Patch v4 0/4] Move generation, graph_pos to a slab","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-19T17:44:32Z","receivedAt":"2020-06-19T17:44:40Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 6/17/2020 5:14 AM, Abhishek Kumar wrote:\n>> The struct commit is used in many contexts. However, members\n>> `generation` and `graph_pos` are only used for commit graph related\n>> operations and otherwise waste memory.\n>> \n>> This wastage would have been more pronounced as we transition to\n>> generation nuber v2, which uses 64-bit generation number instead of\n>> current 32-bits.\n>\n> Thanks, Szeder (CC'd) for the quality review in the previous\n> versions. I manually built and tested all of the patches here\n> and verified they passed all tests.\n>\n> I think this series is in good shape.\n\nThank you to all who are involved in this topic. Looking good.\n\n"}]}