{"thread":{"id":"53210","subject":"[PATCH 0/3] Integrate changed-path Bloom filters with 'git blame'","startedAt":"2020-04-11T01:03:06Z","lastAt":"2020-06-07T20:33:30Z","messageCount":48,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Eric Sunshine","Taylor Blau","Derrick Stolee","Jakub Narębski","SZEDER Gábor"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"395259","messageId":"pull.609.git.1586566981.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":null,"subject":"[PATCH 0/3] Integrate changed-path Bloom filters with 'git blame'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-11T01:02:58Z","receivedAt":"2020-04-11T01:03:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"If the changed-path Bloom filters are relatively stable, then I propose\ntrying to build upon them as a way to discover any deficiencies. Also, it's\ngood to use them when we can.\n\nThe goal I set out to achieve was to use Bloom filters as much as possible\nin git blame. I think I have achieved most of that, except I did not\nintegrate it with the -C mode. In that case, the blob-diff computation takes\na majority of the computation time, so short-circuiting the tree diff using\nBloom filters. Also, it's just really complicated. If someone else thinks\nthere is an easy win there, then please go ahead and give it a try with the\nextra logic presented here in PATCH 3.\n\nWhile I was playing around with Bloom filters and git blame, I purposefully\ngot it working with some scenarios but not all. Then I tried to trigger a\nfailing build in the blame tests using GIT_TEST_COMMIT_GRAPH=1 and \nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1. But the tests all succeeded!\n\nExamining the data, I see that the commit-graph didn't have the Bloom filter\nchunks at all. This is because we are not setting the flag to write them in\nthe right spot. The GIT_TEST_COMMIT_GRAPH=1 variable triggers a commit-graph\nwrite during git commit, so we need to update the code there instead of just\ninspecting the variable in git commit-graph write. (This is PATCH 2.)\n\nBy updating this variable, I saw some test failures in other tests regarding\nnon-exact pathspecs. I fixed these in PATCH 1 so we keep clean builds.\n\nI based this change on [1] but it would apply cleanly (and logically) on\ngs/commit-graph-path-filter\n\nThanks, -Stolee\n\n[1] \nhttps://lore.kernel.org/git/pull.601.v2.git.1586437211842.gitgitgadget@gmail.com/\n\nDerrick Stolee (3):\n revision: complicated pathspecs disable filters\n commit: write commit-graph with bloom filters\n blame: use changed-path Bloom filters\n\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++---\n blame.h | 6 ++\n builtin/blame.c | 10 ++++\n builtin/commit.c | 4 +-\n revision.c | 9 +++\n 5 files changed, 158 insertions(+), 10 deletions(-)\n\n\nbase-commit: f4df00a0dd448edce0e854a97f63598fefe27d27\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-609%2Fderrickstolee%2Fbloom-blame-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-609/derrickstolee/bloom-blame-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/609\n-- \ngitgitgadget\n"},{"id":"395260","messageId":"9cc31c289aa785f026eec84452ed68e80505d95e.1586566981.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.git.1586566981.gitgitgadget@gmail.com","subject":"[PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-11T01:02:59Z","receivedAt":"2020-04-11T01:03:07Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters work only when we can compute an\nexplicit Bloom filter key in advance. When a pathspec is given\nthat allows case-insensitive checks or wildcard matching, we\nmust disable the Bloom filter performance checks.\n\nBy checking the pathspec in prepare_to_use_bloom_filters(), we\navoid setting up the Bloom filter data and thus revert to the\nusual logic.\n\nBefore this change, the following tests would fail*:\n\n\tt6004-rev-list-path-optim.sh (Tests 6-7)\n\tt6130-pathspec-noglob.sh (Tests 3-6)\n\tt6131-pathspec-icase.sh (Tests 3-5)\n\n*These tests would fail when using GIT_TEST_COMMIT_GRAPH and\nGIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\nenvironment variable was not set up correctly to write the changed-\npath Bloom filters in the test suite. That will be fixed in the\nnext change.\n\nSigned-off-by: Derrick Stolee \n---\n revision.c | 9 +++++++++\n 1 file changed, 9 insertions(+)\n\ndiff --git a/revision.c b/revision.c\nindex 2b06ee739c8..e37b5b06108 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -661,6 +661,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n \tif (!revs->commits)\n \t return;\n \n+\tif (revs->prune_data.has_wildcard)\n+\t\treturn;\n+\tif (revs->prune_data.nr > 1)\n+\t\treturn;\n+\tif (revs->prune_data.magic ||\n+\t (revs->prune_data.nr &&\n+\t revs->prune_data.items[0].magic))\n+\t\treturn;\n+\n \trepo_parse_commit(revs->repo, revs->commits->item);\n \n \tif (!revs->repo->objects->commit_graph)\n-- \ngitgitgadget\n\n"},{"id":"395261","messageId":"bb5ce39d0283f14095d87dd0645e641ae799f16c.1586566981.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.git.1586566981.gitgitgadget@gmail.com","subject":"[PATCH 2/3] commit: write commit-graph with bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-11T01:03:00Z","receivedAt":"2020-04-11T01:03:08Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe GIT_TEST_COMMIT_GRAPH environment variable updates the commit-\ngraph file whenever \"git commit\" is run, ensuring that we always\nhave an updated commit-graph throughout the test suite. The\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variable was\nintroduced to write the changed-path Bloom filters whenever \"git\ncommit-graph write\" is run. However, the GIT_TEST_COMMIT_GRAPH\ntrick doesn't launch a separate process and instead writes it\ndirectly.\n\nUpdate the \"git commit\" builtin to write changed-path Bloom filters\nwhen both GIT_TEST_COMMIT_GRAPH and GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\nare enabled.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/commit.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/commit.c b/builtin/commit.c\nindex d3e7781e658..d2fdfdc4363 100644\n--- a/builtin/commit.c\n+++ b/builtin/commit.c\n@@ -1701,7 +1701,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n \n \tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n-\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n+\t write_commit_graph_reachable(the_repository->objects->odb,\n+\t\t\t\t\t git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0) ? COMMIT_GRAPH_WRITE_BLOOM_FILTERS : 0,\n+\t\t\t\t\t NULL))\n \t\treturn 1;\n \n \trepo_rerere(the_repository, 0);\n-- \ngitgitgadget\n\n"},{"id":"395262","messageId":"431fde6803140398eec0744c866616a0a78f9433.1586566981.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.git.1586566981.gitgitgadget@gmail.com","subject":"[PATCH 3/3] blame: use changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-11T01:03:01Z","receivedAt":"2020-04-11T01:03:12Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters help reduce the amount of tree\nparsing required during history queries. Before calculating a\ndiff, we can ask the filter if a path changed between a commit\nand its first parent. If the filter says \"no\" then we can move\non without parsing trees. If the filter says \"maybe\" then we\nparse trees to discover if the answer is actually \"yes\" or \"no\".\n\nWhen computing a blame, there is a section in find_origin() that\ncomputes a diff between a commit and one of its parents. When this\nis the first parent, we can check the Bloom filters before calling\ndiff_tree_oid().\n\nIn order to make this work with the blame machinery, we need to\ninitialize a struct bloom_key with the initial path. But also, we\nneed to add more keys to a list if a rename is detected. We then\ncheck to see if _any_ of these keys answer \"maybe\" in the diff.\n\nDuring development, I purposefully left out this \"add a new key\nwhen a rename is detected\" to see if the test suite would catch\nmy error. That is how I discovered the issues with\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS from the previous change.\nWith that change, we can feel some confidence in the coverage of\nthis change.\n\nIf a user requests copy detection using \"git blame -C\", then there\nare more places where the set of \"important\" files can expand. I\ndo not know enough about how this happens in the blame machinery.\nThus, the Bloom filter integration is explicitly disabled in this\nmode. A later change could expand the bloom_key data with an\nappropriate call (or calls) to add_bloom_key().\n\nIf we did not disable this mode, then the following tests would\nfail:\n\n\tt8003-blame-corner-cases.sh\n\tt8011-blame-split-file.sh\n\nGenerally, this is a performance enhancement and should not\nchange the behavior of 'git blame' in any way. If a repo has a\ncommit-graph file with computed changed-path Bloom filters, then\nthey should notice improved performance for their 'git blame'\ncommands.\n\nHere are some example timings that I found by blaming some paths\nin the Linux kernel repository:\n\n git blame arch/x86/kernel/topology.c >/dev/null\n\n Before: 0.83s\n After: 0.24s\n\n git blame kernel/time/time.c >/dev/null\n\n Before: 0.72s\n After: 0.24s\n\n git blame tools/perf/ui/stdio/hist.c >/dev/null\n\n Before: 0.27s\n After: 0.11s\n\nI specifically looked for \"deep\" paths that were also edited many\ntimes. As a counterpoint, the MAINTAINERS file was edited many\ntimes but is located in the root tree. This means that the cost of\ncomputing a diff relative to the pathspec is very small. Here are\nthe timings for that command:\n\n git blame MAINTAINERS >/dev/null\n\n Before: 20.1s\n After: 18.0s\n\nThese timings are the best of five. The worst-case runs were on the\norder of 2.5 minutes for both cases. Note that the MAINTAINERS file\nhas 18,740 lines across 17,000+ commits. This happens to be one of\nthe cases where this change provides the least improvement.\n\nThe lack of improvement for the MAINTAINERS file and the relatively\nmodest improvement for the other examples can be easily explained.\nThe blame machinery needs to compute line-level diffs to determine\nwhich lines were changed by each commit. That makes up a large\nproportion of the computation time, and this change does not\nattempt to improve on that section of the algorithm. The\nMAINTAINERS file is large and changed often, so it takes time to\ndetermine which lines were updated by which commit. In contrast,\nthe code files are much smaller, and it takes longer to comute\nthe line-by-line diff for a single patch on the Linux mailing\nlists.\n\nOutside of the \"-C\" integration, I believe there is little more to\ngain from the changed-path Bloom filters for 'git blame' after this\npatch.\n\nSigned-off-by: Derrick Stolee \n---\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++----\n blame.h | 6 +++\n builtin/blame.c | 10 ++++\n 3 files changed, 146 insertions(+), 9 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 29770e5c81c..9fbf79e47c3 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -9,6 +9,8 @@\n #include \"blame.h\"\n #include \"alloc.h\"\n #include \"commit-slab.h\"\n+#include \"bloom.h\"\n+#include \"commit-graph.h\"\n \n define_commit_slab(blame_suspects, struct blame_origin *);\n static struct blame_suspects blame_suspects;\n@@ -1246,13 +1248,75 @@ static int fill_blob_sha1_and_mode(struct repository *r,\n \treturn -1;\n }\n \n+struct blame_bloom_data {\n+\t/*\n+\t * Changed-path Bloom filter keys. These can help prevent\n+\t * computing diffs against first parents, but we need to\n+\t * expand the list as code is moved or files are renamed.\n+\t */\n+\tstruct bloom_filter_settings *settings;\n+\tstruct bloom_key **keys;\n+\tint nr;\n+\tint alloc;\n+};\n+\n+static int bloom_count_queries = 0;\n+static int bloom_count_no = 0;\n+static int maybe_changed_path(struct repository *r,\n+\t\t\t struct commit *parent,\n+\t\t\t struct blame_origin *origin,\n+\t\t\t struct blame_bloom_data *bd)\n+{\n+\tint i;\n+\tstruct bloom_filter *filter;\n+\n+\tif (!bd)\n+\t\treturn 1;\n+\n+\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\t\treturn 1;\n+\n+\tfilter = get_bloom_filter(r, origin->commit, 0);\n+\n+\tif (!filter)\n+\t\treturn 1;\n+\n+\tbloom_count_queries++;\n+\tfor (i = 0; i < bd->nr; i++) {\n+\t\tif (bloom_filter_contains(filter,\n+\t\t\t\t\t bd->keys[i],\n+\t\t\t\t\t bd->settings))\n+\t\t\treturn 1;\n+\t}\n+\n+\tbloom_count_no++;\n+\treturn 0;\n+}\n+\n+static void add_bloom_key(struct blame_bloom_data *bd,\n+\t\t\t const char *path)\n+{\n+\tif (!bd)\n+\t\treturn;\n+\n+\tif (bd->nr >= bd->alloc) {\n+\t\tbd->alloc *= 2;\n+\t\tREALLOC_ARRAY(bd->keys, bd->alloc);\n+\t}\n+\n+\tbd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));\n+\tfill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);\n+\tbd->nr++;\n+}\n+\n /*\n * We have an origin -- check if the same path exists in the\n * parent and return an origin structure to represent it.\n */\n static struct blame_origin *find_origin(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin;\n \tstruct diff_options diff_opts;\n@@ -1286,10 +1350,19 @@ static struct blame_origin *find_origin(struct repository *r,\n \n \tif (is_null_oid(&origin->commit->object.oid))\n \t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n-\telse\n-\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n-\t\t\t get_commit_tree_oid(origin->commit),\n-\t\t\t \"\", &diff_opts);\n+\telse {\n+\t\tint compute_diff = 1;\n+\t\tif (origin->commit->parents &&\n+\t\t !oidcmp(&parent->object.oid,\n+\t\t\t &origin->commit->parents->item->object.oid))\n+\t\t\tcompute_diff = maybe_changed_path(r, parent,\n+\t\t\t\t\t\t\t origin, bd);\n+\n+\t\tif (compute_diff)\n+\t\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t\t get_commit_tree_oid(origin->commit),\n+\t\t\t\t \"\", &diff_opts);\n+\t}\n \tdiffcore_std(&diff_opts);\n \n \tif (!diff_queued_diff.nr) {\n@@ -1341,7 +1414,8 @@ static struct blame_origin *find_origin(struct repository *r,\n */\n static struct blame_origin *find_rename(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin = NULL;\n \tstruct diff_options diff_opts;\n@@ -1366,6 +1440,7 @@ static struct blame_origin *find_rename(struct repository *r,\n \t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n \t\tif ((p->status == 'R' || p->status == 'C') &&\n \t\t !strcmp(p->two->path, origin->path)) {\n+\t\t\tadd_bloom_key(bd, p->one->path);\n \t\t\tporigin = get_origin(parent, p->one->path);\n \t\t\toidcpy(&porigin->blob_oid, &p->one->oid);\n \t\t\tporigin->mode = p->one->mode;\n@@ -2332,6 +2407,11 @@ static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *bl\n \n #define MAXSG 16\n \n+typedef struct blame_origin *(*blame_find_alg)(struct repository *,\n+\t\t\t\t\t struct commit *,\n+\t\t\t\t\t struct blame_origin *,\n+\t\t\t\t\t struct blame_bloom_data *);\n+\n static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, int opt)\n {\n \tstruct rev_info *revs = sb->revs;\n@@ -2356,8 +2436,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t * common cases, then we look for renames in the second pass.\n \t */\n \tfor (pass = 0; pass < 2 - sb->no_whole_file_rename; pass++) {\n-\t\tstruct blame_origin *(*find)(struct repository *, struct commit *, struct blame_origin *);\n-\t\tfind = pass ? find_rename : find_origin;\n+\t\tblame_find_alg find = pass ? find_rename : find_origin;\n \n \t\tfor (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);\n \t\t i < num_sg && sg;\n@@ -2369,7 +2448,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t\t\t\tcontinue;\n \t\t\tif (parse_commit(p))\n \t\t\t\tcontinue;\n-\t\t\tporigin = find(sb->repo, p, origin);\n+\t\t\tporigin = find(sb->repo, p, origin, sb->bloom_data);\n \t\t\tif (!porigin)\n \t\t\t\tcontinue;\n \t\t\tif (oideq(&porigin->blob_oid, &origin->blob_oid)) {\n@@ -2809,3 +2888,45 @@ struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \tblame_origin_incref(o);\n \treturn new_head;\n }\n+\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path)\n+{\n+\tstruct blame_bloom_data *bd;\n+\n+\tif (!sb->repo->objects->commit_graph)\n+\t\treturn;\n+\n+\tif (!sb->repo->objects->commit_graph->bloom_filter_settings)\n+\t\treturn;\n+\n+\tbd = xmalloc(sizeof(struct blame_bloom_data));\n+\n+\tbd->settings = sb->repo->objects->commit_graph->bloom_filter_settings;\n+\n+\tbd->alloc = 4;\n+\tbd->nr = 0;\n+\tALLOC_ARRAY(bd->keys, bd->alloc);\n+\n+\tadd_bloom_key(bd, path);\n+\n+\tsb->bloom_data = bd;\n+}\n+\n+void cleanup_scoreboard(struct blame_scoreboard *sb)\n+{\n+\tif (sb->bloom_data) {\n+\t\tint i;\n+\t\tfor (i = 0; i < sb->bloom_data->nr; i++) {\n+\t\t\tfree(sb->bloom_data->keys[i]->hashes);\n+\t\t\tfree(sb->bloom_data->keys[i]);\n+\t\t}\n+\t\tfree(sb->bloom_data->keys);\n+\t\tFREE_AND_NULL(sb->bloom_data);\n+\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/queries\", bloom_count_queries);\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/response-no\", bloom_count_no);\n+\t}\n+}\ndiff --git a/blame.h b/blame.h\nindex 089b181ff27..b6bbee41472 100644\n--- a/blame.h\n+++ b/blame.h\n@@ -100,6 +100,8 @@ struct blame_entry {\n \tint unblamable;\n };\n \n+struct blame_bloom_data;\n+\n /*\n * The current state of the blame assignment.\n */\n@@ -156,6 +158,7 @@ struct blame_scoreboard {\n \tvoid(*found_guilty_entry)(struct blame_entry *, void *);\n \n \tvoid *found_guilty_entry_data;\n+\tstruct blame_bloom_data *bloom_data;\n };\n \n /*\n@@ -180,6 +183,9 @@ void init_scoreboard(struct blame_scoreboard *sb);\n void setup_scoreboard(struct blame_scoreboard *sb,\n \t\t const char *path,\n \t\t struct blame_origin **orig);\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path);\n+void cleanup_scoreboard(struct blame_scoreboard *sb);\n \n struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \t\t\t\t\tlong start, long end,\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex bf1cecdf3f9..3c13634f279 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1061,6 +1061,14 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \tstring_list_clear(&ignore_revs_file_list, 0);\n \tstring_list_clear(&ignore_rev_list, 0);\n \tsetup_scoreboard(&sb, path, &o);\n+\n+\t/*\n+\t * Changed-path Bloom filters are disabled when looking\n+\t * for copies.\n+\t */\n+\tif (!(opt & PICKAXE_BLAME_COPY))\n+\t\tsetup_blame_bloom_data(&sb, path);\n+\n \tlno = sb.num_lines;\n \n \tif (lno && !range_list.nr)\n@@ -1164,5 +1172,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \t\tprintf(\"num get patch: %d\\n\", sb.num_get_patch);\n \t\tprintf(\"num commits: %d\\n\", sb.num_commits);\n \t}\n+\n+\tcleanup_scoreboard(&sb);\n \treturn 0;\n }\n-- \ngitgitgadget\n"},{"id":"395285","messageId":"xmqqimi5hfrj.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"pull.609.git.1586566981.gitgitgadget@gmail.com","subject":"Re: [PATCH 0/3] Integrate changed-path Bloom filters with 'git blame'","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-11T21:30:24Z","receivedAt":"2020-04-11T21:30:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> The goal I set out to achieve was to use Bloom filters as much as possible\n> in git blame.\n\nExciting. Uncomfortably exciting.\n\nThanks.\n"},{"id":"395286","messageId":"xmqqeesthfbf.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"9cc31c289aa785f026eec84452ed68e80505d95e.1586566981.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-11T21:40:04Z","receivedAt":"2020-04-11T21:42:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n>\n> The changed-path Bloom filters work only when we can compute an\n> explicit Bloom filter key in advance. When a pathspec is given\n> that allows case-insensitive checks or wildcard matching, we\n> must disable the Bloom filter performance checks.\n\nHow often do we want to do case-insensitive path matching, I wonder.\n\nAs somebody who never touches case-insensitive filesystem, I would\nbe a bad judge, and I would imagine that I would be looking for a\npathspec \"[Mm]akefile\" rather than \":(icase)makefile\" myself if\nthere are projects that may have either/both, so I do not mind\ndisabling the bloom filter for case insensitivity myself.\n\nBut if users may use icase pathspec very often, it may be worth\nconsidering to build the bloom filter after downcasing the paths,\nperhaps? Given that many projects extract their source code to a\ncase insensitive filesystem, I would imagine that downcasing paths\nwould map two originally different paths into the same thing only\nrarely, if ever, so there may not be much downside to do so.\n\n> By checking the pathspec in prepare_to_use_bloom_filters(), we\n> avoid setting up the Bloom filter data and thus revert to the\n> usual logic.\n>\n> Before this change, the following tests would fail*:\n>\n> \tt6004-rev-list-path-optim.sh (Tests 6-7)\n> \tt6130-pathspec-noglob.sh (Tests 3-6)\n> \tt6131-pathspec-icase.sh (Tests 3-5)\n>\n> *These tests would fail when using GIT_TEST_COMMIT_GRAPH and\n> GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\n> environment variable was not set up correctly to write the changed-\n> path Bloom filters in the test suite. That will be fixed in the\n> next change.\n\nThanks. This is exciting.\n"},{"id":"395288","messageId":"xmqqa73hheip.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"bb5ce39d0283f14095d87dd0645e641ae799f16c.1586566981.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 2/3] commit: write commit-graph with bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-11T21:57:18Z","receivedAt":"2020-04-11T21:57:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> diff --git a/builtin/commit.c b/builtin/commit.c\n> index d3e7781e658..d2fdfdc4363 100644\n> --- a/builtin/commit.c\n> +++ b/builtin/commit.c\n> @@ -1701,7 +1701,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n> \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n> \n> \tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n> -\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n> +\t write_commit_graph_reachable(the_repository->objects->odb,\n> +\t\t\t\t\t git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0) ? COMMIT_GRAPH_WRITE_BLOOM_FILTERS : 0,\n> +\t\t\t\t\t NULL))\n\nYuck. That is doubly mouthful.\n\nI wonder how much value we are getting by having this call here in\nthe first place. This function being cmd_commit(), by definition we\nwon't be updating the graph file unless the test script does \"git\ncommit\". We won't update the graph file upon \"git rebase\", \"git\nmerge\", \"git pull\", \"git fetch\", etc., so it is not like with this\nhack, the test coverage for various traversal using the graph file\nwould magically be perfect. We'd still need an explicit call to\n\"commit-graph write\" at strategic places in the test scripts, no?\n\nHow are we testing with and without bitmaps, and do we have a kludge\nlike this one for the feature, or do we use a different mechanism\nto help writing tests easier to gain better coverage?\n\nIn any case, I can see why we want a separate knob specific to the\nCHANGED_PATHS until the path filter part becomes as stable as the\nrest of the graph file, but after some time, we should remove that\nknob, and at that point, we always use the path filter whenever we\nuse commit-graph, so that we won't have to suffer from the ugliness.\n\nWait. I wonder if we can tweak the arrangement a bit so that this\nlayer does not need to know any more than GIT_TEST_COMMIT_GRAPH?\n\nFor example, in commit-graph.c::write_commit_graph(), can we test\nthe CHANGED_PATHS environment variable and flip the .changed_paths\nbit, no matter what the 'flags' argument to the function says?\n\nThanks.\n\n> \t\treturn 1;\n> \n> \trepo_rerere(the_repository, 0);\n"},{"id":"395289","messageId":"xmqq5ze5he8o.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"431fde6803140398eec0744c866616a0a78f9433.1586566981.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 3/3] blame: use changed-path Bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-11T22:03:19Z","receivedAt":"2020-04-11T22:03:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> From: Derrick Stolee \n> Subject: Re: [PATCH 3/3] blame: use changed-path Bloom filters\n\nAhh, I almost forgot we spell Bloom with capital B, so I should go\nback and amend the title of [2/3].\n\n> When computing a blame, there is a section in find_origin() that\n> computes a diff between a commit and one of its parents. When this\n> is the first parent, we can check the Bloom filters before calling\n> diff_tree_oid().\n>\n> In order to make this work with the blame machinery, we need to\n> initialize a struct bloom_key with the initial path. But also, we\n> need to add more keys to a list if a rename is detected. We then\n> check to see if _any_ of these keys answer \"maybe\" in the diff.\n\nYes. I think after gaining experience with this technique, we may\nbe able to speed up the \"git log --follow\" while correcting its\nsemantics at the same time. The prospect is unnervingly exciting.\n\n> Generally, this is a performance enhancement and should not\n> change the behavior of 'git blame' in any way.\n\nAbsolutely.\n\n> The lack of improvement for the MAINTAINERS file and the relatively\n> modest improvement for the other examples can be easily explained.\n> The blame machinery needs to compute line-level diffs to determine\n> which lines were changed by each commit. That makes up a large\n> proportion of the computation time, and this change does not\n> attempt to improve on that section of the algorithm. The\n> MAINTAINERS file is large and changed often, so it takes time to\n> determine which lines were updated by which commit. In contrast,\n> the code files are much smaller, and it takes longer to comute\n> the line-by-line diff for a single patch on the Linux mailing\n> lists.\n\nYup, tree-diff for a deeper path would benefit the most, and your\nnumbers were indeed impressive.\n\n> Signed-off-by: Derrick Stolee \n> ---\n> blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++----\n> blame.h | 6 +++\n> builtin/blame.c | 10 ++++\n> 3 files changed, 146 insertions(+), 9 deletions(-)\n\nI am kind-a surprised how little additional code it takes to do\nthis. Good job.\n"},{"id":"395291","messageId":"CAPig+cRm515C05SD_ivZmdPEUW=Tw3j2r4_p9_oSmRjs++BLZw@mail.gmail.com","threadId":"53210","inReplyTo":"xmqq5ze5he8o.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 3/3] blame: use changed-path Bloom filters","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2020-04-12T07:39:33Z","receivedAt":"2020-04-12T07:39:49Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Apr 11, 2020 at 6:03 PM Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> > The lack of improvement for the MAINTAINERS file and the relatively\n> > modest improvement for the other examples can be easily explained.\n> > The blame machinery needs to compute line-level diffs to determine\n> > which lines were changed by each commit. That makes up a large\n> > proportion of the computation time, and this change does not\n> > attempt to improve on that section of the algorithm. The\n> > MAINTAINERS file is large and changed often, so it takes time to\n> > determine which lines were updated by which commit. In contrast,\n> > the code files are much smaller, and it takes longer to comute\n> > the line-by-line diff for a single patch on the Linux mailing\n> > lists.\n\ns/comute/compute/\n\n(Sorry for replying to Junio's reply -- the original is no longer in\nmy mailbox.)\n"},{"id":"395306","messageId":"20200412205148.GB50412@syl.local","threadId":"53210","inReplyTo":"xmqqa73hheip.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 2/3] commit: write commit-graph with bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-12T20:51:48Z","receivedAt":"2020-04-12T20:51:57Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sat, Apr 11, 2020 at 02:57:18PM -0700, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>\n> > diff --git a/builtin/commit.c b/builtin/commit.c\n> > index d3e7781e658..d2fdfdc4363 100644\n> > --- a/builtin/commit.c\n> > +++ b/builtin/commit.c\n> > @@ -1701,7 +1701,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n> > \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n> >\n> > \tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n> > -\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n> > +\t write_commit_graph_reachable(the_repository->objects->odb,\n> > +\t\t\t\t\t git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0) ? COMMIT_GRAPH_WRITE_BLOOM_FILTERS : 0,\n> > +\t\t\t\t\t NULL))\n>\n> Yuck. That is doubly mouthful.\n\nYeah, this is quite a mouthful indeed. I think the most conservative fix\nwould be something like:\n\n if (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0)) {\n enum commit_graph_write_flags flags = 0;\n if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;\n\n if (write_commit_graph_reachable(the_repository->objects->odb,\n flags, NULL)) {\n /* ... */\n }\n }\n\nand then ripping this knob out (as Junio suggests below, which I think\nis a wise suggestion) out would be straightforward.\n\n> I wonder how much value we are getting by having this call here in\n> the first place. This function being cmd_commit(), by definition we\n> won't be updating the graph file unless the test script does \"git\n> commit\". We won't update the graph file upon \"git rebase\", \"git\n> merge\", \"git pull\", \"git fetch\", etc., so it is not like with this\n> hack, the test coverage for various traversal using the graph file\n> would magically be perfect. We'd still need an explicit call to\n> \"commit-graph write\" at strategic places in the test scripts, no?\n\nYeah. It's definitely not a silver bullet for the reasons you mention,\nbut I think that it is helping out in some common cases. For example,\nif we moved this check out to 'test_commit', then we'd be relying on\ntests to use that instead of 'git commit'. On the other hand, this\ncatches either, since they both wind up in this builtin.\n\nI guess you could push this check down much further to when we're about\nto write a new object, and--if that new object is a commit--update the\ncommit-graph. That sounds awfully slow (and feels to me like a hack, but\nI can't justify whether it's more or less of a hack than we already\nhave), but I think it would be OK, since this isn't the normal way to\nrun tests.\n\n> How are we testing with and without bitmaps, and do we have a kludge\n> like this one for the feature, or do we use a different mechanism\n> to help writing tests easier to gain better coverage?\n\nAs far as I know after a brief search, we have no similar such mechanism\nfor bitmaps, so commit-graphs are a unique instance.\n\n> In any case, I can see why we want a separate knob specific to the\n> CHANGED_PATHS until the path filter part becomes as stable as the\n> rest of the graph file, but after some time, we should remove that\n> knob, and at that point, we always use the path filter whenever we\n> use commit-graph, so that we won't have to suffer from the ugliness.\n>\n> Wait. I wonder if we can tweak the arrangement a bit so that this\n> layer does not need to know any more than GIT_TEST_COMMIT_GRAPH?\n>\n> For example, in commit-graph.c::write_commit_graph(), can we test\n> the CHANGED_PATHS environment variable and flip the .changed_paths\n> bit, no matter what the 'flags' argument to the function says?\n\nIt may be cleaner to have 'GIT_TEST_COMMIT_GRAPH' specify the flags that\nit wants as its value, but the additional coupling makes me somewhat\nuncomfortable.\n\n> Thanks.\n>\n> > \t\treturn 1;\n> >\n> > \trepo_rerere(the_repository, 0);\n\nThanks,\nTaylor\n"},{"id":"395312","messageId":"20200412222210.GA53057@syl.local","threadId":"53210","inReplyTo":"9cc31c289aa785f026eec84452ed68e80505d95e.1586566981.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-12T22:22:10Z","receivedAt":"2020-04-12T22:22:17Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"Hi Stolee,\n\nOn Sat, Apr 11, 2020 at 01:02:59AM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> The changed-path Bloom filters work only when we can compute an\n> explicit Bloom filter key in advance. When a pathspec is given\n> that allows case-insensitive checks or wildcard matching, we\n> must disable the Bloom filter performance checks.\n>\n> By checking the pathspec in prepare_to_use_bloom_filters(), we\n> avoid setting up the Bloom filter data and thus revert to the\n> usual logic.\n\nAll makes sense to me, and this seems like the only reasonable thing\n*to* do in this situation. That's fine, since we're not regressing,\nwe're just not using Bloom filters.\n\n> Before this change, the following tests would fail*:\n>\n> \tt6004-rev-list-path-optim.sh (Tests 6-7)\n> \tt6130-pathspec-noglob.sh (Tests 3-6)\n> \tt6131-pathspec-icase.sh (Tests 3-5)\n>\n> *These tests would fail when using GIT_TEST_COMMIT_GRAPH and\n> GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\n> environment variable was not set up correctly to write the changed-\n> path Bloom filters in the test suite. That will be fixed in the\n> next change.\n\nNicely done.\n\n> Signed-off-by: Derrick Stolee \n> ---\n> revision.c | 9 +++++++++\n> 1 file changed, 9 insertions(+)\n>\n> diff --git a/revision.c b/revision.c\n> index 2b06ee739c8..e37b5b06108 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -661,6 +661,15 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> \tif (!revs->commits)\n> \t return;\n>\n\nI certainly wouldn't complain about a comment here explaining these\nthree checks, but I suppose that the rationale is only a 'git blame'\naway (and I guess that is faster now after this series ;-)).\n\n> +\tif (revs->prune_data.has_wildcard)\n> +\t\treturn;\n> +\tif (revs->prune_data.nr > 1)\n> +\t\treturn;\n> +\tif (revs->prune_data.magic ||\n> +\t (revs->prune_data.nr &&\n> +\t revs->prune_data.items[0].magic))\n> +\t\treturn;\n> +\n> \trepo_parse_commit(revs->repo, revs->commits->item);\n>\n> \tif (!revs->repo->objects->commit_graph)\n> --\n> gitgitgadget\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"395314","messageId":"xmqqa73gcp74.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"20200412222210.GA53057@syl.local","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-12T22:30:07Z","receivedAt":"2020-04-12T22:30:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> I certainly wouldn't complain about a comment here explaining these\n> three checks, but I suppose that the rationale is only a 'git blame'\n> away (and I guess that is faster now after this series ;-)).\n>\n>> +\tif (revs->prune_data.has_wildcard)\n>> +\t\treturn;\n>> +\tif (revs->prune_data.nr > 1)\n>> +\t\treturn;\n>> +\tif (revs->prune_data.magic ||\n>> +\t (revs->prune_data.nr &&\n>> +\t revs->prune_data.items[0].magic))\n\nThis says \"any magic\", but it is overly pessimistic to disable the\noptimization for \"literal\" magic. That magic is the one that lets\nwell written scripts to say \"I have in a '$variable' that the user\ngave me as a pathname (not pathspec), and it may have a wildcard\nletter in it, but please treat it as a literal string\" by prefixing\n\":(literal)\" before that user-supplied data, so it is punishing well\ndisciplined folks.\n\n>> +\t\treturn;\n>> +\n>> \trepo_parse_commit(revs->repo, revs->commits->item);\n>>\n>> \tif (!revs->repo->objects->commit_graph)\n>> --\n>> gitgitgadget\n>\n> Reviewed-by: Taylor Blau \n>\n> Thanks,\n> Taylor\n"},{"id":"395315","messageId":"20200413000748.GA55122@syl.local","threadId":"53210","inReplyTo":"xmqqa73gcp74.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-13T00:07:48Z","receivedAt":"2020-04-13T00:07:53Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Sun, Apr 12, 2020 at 03:30:07PM -0700, Junio C Hamano wrote:\n> Taylor Blau writes:\n>\n> > I certainly wouldn't complain about a comment here explaining these\n> > three checks, but I suppose that the rationale is only a 'git blame'\n> > away (and I guess that is faster now after this series ;-)).\n> >\n> >> +\tif (revs->prune_data.has_wildcard)\n> >> +\t\treturn;\n> >> +\tif (revs->prune_data.nr > 1)\n> >> +\t\treturn;\n> >> +\tif (revs->prune_data.magic ||\n> >> +\t (revs->prune_data.nr &&\n> >> +\t revs->prune_data.items[0].magic))\n>\n> This says \"any magic\", but it is overly pessimistic to disable the\n> optimization for \"literal\" magic. That magic is the one that lets\n> well written scripts to say \"I have in a '$variable' that the user\n> gave me as a pathname (not pathspec), and it may have a wildcard\n> letter in it, but please treat it as a literal string\" by prefixing\n> \":(literal)\" before that user-supplied data, so it is punishing well\n> disciplined folks.\n\nI hadn't thought of that, but it makes sense to me. How about something\nlike this squashed into this patch? I moved the if-chain that Stolee\nintroduced out to its own function, at least since they seem\nwell-contained and related to one another. I figure that this simplifies\nthe implementation of 'prepare_to_use_bloom_filter' by giving the reader\nless to think about up-front.\n\ndiff --git a/revision.c b/revision.c\nindex 534c0bf996..15bf4ccff5 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -654,6 +654,18 @@ static void trace2_bloom_filter_statistics_atexit(void)\n jw_release(&jw);\n }\n\n+static int has_bloom_key(struct pathspec *spec)\n+{\n+ if (spec->has_wildcard)\n+ return 0;\n+ if (spec->nr > 1)\n+ return 0;\n+ if ((spec->magic & ~PATHSPEC_LITERAL) ||\n+ (spec->nr && spec->items[0].magic & ~PATHSPEC_LITERAL))\n+ return 0;\n+ return 1;\n+}\n+\n static void prepare_to_use_bloom_filter(struct rev_info *revs)\n {\n struct pathspec_item *pi;\n@@ -665,13 +677,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n if (!revs->commits)\n return;\n\n- if (revs->prune_data.has_wildcard)\n- return;\n- if (revs->prune_data.nr > 1)\n- return;\n- if (revs->prune_data.magic ||\n- (revs->prune_data.nr &&\n- revs->prune_data.items[0].magic))\n+ if (!has_bloom_key(&revs->prune_data))\n return;\n\n repo_parse_commit(revs->repo, revs->commits->item);\n\n> >> +\t\treturn;\n> >> +\n> >> \trepo_parse_commit(revs->repo, revs->commits->item);\n> >>\n> >> \tif (!revs->repo->objects->commit_graph)\n> >> --\n> >> gitgitgadget\n> >\n> > Reviewed-by: Taylor Blau \n> >\n> > Thanks,\n> > Taylor\n\nThanks,\nTaylor\n"},{"id":"395327","messageId":"44ce43e2-6cf0-0e48-18eb-f02543d81bf4@gmail.com","threadId":"53210","inReplyTo":"xmqqeesthfbf.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-13T11:49:12Z","receivedAt":"2020-04-13T11:54:46Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/11/2020 5:40 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> From: Derrick Stolee \n>>\n>> The changed-path Bloom filters work only when we can compute an\n>> explicit Bloom filter key in advance. When a pathspec is given\n>> that allows case-insensitive checks or wildcard matching, we\n>> must disable the Bloom filter performance checks.\n> \n> How often do we want to do case-insensitive path matching, I wonder.\n> \n> As somebody who never touches case-insensitive filesystem, I would\n> be a bad judge, and I would imagine that I would be looking for a\n> pathspec \"[Mm]akefile\" rather than \":(icase)makefile\" myself if\n> there are projects that may have either/both, so I do not mind\n> disabling the bloom filter for case insensitivity myself.\n> \n> But if users may use icase pathspec very often, it may be worth\n> considering to build the bloom filter after downcasing the paths,\n> perhaps? Given that many projects extract their source code to a\n> case insensitive filesystem, I would imagine that downcasing paths\n> would map two originally different paths into the same thing only\n> rarely, if ever, so there may not be much downside to do so.\n\nThis behavior could be extended later, and carefully. My initial\nthought was that the case check would happen on every commit. If\nthe :(icase) check only happens at the walk tip(s), then we could\ncompute a single Bloom key at the start.\n\nThanks,\n-Stolee\n"},{"id":"395328","messageId":"4a3af6a9-50ef-1759-7e4c-56f6c5af542a@gmail.com","threadId":"53210","inReplyTo":"20200413000748.GA55122@syl.local","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-13T11:54:48Z","receivedAt":"2020-04-13T11:59:26Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/12/2020 8:07 PM, Taylor Blau wrote:\n> On Sun, Apr 12, 2020 at 03:30:07PM -0700, Junio C Hamano wrote:\n>> Taylor Blau writes:\n>>\n>>> I certainly wouldn't complain about a comment here explaining these\n>>> three checks, but I suppose that the rationale is only a 'git blame'\n>>> away (and I guess that is faster now after this series ;-)).\n>>>\n>>>> +\tif (revs->prune_data.has_wildcard)\n>>>> +\t\treturn;\n>>>> +\tif (revs->prune_data.nr > 1)\n>>>> +\t\treturn;\n>>>> +\tif (revs->prune_data.magic ||\n>>>> +\t (revs->prune_data.nr &&\n>>>> +\t revs->prune_data.items[0].magic))\n>>\n>> This says \"any magic\", but it is overly pessimistic to disable the\n>> optimization for \"literal\" magic. That magic is the one that lets\n>> well written scripts to say \"I have in a '$variable' that the user\n>> gave me as a pathname (not pathspec), and it may have a wildcard\n>> letter in it, but please treat it as a literal string\" by prefixing\n>> \":(literal)\" before that user-supplied data, so it is punishing well\n>> disciplined folks.\n\nThis is a good point. I'm unfamiliar with these advanced pathspec\ntricks.\n\n> I hadn't thought of that, but it makes sense to me. How about something\n> like this squashed into this patch? I moved the if-chain that Stolee\n> introduced out to its own function, at least since they seem\n> well-contained and related to one another. I figure that this simplifies\n> the implementation of 'prepare_to_use_bloom_filter' by giving the reader\n> less to think about up-front.\n> \n> diff --git a/revision.c b/revision.c\n> index 534c0bf996..15bf4ccff5 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -654,6 +654,18 @@ static void trace2_bloom_filter_statistics_atexit(void)\n> jw_release(&jw);\n> }\n> \n> +static int has_bloom_key(struct pathspec *spec)\n> +{\n> + if (spec->has_wildcard)\n> + return 0;\n> + if (spec->nr > 1)\n> + return 0;\n> + if ((spec->magic & ~PATHSPEC_LITERAL) ||\n> + (spec->nr && spec->items[0].magic & ~PATHSPEC_LITERAL))\n> + return 0;\n> + return 1;\n> +}\n> +\n\nPerhaps flip this on its head?\n\n+static int forbids_bloom_key(struct pathspec *spec)\n+{\n+ if (spec->has_wildcard)\n+ return 1;\n+ if (spec->nr > 1)\n+ return 1;\n+ if (spec->magic & ~PATHSPEC_LITERAL)\n+\t\treturn 1;\n+\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n+ return 1;\n+ return 0;\n+}\n+\n\n> static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> {\n> struct pathspec_item *pi;\n> @@ -665,13 +677,7 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> if (!revs->commits)\n> return;\n> \n> - if (revs->prune_data.has_wildcard)\n> - return;\n> - if (revs->prune_data.nr > 1)\n> - return;\n> - if (revs->prune_data.magic ||\n> - (revs->prune_data.nr &&\n> - revs->prune_data.items[0].magic))\n> + if (!has_bloom_key(&revs->prune_data))\n> return;\n\nThen this would be \"if (forbids_bloom_key(&revs->prune_data))\"\n\nGenerally, I like pulling this stuff out as a method to isolate and\nlabel its purpose. If we wanted to allow certain :(icase) things\nlater, then we know what to modify in order to \"allow\" it.\n\nThanks,\n-Stolee\n"},{"id":"395329","messageId":"8ef47003-784d-6a27-666d-5c916c4deb33@gmail.com","threadId":"53210","inReplyTo":"20200412205148.GB50412@syl.local","subject":"Re: [PATCH 2/3] commit: write commit-graph with bloom filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-13T12:08:50Z","receivedAt":"2020-04-13T12:08:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/12/2020 4:51 PM, Taylor Blau wrote:\n> On Sat, Apr 11, 2020 at 02:57:18PM -0700, Junio C Hamano wrote:\n>> \"Derrick Stolee via GitGitGadget\" writes:\n>>\n>>> diff --git a/builtin/commit.c b/builtin/commit.c\n>>> index d3e7781e658..d2fdfdc4363 100644\n>>> --- a/builtin/commit.c\n>>> +++ b/builtin/commit.c\n>>> @@ -1701,7 +1701,9 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n>>> \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n>>>\n>>> \tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n>>> -\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n>>> +\t write_commit_graph_reachable(the_repository->objects->odb,\n>>> +\t\t\t\t\t git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0) ? COMMIT_GRAPH_WRITE_BLOOM_FILTERS : 0,\n>>> +\t\t\t\t\t NULL))\n>>\n>> Yuck. That is doubly mouthful.\n> \n> Yeah, this is quite a mouthful indeed. I think the most conservative fix\n> would be something like:\n> \n> if (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0)) {\n> enum commit_graph_write_flags flags = 0;\n> if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n> flags |= COMMIT_GRAPH_WRITE_BLOOM_FILTERS;\n> \n> if (write_commit_graph_reachable(the_repository->objects->odb,\n> flags, NULL)) {\n> /* ... */\n> }\n> }\n> \n> and then ripping this knob out (as Junio suggests below, which I think\n> is a wise suggestion) out would be straightforward.\n> \n>> I wonder how much value we are getting by having this call here in\n>> the first place. This function being cmd_commit(), by definition we\n>> won't be updating the graph file unless the test script does \"git\n>> commit\". We won't update the graph file upon \"git rebase\", \"git\n>> merge\", \"git pull\", \"git fetch\", etc., so it is not like with this\n>> hack, the test coverage for various traversal using the graph file\n>> would magically be perfect. We'd still need an explicit call to\n>> \"commit-graph write\" at strategic places in the test scripts, no?\n> \n> Yeah. It's definitely not a silver bullet for the reasons you mention,\n> but I think that it is helping out in some common cases. For example,\n> if we moved this check out to 'test_commit', then we'd be relying on\n> tests to use that instead of 'git commit'. On the other hand, this\n> catches either, since they both wind up in this builtin.\n> \n> I guess you could push this check down much further to when we're about\n> to write a new object, and--if that new object is a commit--update the\n> commit-graph. That sounds awfully slow (and feels to me like a hack, but\n> I can't justify whether it's more or less of a hack than we already\n> have), but I think it would be OK, since this isn't the normal way to\n> run tests.\n\nIf we keep this simple, or extract the process to a\n\"write_commit_graph_for_tests()\" macro inside builtin.h, then we could\ninsert a commit-graph write in more places.\n\nHowever, I think there is value in testing the \"not every commit is\nincluded in the commit-graph\" case, which our current setup does quite\nnicely. The one exception is that 'git merge' could benefit from this\nsnippet, so we cap off the commit-graph whenever a test script\n\"constructs\" a repository to match a data shape.\n\n>> How are we testing with and without bitmaps, and do we have a kludge\n>> like this one for the feature, or do we use a different mechanism\n>> to help writing tests easier to gain better coverage?\n> \n> As far as I know after a brief search, we have no similar such mechanism\n> for bitmaps, so commit-graphs are a unique instance.\n\nI would not be against a similar mechanism for bitmaps, but this is\nreally important for commit-graphs. The difference lies in which users\nhave commit-graphs versus bitmaps. Now that commit-graphs are on by\ndefault and written by 'git gc', client users get commit-graphs unless\nthey opt-out. We need to test as many scenarios as possible to avoid\ncausing them disruption.\n\nWho uses bitmaps? Primarily Git servers. The scenarios run on those\nrepos are much more restricted, and those scenarios are tested with\nbitmaps explicitly.\n\n>> In any case, I can see why we want a separate knob specific to the\n>> CHANGED_PATHS until the path filter part becomes as stable as the\n>> rest of the graph file, but after some time, we should remove that\n>> knob, and at that point, we always use the path filter whenever we\n>> use commit-graph, so that we won't have to suffer from the ugliness.\n>>\n>> Wait. I wonder if we can tweak the arrangement a bit so that this\n>> layer does not need to know any more than GIT_TEST_COMMIT_GRAPH?\n>>\n>> For example, in commit-graph.c::write_commit_graph(), can we test\n>> the CHANGED_PATHS environment variable and flip the .changed_paths\n>> bit, no matter what the 'flags' argument to the function says?\n> \n> It may be cleaner to have 'GIT_TEST_COMMIT_GRAPH' specify the flags that\n> it wants as its value, but the additional coupling makes me somewhat\n> uncomfortable.\n\nIt would be easy to insert it here: \n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 77668629e2..3e8f36ce5c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1968,6 +1968,8 @@ int write_commit_graph(struct object_directory *odb,\n ctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;\n ctx->split_opts = split_opts;\n ctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;\n+ if (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n+ ctx->changed_paths = 1;\n ctx->total_bloom_filter_data_size = 0;\n \n if (ctx->split) {\n\nThe problem here is that if GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1 and\nsomeone runs \"git commit-graph write --no-changed-paths\" then the\nnegation of that option is ignored. But this is a GIT_TEST_* variable,\nand any test that requires that check could disable the enviroment\nvariable first.\n\nThanks,\n-Stolee\n"},{"id":"395337","messageId":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.git.1586566981.gitgitgadget@gmail.com","subject":"[PATCH v2 0/4] Integrate changed-path Bloom filters with 'git blame'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-13T14:45:22Z","receivedAt":"2020-04-13T14:45:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"If the changed-path Bloom filters are relatively stable, then I propose\ntrying to build upon them as a way to discover any deficiencies. Also, it's\ngood to use them when we can.\n\nThe goal I set out to achieve was to use Bloom filters as much as possible\nin git blame. I think I have achieved most of that, except I did not\nintegrate it with the -C mode. In that case, the blob-diff computation takes\na majority of the computation time, so short-circuiting the tree diff using\nBloom filters. Also, it's just really complicated. If someone else thinks\nthere is an easy win there, then please go ahead and give it a try with the\nextra logic presented here in PATCH 3.\n\nWhile I was playing around with Bloom filters and git blame, I purposefully\ngot it working with some scenarios but not all. Then I tried to trigger a\nfailing build in the blame tests using GIT_TEST_COMMIT_GRAPH=1 and \nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1. But the tests all succeeded!\n\nExamining the data, I see that the commit-graph didn't have the Bloom filter\nchunks at all. This is because we are not setting the flag to write them in\nthe right spot. The GIT_TEST_COMMIT_GRAPH=1 variable triggers a commit-graph\nwrite during git commit, so we need to update the code there instead of just\ninspecting the variable in git commit-graph write. (This is PATCH 2.)\n\nBy updating this variable, I saw some test failures in other tests regarding\nnon-exact pathspecs. I fixed these in PATCH 1 so we keep clean builds.\n\nI based this change on [1] but it would apply cleanly (and logically) on\ngs/commit-graph-path-filter\n\nUpdates in v2:\n\n * Added PATCH 3 to write commit-graph files during 'git merge' if\n GIT_TEST_COMMIT_GRAPH is enabled.\n \n \n * Updated PATCH 1 with the simplification recommended by Taylor.\n \n \n * Fixed the lower-case \"bloom\" in the commit message.\n \n \n\nThanks, -Stolee\n\n[1] \nhttps://lore.kernel.org/git/pull.601.v2.git.1586437211842.gitgitgadget@gmail.com/\n\nDerrick Stolee (4):\n revision: complicated pathspecs disable filters\n commit: write commit-graph with Bloom filters\n commit-graph: write commit-graph in more tests\n blame: use changed-path Bloom filters\n\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++---\n blame.h | 6 ++\n builtin/blame.c | 10 ++++\n builtin/commit.c | 4 +-\n builtin/merge.c | 7 ++-\n commit-graph.c | 9 +++\n commit-graph.h | 2 +\n revision.c | 19 ++++++-\n 8 files changed, 181 insertions(+), 15 deletions(-)\n\n\nbase-commit: f4df00a0dd448edce0e854a97f63598fefe27d27\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-609%2Fderrickstolee%2Fbloom-blame-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-609/derrickstolee/bloom-blame-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/609\n\nRange-diff vs v1:\n\n 1: 9cc31c289aa ! 1: adc03eee4ac revision: complicated pathspecs disable filters\n @@ Commit message\n path Bloom filters in the test suite. That will be fixed in the\n next change.\n \n + Helped-by: Taylor Blau \n Signed-off-by: Derrick Stolee \n \n ## revision.c ##\n +@@ revision.c: static void trace2_bloom_filter_statistics_atexit(void)\n + \tjw_release(&jw);\n + }\n + \n ++static int forbid_bloom_filters(struct pathspec *spec)\n ++{\n ++\tif (spec->has_wildcard)\n ++\t\treturn 1;\n ++\tif (spec->nr > 1)\n ++\t\treturn 1;\n ++\tif (spec->magic & ~PATHSPEC_LITERAL)\n ++\t\treturn 1;\n ++\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n ++\t\treturn 1;\n ++\n ++\treturn 0;\n ++}\n ++\n + static void prepare_to_use_bloom_filter(struct rev_info *revs)\n + {\n + \tstruct pathspec_item *pi;\n @@ revision.c: static void prepare_to_use_bloom_filter(struct rev_info *revs)\n - \tif (!revs->commits)\n - \t return;\n + \tint len;\n \n -+\tif (revs->prune_data.has_wildcard)\n -+\t\treturn;\n -+\tif (revs->prune_data.nr > 1)\n -+\t\treturn;\n -+\tif (revs->prune_data.magic ||\n -+\t (revs->prune_data.nr &&\n -+\t revs->prune_data.items[0].magic))\n + \tif (!revs->commits)\n +-\t return;\n +\t\treturn;\n +\n ++\tif (forbid_bloom_filters(&revs->prune_data))\n ++\t\treturn;\n + \n \trepo_parse_commit(revs->repo, revs->commits->item);\n \n - \tif (!revs->repo->objects->commit_graph)\n 2: bb5ce39d028 < -: ----------- commit: write commit-graph with bloom filters\n -: ----------- > 2: 7e8f1aed113 commit: write commit-graph with Bloom filters\n -: ----------- > 3: 824f8ad067b commit-graph: write commit-graph in more tests\n 3: 431fde68031 = 4: 4ae196d6355 blame: use changed-path Bloom filters\n\n-- \ngitgitgadget\n"},{"id":"395338","messageId":"adc03eee4ac8a0911bfd2a7ae03364ef0e744ef0.1586789126.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"[PATCH v2 1/4] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-13T14:45:23Z","receivedAt":"2020-04-13T14:45:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters work only when we can compute an\nexplicit Bloom filter key in advance. When a pathspec is given\nthat allows case-insensitive checks or wildcard matching, we\nmust disable the Bloom filter performance checks.\n\nBy checking the pathspec in prepare_to_use_bloom_filters(), we\navoid setting up the Bloom filter data and thus revert to the\nusual logic.\n\nBefore this change, the following tests would fail*:\n\n\tt6004-rev-list-path-optim.sh (Tests 6-7)\n\tt6130-pathspec-noglob.sh (Tests 3-6)\n\tt6131-pathspec-icase.sh (Tests 3-5)\n\n*These tests would fail when using GIT_TEST_COMMIT_GRAPH and\nGIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\nenvironment variable was not set up correctly to write the changed-\npath Bloom filters in the test suite. That will be fixed in the\nnext change.\n\nHelped-by: Taylor Blau \nSigned-off-by: Derrick Stolee \n---\n revision.c | 19 ++++++++++++++++++-\n 1 file changed, 18 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex 2b06ee739c8..f78c636e4d0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -650,6 +650,20 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \tjw_release(&jw);\n }\n \n+static int forbid_bloom_filters(struct pathspec *spec)\n+{\n+\tif (spec->has_wildcard)\n+\t\treturn 1;\n+\tif (spec->nr > 1)\n+\t\treturn 1;\n+\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\t\treturn 1;\n+\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n+\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n static void prepare_to_use_bloom_filter(struct rev_info *revs)\n {\n \tstruct pathspec_item *pi;\n@@ -659,7 +673,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n \tint len;\n \n \tif (!revs->commits)\n-\t return;\n+\t\treturn;\n+\n+\tif (forbid_bloom_filters(&revs->prune_data))\n+\t\treturn;\n \n \trepo_parse_commit(revs->repo, revs->commits->item);\n \n-- \ngitgitgadget\n\n"},{"id":"395339","messageId":"7e8f1aed1138ab2a52a8957ac95895ac9effd933.1586789126.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"[PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-13T14:45:24Z","receivedAt":"2020-04-13T14:45:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe GIT_TEST_COMMIT_GRAPH environment variable updates the commit-\ngraph file whenever \"git commit\" is run, ensuring that we always\nhave an updated commit-graph throughout the test suite. The\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variable was\nintroduced to write the changed-path Bloom filters whenever \"git\ncommit-graph write\" is run. However, the GIT_TEST_COMMIT_GRAPH\ntrick doesn't launch a separate process and instead writes it\ndirectly.\n\nUpdate the \"git commit\" builtin to write changed-path Bloom filters\nwhen both GIT_TEST_COMMIT_GRAPH and GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\nare enabled.\n\nSigned-off-by: Derrick Stolee \n---\n commit-graph.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 77668629e27..3e8f36ce5c8 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1968,6 +1968,8 @@ int write_commit_graph(struct object_directory *odb,\n \tctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;\n \tctx->split_opts = split_opts;\n \tctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;\n+\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n+\t\tctx->changed_paths = 1;\n \tctx->total_bloom_filter_data_size = 0;\n \n \tif (ctx->split) {\n-- \ngitgitgadget\n\n"},{"id":"395340","messageId":"824f8ad067bd53e0283180ab8e3828662fcd1fd4.1586789126.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"[PATCH v2 3/4] commit-graph: write commit-graph in more tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-13T14:45:25Z","receivedAt":"2020-04-13T14:45:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe GIT_TEST_COMMIT_GRAPH test environment variable triggers\ncommit-graph writes during each \"git commit\" process. To expand\nthe number of tests that have commits in the commit-graph file,\nadd a helper method that computes the commit-graph and place\nthat helper inside \"git commit\" and \"git merge\".\n\nSigned-off-by: Derrick Stolee \n---\n builtin/commit.c | 4 +---\n builtin/merge.c | 7 +++++--\n commit-graph.c | 7 +++++++\n commit-graph.h | 2 ++\n 4 files changed, 15 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/commit.c b/builtin/commit.c\nindex d3e7781e658..27d4ff6b790 100644\n--- a/builtin/commit.c\n+++ b/builtin/commit.c\n@@ -1700,9 +1700,7 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n \t\t \"new_index file. Check that disk is not full and quota is\\n\"\n \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n \n-\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n-\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n-\t\treturn 1;\n+\tgit_test_write_commit_graph_or_die();\n \n \trepo_rerere(the_repository, 0);\n \trun_command_v_opt(argv_gc_auto, RUN_GIT_CMD);\ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex d127d2225f8..db11af5b1cd 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -40,6 +40,7 @@\n #include \"branch.h\"\n #include \"commit-reach.h\"\n #include \"wt-status.h\"\n+#include \"commit-graph.h\"\n \n #define DEFAULT_TWOHEAD (1<<0)\n #define DEFAULT_OCTOPUS (1<<1)\n@@ -1673,9 +1674,11 @@ int cmd_merge(int argc, const char **argv, const char *prefix)\n \t\t\t\t head_commit);\n \t}\n \n-\tif (squash)\n+\tif (squash) {\n \t\tfinish(head_commit, remoteheads, NULL, NULL);\n-\telse\n+\n+\t\tgit_test_write_commit_graph_or_die();\n+\t} else\n \t\twrite_merge_state(remoteheads);\n \n \tif (merge_was_ok)\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 3e8f36ce5c8..5d64cb5f09c 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -19,6 +19,13 @@\n #include \"bloom.h\"\n #include \"commit-slab.h\"\n \n+void git_test_write_commit_graph_or_die(void)\n+{\n+\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n+\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n+\t\tdie(\"failed to write commit-graph under GIT_TEST_COMMIT_GRAPH\");\n+}\n+\n #define GRAPH_SIGNATURE 0x43475048 /* \"CGPH\" */\n #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* \"OIDF\" */\n #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* \"OIDL\" */\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 8655d064c14..8f852a9bee2 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -11,6 +11,8 @@\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 \n+void git_test_write_commit_graph_or_die(void);\n+\n struct commit;\n struct bloom_filter_settings;\n \n-- \ngitgitgadget\n\n"},{"id":"395341","messageId":"4ae196d6355926c56095aee30cf73665a4ea5785.1586789126.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"[PATCH v2 4/4] blame: use changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-13T14:45:26Z","receivedAt":"2020-04-13T14:45:41Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters help reduce the amount of tree\nparsing required during history queries. Before calculating a\ndiff, we can ask the filter if a path changed between a commit\nand its first parent. If the filter says \"no\" then we can move\non without parsing trees. If the filter says \"maybe\" then we\nparse trees to discover if the answer is actually \"yes\" or \"no\".\n\nWhen computing a blame, there is a section in find_origin() that\ncomputes a diff between a commit and one of its parents. When this\nis the first parent, we can check the Bloom filters before calling\ndiff_tree_oid().\n\nIn order to make this work with the blame machinery, we need to\ninitialize a struct bloom_key with the initial path. But also, we\nneed to add more keys to a list if a rename is detected. We then\ncheck to see if _any_ of these keys answer \"maybe\" in the diff.\n\nDuring development, I purposefully left out this \"add a new key\nwhen a rename is detected\" to see if the test suite would catch\nmy error. That is how I discovered the issues with\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS from the previous change.\nWith that change, we can feel some confidence in the coverage of\nthis change.\n\nIf a user requests copy detection using \"git blame -C\", then there\nare more places where the set of \"important\" files can expand. I\ndo not know enough about how this happens in the blame machinery.\nThus, the Bloom filter integration is explicitly disabled in this\nmode. A later change could expand the bloom_key data with an\nappropriate call (or calls) to add_bloom_key().\n\nIf we did not disable this mode, then the following tests would\nfail:\n\n\tt8003-blame-corner-cases.sh\n\tt8011-blame-split-file.sh\n\nGenerally, this is a performance enhancement and should not\nchange the behavior of 'git blame' in any way. If a repo has a\ncommit-graph file with computed changed-path Bloom filters, then\nthey should notice improved performance for their 'git blame'\ncommands.\n\nHere are some example timings that I found by blaming some paths\nin the Linux kernel repository:\n\n git blame arch/x86/kernel/topology.c >/dev/null\n\n Before: 0.83s\n After: 0.24s\n\n git blame kernel/time/time.c >/dev/null\n\n Before: 0.72s\n After: 0.24s\n\n git blame tools/perf/ui/stdio/hist.c >/dev/null\n\n Before: 0.27s\n After: 0.11s\n\nI specifically looked for \"deep\" paths that were also edited many\ntimes. As a counterpoint, the MAINTAINERS file was edited many\ntimes but is located in the root tree. This means that the cost of\ncomputing a diff relative to the pathspec is very small. Here are\nthe timings for that command:\n\n git blame MAINTAINERS >/dev/null\n\n Before: 20.1s\n After: 18.0s\n\nThese timings are the best of five. The worst-case runs were on the\norder of 2.5 minutes for both cases. Note that the MAINTAINERS file\nhas 18,740 lines across 17,000+ commits. This happens to be one of\nthe cases where this change provides the least improvement.\n\nThe lack of improvement for the MAINTAINERS file and the relatively\nmodest improvement for the other examples can be easily explained.\nThe blame machinery needs to compute line-level diffs to determine\nwhich lines were changed by each commit. That makes up a large\nproportion of the computation time, and this change does not\nattempt to improve on that section of the algorithm. The\nMAINTAINERS file is large and changed often, so it takes time to\ndetermine which lines were updated by which commit. In contrast,\nthe code files are much smaller, and it takes longer to comute\nthe line-by-line diff for a single patch on the Linux mailing\nlists.\n\nOutside of the \"-C\" integration, I believe there is little more to\ngain from the changed-path Bloom filters for 'git blame' after this\npatch.\n\nSigned-off-by: Derrick Stolee \n---\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++----\n blame.h | 6 +++\n builtin/blame.c | 10 ++++\n 3 files changed, 146 insertions(+), 9 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 29770e5c81c..9fbf79e47c3 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -9,6 +9,8 @@\n #include \"blame.h\"\n #include \"alloc.h\"\n #include \"commit-slab.h\"\n+#include \"bloom.h\"\n+#include \"commit-graph.h\"\n \n define_commit_slab(blame_suspects, struct blame_origin *);\n static struct blame_suspects blame_suspects;\n@@ -1246,13 +1248,75 @@ static int fill_blob_sha1_and_mode(struct repository *r,\n \treturn -1;\n }\n \n+struct blame_bloom_data {\n+\t/*\n+\t * Changed-path Bloom filter keys. These can help prevent\n+\t * computing diffs against first parents, but we need to\n+\t * expand the list as code is moved or files are renamed.\n+\t */\n+\tstruct bloom_filter_settings *settings;\n+\tstruct bloom_key **keys;\n+\tint nr;\n+\tint alloc;\n+};\n+\n+static int bloom_count_queries = 0;\n+static int bloom_count_no = 0;\n+static int maybe_changed_path(struct repository *r,\n+\t\t\t struct commit *parent,\n+\t\t\t struct blame_origin *origin,\n+\t\t\t struct blame_bloom_data *bd)\n+{\n+\tint i;\n+\tstruct bloom_filter *filter;\n+\n+\tif (!bd)\n+\t\treturn 1;\n+\n+\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\t\treturn 1;\n+\n+\tfilter = get_bloom_filter(r, origin->commit, 0);\n+\n+\tif (!filter)\n+\t\treturn 1;\n+\n+\tbloom_count_queries++;\n+\tfor (i = 0; i < bd->nr; i++) {\n+\t\tif (bloom_filter_contains(filter,\n+\t\t\t\t\t bd->keys[i],\n+\t\t\t\t\t bd->settings))\n+\t\t\treturn 1;\n+\t}\n+\n+\tbloom_count_no++;\n+\treturn 0;\n+}\n+\n+static void add_bloom_key(struct blame_bloom_data *bd,\n+\t\t\t const char *path)\n+{\n+\tif (!bd)\n+\t\treturn;\n+\n+\tif (bd->nr >= bd->alloc) {\n+\t\tbd->alloc *= 2;\n+\t\tREALLOC_ARRAY(bd->keys, bd->alloc);\n+\t}\n+\n+\tbd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));\n+\tfill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);\n+\tbd->nr++;\n+}\n+\n /*\n * We have an origin -- check if the same path exists in the\n * parent and return an origin structure to represent it.\n */\n static struct blame_origin *find_origin(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin;\n \tstruct diff_options diff_opts;\n@@ -1286,10 +1350,19 @@ static struct blame_origin *find_origin(struct repository *r,\n \n \tif (is_null_oid(&origin->commit->object.oid))\n \t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n-\telse\n-\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n-\t\t\t get_commit_tree_oid(origin->commit),\n-\t\t\t \"\", &diff_opts);\n+\telse {\n+\t\tint compute_diff = 1;\n+\t\tif (origin->commit->parents &&\n+\t\t !oidcmp(&parent->object.oid,\n+\t\t\t &origin->commit->parents->item->object.oid))\n+\t\t\tcompute_diff = maybe_changed_path(r, parent,\n+\t\t\t\t\t\t\t origin, bd);\n+\n+\t\tif (compute_diff)\n+\t\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t\t get_commit_tree_oid(origin->commit),\n+\t\t\t\t \"\", &diff_opts);\n+\t}\n \tdiffcore_std(&diff_opts);\n \n \tif (!diff_queued_diff.nr) {\n@@ -1341,7 +1414,8 @@ static struct blame_origin *find_origin(struct repository *r,\n */\n static struct blame_origin *find_rename(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin = NULL;\n \tstruct diff_options diff_opts;\n@@ -1366,6 +1440,7 @@ static struct blame_origin *find_rename(struct repository *r,\n \t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n \t\tif ((p->status == 'R' || p->status == 'C') &&\n \t\t !strcmp(p->two->path, origin->path)) {\n+\t\t\tadd_bloom_key(bd, p->one->path);\n \t\t\tporigin = get_origin(parent, p->one->path);\n \t\t\toidcpy(&porigin->blob_oid, &p->one->oid);\n \t\t\tporigin->mode = p->one->mode;\n@@ -2332,6 +2407,11 @@ static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *bl\n \n #define MAXSG 16\n \n+typedef struct blame_origin *(*blame_find_alg)(struct repository *,\n+\t\t\t\t\t struct commit *,\n+\t\t\t\t\t struct blame_origin *,\n+\t\t\t\t\t struct blame_bloom_data *);\n+\n static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, int opt)\n {\n \tstruct rev_info *revs = sb->revs;\n@@ -2356,8 +2436,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t * common cases, then we look for renames in the second pass.\n \t */\n \tfor (pass = 0; pass < 2 - sb->no_whole_file_rename; pass++) {\n-\t\tstruct blame_origin *(*find)(struct repository *, struct commit *, struct blame_origin *);\n-\t\tfind = pass ? find_rename : find_origin;\n+\t\tblame_find_alg find = pass ? find_rename : find_origin;\n \n \t\tfor (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);\n \t\t i < num_sg && sg;\n@@ -2369,7 +2448,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t\t\t\tcontinue;\n \t\t\tif (parse_commit(p))\n \t\t\t\tcontinue;\n-\t\t\tporigin = find(sb->repo, p, origin);\n+\t\t\tporigin = find(sb->repo, p, origin, sb->bloom_data);\n \t\t\tif (!porigin)\n \t\t\t\tcontinue;\n \t\t\tif (oideq(&porigin->blob_oid, &origin->blob_oid)) {\n@@ -2809,3 +2888,45 @@ struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \tblame_origin_incref(o);\n \treturn new_head;\n }\n+\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path)\n+{\n+\tstruct blame_bloom_data *bd;\n+\n+\tif (!sb->repo->objects->commit_graph)\n+\t\treturn;\n+\n+\tif (!sb->repo->objects->commit_graph->bloom_filter_settings)\n+\t\treturn;\n+\n+\tbd = xmalloc(sizeof(struct blame_bloom_data));\n+\n+\tbd->settings = sb->repo->objects->commit_graph->bloom_filter_settings;\n+\n+\tbd->alloc = 4;\n+\tbd->nr = 0;\n+\tALLOC_ARRAY(bd->keys, bd->alloc);\n+\n+\tadd_bloom_key(bd, path);\n+\n+\tsb->bloom_data = bd;\n+}\n+\n+void cleanup_scoreboard(struct blame_scoreboard *sb)\n+{\n+\tif (sb->bloom_data) {\n+\t\tint i;\n+\t\tfor (i = 0; i < sb->bloom_data->nr; i++) {\n+\t\t\tfree(sb->bloom_data->keys[i]->hashes);\n+\t\t\tfree(sb->bloom_data->keys[i]);\n+\t\t}\n+\t\tfree(sb->bloom_data->keys);\n+\t\tFREE_AND_NULL(sb->bloom_data);\n+\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/queries\", bloom_count_queries);\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/response-no\", bloom_count_no);\n+\t}\n+}\ndiff --git a/blame.h b/blame.h\nindex 089b181ff27..b6bbee41472 100644\n--- a/blame.h\n+++ b/blame.h\n@@ -100,6 +100,8 @@ struct blame_entry {\n \tint unblamable;\n };\n \n+struct blame_bloom_data;\n+\n /*\n * The current state of the blame assignment.\n */\n@@ -156,6 +158,7 @@ struct blame_scoreboard {\n \tvoid(*found_guilty_entry)(struct blame_entry *, void *);\n \n \tvoid *found_guilty_entry_data;\n+\tstruct blame_bloom_data *bloom_data;\n };\n \n /*\n@@ -180,6 +183,9 @@ void init_scoreboard(struct blame_scoreboard *sb);\n void setup_scoreboard(struct blame_scoreboard *sb,\n \t\t const char *path,\n \t\t struct blame_origin **orig);\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path);\n+void cleanup_scoreboard(struct blame_scoreboard *sb);\n \n struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \t\t\t\t\tlong start, long end,\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex bf1cecdf3f9..3c13634f279 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1061,6 +1061,14 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \tstring_list_clear(&ignore_revs_file_list, 0);\n \tstring_list_clear(&ignore_rev_list, 0);\n \tsetup_scoreboard(&sb, path, &o);\n+\n+\t/*\n+\t * Changed-path Bloom filters are disabled when looking\n+\t * for copies.\n+\t */\n+\tif (!(opt & PICKAXE_BLAME_COPY))\n+\t\tsetup_blame_bloom_data(&sb, path);\n+\n \tlno = sb.num_lines;\n \n \tif (lno && !range_list.nr)\n@@ -1164,5 +1172,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \t\tprintf(\"num get patch: %d\\n\", sb.num_get_patch);\n \t\tprintf(\"num commits: %d\\n\", sb.num_commits);\n \t}\n+\n+\tcleanup_scoreboard(&sb);\n \treturn 0;\n }\n-- \ngitgitgadget\n"},{"id":"395350","messageId":"20200413160908.GD59601@syl.local","threadId":"53210","inReplyTo":"adc03eee4ac8a0911bfd2a7ae03364ef0e744ef0.1586789126.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/4] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-13T16:09:08Z","receivedAt":"2020-04-13T16:09:14Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Apr 13, 2020 at 02:45:23PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> The changed-path Bloom filters work only when we can compute an\n> explicit Bloom filter key in advance. When a pathspec is given\n> that allows case-insensitive checks or wildcard matching, we\n> must disable the Bloom filter performance checks.\n>\n> By checking the pathspec in prepare_to_use_bloom_filters(), we\n> avoid setting up the Bloom filter data and thus revert to the\n> usual logic.\n>\n> Before this change, the following tests would fail*:\n>\n> \tt6004-rev-list-path-optim.sh (Tests 6-7)\n> \tt6130-pathspec-noglob.sh (Tests 3-6)\n> \tt6131-pathspec-icase.sh (Tests 3-5)\n>\n> *These tests would fail when using GIT_TEST_COMMIT_GRAPH and\n> GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\n> environment variable was not set up correctly to write the changed-\n> path Bloom filters in the test suite. That will be fixed in the\n> next change.\n>\n> Helped-by: Taylor Blau \n> Signed-off-by: Derrick Stolee \n> ---\n> revision.c | 19 ++++++++++++++++++-\n> 1 file changed, 18 insertions(+), 1 deletion(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 2b06ee739c8..f78c636e4d0 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -650,6 +650,20 @@ static void trace2_bloom_filter_statistics_atexit(void)\n> \tjw_release(&jw);\n> }\n>\n> +static int forbid_bloom_filters(struct pathspec *spec)\n> +{\n> +\tif (spec->has_wildcard)\n> +\t\treturn 1;\n> +\tif (spec->nr > 1)\n> +\t\treturn 1;\n> +\tif (spec->magic & ~PATHSPEC_LITERAL)\n> +\t\treturn 1;\n> +\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n> +\t\treturn 1;\n> +\n> +\treturn 0;\n> +}\n> +\n> static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> {\n> \tstruct pathspec_item *pi;\n> @@ -659,7 +673,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> \tint len;\n>\n> \tif (!revs->commits)\n> -\t return;\n> +\t\treturn;\n> +\n> +\tif (forbid_bloom_filters(&revs->prune_data))\n> +\t\treturn;\n>\n> \trepo_parse_commit(revs->repo, revs->commits->item);\n>\n> --\n> gitgitgadget\n>\n\nNicely done, this looks good to me. Thanks.\n\nThanks,\nTaylor\n"},{"id":"395351","messageId":"20200413161245.GE59601@syl.local","threadId":"53210","inReplyTo":"7e8f1aed1138ab2a52a8957ac95895ac9effd933.1586789126.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-13T16:12:45Z","receivedAt":"2020-04-13T16:12:49Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Apr 13, 2020 at 02:45:24PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> The GIT_TEST_COMMIT_GRAPH environment variable updates the commit-\n> graph file whenever \"git commit\" is run, ensuring that we always\n> have an updated commit-graph throughout the test suite. The\n> GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variable was\n> introduced to write the changed-path Bloom filters whenever \"git\n> commit-graph write\" is run. However, the GIT_TEST_COMMIT_GRAPH\n> trick doesn't launch a separate process and instead writes it\n> directly.\n>\n> Update the \"git commit\" builtin to write changed-path Bloom filters\n> when both GIT_TEST_COMMIT_GRAPH and GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\n> are enabled.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> commit-graph.c | 2 ++\n> 1 file changed, 2 insertions(+)\n>\n> diff --git a/commit-graph.c b/commit-graph.c\n> index 77668629e27..3e8f36ce5c8 100644\n> --- a/commit-graph.c\n> +++ b/commit-graph.c\n> @@ -1968,6 +1968,8 @@ int write_commit_graph(struct object_directory *odb,\n> \tctx->check_oids = flags & COMMIT_GRAPH_WRITE_CHECK_OIDS ? 1 : 0;\n> \tctx->split_opts = split_opts;\n> \tctx->changed_paths = flags & COMMIT_GRAPH_WRITE_BLOOM_FILTERS ? 1 : 0;\n> +\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n> +\t\tctx->changed_paths = 1;\n\nHmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\nenvironment variables and potentially ignoring its arguments, but given\nthe discussion we had in v1, I don't feel strongly enough to recommend\nthat you change this.\n\nFor what it's worth, I think that 'write_commit_graph' could behave more\npurely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n'flags' appropriately from the outside, but I can understand also why\nit's preferred to do it in this style, too.\n\n> \tctx->total_bloom_filter_data_size = 0;\n>\n> \tif (ctx->split) {\n> --\n> gitgitgadget\n>\n\nThanks,\nTaylor\n"},{"id":"395352","messageId":"20200413162141.GF59601@syl.local","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 0/4] Integrate changed-path Bloom filters with 'git blame'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-13T16:21:41Z","receivedAt":"2020-04-13T16:21:45Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Mon, Apr 13, 2020 at 02:45:22PM +0000, Derrick Stolee via GitGitGadget wrote:\n> Updates in v2:\n>\n> * Added PATCH 3 to write commit-graph files during 'git merge' if\n> GIT_TEST_COMMIT_GRAPH is enabled.\n>\n>\n> * Updated PATCH 1 with the simplification recommended by Taylor.\n>\n>\n> * Fixed the lower-case \"bloom\" in the commit message.\n\nThis updated version looks great to me. Thanks for looking at all of my\nsuggestions :-).\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"395376","messageId":"xmqqtv1navdd.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"8ef47003-784d-6a27-666d-5c916c4deb33@gmail.com","subject":"Re: [PATCH 2/3] commit: write commit-graph with bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-13T22:11:58Z","receivedAt":"2020-04-13T22:12:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> If we keep this simple, or extract the process to a\n> \"write_commit_graph_for_tests()\" macro inside builtin.h, then we could\n> insert a commit-graph write in more places.\n\nAs long as the check necessary is cheap enough to realize that we\nare in production mode, we should be able to keep the run-time\noverhead to the minimum. Sprinkling such a call all over the place,\nhowever, might add to the overhead of reading code, though.\n\n> However, I think there is value in testing the \"not every commit is\n> included in the commit-graph\" case, which our current setup does quite\n> nicely.\n\nYeah, that is also a good point.\n\n> The one exception is that 'git merge' could benefit from this\n> snippet, so we cap off the commit-graph whenever a test script\n> \"constructs\" a repository to match a data shape.\n\nSounds good.\n\n> The problem here is that if GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1 and\n> someone runs \"git commit-graph write --no-changed-paths\" then the\n> negation of that option is ignored. But this is a GIT_TEST_* variable,\n> and any test that requires that check could disable the enviroment\n> variable first.\n\nYeah, that sounds good.\n"},{"id":"395378","messageId":"xmqqlfmzav2w.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"20200413160908.GD59601@syl.local","subject":"Re: [PATCH v2 1/4] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-13T22:18:15Z","receivedAt":"2020-04-13T22:18:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n>> +static int forbid_bloom_filters(struct pathspec *spec)\n>> +{\n>> +\tif (spec->has_wildcard)\n>> +\t\treturn 1;\n>> +\tif (spec->nr > 1)\n>> +\t\treturn 1;\n>> +\tif (spec->magic & ~PATHSPEC_LITERAL)\n>> +\t\treturn 1;\n>> +\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n>> +\t\treturn 1;\n>> +\n>> +\treturn 0;\n>> +}\n>> +\n>> static void prepare_to_use_bloom_filter(struct rev_info *revs)\n>> {\n>> \tstruct pathspec_item *pi;\n>> @@ -659,7 +673,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n>> \tint len;\n>>\n>> \tif (!revs->commits)\n>> -\t return;\n>> +\t\treturn;\n>> +\n>> +\tif (forbid_bloom_filters(&revs->prune_data))\n>> +\t\treturn;\n>>\n>> \trepo_parse_commit(revs->repo, revs->commits->item);\n>>\n>> --\n>> gitgitgadget\n>>\n>\n> Nicely done, this looks good to me. Thanks.\n\nLikewise. Very exciting.\n\nWill queue.\n"},{"id":"395379","messageId":"xmqqh7xnauxc.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"20200413161245.GE59601@syl.local","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-13T22:21:35Z","receivedAt":"2020-04-13T22:21:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n> Hmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\n> environment variables and potentially ignoring its arguments, but given\n> the discussion we had in v1, I don't feel strongly enough to recommend\n> that you change this.\n>\n> For what it's worth, I think that 'write_commit_graph' could behave more\n> purely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n> 'flags' appropriately from the outside,...\n\nYeah, I agree that it would be a lot cleaner if that is easy to\narrange. I have a suspicion that Derrick already tried and the\nresulting code looked messier and was discarded?\n"},{"id":"395413","messageId":"74e4e8d6-d401-081d-14cc-c4b6087bdeda@gmail.com","threadId":"53210","inReplyTo":"xmqqh7xnauxc.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-14T15:04:05Z","receivedAt":"2020-04-14T15:05:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/13/2020 6:21 PM, Junio C Hamano wrote:\n> Taylor Blau writes:\n> \n>> Hmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\n>> environment variables and potentially ignoring its arguments, but given\n>> the discussion we had in v1, I don't feel strongly enough to recommend\n>> that you change this.\n>>\n>> For what it's worth, I think that 'write_commit_graph' could behave more\n>> purely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n>> 'flags' appropriately from the outside,...\n> \n> Yeah, I agree that it would be a lot cleaner if that is easy to\n> arrange. I have a suspicion that Derrick already tried and the\n> resulting code looked messier and was discarded?\n\nPerhaps I could fix both concerns by\n\n1. Use a macro instead of a library call.\n\n2. Check the _CHANGED_PATHS variable in the macro.\n\nThe macro would look like this:\n\n\n#define git_test_write_commit_graph_or_die() \\\n\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0)) { \\\n\t\tint flags = 0; \\\n\t\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0)) \\\n\t\t\tflags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS; \\\n\t\tif (write_commit_graph_reachable( \\\n\t\t\tthe_repository->objects->odb, flags, NULL)) \\\n\t\t\tdie(\"failed to write commit-graph under GIT_TEST_COMMIT_GRAPH\"); \\\n\t}\n\nThanks,\n-Stolee\n"},{"id":"395425","messageId":"xmqqa73e9dws.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"74e4e8d6-d401-081d-14cc-c4b6087bdeda@gmail.com","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-14T17:26:43Z","receivedAt":"2020-04-14T17:26:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> On 4/13/2020 6:21 PM, Junio C Hamano wrote:\n>> Taylor Blau writes:\n>> \n>>> Hmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\n>>> environment variables and potentially ignoring its arguments, but given\n>>> the discussion we had in v1, I don't feel strongly enough to recommend\n>>> that you change this.\n>>>\n>>> For what it's worth, I think that 'write_commit_graph' could behave more\n>>> purely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n>>> 'flags' appropriately from the outside,...\n>> \n>> Yeah, I agree that it would be a lot cleaner if that is easy to\n>> arrange. I have a suspicion that Derrick already tried and the\n>> resulting code looked messier and was discarded?\n>\n> Perhaps I could fix both concerns by\n>\n> 1. Use a macro instead of a library call.\n>\n> 2. Check the _CHANGED_PATHS variable in the macro.\n\nI am not sure how use of a macro \"fixes\" purity, though. And what\nis the other concern?\n\nHow widely would this \"if we are testing, write out the graph file\"\ncall be sprinkled over the codebase? I am hoping that it won't be\n\"everywhere\", but only at strategic places (like \"just once before\nwe leave a subcommand that creates one or bunch of commits\"). And\nhow often would they be called? I am also hoping that it won't be\n\"inside a tight loop\". In short, I am wondering if we can promise\nour codebase that \n\n - git_test_write_commit_graph_or_die() calls won't be an eyesore\n (and/or distraction) for developers too much.\n\n - git_env_bool() call won't have performance impact.\n\n\n> The macro would look like this:\n>\n>\n> #define git_test_write_commit_graph_or_die() \\\n> \tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0)) { \\\n> \t\tint flags = 0; \\\n> \t\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0)) \\\n> \t\t\tflags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS; \\\n> \t\tif (write_commit_graph_reachable( \\\n> \t\t\tthe_repository->objects->odb, flags, NULL)) \\\n> \t\t\tdie(\"failed to write commit-graph under GIT_TEST_COMMIT_GRAPH\"); \\\n> \t}\n>\n> Thanks,\n> -Stolee\n"},{"id":"395426","messageId":"36f321b9-e2ff-60c3-637a-38682ee5d9f0@gmail.com","threadId":"53210","inReplyTo":"xmqqa73e9dws.fsf@gitster.c.googlers.com","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-14T17:40:53Z","receivedAt":"2020-04-14T17:41:01Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/14/2020 1:26 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n>> On 4/13/2020 6:21 PM, Junio C Hamano wrote:\n>>> Taylor Blau writes:\n>>>\n>>>> Hmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\n>>>> environment variables and potentially ignoring its arguments, but given\n>>>> the discussion we had in v1, I don't feel strongly enough to recommend\n>>>> that you change this.\n>>>>\n>>>> For what it's worth, I think that 'write_commit_graph' could behave more\n>>>> purely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n>>>> 'flags' appropriately from the outside,...\n>>>\n>>> Yeah, I agree that it would be a lot cleaner if that is easy to\n>>> arrange. I have a suspicion that Derrick already tried and the\n>>> resulting code looked messier and was discarded?\n>>\n>> Perhaps I could fix both concerns by\n>>\n>> 1. Use a macro instead of a library call.\n>>\n>> 2. Check the _CHANGED_PATHS variable in the macro.\n> \n> I am not sure how use of a macro \"fixes\" purity, though. And what\n> is the other concern?\n\nThe concern was (1) checking the environment and (2) die()ing in the\nlibrary.\n\n> How widely would this \"if we are testing, write out the graph file\"\n> call be sprinkled over the codebase? I am hoping that it won't be\n> \"everywhere\", but only at strategic places (like \"just once before\n> we leave a subcommand that creates one or bunch of commits\"). And\n> how often would they be called? I am also hoping that it won't be\n> \"inside a tight loop\". In short, I am wondering if we can promise\n> our codebase that \n> \n> - git_test_write_commit_graph_or_die() calls won't be an eyesore\n> (and/or distraction) for developers too much.\n> \n> - git_env_bool() call won't have performance impact.\n\nI could add a comment to the header file to say \"this is only for\nimproving coverage of optional features in the test suite. Do not\ncall this method unless you know what you are doing.\"\n\nMy intention right now is to only include this in 'git commit'\nand 'git merge'. Earlier discussion included thoughts about\n'git rebase' and similar, but those are more rarely used when\nconstructing an \"example repo\" in the test scripts.\n\n-Stolee\n"},{"id":"395431","messageId":"xmqqmu7d9b6j.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"44ce43e2-6cf0-0e48-18eb-f02543d81bf4@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-14T18:25:40Z","receivedAt":"2020-04-14T18:25:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> But if users may use icase pathspec very often, it may be worth\n>> considering to build the bloom filter after downcasing the paths,\n>> perhaps? Given that many projects extract their source code to a\n>> case insensitive filesystem, I would imagine that downcasing paths\n>> would map two originally different paths into the same thing only\n>> rarely, if ever, so there may not be much downside to do so.\n>\n> This behavior could be extended later, and carefully. My initial\n> thought was that the case check would happen on every commit. If\n> the :(icase) check only happens at the walk tip(s), then we could\n> compute a single Bloom key at the start.\n\nSorry, I am not sure what you mean.\n\nDo you mean that we notice that the user wants to match 'foo' case\ninsensitively, and tell the logic that uses changed-path records in\nthe graph file that commits that cannot possibly have touched any or\nthe paths 'foo', 'foO', 'fOo', ... (all 8 case permutations) are not\ninteresting?\n\nI guess that would work, but I was wondering if it is simpler\nwithout much downside if the changed-path records in the graph file\nare prepared on paths after they are normalized to a single case.\nThat would lose information (e.g. you no longer can say \"commits\nthat touch the path 'foo' is interesting, but those that touch the\npath 'Foo' are not\"), but makes the side that queries much simpler\n(i.e. you do not have to prepare all 8 case permutations---you only\nask about 'foo').\n\nAnd because the Bloom filter is used only for performance to cull\ncommits that can never possibly match, allowing a false positive\nthat would be discarded by actually running tree-diff anyway, the\nonly potential downside happens when the project has too many paths\nthat are different only in cases by increased collisions and by\nreducing our chances to skip running tree-diff (and never affects\ncorrectness). \n\nBut this is not the \"could be extended later\" kind of behaviour, I\nam afraid. It is baked in the data stored in the graph file.\n\nIt all depends on how often people want :(icase) pathspec matches in\nthe history, I suspect. My point was that we need to declare that\n:(icase) won't matter in real life (hence we won't optimize our data\nto support that use case), before the way in which the data stored\nin the graph file is computed is cast in stone.\n\nThanks.\n"},{"id":"395459","messageId":"20200415001713.GB7457@syl.local","threadId":"53210","inReplyTo":"36f321b9-e2ff-60c3-637a-38682ee5d9f0@gmail.com","subject":"Re: [PATCH v2 2/4] commit: write commit-graph with Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-15T00:17:13Z","receivedAt":"2020-04-15T00:17:23Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Apr 14, 2020 at 01:40:53PM -0400, Derrick Stolee wrote:\n> On 4/14/2020 1:26 PM, Junio C Hamano wrote:\n> > Derrick Stolee writes:\n> >\n> >> On 4/13/2020 6:21 PM, Junio C Hamano wrote:\n> >>> Taylor Blau writes:\n> >>>\n> >>>> Hmm. I'm not crazy about a library function looking at 'GIT_TEST_*'\n> >>>> environment variables and potentially ignoring its arguments, but given\n> >>>> the discussion we had in v1, I don't feel strongly enough to recommend\n> >>>> that you change this.\n> >>>>\n> >>>> For what it's worth, I think that 'write_commit_graph' could behave more\n> >>>> purely if callers checked 'GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS' and set\n> >>>> 'flags' appropriately from the outside,...\n> >>>\n> >>> Yeah, I agree that it would be a lot cleaner if that is easy to\n> >>> arrange. I have a suspicion that Derrick already tried and the\n> >>> resulting code looked messier and was discarded?\n> >>\n> >> Perhaps I could fix both concerns by\n> >>\n> >> 1. Use a macro instead of a library call.\n> >>\n> >> 2. Check the _CHANGED_PATHS variable in the macro.\n> >\n> > I am not sure how use of a macro \"fixes\" purity, though. And what\n> > is the other concern?\n>\n> The concern was (1) checking the environment and (2) die()ing in the\n> library.\n\nI think that we might as well use a plain old function here instead of a\nmacro, especially since the macro is just expanding out to what that\nfunction would be if we had written it that way.\n\nFor what it's worth, my concern was more that I don't mind dying, but\nI'd rather do so in a calling function, and that by the time we're\ncalling 'write_commit_graph', that we should be using return values\ninstead of 'die()' or 'error()'.\n\n> > How widely would this \"if we are testing, write out the graph file\"\n> > call be sprinkled over the codebase? I am hoping that it won't be\n> > \"everywhere\", but only at strategic places (like \"just once before\n> > we leave a subcommand that creates one or bunch of commits\"). And\n> > how often would they be called? I am also hoping that it won't be\n> > \"inside a tight loop\". In short, I am wondering if we can promise\n> > our codebase that\n> >\n> > - git_test_write_commit_graph_or_die() calls won't be an eyesore\n> > (and/or distraction) for developers too much.\n> >\n> > - git_env_bool() call won't have performance impact.\n>\n> I could add a comment to the header file to say \"this is only for\n> improving coverage of optional features in the test suite. Do not\n> call this method unless you know what you are doing.\"\n\nWorks for me.\n\n> My intention right now is to only include this in 'git commit'\n> and 'git merge'. Earlier discussion included thoughts about\n> 'git rebase' and similar, but those are more rarely used when\n> constructing an \"example repo\" in the test scripts.\n\nDitto. I think that there's benefit in having it in some places but not\nall (as Stolee pointed out earlier in the thread), and that trying to\nhave it everywhere is a fool's errand.\n\n> -Stolee\n\nThanks,\nTaylor\n"},{"id":"395491","messageId":"f57c7908-55ae-deae-e9ea-1909549e628c@gmail.com","threadId":"53210","inReplyTo":"xmqqmu7d9b6j.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-15T13:27:45Z","receivedAt":"2020-04-15T13:27:58Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/14/2020 2:25 PM, Junio C Hamano wrote:\n> Derrick Stolee writes:\n> \n>>> But if users may use icase pathspec very often, it may be worth\n>>> considering to build the bloom filter after downcasing the paths,\n>>> perhaps? Given that many projects extract their source code to a\n>>> case insensitive filesystem, I would imagine that downcasing paths\n>>> would map two originally different paths into the same thing only\n>>> rarely, if ever, so there may not be much downside to do so.\n>>\n>> This behavior could be extended later, and carefully. My initial\n>> thought was that the case check would happen on every commit. If\n>> the :(icase) check only happens at the walk tip(s), then we could\n>> compute a single Bloom key at the start.\n> \n> Sorry, I am not sure what you mean.\n\nThat's my fault. There are a couple of things I misunderstood here.\n\n1. Thinking about \"git blame\" we would need to \"collapse\" a pathspec\n to a specific file before starting history. But blame doesn't\n allow \":(icase)\" anyway.\n\n2. With that context of \"git blame\" in my head, I was thinking\n (incorrectly) that \"git log\" would collapse the pathspec based on\n what file(s) match the pattern at HEAD. The tests in\n t6131-pathspec-icase.sh clearly show that this is wrong. In fact,\n if we apply the following diff to this patch, then we can get failures\n with the changed-path filters:\n\ndiff --git a/revision.c b/revision.c\nindex f78c636e4d..a02be25feb 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -652,13 +652,14 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n+ int allowed_flags = PATHSPEC_LITERAL | PATHSPEC_ICASE;\n if (spec->has_wildcard)\n return 1;\n if (spec->nr > 1)\n return 1;\n- if (spec->magic & ~PATHSPEC_LITERAL)\n+ if (spec->magic & ~allowed_flags)\n return 1;\n- if (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n+ if (spec->nr && (spec->items[0].magic & ~allowed_flags))\n return 1;\n \n return 0;\n\n> Do you mean that we notice that the user wants to match 'foo' case\n> insensitively, and tell the logic that uses changed-path records in\n> the graph file that commits that cannot possibly have touched any or\n> the paths 'foo', 'foO', 'fOo', ... (all 8 case permutations) are not\n> interesting?\n> \n> I guess that would work, but I was wondering if it is simpler\n> without much downside if the changed-path records in the graph file\n> are prepared on paths after they are normalized to a single case.\n> That would lose information (e.g. you no longer can say \"commits\n> that touch the path 'foo' is interesting, but those that touch the\n> path 'Foo' are not\"), but makes the side that queries much simpler\n> (i.e. you do not have to prepare all 8 case permutations---you only\n> ask about 'foo').\n> \n> And because the Bloom filter is used only for performance to cull\n> commits that can never possibly match, allowing a false positive\n> that would be discarded by actually running tree-diff anyway, the\n> only potential downside happens when the project has too many paths\n> that are different only in cases by increased collisions and by\n> reducing our chances to skip running tree-diff (and never affects\n> correctness). \n> \n> But this is not the \"could be extended later\" kind of behaviour, I\n> am afraid. It is baked in the data stored in the graph file.\n\nSince the feature is not released, we still have time to update the\nformat if we so desired. With the current format, we would need to\ndisable the filters when using an :(icase) pathspec as the current\npatch does.\n\nI'm not against the idea. Logically, collapsing case before hashing\nthe Bloom keys should not increase the probabilities of false\npositives except in the situations where we have case conflicts.\nThere is a small cost in the pre-hashing step to change the case of\nthe paths, but that should be much lower than the cost of the hash\nitself and the tree parsing to find the changed paths.\n\n> It all depends on how often people want :(icase) pathspec matches in\n> the history, I suspect. My point was that we need to declare that\n> :(icase) won't matter in real life (hence we won't optimize our data\n> to support that use case), before the way in which the data stored\n> in the graph file is computed is cast in stone.\n\nMy earlier statement can be summarized as \"we could make this happen\"\nand you ask here \"is it worth doing?\"\n\nI will play around with how complicated the change would be while\nthe community considers the \"is it worth doing?\" question.\n\nThanks,\n-Stolee\n"},{"id":"395525","messageId":"99e0ae2c-6b65-24e4-3d2b-1dff619a5daa@gmail.com","threadId":"53210","inReplyTo":"f57c7908-55ae-deae-e9ea-1909549e628c@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-15T18:37:40Z","receivedAt":"2020-04-15T19:17:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/15/2020 9:27 AM, Derrick Stolee wrote:\n>\n> I'm not against the idea. Logically, collapsing case before hashing\n> the Bloom keys should not increase the probabilities of false\n> positives except in the situations where we have case conflicts.\n> There is a small cost in the pre-hashing step to change the case of\n> the paths, but that should be much lower than the cost of the hash\n> itself and the tree parsing to find the changed paths.\n> \n>> It all depends on how often people want :(icase) pathspec matches in\n>> the history, I suspect. My point was that we need to declare that\n>> :(icase) won't matter in real life (hence we won't optimize our data\n>> to support that use case), before the way in which the data stored\n>> in the graph file is computed is cast in stone.\n> \n> My earlier statement can be summarized as \"we could make this happen\"\n> and you ask here \"is it worth doing?\"\n> \n> I will play around with how complicated the change would be while\n> the community considers the \"is it worth doing?\" question.\n\nI played a bit, and it wasn't terrible to cover everything by\nadjusting fill_bloom_key(). I also added a test that we will want\nanyways.\n\nThere is more work to be done if this is the direction we want to\ngo, including double-checking that this doesn't cause significant\nperformance degradation.\n\nThe point of me sending this patch is to make the proposed\ndirection very clear how it would work. I'm still not sure how I\nfeel about it.\n\nThanks,\n-Stolee\n\n-->8--\nFrom 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001\nFrom: Derrick Stolee \nDate: Wed, 15 Apr 2020 18:04:25 +0000\nSubject: [PATCH] bloom: compute all Bloom hashes from lowercase\n\nThe changed-path Bloom filters currently hash path strings using\nthe exact string for the path. This makes it difficult* to use the\nfilters when restricting to case-insensitive pathspecs.\n\n* I say \"difficult\" because it is possible to generate all 2^n\n options for the case of a path and test them all, but this is\n a bad idea and should not be done. \"Impossible\" is an appropriate\n alternative.\n\nTHIS IS A BREAKING CHANGE. Commit-graph files with changed-path\nBloom filters computed by a previous commit will not be compatible\nwith the filters computed in this commit, nor will we get correct\nresults when testing across these incompatible versions. Normally,\nthis would be a completely unacceptable change, but the filters\nhave not been released and hence are still possible to update\nbefore release.\n\nTODO: If we decide to move in this direction, then the following\nsteps should be done (and some of them should be done anyway):\n\n* We need to document the Bloom filter format to specify exactly\n how we compute the filter data. The details should be careful\n enough that someone can reproduce the exact file format without\n looking at the C code.\n\n* That document would include the tolower() transformation that is\n being done here.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 16 ++++++++++++++--\n revision.c | 5 +++--\n t/t6131-pathspec-icase.sh | 18 ++++++++++++++++++\n 3 files changed, 35 insertions(+), 4 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex dd9bab9bbd..c919c60f12 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -130,8 +130,20 @@ void fill_bloom_key(const char *data,\n \tint i;\n \tconst uint32_t seed0 = 0x293ae76f;\n \tconst uint32_t seed1 = 0x7e646e2c;\n-\tconst uint32_t hash0 = murmur3_seeded(seed0, data, len);\n-\tconst uint32_t hash1 = murmur3_seeded(seed1, data, len);\n+\tuint32_t hash0, hash1;\n+\tstatic struct strbuf icase_data = STRBUF_INIT;\n+\tchar *cur;\n+\n+\tstrbuf_setlen(&icase_data, 0);\n+\tstrbuf_addstr(&icase_data, data);\n+\n+\tfor (cur = icase_data.buf; cur && *cur; cur++) {\n+\t\tif (isupper(*cur))\n+\t\t\t*cur = tolower(*cur);\n+\t}\n+\n+\thash0 = murmur3_seeded(seed0, icase_data.buf, len);\n+\thash1 = murmur3_seeded(seed1, icase_data.buf, len);\n \n \tkey->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));\n \tfor (i = 0; i < settings->num_hashes; i++)\ndiff --git a/revision.c b/revision.c\nindex f78c636e4d..a02be25feb 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -652,13 +652,14 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \n static int forbid_bloom_filters(struct pathspec *spec)\n {\n+\tint allowed_flags = PATHSPEC_LITERAL | PATHSPEC_ICASE;\n \tif (spec->has_wildcard)\n \t\treturn 1;\n \tif (spec->nr > 1)\n \t\treturn 1;\n-\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\tif (spec->magic & ~allowed_flags)\n \t\treturn 1;\n-\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n+\tif (spec->nr && (spec->items[0].magic & ~allowed_flags))\n \t\treturn 1;\n \n \treturn 0;\ndiff --git a/t/t6131-pathspec-icase.sh b/t/t6131-pathspec-icase.sh\nindex 39fc3f6769..ee0766bd91 100755\n--- a/t/t6131-pathspec-icase.sh\n+++ b/t/t6131-pathspec-icase.sh\n@@ -106,4 +106,22 @@ test_expect_success '\"git diff\" can take magic :(icase) pathspec' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success '\"git log\" takes the magic :(icase) pathspec' '\n+\tcat >expect <<-\\EOF &&\n+\tFOO/BAR\n+\tFOO/bAr\n+\tFOO/bar\n+\tfOo/BAR\n+\tfOo/bAr\n+\tfOo/bar\n+\tfoo/BAR\n+\tfoo/bAr\n+\tfoo/bar\n+\tEOF\n+\tgit log --pretty=%s HEAD -- \":(icase)foo/bar\" >actual &&\n+\ttest_cmp expect actual &&\n+\tgit log --pretty=%s HEAD -- \":(icase)foo\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n\n\n"},{"id":"395527","messageId":"xmqqr1wo5yud.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"99e0ae2c-6b65-24e4-3d2b-1dff619a5daa@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-15T19:32:42Z","receivedAt":"2020-04-15T19:33:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> diff --git a/bloom.c b/bloom.c\n> index dd9bab9bbd..c919c60f12 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -130,8 +130,20 @@ void fill_bloom_key(const char *data,\n> \tint i;\n> \tconst uint32_t seed0 = 0x293ae76f;\n> \tconst uint32_t seed1 = 0x7e646e2c;\n> -\tconst uint32_t hash0 = murmur3_seeded(seed0, data, len);\n> -\tconst uint32_t hash1 = murmur3_seeded(seed1, data, len);\n> +\tuint32_t hash0, hash1;\n> +\tstatic struct strbuf icase_data = STRBUF_INIT;\n> +\tchar *cur;\n> +\n> +\tstrbuf_setlen(&icase_data, 0);\n> +\tstrbuf_addstr(&icase_data, data);\n\nPerhaps \n\n\tstrbuf_reset(&icase_data);\n\tstrbuf_add(&icase_data, data, len);\n\nOr do we know bloom keys are always NUL-terminated string?\n\nI am not sure how reusable bloom.c::fill_bloom_key() is designed to\nbe. If it is for the sole use of the changed-paths, then it is OK\nto assume that our data is NUL-terminated string and that keys wants\nto be always computed after downcasing (assuming that icase search\nis something we want to optimize for, which I find is a bit iffy).\n\nIf not, obviously we would want these two things done on the\ncaller's side (or perhaps a new helper function whose callers can\nmake these assumption, fill_bloom_path(), may want to be inserted\nbetween fill_bloom_key() and its callers).\n\n> +\tfor (cur = icase_data.buf; cur && *cur; cur++) {\n> +\t\tif (isupper(*cur))\n> +\t\t\t*cur = tolower(*cur);\n> +\t}\n> +\n> +\thash0 = murmur3_seeded(seed0, icase_data.buf, len);\n> +\thash1 = murmur3_seeded(seed1, icase_data.buf, len);\n> \n> \tkey->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));\n> \tfor (i = 0; i < settings->num_hashes; i++)\n\nIn any case, the update to the above function seems fairly isolated.\nNicely done.\n\n> diff --git a/revision.c b/revision.c\n> index f78c636e4d..a02be25feb 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -652,13 +652,14 @@ static void trace2_bloom_filter_statistics_atexit(void)\n> \n> static int forbid_bloom_filters(struct pathspec *spec)\n> {\n> +\tint allowed_flags = PATHSPEC_LITERAL | PATHSPEC_ICASE;\n> \tif (spec->has_wildcard)\n> \t\treturn 1;\n> \tif (spec->nr > 1)\n> \t\treturn 1;\n> -\tif (spec->magic & ~PATHSPEC_LITERAL)\n> +\tif (spec->magic & ~allowed_flags)\n> \t\treturn 1;\n> -\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n> +\tif (spec->nr && (spec->items[0].magic & ~allowed_flags))\n> \t\treturn 1;\n> \n> \treturn 0;\n\nAnd thanks to the refactoring done to invent this helper function,\nthe side that uses the Bloom data is quite straight-forward.\n\nAs you are, I am on the fence. \n\nI do not think :(icase) pathspec is something we want to optimize\nfor, but I still like this new hash function primarily because I\nsuspect that it will increase the number of paths that you can cram\ninto the filter without getting their hashes collided (hence getting\nfalse positive), under the assumption that real projects won't try\nto store too many pair of paths that are only different in their\ncase, and if that is the case, it would help performance. So if we\nwere to benchmark, we'd also pay attention to that side, in addition\nto the obvious downside of having to allocate and downcase.\n\nThanks.\n"},{"id":"395528","messageId":"xmqqmu7c5yio.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"xmqqr1wo5yud.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-15T19:39:43Z","receivedAt":"2020-04-15T19:39:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> As you are, I am on the fence. \n>\n> I do not think :(icase) pathspec is something we want to optimize\n> for, but I still like this new hash function primarily because I\n> suspect that it will increase the number of paths that you can cram\n> into the filter without getting their hashes collided (hence getting\n> false positive), under the assumption that real projects won't try\n> to store too many pair of paths that are only different in their\n> case...\n\nSorry, but no, I do not think there is such upside. It may have\neffects on the actual hash values to downcase paths that are\noriginally camelCased, but reducing the entropy of input paths that\nway shouldn't have effect on the overall distribution and rate of\ncollision in any meaningful way (otherwise the chosen underlying\nhash function would be broken). So, sorry for the noise.\n\n\n\n"},{"id":"395538","messageId":"xmqq8siw5tlv.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"99e0ae2c-6b65-24e4-3d2b-1dff619a5daa@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-15T21:25:48Z","receivedAt":"2020-04-15T21:26:03Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n> Bloom filters computed by a previous commit will not be compatible\n> with the filters computed in this commit, nor will we get correct\n> results when testing across these incompatible versions. Normally,\n> this would be a completely unacceptable change, but the filters\n> have not been released and hence are still possible to update\n> before release.\n\nSure, it hasn't even hit 'next' yet. \n\nBut I think we are both sort-of leaning towards concluding that it\ndoes not help all that much. So I think it is OK.\n\n> TODO: If we decide to move in this direction, then the following\n> steps should be done (and some of them should be done anyway):\n\nEven if we decide not to do this \"downcase before hashing\" thing, we\nshould document how exactly we compute, I think.\n\nAnd if we decide do change our mind later, it is not the end of the\nworld. We should be able to use a different chunk type to store the\nfilters computed over downcased paths.\n\n> * We need to document the Bloom filter format to specify exactly\n> how we compute the filter data. The details should be careful\n> enough that someone can reproduce the exact file format without\n> looking at the C code.\n>\n> * That document would include the tolower() transformation that is\n> being done here.\n\nAs the tree-diff comparison done internally while running \"git\nblame\" does not take an end-user specified pathspec in any\nmeaningful way, this does not matter in practice, but there is\nanother possible complication we would want to consider when we\nextend the support to \"git log\" and friends---negative pathspecs\n(e.g. \"git log ':(exclude)COPYING'\"). A commit that cannot possibly\nhave touched the COPYING file would be eligible for output without\nactually running tree-diff between it and its parent (as long as the\ntrees of the two commits are different, we know it must be shown).\n\nThanks.\n"},{"id":"395543","messageId":"CANQwDwdcM-hc+Nyc0nBnp79W0BuH2PfdgM6WLqET3sPn1GYc-A@mail.gmail.com","threadId":"53210","inReplyTo":"99e0ae2c-6b65-24e4-3d2b-1dff619a5daa@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2020-04-15T22:18:33Z","receivedAt":"2020-04-15T22:19:17Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Wed, 15 Apr 2020 at 20:37, Derrick Stolee wrote:\n[...]\n> -->8--\n> From 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001\n> From: Derrick Stolee \n> Date: Wed, 15 Apr 2020 18:04:25 +0000\n> Subject: [PATCH] bloom: compute all Bloom hashes from lowercase\n>\n> The changed-path Bloom filters currently hash path strings using\n> the exact string for the path. This makes it difficult* to use the\n> filters when restricting to case-insensitive pathspecs.\n>\n> * I say \"difficult\" because it is possible to generate all 2^n\n> options for the case of a path and test them all, but this is\n> a bad idea and should not be done. \"Impossible\" is an appropriate\n> alternative.\n>\n> THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n> Bloom filters computed by a previous commit will not be compatible\n> with the filters computed in this commit, nor will we get correct\n> results when testing across these incompatible versions. Normally,\n> this would be a completely unacceptable change, but the filters\n> have not been released and hence are still possible to update\n> before release.\n>\n> TODO: If we decide to move in this direction, then the following\n> steps should be done (and some of them should be done anyway):\n>\n> * We need to document the Bloom filter format to specify exactly\n> how we compute the filter data. The details should be careful\n> enough that someone can reproduce the exact file format without\n> looking at the C code.\n>\n> * That document would include the tolower() transformation that is\n> being done here.\n\nWhy not modify the BDAT chunk to include version of\ncase folding transformation or other collation algorithm\n(other transformation).that is done prior to computing\nthe Bloom filter key? Though that might be unnecessary\nflexibility...\n\nFor example the value of 0x00 in such field of BDAT\nchunk header would mean no transformation, while\nthe value of 0x01 would mean per-character tolower()\nor Unicode equivalent of it.\n\nBest,\n-- \nJakub Narębski\n"},{"id":"395556","messageId":"20200416005241.GB36156@syl.local","threadId":"53210","inReplyTo":"CANQwDwdcM-hc+Nyc0nBnp79W0BuH2PfdgM6WLqET3sPn1GYc-A@mail.gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-16T00:52:41Z","receivedAt":"2020-04-16T00:52:54Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Apr 16, 2020 at 12:18:33AM +0200, Jakub Narębski wrote:\n> On Wed, 15 Apr 2020 at 20:37, Derrick Stolee wrote:\n> [...]\n> > -->8--\n> > From 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001\n> > From: Derrick Stolee \n> > Date: Wed, 15 Apr 2020 18:04:25 +0000\n> > Subject: [PATCH] bloom: compute all Bloom hashes from lowercase\n> >\n> > The changed-path Bloom filters currently hash path strings using\n> > the exact string for the path. This makes it difficult* to use the\n> > filters when restricting to case-insensitive pathspecs.\n> >\n> > * I say \"difficult\" because it is possible to generate all 2^n\n> > options for the case of a path and test them all, but this is\n> > a bad idea and should not be done. \"Impossible\" is an appropriate\n> > alternative.\n> >\n> > THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n> > Bloom filters computed by a previous commit will not be compatible\n> > with the filters computed in this commit, nor will we get correct\n> > results when testing across these incompatible versions. Normally,\n> > this would be a completely unacceptable change, but the filters\n> > have not been released and hence are still possible to update\n> > before release.\n> >\n> > TODO: If we decide to move in this direction, then the following\n> > steps should be done (and some of them should be done anyway):\n> >\n> > * We need to document the Bloom filter format to specify exactly\n> > how we compute the filter data. The details should be careful\n> > enough that someone can reproduce the exact file format without\n> > looking at the C code.\n> >\n> > * That document would include the tolower() transformation that is\n> > being done here.\n>\n> Why not modify the BDAT chunk to include version of\n> case folding transformation or other collation algorithm\n> (other transformation).that is done prior to computing\n> the Bloom filter key? Though that might be unnecessary\n> flexibility...\n\nIf this ends up being something that we want to do, I agree with\nStolee's reasoning that this should be a breaking change. If we were,\nsay, several months into having Bloom filters in a release and decided\nat that point to make the change, then: sure, supporting both by writing\na bit in the BDAT chunk makes sense.\n\nBut, we're many months away from that state yet, and so I don't think\nthe cost of rebuilding what few commit-graphs exist with bloom filters\nin them today to support both ordinary and lower-cased paths in the\nfilter.\n\nAnyway, I'm still not sold on this idea in general (nor do I understand\nit that others are), so I'll respond in more detail in another part of\nthe thread...\n\n> For example the value of 0x00 in such field of BDAT\n> chunk header would mean no transformation, while\n> the value of 0x01 would mean per-character tolower()\n> or Unicode equivalent of it.\n>\n> Best,\n> --\n> Jakub Narębski\n\nThanks,\nTaylor\n"},{"id":"395557","messageId":"20200416005640.GC36156@syl.local","threadId":"53210","inReplyTo":"xmqq8siw5tlv.fsf@gitster.c.googlers.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-16T00:56:40Z","receivedAt":"2020-04-16T00:57:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Wed, Apr 15, 2020 at 02:25:48PM -0700, Junio C Hamano wrote:\n> Derrick Stolee writes:\n>\n> > THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n> > Bloom filters computed by a previous commit will not be compatible\n> > with the filters computed in this commit, nor will we get correct\n> > results when testing across these incompatible versions. Normally,\n> > this would be a completely unacceptable change, but the filters\n> > have not been released and hence are still possible to update\n> > before release.\n>\n> Sure, it hasn't even hit 'next' yet.\n>\n> But I think we are both sort-of leaning towards concluding that it\n> does not help all that much. So I think it is OK.\n\nYeah, I think that the only thing that it is potentially helping is the\n:(icase) magic. In a repository that doesn't have colliding paths in\ncase-insensitive filesystems (i.e., having both 'foo' and 'FOO' in the\nsame tree), this doesn't seem to be obviously hurting anything.\n\nBut, it is at least semi-harmful to repositories that do have such\ntrees, since we now can't answer \"probably yes\" or \"definitely not\" for\ncolliding paths unless both produce the same fingerprint. That seems\nlike a clear downside.\n\nNow, how common is that against people who would benefit from\nchanged-path Bloom filters in their commit-graphs? I don't know one way\nor the other. But, the upside seems to be minimal compared to the\npotential cost, so I think that it may be better to just leave this one\nalone.\n\n> > TODO: If we decide to move in this direction, then the following\n> > steps should be done (and some of them should be done anyway):\n>\n> Even if we decide not to do this \"downcase before hashing\" thing, we\n> should document how exactly we compute, I think.\n>\n> And if we decide do change our mind later, it is not the end of the\n> world. We should be able to use a different chunk type to store the\n> filters computed over downcased paths.\n>\n> > * We need to document the Bloom filter format to specify exactly\n> > how we compute the filter data. The details should be careful\n> > enough that someone can reproduce the exact file format without\n> > looking at the C code.\n> >\n> > * That document would include the tolower() transformation that is\n> > being done here.\n>\n> As the tree-diff comparison done internally while running \"git\n> blame\" does not take an end-user specified pathspec in any\n> meaningful way, this does not matter in practice, but there is\n> another possible complication we would want to consider when we\n> extend the support to \"git log\" and friends---negative pathspecs\n> (e.g. \"git log ':(exclude)COPYING'\"). A commit that cannot possibly\n> have touched the COPYING file would be eligible for output without\n> actually running tree-diff between it and its parent (as long as the\n> trees of the two commits are different, we know it must be shown).\n>\n> Thanks.\n\nThanks,\nTaylor\n"},{"id":"395598","messageId":"67350f6c-d558-8b9b-4d57-5830f7a74fab@gmail.com","threadId":"53210","inReplyTo":"20200416005241.GB36156@syl.local","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-04-16T13:26:49Z","receivedAt":"2020-04-16T16:02:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/15/2020 8:52 PM, Taylor Blau wrote:\n> On Thu, Apr 16, 2020 at 12:18:33AM +0200, Jakub Narębski wrote:\n>> On Wed, 15 Apr 2020 at 20:37, Derrick Stolee wrote:\n>> [...]\n>>> -->8--\n>>> From 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001\n>>> From: Derrick Stolee \n>>> Date: Wed, 15 Apr 2020 18:04:25 +0000\n>>> Subject: [PATCH] bloom: compute all Bloom hashes from lowercase\n>>>\n>>> The changed-path Bloom filters currently hash path strings using\n>>> the exact string for the path. This makes it difficult* to use the\n>>> filters when restricting to case-insensitive pathspecs.\n>>>\n>>> * I say \"difficult\" because it is possible to generate all 2^n\n>>> options for the case of a path and test them all, but this is\n>>> a bad idea and should not be done. \"Impossible\" is an appropriate\n>>> alternative.\n>>>\n>>> THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n>>> Bloom filters computed by a previous commit will not be compatible\n>>> with the filters computed in this commit, nor will we get correct\n>>> results when testing across these incompatible versions. Normally,\n>>> this would be a completely unacceptable change, but the filters\n>>> have not been released and hence are still possible to update\n>>> before release.\n>>>\n>>> TODO: If we decide to move in this direction, then the following\n>>> steps should be done (and some of them should be done anyway):\n>>>\n>>> * We need to document the Bloom filter format to specify exactly\n>>> how we compute the filter data. The details should be careful\n>>> enough that someone can reproduce the exact file format without\n>>> looking at the C code.\n>>>\n>>> * That document would include the tolower() transformation that is\n>>> being done here.\n>>\n>> Why not modify the BDAT chunk to include version of\n>> case folding transformation or other collation algorithm\n>> (other transformation).that is done prior to computing\n>> the Bloom filter key? Though that might be unnecessary\n>> flexibility...\n> \n> If this ends up being something that we want to do, I agree with\n> Stolee's reasoning that this should be a breaking change. If we were,\n> say, several months into having Bloom filters in a release and decided\n> at that point to make the change, then: sure, supporting both by writing\n> a bit in the BDAT chunk makes sense.\n> \n> But, we're many months away from that state yet, and so I don't think\n> the cost of rebuilding what few commit-graphs exist with bloom filters\n> in them today to support both ordinary and lower-cased paths in the\n> filter.\n> \n> Anyway, I'm still not sold on this idea in general (nor do I understand\n> it that others are), so I'll respond in more detail in another part of\n> the thread...\n\nI agree that this is not a good direction to go. I created the patch\nbecause I was curious how difficult it would be, and it is good to have\na record of the possible direction. However, it complicates the file\nformat and will have unpredictable effects on the entropy (or on the\nperformance of history for case-colliding paths).\n\nIt is good that we have the capability to extend the filter data in\nthe future if we really need to.\n\nI'll make a TODO item for myself to try writing that detailed Bloom\nfilter format documentation as a follow-up. In the meantime, I'll try\nto close this out by responding to the feedback we have so far.\n\nThanks,\n-Stolee\n\n\n"},{"id":"395606","messageId":"20200416163330.GB78342@syl.local","threadId":"53210","inReplyTo":"67350f6c-d558-8b9b-4d57-5830f7a74fab@gmail.com","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-04-16T16:33:30Z","receivedAt":"2020-04-16T16:33:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Apr 16, 2020 at 09:26:49AM -0400, Derrick Stolee wrote:\n> On 4/15/2020 8:52 PM, Taylor Blau wrote:\n> > On Thu, Apr 16, 2020 at 12:18:33AM +0200, Jakub Narębski wrote:\n> >> On Wed, 15 Apr 2020 at 20:37, Derrick Stolee wrote:\n> >> [...]\n> >>> -->8--\n> >>> From 89beb9598daabb19e3c896bbceeb0fc1b9ccc6ca Mon Sep 17 00:00:00 2001\n> >>> From: Derrick Stolee \n> >>> Date: Wed, 15 Apr 2020 18:04:25 +0000\n> >>> Subject: [PATCH] bloom: compute all Bloom hashes from lowercase\n> >>>\n> >>> The changed-path Bloom filters currently hash path strings using\n> >>> the exact string for the path. This makes it difficult* to use the\n> >>> filters when restricting to case-insensitive pathspecs.\n> >>>\n> >>> * I say \"difficult\" because it is possible to generate all 2^n\n> >>> options for the case of a path and test them all, but this is\n> >>> a bad idea and should not be done. \"Impossible\" is an appropriate\n> >>> alternative.\n> >>>\n> >>> THIS IS A BREAKING CHANGE. Commit-graph files with changed-path\n> >>> Bloom filters computed by a previous commit will not be compatible\n> >>> with the filters computed in this commit, nor will we get correct\n> >>> results when testing across these incompatible versions. Normally,\n> >>> this would be a completely unacceptable change, but the filters\n> >>> have not been released and hence are still possible to update\n> >>> before release.\n> >>>\n> >>> TODO: If we decide to move in this direction, then the following\n> >>> steps should be done (and some of them should be done anyway):\n> >>>\n> >>> * We need to document the Bloom filter format to specify exactly\n> >>> how we compute the filter data. The details should be careful\n> >>> enough that someone can reproduce the exact file format without\n> >>> looking at the C code.\n> >>>\n> >>> * That document would include the tolower() transformation that is\n> >>> being done here.\n> >>\n> >> Why not modify the BDAT chunk to include version of\n> >> case folding transformation or other collation algorithm\n> >> (other transformation).that is done prior to computing\n> >> the Bloom filter key? Though that might be unnecessary\n> >> flexibility...\n> >\n> > If this ends up being something that we want to do, I agree with\n> > Stolee's reasoning that this should be a breaking change. If we were,\n> > say, several months into having Bloom filters in a release and decided\n> > at that point to make the change, then: sure, supporting both by writing\n> > a bit in the BDAT chunk makes sense.\n> >\n> > But, we're many months away from that state yet, and so I don't think\n> > the cost of rebuilding what few commit-graphs exist with bloom filters\n> > in them today to support both ordinary and lower-cased paths in the\n> > filter.\n> >\n> > Anyway, I'm still not sold on this idea in general (nor do I understand\n> > it that others are), so I'll respond in more detail in another part of\n> > the thread...\n>\n> I agree that this is not a good direction to go. I created the patch\n> because I was curious how difficult it would be, and it is good to have\n> a record of the possible direction. However, it complicates the file\n> format and will have unpredictable effects on the entropy (or on the\n> performance of history for case-colliding paths).\n>\n> It is good that we have the capability to extend the filter data in\n> the future if we really need to.\n>\n> I'll make a TODO item for myself to try writing that detailed Bloom\n> filter format documentation as a follow-up. In the meantime, I'll try\n> to close this out by responding to the feedback we have so far.\n\nSounds good, and thanks for investigating.\n\n> Thanks,\n> -Stolee\n\nThanks,\nTaylor\n"},{"id":"395609","messageId":"xmqqk12fz4uk.fsf@gitster.c.googlers.com","threadId":"53210","inReplyTo":"20200416163330.GB78342@syl.local","subject":"Re: [PATCH 1/3] revision: complicated pathspecs disable filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-04-16T18:02:27Z","receivedAt":"2020-04-16T18:02:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau writes:\n\n>> It is good that we have the capability to extend the filter data in\n>> the future if we really need to.\n>>\n>> I'll make a TODO item for myself to try writing that detailed Bloom\n>> filter format documentation as a follow-up. In the meantime, I'll try\n>> to close this out by responding to the feedback we have so far.\n>\n> Sounds good, and thanks for investigating.\n\nYeah, thanks, all.\n\n"},{"id":"395617","messageId":"adc03eee4ac8a0911bfd2a7ae03364ef0e744ef0.1587068044.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v3.git.1587068044.gitgitgadget@gmail.com","subject":"[PATCH v3 1/3] revision: complicated pathspecs disable filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-16T20:14:02Z","receivedAt":"2020-04-16T20:19:55Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters work only when we can compute an\nexplicit Bloom filter key in advance. When a pathspec is given\nthat allows case-insensitive checks or wildcard matching, we\nmust disable the Bloom filter performance checks.\n\nBy checking the pathspec in prepare_to_use_bloom_filters(), we\navoid setting up the Bloom filter data and thus revert to the\nusual logic.\n\nBefore this change, the following tests would fail*:\n\n\tt6004-rev-list-path-optim.sh (Tests 6-7)\n\tt6130-pathspec-noglob.sh (Tests 3-6)\n\tt6131-pathspec-icase.sh (Tests 3-5)\n\n*These tests would fail when using GIT_TEST_COMMIT_GRAPH and\nGIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\nenvironment variable was not set up correctly to write the changed-\npath Bloom filters in the test suite. That will be fixed in the\nnext change.\n\nHelped-by: Taylor Blau \nSigned-off-by: Derrick Stolee \n---\n revision.c | 19 ++++++++++++++++++-\n 1 file changed, 18 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex 2b06ee739c8..f78c636e4d0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -650,6 +650,20 @@ static void trace2_bloom_filter_statistics_atexit(void)\n \tjw_release(&jw);\n }\n \n+static int forbid_bloom_filters(struct pathspec *spec)\n+{\n+\tif (spec->has_wildcard)\n+\t\treturn 1;\n+\tif (spec->nr > 1)\n+\t\treturn 1;\n+\tif (spec->magic & ~PATHSPEC_LITERAL)\n+\t\treturn 1;\n+\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n+\t\treturn 1;\n+\n+\treturn 0;\n+}\n+\n static void prepare_to_use_bloom_filter(struct rev_info *revs)\n {\n \tstruct pathspec_item *pi;\n@@ -659,7 +673,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n \tint len;\n \n \tif (!revs->commits)\n-\t return;\n+\t\treturn;\n+\n+\tif (forbid_bloom_filters(&revs->prune_data))\n+\t\treturn;\n \n \trepo_parse_commit(revs->repo, revs->commits->item);\n \n-- \ngitgitgadget\n\n"},{"id":"395618","messageId":"4073c8fe42ffbf32288c598abda527342d21bf67.1587068044.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v3.git.1587068044.gitgitgadget@gmail.com","subject":"[PATCH v3 2/3] tests: write commit-graph with Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-16T20:14:03Z","receivedAt":"2020-04-16T20:19:57Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe GIT_TEST_COMMIT_GRAPH environment variable updates the commit-\ngraph file whenever \"git commit\" is run, ensuring that we always\nhave an updated commit-graph throughout the test suite. The\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variable was\nintroduced to write the changed-path Bloom filters whenever \"git\ncommit-graph write\" is run. However, the GIT_TEST_COMMIT_GRAPH\ntrick doesn't launch a separate process and instead writes it\ndirectly.\n\nTo expand the number of tests that have commits in the commit-graph\nfile, add a helper method that computes the commit-graph and place\nthat helper inside \"git commit\" and \"git merge\".\n\nIn the helper method, check GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\nto ensure we are writing changed-path Bloom filters whenever\npossible.\n\nSigned-off-by: Derrick Stolee \n---\n builtin/commit.c | 4 +---\n builtin/merge.c | 7 +++++--\n commit-graph.c | 14 ++++++++++++++\n commit-graph.h | 9 +++++++++\n 4 files changed, 29 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/commit.c b/builtin/commit.c\nindex d3e7781e658..27d4ff6b790 100644\n--- a/builtin/commit.c\n+++ b/builtin/commit.c\n@@ -1700,9 +1700,7 @@ int cmd_commit(int argc, const char **argv, const char *prefix)\n \t\t \"new_index file. Check that disk is not full and quota is\\n\"\n \t\t \"not exceeded, and then \\\"git restore --staged :/\\\" to recover.\"));\n \n-\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n-\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n-\t\treturn 1;\n+\tgit_test_write_commit_graph_or_die();\n \n \trepo_rerere(the_repository, 0);\n \trun_command_v_opt(argv_gc_auto, RUN_GIT_CMD);\ndiff --git a/builtin/merge.c b/builtin/merge.c\nindex d127d2225f8..db11af5b1cd 100644\n--- a/builtin/merge.c\n+++ b/builtin/merge.c\n@@ -40,6 +40,7 @@\n #include \"branch.h\"\n #include \"commit-reach.h\"\n #include \"wt-status.h\"\n+#include \"commit-graph.h\"\n \n #define DEFAULT_TWOHEAD (1<<0)\n #define DEFAULT_OCTOPUS (1<<1)\n@@ -1673,9 +1674,11 @@ int cmd_merge(int argc, const char **argv, const char *prefix)\n \t\t\t\t head_commit);\n \t}\n \n-\tif (squash)\n+\tif (squash) {\n \t\tfinish(head_commit, remoteheads, NULL, NULL);\n-\telse\n+\n+\t\tgit_test_write_commit_graph_or_die();\n+\t} else\n \t\twrite_merge_state(remoteheads);\n \n \tif (merge_was_ok)\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 77668629e27..0809f34f8d3 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -19,6 +19,20 @@\n #include \"bloom.h\"\n #include \"commit-slab.h\"\n \n+void git_test_write_commit_graph_or_die(void)\n+{\n+\tint flags = 0;\n+\tif (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))\n+\t\treturn;\n+\n+\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n+\t\tflags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS;\n+\t\n+\tif (write_commit_graph_reachable(the_repository->objects->odb,\n+\t\t\t\t\t flags, NULL))\n+\t\tdie(\"failed to write commit-graph under GIT_TEST_COMMIT_GRAPH\");\n+}\n+\n #define GRAPH_SIGNATURE 0x43475048 /* \"CGPH\" */\n #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* \"OIDF\" */\n #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* \"OIDL\" */\ndiff --git a/commit-graph.h b/commit-graph.h\nindex 8655d064c14..39484482cc1 100644\n--- a/commit-graph.h\n+++ b/commit-graph.h\n@@ -11,6 +11,15 @@\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 \n+/*\n+ * This method is only used to enhance coverage of the commit-graph\n+ * feature in the test suite with the GIT_TEST_COMMIT_GRAPH and\n+ * GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variables. Do not\n+ * call this method oustide of a builtin, and only if you know what\n+ * you are doing!\n+ */\n+void git_test_write_commit_graph_or_die(void);\n+\n struct commit;\n struct bloom_filter_settings;\n \n-- \ngitgitgadget\n\n"},{"id":"395619","messageId":"pull.609.v3.git.1587068044.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v2.git.1586789126.gitgitgadget@gmail.com","subject":"[PATCH v3 0/3] Integrate changed-path Bloom filters with 'git blame'","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-16T20:14:01Z","receivedAt":"2020-04-16T20:19:59Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"If the changed-path Bloom filters are relatively stable, then I propose\ntrying to build upon them as a way to discover any deficiencies. Also, it's\ngood to use them when we can.\n\nThe goal I set out to achieve was to use Bloom filters as much as possible\nin git blame. I think I have achieved most of that, except I did not\nintegrate it with the -C mode. In that case, the blob-diff computation takes\na majority of the computation time, so short-circuiting the tree diff using\nBloom filters. Also, it's just really complicated. If someone else thinks\nthere is an easy win there, then please go ahead and give it a try with the\nextra logic presented here in PATCH 3.\n\nWhile I was playing around with Bloom filters and git blame, I purposefully\ngot it working with some scenarios but not all. Then I tried to trigger a\nfailing build in the blame tests using GIT_TEST_COMMIT_GRAPH=1 and \nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS=1. But the tests all succeeded!\n\nExamining the data, I see that the commit-graph didn't have the Bloom filter\nchunks at all. This is because we are not setting the flag to write them in\nthe right spot. The GIT_TEST_COMMIT_GRAPH=1 variable triggers a commit-graph\nwrite during git commit, so we need to update the code there instead of just\ninspecting the variable in git commit-graph write. (This is PATCH 2.)\n\nBy updating this variable, I saw some test failures in other tests regarding\nnon-exact pathspecs. I fixed these in PATCH 1 so we keep clean builds.\n\nI based this change on [1] but it would apply cleanly (and logically) on\ngs/commit-graph-path-filter\n\nUpdates in v2:\n\n * Added PATCH 3 to write commit-graph files during 'git merge' if\n GIT_TEST_COMMIT_GRAPH is enabled.\n \n \n * Updated PATCH 1 with the simplification recommended by Taylor.\n \n \n * Fixed the lower-case \"bloom\" in the commit message.\n \n \n\nThanks, -Stolee\n\n[1] \nhttps://lore.kernel.org/git/pull.601.v2.git.1586437211842.gitgitgadget@gmail.com/\n\nDerrick Stolee (3):\n revision: complicated pathspecs disable filters\n tests: write commit-graph with Bloom filters\n blame: use changed-path Bloom filters\n\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++---\n blame.h | 6 ++\n builtin/blame.c | 10 ++++\n builtin/commit.c | 4 +-\n builtin/merge.c | 7 ++-\n commit-graph.c | 14 +++++\n commit-graph.h | 9 +++\n revision.c | 19 ++++++-\n 8 files changed, 193 insertions(+), 15 deletions(-)\n\n\nbase-commit: f4df00a0dd448edce0e854a97f63598fefe27d27\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-609%2Fderrickstolee%2Fbloom-blame-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-609/derrickstolee/bloom-blame-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/609\n\nRange-diff vs v2:\n\n 1: adc03eee4ac = 1: adc03eee4ac revision: complicated pathspecs disable filters\n 2: 7e8f1aed113 < -: ----------- commit: write commit-graph with Bloom filters\n 3: 824f8ad067b ! 2: 4073c8fe42f commit-graph: write commit-graph in more tests\n @@ Metadata\n Author: Derrick Stolee \n \n ## Commit message ##\n - commit-graph: write commit-graph in more tests\n + tests: write commit-graph with Bloom filters\n \n - The GIT_TEST_COMMIT_GRAPH test environment variable triggers\n - commit-graph writes during each \"git commit\" process. To expand\n - the number of tests that have commits in the commit-graph file,\n - add a helper method that computes the commit-graph and place\n + The GIT_TEST_COMMIT_GRAPH environment variable updates the commit-\n + graph file whenever \"git commit\" is run, ensuring that we always\n + have an updated commit-graph throughout the test suite. The\n + GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variable was\n + introduced to write the changed-path Bloom filters whenever \"git\n + commit-graph write\" is run. However, the GIT_TEST_COMMIT_GRAPH\n + trick doesn't launch a separate process and instead writes it\n + directly.\n +\n + To expand the number of tests that have commits in the commit-graph\n + file, add a helper method that computes the commit-graph and place\n that helper inside \"git commit\" and \"git merge\".\n \n + In the helper method, check GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS\n + to ensure we are writing changed-path Bloom filters whenever\n + possible.\n +\n Signed-off-by: Derrick Stolee \n \n ## builtin/commit.c ##\n @@ commit-graph.c\n \n +void git_test_write_commit_graph_or_die(void)\n +{\n -+\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH, 0) &&\n -+\t write_commit_graph_reachable(the_repository->objects->odb, 0, NULL))\n ++\tint flags = 0;\n ++\tif (!git_env_bool(GIT_TEST_COMMIT_GRAPH, 0))\n ++\t\treturn;\n ++\n ++\tif (git_env_bool(GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS, 0))\n ++\t\tflags = COMMIT_GRAPH_WRITE_BLOOM_FILTERS;\n ++\t\n ++\tif (write_commit_graph_reachable(the_repository->objects->odb,\n ++\t\t\t\t\t flags, NULL))\n +\t\tdie(\"failed to write commit-graph under GIT_TEST_COMMIT_GRAPH\");\n +}\n +\n @@ commit-graph.h\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 \n ++/*\n ++ * This method is only used to enhance coverage of the commit-graph\n ++ * feature in the test suite with the GIT_TEST_COMMIT_GRAPH and\n ++ * GIT_TEST_COMMIT_GRAPH_CHANGED_PATHS environment variables. Do not\n ++ * call this method oustide of a builtin, and only if you know what\n ++ * you are doing!\n ++ */\n +void git_test_write_commit_graph_or_die(void);\n +\n struct commit;\n 4: 4ae196d6355 = 3: 463d6bf5033 blame: use changed-path Bloom filters\n\n-- \ngitgitgadget\n"},{"id":"395620","messageId":"463d6bf5033cc6c3d22913c72535d094ffb5b41d.1587068044.git.gitgitgadget@gmail.com","threadId":"53210","inReplyTo":"pull.609.v3.git.1587068044.gitgitgadget@gmail.com","subject":"[PATCH v3 3/3] blame: use changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-04-16T20:14:04Z","receivedAt":"2020-04-16T20:20:02Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe changed-path Bloom filters help reduce the amount of tree\nparsing required during history queries. Before calculating a\ndiff, we can ask the filter if a path changed between a commit\nand its first parent. If the filter says \"no\" then we can move\non without parsing trees. If the filter says \"maybe\" then we\nparse trees to discover if the answer is actually \"yes\" or \"no\".\n\nWhen computing a blame, there is a section in find_origin() that\ncomputes a diff between a commit and one of its parents. When this\nis the first parent, we can check the Bloom filters before calling\ndiff_tree_oid().\n\nIn order to make this work with the blame machinery, we need to\ninitialize a struct bloom_key with the initial path. But also, we\nneed to add more keys to a list if a rename is detected. We then\ncheck to see if _any_ of these keys answer \"maybe\" in the diff.\n\nDuring development, I purposefully left out this \"add a new key\nwhen a rename is detected\" to see if the test suite would catch\nmy error. That is how I discovered the issues with\nGIT_TEST_COMMIT_GRAPH_CHANGED_PATHS from the previous change.\nWith that change, we can feel some confidence in the coverage of\nthis change.\n\nIf a user requests copy detection using \"git blame -C\", then there\nare more places where the set of \"important\" files can expand. I\ndo not know enough about how this happens in the blame machinery.\nThus, the Bloom filter integration is explicitly disabled in this\nmode. A later change could expand the bloom_key data with an\nappropriate call (or calls) to add_bloom_key().\n\nIf we did not disable this mode, then the following tests would\nfail:\n\n\tt8003-blame-corner-cases.sh\n\tt8011-blame-split-file.sh\n\nGenerally, this is a performance enhancement and should not\nchange the behavior of 'git blame' in any way. If a repo has a\ncommit-graph file with computed changed-path Bloom filters, then\nthey should notice improved performance for their 'git blame'\ncommands.\n\nHere are some example timings that I found by blaming some paths\nin the Linux kernel repository:\n\n git blame arch/x86/kernel/topology.c >/dev/null\n\n Before: 0.83s\n After: 0.24s\n\n git blame kernel/time/time.c >/dev/null\n\n Before: 0.72s\n After: 0.24s\n\n git blame tools/perf/ui/stdio/hist.c >/dev/null\n\n Before: 0.27s\n After: 0.11s\n\nI specifically looked for \"deep\" paths that were also edited many\ntimes. As a counterpoint, the MAINTAINERS file was edited many\ntimes but is located in the root tree. This means that the cost of\ncomputing a diff relative to the pathspec is very small. Here are\nthe timings for that command:\n\n git blame MAINTAINERS >/dev/null\n\n Before: 20.1s\n After: 18.0s\n\nThese timings are the best of five. The worst-case runs were on the\norder of 2.5 minutes for both cases. Note that the MAINTAINERS file\nhas 18,740 lines across 17,000+ commits. This happens to be one of\nthe cases where this change provides the least improvement.\n\nThe lack of improvement for the MAINTAINERS file and the relatively\nmodest improvement for the other examples can be easily explained.\nThe blame machinery needs to compute line-level diffs to determine\nwhich lines were changed by each commit. That makes up a large\nproportion of the computation time, and this change does not\nattempt to improve on that section of the algorithm. The\nMAINTAINERS file is large and changed often, so it takes time to\ndetermine which lines were updated by which commit. In contrast,\nthe code files are much smaller, and it takes longer to comute\nthe line-by-line diff for a single patch on the Linux mailing\nlists.\n\nOutside of the \"-C\" integration, I believe there is little more to\ngain from the changed-path Bloom filters for 'git blame' after this\npatch.\n\nSigned-off-by: Derrick Stolee \n---\n blame.c | 139 ++++++++++++++++++++++++++++++++++++++++++++----\n blame.h | 6 +++\n builtin/blame.c | 10 ++++\n 3 files changed, 146 insertions(+), 9 deletions(-)\n\ndiff --git a/blame.c b/blame.c\nindex 29770e5c81c..9fbf79e47c3 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -9,6 +9,8 @@\n #include \"blame.h\"\n #include \"alloc.h\"\n #include \"commit-slab.h\"\n+#include \"bloom.h\"\n+#include \"commit-graph.h\"\n \n define_commit_slab(blame_suspects, struct blame_origin *);\n static struct blame_suspects blame_suspects;\n@@ -1246,13 +1248,75 @@ static int fill_blob_sha1_and_mode(struct repository *r,\n \treturn -1;\n }\n \n+struct blame_bloom_data {\n+\t/*\n+\t * Changed-path Bloom filter keys. These can help prevent\n+\t * computing diffs against first parents, but we need to\n+\t * expand the list as code is moved or files are renamed.\n+\t */\n+\tstruct bloom_filter_settings *settings;\n+\tstruct bloom_key **keys;\n+\tint nr;\n+\tint alloc;\n+};\n+\n+static int bloom_count_queries = 0;\n+static int bloom_count_no = 0;\n+static int maybe_changed_path(struct repository *r,\n+\t\t\t struct commit *parent,\n+\t\t\t struct blame_origin *origin,\n+\t\t\t struct blame_bloom_data *bd)\n+{\n+\tint i;\n+\tstruct bloom_filter *filter;\n+\n+\tif (!bd)\n+\t\treturn 1;\n+\n+\tif (origin->commit->generation == GENERATION_NUMBER_INFINITY)\n+\t\treturn 1;\n+\n+\tfilter = get_bloom_filter(r, origin->commit, 0);\n+\n+\tif (!filter)\n+\t\treturn 1;\n+\n+\tbloom_count_queries++;\n+\tfor (i = 0; i < bd->nr; i++) {\n+\t\tif (bloom_filter_contains(filter,\n+\t\t\t\t\t bd->keys[i],\n+\t\t\t\t\t bd->settings))\n+\t\t\treturn 1;\n+\t}\n+\n+\tbloom_count_no++;\n+\treturn 0;\n+}\n+\n+static void add_bloom_key(struct blame_bloom_data *bd,\n+\t\t\t const char *path)\n+{\n+\tif (!bd)\n+\t\treturn;\n+\n+\tif (bd->nr >= bd->alloc) {\n+\t\tbd->alloc *= 2;\n+\t\tREALLOC_ARRAY(bd->keys, bd->alloc);\n+\t}\n+\n+\tbd->keys[bd->nr] = xmalloc(sizeof(struct bloom_key));\n+\tfill_bloom_key(path, strlen(path), bd->keys[bd->nr], bd->settings);\n+\tbd->nr++;\n+}\n+\n /*\n * We have an origin -- check if the same path exists in the\n * parent and return an origin structure to represent it.\n */\n static struct blame_origin *find_origin(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin;\n \tstruct diff_options diff_opts;\n@@ -1286,10 +1350,19 @@ static struct blame_origin *find_origin(struct repository *r,\n \n \tif (is_null_oid(&origin->commit->object.oid))\n \t\tdo_diff_cache(get_commit_tree_oid(parent), &diff_opts);\n-\telse\n-\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n-\t\t\t get_commit_tree_oid(origin->commit),\n-\t\t\t \"\", &diff_opts);\n+\telse {\n+\t\tint compute_diff = 1;\n+\t\tif (origin->commit->parents &&\n+\t\t !oidcmp(&parent->object.oid,\n+\t\t\t &origin->commit->parents->item->object.oid))\n+\t\t\tcompute_diff = maybe_changed_path(r, parent,\n+\t\t\t\t\t\t\t origin, bd);\n+\n+\t\tif (compute_diff)\n+\t\t\tdiff_tree_oid(get_commit_tree_oid(parent),\n+\t\t\t\t get_commit_tree_oid(origin->commit),\n+\t\t\t\t \"\", &diff_opts);\n+\t}\n \tdiffcore_std(&diff_opts);\n \n \tif (!diff_queued_diff.nr) {\n@@ -1341,7 +1414,8 @@ static struct blame_origin *find_origin(struct repository *r,\n */\n static struct blame_origin *find_rename(struct repository *r,\n \t\t\t\t\tstruct commit *parent,\n-\t\t\t\t\tstruct blame_origin *origin)\n+\t\t\t\t\tstruct blame_origin *origin,\n+\t\t\t\t\tstruct blame_bloom_data *bd)\n {\n \tstruct blame_origin *porigin = NULL;\n \tstruct diff_options diff_opts;\n@@ -1366,6 +1440,7 @@ static struct blame_origin *find_rename(struct repository *r,\n \t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n \t\tif ((p->status == 'R' || p->status == 'C') &&\n \t\t !strcmp(p->two->path, origin->path)) {\n+\t\t\tadd_bloom_key(bd, p->one->path);\n \t\t\tporigin = get_origin(parent, p->one->path);\n \t\t\toidcpy(&porigin->blob_oid, &p->one->oid);\n \t\t\tporigin->mode = p->one->mode;\n@@ -2332,6 +2407,11 @@ static void distribute_blame(struct blame_scoreboard *sb, struct blame_entry *bl\n \n #define MAXSG 16\n \n+typedef struct blame_origin *(*blame_find_alg)(struct repository *,\n+\t\t\t\t\t struct commit *,\n+\t\t\t\t\t struct blame_origin *,\n+\t\t\t\t\t struct blame_bloom_data *);\n+\n static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin, int opt)\n {\n \tstruct rev_info *revs = sb->revs;\n@@ -2356,8 +2436,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t * common cases, then we look for renames in the second pass.\n \t */\n \tfor (pass = 0; pass < 2 - sb->no_whole_file_rename; pass++) {\n-\t\tstruct blame_origin *(*find)(struct repository *, struct commit *, struct blame_origin *);\n-\t\tfind = pass ? find_rename : find_origin;\n+\t\tblame_find_alg find = pass ? find_rename : find_origin;\n \n \t\tfor (i = 0, sg = first_scapegoat(revs, commit, sb->reverse);\n \t\t i < num_sg && sg;\n@@ -2369,7 +2448,7 @@ static void pass_blame(struct blame_scoreboard *sb, struct blame_origin *origin,\n \t\t\t\tcontinue;\n \t\t\tif (parse_commit(p))\n \t\t\t\tcontinue;\n-\t\t\tporigin = find(sb->repo, p, origin);\n+\t\t\tporigin = find(sb->repo, p, origin, sb->bloom_data);\n \t\t\tif (!porigin)\n \t\t\t\tcontinue;\n \t\t\tif (oideq(&porigin->blob_oid, &origin->blob_oid)) {\n@@ -2809,3 +2888,45 @@ struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \tblame_origin_incref(o);\n \treturn new_head;\n }\n+\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path)\n+{\n+\tstruct blame_bloom_data *bd;\n+\n+\tif (!sb->repo->objects->commit_graph)\n+\t\treturn;\n+\n+\tif (!sb->repo->objects->commit_graph->bloom_filter_settings)\n+\t\treturn;\n+\n+\tbd = xmalloc(sizeof(struct blame_bloom_data));\n+\n+\tbd->settings = sb->repo->objects->commit_graph->bloom_filter_settings;\n+\n+\tbd->alloc = 4;\n+\tbd->nr = 0;\n+\tALLOC_ARRAY(bd->keys, bd->alloc);\n+\n+\tadd_bloom_key(bd, path);\n+\n+\tsb->bloom_data = bd;\n+}\n+\n+void cleanup_scoreboard(struct blame_scoreboard *sb)\n+{\n+\tif (sb->bloom_data) {\n+\t\tint i;\n+\t\tfor (i = 0; i < sb->bloom_data->nr; i++) {\n+\t\t\tfree(sb->bloom_data->keys[i]->hashes);\n+\t\t\tfree(sb->bloom_data->keys[i]);\n+\t\t}\n+\t\tfree(sb->bloom_data->keys);\n+\t\tFREE_AND_NULL(sb->bloom_data);\n+\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/queries\", bloom_count_queries);\n+\t\ttrace2_data_intmax(\"blame\", sb->repo,\n+\t\t\t\t \"bloom/response-no\", bloom_count_no);\n+\t}\n+}\ndiff --git a/blame.h b/blame.h\nindex 089b181ff27..b6bbee41472 100644\n--- a/blame.h\n+++ b/blame.h\n@@ -100,6 +100,8 @@ struct blame_entry {\n \tint unblamable;\n };\n \n+struct blame_bloom_data;\n+\n /*\n * The current state of the blame assignment.\n */\n@@ -156,6 +158,7 @@ struct blame_scoreboard {\n \tvoid(*found_guilty_entry)(struct blame_entry *, void *);\n \n \tvoid *found_guilty_entry_data;\n+\tstruct blame_bloom_data *bloom_data;\n };\n \n /*\n@@ -180,6 +183,9 @@ void init_scoreboard(struct blame_scoreboard *sb);\n void setup_scoreboard(struct blame_scoreboard *sb,\n \t\t const char *path,\n \t\t struct blame_origin **orig);\n+void setup_blame_bloom_data(struct blame_scoreboard *sb,\n+\t\t\t const char *path);\n+void cleanup_scoreboard(struct blame_scoreboard *sb);\n \n struct blame_entry *blame_entry_prepend(struct blame_entry *head,\n \t\t\t\t\tlong start, long end,\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex bf1cecdf3f9..3c13634f279 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1061,6 +1061,14 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \tstring_list_clear(&ignore_revs_file_list, 0);\n \tstring_list_clear(&ignore_rev_list, 0);\n \tsetup_scoreboard(&sb, path, &o);\n+\n+\t/*\n+\t * Changed-path Bloom filters are disabled when looking\n+\t * for copies.\n+\t */\n+\tif (!(opt & PICKAXE_BLAME_COPY))\n+\t\tsetup_blame_bloom_data(&sb, path);\n+\n \tlno = sb.num_lines;\n \n \tif (lno && !range_list.nr)\n@@ -1164,5 +1172,7 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \t\tprintf(\"num get patch: %d\\n\", sb.num_get_patch);\n \t\tprintf(\"num commits: %d\\n\", sb.num_commits);\n \t}\n+\n+\tcleanup_scoreboard(&sb);\n \treturn 0;\n }\n-- \ngitgitgadget\n"},{"id":"399263","messageId":"20200607203323.GB11344@szeder.dev","threadId":"53210","inReplyTo":"adc03eee4ac8a0911bfd2a7ae03364ef0e744ef0.1587068044.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v3 1/3] revision: complicated pathspecs disable filters","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-07T20:33:23Z","receivedAt":"2020-06-07T20:33:30Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Thu, Apr 16, 2020 at 08:14:02PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> The changed-path Bloom filters work only when we can compute an\n> explicit Bloom filter key in advance. When a pathspec is given\n> that allows case-insensitive checks or wildcard matching, we\n> must disable the Bloom filter performance checks.\n> \n> By checking the pathspec in prepare_to_use_bloom_filters(), we\n> avoid setting up the Bloom filter data and thus revert to the\n> usual logic.\n> \n> Before this change, the following tests would fail*:\n> \n> \tt6004-rev-list-path-optim.sh (Tests 6-7)\n> \tt6130-pathspec-noglob.sh (Tests 3-6)\n> \tt6131-pathspec-icase.sh (Tests 3-5)\n> \n> *These tests would fail when using GIT_TEST_COMMIT_GRAPH and\n> GIT_TEST_COMMIT_GRAPH_BLOOM_FILTERS except that the latter\n> environment variable was not set up correctly to write the changed-\n> path Bloom filters in the test suite. That will be fixed in the\n> next change.\n> \n> Helped-by: Taylor Blau \n> Signed-off-by: Derrick Stolee \n> ---\n> revision.c | 19 ++++++++++++++++++-\n> 1 file changed, 18 insertions(+), 1 deletion(-)\n> \n> diff --git a/revision.c b/revision.c\n> index 2b06ee739c8..f78c636e4d0 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -650,6 +650,20 @@ static void trace2_bloom_filter_statistics_atexit(void)\n> \tjw_release(&jw);\n> }\n> \n> +static int forbid_bloom_filters(struct pathspec *spec)\n> +{\n> +\tif (spec->has_wildcard)\n> +\t\treturn 1;\n> +\tif (spec->nr > 1)\n> +\t\treturn 1;\n> +\tif (spec->magic & ~PATHSPEC_LITERAL)\n\nNit: spec->magic is the bitwise OR combination of all\nspec->items[i].magic, so checking the latter below is unnecessary.\n\n> +\t\treturn 1;\n> +\tif (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL))\n> +\t\treturn 1;\n> +\n> +\treturn 0;\n> +}\n> +\n> static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> {\n> \tstruct pathspec_item *pi;\n> @@ -659,7 +673,10 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n> \tint len;\n> \n> \tif (!revs->commits)\n> -\t return;\n> +\t\treturn;\n> +\n> +\tif (forbid_bloom_filters(&revs->prune_data))\n> +\t\treturn;\n> \n> \trepo_parse_commit(revs->repo, revs->commits->item);\n> \n> -- \n> gitgitgadget\n> \n"}]}