{"thread":{"id":"53367","subject":"[PATCH 01/12] bloom: fix whitespace around tab length","startedAt":"2020-05-01T15:30:34Z","lastAt":"2020-08-04T14:51:53Z","messageCount":42,"participants":["Derrick Stolee via GitGitGadget","SZEDER Gábor via GitGitGadget","Junio C Hamano","Taylor Blau","Derrick Stolee","SZEDER Gábor"],"isPatch":true,"patchVersion":1,"patchTotal":12},"messages":[{"id":"396755","messageId":"89625b0efae43c8cb0d444a843d389d6cb9f6772.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 01/12] bloom: fix whitespace around tab length","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:18Z","receivedAt":"2020-05-01T15:30:34Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nFix alignment issues that were likely introduced due to an editor\nusing tab lengths of 4 instead of 8.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 16 ++++++++--------\n bloom.h | 4 ++--\n 2 files changed, 10 insertions(+), 10 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex dd9bab9bbd6..2e3e0f5037b 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -29,8 +29,8 @@ static inline unsigned char get_bitmask(uint32_t pos)\n }\n \n static int load_bloom_filter_from_graph(struct commit_graph *g,\n-\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t struct commit *c)\n+\t\t\t\t\tstruct bloom_filter *filter,\n+\t\t\t\t\tstruct commit *c)\n {\n \tuint32_t lex_pos, start_index, end_index;\n \n@@ -123,9 +123,9 @@ uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n }\n \n void fill_bloom_key(const char *data,\n-\t\t\t\t\tsize_t len,\n-\t\t\t\t\tstruct bloom_key *key,\n-\t\t\t\t\tconst struct bloom_filter_settings *settings)\n+\t\t size_t len,\n+\t\t struct bloom_key *key,\n+\t\t const struct bloom_filter_settings *settings)\n {\n \tint i;\n \tconst uint32_t seed0 = 0x293ae76f;\n@@ -139,8 +139,8 @@ void fill_bloom_key(const char *data,\n }\n \n void add_key_to_filter(const struct bloom_key *key,\n-\t\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t\t const struct bloom_filter_settings *settings)\n+\t\t struct bloom_filter *filter,\n+\t\t const struct bloom_filter_settings *settings)\n {\n \tint i;\n \tuint64_t mod = filter->len * BITS_PER_WORD;\n@@ -160,7 +160,7 @@ void init_bloom_filters(void)\n \n struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\t\t\t struct commit *c,\n-\t\t\t\t\t int compute_if_not_present)\n+\t\t\t\t int compute_if_not_present)\n {\n \tstruct bloom_filter *filter;\n \tstruct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;\ndiff --git a/bloom.h b/bloom.h\nindex b935186425d..a51e3715296 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -74,8 +74,8 @@ void fill_bloom_key(const char *data,\n \t\t const struct bloom_filter_settings *settings);\n \n void add_key_to_filter(const struct bloom_key *key,\n-\t\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t\t const struct bloom_filter_settings *settings);\n+\t\t struct bloom_filter *filter,\n+\t\t const struct bloom_filter_settings *settings);\n \n void init_bloom_filters(void);\n \n-- \ngitgitgadget\n\n"},{"id":"396756","messageId":"pull.622.git.1588347029.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":null,"subject":"[PATCH 00/12] Integrating line-log and changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:17Z","receivedAt":"2020-05-01T15:30:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The best way to learn how a feature works is to build on it. That's also the\nbest way to find defects.\n\nI started on this patch series with two goals:\n\n 1. Understand and submit Szeder's incremental line-log RFC [1].\n 2. Integrate changed-path Bloom filters with line-log.\n\n[1] https://lore.kernel.org/git/20190818182801.7580-1-szeder.dev@gmail.com/\n\nSince I knew a lot about the Bloom filters and not much about line-log.c, I\nexpected to learn a lot that could contribute to improving Szeder's patches.\nInstead, I discovered some deficiencies in the Bloom filter code, including\na few meaningful bugs that should be fixed before the topic is merge to\nmaster.\n\nThis series is organized as follows:\n\n * Patches 1-4 are minor Bloom filter cleanups, including a documentation\n bug.\n \n \n * Patch 5 fixes a problem where the Bloom filters use much larger filters\n than expected.\n \n \n * Patch 6 fixes a bug related to the short-circuit of large diffs from\n e369698016 (diff: halt tree-diff early after max_changes, 2020-03-30).\n The condition for halting the diff computation is different than the\n check in bloom.c to see if that short-circuit was hit, which leads to\n some commits with large diffs getting an incomplete Bloom filter. This\n happened on the root commit of the Linux kernel repo, for example.\n \n \n * Patches 7-11 are Szeder's RFC, with my sign-off added. I have not changed\n the code from those submissions because I didn't find anything wrong with\n them as I was testing. However, I will take responsibility to respond to\n the feedback in this series.\n \n \n * Patch 12 integrates Bloom filters with the line-log code.\n \n \n\nI organized these patches so patches 1-6 could be split into its own topic,\nif beneficial to take earlier than the line-log changes.\n\nThe end result of this combined effort is the following: git log -L commands\nfeel much more responsive to a terminal user because Szeder's changes make\nthe computation incremental, and they have better end-to-end performance\nbecause of the integration with Bloom filters to reduce time spent running\ntree diffs for TREESAME commits.\n\nThe following table is also in patch 12, but it summarizes the results of\nthis series. These are timings for running git log -L 1,10:$path for these\nrecently-edited paths. The \"Entire History\" columns wait for the full\ncommand to complete. The \"First Result\" columns add \"-n 1\" to the command,\nso we see the benefits of the incremental algorithm. Thus, the performance\nimprovements from \"Entire History\" to \"First Result\" are due entirely to\nSzeder's patches. The performance improvements from \"Before\" to \"After\" are\ndue to the changed-path Bloom filters.\n\n| | Entire History | First Result |\n| Path | Before | After | Before | After |\n|------------------------------|--------|--------|--------|--------|\n| MAINTAINERS | 4.26 s | 3.87 s | 0.41 s | 0.39 s |\n| fs/namei.c | 1.99 s | 0.99 s | 0.42 s | 0.21 s |\n| arch/x86/kvm/cpuid.c | 5.28 s | 1.12 s | 0.16 s | 0.09 s |\n| fs/io_uring.c | 4.34 s | 0.99 s | 0.94 s | 0.27 s |\n| arch/x86/kvm/vmx/vmx.c | 5.01 s | 1.34 s | 0.21 s | 0.12 s |\n| arch/x86/kvm/x86.c | 2.24 s | 1.18 s | 0.21 s | 0.14 s |\n| fs/btrfs/disk-io.c | 1.82 s | 1.01 s | 0.06 s | 0.05 s |\n| Documentation/scsi/index.rst | 3.30 s | 0.89 s | 1.46 s | 0.03 s |\n\nSome splashy numbers include a 110x speedup for finding the first result for\nDocumentation/scsi/index.rst. That's certainly an outlier, but the rest have\nan at least 10x speedup.\n\nThanks, -Stolee\n\nDerrick Stolee (7):\n bloom: fix whitespace around tab length\n test-bloom: fix usage typo\n Documentation: changed-path Bloom filters use byte words\n bloom: de-duplicate directory entries\n bloom: parse commit before computing filters\n bloom: use num_changes not nr for limit detection\n line-log: integrate with changed-path Bloom filters\n\nSZEDER Gábor (5):\n completion: offer '--(no-)patch' among 'git log' options\n line-log: remove unused fields from 'struct line_log_data'\n t4211-line-log: add tests for parent oids\n line-log: more responsive, incremental 'git log -L'\n line-log: try to use generation number-based topo-ordering\n\n .../technical/commit-graph-format.txt | 8 +--\n bloom.c | 61 ++++++++++++-----\n bloom.h | 5 +-\n contrib/completion/git-completion.bash | 1 +\n line-log.c | 43 +++++++++++-\n line-log.h | 5 +-\n revision.c | 43 ++++++++++--\n t/helper/test-bloom.c | 2 +-\n t/t0095-bloom.sh | 6 +-\n t/t4211-line-log.sh | 68 +++++++++++++++++++\n 10 files changed, 201 insertions(+), 41 deletions(-)\n\n\nbase-commit: 1b4c57fa87e121f155863f898dc39d06cf4a1d99\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-622%2Fderrickstolee%2Flog-l-on-bloom-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-622/derrickstolee/log-l-on-bloom-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/622\n-- \ngitgitgadget\n"},{"id":"396757","messageId":"03b2c84db36754b321dd15cd8a9e1a22b7c11c36.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 03/12] Documentation: changed-path Bloom filters use byte words","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:20Z","receivedAt":"2020-05-01T15:30:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn Documentation/technical/commit-graph-format.txt, the definition\nof the BIDX chunk specifies the length is a number of 8-byte words.\nDuring development we discovered that using 8-byte words in the\nMurmur3 hash algorithm causes issues with Big-Endian versus Little-\nEndian machines. Thus, the hash algorithm was adapted to work on a\nbyte-by-byte basis. However, this caused a change in the definition\nof a \"word\" in bloom.h. Now, a \"word\" is a single byte, which allows\nfilters to be as small as two bytes. These length-two filters are\ndemonstrated in t0095-bloom.sh, and a larger filter of length 25 is\ndemonstrated as well.\n\nThe original point of using 8-byte words was for alignment reasons.\nIt also presented opportunities for extremely sparse Bloom filters\nwhen there were a small number of changes at a commit, creating a\nvery low false-positive rate. However, modifying the format at this\npoint is unlikely to be a valuable exercise. Also, this use of\nsingle-byte granularity does present opportunities to save space.\nIt is unclear if 8-byte alignment of the filters would present any\nmeaningful performance benefits.\n\nModify the format document to reflect reality.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/commit-graph-format.txt | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt\nindex de56f9f1efd..1beef171822 100644\n--- a/Documentation/technical/commit-graph-format.txt\n+++ b/Documentation/technical/commit-graph-format.txt\n@@ -97,10 +97,10 @@ CHUNK DATA:\n bit on. The other bits correspond to the position of the last parent.\n \n Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]\n- * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all\n- Bloom filters from commit 0 to commit i (inclusive) in lexicographic\n- order. The Bloom filter for the i-th commit spans from BIDX[i-1] to\n- BIDX[i] (plus header length), where BIDX[-1] is 0.\n+ * The ith entry, BIDX[i], stores the number of bytes in all Bloom filters\n+ from commit 0 to commit i (inclusive) in lexicographic order. The Bloom\n+ filter for the i-th commit spans from BIDX[i-1] to BIDX[i] (plus header\n+ length), where BIDX[-1] is 0.\n * The BIDX chunk is ignored if the BDAT chunk is not present.\n \n Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]\n-- \ngitgitgadget\n\n"},{"id":"396758","messageId":"572d0508fe0364119d83c08e01a66153810958e9.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 02/12] test-bloom: fix usage typo","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:19Z","receivedAt":"2020-05-01T15:30:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nSigned-off-by: Derrick Stolee \n---\n t/helper/test-bloom.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\nindex 77eb27adac7..00c1d44a561 100644\n--- a/t/helper/test-bloom.c\n+++ b/t/helper/test-bloom.c\n@@ -44,7 +44,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n }\n \n static const char *bloom_usage = \"\\n\"\n-\" test-tool bloom get_murmer3 \\n\"\n+\" test-tool bloom get_murmur3 \\n\"\n \" test-tool bloom generate_filter [...]\\n\"\n \" test-tool get_filter_for_commit \\n\";\n \n-- \ngitgitgadget\n\n"},{"id":"396759","messageId":"07d0a25f1c438f02d71918e4ca05f2901eb802be.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 04/12] bloom: de-duplicate directory entries","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:21Z","receivedAt":"2020-05-01T15:30:39Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen computing a changed-path Bloom filter, we need to take the\nfiles that changed from the diff computation and extract the parent\ndirectories. That way, a directory pathspec such as \"Documentation\"\ncould match commits that change \"Documentation/git.txt\".\n\nHowever, the current code does a poor job of this process. The paths\nare added to a hashmap, but we do not check if an entry already\nexists with that path. This can create many duplicate entries and\ncause the filter to have a much larger length than it should. This\nmeans that the filter is more sparse than intended, which helps the\nfalse positive rate, but wastes a lot of space.\n\nProperly use hashmap_get() before hashmap_add(). Also be sure to\ninclude a comparison function so these can be matched correctly.\n\nThis has an effect on a test in t0095-bloom.sh. This makes sense,\nthere are ten changes inside \"smallDir\" so the total number of\npaths in the filter should be 11. This would result in 11 * 10 bits\nrequired, and with 8 bits per byte, this results in 14 bytes.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 35 ++++++++++++++++++++++++++---------\n t/t0095-bloom.sh | 4 ++--\n 2 files changed, 28 insertions(+), 11 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 2e3e0f5037b..eb08571c628 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -158,6 +158,19 @@ void init_bloom_filters(void)\n \tinit_bloom_filter_slab(&bloom_filters);\n }\n \n+static int pathmap_cmp(const void *hashmap_cmp_fn_data,\n+\t\t const struct hashmap_entry *eptr,\n+\t\t const struct hashmap_entry *entry_or_key,\n+\t\t const void *keydata)\n+{\n+\tconst struct pathmap_hash_entry *e1, *e2;\n+\n+\te1 = container_of(eptr, const struct pathmap_hash_entry, entry);\n+\te2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);\n+\n+\treturn strcmp(e1->path, e2->path);\n+}\n+\n struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\t\t\t struct commit *c,\n \t\t\t\t int compute_if_not_present)\n@@ -203,25 +216,29 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\tstruct hashmap pathmap;\n \t\tstruct pathmap_hash_entry *e;\n \t\tstruct hashmap_iter iter;\n-\t\thashmap_init(&pathmap, NULL, NULL, 0);\n+\t\thashmap_init(&pathmap, pathmap_cmp, NULL, 0);\n \n \t\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n \t\t\tconst char *path = diff_queued_diff.queue[i]->two->path;\n \n \t\t\t/*\n-\t\t\t* Add each leading directory of the changed file, i.e. for\n-\t\t\t* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n-\t\t\t* the Bloom filter could be used to speed up commands like\n-\t\t\t* 'git log dir/subdir', too.\n-\t\t\t*\n-\t\t\t* Note that directories are added without the trailing '/'.\n-\t\t\t*/\n+\t\t\t * Add each leading directory of the changed file, i.e. for\n+\t\t\t * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n+\t\t\t * the Bloom filter could be used to speed up commands like\n+\t\t\t * 'git log dir/subdir', too.\n+\t\t\t *\n+\t\t\t * Note that directories are added without the trailing '/'.\n+\t\t\t */\n \t\t\tdo {\n \t\t\t\tchar *last_slash = strrchr(path, '/');\n \n \t\t\t\tFLEX_ALLOC_STR(e, path, path);\n \t\t\t\thashmap_entry_init(&e->entry, strhash(path));\n-\t\t\t\thashmap_add(&pathmap, &e->entry);\n+\n+\t\t\t\tif (!hashmap_get(&pathmap, &e->entry, NULL))\n+\t\t\t\t\thashmap_add(&pathmap, &e->entry);\n+\t\t\t\telse\n+\t\t\t\t\tfree(e);\n \n \t\t\t\tif (!last_slash)\n \t\t\t\t\tlast_slash = (char*)path;\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex 8f9eef116dc..6defeb544f1 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -89,8 +89,8 @@ test_expect_success 'get bloom filter for commit with 10 changes' '\n \tgit add smallDir &&\n \tgit commit -m \"commit with 10 changes\" &&\n \tcat >expect <<-\\EOF &&\n-\tFilter_Length:25\n-\tFilter_Data:82|a0|65|47|0c|92|90|c0|a1|40|02|a0|e2|40|e0|04|0a|9a|66|cf|80|19|85|42|23|\n+\tFilter_Length:14\n+\tFilter_Data:02|b3|c4|a0|34|e7|fe|eb|cb|47|fe|a0|e8|72|\n \tEOF\n \ttest-tool bloom get_filter_for_commit \"$(git rev-parse HEAD)\" >actual &&\n \ttest_cmp expect actual\n-- \ngitgitgadget\n\n"},{"id":"396760","messageId":"ef4c08e401bd57dddf327910032220632a36885f.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 05/12] bloom: parse commit before computing filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:22Z","receivedAt":"2020-05-01T15:30:40Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen computing changed-path Bloom filters for a commit, we need to\nknow if the commit has a parent or not. If the commit is not parsed,\nthen its parent pointer will be NULL.\n\nAs far as I can tell, the only opportunity to reach this code\nwithout parsing the commit is inside \"test-tool bloom\nget_filter_for_commit\" but it is best to be safe.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/bloom.c b/bloom.c\nindex eb08571c628..c3b81b1a38a 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -206,6 +206,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \tdiffopt.max_changes = max_changes;\n \tdiff_setup_done(&diffopt);\n \n+\t/* ensure commit is parsed so we have parent information */\n+\tparse_commit(c);\n+\n \tif (c->parents)\n \t\tdiff_tree_oid(&c->parents->item->object.oid, &c->object.oid, \"\", &diffopt);\n \telse\n-- \ngitgitgadget\n\n"},{"id":"396761","messageId":"35d2901957efbb8727142ef633ae0953b613c0d1.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 07/12] completion: offer '--(no-)patch' among 'git log' options","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:24Z","receivedAt":"2020-05-01T15:30:40Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n contrib/completion/git-completion.bash | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex c21786f2fd0..ec6ff1d5fb8 100644\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -1860,6 +1860,7 @@ _git_log ()\n \t\t\t$merge\n \t\t\t$__git_diff_common_options\n \t\t\t--pickaxe-all --pickaxe-regex\n+\t\t\t--patch --no-patch\n \t\t\t\"\n \t\treturn\n \t\t;;\n-- \ngitgitgadget\n\n"},{"id":"396762","messageId":"1f326612da05dfa74ebaaee6a852d5ef92a4ed29.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 08/12] line-log: remove unused fields from 'struct line_log_data'","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:25Z","receivedAt":"2020-05-01T15:30:42Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nRemove the unused fields 'status', 'arg_alloc', 'arg_nr' and 'args'\nfrom 'struct line_log_data'. They were already part of the struct\nwhen it was introduced in commit 12da1d1f6 (Implement line-history\nsearch (git log -L), 2013-03-28), but as far as I can tell none of\nthem have ever been actually used.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n line-log.h | 3 ---\n 1 file changed, 3 deletions(-)\n\ndiff --git a/line-log.h b/line-log.h\nindex 8ee7a2bd4a1..882c5055bb8 100644\n--- a/line-log.h\n+++ b/line-log.h\n@@ -46,10 +46,7 @@ void sort_and_merge_range_set(struct range_set *);\n struct line_log_data {\n \tstruct line_log_data *next;\n \tchar *path;\n-\tchar status;\n \tstruct range_set ranges;\n-\tint arg_alloc, arg_nr;\n-\tconst char **args;\n \tstruct diff_filepair *pair;\n \tstruct diff_ranges diff;\n };\n-- \ngitgitgadget\n\n"},{"id":"396763","messageId":"7d5561575d5e81128dcccb411bf2b052491d1850.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 06/12] bloom: use num_changes not nr for limit detection","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:23Z","receivedAt":"2020-05-01T15:30:42Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs diff_tree_oid() computes a diff, it will terminate early if the\ntotal number of changed paths is strictly larger than max_changes.\nThis includes the directories that changed, not just the file paths.\nHowever, only the file paths are reflected in the resulting diff\nqueue \"nr\" value.\n\nUse the \"num_changes\" from diffopt to check if the diff terminated\nearly. This is incredibly important, as it can result in incorrect\nfilters! For example, the first commit in the Linux kernel repo\nreports only 471 changes, but since these are nested inside several\ndirectories they expand to 513 \"real\" changes, and in fact the\ntotal list of changes is not reported. Thus, the computed filter\nfor this commit is incorrect.\n\nDemonstrate the subtle difference by using one fewer file change\nin the 'get bloom filter for commit with 513 changes' test. Before,\nthis edited 513 files inside \"bigDir\" which hit this inequality.\nHowever, dropping the file count by one demonstrates how the\nprevious inequality was incorrect but the new one is correct.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 2 +-\n t/t0095-bloom.sh | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex c3b81b1a38a..9a8386ac676 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -215,7 +215,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\tdiff_tree_oid(NULL, &c->object.oid, \"\", &diffopt);\n \tdiffcore_std(&diffopt);\n \n-\tif (diff_queued_diff.nr <= max_changes) {\n+\tif (diffopt.num_changes <= max_changes) {\n \t\tstruct hashmap pathmap;\n \t\tstruct pathmap_hash_entry *e;\n \t\tstruct hashmap_iter iter;\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex 6defeb544f1..48a90625596 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -100,7 +100,7 @@ test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '\n \trm actual &&\n \trm expect &&\n \tmkdir bigDir &&\n-\tfor i in $(test_seq 0 512)\n+\tfor i in $(test_seq 0 511)\n \tdo\n \t\techo $i >bigDir/$i\n \tdone &&\n-- \ngitgitgadget\n\n"},{"id":"396764","messageId":"4e3d7233095064de197c447cb31cf4652d42b775.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 09/12] t4211-line-log: add tests for parent oids","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:26Z","receivedAt":"2020-05-01T15:30:43Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nNone of the tests in 't4211-line-log.sh' really check which parent\nobject IDs are shown in the output, either implicitly as part of\n\"Merge: ...\" lines [1] or explicitly via the '%p' or '%P' format\nspecifiers in a custom pretty format.\n\nAdd two tests to 't4211-line-log.sh' to check which parent object IDs\nare shown, one without and one with explicitly requested parent\nrewriting, IOW without and with the '--parents' option.\n\nThe test without '--parents' is marked as failing, because without\nthat option parent rewriting should not be performed, and thus the\nparent object ID should be that of the immediate parent, just like in\ncase of a pathspec-limited history traversal without parent rewriting.\nThe current line-level log implementation, however, performs parent\nrewriting unconditionally and without a possibility to turn it off,\nand, consequently, it shows the object ID of the most recent ancestor\nthat modified the given line range.\n\nIn both of these new tests we only really care about the object IDs of\nthe listed commits and their parents, but not the diffs of the line\nranges; the diffs have already been thoroughly checked in the previous\ntests.\n\n[1] While one of the tests ('-M -L ':f:b.c' parallel-change') does\n list a merge commit, both of its parents happen to modify the\n given line range and are listed as well, so the implications of\n parent rewriting remained hidden and untested.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n t/t4211-line-log.sh | 68 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 68 insertions(+)\n\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex cda58186c2d..ea4a9398365 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -215,4 +215,72 @@ test_expect_success 'fancy rename following #2' '\n \ttest_cmp expect actual\n '\n \n+# Create the following linear history, where each commit does what its\n+# subject line promises:\n+#\n+# * 66c6410 Modify func2() in file.c\n+# * 50834e5 Modify other-file\n+# * fe5851c Modify func1() in file.c\n+# * 8c7c7dd Add other-file\n+# * d5f4417 Add func1() and func2() in file.c\n+test_expect_success 'setup for checking line-log and parent oids' '\n+\tgit checkout --orphan parent-oids &&\n+\tgit reset --hard &&\n+\n+\tcat >file.c <<-\\EOF &&\n+\tint func1()\n+\t{\n+\t return F1;\n+\t}\n+\n+\tint func2()\n+\t{\n+\t return F2;\n+\t}\n+\tEOF\n+\tgit add file.c &&\n+\ttest_tick &&\n+\tgit commit -m \"Add func1() and func2() in file.c\" &&\n+\n+\techo 1 >other-file &&\n+\tgit add other-file &&\n+\tgit commit -m \"Add other-file\" &&\n+\n+\tsed -e \"s/F1/F1 + 1/\" file.c >tmp &&\n+\tmv tmp file.c &&\n+\tgit commit -a -m \"Modify func1() in file.c\" &&\n+\n+\techo 2 >other-file &&\n+\tgit commit -a -m \"Modify other-file\" &&\n+\n+\tsed -e \"s/F2/F2 + 2/\" file.c >tmp &&\n+\tmv tmp file.c &&\n+\tgit commit -a -m \"Modify func2() in file.c\" &&\n+\n+\thead_oid=$(git rev-parse --short HEAD) &&\n+\tprev_oid=$(git rev-parse --short HEAD^) &&\n+\troot_oid=$(git rev-parse --short HEAD~4)\n+'\n+\n+# Parent oid should be from immediate parent.\n+test_expect_failure 'parent oids without parent rewriting' '\n+\tcat >expect <<-EOF &&\n+\t$head_oid $prev_oid Modify func2() in file.c\n+\t$root_oid Add func1() and func2() in file.c\n+\tEOF\n+\tgit log --format=\"%h %p %s\" --no-patch -L:func2:file.c >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+# Parent oid should be from the most recent ancestor touching func2(),\n+# i.e. in this case from the root commit.\n+test_expect_success 'parent oids with parent rewriting' '\n+\tcat >expect <<-EOF &&\n+\t$head_oid $root_oid Modify func2() in file.c\n+\t$root_oid Add func1() and func2() in file.c\n+\tEOF\n+\tgit log --format=\"%h %p %s\" --no-patch -L:func2:file.c --parents >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"396765","messageId":"3abc713092456b7c34ac72c0064b0b5c51ac726f.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 11/12] line-log: try to use generation number-based topo-ordering","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:28Z","receivedAt":"2020-05-01T15:30:48Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nThe previous patch made it possible to perform line-level filtering\nduring history traversal instead of in an expensive preprocessing\nstep, but it still requires some simpler preprocessing steps, notably\ntopo-ordering. However, nowadays we have commit-graphs storing\ngeneration numbers, which make it possible to incrementally traverse\nthe history in topological order, without the preparatory limit_list()\nand sort_in_topological_order() steps; see b45424181e (revision.c:\ngeneration-based topo-order algorithm, 2018-11-01).\n\nThis patch combines the two, so we can do both the topo-ordering and\nthe line-level filtering during history traversal, eliminating even\nthose simpler preprocessing steps, and thus further reducing the delay\nbefore showing the first commit modifying the given line range.\n\nThe 'revs->limited' flag plays the central role in this, because, due\nto limitations of the current implementation, the generation\nnumber-based topo-ordering is only enabled when this flag remains\nunset. Line-level log, however, always sets this flag in\nsetup_revisions() ever since the feature was introduced in 12da1d1f6f\n(Implement line-history search (git log -L), 2013-03-28). The reason\nfor setting 'limited' is unclear, though, because the line-level log\nitself doesn't directly depend on it, and it doesn't affect how the\nlimit_list() function limits the revision range. However, there is an\nindirect dependency: the line-level log requires topo-ordering, and\nthe \"traditional\" sort_in_topological_order() requires an already\nlimited commit list since e6c3505b44 (Make sure we generate the whole\ncommit list before trying to sort it topologically, 2005-07-06). The\nnew, generation numbers-based topo-ordering doesn't require a limited\ncommit list anymore.\n\nSo don't set 'revs->limited' for line-level log, unless it is really\nnecessary, namely:\n\n - The user explicitly requested parent rewriting, because that is\n still done in the line_log_filter() preprocessing step (see\n previous patch), which requires sort_in_topological_order() and in\n turn limit_list() as well.\n\n - A commit-graph file is not available or it doesn't yet contain\n generation numbers. In these cases we had to fall back on\n sort_in_topological_order() and in turn limit_list(). The\n existing condition with generation_numbers_enabled() has already\n ensured that the 'limited' flag is set in these cases; this patch\n just makes sure that the line-level log sets 'revs->topo_order'\n before that condition.\n\nWhile the reduced delay before showing the first commit is measurable\nin git.git, it takes a bigger repository to make it clearly noticable.\nIn both cases below the line ranges were chosen so that they were\nmodified rather close to the starting revisions, so the effect of this\nchange is most noticable.\n\n # git.git\n $ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0\n\n Before:\n\n real 0m0.107s\n user 0m0.091s\n sys 0m0.013s\n\n After:\n\n real 0m0.058s\n user 0m0.050s\n sys 0m0.005s\n\n # linux.git\n $ time git --no-pager log \\\n -L:build_restore_work_registers:arch/mips/mm/tlbex.c -1 v5.2\n\n Before:\n\n real 0m1.129s\n user 0m1.061s\n sys 0m0.069s\n\n After:\n\n real 0m0.096s\n user 0m0.087s\n sys 0m0.009s\n\nAdditional testing by Derrick Stolee: Since this patch improves\nthe performance for the first result, I repeated the experiment\nfrom the previous patch on the Linux kernel repository:\n\n Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 0.71 s\n After: 0.05 s\n\nNow, we have dropped the full topo-order of all ~910,000 commits\nbefore reporting the first result. The remaining performance\nimprovements then are:\n\n 1. Update the parent-rewriting logic to be incremental similar to\n how \"git log --graph\" behaves.\n\n 2. Use changed-path Bloom filters to reduce the time spend in the\n tree-diff to see if the path(s) changed.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n revision.c | 11 ++++++-----\n 1 file changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 3228db9af6d..3356ede9a20 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2790,6 +2790,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \tif (revs->diffopt.objfind)\n \t\trevs->simplify_history = 0;\n \n+\tif (revs->line_level_traverse) {\n+\t\tif (want_ancestry(revs))\n+\t\t\trevs->limited = 1;\n+\t\trevs->topo_order = 1;\n+\t}\n+\n \tif (revs->topo_order && !generation_numbers_enabled(the_repository))\n \t\trevs->limited = 1;\n \n@@ -2809,11 +2815,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \n \trevs->diffopt.abbrev = revs->abbrev;\n \n-\tif (revs->line_level_traverse) {\n-\t\trevs->limited = 1;\n-\t\trevs->topo_order = 1;\n-\t}\n-\n \tdiff_setup_done(&revs->diffopt);\n \n \tgrep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,\n-- \ngitgitgadget\n\n"},{"id":"396766","messageId":"d9991d6158df6af0e62b8739591dd726d3479324.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 10/12] line-log: more responsive, incremental 'git log -L'","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:27Z","receivedAt":"2020-05-01T15:30:49Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nThe current line-level log implementation performs a preprocessing\nstep in prepare_revision_walk(), during which the line_log_filter()\nfunction filters and rewrites history to keep only commits modifying\nthe given line range. This preprocessing affects both responsiveness\nand correctness:\n\n - Git doesn't produce any output during this preprocessing step.\n Checking whether a commit modified the given line range is\n somewhat expensive, so depending on the size of the given revision\n range this preprocessing can result in a significant delay before\n the first commit is shown.\n\n - Limiting the number of displayed commits (e.g. 'git log -3 -L...')\n doesn't limit the amount of work during preprocessing, because\n that limit is applied during history traversal. Alas, by that\n point this expensive preprocessing step has already churned\n through the whole revision range to find all commits modifying the\n revision range, even though only a few of them need to be shown.\n\n - It rewrites parents, with no way to turn it off. Without the user\n explicitly requesting parent rewriting any parent object ID shown\n should be that of the immediate parent, just like in case of a\n pathspec-limited history traversal without parent rewriting.\n\n However, after that preprocessing step rewrote history, the\n subsequent \"regular\" history traversal (i.e. get_revision() in a\n loop) only sees commits modifying the given line range.\n Consequently, it can only show the object ID of the last ancestor\n that modified the given line range (which might happen to be the\n immediate parent, but many-many times it isn't).\n\nThis patch addresses both the correctness and, at least for the common\ncase, the responsiveness issues by integrating line-level log\nfiltering into the regular revision walking machinery:\n\n - Make process_ranges_arbitrary_commit(), the static function in\n 'line-log.c' deciding whether a commit modifies the given line\n range, public by removing the static keyword and adding the\n 'line_log_' prefix, so it can be called from other parts of the\n revision walking machinery.\n\n - If the user didn't explicitly ask for parent rewriting (which, I\n believe, is the most common case):\n\n - Call this now-public function during regular history traversal,\n namely from get_commit_action() to ignore any commits not\n modifying the given line range.\n\n Note that while this check is relatively expensive, it must be\n performed before other, much cheaper conditions, because the\n tracked line range must be adjusted even when the commit will\n end up being ignored by other conditions.\n\n - Skip the line_log_filter() call, i.e. the expensive\n preprocessing step, in prepare_revision_walk(), because, thanks\n to the above points, the revision walking machinery is now able\n to filter out commits not modifying the given line range while\n traversing history.\n\n This way the regular history traversal sees the unmodified\n history, and is therefore able to print the object ids of the\n immediate parents of the listed commits. The eliminated\n preprocessing step can greatly reduce the delay before the first\n commit is shown, see the numbers below.\n\n - However, if the user did explicitly ask for parent rewriting via\n '--parents' or a similar option, then stick with the current\n implementation for now, i.e. perform that expensive filtering and\n history rewriting in the preprocessing step just like we did\n before, leaving the initial delay as long as it was.\n\nI tried to integrate line-level log filtering with parent rewriting\ninto the regular history traversal, but, unfortunately, several\nsubtleties resisted... :) Maybe someday we'll figure out how to do\nthat, but until then at least the simple and common (i.e. without\nparent rewriting) 'git log -L:func:file' commands can benefit from the\nreduced delay.\n\nThis change makes the failing 'parent oids without parent rewriting'\ntest in 't4211-line-log.sh' succeed.\n\nThe reduced delay is most noticable when there's a commit modifying\nthe line range near the tip of a large-ish revision range:\n\n # no parent rewriting requested, no commit-graph present\n $ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0\n\n Before:\n\n real 0m9.570s\n user 0m9.494s\n sys 0m0.076s\n\n After:\n\n real 0m0.718s\n user 0m0.674s\n sys 0m0.044s\n\nA significant part of the remaining delay is spent reading and parsing\ncommit objects in limit_list(). With the help of the commit-graph we\ncan eliminate most of that reading and parsing overhead, so here are\nthe timing results of the same command as above, but this time using\nthe commit-graph:\n\n Before:\n\n real 0m8.874s\n user 0m8.816s\n sys 0m0.057s\n\n After:\n\n real 0m0.107s\n user 0m0.091s\n sys 0m0.013s\n\nThe next patch will further reduce the remaining delay.\n\nTo be clear: this patch doesn't actually optimize the line-level log,\nbut merely moves most of the work from the preprocessing step to the\nhistory travelsal, so the commits modifying the line range can be\nshown as soon as they are processed, and the traversal can be\nterminated as soon as the given number of commits are shown.\nConsequently, listing the full history of a line range, potentially\nall the way to the root commit, will take the same time as before (but\nat least the user might start reading the output earlier).\nFurthermore, if the most recent commit modifying the line range is far\naway from the starting revision, then that initial delay will still be\nsignificant.\n\nAdditional testing by Derrick Stolee: In the Linux kernel repository,\nthe MAINTAINERS file was changed ~3,500 times across the ~915,000\ncommits. In addition to that edit frequency, the file itself is quite\nlarge (~18,700 lines). This means that a significant portion of the\ncomputation is taken up by computing the patch-diff of the file. This\npatch improves the time it takes to output the first result quite a\nbit:\n\nCommand: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 3.88 s\n After: 0.71 s\n\nIf we drop the \"-n 1\" in the command, then there is no change in\nend-to-end process time. This is because the command still needs to\nwalk the entire commit history, which negates the point of this\npatch. This is expected.\n\nAs a note for future reference, the ~4.3 seconds in the old code\nspends ~2.6 seconds computing the patch-diffs, and the rest of the\ntime is spent walking commits and computing diffs for which paths\nchanged at each commit. The changed-path Bloom filters could improve\nthe end-to-end computation time (i.e. no \"-n 1\" in the command).\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n line-log.c | 4 ++--\n line-log.h | 2 ++\n revision.c | 27 ++++++++++++++++++++++++++-\n t/t4211-line-log.sh | 2 +-\n 4 files changed, 31 insertions(+), 4 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 9010e00950b..520ee715bcd 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -1227,7 +1227,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n \t/* NEEDSWORK leaking like a sieve */\n }\n \n-static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n+int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n {\n \tstruct line_log_data *range = lookup_line_range(rev, commit);\n \tint changed = 0;\n@@ -1270,7 +1270,7 @@ int line_log_filter(struct rev_info *rev)\n \twhile (list) {\n \t\tstruct commit_list *to_free = NULL;\n \t\tcommit = list->item;\n-\t\tif (process_ranges_arbitrary_commit(rev, commit)) {\n+\t\tif (line_log_process_ranges_arbitrary_commit(rev, commit)) {\n \t\t\t*pp = list;\n \t\t\tpp = &list->next;\n \t\t} else\ndiff --git a/line-log.h b/line-log.h\nindex 882c5055bb8..82ae8d98a40 100644\n--- a/line-log.h\n+++ b/line-log.h\n@@ -54,6 +54,8 @@ struct line_log_data {\n void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args);\n \n int line_log_filter(struct rev_info *rev);\n+int line_log_process_ranges_arbitrary_commit(struct rev_info *rev,\n+\t\t\t\t\t\t struct commit *commit);\n \n int line_log_print(struct rev_info *rev, struct commit *commit);\n \ndiff --git a/revision.c b/revision.c\nindex f78c636e4d0..3228db9af6d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -39,6 +39,8 @@ static const char *term_good;\n \n implement_shared_commit_slab(revision_sources, char *);\n \n+static inline int want_ancestry(const struct rev_info *revs);\n+\n void show_object_with_name(FILE *out, struct object *obj, const char *name)\n {\n \tconst char *p;\n@@ -3511,7 +3513,14 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \t} else if (revs->topo_order)\n \t\tinit_topo_walk(revs);\n-\tif (revs->line_level_traverse)\n+\tif (revs->line_level_traverse && want_ancestry(revs))\n+\t\t/*\n+\t\t * At the moment we can only do line-level log with parent\n+\t\t * rewriting by performing this expensive pre-filtering step.\n+\t\t * If parent rewriting is not requested, then we rather\n+\t\t * perform the line-level log filtering during the regular\n+\t\t * history traversal.\n+\t\t */\n \t\tline_log_filter(revs);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n@@ -3722,6 +3731,22 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi\n \t\treturn commit_ignore;\n \tif (commit->object.flags & UNINTERESTING)\n \t\treturn commit_ignore;\n+\tif (revs->line_level_traverse && !want_ancestry(revs)) {\n+\t\t/*\n+\t\t * In case of line-level log with parent rewriting\n+\t\t * prepare_revision_walk() already took care of all line-level\n+\t\t * log filtering, and there is nothing left to do here.\n+\t\t *\n+\t\t * If parent rewriting was not requested, then this is the\n+\t\t * place to perform the line-level log filtering. Notably,\n+\t\t * this check, though expensive, must come before the other,\n+\t\t * cheaper filtering conditions, because the tracked line\n+\t\t * ranges must be adjusted even when the commit will end up\n+\t\t * being ignored based on other conditions.\n+\t\t */\n+\t\tif (!line_log_process_ranges_arbitrary_commit(revs, commit))\n+\t\t\treturn commit_ignore;\n+\t}\n \tif (revs->min_age != -1 &&\n \t comparison_date(revs, commit) > revs->min_age)\n \t\t\treturn commit_ignore;\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex ea4a9398365..1428eae2629 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -263,7 +263,7 @@ test_expect_success 'setup for checking line-log and parent oids' '\n '\n \n # Parent oid should be from immediate parent.\n-test_expect_failure 'parent oids without parent rewriting' '\n+test_expect_success 'parent oids without parent rewriting' '\n \tcat >expect <<-EOF &&\n \t$head_oid $prev_oid Modify func2() in file.c\n \t$root_oid Add func1() and func2() in file.c\n-- \ngitgitgadget\n\n"},{"id":"396767","messageId":"7e0c2871cf73dead655626442cc191d13b7bd94b.1588347029.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH 12/12] line-log: integrate with changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-01T15:30:29Z","receivedAt":"2020-05-01T15:30:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous changes to the line-log machinery focused on making the\nfirst result appear faster. This was achieved by no longer walking the\nentire commit history before returning the early results. There is still\nanother way to improve the performance: walk most commits much faster.\nLet's use the changed-path Bloom filters to reduce time spent computing\ndiffs.\n\nSince the line-log computation requires opening blobs and checking the\ncontent-diff, there is still a lot of necessary computation that cannot\nbe replaced with changed-path Bloom filters. The part that we can reduce\nis most effective when checking the history of a file that is deep in\nseveral directories and those directories are modified frequently. In\nthis case, the computation to check if a commit is TREESAME to its first\nparent takes a large fraction of the time. That is ripe for improvement\nwith changed-path Bloom filters.\n\nWe must ensure that prepare_to_use_bloom_filters() is called in\nrevision.c so that the bloom_filter_settings are loaded into the struct\nrev_info from the commit-graph. Of course, some cases are still\nforbidden, but in the line-log case the pathspec is provided in a\ndifferent way than normal.\n\nSince multiple paths and segments could be requested, we compute the\nstruct bloom_key data dynamically during the commit walk. This could\nlikely be improved, but adds code complexity that is not valuable at\nthis time.\n\nThere are two cases to care about: merge commits and \"ordinary\" commits.\nMerge commits have multiple parents, but if we are TREESAME to our first\nparent in every range, then pass the blame for all ranges to the first\nparent. Ordinary commits have the same condition, but each is done\nslightly differently in the process_ranges_[merge|ordinary]_commit()\nmethods. By checking if the changed-path Bloom filter can guarantee\nTREESAME, we can avoid that tree-diff cost. If the filter says \"probably\nchanged\", then we need to run the tree-diff and then the blob-diff if\nthere was a real edit.\n\nThe Linux kernel repository is a good testing ground for the performance\nimprovements claimed here. There are two different cases to test. The\nfirst is the \"entire history\" case, where we output the entire history\nto /dev/null to see how long it would take to compute the full line-log\nhistory. The second is the \"first result\" case, where we find how long\nit takes to show the first value, which is an indicator of how quickly a\nuser would see responses when waiting at a terminal.\n\nTo test, I selected the paths that were changed most frequently in the\ntop 10,000 commits using this command (stolen from StackOverflow [1]):\n\n\tgit log --pretty=format: --name-only -n 10000 | sort | \\\n\t\tuniq -c | sort -rg | head -10\n\nwhich results in\n\n 121 MAINTAINERS\n 63 fs/namei.c\n 60 arch/x86/kvm/cpuid.c\n 59 fs/io_uring.c\n 58 arch/x86/kvm/vmx/vmx.c\n 51 arch/x86/kvm/x86.c\n 45 arch/x86/kvm/svm.c\n 42 fs/btrfs/disk-io.c\n 42 Documentation/scsi/index.rst\n\n(along with a bogus first result). It appears that the path\narch/x86/kvm/svm.c was renamed, so we ignore that entry. This leaves the\nfollowing results:\n\n| | Entire History | First Result |\n| Path | Before | After | Before | After |\n|------------------------------|--------|--------|--------|--------|\n| MAINTAINERS | 4.26 s | 3.87 s | 0.41 s | 0.39 s |\n| fs/namei.c | 1.99 s | 0.99 s | 0.42 s | 0.21 s |\n| arch/x86/kvm/cpuid.c | 5.28 s | 1.12 s | 0.16 s | 0.09 s |\n| fs/io_uring.c | 4.34 s | 0.99 s | 0.94 s | 0.27 s |\n| arch/x86/kvm/vmx/vmx.c | 5.01 s | 1.34 s | 0.21 s | 0.12 s |\n| arch/x86/kvm/x86.c | 2.24 s | 1.18 s | 0.21 s | 0.14 s |\n| fs/btrfs/disk-io.c | 1.82 s | 1.01 s | 0.06 s | 0.05 s |\n| Documentation/scsi/index.rst | 3.30 s | 0.89 s | 1.46 s | 0.03 s |\n\nIt is worth noting that the least speedup comes for the MAINTAINERS file\nwhich is\n\n * edited frequently,\n * low in the directory heirarchy, and\n * quite a large file.\n\nAll of those points lead to spending more time doing the blob diff and\nless time doing the tree diff. Still, we see some improvement in that\ncase and significant improvement in other cases. A 2-4x speedup is\nlikely the more typical case as opposed to the small 5% change for that\nfile.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 5 +++++\n bloom.h | 1 +\n line-log.c | 39 ++++++++++++++++++++++++++++++++++++++-\n revision.c | 5 ++++-\n 4 files changed, 48 insertions(+), 2 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 9a8386ac676..e22c0108f39 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -138,6 +138,11 @@ void fill_bloom_key(const char *data,\n \t\tkey->hashes[i] = hash0 + i * hash1;\n }\n \n+void clear_bloom_key(struct bloom_key *key)\n+{\n+\tFREE_AND_NULL(key->hashes);\n+}\n+\n void add_key_to_filter(const struct bloom_key *key,\n \t\t struct bloom_filter *filter,\n \t\t const struct bloom_filter_settings *settings)\ndiff --git a/bloom.h b/bloom.h\nindex a51e3715296..d0c69172e67 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -72,6 +72,7 @@ void fill_bloom_key(const char *data,\n \t\t size_t len,\n \t\t struct bloom_key *key,\n \t\t const struct bloom_filter_settings *settings);\n+void clear_bloom_key(struct bloom_key *key);\n \n void add_key_to_filter(const struct bloom_key *key,\n \t\t struct bloom_filter *filter,\ndiff --git a/line-log.c b/line-log.c\nindex 520ee715bcd..7dc411da8f6 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -15,6 +15,7 @@\n #include \"userdiff.h\"\n #include \"line-log.h\"\n #include \"argv-array.h\"\n+#include \"bloom.h\"\n \n static void range_set_grow(struct range_set *rs, size_t extra)\n {\n@@ -1146,6 +1147,37 @@ int line_log_print(struct rev_info *rev, struct commit *commit)\n \treturn 1;\n }\n \n+static int bloom_filter_check(struct rev_info *rev,\n+\t\t\t struct commit *commit,\n+\t\t\t struct line_log_data *range)\n+{\n+\tstruct bloom_filter *filter;\n+\tstruct bloom_key key;\n+\tint result = 0;\n+\n+\tif (!commit->parents)\n+\t\treturn 1;\n+\n+\tif (!rev->bloom_filter_settings ||\n+\t !(filter = get_bloom_filter(rev->repo, commit, 0)))\n+\t\treturn 1;\n+\n+\tif (!range)\n+\t\treturn 0;\n+\n+\twhile (!result && range) {\n+\t\tfill_bloom_key(range->path, strlen(range->path), &key, rev->bloom_filter_settings);\n+\n+\t\tif (bloom_filter_contains(filter, &key, rev->bloom_filter_settings))\n+\t\t\tresult = 1;\n+\n+\t\tclear_bloom_key(&key);\n+\t\trange = range->next;\n+\t}\n+\n+\treturn result;\n+}\n+\n static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,\n \t\t\t\t\t struct line_log_data *range)\n {\n@@ -1159,6 +1191,7 @@ static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *c\n \n \tqueue_diffs(range, &rev->diffopt, &queue, commit, parent);\n \tchanged = process_all_files(&parent_range, rev, &queue, range);\n+\n \tif (parent)\n \t\tadd_line_range(rev, parent, parent_range);\n \tfree_line_log_data(parent_range);\n@@ -1233,7 +1266,11 @@ int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit\n \tint changed = 0;\n \n \tif (range) {\n-\t\tif (!commit->parents || !commit->parents->next)\n+\t\tif (commit->parents && !bloom_filter_check(rev, commit, range)) {\n+\t\t\tstruct line_log_data *prange = line_log_data_copy(range);\n+\t\t\tadd_line_range(rev, commit->parents->item, prange);\n+\t\t\tclear_commit_line_range(rev, commit);\n+\t\t} else if (!commit->parents || !commit->parents->next)\n \t\t\tchanged = process_ranges_ordinary_commit(rev, commit, range);\n \t\telse\n \t\t\tchanged = process_ranges_merge_commit(rev, commit, range);\ndiff --git a/revision.c b/revision.c\nindex 3356ede9a20..cbf4b61aa67 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -689,6 +689,9 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n \tif (!revs->bloom_filter_settings)\n \t\treturn;\n \n+\tif (!revs->pruning.pathspec.nr)\n+\t\treturn;\n+\n \tpi = &revs->pruning.pathspec.items[0];\n \tlast_index = pi->len - 1;\n \n@@ -3501,7 +3504,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\t\t FOR_EACH_OBJECT_PROMISOR_ONLY);\n \t}\n \n-\tif (revs->pruning.pathspec.nr == 1 && !revs->reflog_info)\n+\tif (!revs->reflog_info)\n \t\tprepare_to_use_bloom_filter(revs);\n \tif (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)\n \t\tcommit_list_sort_by_date(&revs->commits);\n-- \ngitgitgadget\n"},{"id":"396774","messageId":"xmqqzharmudl.fsf@gitster.c.googlers.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"Re: [PATCH 00/12] Integrating line-log and changed-path Bloom filters","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-05-01T17:34:46Z","receivedAt":"2020-05-01T17:34:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> This series is organized as follows:\n>\n> * Patches 1-4 are minor Bloom filter cleanups, including a documentation\n> bug.\n> \n> \n> * Patch 5 fixes a problem where the Bloom filters use much larger filters\n> than expected.\n> \n> \n> * Patch 6 fixes a bug related to the short-circuit of large diffs from\n> e369698016 (diff: halt tree-diff early after max_changes, 2020-03-30).\n> The condition for halting the diff computation is different than the\n> check in bloom.c to see if that short-circuit was hit, which leads to\n> some commits with large diffs getting an incomplete Bloom filter. This\n> happened on the root commit of the Linux kernel repo, for example.\n> ... \n> I organized these patches so patches 1-6 could be split into its own topic,\n> if beneficial to take earlier than the line-log changes.\n\nNice.\n\n> The end result of this combined effort is the following: git log -L commands\n> feel much more responsive to a terminal user because Szeder's changes make\n> the computation incremental, and they have better end-to-end performance\n> because of the integration with Bloom filters to reduce time spent running\n> tree diffs for TREESAME commits.\n\nNice, again.\n\n"},{"id":"396800","messageId":"20200501225111.GI41612@syl.local","threadId":"53367","inReplyTo":"89625b0efae43c8cb0d444a843d389d6cb9f6772.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 01/12] bloom: fix whitespace around tab length","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T22:51:11Z","receivedAt":"2020-05-01T22:51:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:18PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> Fix alignment issues that were likely introduced due to an editor\n> using tab lengths of 4 instead of 8.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n\nAll looks good, thanks.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396801","messageId":"20200501225123.GJ41612@syl.local","threadId":"53367","inReplyTo":"572d0508fe0364119d83c08e01a66153810958e9.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 02/12] test-bloom: fix usage typo","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T22:51:23Z","receivedAt":"2020-05-01T22:51:27Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:19PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> Signed-off-by: Derrick Stolee \n> ---\n> t/helper/test-bloom.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\n> index 77eb27adac7..00c1d44a561 100644\n> --- a/t/helper/test-bloom.c\n> +++ b/t/helper/test-bloom.c\n> @@ -44,7 +44,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n> }\n>\n> static const char *bloom_usage = \"\\n\"\n> -\" test-tool bloom get_murmer3 \\n\"\n> +\" test-tool bloom get_murmur3 \\n\"\n\nI stared at this change for _far_ longer than I'm willing to admit\ntrying to find the difference between these lines. Looks good, though.\n\n> \" test-tool bloom generate_filter [...]\\n\"\n> \" test-tool get_filter_for_commit \\n\";\n>\n> --\n> gitgitgadget\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396802","messageId":"20200501225500.GA46146@syl.local","threadId":"53367","inReplyTo":"03b2c84db36754b321dd15cd8a9e1a22b7c11c36.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 03/12] Documentation: changed-path Bloom filters use byte words","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T22:55:00Z","receivedAt":"2020-05-01T22:55:04Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:20PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> In Documentation/technical/commit-graph-format.txt, the definition\n> of the BIDX chunk specifies the length is a number of 8-byte words.\n> During development we discovered that using 8-byte words in the\n> Murmur3 hash algorithm causes issues with Big-Endian versus Little-\n> Endian machines. Thus, the hash algorithm was adapted to work on a\n\nI'm nit-picking here, but I believe that \"Little Endian\" is usually\nspelled \"little endian\", right?\n\nAt least, 'git log --oneline -Gendian | wc -l' doesn't return many/any\nresults for me, but '-GEndian' does.\n\n> byte-by-byte basis. However, this caused a change in the definition\n> of a \"word\" in bloom.h. Now, a \"word\" is a single byte, which allows\n> filters to be as small as two bytes. These length-two filters are\n> demonstrated in t0095-bloom.sh, and a larger filter of length 25 is\n> demonstrated as well.\n>\n> The original point of using 8-byte words was for alignment reasons.\n> It also presented opportunities for extremely sparse Bloom filters\n> when there were a small number of changes at a commit, creating a\n> very low false-positive rate. However, modifying the format at this\n> point is unlikely to be a valuable exercise. Also, this use of\n> single-byte granularity does present opportunities to save space.\n> It is unclear if 8-byte alignment of the filters would present any\n> meaningful performance benefits.\n>\n> Modify the format document to reflect reality.\n>\n> Signed-off-by: Derrick Stolee \n\nThe rest of this patch looks good, and indeed matches reality ;).\n\n Reviewed-by: Taylor Blau \n\n> ---\n> Documentation/technical/commit-graph-format.txt | 8 ++++----\n> 1 file changed, 4 insertions(+), 4 deletions(-)\n>\n> diff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt\n> index de56f9f1efd..1beef171822 100644\n> --- a/Documentation/technical/commit-graph-format.txt\n> +++ b/Documentation/technical/commit-graph-format.txt\n> @@ -97,10 +97,10 @@ CHUNK DATA:\n> bit on. The other bits correspond to the position of the last parent.\n>\n> Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]\n> - * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all\n> - Bloom filters from commit 0 to commit i (inclusive) in lexicographic\n> - order. The Bloom filter for the i-th commit spans from BIDX[i-1] to\n> - BIDX[i] (plus header length), where BIDX[-1] is 0.\n> + * The ith entry, BIDX[i], stores the number of bytes in all Bloom filters\n> + from commit 0 to commit i (inclusive) in lexicographic order. The Bloom\n> + filter for the i-th commit spans from BIDX[i-1] to BIDX[i] (plus header\n> + length), where BIDX[-1] is 0.\n> * The BIDX chunk is ignored if the BDAT chunk is not present.\n>\n> Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]\n> --\n> gitgitgadget\n\nThanks,\nTaylor\n"},{"id":"396803","messageId":"20200501230631.GA46422@syl.local","threadId":"53367","inReplyTo":"07d0a25f1c438f02d71918e4ca05f2901eb802be.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 04/12] bloom: de-duplicate directory entries","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T23:06:31Z","receivedAt":"2020-05-01T23:06:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:21PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> When computing a changed-path Bloom filter, we need to take the\n> files that changed from the diff computation and extract the parent\n> directories. That way, a directory pathspec such as \"Documentation\"\n> could match commits that change \"Documentation/git.txt\".\n>\n> However, the current code does a poor job of this process. The paths\n> are added to a hashmap, but we do not check if an entry already\n> exists with that path. This can create many duplicate entries and\n> cause the filter to have a much larger length than it should. This\n> means that the filter is more sparse than intended, which helps the\n> false positive rate, but wastes a lot of space.\n>\n> Properly use hashmap_get() before hashmap_add(). Also be sure to\n> include a comparison function so these can be matched correctly.\n>\n> This has an effect on a test in t0095-bloom.sh. This makes sense,\n> there are ten changes inside \"smallDir\" so the total number of\n> paths in the filter should be 11. This would result in 11 * 10 bits\n> required, and with 8 bits per byte, this results in 14 bytes.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> bloom.c | 35 ++++++++++++++++++++++++++---------\n> t/t0095-bloom.sh | 4 ++--\n> 2 files changed, 28 insertions(+), 11 deletions(-)\n>\n> diff --git a/bloom.c b/bloom.c\n> index 2e3e0f5037b..eb08571c628 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -158,6 +158,19 @@ void init_bloom_filters(void)\n> \tinit_bloom_filter_slab(&bloom_filters);\n> }\n>\n> +static int pathmap_cmp(const void *hashmap_cmp_fn_data,\n> +\t\t const struct hashmap_entry *eptr,\n> +\t\t const struct hashmap_entry *entry_or_key,\n> +\t\t const void *keydata)\n> +{\n> +\tconst struct pathmap_hash_entry *e1, *e2;\n> +\n> +\te1 = container_of(eptr, const struct pathmap_hash_entry, entry);\n> +\te2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);\n> +\n> +\treturn strcmp(e1->path, e2->path);\n> +}\n> +\n> struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\t\t\t struct commit *c,\n> \t\t\t\t int compute_if_not_present)\n> @@ -203,25 +216,29 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\tstruct hashmap pathmap;\n> \t\tstruct pathmap_hash_entry *e;\n> \t\tstruct hashmap_iter iter;\n> -\t\thashmap_init(&pathmap, NULL, NULL, 0);\n> +\t\thashmap_init(&pathmap, pathmap_cmp, NULL, 0);\n>\n> \t\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n> \t\t\tconst char *path = diff_queued_diff.queue[i]->two->path;\n>\n> \t\t\t/*\n> -\t\t\t* Add each leading directory of the changed file, i.e. for\n> -\t\t\t* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n> -\t\t\t* the Bloom filter could be used to speed up commands like\n> -\t\t\t* 'git log dir/subdir', too.\n> -\t\t\t*\n> -\t\t\t* Note that directories are added without the trailing '/'.\n> -\t\t\t*/\n> +\t\t\t * Add each leading directory of the changed file, i.e. for\n> +\t\t\t * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n> +\t\t\t * the Bloom filter could be used to speed up commands like\n> +\t\t\t * 'git log dir/subdir', too.\n> +\t\t\t *\n> +\t\t\t * Note that directories are added without the trailing '/'.\n> +\t\t\t */\n> \t\t\tdo {\n> \t\t\t\tchar *last_slash = strrchr(path, '/');\n>\n> \t\t\t\tFLEX_ALLOC_STR(e, path, path);\n> \t\t\t\thashmap_entry_init(&e->entry, strhash(path));\n> -\t\t\t\thashmap_add(&pathmap, &e->entry);\n> +\n> +\t\t\t\tif (!hashmap_get(&pathmap, &e->entry, NULL))\n> +\t\t\t\t\thashmap_add(&pathmap, &e->entry);\n> +\t\t\t\telse\n> +\t\t\t\t\tfree(e);\n\nYep; this seems right on: if we have a match in the hashmap already,\nthere's no need to add another one. In fact, it's much better not to, as\nyou point out.\n\nIn the case that we didn't need to add one, we can free up the\ncorresponding resources (I had to double-check that 'free()' would\nappropriately discard the flex array, but that's fine).\n\nNice find!\n\n> \t\t\t\tif (!last_slash)\n> \t\t\t\t\tlast_slash = (char*)path;\n> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> index 8f9eef116dc..6defeb544f1 100755\n> --- a/t/t0095-bloom.sh\n> +++ b/t/t0095-bloom.sh\n> @@ -89,8 +89,8 @@ test_expect_success 'get bloom filter for commit with 10 changes' '\n> \tgit add smallDir &&\n> \tgit commit -m \"commit with 10 changes\" &&\n> \tcat >expect <<-\\EOF &&\n> -\tFilter_Length:25\n> -\tFilter_Data:82|a0|65|47|0c|92|90|c0|a1|40|02|a0|e2|40|e0|04|0a|9a|66|cf|80|19|85|42|23|\n> +\tFilter_Length:14\n> +\tFilter_Data:02|b3|c4|a0|34|e7|fe|eb|cb|47|fe|a0|e8|72|\n> \tEOF\n> \ttest-tool bloom get_filter_for_commit \"$(git rev-parse HEAD)\" >actual &&\n> \ttest_cmp expect actual\n> --\n> gitgitgadget\n\nMakes sense, I figured that there'd be a little bit of test-fallout\nhere.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396804","messageId":"20200501231042.GB46422@syl.local","threadId":"53367","inReplyTo":"ef4c08e401bd57dddf327910032220632a36885f.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 05/12] bloom: parse commit before computing filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T23:10:42Z","receivedAt":"2020-05-01T23:10:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:22PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> When computing changed-path Bloom filters for a commit, we need to\n> know if the commit has a parent or not. If the commit is not parsed,\n> then its parent pointer will be NULL.\n>\n> As far as I can tell, the only opportunity to reach this code\n> without parsing the commit is inside \"test-tool bloom\n> get_filter_for_commit\" but it is best to be safe.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> bloom.c | 3 +++\n> 1 file changed, 3 insertions(+)\n>\n> diff --git a/bloom.c b/bloom.c\n> index eb08571c628..c3b81b1a38a 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -206,6 +206,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \tdiffopt.max_changes = max_changes;\n> \tdiff_setup_done(&diffopt);\n>\n> +\t/* ensure commit is parsed so we have parent information */\n\nI don't think that this comment is critical to the change, since\nfamiliar readers will know why this 'parse_commit' call is here, but I\ndon't really mind either way...\n\n> +\tparse_commit(c);\n> +\n\nOK. I figure that we could force the callers to parse these commits, but\nI think that this approach makes more sense. This should be a no-op for\nalready-parsed commits, which means we'll get out of this call pretty\nquickly.\n\nThe benefit there, of course, would be that we don't have to worry about\nsome callers forgetting to make sure that they are passing\nalready-parsed commits, and that the trade-off we make to allow such a\nthing is pretty cheap, relatively speaking.\n\n> \tif (c->parents)\n> \t\tdiff_tree_oid(&c->parents->item->object.oid, &c->object.oid, \"\", &diffopt);\n> \telse\n> --\n> gitgitgadget\n\nMakes sense, thanks.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396805","messageId":"20200501231240.GC46422@syl.local","threadId":"53367","inReplyTo":"7d5561575d5e81128dcccb411bf2b052491d1850.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 06/12] bloom: use num_changes not nr for limit detection","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T23:12:40Z","receivedAt":"2020-05-01T23:12:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:23PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n>\n> As diff_tree_oid() computes a diff, it will terminate early if the\n> total number of changed paths is strictly larger than max_changes.\n> This includes the directories that changed, not just the file paths.\n> However, only the file paths are reflected in the resulting diff\n> queue \"nr\" value.\n\nNit; s/queue/queue's\n\n>\n> Use the \"num_changes\" from diffopt to check if the diff terminated\n> early. This is incredibly important, as it can result in incorrect\n> filters! For example, the first commit in the Linux kernel repo\n> reports only 471 changes, but since these are nested inside several\n> directories they expand to 513 \"real\" changes, and in fact the\n> total list of changes is not reported. Thus, the computed filter\n> for this commit is incorrect.\n\nWow, this is a great find. Nicely done!\n\n> Demonstrate the subtle difference by using one fewer file change\n> in the 'get bloom filter for commit with 513 changes' test. Before,\n> this edited 513 files inside \"bigDir\" which hit this inequality.\n> However, dropping the file count by one demonstrates how the\n> previous inequality was incorrect but the new one is correct.\n>\n> Signed-off-by: Derrick Stolee \n> ---\n> bloom.c | 2 +-\n> t/t0095-bloom.sh | 2 +-\n> 2 files changed, 2 insertions(+), 2 deletions(-)\n>\n> diff --git a/bloom.c b/bloom.c\n> index c3b81b1a38a..9a8386ac676 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -215,7 +215,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\tdiff_tree_oid(NULL, &c->object.oid, \"\", &diffopt);\n> \tdiffcore_std(&diffopt);\n>\n> -\tif (diff_queued_diff.nr <= max_changes) {\n> +\tif (diffopt.num_changes <= max_changes) {\n> \t\tstruct hashmap pathmap;\n> \t\tstruct pathmap_hash_entry *e;\n> \t\tstruct hashmap_iter iter;\n> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> index 6defeb544f1..48a90625596 100755\n> --- a/t/t0095-bloom.sh\n> +++ b/t/t0095-bloom.sh\n> @@ -100,7 +100,7 @@ test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '\n> \trm actual &&\n> \trm expect &&\n> \tmkdir bigDir &&\n> -\tfor i in $(test_seq 0 512)\n> +\tfor i in $(test_seq 0 511)\n\nThanks for demonstrating the fix. This is change is very subtle, but I\nthink that it's right on.\n\n> \tdo\n> \t\techo $i >bigDir/$i\n> \tdone &&\n> --\n> gitgitgadget\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396807","messageId":"20200501234447.GD46422@syl.local","threadId":"53367","inReplyTo":"35d2901957efbb8727142ef633ae0953b613c0d1.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 07/12] completion: offer '--(no-)patch' among 'git log' options","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T23:44:47Z","receivedAt":"2020-05-01T23:44:52Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:24PM +0000, SZEDER Gábor via GitGitGadget wrote:\n> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nThis doesn't look quite right ;). Interestingly, Git applies it just\nfine, and your encoding looks reasonable to me.\n\n> Signed-off-by: SZEDER Gábor \n> Signed-off-by: Derrick Stolee \n> ---\n> contrib/completion/git-completion.bash | 1 +\n> 1 file changed, 1 insertion(+)\n>\n> diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\n> index c21786f2fd0..ec6ff1d5fb8 100644\n> --- a/contrib/completion/git-completion.bash\n> +++ b/contrib/completion/git-completion.bash\n> @@ -1860,6 +1860,7 @@ _git_log ()\n> \t\t\t$merge\n> \t\t\t$__git_diff_common_options\n> \t\t\t--pickaxe-all --pickaxe-regex\n> +\t\t\t--patch --no-patch\n> \t\t\t\"\n> \t\treturn\n> \t\t;;\n> --\n> gitgitgadget\n>\nThanks,\nTaylor\n"},{"id":"396808","messageId":"20200501234618.GE46422@syl.local","threadId":"53367","inReplyTo":"1f326612da05dfa74ebaaee6a852d5ef92a4ed29.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 08/12] line-log: remove unused fields from 'struct line_log_data'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-01T23:46:18Z","receivedAt":"2020-05-01T23:46:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:25PM +0000, SZEDER Gábor via GitGitGadget wrote:\n> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n>\n> Remove the unused fields 'status', 'arg_alloc', 'arg_nr' and 'args'\n> from 'struct line_log_data'. They were already part of the struct\n> when it was introduced in commit 12da1d1f6 (Implement line-history\n> search (git log -L), 2013-03-28), but as far as I can tell none of\n> them have ever been actually used.\n>\n> Signed-off-by: SZEDER Gábor \n> Signed-off-by: Derrick Stolee \n> ---\n> line-log.h | 3 ---\n> 1 file changed, 3 deletions(-)\n>\n> diff --git a/line-log.h b/line-log.h\n> index 8ee7a2bd4a1..882c5055bb8 100644\n> --- a/line-log.h\n> +++ b/line-log.h\n> @@ -46,10 +46,7 @@ void sort_and_merge_range_set(struct range_set *);\n> struct line_log_data {\n> \tstruct line_log_data *next;\n> \tchar *path;\n> -\tchar status;\n> \tstruct range_set ranges;\n> -\tint arg_alloc, arg_nr;\n> -\tconst char **args;\n> \tstruct diff_filepair *pair;\n> \tstruct diff_ranges diff;\n> };\n> --\n> gitgitgadget\n\nVery sensible.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396939","messageId":"20200504173106.GA35579@syl.local","threadId":"53367","inReplyTo":"4e3d7233095064de197c447cb31cf4652d42b775.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 09/12] t4211-line-log: add tests for parent oids","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T17:31:06Z","receivedAt":"2020-05-04T17:31:12Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:26PM +0000, SZEDER Gábor via GitGitGadget wrote:\n> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n>\n> None of the tests in 't4211-line-log.sh' really check which parent\n> object IDs are shown in the output, either implicitly as part of\n> \"Merge: ...\" lines [1] or explicitly via the '%p' or '%P' format\n> specifiers in a custom pretty format.\n>\n> Add two tests to 't4211-line-log.sh' to check which parent object IDs\n> are shown, one without and one with explicitly requested parent\n> rewriting, IOW without and with the '--parents' option.\n>\n> The test without '--parents' is marked as failing, because without\n> that option parent rewriting should not be performed, and thus the\n> parent object ID should be that of the immediate parent, just like in\n> case of a pathspec-limited history traversal without parent rewriting.\n> The current line-level log implementation, however, performs parent\n> rewriting unconditionally and without a possibility to turn it off,\n> and, consequently, it shows the object ID of the most recent ancestor\n> that modified the given line range.\n>\n> In both of these new tests we only really care about the object IDs of\n> the listed commits and their parents, but not the diffs of the line\n> ranges; the diffs have already been thoroughly checked in the previous\n> tests.\n>\n> [1] While one of the tests ('-M -L ':f:b.c' parallel-change') does\n> list a merge commit, both of its parents happen to modify the\n> given line range and are listed as well, so the implications of\n> parent rewriting remained hidden and untested.\n>\n> Signed-off-by: SZEDER Gábor \n> Signed-off-by: Derrick Stolee \n> ---\n\nThese tests make sense, and demonstrate the problem nicely. I don't\nthink that I have a ton to add to this patch, so:\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396944","messageId":"20200504175230.GB35579@syl.local","threadId":"53367","inReplyTo":"d9991d6158df6af0e62b8739591dd726d3479324.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 10/12] line-log: more responsive, incremental 'git log -L'","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T17:52:30Z","receivedAt":"2020-05-04T17:52:36Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:27PM +0000, SZEDER Gábor via GitGitGadget wrote:\n> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n>\n> The current line-level log implementation performs a preprocessing\n> step in prepare_revision_walk(), during which the line_log_filter()\n> function filters and rewrites history to keep only commits modifying\n> the given line range. This preprocessing affects both responsiveness\n> and correctness:\n>\n> - Git doesn't produce any output during this preprocessing step.\n> Checking whether a commit modified the given line range is\n> somewhat expensive, so depending on the size of the given revision\n> range this preprocessing can result in a significant delay before\n> the first commit is shown.\n>\n> - Limiting the number of displayed commits (e.g. 'git log -3 -L...')\n> doesn't limit the amount of work during preprocessing, because\n> that limit is applied during history traversal. Alas, by that\n> point this expensive preprocessing step has already churned\n> through the whole revision range to find all commits modifying the\n> revision range, even though only a few of them need to be shown.\n>\n> - It rewrites parents, with no way to turn it off. Without the user\n> explicitly requesting parent rewriting any parent object ID shown\n> should be that of the immediate parent, just like in case of a\n> pathspec-limited history traversal without parent rewriting.\n>\n> However, after that preprocessing step rewrote history, the\n> subsequent \"regular\" history traversal (i.e. get_revision() in a\n> loop) only sees commits modifying the given line range.\n> Consequently, it can only show the object ID of the last ancestor\n> that modified the given line range (which might happen to be the\n> immediate parent, but many-many times it isn't).\n\nThanks for a very clear and straightforward explanation of the problem\nthat you are trying to solve, here.\n\n> This patch addresses both the correctness and, at least for the common\n> case, the responsiveness issues by integrating line-level log\n> filtering into the regular revision walking machinery:\n>\n> - Make process_ranges_arbitrary_commit(), the static function in\n> 'line-log.c' deciding whether a commit modifies the given line\n> range, public by removing the static keyword and adding the\n> 'line_log_' prefix, so it can be called from other parts of the\n> revision walking machinery.\n>\n> - If the user didn't explicitly ask for parent rewriting (which, I\n> believe, is the most common case):\n>\n> - Call this now-public function during regular history traversal,\n> namely from get_commit_action() to ignore any commits not\n> modifying the given line range.\n>\n> Note that while this check is relatively expensive, it must be\n> performed before other, much cheaper conditions, because the\n> tracked line range must be adjusted even when the commit will\n> end up being ignored by other conditions.\n>\n> - Skip the line_log_filter() call, i.e. the expensive\n> preprocessing step, in prepare_revision_walk(), because, thanks\n> to the above points, the revision walking machinery is now able\n> to filter out commits not modifying the given line range while\n> traversing history.\n>\n> This way the regular history traversal sees the unmodified\n> history, and is therefore able to print the object ids of the\n> immediate parents of the listed commits. The eliminated\n> preprocessing step can greatly reduce the delay before the first\n> commit is shown, see the numbers below.\n\nNicely done.\n\n> - However, if the user did explicitly ask for parent rewriting via\n> '--parents' or a similar option, then stick with the current\n> implementation for now, i.e. perform that expensive filtering and\n> history rewriting in the preprocessing step just like we did\n> before, leaving the initial delay as long as it was.\n\nRight; here we're stuck taking the slow path. Maybe in the future that\ncould become faster, too, if the revision walking machinery knew how to\nperform this filtering, but not today. Makes sense.\n\n> I tried to integrate line-level log filtering with parent rewriting\n> into the regular history traversal, but, unfortunately, several\n> subtleties resisted... :) Maybe someday we'll figure out how to do\n> that, but until then at least the simple and common (i.e. without\n> parent rewriting) 'git log -L:func:file' commands can benefit from the\n> reduced delay.\n\n:)\n\n> This change makes the failing 'parent oids without parent rewriting'\n> test in 't4211-line-log.sh' succeed.\n>\n> The reduced delay is most noticable when there's a commit modifying\n> the line range near the tip of a large-ish revision range:\n>\n> # no parent rewriting requested, no commit-graph present\n> $ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0\n>\n> Before:\n>\n> real 0m9.570s\n> user 0m9.494s\n> sys 0m0.076s\n>\n> After:\n>\n> real 0m0.718s\n> user 0m0.674s\n> sys 0m0.044s\n>\n> A significant part of the remaining delay is spent reading and parsing\n> commit objects in limit_list(). With the help of the commit-graph we\n> can eliminate most of that reading and parsing overhead, so here are\n> the timing results of the same command as above, but this time using\n> the commit-graph:\n>\n> Before:\n>\n> real 0m8.874s\n> user 0m8.816s\n> sys 0m0.057s\n>\n> After:\n>\n> real 0m0.107s\n> user 0m0.091s\n> sys 0m0.013s\n>\n> The next patch will further reduce the remaining delay.\n>\n> To be clear: this patch doesn't actually optimize the line-level log,\n> but merely moves most of the work from the preprocessing step to the\n> history travelsal, so the commits modifying the line range can be\n\ns/travelsal/traversal\n\n> shown as soon as they are processed, and the traversal can be\n> terminated as soon as the given number of commits are shown.\n> Consequently, listing the full history of a line range, potentially\n> all the way to the root commit, will take the same time as before (but\n> at least the user might start reading the output earlier).\n> Furthermore, if the most recent commit modifying the line range is far\n> away from the starting revision, then that initial delay will still be\n> significant.\n>\n> Additional testing by Derrick Stolee: In the Linux kernel repository,\n> the MAINTAINERS file was changed ~3,500 times across the ~915,000\n> commits. In addition to that edit frequency, the file itself is quite\n> large (~18,700 lines). This means that a significant portion of the\n> computation is taken up by computing the patch-diff of the file. This\n> patch improves the time it takes to output the first result quite a\n> bit:\n>\n> Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n> Before: 3.88 s\n> After: 0.71 s\n\nAre these 'real' times, or user/sys times?\n\n> If we drop the \"-n 1\" in the command, then there is no change in\n> end-to-end process time. This is because the command still needs to\n> walk the entire commit history, which negates the point of this\n> patch. This is expected.\n>\n> As a note for future reference, the ~4.3 seconds in the old code\n> spends ~2.6 seconds computing the patch-diffs, and the rest of the\n> time is spent walking commits and computing diffs for which paths\n> changed at each commit. The changed-path Bloom filters could improve\n> the end-to-end computation time (i.e. no \"-n 1\" in the command).\n>\n> Signed-off-by: SZEDER Gábor \n> Signed-off-by: Derrick Stolee \n> ---\n> line-log.c | 4 ++--\n> line-log.h | 2 ++\n> revision.c | 27 ++++++++++++++++++++++++++-\n> t/t4211-line-log.sh | 2 +-\n> 4 files changed, 31 insertions(+), 4 deletions(-)\n>\n> diff --git a/line-log.c b/line-log.c\n> index 9010e00950b..520ee715bcd 100644\n> --- a/line-log.c\n> +++ b/line-log.c\n> @@ -1227,7 +1227,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n> \t/* NEEDSWORK leaking like a sieve */\n> }\n>\n> -static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n> +int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n> {\n> \tstruct line_log_data *range = lookup_line_range(rev, commit);\n> \tint changed = 0;\n> @@ -1270,7 +1270,7 @@ int line_log_filter(struct rev_info *rev)\n> \twhile (list) {\n> \t\tstruct commit_list *to_free = NULL;\n> \t\tcommit = list->item;\n> -\t\tif (process_ranges_arbitrary_commit(rev, commit)) {\n> +\t\tif (line_log_process_ranges_arbitrary_commit(rev, commit)) {\n> \t\t\t*pp = list;\n> \t\t\tpp = &list->next;\n> \t\t} else\n> diff --git a/line-log.h b/line-log.h\n> index 882c5055bb8..82ae8d98a40 100644\n> --- a/line-log.h\n> +++ b/line-log.h\n> @@ -54,6 +54,8 @@ struct line_log_data {\n> void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args);\n>\n> int line_log_filter(struct rev_info *rev);\n> +int line_log_process_ranges_arbitrary_commit(struct rev_info *rev,\n> +\t\t\t\t\t\t struct commit *commit);\n>\n> int line_log_print(struct rev_info *rev, struct commit *commit);\n>\n> diff --git a/revision.c b/revision.c\n> index f78c636e4d0..3228db9af6d 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -39,6 +39,8 @@ static const char *term_good;\n>\n> implement_shared_commit_slab(revision_sources, char *);\n>\n> +static inline int want_ancestry(const struct rev_info *revs);\n> +\n\nI wouldn't be opposed to simply moving the definition of 'want_ancestry'\nup here, since it is self-contained and doesn't depend on any other\ndefinitions, except 'struct rev_info' itself, which comes from\n'revision.h'.\n\n> void show_object_with_name(FILE *out, struct object *obj, const char *name)\n> {\n> \tconst char *p;\n> @@ -3511,7 +3513,14 @@ int prepare_revision_walk(struct rev_info *revs)\n> \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n> \t} else if (revs->topo_order)\n> \t\tinit_topo_walk(revs);\n> -\tif (revs->line_level_traverse)\n> +\tif (revs->line_level_traverse && want_ancestry(revs))\n> +\t\t/*\n> +\t\t * At the moment we can only do line-level log with parent\n> +\t\t * rewriting by performing this expensive pre-filtering step.\n> +\t\t * If parent rewriting is not requested, then we rather\n> +\t\t * perform the line-level log filtering during the regular\n> +\t\t * history traversal.\n\nI think that this is just a style comment at this point, but I'm not\noverly attached to the last three lines of this comment. I think that\nthe commit message that these lines would blame down to explains the\nsituation quite clearly, and the reader can search for the\n'!want_ancestry' call a couple hundred lines later.\n\nThat said, I certainly won't be offended if you want to keep this\ncomment around; I just don't think that it's strictly necessary.\n\n> +\t\t */\n> \t\tline_log_filter(revs);\n> \tif (revs->simplify_merges)\n> \t\tsimplify_merges(revs);\n> @@ -3722,6 +3731,22 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi\n> \t\treturn commit_ignore;\n> \tif (commit->object.flags & UNINTERESTING)\n> \t\treturn commit_ignore;\n> +\tif (revs->line_level_traverse && !want_ancestry(revs)) {\n> +\t\t/*\n> +\t\t * In case of line-level log with parent rewriting\n> +\t\t * prepare_revision_walk() already took care of all line-level\n> +\t\t * log filtering, and there is nothing left to do here.\n> +\t\t *\n> +\t\t * If parent rewriting was not requested, then this is the\n> +\t\t * place to perform the line-level log filtering. Notably,\n> +\t\t * this check, though expensive, must come before the other,\n> +\t\t * cheaper filtering conditions, because the tracked line\n> +\t\t * ranges must be adjusted even when the commit will end up\n> +\t\t * being ignored based on other conditions.\n> +\t\t */\n> +\t\tif (!line_log_process_ranges_arbitrary_commit(revs, commit))\n> +\t\t\treturn commit_ignore;\n> +\t}\n> \tif (revs->min_age != -1 &&\n> \t comparison_date(revs, commit) > revs->min_age)\n> \t\t\treturn commit_ignore;\n> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\n> index ea4a9398365..1428eae2629 100755\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -263,7 +263,7 @@ test_expect_success 'setup for checking line-log and parent oids' '\n> '\n>\n> # Parent oid should be from immediate parent.\n> -test_expect_failure 'parent oids without parent rewriting' '\n> +test_expect_success 'parent oids without parent rewriting' '\n> \tcat >expect <<-EOF &&\n> \t$head_oid $prev_oid Modify func2() in file.c\n> \t$root_oid Add func1() and func2() in file.c\n> --\n> gitgitgadget\n\nAll makes sense, and the ending is very satisfying. Someone with a\nlittle more familiarity with line-log should review this also. But, for\nmy part this has been:\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"396946","messageId":"4b7e5f51-9fdb-45ac-123e-2589087afa48@gmail.com","threadId":"53367","inReplyTo":"20200504175230.GB35579@syl.local","subject":"Re: [PATCH 10/12] line-log: more responsive, incremental 'git log -L'","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-05-04T17:55:57Z","receivedAt":"2020-05-04T17:56:03Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 5/4/2020 1:52 PM, Taylor Blau wrote:\n> On Fri, May 01, 2020 at 03:30:27PM +0000, SZEDER Gábor via GitGitGadget wrote:\n\n>> To be clear: this patch doesn't actually optimize the line-level log,\n>> but merely moves most of the work from the preprocessing step to the\n>> history travelsal, so the commits modifying the line range can be\n> \n> s/travelsal/traversal\n\nThanks!\n\n>> shown as soon as they are processed, and the traversal can be\n>> terminated as soon as the given number of commits are shown.\n>> Consequently, listing the full history of a line range, potentially\n>> all the way to the root commit, will take the same time as before (but\n>> at least the user might start reading the output earlier).\n>> Furthermore, if the most recent commit modifying the line range is far\n>> away from the starting revision, then that initial delay will still be\n>> significant.\n>>\n>> Additional testing by Derrick Stolee: In the Linux kernel repository,\n>> the MAINTAINERS file was changed ~3,500 times across the ~915,000\n>> commits. In addition to that edit frequency, the file itself is quite\n>> large (~18,700 lines). This means that a significant portion of the\n>> computation is taken up by computing the patch-diff of the file. This\n>> patch improves the time it takes to output the first result quite a\n>> bit:\n>>\n>> Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n>> Before: 3.88 s\n>> After: 0.71 s\n> \n> Are these 'real' times, or user/sys times?\n\nTrue, this is a difference between my reporting and Szeder's. I only\nreport \"real\" time. \n\nThanks,\n-Stolee\n\n"},{"id":"396991","messageId":"20200504212516.GA45250@syl.local","threadId":"53367","inReplyTo":"3abc713092456b7c34ac72c0064b0b5c51ac726f.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 11/12] line-log: try to use generation number-based topo-ordering","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T21:25:16Z","receivedAt":"2020-05-04T21:25:22Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:28PM +0000, SZEDER Gábor via GitGitGadget wrote:\n> From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n>\n> The previous patch made it possible to perform line-level filtering\n> during history traversal instead of in an expensive preprocessing\n> step, but it still requires some simpler preprocessing steps, notably\n> topo-ordering. However, nowadays we have commit-graphs storing\n> generation numbers, which make it possible to incrementally traverse\n> the history in topological order, without the preparatory limit_list()\n> and sort_in_topological_order() steps; see b45424181e (revision.c:\n> generation-based topo-order algorithm, 2018-11-01).\n>\n> [snip]\n\nThis one makes sense, too. Sorry for a long gap in reviewing parts of\nthis series. A few other things have popped up throughout the day. I'll\nget to the last one shortly.\n\n\nThanks,\nTaylor\n"},{"id":"396996","messageId":"20200504215036.GB45250@syl.local","threadId":"53367","inReplyTo":"7e0c2871cf73dead655626442cc191d13b7bd94b.1588347029.git.gitgitgadget@gmail.com","subject":"Re: [PATCH 12/12] line-log: integrate with changed-path Bloom filters","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2020-05-04T21:50:36Z","receivedAt":"2020-05-04T21:50:42Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, May 01, 2020 at 03:30:29PM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n\nExtremely well done. These changes all make sense to me, and the\nperformance improvements are all very appealing. Thanks for a most\nenjoyable read.\n\n Reviewed-by: Taylor Blau \n\nThanks,\nTaylor\n"},{"id":"397534","messageId":"572d0508fe0364119d83c08e01a66153810958e9.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 02/12] test-bloom: fix usage typo","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:09Z","receivedAt":"2020-05-11T11:56:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nSigned-off-by: Derrick Stolee \n---\n t/helper/test-bloom.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/helper/test-bloom.c b/t/helper/test-bloom.c\nindex 77eb27adac7..00c1d44a561 100644\n--- a/t/helper/test-bloom.c\n+++ b/t/helper/test-bloom.c\n@@ -44,7 +44,7 @@ static void get_bloom_filter_for_commit(const struct object_id *commit_oid)\n }\n \n static const char *bloom_usage = \"\\n\"\n-\" test-tool bloom get_murmer3 \\n\"\n+\" test-tool bloom get_murmur3 \\n\"\n \" test-tool bloom generate_filter [...]\\n\"\n \" test-tool get_filter_for_commit \\n\";\n \n-- \ngitgitgadget\n\n"},{"id":"397535","messageId":"0e08cec78d325452f9901501b2e0b53b3145a022.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 03/12] bloom: parse commit before computing filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:10Z","receivedAt":"2020-05-11T11:56:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen computing changed-path Bloom filters for a commit, we need to\nknow if the commit has a parent or not. If the commit is not parsed,\nthen its parent pointer will be NULL.\n\nAs far as I can tell, the only opportunity to reach this code\nwithout parsing the commit is inside \"test-tool bloom\nget_filter_for_commit\" but it is best to be safe.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 3 +++\n 1 file changed, 3 insertions(+)\n\ndiff --git a/bloom.c b/bloom.c\nindex 2e3e0f5037b..96792782719 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -193,6 +193,9 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \tdiffopt.max_changes = max_changes;\n \tdiff_setup_done(&diffopt);\n \n+\t/* ensure commit is parsed so we have parent information */\n+\trepo_parse_commit(r, c);\n+\n \tif (c->parents)\n \t\tdiff_tree_oid(&c->parents->item->object.oid, &c->object.oid, \"\", &diffopt);\n \telse\n-- \ngitgitgadget\n\n"},{"id":"397536","messageId":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.git.1588347029.gitgitgadget@gmail.com","subject":"[PATCH v2 00/12] Integrating line-log and changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:07Z","receivedAt":"2020-05-11T11:56:27Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"The best way to learn how a feature works is to build on it. That's also the\nbest way to find defects.\n\nI started on this patch series with two goals:\n\n 1. Understand and submit Szeder's incremental line-log RFC [1].\n 2. Integrate changed-path Bloom filters with line-log.\n\n[1] https://lore.kernel.org/git/20190818182801.7580-1-szeder.dev@gmail.com/\n\nSince I knew a lot about the Bloom filters and not much about line-log.c, I\nexpected to learn a lot that could contribute to improving Szeder's patches.\nInstead, I discovered some deficiencies in the Bloom filter code, including\na few meaningful bugs that should be fixed before the topic is merge to\nmaster.\n\nThis series is organized as follows:\n\n * Patches 1-4 are minor Bloom filter cleanups, including a documentation\n bug.\n \n \n * Patch 5 fixes a problem where the Bloom filters use much larger filters\n than expected.\n \n \n * Patch 6 fixes a bug related to the short-circuit of large diffs from\n e369698016 (diff: halt tree-diff early after max_changes, 2020-03-30).\n The condition for halting the diff computation is different than the\n check in bloom.c to see if that short-circuit was hit, which leads to\n some commits with large diffs getting an incomplete Bloom filter. This\n happened on the root commit of the Linux kernel repo, for example.\n \n \n * Patches 7-11 are Szeder's RFC, with my sign-off added. I have not changed\n the code from those submissions because I didn't find anything wrong with\n them as I was testing. However, I will take responsibility to respond to\n the feedback in this series.\n \n \n * Patch 12 integrates Bloom filters with the line-log code.\n \n \n\nI organized these patches so patches 1-6 could be split into its own topic,\nif beneficial to take earlier than the line-log changes.\n\nThe end result of this combined effort is the following: git log -L commands\nfeel much more responsive to a terminal user because Szeder's changes make\nthe computation incremental, and they have better end-to-end performance\nbecause of the integration with Bloom filters to reduce time spent running\ntree diffs for TREESAME commits.\n\nThe following table is also in patch 12, but it summarizes the results of\nthis series. These are timings for running git log -L 1,10:$path for these\nrecently-edited paths. The \"Entire History\" columns wait for the full\ncommand to complete. The \"First Result\" columns add \"-n 1\" to the command,\nso we see the benefits of the incremental algorithm. Thus, the performance\nimprovements from \"Entire History\" to \"First Result\" are due entirely to\nSzeder's patches. The performance improvements from \"Before\" to \"After\" are\ndue to the changed-path Bloom filters.\n\n| | Entire History | First Result |\n| Path | Before | After | Before | After |\n|------------------------------|--------|--------|--------|--------|\n| MAINTAINERS | 4.26 s | 3.87 s | 0.41 s | 0.39 s |\n| fs/namei.c | 1.99 s | 0.99 s | 0.42 s | 0.21 s |\n| arch/x86/kvm/cpuid.c | 5.28 s | 1.12 s | 0.16 s | 0.09 s |\n| fs/io_uring.c | 4.34 s | 0.99 s | 0.94 s | 0.27 s |\n| arch/x86/kvm/vmx/vmx.c | 5.01 s | 1.34 s | 0.21 s | 0.12 s |\n| arch/x86/kvm/x86.c | 2.24 s | 1.18 s | 0.21 s | 0.14 s |\n| fs/btrfs/disk-io.c | 1.82 s | 1.01 s | 0.06 s | 0.05 s |\n| Documentation/scsi/index.rst | 3.30 s | 0.89 s | 1.46 s | 0.03 s |\n\nSome splashy numbers include a 110x speedup for finding the first result for\nDocumentation/scsi/index.rst. That's certainly an outlier, but the rest have\nan at least 10x speedup.\n\nUpdate in V2: Modified commit messages according to Taylor's feedback.\n\nThanks, -Stolee\n\nDerrick Stolee (7):\n bloom: fix whitespace around tab length\n test-bloom: fix usage typo\n bloom: parse commit before computing filters\n Documentation: changed-path Bloom filters use byte words\n bloom: de-duplicate directory entries\n bloom: use num_changes not nr for limit detection\n line-log: integrate with changed-path Bloom filters\n\nSZEDER Gábor (5):\n completion: offer '--(no-)patch' among 'git log' options\n line-log: remove unused fields from 'struct line_log_data'\n t4211-line-log: add tests for parent oids\n line-log: more responsive, incremental 'git log -L'\n line-log: try to use generation number-based topo-ordering\n\n .../technical/commit-graph-format.txt | 8 +--\n bloom.c | 61 ++++++++++++-----\n bloom.h | 5 +-\n contrib/completion/git-completion.bash | 1 +\n line-log.c | 43 +++++++++++-\n line-log.h | 5 +-\n revision.c | 43 ++++++++++--\n t/helper/test-bloom.c | 2 +-\n t/t0095-bloom.sh | 6 +-\n t/t4211-line-log.sh | 68 +++++++++++++++++++\n 10 files changed, 201 insertions(+), 41 deletions(-)\n\n\nbase-commit: 1b4c57fa87e121f155863f898dc39d06cf4a1d99\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-622%2Fderrickstolee%2Flog-l-on-bloom-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-622/derrickstolee/log-l-on-bloom-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/622\n\nRange-diff vs v1:\n\n 1: 89625b0efae = 1: 89625b0efae bloom: fix whitespace around tab length\n 2: 572d0508fe0 = 2: 572d0508fe0 test-bloom: fix usage typo\n 5: ef4c08e401b ! 3: 0e08cec78d3 bloom: parse commit before computing filters\n @@ bloom.c: struct bloom_filter *get_bloom_filter(struct repository *r,\n \tdiff_setup_done(&diffopt);\n \n +\t/* ensure commit is parsed so we have parent information */\n -+\tparse_commit(c);\n ++\trepo_parse_commit(r, c);\n +\n \tif (c->parents)\n \t\tdiff_tree_oid(&c->parents->item->object.oid, &c->object.oid, \"\", &diffopt);\n 3: 03b2c84db36 ! 4: 61f78a2b0dd Documentation: changed-path Bloom filters use byte words\n @@ Commit message\n In Documentation/technical/commit-graph-format.txt, the definition\n of the BIDX chunk specifies the length is a number of 8-byte words.\n During development we discovered that using 8-byte words in the\n - Murmur3 hash algorithm causes issues with Big-Endian versus Little-\n - Endian machines. Thus, the hash algorithm was adapted to work on a\n + Murmur3 hash algorithm causes issues with big-endian versus little-\n + endian machines. Thus, the hash algorithm was adapted to work on a\n byte-by-byte basis. However, this caused a change in the definition\n of a \"word\" in bloom.h. Now, a \"word\" is a single byte, which allows\n filters to be as small as two bytes. These length-two filters are\n 4: 07d0a25f1c4 = 5: ba0d8c1f539 bloom: de-duplicate directory entries\n 6: 7d5561575d5 ! 6: 8278b5c0918 bloom: use num_changes not nr for limit detection\n @@ Commit message\n total number of changed paths is strictly larger than max_changes.\n This includes the directories that changed, not just the file paths.\n However, only the file paths are reflected in the resulting diff\n - queue \"nr\" value.\n + queue's \"nr\" value.\n \n Use the \"num_changes\" from diffopt to check if the diff terminated\n early. This is incredibly important, as it can result in incorrect\n 7: 35d2901957e = 7: 05f8ee14752 completion: offer '--(no-)patch' among 'git log' options\n 8: 1f326612da0 = 8: c3f87ec4379 line-log: remove unused fields from 'struct line_log_data'\n 9: 4e3d7233095 ! 9: 69c2c2f775f t4211-line-log: add tests for parent oids\n @@ Metadata\n Author: SZEDER Gábor \n \n ## Commit message ##\n - t4211-line-log: add tests for parent oids\n + t4211-line-log: add tests for parent oids\n \n None of the tests in 't4211-line-log.sh' really check which parent\n object IDs are shown in the output, either implicitly as part of\n 10: d9991d6158d ! 10: 009da4b93f6 line-log: more responsive, incremental 'git log -L'\n @@ Commit message\n \n To be clear: this patch doesn't actually optimize the line-level log,\n but merely moves most of the work from the preprocessing step to the\n - history travelsal, so the commits modifying the line range can be\n + history traversal, so the commits modifying the line range can be\n shown as soon as they are processed, and the traversal can be\n terminated as soon as the given number of commits are shown.\n Consequently, listing the full history of a line range, potentially\n @@ Commit message\n commits. In addition to that edit frequency, the file itself is quite\n large (~18,700 lines). This means that a significant portion of the\n computation is taken up by computing the patch-diff of the file. This\n - patch improves the time it takes to output the first result quite a\n - bit:\n + patch improves the real time it takes to output the first result quite\n + a bit:\n \n Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 3.88 s\n 11: 3abc7130924 ! 11: da087d2acbb line-log: try to use generation number-based topo-ordering\n @@ Commit message\n \n Additional testing by Derrick Stolee: Since this patch improves\n the performance for the first result, I repeated the experiment\n - from the previous patch on the Linux kernel repository:\n + from the previous patch on the Linux kernel repository, reporting\n + real time here:\n \n Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 0.71 s\n 12: 7e0c2871cf7 ! 12: 305f1eb0982 line-log: integrate with changed-path Bloom filters\n @@ Commit message\n \n (along with a bogus first result). It appears that the path\n arch/x86/kvm/svm.c was renamed, so we ignore that entry. This leaves the\n - following results:\n + following results for the real command time:\n \n | | Entire History | First Result |\n | Path | Before | After | Before | After |\n\n-- \ngitgitgadget\n"},{"id":"397537","messageId":"ba0d8c1f539751d9cfd556dac4eeda97758cf12e.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 05/12] bloom: de-duplicate directory entries","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:12Z","receivedAt":"2020-05-11T11:56:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nWhen computing a changed-path Bloom filter, we need to take the\nfiles that changed from the diff computation and extract the parent\ndirectories. That way, a directory pathspec such as \"Documentation\"\ncould match commits that change \"Documentation/git.txt\".\n\nHowever, the current code does a poor job of this process. The paths\nare added to a hashmap, but we do not check if an entry already\nexists with that path. This can create many duplicate entries and\ncause the filter to have a much larger length than it should. This\nmeans that the filter is more sparse than intended, which helps the\nfalse positive rate, but wastes a lot of space.\n\nProperly use hashmap_get() before hashmap_add(). Also be sure to\ninclude a comparison function so these can be matched correctly.\n\nThis has an effect on a test in t0095-bloom.sh. This makes sense,\nthere are ten changes inside \"smallDir\" so the total number of\npaths in the filter should be 11. This would result in 11 * 10 bits\nrequired, and with 8 bits per byte, this results in 14 bytes.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 35 ++++++++++++++++++++++++++---------\n t/t0095-bloom.sh | 4 ++--\n 2 files changed, 28 insertions(+), 11 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 96792782719..196cda0a1bd 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -158,6 +158,19 @@ void init_bloom_filters(void)\n \tinit_bloom_filter_slab(&bloom_filters);\n }\n \n+static int pathmap_cmp(const void *hashmap_cmp_fn_data,\n+\t\t const struct hashmap_entry *eptr,\n+\t\t const struct hashmap_entry *entry_or_key,\n+\t\t const void *keydata)\n+{\n+\tconst struct pathmap_hash_entry *e1, *e2;\n+\n+\te1 = container_of(eptr, const struct pathmap_hash_entry, entry);\n+\te2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);\n+\n+\treturn strcmp(e1->path, e2->path);\n+}\n+\n struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\t\t\t struct commit *c,\n \t\t\t\t int compute_if_not_present)\n@@ -206,25 +219,29 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\tstruct hashmap pathmap;\n \t\tstruct pathmap_hash_entry *e;\n \t\tstruct hashmap_iter iter;\n-\t\thashmap_init(&pathmap, NULL, NULL, 0);\n+\t\thashmap_init(&pathmap, pathmap_cmp, NULL, 0);\n \n \t\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n \t\t\tconst char *path = diff_queued_diff.queue[i]->two->path;\n \n \t\t\t/*\n-\t\t\t* Add each leading directory of the changed file, i.e. for\n-\t\t\t* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n-\t\t\t* the Bloom filter could be used to speed up commands like\n-\t\t\t* 'git log dir/subdir', too.\n-\t\t\t*\n-\t\t\t* Note that directories are added without the trailing '/'.\n-\t\t\t*/\n+\t\t\t * Add each leading directory of the changed file, i.e. for\n+\t\t\t * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n+\t\t\t * the Bloom filter could be used to speed up commands like\n+\t\t\t * 'git log dir/subdir', too.\n+\t\t\t *\n+\t\t\t * Note that directories are added without the trailing '/'.\n+\t\t\t */\n \t\t\tdo {\n \t\t\t\tchar *last_slash = strrchr(path, '/');\n \n \t\t\t\tFLEX_ALLOC_STR(e, path, path);\n \t\t\t\thashmap_entry_init(&e->entry, strhash(path));\n-\t\t\t\thashmap_add(&pathmap, &e->entry);\n+\n+\t\t\t\tif (!hashmap_get(&pathmap, &e->entry, NULL))\n+\t\t\t\t\thashmap_add(&pathmap, &e->entry);\n+\t\t\t\telse\n+\t\t\t\t\tfree(e);\n \n \t\t\t\tif (!last_slash)\n \t\t\t\t\tlast_slash = (char*)path;\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex 8f9eef116dc..6defeb544f1 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -89,8 +89,8 @@ test_expect_success 'get bloom filter for commit with 10 changes' '\n \tgit add smallDir &&\n \tgit commit -m \"commit with 10 changes\" &&\n \tcat >expect <<-\\EOF &&\n-\tFilter_Length:25\n-\tFilter_Data:82|a0|65|47|0c|92|90|c0|a1|40|02|a0|e2|40|e0|04|0a|9a|66|cf|80|19|85|42|23|\n+\tFilter_Length:14\n+\tFilter_Data:02|b3|c4|a0|34|e7|fe|eb|cb|47|fe|a0|e8|72|\n \tEOF\n \ttest-tool bloom get_filter_for_commit \"$(git rev-parse HEAD)\" >actual &&\n \ttest_cmp expect actual\n-- \ngitgitgadget\n\n"},{"id":"397538","messageId":"05f8ee147527f44fa673ebab26f2a08db0068ffe.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 07/12] completion: offer '--(no-)patch' among 'git log' options","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:14Z","receivedAt":"2020-05-11T11:56:32Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n contrib/completion/git-completion.bash | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash\nindex c21786f2fd0..ec6ff1d5fb8 100644\n--- a/contrib/completion/git-completion.bash\n+++ b/contrib/completion/git-completion.bash\n@@ -1860,6 +1860,7 @@ _git_log ()\n \t\t\t$merge\n \t\t\t$__git_diff_common_options\n \t\t\t--pickaxe-all --pickaxe-regex\n+\t\t\t--patch --no-patch\n \t\t\t\"\n \t\treturn\n \t\t;;\n-- \ngitgitgadget\n\n"},{"id":"397539","messageId":"c3f87ec4379ef31778e5184c81a38ed2b59b3cbf.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 08/12] line-log: remove unused fields from 'struct line_log_data'","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:15Z","receivedAt":"2020-05-11T11:56:33Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nRemove the unused fields 'status', 'arg_alloc', 'arg_nr' and 'args'\nfrom 'struct line_log_data'. They were already part of the struct\nwhen it was introduced in commit 12da1d1f6 (Implement line-history\nsearch (git log -L), 2013-03-28), but as far as I can tell none of\nthem have ever been actually used.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n line-log.h | 3 ---\n 1 file changed, 3 deletions(-)\n\ndiff --git a/line-log.h b/line-log.h\nindex 8ee7a2bd4a1..882c5055bb8 100644\n--- a/line-log.h\n+++ b/line-log.h\n@@ -46,10 +46,7 @@ void sort_and_merge_range_set(struct range_set *);\n struct line_log_data {\n \tstruct line_log_data *next;\n \tchar *path;\n-\tchar status;\n \tstruct range_set ranges;\n-\tint arg_alloc, arg_nr;\n-\tconst char **args;\n \tstruct diff_filepair *pair;\n \tstruct diff_ranges diff;\n };\n-- \ngitgitgadget\n\n"},{"id":"397540","messageId":"69c2c2f775fd873e5df8316e90e2d1a0df07e141.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 09/12] t4211-line-log: add tests for parent oids","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:16Z","receivedAt":"2020-05-11T11:56:34Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nNone of the tests in 't4211-line-log.sh' really check which parent\nobject IDs are shown in the output, either implicitly as part of\n\"Merge: ...\" lines [1] or explicitly via the '%p' or '%P' format\nspecifiers in a custom pretty format.\n\nAdd two tests to 't4211-line-log.sh' to check which parent object IDs\nare shown, one without and one with explicitly requested parent\nrewriting, IOW without and with the '--parents' option.\n\nThe test without '--parents' is marked as failing, because without\nthat option parent rewriting should not be performed, and thus the\nparent object ID should be that of the immediate parent, just like in\ncase of a pathspec-limited history traversal without parent rewriting.\nThe current line-level log implementation, however, performs parent\nrewriting unconditionally and without a possibility to turn it off,\nand, consequently, it shows the object ID of the most recent ancestor\nthat modified the given line range.\n\nIn both of these new tests we only really care about the object IDs of\nthe listed commits and their parents, but not the diffs of the line\nranges; the diffs have already been thoroughly checked in the previous\ntests.\n\n[1] While one of the tests ('-M -L ':f:b.c' parallel-change') does\n list a merge commit, both of its parents happen to modify the\n given line range and are listed as well, so the implications of\n parent rewriting remained hidden and untested.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n t/t4211-line-log.sh | 68 +++++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 68 insertions(+)\n\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex cda58186c2d..ea4a9398365 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -215,4 +215,72 @@ test_expect_success 'fancy rename following #2' '\n \ttest_cmp expect actual\n '\n \n+# Create the following linear history, where each commit does what its\n+# subject line promises:\n+#\n+# * 66c6410 Modify func2() in file.c\n+# * 50834e5 Modify other-file\n+# * fe5851c Modify func1() in file.c\n+# * 8c7c7dd Add other-file\n+# * d5f4417 Add func1() and func2() in file.c\n+test_expect_success 'setup for checking line-log and parent oids' '\n+\tgit checkout --orphan parent-oids &&\n+\tgit reset --hard &&\n+\n+\tcat >file.c <<-\\EOF &&\n+\tint func1()\n+\t{\n+\t return F1;\n+\t}\n+\n+\tint func2()\n+\t{\n+\t return F2;\n+\t}\n+\tEOF\n+\tgit add file.c &&\n+\ttest_tick &&\n+\tgit commit -m \"Add func1() and func2() in file.c\" &&\n+\n+\techo 1 >other-file &&\n+\tgit add other-file &&\n+\tgit commit -m \"Add other-file\" &&\n+\n+\tsed -e \"s/F1/F1 + 1/\" file.c >tmp &&\n+\tmv tmp file.c &&\n+\tgit commit -a -m \"Modify func1() in file.c\" &&\n+\n+\techo 2 >other-file &&\n+\tgit commit -a -m \"Modify other-file\" &&\n+\n+\tsed -e \"s/F2/F2 + 2/\" file.c >tmp &&\n+\tmv tmp file.c &&\n+\tgit commit -a -m \"Modify func2() in file.c\" &&\n+\n+\thead_oid=$(git rev-parse --short HEAD) &&\n+\tprev_oid=$(git rev-parse --short HEAD^) &&\n+\troot_oid=$(git rev-parse --short HEAD~4)\n+'\n+\n+# Parent oid should be from immediate parent.\n+test_expect_failure 'parent oids without parent rewriting' '\n+\tcat >expect <<-EOF &&\n+\t$head_oid $prev_oid Modify func2() in file.c\n+\t$root_oid Add func1() and func2() in file.c\n+\tEOF\n+\tgit log --format=\"%h %p %s\" --no-patch -L:func2:file.c >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+# Parent oid should be from the most recent ancestor touching func2(),\n+# i.e. in this case from the root commit.\n+test_expect_success 'parent oids with parent rewriting' '\n+\tcat >expect <<-EOF &&\n+\t$head_oid $root_oid Modify func2() in file.c\n+\t$root_oid Add func1() and func2() in file.c\n+\tEOF\n+\tgit log --format=\"%h %p %s\" --no-patch -L:func2:file.c --parents >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"397541","messageId":"009da4b93f626957e1b8cd103a3afcb7fa5386d3.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 10/12] line-log: more responsive, incremental 'git log -L'","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:17Z","receivedAt":"2020-05-11T11:56:41Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nThe current line-level log implementation performs a preprocessing\nstep in prepare_revision_walk(), during which the line_log_filter()\nfunction filters and rewrites history to keep only commits modifying\nthe given line range. This preprocessing affects both responsiveness\nand correctness:\n\n - Git doesn't produce any output during this preprocessing step.\n Checking whether a commit modified the given line range is\n somewhat expensive, so depending on the size of the given revision\n range this preprocessing can result in a significant delay before\n the first commit is shown.\n\n - Limiting the number of displayed commits (e.g. 'git log -3 -L...')\n doesn't limit the amount of work during preprocessing, because\n that limit is applied during history traversal. Alas, by that\n point this expensive preprocessing step has already churned\n through the whole revision range to find all commits modifying the\n revision range, even though only a few of them need to be shown.\n\n - It rewrites parents, with no way to turn it off. Without the user\n explicitly requesting parent rewriting any parent object ID shown\n should be that of the immediate parent, just like in case of a\n pathspec-limited history traversal without parent rewriting.\n\n However, after that preprocessing step rewrote history, the\n subsequent \"regular\" history traversal (i.e. get_revision() in a\n loop) only sees commits modifying the given line range.\n Consequently, it can only show the object ID of the last ancestor\n that modified the given line range (which might happen to be the\n immediate parent, but many-many times it isn't).\n\nThis patch addresses both the correctness and, at least for the common\ncase, the responsiveness issues by integrating line-level log\nfiltering into the regular revision walking machinery:\n\n - Make process_ranges_arbitrary_commit(), the static function in\n 'line-log.c' deciding whether a commit modifies the given line\n range, public by removing the static keyword and adding the\n 'line_log_' prefix, so it can be called from other parts of the\n revision walking machinery.\n\n - If the user didn't explicitly ask for parent rewriting (which, I\n believe, is the most common case):\n\n - Call this now-public function during regular history traversal,\n namely from get_commit_action() to ignore any commits not\n modifying the given line range.\n\n Note that while this check is relatively expensive, it must be\n performed before other, much cheaper conditions, because the\n tracked line range must be adjusted even when the commit will\n end up being ignored by other conditions.\n\n - Skip the line_log_filter() call, i.e. the expensive\n preprocessing step, in prepare_revision_walk(), because, thanks\n to the above points, the revision walking machinery is now able\n to filter out commits not modifying the given line range while\n traversing history.\n\n This way the regular history traversal sees the unmodified\n history, and is therefore able to print the object ids of the\n immediate parents of the listed commits. The eliminated\n preprocessing step can greatly reduce the delay before the first\n commit is shown, see the numbers below.\n\n - However, if the user did explicitly ask for parent rewriting via\n '--parents' or a similar option, then stick with the current\n implementation for now, i.e. perform that expensive filtering and\n history rewriting in the preprocessing step just like we did\n before, leaving the initial delay as long as it was.\n\nI tried to integrate line-level log filtering with parent rewriting\ninto the regular history traversal, but, unfortunately, several\nsubtleties resisted... :) Maybe someday we'll figure out how to do\nthat, but until then at least the simple and common (i.e. without\nparent rewriting) 'git log -L:func:file' commands can benefit from the\nreduced delay.\n\nThis change makes the failing 'parent oids without parent rewriting'\ntest in 't4211-line-log.sh' succeed.\n\nThe reduced delay is most noticable when there's a commit modifying\nthe line range near the tip of a large-ish revision range:\n\n # no parent rewriting requested, no commit-graph present\n $ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0\n\n Before:\n\n real 0m9.570s\n user 0m9.494s\n sys 0m0.076s\n\n After:\n\n real 0m0.718s\n user 0m0.674s\n sys 0m0.044s\n\nA significant part of the remaining delay is spent reading and parsing\ncommit objects in limit_list(). With the help of the commit-graph we\ncan eliminate most of that reading and parsing overhead, so here are\nthe timing results of the same command as above, but this time using\nthe commit-graph:\n\n Before:\n\n real 0m8.874s\n user 0m8.816s\n sys 0m0.057s\n\n After:\n\n real 0m0.107s\n user 0m0.091s\n sys 0m0.013s\n\nThe next patch will further reduce the remaining delay.\n\nTo be clear: this patch doesn't actually optimize the line-level log,\nbut merely moves most of the work from the preprocessing step to the\nhistory traversal, so the commits modifying the line range can be\nshown as soon as they are processed, and the traversal can be\nterminated as soon as the given number of commits are shown.\nConsequently, listing the full history of a line range, potentially\nall the way to the root commit, will take the same time as before (but\nat least the user might start reading the output earlier).\nFurthermore, if the most recent commit modifying the line range is far\naway from the starting revision, then that initial delay will still be\nsignificant.\n\nAdditional testing by Derrick Stolee: In the Linux kernel repository,\nthe MAINTAINERS file was changed ~3,500 times across the ~915,000\ncommits. In addition to that edit frequency, the file itself is quite\nlarge (~18,700 lines). This means that a significant portion of the\ncomputation is taken up by computing the patch-diff of the file. This\npatch improves the real time it takes to output the first result quite\na bit:\n\nCommand: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 3.88 s\n After: 0.71 s\n\nIf we drop the \"-n 1\" in the command, then there is no change in\nend-to-end process time. This is because the command still needs to\nwalk the entire commit history, which negates the point of this\npatch. This is expected.\n\nAs a note for future reference, the ~4.3 seconds in the old code\nspends ~2.6 seconds computing the patch-diffs, and the rest of the\ntime is spent walking commits and computing diffs for which paths\nchanged at each commit. The changed-path Bloom filters could improve\nthe end-to-end computation time (i.e. no \"-n 1\" in the command).\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n line-log.c | 4 ++--\n line-log.h | 2 ++\n revision.c | 27 ++++++++++++++++++++++++++-\n t/t4211-line-log.sh | 2 +-\n 4 files changed, 31 insertions(+), 4 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 9010e00950b..520ee715bcd 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -1227,7 +1227,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n \t/* NEEDSWORK leaking like a sieve */\n }\n \n-static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n+int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n {\n \tstruct line_log_data *range = lookup_line_range(rev, commit);\n \tint changed = 0;\n@@ -1270,7 +1270,7 @@ int line_log_filter(struct rev_info *rev)\n \twhile (list) {\n \t\tstruct commit_list *to_free = NULL;\n \t\tcommit = list->item;\n-\t\tif (process_ranges_arbitrary_commit(rev, commit)) {\n+\t\tif (line_log_process_ranges_arbitrary_commit(rev, commit)) {\n \t\t\t*pp = list;\n \t\t\tpp = &list->next;\n \t\t} else\ndiff --git a/line-log.h b/line-log.h\nindex 882c5055bb8..82ae8d98a40 100644\n--- a/line-log.h\n+++ b/line-log.h\n@@ -54,6 +54,8 @@ struct line_log_data {\n void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args);\n \n int line_log_filter(struct rev_info *rev);\n+int line_log_process_ranges_arbitrary_commit(struct rev_info *rev,\n+\t\t\t\t\t\t struct commit *commit);\n \n int line_log_print(struct rev_info *rev, struct commit *commit);\n \ndiff --git a/revision.c b/revision.c\nindex f78c636e4d0..3228db9af6d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -39,6 +39,8 @@ static const char *term_good;\n \n implement_shared_commit_slab(revision_sources, char *);\n \n+static inline int want_ancestry(const struct rev_info *revs);\n+\n void show_object_with_name(FILE *out, struct object *obj, const char *name)\n {\n \tconst char *p;\n@@ -3511,7 +3513,14 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\tsort_in_topological_order(&revs->commits, revs->sort_order);\n \t} else if (revs->topo_order)\n \t\tinit_topo_walk(revs);\n-\tif (revs->line_level_traverse)\n+\tif (revs->line_level_traverse && want_ancestry(revs))\n+\t\t/*\n+\t\t * At the moment we can only do line-level log with parent\n+\t\t * rewriting by performing this expensive pre-filtering step.\n+\t\t * If parent rewriting is not requested, then we rather\n+\t\t * perform the line-level log filtering during the regular\n+\t\t * history traversal.\n+\t\t */\n \t\tline_log_filter(revs);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n@@ -3722,6 +3731,22 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi\n \t\treturn commit_ignore;\n \tif (commit->object.flags & UNINTERESTING)\n \t\treturn commit_ignore;\n+\tif (revs->line_level_traverse && !want_ancestry(revs)) {\n+\t\t/*\n+\t\t * In case of line-level log with parent rewriting\n+\t\t * prepare_revision_walk() already took care of all line-level\n+\t\t * log filtering, and there is nothing left to do here.\n+\t\t *\n+\t\t * If parent rewriting was not requested, then this is the\n+\t\t * place to perform the line-level log filtering. Notably,\n+\t\t * this check, though expensive, must come before the other,\n+\t\t * cheaper filtering conditions, because the tracked line\n+\t\t * ranges must be adjusted even when the commit will end up\n+\t\t * being ignored based on other conditions.\n+\t\t */\n+\t\tif (!line_log_process_ranges_arbitrary_commit(revs, commit))\n+\t\t\treturn commit_ignore;\n+\t}\n \tif (revs->min_age != -1 &&\n \t comparison_date(revs, commit) > revs->min_age)\n \t\t\treturn commit_ignore;\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex ea4a9398365..1428eae2629 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -263,7 +263,7 @@ test_expect_success 'setup for checking line-log and parent oids' '\n '\n \n # Parent oid should be from immediate parent.\n-test_expect_failure 'parent oids without parent rewriting' '\n+test_expect_success 'parent oids without parent rewriting' '\n \tcat >expect <<-EOF &&\n \t$head_oid $prev_oid Modify func2() in file.c\n \t$root_oid Add func1() and func2() in file.c\n-- \ngitgitgadget\n\n"},{"id":"397542","messageId":"305f1eb0982021e22526ca5b5bef141364a1131f.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 12/12] line-log: integrate with changed-path Bloom filters","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:19Z","receivedAt":"2020-05-11T11:56:44Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous changes to the line-log machinery focused on making the\nfirst result appear faster. This was achieved by no longer walking the\nentire commit history before returning the early results. There is still\nanother way to improve the performance: walk most commits much faster.\nLet's use the changed-path Bloom filters to reduce time spent computing\ndiffs.\n\nSince the line-log computation requires opening blobs and checking the\ncontent-diff, there is still a lot of necessary computation that cannot\nbe replaced with changed-path Bloom filters. The part that we can reduce\nis most effective when checking the history of a file that is deep in\nseveral directories and those directories are modified frequently. In\nthis case, the computation to check if a commit is TREESAME to its first\nparent takes a large fraction of the time. That is ripe for improvement\nwith changed-path Bloom filters.\n\nWe must ensure that prepare_to_use_bloom_filters() is called in\nrevision.c so that the bloom_filter_settings are loaded into the struct\nrev_info from the commit-graph. Of course, some cases are still\nforbidden, but in the line-log case the pathspec is provided in a\ndifferent way than normal.\n\nSince multiple paths and segments could be requested, we compute the\nstruct bloom_key data dynamically during the commit walk. This could\nlikely be improved, but adds code complexity that is not valuable at\nthis time.\n\nThere are two cases to care about: merge commits and \"ordinary\" commits.\nMerge commits have multiple parents, but if we are TREESAME to our first\nparent in every range, then pass the blame for all ranges to the first\nparent. Ordinary commits have the same condition, but each is done\nslightly differently in the process_ranges_[merge|ordinary]_commit()\nmethods. By checking if the changed-path Bloom filter can guarantee\nTREESAME, we can avoid that tree-diff cost. If the filter says \"probably\nchanged\", then we need to run the tree-diff and then the blob-diff if\nthere was a real edit.\n\nThe Linux kernel repository is a good testing ground for the performance\nimprovements claimed here. There are two different cases to test. The\nfirst is the \"entire history\" case, where we output the entire history\nto /dev/null to see how long it would take to compute the full line-log\nhistory. The second is the \"first result\" case, where we find how long\nit takes to show the first value, which is an indicator of how quickly a\nuser would see responses when waiting at a terminal.\n\nTo test, I selected the paths that were changed most frequently in the\ntop 10,000 commits using this command (stolen from StackOverflow [1]):\n\n\tgit log --pretty=format: --name-only -n 10000 | sort | \\\n\t\tuniq -c | sort -rg | head -10\n\nwhich results in\n\n 121 MAINTAINERS\n 63 fs/namei.c\n 60 arch/x86/kvm/cpuid.c\n 59 fs/io_uring.c\n 58 arch/x86/kvm/vmx/vmx.c\n 51 arch/x86/kvm/x86.c\n 45 arch/x86/kvm/svm.c\n 42 fs/btrfs/disk-io.c\n 42 Documentation/scsi/index.rst\n\n(along with a bogus first result). It appears that the path\narch/x86/kvm/svm.c was renamed, so we ignore that entry. This leaves the\nfollowing results for the real command time:\n\n| | Entire History | First Result |\n| Path | Before | After | Before | After |\n|------------------------------|--------|--------|--------|--------|\n| MAINTAINERS | 4.26 s | 3.87 s | 0.41 s | 0.39 s |\n| fs/namei.c | 1.99 s | 0.99 s | 0.42 s | 0.21 s |\n| arch/x86/kvm/cpuid.c | 5.28 s | 1.12 s | 0.16 s | 0.09 s |\n| fs/io_uring.c | 4.34 s | 0.99 s | 0.94 s | 0.27 s |\n| arch/x86/kvm/vmx/vmx.c | 5.01 s | 1.34 s | 0.21 s | 0.12 s |\n| arch/x86/kvm/x86.c | 2.24 s | 1.18 s | 0.21 s | 0.14 s |\n| fs/btrfs/disk-io.c | 1.82 s | 1.01 s | 0.06 s | 0.05 s |\n| Documentation/scsi/index.rst | 3.30 s | 0.89 s | 1.46 s | 0.03 s |\n\nIt is worth noting that the least speedup comes for the MAINTAINERS file\nwhich is\n\n * edited frequently,\n * low in the directory heirarchy, and\n * quite a large file.\n\nAll of those points lead to spending more time doing the blob diff and\nless time doing the tree diff. Still, we see some improvement in that\ncase and significant improvement in other cases. A 2-4x speedup is\nlikely the more typical case as opposed to the small 5% change for that\nfile.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 5 +++++\n bloom.h | 1 +\n line-log.c | 39 ++++++++++++++++++++++++++++++++++++++-\n revision.c | 5 ++++-\n 4 files changed, 48 insertions(+), 2 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex e2ede44126c..c38d1cff0c6 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -138,6 +138,11 @@ void fill_bloom_key(const char *data,\n \t\tkey->hashes[i] = hash0 + i * hash1;\n }\n \n+void clear_bloom_key(struct bloom_key *key)\n+{\n+\tFREE_AND_NULL(key->hashes);\n+}\n+\n void add_key_to_filter(const struct bloom_key *key,\n \t\t struct bloom_filter *filter,\n \t\t const struct bloom_filter_settings *settings)\ndiff --git a/bloom.h b/bloom.h\nindex a51e3715296..d0c69172e67 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -72,6 +72,7 @@ void fill_bloom_key(const char *data,\n \t\t size_t len,\n \t\t struct bloom_key *key,\n \t\t const struct bloom_filter_settings *settings);\n+void clear_bloom_key(struct bloom_key *key);\n \n void add_key_to_filter(const struct bloom_key *key,\n \t\t struct bloom_filter *filter,\ndiff --git a/line-log.c b/line-log.c\nindex 520ee715bcd..7dc411da8f6 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -15,6 +15,7 @@\n #include \"userdiff.h\"\n #include \"line-log.h\"\n #include \"argv-array.h\"\n+#include \"bloom.h\"\n \n static void range_set_grow(struct range_set *rs, size_t extra)\n {\n@@ -1146,6 +1147,37 @@ int line_log_print(struct rev_info *rev, struct commit *commit)\n \treturn 1;\n }\n \n+static int bloom_filter_check(struct rev_info *rev,\n+\t\t\t struct commit *commit,\n+\t\t\t struct line_log_data *range)\n+{\n+\tstruct bloom_filter *filter;\n+\tstruct bloom_key key;\n+\tint result = 0;\n+\n+\tif (!commit->parents)\n+\t\treturn 1;\n+\n+\tif (!rev->bloom_filter_settings ||\n+\t !(filter = get_bloom_filter(rev->repo, commit, 0)))\n+\t\treturn 1;\n+\n+\tif (!range)\n+\t\treturn 0;\n+\n+\twhile (!result && range) {\n+\t\tfill_bloom_key(range->path, strlen(range->path), &key, rev->bloom_filter_settings);\n+\n+\t\tif (bloom_filter_contains(filter, &key, rev->bloom_filter_settings))\n+\t\t\tresult = 1;\n+\n+\t\tclear_bloom_key(&key);\n+\t\trange = range->next;\n+\t}\n+\n+\treturn result;\n+}\n+\n static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,\n \t\t\t\t\t struct line_log_data *range)\n {\n@@ -1159,6 +1191,7 @@ static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *c\n \n \tqueue_diffs(range, &rev->diffopt, &queue, commit, parent);\n \tchanged = process_all_files(&parent_range, rev, &queue, range);\n+\n \tif (parent)\n \t\tadd_line_range(rev, parent, parent_range);\n \tfree_line_log_data(parent_range);\n@@ -1233,7 +1266,11 @@ int line_log_process_ranges_arbitrary_commit(struct rev_info *rev, struct commit\n \tint changed = 0;\n \n \tif (range) {\n-\t\tif (!commit->parents || !commit->parents->next)\n+\t\tif (commit->parents && !bloom_filter_check(rev, commit, range)) {\n+\t\t\tstruct line_log_data *prange = line_log_data_copy(range);\n+\t\t\tadd_line_range(rev, commit->parents->item, prange);\n+\t\t\tclear_commit_line_range(rev, commit);\n+\t\t} else if (!commit->parents || !commit->parents->next)\n \t\t\tchanged = process_ranges_ordinary_commit(rev, commit, range);\n \t\telse\n \t\t\tchanged = process_ranges_merge_commit(rev, commit, range);\ndiff --git a/revision.c b/revision.c\nindex 3356ede9a20..cbf4b61aa67 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -689,6 +689,9 @@ static void prepare_to_use_bloom_filter(struct rev_info *revs)\n \tif (!revs->bloom_filter_settings)\n \t\treturn;\n \n+\tif (!revs->pruning.pathspec.nr)\n+\t\treturn;\n+\n \tpi = &revs->pruning.pathspec.items[0];\n \tlast_index = pi->len - 1;\n \n@@ -3501,7 +3504,7 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\t\t FOR_EACH_OBJECT_PROMISOR_ONLY);\n \t}\n \n-\tif (revs->pruning.pathspec.nr == 1 && !revs->reflog_info)\n+\tif (!revs->reflog_info)\n \t\tprepare_to_use_bloom_filter(revs);\n \tif (revs->no_walk != REVISION_WALK_NO_WALK_UNSORTED)\n \t\tcommit_list_sort_by_date(&revs->commits);\n-- \ngitgitgadget\n"},{"id":"397543","messageId":"da087d2acbb83a7056427d237627188744bbd3a2.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 11/12] line-log: try to use generation number-based topo-ordering","fromName":"SZEDER Gábor via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:18Z","receivedAt":"2020-05-11T11:56:44Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= \n\nThe previous patch made it possible to perform line-level filtering\nduring history traversal instead of in an expensive preprocessing\nstep, but it still requires some simpler preprocessing steps, notably\ntopo-ordering. However, nowadays we have commit-graphs storing\ngeneration numbers, which make it possible to incrementally traverse\nthe history in topological order, without the preparatory limit_list()\nand sort_in_topological_order() steps; see b45424181e (revision.c:\ngeneration-based topo-order algorithm, 2018-11-01).\n\nThis patch combines the two, so we can do both the topo-ordering and\nthe line-level filtering during history traversal, eliminating even\nthose simpler preprocessing steps, and thus further reducing the delay\nbefore showing the first commit modifying the given line range.\n\nThe 'revs->limited' flag plays the central role in this, because, due\nto limitations of the current implementation, the generation\nnumber-based topo-ordering is only enabled when this flag remains\nunset. Line-level log, however, always sets this flag in\nsetup_revisions() ever since the feature was introduced in 12da1d1f6f\n(Implement line-history search (git log -L), 2013-03-28). The reason\nfor setting 'limited' is unclear, though, because the line-level log\nitself doesn't directly depend on it, and it doesn't affect how the\nlimit_list() function limits the revision range. However, there is an\nindirect dependency: the line-level log requires topo-ordering, and\nthe \"traditional\" sort_in_topological_order() requires an already\nlimited commit list since e6c3505b44 (Make sure we generate the whole\ncommit list before trying to sort it topologically, 2005-07-06). The\nnew, generation numbers-based topo-ordering doesn't require a limited\ncommit list anymore.\n\nSo don't set 'revs->limited' for line-level log, unless it is really\nnecessary, namely:\n\n - The user explicitly requested parent rewriting, because that is\n still done in the line_log_filter() preprocessing step (see\n previous patch), which requires sort_in_topological_order() and in\n turn limit_list() as well.\n\n - A commit-graph file is not available or it doesn't yet contain\n generation numbers. In these cases we had to fall back on\n sort_in_topological_order() and in turn limit_list(). The\n existing condition with generation_numbers_enabled() has already\n ensured that the 'limited' flag is set in these cases; this patch\n just makes sure that the line-level log sets 'revs->topo_order'\n before that condition.\n\nWhile the reduced delay before showing the first commit is measurable\nin git.git, it takes a bigger repository to make it clearly noticable.\nIn both cases below the line ranges were chosen so that they were\nmodified rather close to the starting revisions, so the effect of this\nchange is most noticable.\n\n # git.git\n $ time git --no-pager log -L:read_alternate_refs:sha1-file.c -1 v2.23.0\n\n Before:\n\n real 0m0.107s\n user 0m0.091s\n sys 0m0.013s\n\n After:\n\n real 0m0.058s\n user 0m0.050s\n sys 0m0.005s\n\n # linux.git\n $ time git --no-pager log \\\n -L:build_restore_work_registers:arch/mips/mm/tlbex.c -1 v5.2\n\n Before:\n\n real 0m1.129s\n user 0m1.061s\n sys 0m0.069s\n\n After:\n\n real 0m0.096s\n user 0m0.087s\n sys 0m0.009s\n\nAdditional testing by Derrick Stolee: Since this patch improves\nthe performance for the first result, I repeated the experiment\nfrom the previous patch on the Linux kernel repository, reporting\nreal time here:\n\n Command: git log -L 100,200:MAINTAINERS -n 1 >/dev/null\n Before: 0.71 s\n After: 0.05 s\n\nNow, we have dropped the full topo-order of all ~910,000 commits\nbefore reporting the first result. The remaining performance\nimprovements then are:\n\n 1. Update the parent-rewriting logic to be incremental similar to\n how \"git log --graph\" behaves.\n\n 2. Use changed-path Bloom filters to reduce the time spend in the\n tree-diff to see if the path(s) changed.\n\nSigned-off-by: SZEDER Gábor \nSigned-off-by: Derrick Stolee \n---\n revision.c | 11 ++++++-----\n 1 file changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 3228db9af6d..3356ede9a20 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2790,6 +2790,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \tif (revs->diffopt.objfind)\n \t\trevs->simplify_history = 0;\n \n+\tif (revs->line_level_traverse) {\n+\t\tif (want_ancestry(revs))\n+\t\t\trevs->limited = 1;\n+\t\trevs->topo_order = 1;\n+\t}\n+\n \tif (revs->topo_order && !generation_numbers_enabled(the_repository))\n \t\trevs->limited = 1;\n \n@@ -2809,11 +2815,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \n \trevs->diffopt.abbrev = revs->abbrev;\n \n-\tif (revs->line_level_traverse) {\n-\t\trevs->limited = 1;\n-\t\trevs->topo_order = 1;\n-\t}\n-\n \tdiff_setup_done(&revs->diffopt);\n \n \tgrep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,\n-- \ngitgitgadget\n\n"},{"id":"397544","messageId":"8278b5c0918c6b357e1f1ab3ee65ed2091ec3f61.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 06/12] bloom: use num_changes not nr for limit detection","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:13Z","receivedAt":"2020-05-11T11:56:47Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAs diff_tree_oid() computes a diff, it will terminate early if the\ntotal number of changed paths is strictly larger than max_changes.\nThis includes the directories that changed, not just the file paths.\nHowever, only the file paths are reflected in the resulting diff\nqueue's \"nr\" value.\n\nUse the \"num_changes\" from diffopt to check if the diff terminated\nearly. This is incredibly important, as it can result in incorrect\nfilters! For example, the first commit in the Linux kernel repo\nreports only 471 changes, but since these are nested inside several\ndirectories they expand to 513 \"real\" changes, and in fact the\ntotal list of changes is not reported. Thus, the computed filter\nfor this commit is incorrect.\n\nDemonstrate the subtle difference by using one fewer file change\nin the 'get bloom filter for commit with 513 changes' test. Before,\nthis edited 513 files inside \"bigDir\" which hit this inequality.\nHowever, dropping the file count by one demonstrates how the\nprevious inequality was incorrect but the new one is correct.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 2 +-\n t/t0095-bloom.sh | 2 +-\n 2 files changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex 196cda0a1bd..e2ede44126c 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -215,7 +215,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\tdiff_tree_oid(NULL, &c->object.oid, \"\", &diffopt);\n \tdiffcore_std(&diffopt);\n \n-\tif (diff_queued_diff.nr <= max_changes) {\n+\tif (diffopt.num_changes <= max_changes) {\n \t\tstruct hashmap pathmap;\n \t\tstruct pathmap_hash_entry *e;\n \t\tstruct hashmap_iter iter;\ndiff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\nindex 6defeb544f1..48a90625596 100755\n--- a/t/t0095-bloom.sh\n+++ b/t/t0095-bloom.sh\n@@ -100,7 +100,7 @@ test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '\n \trm actual &&\n \trm expect &&\n \tmkdir bigDir &&\n-\tfor i in $(test_seq 0 512)\n+\tfor i in $(test_seq 0 511)\n \tdo\n \t\techo $i >bigDir/$i\n \tdone &&\n-- \ngitgitgadget\n\n"},{"id":"397545","messageId":"89625b0efae43c8cb0d444a843d389d6cb9f6772.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 01/12] bloom: fix whitespace around tab length","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:08Z","receivedAt":"2020-05-11T11:56:48Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nFix alignment issues that were likely introduced due to an editor\nusing tab lengths of 4 instead of 8.\n\nSigned-off-by: Derrick Stolee \n---\n bloom.c | 16 ++++++++--------\n bloom.h | 4 ++--\n 2 files changed, 10 insertions(+), 10 deletions(-)\n\ndiff --git a/bloom.c b/bloom.c\nindex dd9bab9bbd6..2e3e0f5037b 100644\n--- a/bloom.c\n+++ b/bloom.c\n@@ -29,8 +29,8 @@ static inline unsigned char get_bitmask(uint32_t pos)\n }\n \n static int load_bloom_filter_from_graph(struct commit_graph *g,\n-\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t struct commit *c)\n+\t\t\t\t\tstruct bloom_filter *filter,\n+\t\t\t\t\tstruct commit *c)\n {\n \tuint32_t lex_pos, start_index, end_index;\n \n@@ -123,9 +123,9 @@ uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)\n }\n \n void fill_bloom_key(const char *data,\n-\t\t\t\t\tsize_t len,\n-\t\t\t\t\tstruct bloom_key *key,\n-\t\t\t\t\tconst struct bloom_filter_settings *settings)\n+\t\t size_t len,\n+\t\t struct bloom_key *key,\n+\t\t const struct bloom_filter_settings *settings)\n {\n \tint i;\n \tconst uint32_t seed0 = 0x293ae76f;\n@@ -139,8 +139,8 @@ void fill_bloom_key(const char *data,\n }\n \n void add_key_to_filter(const struct bloom_key *key,\n-\t\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t\t const struct bloom_filter_settings *settings)\n+\t\t struct bloom_filter *filter,\n+\t\t const struct bloom_filter_settings *settings)\n {\n \tint i;\n \tuint64_t mod = filter->len * BITS_PER_WORD;\n@@ -160,7 +160,7 @@ void init_bloom_filters(void)\n \n struct bloom_filter *get_bloom_filter(struct repository *r,\n \t\t\t\t struct commit *c,\n-\t\t\t\t\t int compute_if_not_present)\n+\t\t\t\t int compute_if_not_present)\n {\n \tstruct bloom_filter *filter;\n \tstruct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;\ndiff --git a/bloom.h b/bloom.h\nindex b935186425d..a51e3715296 100644\n--- a/bloom.h\n+++ b/bloom.h\n@@ -74,8 +74,8 @@ void fill_bloom_key(const char *data,\n \t\t const struct bloom_filter_settings *settings);\n \n void add_key_to_filter(const struct bloom_key *key,\n-\t\t\t\t\t struct bloom_filter *filter,\n-\t\t\t\t\t const struct bloom_filter_settings *settings);\n+\t\t struct bloom_filter *filter,\n+\t\t const struct bloom_filter_settings *settings);\n \n void init_bloom_filters(void);\n \n-- \ngitgitgadget\n\n"},{"id":"397546","messageId":"61f78a2b0dd7d8e8ca04ce2e1681bd14ba81c1b9.1589198180.git.gitgitgadget@gmail.com","threadId":"53367","inReplyTo":"pull.622.v2.git.1589198180.gitgitgadget@gmail.com","subject":"[PATCH v2 04/12] Documentation: changed-path Bloom filters use byte words","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2020-05-11T11:56:11Z","receivedAt":"2020-05-11T11:56:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nIn Documentation/technical/commit-graph-format.txt, the definition\nof the BIDX chunk specifies the length is a number of 8-byte words.\nDuring development we discovered that using 8-byte words in the\nMurmur3 hash algorithm causes issues with big-endian versus little-\nendian machines. Thus, the hash algorithm was adapted to work on a\nbyte-by-byte basis. However, this caused a change in the definition\nof a \"word\" in bloom.h. Now, a \"word\" is a single byte, which allows\nfilters to be as small as two bytes. These length-two filters are\ndemonstrated in t0095-bloom.sh, and a larger filter of length 25 is\ndemonstrated as well.\n\nThe original point of using 8-byte words was for alignment reasons.\nIt also presented opportunities for extremely sparse Bloom filters\nwhen there were a small number of changes at a commit, creating a\nvery low false-positive rate. However, modifying the format at this\npoint is unlikely to be a valuable exercise. Also, this use of\nsingle-byte granularity does present opportunities to save space.\nIt is unclear if 8-byte alignment of the filters would present any\nmeaningful performance benefits.\n\nModify the format document to reflect reality.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/technical/commit-graph-format.txt | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/Documentation/technical/commit-graph-format.txt b/Documentation/technical/commit-graph-format.txt\nindex de56f9f1efd..1beef171822 100644\n--- a/Documentation/technical/commit-graph-format.txt\n+++ b/Documentation/technical/commit-graph-format.txt\n@@ -97,10 +97,10 @@ CHUNK DATA:\n bit on. The other bits correspond to the position of the last parent.\n \n Bloom Filter Index (ID: {'B', 'I', 'D', 'X'}) (N * 4 bytes) [Optional]\n- * The ith entry, BIDX[i], stores the number of 8-byte word blocks in all\n- Bloom filters from commit 0 to commit i (inclusive) in lexicographic\n- order. The Bloom filter for the i-th commit spans from BIDX[i-1] to\n- BIDX[i] (plus header length), where BIDX[-1] is 0.\n+ * The ith entry, BIDX[i], stores the number of bytes in all Bloom filters\n+ from commit 0 to commit i (inclusive) in lexicographic order. The Bloom\n+ filter for the i-th commit spans from BIDX[i-1] to BIDX[i] (plus header\n+ length), where BIDX[-1] is 0.\n * The BIDX chunk is ignored if the BDAT chunk is not present.\n \n Bloom Filter Data (ID: {'B', 'D', 'A', 'T'}) [Optional]\n-- \ngitgitgadget\n\n"},{"id":"399266","messageId":"20200607214550.GA22200@szeder.dev","threadId":"53367","inReplyTo":"ba0d8c1f539751d9cfd556dac4eeda97758cf12e.1589198180.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 05/12] bloom: de-duplicate directory entries","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-06-07T21:45:50Z","receivedAt":"2020-06-07T21:46:00Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, May 11, 2020 at 11:56:12AM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> When computing a changed-path Bloom filter, we need to take the\n> files that changed from the diff computation and extract the parent\n> directories. That way, a directory pathspec such as \"Documentation\"\n> could match commits that change \"Documentation/git.txt\".\n> \n> However, the current code does a poor job of this process. The paths\n> are added to a hashmap, but we do not check if an entry already\n> exists with that path. This can create many duplicate entries and\n> cause the filter to have a much larger length than it should. This\n> means that the filter is more sparse than intended, which helps the\n> false positive rate, but wastes a lot of space.\n> \n> Properly use hashmap_get() before hashmap_add(). Also be sure to\n> include a comparison function so these can be matched correctly.\n> \n> This has an effect on a test in t0095-bloom.sh. This makes sense,\n> there are ten changes inside \"smallDir\" so the total number of\n> paths in the filter should be 11. This would result in 11 * 10 bits\n> required, and with 8 bits per byte, this results in 14 bytes.\n\nThis is the first patch where the chunk format and the specs are in\nsync and the Bloom filters are as large as promised, so it would have\nbeen nice to see how the false positive rate, the runtime of\npathspec-limited revision walks, and the size of the Bloom filters\nchunk or the commit-graph file turned out...\n\n> Signed-off-by: Derrick Stolee \n> ---\n> bloom.c | 35 ++++++++++++++++++++++++++---------\n> t/t0095-bloom.sh | 4 ++--\n> 2 files changed, 28 insertions(+), 11 deletions(-)\n> \n> diff --git a/bloom.c b/bloom.c\n> index 96792782719..196cda0a1bd 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -158,6 +158,19 @@ void init_bloom_filters(void)\n> \tinit_bloom_filter_slab(&bloom_filters);\n> }\n> \n> +static int pathmap_cmp(const void *hashmap_cmp_fn_data,\n> +\t\t const struct hashmap_entry *eptr,\n> +\t\t const struct hashmap_entry *entry_or_key,\n> +\t\t const void *keydata)\n> +{\n> +\tconst struct pathmap_hash_entry *e1, *e2;\n> +\n> +\te1 = container_of(eptr, const struct pathmap_hash_entry, entry);\n> +\te2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);\n> +\n> +\treturn strcmp(e1->path, e2->path);\n> +}\n> +\n> struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\t\t\t struct commit *c,\n> \t\t\t\t int compute_if_not_present)\n> @@ -206,25 +219,29 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\tstruct hashmap pathmap;\n> \t\tstruct pathmap_hash_entry *e;\n> \t\tstruct hashmap_iter iter;\n> -\t\thashmap_init(&pathmap, NULL, NULL, 0);\n> +\t\thashmap_init(&pathmap, pathmap_cmp, NULL, 0);\n> \n> \t\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n> \t\t\tconst char *path = diff_queued_diff.queue[i]->two->path;\n> \n> \t\t\t/*\n> -\t\t\t* Add each leading directory of the changed file, i.e. for\n> -\t\t\t* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n> -\t\t\t* the Bloom filter could be used to speed up commands like\n> -\t\t\t* 'git log dir/subdir', too.\n> -\t\t\t*\n> -\t\t\t* Note that directories are added without the trailing '/'.\n> -\t\t\t*/\n> +\t\t\t * Add each leading directory of the changed file, i.e. for\n> +\t\t\t * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so\n> +\t\t\t * the Bloom filter could be used to speed up commands like\n> +\t\t\t * 'git log dir/subdir', too.\n> +\t\t\t *\n> +\t\t\t * Note that directories are added without the trailing '/'.\n> +\t\t\t */\n> \t\t\tdo {\n> \t\t\t\tchar *last_slash = strrchr(path, '/');\n> \n> \t\t\t\tFLEX_ALLOC_STR(e, path, path);\n\nAllocating a hashmap entry each time we query whether a path is\nalready present in the hashmap has some overhead. It's cheaper to\ncreate an entry on the stack just for the query and allocate an entry\non the heap only if the path isn't in the map.\n\nDeduplicating without a hashmap is faster still.\n\n> \t\t\t\thashmap_entry_init(&e->entry, strhash(path));\n> -\t\t\t\thashmap_add(&pathmap, &e->entry);\n> +\n> +\t\t\t\tif (!hashmap_get(&pathmap, &e->entry, NULL))\n> +\t\t\t\t\thashmap_add(&pathmap, &e->entry);\n> +\t\t\t\telse\n> +\t\t\t\t\tfree(e);\n> \n> \t\t\t\tif (!last_slash)\n> \t\t\t\t\tlast_slash = (char*)path;\n> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> index 8f9eef116dc..6defeb544f1 100755\n> --- a/t/t0095-bloom.sh\n> +++ b/t/t0095-bloom.sh\n> @@ -89,8 +89,8 @@ test_expect_success 'get bloom filter for commit with 10 changes' '\n> \tgit add smallDir &&\n> \tgit commit -m \"commit with 10 changes\" &&\n> \tcat >expect <<-\\EOF &&\n> -\tFilter_Length:25\n> -\tFilter_Data:82|a0|65|47|0c|92|90|c0|a1|40|02|a0|e2|40|e0|04|0a|9a|66|cf|80|19|85|42|23|\n> +\tFilter_Length:14\n> +\tFilter_Data:02|b3|c4|a0|34|e7|fe|eb|cb|47|fe|a0|e8|72|\n> \tEOF\n> \ttest-tool bloom get_filter_for_commit \"$(git rev-parse HEAD)\" >actual &&\n> \ttest_cmp expect actual\n> -- \n> gitgitgadget\n> \n"},{"id":"402817","messageId":"20200804145144.GQ2898@szeder.dev","threadId":"53367","inReplyTo":"8278b5c0918c6b357e1f1ab3ee65ed2091ec3f61.1589198180.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 06/12] bloom: use num_changes not nr for limit detection","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2020-08-04T14:51:44Z","receivedAt":"2020-08-04T14:51:53Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Mon, May 11, 2020 at 11:56:13AM +0000, Derrick Stolee via GitGitGadget wrote:\n> From: Derrick Stolee \n> \n> As diff_tree_oid() computes a diff, it will terminate early if the\n> total number of changed paths is strictly larger than max_changes.\n> This includes the directories that changed, not just the file paths.\n> However, only the file paths are reflected in the resulting diff\n> queue's \"nr\" value.\n> \n> Use the \"num_changes\" from diffopt to check if the diff terminated\n> early. This is incredibly important, as it can result in incorrect\n> filters! For example, the first commit in the Linux kernel repo\n> reports only 471 changes, but since these are nested inside several\n> directories they expand to 513 \"real\" changes, and in fact the\n> total list of changes is not reported. Thus, the computed filter\n> for this commit is incorrect.\n> \n> Demonstrate the subtle difference by using one fewer file change\n> in the 'get bloom filter for commit with 513 changes' test. Before,\n> this edited 513 files inside \"bigDir\" which hit this inequality.\n> However, dropping the file count by one demonstrates how the\n> previous inequality was incorrect but the new one is correct.\n> \n> Signed-off-by: Derrick Stolee \n> ---\n> bloom.c | 2 +-\n> t/t0095-bloom.sh | 2 +-\n> 2 files changed, 2 insertions(+), 2 deletions(-)\n> \n> diff --git a/bloom.c b/bloom.c\n> index 196cda0a1bd..e2ede44126c 100644\n> --- a/bloom.c\n> +++ b/bloom.c\n> @@ -215,7 +215,7 @@ struct bloom_filter *get_bloom_filter(struct repository *r,\n> \t\tdiff_tree_oid(NULL, &c->object.oid, \"\", &diffopt);\n> \tdiffcore_std(&diffopt);\n> \n> -\tif (diff_queued_diff.nr <= max_changes) {\n> +\tif (diffopt.num_changes <= max_changes) {\n\nThe field 'diffopt.num_changes' is marked with:\n\n /* For internal use only. */\n\n> \t\tstruct hashmap pathmap;\n> \t\tstruct pathmap_hash_entry *e;\n> \t\tstruct hashmap_iter iter;\n> diff --git a/t/t0095-bloom.sh b/t/t0095-bloom.sh\n> index 6defeb544f1..48a90625596 100755\n> --- a/t/t0095-bloom.sh\n> +++ b/t/t0095-bloom.sh\n> @@ -100,7 +100,7 @@ test_expect_success EXPENSIVE 'get bloom filter for commit with 513 changes' '\n> \trm actual &&\n> \trm expect &&\n> \tmkdir bigDir &&\n> -\tfor i in $(test_seq 0 512)\n> +\tfor i in $(test_seq 0 511)\n> \tdo\n> \t\techo $i >bigDir/$i\n> \tdone &&\n> -- \n> gitgitgadget\n> \n"}]}