{"thread":{"id":"53668","subject":"[GSoC Patch v3 0/4] Move generation, graph_pos to a slab","startedAt":"2020-06-12T18:42:01Z","lastAt":"2020-06-17T09:20:11Z","messageCount":14,"participants":["Abhishek Kumar","Junio C Hamano","Jakub Narębski","SZEDER Gábor"],"isPatch":true,"patchVersion":3,"patchTotal":4},"messages":[{"id":"399622","messageId":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","threadId":"53668","inReplyTo":null,"subject":"[GSoC Patch v3 0/4] Move generation, graph_pos to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-12T18:40:10Z","receivedAt":"2020-06-12T18:42:01Z","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\nWhile the overall test suite runs slightly faster than master\n(series: 27m10s, master: 27ms34s, faster by 2.35%), certain commands\nlike `git merge-base --is-ancestory` are slowed by nearly 40% as\ndiscovered by SDEZER Gabor [1].\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 on that in a later series.\n\nI did not mention maximum RSS in the commit messages as they were nearly\nidentical (series: 68104kb, master: 68040kb, fewer by <0.1%). This leads\nme to conclude that either the test using maximum memory involves commit\ngraph or did not involve the struct commit at all. The move to\ncommit-slab reduces memory footprint for the cases where struct commit\nis used but members generation and graph position are not. Average RSS\nwould have been a good and more representative measure, but \nunfortunately time(1) could not measure it on my system.\n\nWith this, I feel the patch will require minor fixes, if any. I am\nmoving ahead with working the next step of \"Implement Generation Number\nv2\" that is proper handling of commit-graph format change.\n\nBased on the discussions, I feel we should compute both generation\nnumber v1 and the date offset value with storing date offsets in a new\nchunk as the cost is mostly from walking the commits.\n\nAbhishek Kumar (4):\n  alloc: introduce parsed_commits_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                         |   6 +-\n blame.c                         |   2 +-\n bloom.c                         |   7 +-\n commit-graph.c                  | 122 ++++++++++++++++++++++++--------\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, 188 insertions(+), 74 deletions(-)\n\n-- \n2.27.0\n\nChanges in v3:\n- Introduce alloc commit to fix the failing diff-submodule test.\n- Elaborate on performance and slow down noticed in the 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_ZERO) from commit.h to commit-graph.h\n\nCI Build: https://travis-ci.com/github/abhishekkumar2718/git  \n"},{"id":"399623","messageId":"20200612184014.1226972-2-abhishekkumar8222@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","subject":"[PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-12T18:40:11Z","receivedAt":"2020-06-12T18:42:05Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"Commit slab relies on uniqueness of commit->index to access data. As\nsubmodules are repositories on their own, alloc_commit_index() (which\ndepends on repository->parsed_objects->commit_count) no longer\nreturns unique values.\n\nThis would break tests once we move `generation` and `graph_pos` into a\ncommit slab, as commits of supermodule and submodule can have the same\nindex but must have different graph positions.\n\nLet's introduce a counter variable, `parsed_commits_count` to keep track\nof parsed commits so far.\n\n\nSigned-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>\n---\n\nCI Build for the failing tests:\nhttps://travis-ci.com/github/abhishekkumar2718/git/jobs/345413840\n\n alloc.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 1c64c4dd16..29f0e3aa80 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -101,7 +101,9 @@ void *alloc_object_node(struct repository *r)\n \n static unsigned int alloc_commit_index(struct repository *r)\n {\n-\treturn r->parsed_objects->commit_count++;\n+\tstatic unsigned int parsed_commits_count = 0;\n+\tr->parsed_objects->commit_count++;\n+\treturn parsed_commits_count++;\n }\n \n void init_commit_node(struct repository *r, struct commit *c)\n-- \n2.27.0\n\n"},{"id":"399624","messageId":"20200612184014.1226972-3-abhishekkumar8222@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","subject":"[PATCH v3 2/4] commit-graph: introduce commit_graph_data_slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-12T18:40:12Z","receivedAt":"2020-06-12T18:42:09Z","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: 27m10s, master: 27m34s), certain commands like\n`git merge-base --is-ancestor` are slowed by nearly 40% as\ndiscovered by SDEZER Gabor [1].\n\nDerrick Stolee believes the slow down is attributable to the\nunderlying algorithm rather slowness of commit-slab access [2] and we will\nfollow-up on that 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 <abhishekkumar8222@gmail.com>\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 2ff042fbf4..91120ba3d3 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+\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+\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 initializing generation with checking if graph position\n+\t * is not 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[i][j].graph_pos =\n+\t\t\t\tCOMMIT_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 3ba0da1e5f..cc76757007 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":"399625","messageId":"20200612184014.1226972-4-abhishekkumar8222@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","subject":"[PATCH v3 3/4] commit: move members graph_pos, generation to a slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-12T18:40:13Z","receivedAt":"2020-06-12T18:42:13Z","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\ncommit_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. This is fixed by using generation number\ndirectly when writing a commit graph, namely in functions\ncompute_generation_numbers() and write_graph_chunk_data().\n\nSigned-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>\n---\n alloc.c                         |  2 -\n blame.c                         |  2 +-\n bloom.c                         |  6 +--\n commit-graph.c                  | 68 ++++++++++++++++++---------------\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, 96 insertions(+), 74 deletions(-)\n\ndiff --git a/alloc.c b/alloc.c\nindex 29f0e3aa80..fe7d7345e1 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -110,8 +110,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 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 91120ba3d3..cb4365e9b6 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -128,7 +128,7 @@ static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\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[i][j].graph_pos =\n+\t\t\tcommit_graph_data_slab.slab[i][j].graph_pos =\n \t\t\t\tCOMMIT_NOT_FROM_GRAPH;\n \t\t}\n \t}\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@@ -1069,7 +1069,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@@ -1268,7 +1268,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@@ -1300,9 +1300,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@@ -1313,22 +1315,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}\n@@ -1507,7 +1513,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@@ -1541,7 +1547,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@@ -2328,8 +2334,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@@ -2339,7 +2345,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@@ -2359,10 +2365,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 cc76757007..28f89cdf3e 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -140,7 +140,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 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":"399626","messageId":"20200612184014.1226972-5-abhishekkumar8222@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","subject":"[PATCH v3 4/4] commit-graph: minimize commit_graph_data_slab access","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-12T18:40:14Z","receivedAt":"2020-06-12T18:42:16Z","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 <abhishekkumar8222@gmail.com>\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 cb4365e9b6..5d86d20459 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@@ -2296,6 +2305,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@@ -2334,8 +2344,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@@ -2365,10 +2376,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 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":"399629","messageId":"xmqqtuzg11zv.fsf@gitster.c.googlers.com","threadId":"53668","inReplyTo":"20200612184014.1226972-2-abhishekkumar8222@gmail.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-12T20:08:04Z","receivedAt":"2020-06-12T20:08:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n>  static unsigned int alloc_commit_index(struct repository *r)\n>  {\n> -\treturn r->parsed_objects->commit_count++;\n> +\tstatic unsigned int parsed_commits_count = 0;\n> +\tr->parsed_objects->commit_count++;\n> +\treturn parsed_commits_count++;\n>  }\n\nHmph, ugly.  \n\nThe need for this hack, which butchers the function that explicitly\ntakes a repository as its parameter so that parsed commits can be\ncounted per repository to not count commits per repository, makes\nthe whole thing smell fishy.\n\nThere shouldn't be a reason why a commit in the superproject and\nanother commit in the submodule need to be in the same commit graph\nin the first place.\n\nInstead of breaking the function like this, the right \"fix\" may be\nto make the commit slab per repository, because the commit index are\ntaken from the separate namespace per repository.\n\n"},{"id":"399630","messageId":"f7f2cee7-c4c3-0b68-c164-bcb9b6839219@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-1-abhishekkumar8222@gmail.com","subject":"Re: [GSoC Patch v3 0/4] Move generation, graph_pos to a slab","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-12T21:26:54Z","receivedAt":"2020-06-12T21:34:04Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On 12.06.2020, Abhishek Kumar wrote:\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-bit generation number instead of\n> current 32-bits.\n\nI think s/would have been/would be/1, but I am not native English\nspeaker.\n\n> \n> While the overall test suite runs slightly faster than master\n> (series: 27m10s, master: 27ms34s, faster by 2.35%), certain commands\n> like `git merge-base --is-ancestory` are slowed by nearly 40% as\n> discovered by SDEZER Gabor [1].\n\nFirst, the name is SZEDER Gábor.\n\nSecond, it would be nice to have some specific examples, like for\nexample the results of running `git merge-base --is-ancestory` in\nspecific repository, and from specific starting point.\n\nIt might be good idea to also show performance change for a command\nthat handles large amount of commits but does not use the commit-graph,\nlike for example `git gc`.\n\n> \n> Derrick Stolee believes the slow down is attributable to the underlying\n> algorithm rather than the slowness of commit-slab access [2] and we will\n> follow-up on that in a later series.\n\nWould it be possible to show profiling results?\n\n> \n> I did not mention maximum RSS in the commit messages as they were nearly\n> identical (series: 68104kb, master: 68040kb, fewer by <0.1%). This leads\n> me to conclude that either the test using maximum memory involves commit\n> graph or did not involve the struct commit at all. The move to\n> commit-slab reduces memory footprint for the cases where struct commit\n> is used but members generation and graph position are not. Average RSS\n> would have been a good and more representative measure, but\n> unfortunately time(1) could not measure it on my system.\n\nWhat operating system do you use?\n\n> \n> With this, I feel the patch will require minor fixes, if any. I am\n> moving ahead with working the next step of \"Implement Generation Number\n> v2\" that is proper handling of commit-graph format change.\n\nAll right.  It should be not a problem to rebase series on top of\ndifferent implementation of [inline-able] helper function if it\nturns out that the move to slab serious affects negatively performance.\n\n> \n> Based on the discussions, I feel we should compute both generation\n> number v1 and the date offset value with storing date offsets in a new\n> chunk as the cost is mostly from walking the commits.\n\nShould we store offsets and corrected commit date on the slab,\nor just the corrected date (with offset applied)?  We should be\nusing corrected commit date only; offset can be recomputed if\nneeded, e.g. when writing the commit-graph.\n\n> \n> Abhishek Kumar (4):\n>    alloc: introduce parsed_commits_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                         |   6 +-\n>   blame.c                         |   2 +-\n>   bloom.c                         |   7 +-\n>   commit-graph.c                  | 122 ++++++++++++++++++++++++--------\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, 188 insertions(+), 74 deletions(-)\n> \n\n"},{"id":"399631","messageId":"xmqqpna40ws8.fsf@gitster.c.googlers.com","threadId":"53668","inReplyTo":"xmqqtuzg11zv.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-12T22:00:39Z","receivedAt":"2020-06-12T22:00:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n>\n>>  static unsigned int alloc_commit_index(struct repository *r)\n>>  {\n>> -\treturn r->parsed_objects->commit_count++;\n>> +\tstatic unsigned int parsed_commits_count = 0;\n>> +\tr->parsed_objects->commit_count++;\n>> +\treturn parsed_commits_count++;\n>>  }\n>\n> Hmph, ugly.  \n>\n> The need for this hack, which butchers the function that explicitly\n> takes a repository as its parameter so that parsed commits can be\n> counted per repository to not count commits per repository, makes\n> the whole thing smell fishy.\n>\n> There shouldn't be a reason why a commit in the superproject and\n> another commit in the submodule need to be in the same commit graph\n> in the first place.\n>\n> Instead of breaking the function like this, the right \"fix\" may be\n> to make the commit slab per repository, because the commit index are\n> taken from the separate namespace per repository.\n\nGiven a commit object (i.e. \"struct commit *\"), currently there is\nno way to tell from which repository it came from.  So from that\npoint of view, we cannot identify which commit slab to use, unless\nwe add a back-pointer that says from which repository each commit\nobject came from, but that makes the commit object even heavier.\n\nBack when 14ba97f8 (alloc: allow arbitrary repositories for alloc\nfunctions, 2018-05-15) made the count per repository (which you are\nreverting with this patch), there must have been a reason why it did\nso.  We know that commit slab code wants you to count globally and\nthat is why you wrote this patch, but don't other parts of the code\nexpect and rely on the commits being counted per repository?  In\nother words, with this change, who are you breaking to help the\ncommit slab code?\n\nCc'ing SZEDER who also have touched this and made the function\nstatic early last year.\n\nThanks.\n"},{"id":"399632","messageId":"xmqqlfks0vvh.fsf@gitster.c.googlers.com","threadId":"53668","inReplyTo":"xmqqpna40ws8.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-12T22:20:18Z","receivedAt":"2020-06-12T22:20:25Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Back when 14ba97f8 (alloc: allow arbitrary repositories for alloc\n> functions, 2018-05-15) made the count per repository (which you are\n> reverting with this patch), there must have been a reason why it did\n> so.  We know that commit slab code wants you to count globally and\n> that is why you wrote this patch, but don't other parts of the code\n> expect and rely on the commits being counted per repository?  In\n> other words, with this change, who are you breaking to help the\n> commit slab code?\n\nI did a bit more digging, as I had a bit of time after pushing\ntoday's integration result out, and it turns out that in the today's\ncode, c->index is the only thing that uses this counter.  It is set\nin init_commit_node() function, which is called from object.c when\nan in-core commit object is created.  The callchain looks like this:\n\nobject_as_type(struct repository *, struct object *, enum object_type, int quiet)\n  -> init_commit_node(struct repository *, struct commit *)\n       -> alloc_commit_index(struct repository *)\n\nWhat is interesting is that object_as_type() takes the parameter\n\"struct repository *\" ONLY BECAUSE it needs to pass something to\ninit_commit_node(), which in turn takes it ONLY BECAUSE the\nalloc_commit_index() wants one to be passed.\n\nSince the ONLY reason why there needs a monotorically increasing\ncounter of in-core commit objects is because we need to be able to\nindex into the commit slab, and because we cannot make commit slabs\nper-repository due to the lack of backpointer from an in-core commit\nobject to the repository it belongs to, reverting 14ba97f8 (alloc:\nallow arbitrary repositories for alloc functions, 2018-05-15) is a\nreasonable thing to do, but then since the only reason the above\nthree functions in the callchain take \"struct repository *\" is\nbecause the bottom-most alloc_commit_index() wants it WHEN IT DOES\nNOT USE IT, it would be good to get rid of the \"struct repository\"\nparameter from the functions involved in the callchain altogether.\n\nThen we won't have to ask the \"who are we breaking with this change\"\nquestion.  At that point it would be clear that everybody would be\nOK with a single counter to ensure uniqueness of in-core commit\nacross all the in-core repository instances.\n\nThanks.\n"},{"id":"399633","messageId":"xmqq8sgr28yd.fsf@gitster.c.googlers.com","threadId":"53668","inReplyTo":"20200612184014.1226972-2-abhishekkumar8222@gmail.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-12T22:52:26Z","receivedAt":"2020-06-12T22:52:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n\n>  static unsigned int alloc_commit_index(struct repository *r)\n>  {\n> -\treturn r->parsed_objects->commit_count++;\n> +\tstatic unsigned int parsed_commits_count = 0;\n> +\tr->parsed_objects->commit_count++;\n> +\treturn parsed_commits_count++;\n>  }\n\nI'll queue this as-is, together with the rest of the series, but\nwith the following SQUASH??? to document why we are counting\nglobally.\n\nI do not think r->parsed_objects->*_count is used by anybody, and we\nprobably can eventually get rid of these stats fields, and when that\nhappens, we may want to lose the \"struct repository *\" pointer from\nthe functions in the callchain, but not right now.\n\nThanks.\n\n alloc.c | 5 +++++\n 1 file changed, 5 insertions(+)\n\ndiff --git a/alloc.c b/alloc.c\nindex 29f0e3aa80..ee92661b71 100644\n--- a/alloc.c\n+++ b/alloc.c\n@@ -99,6 +99,11 @@ void *alloc_object_node(struct repository *r)\n \treturn obj;\n }\n \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(struct repository *r)\n {\n \tstatic unsigned int parsed_commits_count = 0;\n-- \n2.27.0-90-geebb51ba8c\n\n"},{"id":"399635","messageId":"8b0facef-c85d-c25c-d49d-2bc1a3836e77@gmail.com","threadId":"53668","inReplyTo":"20200612184014.1226972-2-abhishekkumar8222@gmail.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-06-12T23:16:51Z","receivedAt":"2020-06-12T23:16:58Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On 12.06.2020, Abhishek Kumar wrote:\n\n> Commit slab relies on uniqueness of commit->index to access data. As\n> submodules are repositories on their own, alloc_commit_index() (which\n> depends on repository->parsed_objects->commit_count) no longer\n> returns unique values.\n> \n> This would break tests once we move `generation` and `graph_pos` into a\n> commit slab, as commits of supermodule and submodule can have the same\n> index but must have different graph positions.\n\nFirst, commits of supermodule and of submodule are in different graphs,\nso I don't see why they have to be in the same serialized commit-graph\nfile.\n\nSecond, Git stores many different types of information on slab already.\nHow comes that we have not had any problems till now?  \n\nThere is contains_cache, commit_seen, indegree_slab, author_date_slab,\ncommit_base, commit_pos, bloom_filter_slab, buffer_slab, commit_rev_name,\ncommit_names, commit_name_slab, saved_parents, blame_suspects,\ncommit_todo_item.\n\n> \n> Let's introduce a counter variable, `parsed_commits_count` to keep track\n> of parsed commits so far.\n\nAll right, thought it might be worth mentioning that it is a global\nvariable, or rather a static variable in a function.\n\n> \n> \n> Signed-off-by: Abhishek Kumar <abhishekkumar8222@gmail.com>\n> ---\n> \n> CI Build for the failing tests:\n> https://travis-ci.com/github/abhishekkumar2718/git/jobs/345413840\n\nThe failed tests are, from what I see:\n- t4060-diff-submodule-option-diff-format.sh\n- t4041-diff-submodule-option.sh\n- t4059-diff-submodule-not-initialized.sh\n\n\n> \n>   alloc.c | 4 +++-\n>   1 file changed, 3 insertions(+), 1 deletion(-)\n> \n> diff --git a/alloc.c b/alloc.c\n> index 1c64c4dd16..29f0e3aa80 100644\n> --- a/alloc.c\n> +++ b/alloc.c\n> @@ -101,7 +101,9 @@ void *alloc_object_node(struct repository *r)\n>   \n>   static unsigned int alloc_commit_index(struct repository *r)\n>   {\n> -\treturn r->parsed_objects->commit_count++;\n> +\tstatic unsigned int parsed_commits_count = 0;\n> +\tr->parsed_objects->commit_count++;\n\nDo we use r->parsed_objects->commit_count anywhere?\n\n> +\treturn parsed_commits_count++;\n\nDoes it matter that it is not thread safe, because it is not atomic?\nShouldn't it be\n\n  +\tstatic _Atomic unsigned int parsed_commits_count = 0;\n\nor\n\n  +\tstatic _Atomic unsigned int parsed_commits_count = ATOMIC_VAR_INIT(0);\n\n(If it is allowed).\n\n>   }\n>   \n>   void init_commit_node(struct repository *r, struct commit *c)\n> \n\n"},{"id":"399638","messageId":"20200613065339.GC2898@szeder.dev","threadId":"53668","inReplyTo":"20200612184014.1226972-3-abhishekkumar8222@gmail.com","subject":"Re: [PATCH v3 2/4] commit-graph: introduce commit_graph_data_slab","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-13T06:53:39Z","receivedAt":"2020-06-13T06:53:48Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Sat, Jun 13, 2020 at 12:10:12AM +0530, Abhishek Kumar wrote:\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 2ff042fbf4..91120ba3d3 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> +\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  commit-graph.c: At top level:\n  commit-graph.c:115:34: error: ‘commit_graph_data_at’ defined but not used [-Werror=unused-function]\n   static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\n                                    ^\n\nPlease make sure that each and every commit of your series can be\nbuilt with DEVELOPER=1 and passes the test suite.\n\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 initializing generation with checking if graph position\n> +\t * is not 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[i][j].graph_pos =\n\n  commit-graph.c: In function ‘commit_graph_data_at’:\n  commit-graph.c:131:26: error: subscripted value is neither array nor pointer nor vector\n      commit_graph_data_slab[i][j].graph_pos =\n                            ^\n\nOnce the next patch is applied Git can be built again, but then:\n\n  $ ~/src/git/git -C webkit.git commit-graph write\n  Finding commits for commit graph among packed objects: 100% (3984415/3984415), done.\n  Expanding reachable commits in commit graph: 219420, done.\n  Segmentation fault\n\nLooking at it with a debugger:\n\n  Program received signal SIGSEGV, Segmentation fault.\n  0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0) at commit-graph.c:131\n  131                             commit_graph_data_slab.slab[i][j].graph_pos =\n  (gdb) bt\n  #0  0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0)\n      at commit-graph.c:131\n  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)\n      at commit-graph.c:1304\n  #2  0x000000000050d37d in write_commit_graph (odb=0x9d3d80, pack_indexes=0x0, \n      commits=0x0, flags=COMMIT_GRAPH_WRITE_PROGRESS, \n      split_opts=0x98e730 <split_opts>) at commit-graph.c:2178\n  #3  0x000000000042bb7e in graph_write (argc=0, argv=0x7fffffffe2f0)\n      at builtin/commit-graph.c:242\n  #4  0x000000000042bc8d in cmd_commit_graph (argc=1, argv=0x7fffffffe2f0, \n      prefix=0x0) at builtin/commit-graph.c:278\n  #5  0x00000000004061d1 in run_builtin (p=0x97b950 <commands+528>, argc=2, \n      argv=0x7fffffffe2f0) at git.c:448\n  #6  0x0000000000406521 in handle_builtin (argc=2, argv=0x7fffffffe2f0)\n      at git.c:673\n  #7  0x00000000004067c9 in run_argv (argcp=0x7fffffffe18c, argv=0x7fffffffe180)\n      at git.c:740\n  #8  0x0000000000406c3a in cmd_main (argc=2, argv=0x7fffffffe2f0) at git.c:871\n  #9  0x00000000004cfbda in main (argc=5, argv=0x7fffffffe2d8)\n      at common-main.c:52\n  (gdb) p commit_graph_data_slab\n  $1 = {\n    slab_size = 65532, \n    stride = 1, \n    slab_count = 4, \n    slab = 0x4f68690\n  }\n  (gdb) p i\n  $2 = 0\n  (gdb) p commit_graph_data_slab.slab[i]\n  $3 = (struct commit_graph_data *) 0x0\n  (gdb) p c->index\n  $4 = 213506\n  (gdb) up\n  #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)\n      at commit-graph.c:1304\n  1304                    uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n  (gdb) p i\n  $5 = 0\n\n\nThe way the loop variable 'i' is initialized and is used in the loop\nheader suggests that you assume that all slabs with an index\n<slab_count are allocated.  That's not the case, only those slabs are\nallocated that contain data associated with a commit that has already\nbeen looked at.\n\n\n> +\t\t\t\tCOMMIT_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;\n> diff --git a/commit-graph.h b/commit-graph.h\n> index 3ba0da1e5f..cc76757007 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\nThis line adds a trailing space which is then removed in next patch.\nPlease don't add it in the first place.\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> \n"},{"id":"399666","messageId":"20200613185713.GA73354@Abhishek-Arch","threadId":"53668","inReplyTo":"xmqq8sgr28yd.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v3 1/4] alloc: introduce parsed_commits_count","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-13T18:57:13Z","receivedAt":"2020-06-13T18:59:02Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Fri, Jun 12, 2020 at 03:52:26PM -0700, Junio C Hamano wrote:\n> Abhishek Kumar <abhishekkumar8222@gmail.com> writes:\n> \n> >  static unsigned int alloc_commit_index(struct repository *r)\n> >  {\n> > -\treturn r->parsed_objects->commit_count++;\n> > +\tstatic unsigned int parsed_commits_count = 0;\n> > +\tr->parsed_objects->commit_count++;\n> > +\treturn parsed_commits_count++;\n> >  }\n> \n> I'll queue this as-is, together with the rest of the series, but\n> with the following SQUASH??? to document why we are counting\n> globally.\n> \n> I do not think r->parsed_objects->*_count is used by anybody, and we\n> probably can eventually get rid of these stats fields, and when that\n> happens, we may want to lose the \"struct repository *\" pointer from\n> the functions in the callchain, but not right now.\n> \n> Thanks.\n> \n>  alloc.c | 5 +++++\n>  1 file changed, 5 insertions(+)\n> \n> diff --git a/alloc.c b/alloc.c\n> index 29f0e3aa80..ee92661b71 100644\n> --- a/alloc.c\n> +++ b/alloc.c\n> @@ -99,6 +99,11 @@ void *alloc_object_node(struct repository *r)\n>  \treturn obj;\n>  }\n>  \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(struct repository *r)\n>  {\n>  \tstatic unsigned int parsed_commits_count = 0;\n> -- \n> 2.27.0-90-geebb51ba8c\n> \n\nThanks for taking a closer look. I have created an issue on\ngitgitgadget [1] to get rid of commit count and avoid passing repository\nto the functions anymore.\n\n[1]: https://github.com/gitgitgadget/git/issues/657\n\nAbhishek\n"},{"id":"399967","messageId":"20200617091822.GA26185@Abhishek-Arch","threadId":"53668","inReplyTo":"20200613065339.GC2898@szeder.dev","subject":"Re: [PATCH v3 2/4] commit-graph: introduce commit_graph_data_slab","fromName":"Abhishek Kumar","fromEmail":"abhishekkumar8222@gmail.com","sentAt":"2020-06-17T09:18:22Z","receivedAt":"2020-06-17T09:20:11Z","isPatch":true,"sender":{"key":"abhishekkumar8222@gmail.com","avatar":"https://avatars.githubusercontent.com/u/31231064?v=4"},"body":"On Sat, Jun 13, 2020 at 08:53:39AM +0200, SZEDER Gábor wrote:\n> On Sat, Jun 13, 2020 at 12:10:12AM +0530, Abhishek Kumar wrote:\n> > diff --git a/commit-graph.c b/commit-graph.c\n> > index 2ff042fbf4..91120ba3d3 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> > +\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>   commit-graph.c: At top level:\n>   commit-graph.c:115:34: error: ‘commit_graph_data_at’ defined but not used [-Werror=unused-function]\n>    static struct commit_graph_data *commit_graph_data_at(const struct commit *c)\n>                                     ^\n> \n> Please make sure that each and every commit of your series can be\n> built with DEVELOPER=1 and passes the test suite.\n> \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 initializing generation with checking if graph position\n> > +\t * is not 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[i][j].graph_pos =\n> \n>   commit-graph.c: In function ‘commit_graph_data_at’:\n>   commit-graph.c:131:26: error: subscripted value is neither array nor pointer nor vector\n>       commit_graph_data_slab[i][j].graph_pos =\n>                             ^\n> \n> Once the next patch is applied Git can be built again, but then:\n> \n>   $ ~/src/git/git -C webkit.git commit-graph write\n>   Finding commits for commit graph among packed objects: 100% (3984415/3984415), done.\n>   Expanding reachable commits in commit graph: 219420, done.\n>   Segmentation fault\n> \n> Looking at it with a debugger:\n> \n>   Program received signal SIGSEGV, Segmentation fault.\n>   0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0) at commit-graph.c:131\n>   131                             commit_graph_data_slab.slab[i][j].graph_pos =\n>   (gdb) bt\n>   #0  0x00000000005079b2 in commit_graph_data_at (c=0x1ad9aa0)\n>       at commit-graph.c:131\n>   #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)\n>       at commit-graph.c:1304\n>   #2  0x000000000050d37d in write_commit_graph (odb=0x9d3d80, pack_indexes=0x0, \n>       commits=0x0, flags=COMMIT_GRAPH_WRITE_PROGRESS, \n>       split_opts=0x98e730 <split_opts>) at commit-graph.c:2178\n>   #3  0x000000000042bb7e in graph_write (argc=0, argv=0x7fffffffe2f0)\n>       at builtin/commit-graph.c:242\n>   #4  0x000000000042bc8d in cmd_commit_graph (argc=1, argv=0x7fffffffe2f0, \n>       prefix=0x0) at builtin/commit-graph.c:278\n>   #5  0x00000000004061d1 in run_builtin (p=0x97b950 <commands+528>, argc=2, \n>       argv=0x7fffffffe2f0) at git.c:448\n>   #6  0x0000000000406521 in handle_builtin (argc=2, argv=0x7fffffffe2f0)\n>       at git.c:673\n>   #7  0x00000000004067c9 in run_argv (argcp=0x7fffffffe18c, argv=0x7fffffffe180)\n>       at git.c:740\n>   #8  0x0000000000406c3a in cmd_main (argc=2, argv=0x7fffffffe2f0) at git.c:871\n>   #9  0x00000000004cfbda in main (argc=5, argv=0x7fffffffe2d8)\n>       at common-main.c:52\n>   (gdb) p commit_graph_data_slab\n>   $1 = {\n>     slab_size = 65532, \n>     stride = 1, \n>     slab_count = 4, \n>     slab = 0x4f68690\n>   }\n>   (gdb) p i\n>   $2 = 0\n>   (gdb) p commit_graph_data_slab.slab[i]\n>   $3 = (struct commit_graph_data *) 0x0\n>   (gdb) p c->index\n>   $4 = 213506\n>   (gdb) up\n>   #1  0x000000000050a6a7 in compute_generation_numbers (ctx=0x9d61a0)\n>       at commit-graph.c:1304\n>   1304                    uint32_t generation = commit_graph_data_at(ctx->commits.list[i])->generation;\n>   (gdb) p i\n>   $5 = 0\n> \n> \n> The way the loop variable 'i' is initialized and is used in the loop\n> header suggests that you assume that all slabs with an index\n> <slab_count are allocated.  That's not the case, only those slabs are\n> allocated that contain data associated with a commit that has already\n> been looked at.\n> \n\nWait, so assuming there are no slabs before and I call\n`commit_graph_data_slab_at(&commit_graph_data_slab, c)` with an commit\nindex that would be in fourth slab, the slab would look like:\n\ncommit_graph_data_slab.slab[] = {NULL, NULL, NULL, <address>}\n\nThat's new to me! Thanks for sharing this.\n\nHopefully this is fixed in the v4 series here [1].\n\n[1]: https://lore.kernel.org/git/20200617091411.14650-1-abhishekkumar8222@gmail.com/T/#u\n\n> \n> > +\t\t\t\tCOMMIT_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;\n> > diff --git a/commit-graph.h b/commit-graph.h\n> > index 3ba0da1e5f..cc76757007 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> \n> This line adds a trailing space which is then removed in next patch.\n> Please don't add it in the first place.\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> > \n\nRegards\nAbhishek\n"}]}