{"thread":{"id":"64332","subject":"[PATCH] last-modified: implement faster algorithm","startedAt":"2025-10-16T08:39:46Z","lastAt":"2025-11-28T17:36:14Z","messageCount":39,"participants":["Toon Claes","Justin Tobler","D. Ben Knoble","Taylor Blau","Jeff King","Junio C Hamano","Anders Kaseorg","Kristoffer Haugsbakk"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"528943","messageId":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","threadId":"64332","inReplyTo":null,"subject":"[PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-16T08:39:25Z","receivedAt":"2025-10-16T08:39:46Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"The current implementation of git-last-modified(1) works by doing a\nrevision walk, and inspecting the diff at each level of that walk to\nannotate entries remaining in the hashmap of paths. In other words, if\nthe diff at some level touches a path which has not yet been associated\nwith a commit, then that commit becomes associated with the path.\n\nWhile a perfectly reasonable implementation, it can perform poorly in\neither one of two scenarios:\n\n  1. There are many entries of interest, in which case there is simply\n     a lot of work to do.\n\n  2. Or, there are (even a few) entries which have not been updated in a\n     long time, and so we must walk through a lot of history in order to\n     find a commit that touches that path.\n\nThis patch rewrites the last-modified implementation that addresses the\nsecond point. The idea behind the algorithm is to propagate a set of\n'active' paths (a path is 'active' if it does not yet belong to a\ncommit) up to parents and do a truncated revision walk.\n\nThe walk is truncated because it does not produce a revision for every\nchange in the original pathspec, but rather only for active paths.\n\nMore specifically, consider a priority queue of commits sorted by\ngeneration number. First, enqueue the set of boundary commits with all\npaths in the original spec marked as interesting.\n\nThen, while the queue is not empty, do the following:\n\n  1. Pop an element, say, 'c', off of the queue, making sure that 'c'\n     isn't reachable by anything in the '--not' set.\n\n  2. For each parent 'p' (with index 'parent_i') of 'c', do the\n     following:\n\n     a. Compute the diff between 'c' and 'p'.\n     b. Pass any active paths that are TREESAME from 'c' to 'p'.\n     c. If 'p' has any active paths, push it onto the queue.\n\n  3. Any path that remains active on 'c' is associated to that commit.\n\nThis ends up being equivalent to doing something like 'git log -1 --\n$path' for each path simultaneously. But, it allows us to go much faster\nthan the original implementation by limiting the number of diffs we\ncompute, since we can avoid parts of history that would have been\nconsidered by the revision walk in the original implementation, but are\nknown to be uninteresting to us because we have already marked all paths\nin that area to be inactive.\n\nTo avoid computing many first-parent diffs, add another trick on top of\nthis and check if all paths active in 'c' are DEFINITELY NOT in c's\nBloom filter. Since the commit-graph only stores first-parent diffs in\nthe Bloom filters, we can only apply this trick to first-parent diffs.\n\nComparing the performance of this new algorithm shows about a 2.6x\nimprovement on git.git:\n\n    Benchmark 1: master\n      Time (mean ± σ):      3.077 s ±  0.055 s    [User: 3.017 s, System: 0.051 s]\n      Range (min … max):    2.947 s …  3.127 s    10 runs\n\n    Benchmark 2: HEAD\n      Time (mean ± σ):      1.181 s ±  0.010 s    [User: 1.139 s, System: 0.038 s]\n      Range (min … max):    1.169 s …  1.194 s    10 runs\n\n    Summary\n      HEAD ran\n        2.60 ± 0.05 times faster than master\n\nBut when comparing a more extreme example of\n`git last-modified -- COPYING t`, the difference is a lot bigger:\n\n    Benchmark 1: master\n      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n      Range (min … max):    4.308 s …  4.509 s    10 runs\n\n    Benchmark 2: HEAD\n      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n      Range (min … max):   810.6 ms … 881.2 ms    10 runs\n\n    Summary\n      HEAD ran\n        5.29 ± 0.16 times faster than master\n\nAs an added benefit, this implementation gives more correct results. For\nexample implementation in 'master' gives:\n\n    $ git log --max-count=1 --format=%H -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\n\n    $ git last-modified -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n\n    $ git last-modified | grep pkt-line.h\n    5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n\nWith the changes in this patch the results of git-last-modified(1)\nalways match those of `git log --max-count=1`.\n\nOne thing to note though, the results might be outputted in a different\norder than before. This is not considerd to be an issue because nowhere\nis documented the order is guaranteed.\n\nBased-on-patches-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\nThe subcommand git-last-modified(1) was based on the patches shared by\nTaylor and the folks at GitHub[1]. That version used an alternative\nimplementation to make it \"go faster\". When I was working on upstreaming\nthose patches, I dropped the patches[2] for this implementation, because\nI didn't see significant improvements.\n\nThis series revives those changes. I did more thorough deep dive through\nthe code and the algorithm and got the code working a lot faster. The\nbenchmark results can be found in the commit message.\n\nSome changes compared to GitHub's version include:\n\n * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n   `struct commit_active_paths`.\n\n * Removed shortcut code that handled the case when commit and parent\n   are fully treesame, and instead always checked 'active_c' whether the\n   next parent is worth looking at.\n\n * Modified comments and commit message to make the algorithm more\n   clear (at least to me).\n\n * Mentioned the use of PARENT1 and PARENT2 in object.h.\n\n * Removed the use of any global variables.\n\n * Less conditions are checked in mark_path() because the hashmap of\n   'paths' is considered the single-source of truth.\n\n * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n   hashmap no more.\n\n[1]: https://lore.kernel.org/git/Z+XJ+1L3PnC9Dyba@nand.local/\n[2]: https://lore.kernel.org/git/20250630-toon-new-blame-tree-v3-0-3516025dc3bc@iotcl.com/\n---\n builtin/last-modified.c  | 252 ++++++++++++++++++++++++++++++++++++++++++++---\n object.h                 |   1 +\n t/t8020-last-modified.sh |   2 +-\n 3 files changed, 240 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex ae8b36a2c3..40e520ba18 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -2,26 +2,32 @@\n #include \"bloom.h\"\n #include \"builtin.h\"\n #include \"commit-graph.h\"\n+#include \"commit-slab.h\"\n #include \"commit.h\"\n #include \"config.h\"\n-#include \"environment.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"environment.h\"\n+#include \"ewah/ewok.h\"\n #include \"hashmap.h\"\n #include \"hex.h\"\n-#include \"log-tree.h\"\n #include \"object-name.h\"\n #include \"object.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n \n+/* Remember to update object flag allocation in object.h */\n+#define PARENT1 (1u<<16) /* used instead of SEEN */\n+#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n+\n struct last_modified_entry {\n \tstruct hashmap_entry hashent;\n \tstruct object_id oid;\n \tstruct bloom_key key;\n+\tsize_t diff_idx;\n \tconst char path[FLEX_ARRAY];\n };\n \n@@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n \treturn strcmp(ent1->path, path ? path : ent2->path);\n }\n \n+/*\n+ * Hold a bitmap for each commit we're working with. Each bit represents a path\n+ * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n+ */\n+define_commit_slab(commit_bitmaps, struct bitmap *);\n+\n struct last_modified {\n \tstruct hashmap paths;\n \tstruct rev_info rev;\n \tbool recursive;\n \tbool show_trees;\n+\n+\tconst char **all_paths;\n+\tsize_t all_paths_nr;\n+\tstruct commit_bitmaps commit_bitmaps;\n+\n+\t/* 'scratch' bitmap to avoid allocating every proccess_parent() */\n+\tstruct bitmap *scratch;\n };\n \n+static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);\n+\tif (!*bitmap)\n+\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n+\n+\treturn *bitmap;\n+}\n+\n static void last_modified_release(struct last_modified *lm)\n {\n \tstruct hashmap_iter iter;\n@@ -54,6 +82,8 @@ static void last_modified_release(struct last_modified *lm)\n \n \thashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent);\n \trelease_revisions(&lm->rev);\n+\n+\tfree(lm->all_paths);\n }\n \n struct last_modified_callback_data {\n@@ -196,7 +226,36 @@ static void last_modified_diff(struct diff_queue_struct *q,\n \t}\n }\n \n-static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n+static size_t path_idx(struct last_modified *lm, char *path)\n+{\n+\tstruct last_modified_entry *ent;\n+\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n+\t\t\t\t\t  struct last_modified_entry, hashent);\n+\n+\treturn ent ? ent->diff_idx : -1;\n+}\n+\n+static void pass_to_parent(struct last_modified *lm,\n+\t\t\t   struct bitmap *c,\n+\t\t\t   struct bitmap *p,\n+\t\t\t   size_t pos)\n+{\n+\tstruct last_modified_entry *ent;\n+\tstruct hashmap_iter iter;\n+\n+\tbitmap_unset(c, pos);\n+\n+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tif (ent->diff_idx == pos) {\n+\t\t\tbitmap_set(p, pos);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+}\n+\n+static bool maybe_changed_path(struct last_modified *lm,\n+\t\t\t       struct commit *origin,\n+\t\t\t       struct bitmap *active)\n {\n \tstruct bloom_filter *filter;\n \tstruct last_modified_entry *ent;\n@@ -213,6 +272,9 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \t\treturn true;\n \n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tif (active && !bitmap_get(active, ent->diff_idx))\n+\t\t\tcontinue;\n+\n \t\tif (bloom_filter_contains(filter, &ent->key,\n \t\t\t\t\t  lm->rev.bloom_filter_settings))\n \t\t\treturn true;\n@@ -220,42 +282,197 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \treturn false;\n }\n \n+static void process_parent(struct last_modified *lm,\n+\t\t\t   struct prio_queue *queue,\n+\t\t\t   struct commit *c, struct bitmap *active_c,\n+\t\t\t   struct commit *parent, int parent_i)\n+{\n+\tsize_t i;\n+\tstruct bitmap *active_p;\n+\n+\trepo_parse_commit(lm->rev.repo, parent);\n+\tactive_p = get_bitmap(lm, parent);\n+\n+\t/*\n+\t * The first time entering this function for this commit (i.e. first parent)\n+\t * see if Bloom filters will tell us it's worth to do the diff.\n+\t */\n+\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n+\t\tdiff_tree_oid(&parent->object.oid,\n+\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n+\t\tdiffcore_std(&lm->rev.diffopt);\n+\t}\n+\n+\t/*\n+\t * Otherwise, test each path for TREESAME-ness against the parent. If\n+\t * a path is TREESAME, pass it on to this parent.\n+\t *\n+\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n+\t * Then, pass paths that *are* TREESAME and active to the parent.\n+\t */\n+\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n+\t\tsize_t k = path_idx(lm, fp->two->path);\n+\t\tif (0 <= k && bitmap_get(active_c, k))\n+\t\t\tbitmap_set(lm->scratch, k);\n+\t\tdiff_free_filepair(fp);\n+\t}\n+\tfor (i = 0; i < lm->all_paths_nr; i++) {\n+\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n+\t\t\tpass_to_parent(lm, active_c, active_p, i);\n+\t}\n+\n+\t/*\n+\t * If parent has any active paths, put it on the queue (if not already).\n+\t */\n+\tif (!bitmap_is_empty(active_p) && !(parent->object.flags & PARENT1)) {\n+\t\tparent->object.flags |= PARENT1;\n+\t\tprio_queue_put(queue, parent);\n+\t}\n+\n+\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n+\tdiff_queued_diff.nr = 0;\n+\tdiff_queue_clear(&diff_queued_diff);\n+}\n+\n static int last_modified_run(struct last_modified *lm)\n {\n+\tint max_count, queue_popped = 0;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit_list *list;\n \tstruct last_modified_callback_data data = { .lm = lm };\n \n \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n \tlm->rev.diffopt.format_callback = last_modified_diff;\n \tlm->rev.diffopt.format_callback_data = &data;\n+\tlm->rev.no_walk = 1;\n \n \tprepare_revision_walk(&lm->rev);\n \n-\twhile (hashmap_get_size(&lm->paths)) {\n-\t\tdata.commit = get_revision(&lm->rev);\n-\t\tif (!data.commit)\n-\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\tmax_count = lm->rev.max_count;\n+\n+\tinit_commit_bitmaps(&lm->commit_bitmaps);\n+\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n+\n+\t/*\n+\t * lm->rev.commits holds the set of boundary commits for our walk.\n+\t *\n+\t * Loop through each such commit, and place it in the appropriate queue.\n+\t */\n+\tfor (list = lm->rev.commits; list; list = list->next) {\n+\t\tstruct commit *c = list->item;\n+\n+\t\tif (c->object.flags & BOTTOM) {\n+\t\t\tprio_queue_put(&not_queue, c);\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t} else if (!(c->object.flags & PARENT1)) {\n+\t\t\t/*\n+\t\t\t * If the commit is a starting point (and hasn't been\n+\t\t\t * seen yet), then initialize the set of interesting\n+\t\t\t * paths, too.\n+\t\t\t */\n+\t\t\tstruct bitmap *active;\n+\n+\t\t\tprio_queue_put(&queue, c);\n+\t\t\tc->object.flags |= PARENT1;\n \n-\t\tif (data.commit->object.flags & BOUNDARY) {\n+\t\t\tactive = get_bitmap(lm, c);\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\t\t\tbitmap_set(active, i);\n+\t\t}\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tint parent_i;\n+\t\tstruct commit_list *p;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tstruct bitmap *active_c = get_bitmap(lm, c);\n+\n+\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n+\t\t    (c->object.flags & PARENT2)) {\n+\t\t\t/*\n+\t\t\t * Either a boundary commit, or we have already seen too\n+\t\t\t * many others. Either way, stop here.\n+\t\t\t */\n+\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n+\t\t\tdata.commit = c;\n \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n-\t\t\t\t      &data.commit->object.oid, \"\",\n-\t\t\t\t      &lm->rev.diffopt);\n+\t\t\t\t      &c->object.oid,\n+\t\t\t\t      \"\", &lm->rev.diffopt);\n \t\t\tdiff_flush(&lm->rev.diffopt);\n+\t\t\tgoto cleanup;\n+\t\t}\n \n-\t\t\tbreak;\n+\t\t/*\n+\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n+\t\t * in the '--not' queue.\n+\t\t */\n+\t\trepo_parse_commit(lm->rev.repo, c);\n+\n+\t\twhile (not_queue.nr) {\n+\t\t\tstruct commit_list *np;\n+\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n+\n+\t\t\trepo_parse_commit(lm->rev.repo, n);\n+\n+\t\t\tfor (np = n->parents; np; np = np->next) {\n+\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n+\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n+\t\t\t\t\tnp->item->object.flags |= PARENT2;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n+\t\t\t\tbreak;\n \t\t}\n \n-\t\tif (!maybe_changed_path(lm, data.commit))\n-\t\t\tcontinue;\n+\t\t/*\n+\t\t * Look at each parent and pass on each path that's TREESAME\n+\t\t * with that parent. Stop early when no active paths remain.\n+\t\t */\n+\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n+\t\t\tprocess_parent(lm, &queue,\n+\t\t\t\t       c, active_c,\n+\t\t\t\t       p->item, parent_i);\n+\n+\t\t\tif (bitmap_is_empty(active_c))\n+\t\t\t\tbreak;\n+\t\t}\n \n-\t\tlog_tree_commit(&lm->rev, data.commit);\n+\t\t/*\n+\t\t * Paths that remain active, or not TREESAME with any parent,\n+\t\t * were changed by 'c'.\n+\t\t */\n+\t\tif (!bitmap_is_empty(active_c))  {\n+\t\t\tdata.commit = c;\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\t\t\t\tif (bitmap_get(active_c, i))\n+\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n+\t\t\t}\n+\t\t}\n+\n+cleanup:\n+\t\tbitmap_free(active_c);\n \t}\n \n+\tif (hashmap_get_size(&lm->paths))\n+\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\n+\tclear_prio_queue(&not_queue);\n+\tclear_prio_queue(&queue);\n+\tclear_commit_bitmaps(&lm->commit_bitmaps);\n+\tbitmap_free(lm->scratch);\n+\n \treturn 0;\n }\n \n static int last_modified_init(struct last_modified *lm, struct repository *r,\n \t\t\t      const char *prefix, int argc, const char **argv)\n {\n+\tstruct hashmap_iter iter;\n+\tstruct last_modified_entry *ent;\n+\n \thashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);\n \n \trepo_init_revisions(r, &lm->rev, prefix);\n@@ -280,6 +497,13 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \tif (populate_paths_from_revs(lm) < 0)\n \t\treturn error(_(\"unable to setup last-modified\"));\n \n+\tlm->all_paths = xcalloc(hashmap_get_size(&lm->paths), sizeof(const char *));\n+\tlm->all_paths_nr = 0;\n+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tent->diff_idx = lm->all_paths_nr++;\n+\t\tlm->all_paths[ent->diff_idx] = ent->path;\n+\t}\n+\n \treturn 0;\n }\n \ndiff --git a/object.h b/object.h\nindex 8c3c1c46e1..fa504a09c0 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n  * http-push.c:                          11-----14\n  * commit-graph.c:                                15\n  * commit-reach.c:                                  16-----19\n+ * builtin/last-modified.c:                         1617\n  * sha1-name.c:                                              20\n  * list-objects-filter.c:                                      21\n  * bloom.c:                                                    2122\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 61f00bc15c..a4c1114ee2 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -57,9 +57,9 @@ test_expect_success 'last-modified recursive' '\n \n test_expect_success 'last-modified recursive with show-trees' '\n \tcheck_last_modified -r -t <<-\\EOF\n-\t3 a\n \t3 a/b\n \t3 a/b/file\n+\t3 a\n \t2 a/file\n \t1 file\n \tEOF\n\n---\nbase-commit: 143f58ef7535f8f8a80d810768a18bdf3807de26\nchange-id: 20251009-b4-toon-last-modified-faster-4c8956a95261\n\nBest regards,\n--  \nToon Claes <toon@iotcl.com>\n\n"},{"id":"528983","messageId":"kkcpsorsmyfdxlxnlzliuggsaehhrfvfphdse7aslvwsrbm64b@ylgl65mzot2z","threadId":"64332","inReplyTo":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Justin Tobler","fromEmail":"jltobler@gmail.com","sentAt":"2025-10-16T18:51:51Z","receivedAt":"2025-10-16T18:51:56Z","isPatch":true,"sender":{"key":"jltobler@gmail.com","avatar":"https://avatars.githubusercontent.com/u/53454972?v=4"},"body":"On 25/10/16 10:39AM, Toon Claes wrote:\n> The current implementation of git-last-modified(1) works by doing a\n> revision walk, and inspecting the diff at each level of that walk to\n> annotate entries remaining in the hashmap of paths. In other words, if\n> the diff at some level touches a path which has not yet been associated\n> with a commit, then that commit becomes associated with the path.\n> \n> While a perfectly reasonable implementation, it can perform poorly in\n> either one of two scenarios:\n> \n>   1. There are many entries of interest, in which case there is simply\n>      a lot of work to do.\n> \n>   2. Or, there are (even a few) entries which have not been updated in a\n>      long time, and so we must walk through a lot of history in order to\n>      find a commit that touches that path.\n> \n> This patch rewrites the last-modified implementation that addresses the\n> second point. The idea behind the algorithm is to propagate a set of\n> 'active' paths (a path is 'active' if it does not yet belong to a\n> commit) up to parents and do a truncated revision walk.\n> \n> The walk is truncated because it does not produce a revision for every\n> change in the original pathspec, but rather only for active paths.\n\nOk so if I understand correctly, the optimization here is that as we\nperform the revision walk, the set of paths we look for at each commit\nmonotonically decreases as changed paths are identified. Prior to this,\nwe were always checking all paths for each commit even though a path may\nhave already found the commit that last modified it.\n\n> More specifically, consider a priority queue of commits sorted by\n> generation number. First, enqueue the set of boundary commits with all\n> paths in the original spec marked as interesting.\n> \n> Then, while the queue is not empty, do the following:\n> \n>   1. Pop an element, say, 'c', off of the queue, making sure that 'c'\n>      isn't reachable by anything in the '--not' set.\n> \n>   2. For each parent 'p' (with index 'parent_i') of 'c', do the\n>      following:\n> \n>      a. Compute the diff between 'c' and 'p'.\n>      b. Pass any active paths that are TREESAME from 'c' to 'p'.\n>      c. If 'p' has any active paths, push it onto the queue.\n> \n>   3. Any path that remains active on 'c' is associated to that commit.\n> \n> This ends up being equivalent to doing something like 'git log -1 --\n> $path' for each path simultaneously. But, it allows us to go much faster\n> than the original implementation by limiting the number of diffs we\n> compute, since we can avoid parts of history that would have been\n> considered by the revision walk in the original implementation, but are\n> known to be uninteresting to us because we have already marked all paths\n> in that area to be inactive.\n> \n> To avoid computing many first-parent diffs, add another trick on top of\n> this and check if all paths active in 'c' are DEFINITELY NOT in c's\n> Bloom filter. Since the commit-graph only stores first-parent diffs in\n> the Bloom filters, we can only apply this trick to first-parent diffs.\n> \n[snip]\n> As an added benefit, this implementation gives more correct results. For\n> example implementation in 'master' gives:\n\ns/implementation/the implementation/\n\n>     $ git log --max-count=1 --format=%H -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de\n> \n>     $ git last-modified -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n> \n>     $ git last-modified | grep pkt-line.h\n>     5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n> \n> With the changes in this patch the results of git-last-modified(1)\n> always match those of `git log --max-count=1`.\n> \n> One thing to note though, the results might be outputted in a different\n> order than before. This is not considerd to be an issue because nowhere\n> is documented the order is guaranteed.\n> \n> Based-on-patches-by: Taylor Blau <me@ttaylorr.com>\n> Signed-off-by: Toon Claes <toon@iotcl.com>\n> ---\n[snip]\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index ae8b36a2c3..40e520ba18 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -2,26 +2,32 @@\n>  #include \"bloom.h\"\n>  #include \"builtin.h\"\n>  #include \"commit-graph.h\"\n> +#include \"commit-slab.h\"\n>  #include \"commit.h\"\n>  #include \"config.h\"\n> -#include \"environment.h\"\n>  #include \"diff.h\"\n>  #include \"diffcore.h\"\n>  #include \"environment.h\"\n> +#include \"ewah/ewok.h\"\n>  #include \"hashmap.h\"\n>  #include \"hex.h\"\n> -#include \"log-tree.h\"\n>  #include \"object-name.h\"\n>  #include \"object.h\"\n>  #include \"parse-options.h\"\n> +#include \"prio-queue.h\"\n>  #include \"quote.h\"\n>  #include \"repository.h\"\n>  #include \"revision.h\"\n>  \n> +/* Remember to update object flag allocation in object.h */\n\nAt first I was wondering if this is a leftover note, but it looks like\nit is just a reminder if the allocations change here.\n\n> +#define PARENT1 (1u<<16) /* used instead of SEEN */\n> +#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n\nNaive question: why do we use these object flags instead of the ones\nmentioned?\n\n> +\n>  struct last_modified_entry {\n>  \tstruct hashmap_entry hashent;\n>  \tstruct object_id oid;\n>  \tstruct bloom_key key;\n> +\tsize_t diff_idx;\n>  \tconst char path[FLEX_ARRAY];\n>  };\n>  \n> @@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n>  \treturn strcmp(ent1->path, path ? path : ent2->path);\n>  }\n>  \n> +/*\n> + * Hold a bitmap for each commit we're working with. Each bit represents a path\n> + * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n> + */\n> +define_commit_slab(commit_bitmaps, struct bitmap *);\n\nWhy do we need a path bitmap for each commit? My understanding is that\nwe check commits in a certain order as dictated by the priority queue.\nAs soon as the commit that last-modified a path has been identified,\nwouldn't we always want the remaining commits processed to only check\nthe outstanding paths?\n\n>  struct last_modified {\n>  \tstruct hashmap paths;\n>  \tstruct rev_info rev;\n>  \tbool recursive;\n>  \tbool show_trees;\n> +\n> +\tconst char **all_paths;\n> +\tsize_t all_paths_nr;\n\nIt is not immediately obvious to me why we have both `paths` and\n`all_paths`. From my understanding, `all_paths` is defining the path\norder for the bitmap. If this is the case, maybe it would be worth\nexplaining in a comment?\n\n> +\tstruct commit_bitmaps commit_bitmaps;\n> +\n> +\t/* 'scratch' bitmap to avoid allocating every proccess_parent() */\n> +\tstruct bitmap *scratch;\n>  };\n>  \n> +static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n> +{\n> +\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);\n> +\tif (!*bitmap)\n> +\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n> +\n> +\treturn *bitmap;\n> +}\n> +\n>  static void last_modified_release(struct last_modified *lm)\n>  {\n>  \tstruct hashmap_iter iter;\n[snip]\n>  static int last_modified_run(struct last_modified *lm)\n>  {\n> +\tint max_count, queue_popped = 0;\n> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> +\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n> +\tstruct commit_list *list;\n>  \tstruct last_modified_callback_data data = { .lm = lm };\n>  \n>  \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n>  \tlm->rev.diffopt.format_callback = last_modified_diff;\n>  \tlm->rev.diffopt.format_callback_data = &data;\n> +\tlm->rev.no_walk = 1;\n>  \n>  \tprepare_revision_walk(&lm->rev);\n>  \n> -\twhile (hashmap_get_size(&lm->paths)) {\n> -\t\tdata.commit = get_revision(&lm->rev);\n> -\t\tif (!data.commit)\n> -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n> +\tmax_count = lm->rev.max_count;\n> +\n> +\tinit_commit_bitmaps(&lm->commit_bitmaps);\n> +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n\nIt looks like we initialize and release both `commit_bitmaps` and\n`scratch` here in `last_modified_run()`. Any reason we wouldn't want to\nmove this to `last_modified_{init,release}()`?\n\n> +\n> +\t/*\n> +\t * lm->rev.commits holds the set of boundary commits for our walk.\n\nNaive question: would it be more correct to say that `rev.commits` is\nthe list of starting commits? Boundary commits sounds like commits on\nthe boundary of what we consider interesting/uninteresting which, from\nmy understanding, is not the case here.\n\n> +\t *\n> +\t * Loop through each such commit, and place it in the appropriate queue.\n> +\t */\n> +\tfor (list = lm->rev.commits; list; list = list->next) {\n> +\t\tstruct commit *c = list->item;\n> +\n> +\t\tif (c->object.flags & BOTTOM) {\n> +\t\t\tprio_queue_put(&not_queue, c);\n\nOk so commits with the BOTTOM flag are at the boundary of the\n\"interesting\" commit graph. Thus they are not included in the search and\nadded to the \"not_queue\".\n\n> +\t\t\tc->object.flags |= PARENT2;\n\nWhat is the meaning behind the name PARENT2 in this context? From my\nunderstanding we are using this flag to denote a commit we are not\ninterested in.\n\n> +\t\t} else if (!(c->object.flags & PARENT1)) {\n\nSame question about PARENT1. It seems to be used to just denote commits\nthat we have already encountered. The names confuse me a bit though.\n\n> +\t\t\t/*\n> +\t\t\t * If the commit is a starting point (and hasn't been\n> +\t\t\t * seen yet), then initialize the set of interesting\n> +\t\t\t * paths, too.\n> +\t\t\t */\n> +\t\t\tstruct bitmap *active;\n> +\n> +\t\t\tprio_queue_put(&queue, c);\n> +\t\t\tc->object.flags |= PARENT1;\n\nWe queue the commit and mark it as seen. Makes sense.\n\n> -\t\tif (data.commit->object.flags & BOUNDARY) {\n> +\t\t\tactive = get_bitmap(lm, c);\n> +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n> +\t\t\t\tbitmap_set(active, i);\n\nHere we set up the path bitmap for the commit. At this point, all paths\nare still \"active\" and thus set accordingly. I'm still not entirely sure\nthough if we really need a path bitmap per commit.\n\n> +\t\t}\n> +\t}\n> +\n> +\twhile (queue.nr) {\n> +\t\tint parent_i;\n> +\t\tstruct commit_list *p;\n> +\t\tstruct commit *c = prio_queue_get(&queue);\n> +\t\tstruct bitmap *active_c = get_bitmap(lm, c);\n> +\n> +\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n> +\t\t    (c->object.flags & PARENT2)) {\n> +\t\t\t/*\n> +\t\t\t * Either a boundary commit, or we have already seen too\n> +\t\t\t * many others. Either way, stop here.\n> +\t\t\t */\n> +\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n> +\t\t\tdata.commit = c;\n>  \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n> -\t\t\t\t      &data.commit->object.oid, \"\",\n> -\t\t\t\t      &lm->rev.diffopt);\n> +\t\t\t\t      &c->object.oid,\n> +\t\t\t\t      \"\", &lm->rev.diffopt);\n>  \t\t\tdiff_flush(&lm->rev.diffopt);\n> +\t\t\tgoto cleanup;\n> +\t\t}\n>  \n> -\t\t\tbreak;\n> +\t\t/*\n> +\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n> +\t\t * in the '--not' queue.\n> +\t\t */\n> +\t\trepo_parse_commit(lm->rev.repo, c);\n> +\n> +\t\twhile (not_queue.nr) {\n> +\t\t\tstruct commit_list *np;\n> +\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n> +\n> +\t\t\trepo_parse_commit(lm->rev.repo, n);\n> +\n> +\t\t\tfor (np = n->parents; np; np = np->next) {\n> +\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n> +\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n> +\t\t\t\t\tnp->item->object.flags |= PARENT2;\n> +\t\t\t\t}\n> +\t\t\t}\n> +\n> +\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n> +\t\t\t\tbreak;\n\nIf the generation number of 'c' is higher than 'n' we know 'c' cannot be\nan ancestor of 'n' and thus we continue on. Makes sense.\n\n>  \t\t}\n>  \n> -\t\tif (!maybe_changed_path(lm, data.commit))\n> -\t\t\tcontinue;\n> +\t\t/*\n> +\t\t * Look at each parent and pass on each path that's TREESAME\n> +\t\t * with that parent. Stop early when no active paths remain.\n> +\t\t */\n> +\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n> +\t\t\tprocess_parent(lm, &queue,\n> +\t\t\t\t       c, active_c,\n> +\t\t\t\t       p->item, parent_i);\n> +\n> +\t\t\tif (bitmap_is_empty(active_c))\n> +\t\t\t\tbreak;\n> +\t\t}\n>  \n> -\t\tlog_tree_commit(&lm->rev, data.commit);\n> +\t\t/*\n> +\t\t * Paths that remain active, or not TREESAME with any parent,\n> +\t\t * were changed by 'c'.\n> +\t\t */\n> +\t\tif (!bitmap_is_empty(active_c))  {\n> +\t\t\tdata.commit = c;\n> +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n> +\t\t\t\tif (bitmap_get(active_c, i))\n> +\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n> +\t\t\t}\n> +\t\t}\n> +\n> +cleanup:\n> +\t\tbitmap_free(active_c);\n>  \t}\n>  \n> +\tif (hashmap_get_size(&lm->paths))\n> +\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n> +\n> +\tclear_prio_queue(&not_queue);\n> +\tclear_prio_queue(&queue);\n> +\tclear_commit_bitmaps(&lm->commit_bitmaps);\n> +\tbitmap_free(lm->scratch);\n> +\n>  \treturn 0;\n>  }\n[snip]\n\nI've taken an initial look a this patch and have mostly questions so\nfar. Just FYI, after applying this patch locally, the last-modified\ntests seem to be failing. The command seems to be segfaulting, but I\nhaven't looked into it further.\n\n-Justin\n"},{"id":"529010","messageId":"CALnO6CBwuAdBFjESZSYZkChNdU9R17OXDc+CY=Z96QoACPgrpQ@mail.gmail.com","threadId":"64332","inReplyTo":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"D. Ben Knoble","fromEmail":"ben.knoble@gmail.com","sentAt":"2025-10-16T20:48:34Z","receivedAt":"2025-10-16T20:48:47Z","isPatch":true,"sender":{"key":"ben.knoble@gmail.com","avatar":"https://avatars.githubusercontent.com/u/22802209?v=4"},"body":"On Thu, Oct 16, 2025 at 4:39 AM Toon Claes <toon@iotcl.com> wrote:\n> As an added benefit, this implementation gives more correct results. For\n> example implementation in 'master' gives:\n\n\"More correct\" is a bit of an oxymoron, no? It's either correct or it's not :)\n\n>\n>     $ git log --max-count=1 --format=%H -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de\n>\n>     $ git last-modified -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de    pkt-line.h\n>\n>     $ git last-modified | grep pkt-line.h\n>     5b49c1af03e600c286f63d9d9c9fb01403230b9f    pkt-line.h\n\nIt seems this commit is the merge to a maintenance branch, which was\nauthored and committed after the mainline merge but topologically we'd\nprobably consider it \"earlier,\" at least starting from master? Anyway,\nI'm not clear why this result was produced.\n\nThanks!\n\n-- \nD. Ben Knoble\n"},{"id":"529032","messageId":"aPGB/FJtjDmyNLvG@nand.local","threadId":"64332","inReplyTo":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-16T23:38:36Z","receivedAt":"2025-10-16T23:38:47Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 16, 2025 at 10:39:25AM +0200, Toon Claes wrote:\n> [...]\n>\n> To avoid computing many first-parent diffs, add another trick on top of\n> this and check if all paths active in 'c' are DEFINITELY NOT in c's\n> Bloom filter. Since the commit-graph only stores first-parent diffs in\n> the Bloom filters, we can only apply this trick to first-parent diffs.\n\nOK, up to this point this is the same as the commit message that I wrote\nwith Stolee back in 2020.\n\n> Comparing the performance of this new algorithm shows about a 2.6x\n> improvement on git.git:\n>\n>     Benchmark 1: master\n>       Time (mean ± σ):      3.077 s ±  0.055 s    [User: 3.017 s, System: 0.051 s]\n>       Range (min … max):    2.947 s …  3.127 s    10 runs\n>\n>     Benchmark 2: HEAD\n>       Time (mean ± σ):      1.181 s ±  0.010 s    [User: 1.139 s, System: 0.038 s]\n>       Range (min … max):    1.169 s …  1.194 s    10 runs\n>\n>     Summary\n>       HEAD ran\n>         2.60 ± 0.05 times faster than master\n>\n> But when comparing a more extreme example of\n> `git last-modified -- COPYING t`, the difference is a lot bigger:\n>\n>     Benchmark 1: master\n>       Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n>       Range (min … max):    4.308 s …  4.509 s    10 runs\n>\n>     Benchmark 2: HEAD\n>       Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n>       Range (min … max):   810.6 ms … 881.2 ms    10 runs\n>\n>     Summary\n>       HEAD ran\n>         5.29 ± 0.16 times faster than master\n\nThese benchmarks are different than the ones that I provided, which is\ngood, since we should be measuring modern Git, not dragging forward\nstale benchmarks ;-).\n\nI imagine that you are just doing a straight last-modified run here in\nboth instances. In the original patch, I timed this both with and\nwithout changed-path Bloom filters, which helped illustrate their impact\non the changes here.\n\nI'd suggest including those benchmarks as well, and potentially running\nthem on linux.git, or another comparably larger open-source repository.\ngit.git is large enough to show some interesting behavior, but I always\nhave found it useful to compare the results against a larger repository\nas well.\n\n> As an added benefit, this implementation gives more correct results. For\n> example implementation in 'master' gives:\n>\n>     $ git log --max-count=1 --format=%H -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de\n>\n>     $ git last-modified -- pkt-line.h\n>     15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n>\n>     $ git last-modified | grep pkt-line.h\n>     5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n>\n> With the changes in this patch the results of git-last-modified(1)\n> always match those of `git log --max-count=1`.\n>\n> One thing to note though, the results might be outputted in a different\n> order than before. This is not considerd to be an issue because nowhere\n> is documented the order is guaranteed.\n>\n> Based-on-patches-by: Taylor Blau <me@ttaylorr.com>\n\nStolee and I wrote these patches together many years ago, so he should\nbe credited here as well. Since this patch appears to be substantially\nbased on the original work, I think it is appropriate to include my\nS-o-b once the patch is ready.\n\n> ---\n> This series revives those changes. I did more thorough deep dive through\n> the code and the algorithm and got the code working a lot faster. The\n> benchmark results can be found in the commit message.\n>\n> Some changes compared to GitHub's version include:\n>\n>  * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n>    `struct commit_active_paths`.\n>\n>  * Removed shortcut code that handled the case when commit and parent\n>    are fully treesame, and instead always checked 'active_c' whether the\n>    next parent is worth looking at.\n>\n>  * Modified comments and commit message to make the algorithm more\n>    clear (at least to me).\n>\n>  * Mentioned the use of PARENT1 and PARENT2 in object.h.\n>\n>  * Removed the use of any global variables.\n>\n>  * Less conditions are checked in mark_path() because the hashmap of\n>    'paths' is considered the single-source of truth.\n>\n>  * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n>    hashmap no more.\n\nThanks for clearly showing what the changes on top are. When I applied\nthis locally and ran it, it pretty quickly segfaulted for me:\n\n    expecting success of 8020.3 'last-modified non-recursive':\n      check_last_modified <<-\\EOF\n      3 a\n      1 file\n      EOF\n\n    + check_last_modified\n    + local indir=\n    + test 0 != 0\n    + cat\n    + git last-modified\n    Segmentation fault\n    error: last command exited with $?=139\n    not ok 3 - last-modified non-recursive\n    #\n    #\t\tcheck_last_modified <<-\\EOF\n    #\t\t3 a\n    #\t\t1 file\n    #\t\tEOF\n    #\n    1..3\n\nLooking through the backtrace, it looks like someone is calling\nmark_path() with a NULL oid, like so:\n\n    (gdb) bt\n    #0  __memcmp_evex_movbe ()\n        at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:132\n    #1  0x00005555555f2c32 in oideq (oid1=0x0, oid2=0x555555a5eeb0)\n        at ./hash.h:408\n    #2  0x00005555555f3523 in mark_path (path=0x555555a5eee8 \"a\", oid=0x0,\n        data=0x7fffffffd650) at builtin/last-modified.c:179\n\n, which makes sense, since at the end of the main loop we call\nmark_path() on all remaining active paths to indicate that they were\nmodified by whatever commit we just popped off the queue.\n\nSomething like this on top (which matches the original patch that I sent\nfrom GitHub's fork) fixes the tests:\n\n--- 8< ---\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 40e520ba18..c8f66633a7 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -176,7 +176,7 @@ static void mark_path(const char *path, const struct object_id *oid,\n \t * Is it arriving at a version of interest, or is it from a side branch\n \t * which did not contribute to the final state?\n \t */\n-\tif (!oideq(oid, &ent->oid))\n+\tif (oid && !oideq(oid, &ent->oid))\n \t\treturn;\n\n \tlast_modified_emit(data->lm, path, data->commit);\n--- >8 ---\n\n> +/* Remember to update object flag allocation in object.h */\n> +#define PARENT1 (1u<<16) /* used instead of SEEN */\n> +#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n> +\n>  struct last_modified_entry {\n>  \tstruct hashmap_entry hashent;\n>  \tstruct object_id oid;\n>  \tstruct bloom_key key;\n> +\tsize_t diff_idx;\n>  \tconst char path[FLEX_ARRAY];\n>  };\n>\n> @@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n>  \treturn strcmp(ent1->path, path ? path : ent2->path);\n>  }\n>\n> +/*\n> + * Hold a bitmap for each commit we're working with. Each bit represents a path\n> + * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n> + */\n> +define_commit_slab(commit_bitmaps, struct bitmap *);\n> +\n\nNice, I am glad to see that we are using a bitmap here rather than the\nhacky 'char *' that we had originally written. I seem to remember that\nthere was a tiny slow-down when using bitmaps, but can't find the\ndiscussion anymore. (It wasn't in the internal PR that I originally\nopened, and I no longer can read messages that far back in history.)\n\nIt might be worth benchmarking here to see if using a 'char *' is\nfaster. Of course, that's 8x worse in terms of memory usage, but not a\nhuge deal given both the magnitude and typical number of directory\nelements (you'd need 1024^2 entries in a single tree to occupy even a\nsingle MiB of heap).\n\nRegardless of how you handle the above, I think that the commit slab\nname here is a little generic. I guess it's OK since this is only\nvisible within this compilation unit, but perhaps something like\n\"active_paths_bitmap\" would be more descriptive.\n\nLikewise, I wonder if we should have elemtype here be just 'struct\nbitmap'. Unfortunately I don't think the EWAH code has a function like:\n\n    void bitmap_init(struct bitmap *);\n\nand only has ones that allocate for us. So we may consider adding one,\nor creating a dummy bitmap and copying its contents, or otherwise.\n\n>  struct last_modified {\n>  \tstruct hashmap paths;\n>  \tstruct rev_info rev;\n>  \tbool recursive;\n>  \tbool show_trees;\n> +\n> +\tconst char **all_paths;\n> +\tsize_t all_paths_nr;\n\nI wonder if all_paths should be a strvec here? I think that this code\nwas all written when the type was called argv_array (hilariously, that\nchange took place towards the end of July, 2020, and the --go-faster\ncode where this patch came from was written just a couple of weeks\nearlier.)\n\n> @@ -196,7 +226,36 @@ static void last_modified_diff(struct diff_queue_struct *q,\n>  \t}\n>  }\n>\n> -static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n> +static size_t path_idx(struct last_modified *lm, char *path)\n> +{\n> +\tstruct last_modified_entry *ent;\n> +\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n> +\t\t\t\t\t  struct last_modified_entry, hashent);\n> +\n> +\treturn ent ? ent->diff_idx : -1;\n> +}\n> +\n> +static void pass_to_parent(struct last_modified *lm,\n> +\t\t\t   struct bitmap *c,\n> +\t\t\t   struct bitmap *p,\n> +\t\t\t   size_t pos)\n> +{\n> +\tstruct last_modified_entry *ent;\n> +\tstruct hashmap_iter iter;\n> +\n> +\tbitmap_unset(c, pos);\n> +\n> +\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n> +\t\tif (ent->diff_idx == pos) {\n> +\t\t\tbitmap_set(p, pos);\n> +\t\t\tbreak;\n> +\t\t}\n> +\t}\n> +}\n\nThis one I'm not quite following. The original implementation does\nsomething like:\n\n    c->active[i] = 0;\n    c->nr--;\n    p->active[i] = 1;\n    p->nr++;\n\n, where 'i' is an index into the all_paths array. It looks like you are\neffectively doing the first part of that with the bitmap_unset() call,\nbut I'm confused why you're iterating over paths here.\n\nThe caller in process_parents() is iterating over all entries that are\ntreesame to the parent, bit by bit. So I think you can just bitmap_set()\nin the parent directly here, but let me know if I am missing something.\n\n> @@ -220,42 +282,197 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n>  \treturn false;\n>  }\n>\n> +static void process_parent(struct last_modified *lm,\n> +\t\t\t   struct prio_queue *queue,\n> +\t\t\t   struct commit *c, struct bitmap *active_c,\n> +\t\t\t   struct commit *parent, int parent_i)\n> +{\n> +\tsize_t i;\n> +\tstruct bitmap *active_p;\n> +\n> +\trepo_parse_commit(lm->rev.repo, parent);\n> +\tactive_p = get_bitmap(lm, parent);\n> +\n> +\t/*\n> +\t * The first time entering this function for this commit (i.e. first parent)\n> +\t * see if Bloom filters will tell us it's worth to do the diff.\n> +\t */\n> +\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n> +\t\tdiff_tree_oid(&parent->object.oid,\n> +\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n> +\t\tdiffcore_std(&lm->rev.diffopt);\n> +\t}\n> +\n> +\t/*\n> +\t * Otherwise, test each path for TREESAME-ness against the parent. If\n\nThis \"otherwise\" is referencing a piece of the patch that doesn't appear\nto be here directly, which is how we handle the special case of having\nnothing in the diff queue, meaning we are treesame at the root.\n\nIn the GitHub version of this patch, we pass all active paths to the\nparent, assign the PARENT1 flag if it doesn't already have it, and put\nit in the queue as well.\n\nIn your version, we'd skip past the next for-loop, and do the same\npass-to-parent dance below, along with inserting the parent into the\nprio queue.\n\nSo I think that this is all functionally equivalent, but I had to work\nthrough a little bit of the details here, mostly since I haven't looked\nat or thought about this code in many years ;-).\n\n>  static int last_modified_run(struct last_modified *lm)\n>  {\n> +\tint max_count, queue_popped = 0;\n> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> +\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n> +\tstruct commit_list *list;\n>  \tstruct last_modified_callback_data data = { .lm = lm };\n>\n>  \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n>  \tlm->rev.diffopt.format_callback = last_modified_diff;\n>  \tlm->rev.diffopt.format_callback_data = &data;\n> +\tlm->rev.no_walk = 1;\n\nThis one is new relative to the original patch. Why set no_walk here?\n\n>\n>  \tprepare_revision_walk(&lm->rev);\n>\n> -\twhile (hashmap_get_size(&lm->paths)) {\n> -\t\tdata.commit = get_revision(&lm->rev);\n> -\t\tif (!data.commit)\n> -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n> +\tmax_count = lm->rev.max_count;\n> +\n> +\tinit_commit_bitmaps(&lm->commit_bitmaps);\n> +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n> +\n> +\t/*\n> +\t * lm->rev.commits holds the set of boundary commits for our walk.\n> +\t *\n> +\t * Loop through each such commit, and place it in the appropriate queue.\n> +\t */\n> +\tfor (list = lm->rev.commits; list; list = list->next) {\n\nHmm. In the original patch, we look at rev.pending, not rev.commits. The\nrest of the patch looks good to me and looks like a faithful\nrepresentation of the original patch from GitHub's fork. Thanks for\nworking on this and making the new last-modified builtin faster ;-).\n\nThanks,\nTaylor\n"},{"id":"529040","messageId":"20251017063039.GA3074253@coredump.intra.peff.net","threadId":"64332","inReplyTo":"aPGB/FJtjDmyNLvG@nand.local","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-17T06:30:39Z","receivedAt":"2025-10-17T06:30:47Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 16, 2025 at 07:38:36PM -0400, Taylor Blau wrote:\n\n> Looking through the backtrace, it looks like someone is calling\n> mark_path() with a NULL oid, like so:\n> \n>     (gdb) bt\n>     #0  __memcmp_evex_movbe ()\n>         at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:132\n>     #1  0x00005555555f2c32 in oideq (oid1=0x0, oid2=0x555555a5eeb0)\n>         at ./hash.h:408\n>     #2  0x00005555555f3523 in mark_path (path=0x555555a5eee8 \"a\", oid=0x0,\n>         data=0x7fffffffd650) at builtin/last-modified.c:179\n> \n> , which makes sense, since at the end of the main loop we call\n> mark_path() on all remaining active paths to indicate that they were\n> modified by whatever commit we just popped off the queue.\n\nHmm, sounds like the mark_path() discussion from:\n\n  https://lore.kernel.org/git/aHmPHcNQYlhGo8JB@nand.local/\n\ncoming home to roost. I'm sure you already knew that, but there's maybe\nan interesting process observation here: in pulling a battle-tested\nimplementation apart into patches to be applied in chunks, we ended up\nmissing a critical part of that original implementation and getting a\nbug.\n\nIt's not like we didn't know that was a risk, of course, and the payoff\nwas getting a fresh look at the patches (to improve them and maybe even\nfix latent bugs). So it's probably something to just live with. But I\nwonder if/how we could mitigate that risk. When I reorganize patches in\na tricky way locally, I often eyeball the diff of the end states\n(whatever mess I had originally, versus the result of the \"clean\"\nversion), and that might have shown the omission here.\n\nI'm not sure if that would have helped here or not. The \"end state\" of\nthe battle-tested version is really GitHub's internal fork. But maybe\nyour original patches extracted from that (tb/blame-tree in your fork, I\nthink) applied on top of the same base point (e.g., the current tip of\nmaster) might be an interesting comparison? Or maybe not. The earlier\nrounds have may have had other adjustments which introduce a bunch of\nnoise.\n\nAnyway, that is mostly philosophical rambling. I did have one concrete\nthing to say below.\n\n> > +/*\n> > + * Hold a bitmap for each commit we're working with. Each bit represents a path\n> > + * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n> > + */\n> > +define_commit_slab(commit_bitmaps, struct bitmap *);\n> > +\n> \n> Nice, I am glad to see that we are using a bitmap here rather than the\n> hacky 'char *' that we had originally written. I seem to remember that\n> there was a tiny slow-down when using bitmaps, but can't find the\n> discussion anymore. (It wasn't in the internal PR that I originally\n> opened, and I no longer can read messages that far back in history.)\n> \n> It might be worth benchmarking here to see if using a 'char *' is\n> faster. Of course, that's 8x worse in terms of memory usage, but not a\n> huge deal given both the magnitude and typical number of directory\n> elements (you'd need 1024^2 entries in a single tree to occupy even a\n> single MiB of heap).\n\nI doubt the memory usage matters too much. We throw away each bitmap\nafter we finish processing its associated commit, so our max memory is\nreally the size of the bitmap/char array times the size of the queue (so\neffectively the width of the history graph). So yeah, I too would be\ncurious if the performance is actually better with chars.\n\nI also wonder how often we pass an unchanged bitmap to our parents\n(e.g., for the common case that a commit has a single parent, and does\nnot touch any of the active paths, the active set will be the same for\nboth). There's probably an easy-ish optimization to avoid allocating a\nnew bitmap, and to just transfer ownership via pointer.\n\n  You can even get fancier and always just speculatively pass your\n  bitmap to _all_ parents, keeping a refcount, and then copy-on-write\n  when you need to clear a bit. We do something similar in\n  delta-island's set_island_marks(). But the complexity may not be worth\n  it, as I'd guess that the single-parent, nothing-cleared case would\n  dominate.\n\nThat's definitely something that could come on top of this, though (or\nnever).\n\n> Likewise, I wonder if we should have elemtype here be just 'struct\n> bitmap'. Unfortunately I don't think the EWAH code has a function like:\n> \n>     void bitmap_init(struct bitmap *);\n> \n> and only has ones that allocate for us. So we may consider adding one,\n> or creating a dummy bitmap and copying its contents, or otherwise.\n\nI thought that, too, though it does change the max memory use a bit.\nRight now we are storing one pointer per commit (the \"struct bitmap *\")\nand that is true whether we have processed the commit or not (it is\npopulated while the commit is in the queue, and then NULL after). If we\nstored the struct directly, that's twice as many bytes (the eword_t\npointer, plus a size_t), and it's per commit.\n\nSo for the 1.3M commits in linux.git, for example, that's 10MB used\nduring the whole program. We save a few bytes by not having the extra\npointers, but only for items that are in the queue (which are relatively\nsmall).\n\nProbably doesn't matter much, as 10MB isn't that much (and we are surely\nstoring much more for the commit structs themselves). I'd be curious if\navoiding the extra malloc/free and pointer chasing shows a run-time\nimprovement, though.\n\nIronically, we do not really need the bitmap's size field at all! All of\nthese bitmaps are going to start as \"all_paths_nr\" worth of 1's and get\nwhittled down from there. So they could all just be the same size\nallocation and skip their \"nr\" field entirely. Of course we couldn't use\nthe bitmap struct then.\n\nI notice that the original implementation does keep a \"nr\" field\nper-commit, but it's not the size of the allocation. It's the number of\nbits set. It feels like we shouldn't need to keep that forever. It's\nmostly used to see if the parent got anything passed to it, but we can\nthrow it away after that. So you could be saving 8 bytes per commit\nthere (and I don't see that information kept at all in Toon's version).\n\nAnyway, these are all probably micro-optimizations that don't matter\nthat much. I am a little curious if chars outperform bitmaps, though.\n\n-Peff\n\nPS I tried building tb/blame-tree from your repo because I was poking at\n   how some of it worked (having forgotten everything I ever knew about\n   it by this point). It does work, but needs this:\n\ndiff --git a/blame-tree.c b/blame-tree.c\nindex 6addac7b0b..2448f2caf4 100644\n--- a/blame-tree.c\n+++ b/blame-tree.c\n@@ -800,7 +800,6 @@ static int process_parent(struct blame_tree *bt,\n \t\tint k = diff2idx(bt, fp->two->path);\n \t\tif (0 <= k && active_c->active[k])\n \t\t\tscratch[k] = 1;\n-\t\tdiff_free_filepair(fp);\n \t}\n \tfor (i = 0; i < bt->all_paths_nr; i++) {\n \t\tif (active_c->active[i] && !scratch[i])\n\n  on top, since otherwise we try to double-free the filepairs. I'd guess\n  it is a victim of rebasing across a5aecb2cdc (diff: improve lifecycle\n  management of diff queues, 2024-09-30), which swapped out\n  DIFF_QUEUE_CLEAR(), which left freeing the responsibility of the\n  caller, for diff_queue_clear() which handles that itself.\n"},{"id":"529041","messageId":"20251017063701.GA3091356@coredump.intra.peff.net","threadId":"64332","inReplyTo":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-17T06:37:01Z","receivedAt":"2025-10-17T06:37:02Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 16, 2025 at 10:39:25AM +0200, Toon Claes wrote:\n\n> +\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n> +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n> +\t\tsize_t k = path_idx(lm, fp->two->path);\n> +\t\tif (0 <= k && bitmap_get(active_c, k))\n> +\t\t\tbitmap_set(lm->scratch, k);\n> +\t\tdiff_free_filepair(fp);\n> +\t}\n\nJust one little oddity while looking at this versus the old patches from\nTaylor. Here you call diff_free_filepair(). But later...\n\n> +\tdiff_queued_diff.nr = 0;\n> +\tdiff_queue_clear(&diff_queued_diff);\n\n...you call diff_queue_clear(), which frees the filepairs itself. It\ndoes the right thing, because you truncate the queue explicitly. But\nwould it be simpler to just leave them in place and let the _clear()\nfunction clean up? I.e., this:\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 40e520ba18..47f2b0ed44 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -315,7 +315,6 @@ static void process_parent(struct last_modified *lm,\n \t\tsize_t k = path_idx(lm, fp->two->path);\n \t\tif (0 <= k && bitmap_get(active_c, k))\n \t\t\tbitmap_set(lm->scratch, k);\n-\t\tdiff_free_filepair(fp);\n \t}\n \tfor (i = 0; i < lm->all_paths_nr; i++) {\n \t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n@@ -331,7 +330,6 @@ static void process_parent(struct last_modified *lm,\n \t}\n \n \tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n-\tdiff_queued_diff.nr = 0;\n \tdiff_queue_clear(&diff_queued_diff);\n }\n \n\nwhich feels a lot more idiomatic to me.\n\n-Peff\n"},{"id":"529056","messageId":"87sefhu81y.fsf@iotcl.com","threadId":"64332","inReplyTo":"kkcpsorsmyfdxlxnlzliuggsaehhrfvfphdse7aslvwsrbm64b@ylgl65mzot2z","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-17T10:38:49Z","receivedAt":"2025-10-17T10:39:02Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Justin Tobler <jltobler@gmail.com> writes:\n\n> Ok so if I understand correctly, the optimization here is that as we\n> perform the revision walk, the set of paths we look for at each commit\n> monotonically decreases as changed paths are identified. Prior to this,\n> we were always checking all paths for each commit even though a path may\n> have already found the commit that last modified it.\n\nNot only that, we only pass on paths to one parent. So either a path is\ntreesame to a parent, that means it was not changed in the current\ncommit, and then we only pass that path to that parent. If the commit\nhad multiple parents, the merge ignored versions from other parents.\n\nIf the path isn't treesame to any of the parents, we know the current\ncommit modified the path, and we associate that commit with that path.\n\n\n> [snip]\n>> As an added benefit, this implementation gives more correct results. For\n>> example implementation in 'master' gives:\n>\n> s/implementation/the implementation/\n\nFair enough, but I also need to rephrase the \"more correct\" as pointed\nout by Ben[1].\n\n[1]: https://lore.kernel.org/git/CALnO6CBwuAdBFjESZSYZkChNdU9R17OXDc+CY=Z96QoACPgrpQ@mail.gmail.com/\n\n>> +/* Remember to update object flag allocation in object.h */\n>\n> At first I was wondering if this is a leftover note, but it looks like\n> it is just a reminder if the allocations change here.\n\nYeah, it seems to be the common pattern to do it like this. Didn't\nquestion it further.\n\n>> +#define PARENT1 (1u<<16) /* used instead of SEEN */\n>> +#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n>\n> Naive question: why do we use these object flags instead of the ones\n> mentioned?\n\nWe set these bits in `struct object::flags`, because other systems might\nbe using other bits for their internal workings we want to avoid\ncolliding bit ranges. That's why users define the bits they use in\nobject.h, to have a general overview over who is using what and which\nsystems might get in trouble with eachother.\n\nBit 16 and 17 seems to be safe to use. We could have named these defines\nSEEN and BOUNDARY, but in revision.h they have different bit positions,\nso we name that PARENT1 and PARENT2, similar to what these bits are\nnamed in other files.\n\n>> +\n>>  struct last_modified_entry {\n>>  \tstruct hashmap_entry hashent;\n>>  \tstruct object_id oid;\n>>  \tstruct bloom_key key;\n>> +\tsize_t diff_idx;\n>>  \tconst char path[FLEX_ARRAY];\n>>  };\n>>  \n>> @@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n>>  \treturn strcmp(ent1->path, path ? path : ent2->path);\n>>  }\n>>  \n>> +/*\n>> + * Hold a bitmap for each commit we're working with. Each bit represents a path\n>> + * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n>> + */\n>> +define_commit_slab(commit_bitmaps, struct bitmap *);\n>\n> Why do we need a path bitmap for each commit? My understanding is that\n> we check commits in a certain order as dictated by the priority queue.\n> As soon as the commit that last-modified a path has been identified,\n> wouldn't we always want the remaining commits processed to only check\n> the outstanding paths?\n\nBecause we want to pass paths to parents that are treesame. Imagine a\ntree with:\n\n    bar-a.txt\n    bar-b.txt\n    baz-a.txt\n    foo-a.txt\n    foo-a.txt\n\nWhen we're looking at a commit and it has the 'active_c' bitmap\n`11111`. This commit has two parents, and we see bar-a.txt and bar-b.txt\nare treesame on parent-0, we pass bitmap `11000` to that parent. If\nfoo-a.txt and foo-b.txt are treesame on the parent-1, we pass bitmap\n`00011` to that parent. This leaves bitmap `00100` behind on the current\ncommit, and we associate baz-a.txt with that commit.\n\nSo a bit for a path would only be passed on to a single parent (or\nnone).\n\n>>  struct last_modified {\n>>  \tstruct hashmap paths;\n>>  \tstruct rev_info rev;\n>>  \tbool recursive;\n>>  \tbool show_trees;\n>> +\n>> +\tconst char **all_paths;\n>> +\tsize_t all_paths_nr;\n>\n> It is not immediately obvious to me why we have both `paths` and\n> `all_paths`. From my understanding, `all_paths` is defining the path\n> order for the bitmap. If this is the case, maybe it would be worth\n> explaining in a comment?\n\nYeah, I'm not extremely happy about storing the information twice, but\nI kept it for two reasons:\n\n * The hashmap is filled by populate_paths_from_revs() and it grows with\n   every call of add_path_from_diff(). Afterwards we malloc() the\n   all_paths buffer to the correct size. Re-allocing all_paths on every\n   call of add_path_from_diff() would be clunky.\n\n * Reverse lookups: When we have a path, we can lookup the index in\n   all_paths using path_idx(), which uses the hashmap to locate the\n   hashmap entry (which has the `diff_idx`).\n\n> [snip]\n>>  static int last_modified_run(struct last_modified *lm)\n>>  {\n>> +\tint max_count, queue_popped = 0;\n>> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n>> +\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n>> +\tstruct commit_list *list;\n>>  \tstruct last_modified_callback_data data = { .lm = lm };\n>>  \n>>  \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n>>  \tlm->rev.diffopt.format_callback = last_modified_diff;\n>>  \tlm->rev.diffopt.format_callback_data = &data;\n>> +\tlm->rev.no_walk = 1;\n>>  \n>>  \tprepare_revision_walk(&lm->rev);\n>>  \n>> -\twhile (hashmap_get_size(&lm->paths)) {\n>> -\t\tdata.commit = get_revision(&lm->rev);\n>> -\t\tif (!data.commit)\n>> -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n>> +\tmax_count = lm->rev.max_count;\n>> +\n>> +\tinit_commit_bitmaps(&lm->commit_bitmaps);\n>> +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n>\n> It looks like we initialize and release both `commit_bitmaps` and\n> `scratch` here in `last_modified_run()`. Any reason we wouldn't want to\n> move this to `last_modified_{init,release}()`?\n\nFor lm->commit_bitmaps, at the `cleanup:` label we call bitmap_free() on\n`active_c`, but `lm->commit_bitmaps` still has a pointer to those\nbitmaps. It feels a bit cleaner to me to not exit this function with\nhaving any in `lm` pointing to invalid data.\n(Also note: we don't call deep_clear_commit_bitmaps() because\nthe bitmaps are already freed, the commit_slab of bitmaps isn't)\n\n`lm->scratch` we could move to `last_modified_{init,release}()` but I\ndecided to keep the bitmaps together.\n\n>> +\n>> +\t/*\n>> +\t * lm->rev.commits holds the set of boundary commits for our walk.\n>\n> Naive question: would it be more correct ...\n\nDon't use \"more correct\", I've been told :-P\n\n> ... to say that `rev.commits` is\n> the list of starting commits? Boundary commits sounds like commits on\n> the boundary of what we consider interesting/uninteresting which, from\n> my understanding, is not the case here.\n\nWhy aren't these boundaries? Users can pass uninteresting commits to\nthis command with `--not aaaaaa` or `aaaaaa..bbbbbb`. So in this context\nboundaries are used on both ends, and `queue` and `not_queue` are used\nto store those.\n\n\n>> +\t *\n>> +\t * Loop through each such commit, and place it in the appropriate queue.\n>> +\t */\n>> +\tfor (list = lm->rev.commits; list; list = list->next) {\n>> +\t\tstruct commit *c = list->item;\n>> +\n>> +\t\tif (c->object.flags & BOTTOM) {\n>> +\t\t\tprio_queue_put(&not_queue, c);\n>\n> Ok so commits with the BOTTOM flag are at the boundary of the\n> \"interesting\" commit graph. Thus they are not included in the search and\n> added to the \"not_queue\".\n>\n>> +\t\t\tc->object.flags |= PARENT2;\n>\n> What is the meaning behind the name PARENT2 in this context? From my\n> understanding we are using this flag to denote a commit we are not\n> interested in.\n\nYes, that's correct. It's used to avoid us adding it to the not_queue\nmore than once.\n\n>\n>> +\t\t} else if (!(c->object.flags & PARENT1)) {\n>\n> Same question about PARENT1. It seems to be used to just denote commits\n> that we have already encountered. The names confuse me a bit though.\n\nNaming isn't great, but see my earlier comment.\n\n>> +\t\t\t/*\n>> +\t\t\t * If the commit is a starting point (and hasn't been\n>> +\t\t\t * seen yet), then initialize the set of interesting\n>> +\t\t\t * paths, too.\n>> +\t\t\t */\n>> +\t\t\tstruct bitmap *active;\n>> +\n>> +\t\t\tprio_queue_put(&queue, c);\n>> +\t\t\tc->object.flags |= PARENT1;\n>\n> We queue the commit and mark it as seen. Makes sense.\n>\n>> -\t\tif (data.commit->object.flags & BOUNDARY) {\n>> +\t\t\tactive = get_bitmap(lm, c);\n>> +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n>> +\t\t\t\tbitmap_set(active, i);\n>\n> Here we set up the path bitmap for the commit. At this point, all paths\n> are still \"active\" and thus set accordingly. I'm still not entirely sure\n> though if we really need a path bitmap per commit.\n\nAfter my explanation above, let me know if you still have questions. I\nmust admit it took me a while to have it click in my brain too.\n\n>> +\t\t}\n>> +\t}\n>> +\n>> +\twhile (queue.nr) {\n>> +\t\tint parent_i;\n>> +\t\tstruct commit_list *p;\n>> +\t\tstruct commit *c = prio_queue_get(&queue);\n>> +\t\tstruct bitmap *active_c = get_bitmap(lm, c);\n>> +\n>> +\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n>> +\t\t    (c->object.flags & PARENT2)) {\n>> +\t\t\t/*\n>> +\t\t\t * Either a boundary commit, or we have already seen too\n>> +\t\t\t * many others. Either way, stop here.\n>> +\t\t\t */\n>> +\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n>> +\t\t\tdata.commit = c;\n>>  \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n>> -\t\t\t\t      &data.commit->object.oid, \"\",\n>> -\t\t\t\t      &lm->rev.diffopt);\n>> +\t\t\t\t      &c->object.oid,\n>> +\t\t\t\t      \"\", &lm->rev.diffopt);\n>>  \t\t\tdiff_flush(&lm->rev.diffopt);\n>> +\t\t\tgoto cleanup;\n>> +\t\t}\n>>  \n>> -\t\t\tbreak;\n>> +\t\t/*\n>> +\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n>> +\t\t * in the '--not' queue.\n>> +\t\t */\n>> +\t\trepo_parse_commit(lm->rev.repo, c);\n>> +\n>> +\t\twhile (not_queue.nr) {\n>> +\t\t\tstruct commit_list *np;\n>> +\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n>> +\n>> +\t\t\trepo_parse_commit(lm->rev.repo, n);\n>> +\n>> +\t\t\tfor (np = n->parents; np; np = np->next) {\n>> +\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n>> +\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n>> +\t\t\t\t\tnp->item->object.flags |= PARENT2;\n>> +\t\t\t\t}\n>> +\t\t\t}\n>> +\n>> +\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n>> +\t\t\t\tbreak;\n>\n> If the generation number of 'c' is higher than 'n' we know 'c' cannot be\n> an ancestor of 'n' and thus we continue on. Makes sense.\n\n<3\n\n>>  \t\t}\n>>  \n>> -\t\tif (!maybe_changed_path(lm, data.commit))\n>> -\t\t\tcontinue;\n>> +\t\t/*\n>> +\t\t * Look at each parent and pass on each path that's TREESAME\n>> +\t\t * with that parent. Stop early when no active paths remain.\n>> +\t\t */\n>> +\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n>> +\t\t\tprocess_parent(lm, &queue,\n>> +\t\t\t\t       c, active_c,\n>> +\t\t\t\t       p->item, parent_i);\n>> +\n>> +\t\t\tif (bitmap_is_empty(active_c))\n>> +\t\t\t\tbreak;\n>> +\t\t}\n>>  \n>> -\t\tlog_tree_commit(&lm->rev, data.commit);\n>> +\t\t/*\n>> +\t\t * Paths that remain active, or not TREESAME with any parent,\n>> +\t\t * were changed by 'c'.\n>> +\t\t */\n>> +\t\tif (!bitmap_is_empty(active_c))  {\n>> +\t\t\tdata.commit = c;\n>> +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n>> +\t\t\t\tif (bitmap_get(active_c, i))\n>> +\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n>> +\t\t\t}\n>> +\t\t}\n>> +\n>> +cleanup:\n>> +\t\tbitmap_free(active_c);\n>>  \t}\n>>  \n>> +\tif (hashmap_get_size(&lm->paths))\n>> +\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n>> +\n>> +\tclear_prio_queue(&not_queue);\n>> +\tclear_prio_queue(&queue);\n>> +\tclear_commit_bitmaps(&lm->commit_bitmaps);\n>> +\tbitmap_free(lm->scratch);\n>> +\n>>  \treturn 0;\n>>  }\n> [snip]\n>\n> I've taken an initial look a this patch and have mostly questions so\n> far. Just FYI, after applying this patch locally, the last-modified\n> tests seem to be failing. The command seems to be segfaulting, but I\n> haven't looked into it further.\n\nYeah, sorry about that. Taylor also noticed. In my final review I revived\nsome code I had removed at some point. I brought it back, but didn't do\na final test afterward. He provided a path to fix it[2] (which I also\nhad in my code at some point, but reverted).\n\n[2]: https://lore.kernel.org/git/aPGB%2FFJtjDmyNLvG@nand.local/\n\n-- \nCheers,\nToon\n"},{"id":"529057","messageId":"87plalu7r7.fsf@iotcl.com","threadId":"64332","inReplyTo":"CALnO6CBwuAdBFjESZSYZkChNdU9R17OXDc+CY=Z96QoACPgrpQ@mail.gmail.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-17T10:45:16Z","receivedAt":"2025-10-17T10:45:26Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"\"D. Ben Knoble\" <ben.knoble@gmail.com> writes:\n\n> On Thu, Oct 16, 2025 at 4:39 AM Toon Claes <toon@iotcl.com> wrote:\n>> As an added benefit, this implementation gives more correct results. For\n>> example implementation in 'master' gives:\n>\n> \"More correct\" is a bit of an oxymoron, no? It's either correct or\n> it's not :)\n\nI can rephrase to \"more accurate\" or something that's better suited.\n\n>>     $ git log --max-count=1 --format=%H -- pkt-line.h\n>>     15df15fe07ef66b51302bb77e393f3c5502629de\n>>\n>>     $ git last-modified -- pkt-line.h\n>>     15df15fe07ef66b51302bb77e393f3c5502629de    pkt-line.h\n>>\n>>     $ git last-modified | grep pkt-line.h\n>>     5b49c1af03e600c286f63d9d9c9fb01403230b9f    pkt-line.h\n>\n> It seems this commit is the merge to a maintenance branch, which was\n> authored and committed after the mainline merge but topologically we'd\n> probably consider it \"earlier,\" at least starting from master? Anyway,\n> I'm not clear why this result was produced.\n\nYeah, me neither. But it's a nice side-effect this behavior result goes\naway with this patch.\n\n-- \nCheers,\nToon\n"},{"id":"529058","messageId":"87ms5pu7n6.fsf@iotcl.com","threadId":"64332","inReplyTo":"20251017063701.GA3091356@coredump.intra.peff.net","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-17T10:47:41Z","receivedAt":"2025-10-17T10:47:59Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Thu, Oct 16, 2025 at 10:39:25AM +0200, Toon Claes wrote:\n>\n>> +\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n>> +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n>> +\t\tsize_t k = path_idx(lm, fp->two->path);\n>> +\t\tif (0 <= k && bitmap_get(active_c, k))\n>> +\t\t\tbitmap_set(lm->scratch, k);\n>> +\t\tdiff_free_filepair(fp);\n>> +\t}\n>\n> Just one little oddity while looking at this versus the old patches from\n> Taylor. Here you call diff_free_filepair(). But later...\n>\n>> +\tdiff_queued_diff.nr = 0;\n>> +\tdiff_queue_clear(&diff_queued_diff);\n>\n> ...you call diff_queue_clear(), which frees the filepairs itself. It\n> does the right thing, because you truncate the queue explicitly. But\n> would it be simpler to just leave them in place and let the _clear()\n> function clean up? I.e., this:\n>\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index 40e520ba18..47f2b0ed44 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -315,7 +315,6 @@ static void process_parent(struct last_modified *lm,\n>  \t\tsize_t k = path_idx(lm, fp->two->path);\n>  \t\tif (0 <= k && bitmap_get(active_c, k))\n>  \t\t\tbitmap_set(lm->scratch, k);\n> -\t\tdiff_free_filepair(fp);\n>  \t}\n>  \tfor (i = 0; i < lm->all_paths_nr; i++) {\n>  \t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n> @@ -331,7 +330,6 @@ static void process_parent(struct last_modified *lm,\n>  \t}\n>  \n>  \tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n> -\tdiff_queued_diff.nr = 0;\n>  \tdiff_queue_clear(&diff_queued_diff);\n>  }\n>\n> which feels a lot more idiomatic to me.\n\nHah, yes. I think I ended up in this situation because initially I was\nonly trying to fix memory leaks. Thanks, I will included these changes.\n\n-- \nCheers,\nToon\n"},{"id":"529063","messageId":"87jz0tu3yh.fsf@iotcl.com","threadId":"64332","inReplyTo":"aPGB/FJtjDmyNLvG@nand.local","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-17T12:07:18Z","receivedAt":"2025-10-17T12:07:43Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> On Thu, Oct 16, 2025 at 10:39:25AM +0200, Toon Claes wrote:\n>> [...]\n>>\n>> To avoid computing many first-parent diffs, add another trick on top of\n>> this and check if all paths active in 'c' are DEFINITELY NOT in c's\n>> Bloom filter. Since the commit-graph only stores first-parent diffs in\n>> the Bloom filters, we can only apply this trick to first-parent diffs.\n>\n> OK, up to this point this is the same as the commit message that I wrote\n> with Stolee back in 2020.\n>\n>> Comparing the performance of this new algorithm shows about a 2.6x\n>> improvement on git.git:\n>>\n>>     Benchmark 1: master\n>>       Time (mean ± σ):      3.077 s ±  0.055 s    [User: 3.017 s, System: 0.051 s]\n>>       Range (min … max):    2.947 s …  3.127 s    10 runs\n>>\n>>     Benchmark 2: HEAD\n>>       Time (mean ± σ):      1.181 s ±  0.010 s    [User: 1.139 s, System: 0.038 s]\n>>       Range (min … max):    1.169 s …  1.194 s    10 runs\n>>\n>>     Summary\n>>       HEAD ran\n>>         2.60 ± 0.05 times faster than master\n>>\n>> But when comparing a more extreme example of\n>> `git last-modified -- COPYING t`, the difference is a lot bigger:\n>>\n>>     Benchmark 1: master\n>>       Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n>>       Range (min … max):    4.308 s …  4.509 s    10 runs\n>>\n>>     Benchmark 2: HEAD\n>>       Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n>>       Range (min … max):   810.6 ms … 881.2 ms    10 runs\n>>\n>>     Summary\n>>       HEAD ran\n>>         5.29 ± 0.16 times faster than master\n>\n> These benchmarks are different than the ones that I provided, which is\n> good, since we should be measuring modern Git, not dragging forward\n> stale benchmarks ;-).\n>\n> I imagine that you are just doing a straight last-modified run here in\n> both instances. In the original patch, I timed this both with and\n> without changed-path Bloom filters, which helped illustrate their impact\n> on the changes here.\n>\n> I'd suggest including those benchmarks as well, and potentially running\n> them on linux.git, or another comparably larger open-source repository.\n> git.git is large enough to show some interesting behavior, but I always\n> have found it useful to compare the results against a larger repository\n> as well.\n\nSure.\n\n>> As an added benefit, this implementation gives more correct results. For\n>> example implementation in 'master' gives:\n>>\n>>     $ git log --max-count=1 --format=%H -- pkt-line.h\n>>     15df15fe07ef66b51302bb77e393f3c5502629de\n>>\n>>     $ git last-modified -- pkt-line.h\n>>     15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n>>\n>>     $ git last-modified | grep pkt-line.h\n>>     5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n>>\n>> With the changes in this patch the results of git-last-modified(1)\n>> always match those of `git log --max-count=1`.\n>>\n>> One thing to note though, the results might be outputted in a different\n>> order than before. This is not considerd to be an issue because nowhere\n>> is documented the order is guaranteed.\n>>\n>> Based-on-patches-by: Taylor Blau <me@ttaylorr.com>\n>\n> Stolee and I wrote these patches together many years ago, so he should\n> be credited here as well. Since this patch appears to be substantially\n> based on the original work, I think it is appropriate to include my\n> S-o-b once the patch is ready.\n\nI'm very grateful you (GitHub) have written and shared these patches, so\nI'm happy to give proper attribution.\n\n>> ---\n>> This series revives those changes. I did more thorough deep dive through\n>> the code and the algorithm and got the code working a lot faster. The\n>> benchmark results can be found in the commit message.\n>>\n>> Some changes compared to GitHub's version include:\n>>\n>>  * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n>>    `struct commit_active_paths`.\n>>\n>>  * Removed shortcut code that handled the case when commit and parent\n>>    are fully treesame, and instead always checked 'active_c' whether the\n>>    next parent is worth looking at.\n>>\n>>  * Modified comments and commit message to make the algorithm more\n>>    clear (at least to me).\n>>\n>>  * Mentioned the use of PARENT1 and PARENT2 in object.h.\n>>\n>>  * Removed the use of any global variables.\n>>\n>>  * Less conditions are checked in mark_path() because the hashmap of\n>>    'paths' is considered the single-source of truth.\n>>\n>>  * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n>>    hashmap no more.\n>\n> Thanks for clearly showing what the changes on top are. When I applied\n> this locally and ran it, it pretty quickly segfaulted for me:\n>\n>     expecting success of 8020.3 'last-modified non-recursive':\n>       check_last_modified <<-\\EOF\n>       3 a\n>       1 file\n>       EOF\n>\n>     + check_last_modified\n>     + local indir=\n>     + test 0 != 0\n>     + cat\n>     + git last-modified\n>     Segmentation fault\n>     error: last command exited with $?=139\n>     not ok 3 - last-modified non-recursive\n>     #\n>     #\t\tcheck_last_modified <<-\\EOF\n>     #\t\t3 a\n>     #\t\t1 file\n>     #\t\tEOF\n>     #\n>     1..3\n>\n> Looking through the backtrace, it looks like someone is calling\n> mark_path() with a NULL oid, like so:\n>\n>     (gdb) bt\n>     #0  __memcmp_evex_movbe ()\n>         at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:132\n>     #1  0x00005555555f2c32 in oideq (oid1=0x0, oid2=0x555555a5eeb0)\n>         at ./hash.h:408\n>     #2  0x00005555555f3523 in mark_path (path=0x555555a5eee8 \"a\", oid=0x0,\n>         data=0x7fffffffd650) at builtin/last-modified.c:179\n>\n> , which makes sense, since at the end of the main loop we call\n> mark_path() on all remaining active paths to indicate that they were\n> modified by whatever commit we just popped off the queue.\n>\n> Something like this on top (which matches the original patch that I sent\n> from GitHub's fork) fixes the tests:\n>\n> --- 8< ---\n> diff --git a/builtin/last-modified.c b/builtin/last-modified.c\n> index 40e520ba18..c8f66633a7 100644\n> --- a/builtin/last-modified.c\n> +++ b/builtin/last-modified.c\n> @@ -176,7 +176,7 @@ static void mark_path(const char *path, const struct object_id *oid,\n>  \t * Is it arriving at a version of interest, or is it from a side branch\n>  \t * which did not contribute to the final state?\n>  \t */\n> -\tif (!oideq(oid, &ent->oid))\n> +\tif (oid && !oideq(oid, &ent->oid))\n>  \t\treturn;\n>\n>  \tlast_modified_emit(data->lm, path, data->commit);\n> --- >8 ---\n\nSorry for this oopsie. Right before I sent this patch, I had a version\nthat removed the oideq() condition. In the final diff I noticed and I\ndecided to undo that, but didn't check my tests again. Thanks for the\npatch, because I know I had that at one point as well.\n\nBut this makes me wonder, is there even any value in keeping `oid` on\n`struct last_modified_entry`? I'll have a deeper look into this.\n\n>> +/* Remember to update object flag allocation in object.h */\n>> +#define PARENT1 (1u<<16) /* used instead of SEEN */\n>> +#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n>> +\n>>  struct last_modified_entry {\n>>  \tstruct hashmap_entry hashent;\n>>  \tstruct object_id oid;\n>>  \tstruct bloom_key key;\n>> +\tsize_t diff_idx;\n>>  \tconst char path[FLEX_ARRAY];\n>>  };\n>>\n>> @@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n>>  \treturn strcmp(ent1->path, path ? path : ent2->path);\n>>  }\n>>\n>> +/*\n>> + * Hold a bitmap for each commit we're working with. Each bit represents a path\n>> + * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n>> + */\n>> +define_commit_slab(commit_bitmaps, struct bitmap *);\n>> +\n>\n> Nice, I am glad to see that we are using a bitmap here rather than the\n> hacky 'char *' that we had originally written. I seem to remember that\n> there was a tiny slow-down when using bitmaps, but can't find the\n> discussion anymore. (It wasn't in the internal PR that I originally\n> opened, and I no longer can read messages that far back in history.)\n>\n> It might be worth benchmarking here to see if using a 'char *' is\n> faster. Of course, that's 8x worse in terms of memory usage, but not a\n> huge deal given both the magnitude and typical number of directory\n> elements (you'd need 1024^2 entries in a single tree to occupy even a\n> single MiB of heap).\n\nOkay, I can give it a try.\n\n> Regardless of how you handle the above, I think that the commit slab\n> name here is a little generic. I guess it's OK since this is only\n> visible within this compilation unit, but perhaps something like\n> \"active_paths_bitmap\" would be more descriptive.\n\nI struggled a lot naming this thing, so I'm open to suggestions.\n\n> Likewise, I wonder if we should have elemtype here be just 'struct\n> bitmap'. Unfortunately I don't think the EWAH code has a function like:\n>\n>     void bitmap_init(struct bitmap *);\n>\n> and only has ones that allocate for us. So we may consider adding one,\n> or creating a dummy bitmap and copying its contents, or otherwise.\n>\n>>  struct last_modified {\n>>  \tstruct hashmap paths;\n>>  \tstruct rev_info rev;\n>>  \tbool recursive;\n>>  \tbool show_trees;\n>> +\n>> +\tconst char **all_paths;\n>> +\tsize_t all_paths_nr;\n>\n> I wonder if all_paths should be a strvec here? I think that this code\n> was all written when the type was called argv_array (hilariously, that\n> change took place towards the end of July, 2020, and the --go-faster\n> code where this patch came from was written just a couple of weeks\n> earlier.)\n\nAhha, that might be a good idea. This might allow us to get rid of the\nhashmap, which stops us from storing the paths twice. Not sure what the\nimpact on the performance would be, because the hashmap now is valuable\nfor path_idx() lookups.\n\n>> @@ -196,7 +226,36 @@ static void last_modified_diff(struct diff_queue_struct *q,\n>>  \t}\n>>  }\n>>\n>> -static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n>> +static size_t path_idx(struct last_modified *lm, char *path)\n>> +{\n>> +\tstruct last_modified_entry *ent;\n>> +\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n>> +\t\t\t\t\t  struct last_modified_entry, hashent);\n>> +\n>> +\treturn ent ? ent->diff_idx : -1;\n>> +}\n>> +\n>> +static void pass_to_parent(struct last_modified *lm,\n>> +\t\t\t   struct bitmap *c,\n>> +\t\t\t   struct bitmap *p,\n>> +\t\t\t   size_t pos)\n>> +{\n>> +\tstruct last_modified_entry *ent;\n>> +\tstruct hashmap_iter iter;\n>> +\n>> +\tbitmap_unset(c, pos);\n>> +\n>> +\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n>> +\t\tif (ent->diff_idx == pos) {\n>> +\t\t\tbitmap_set(p, pos);\n>> +\t\t\tbreak;\n>> +\t\t}\n>> +\t}\n>> +}\n>\n> This one I'm not quite following. The original implementation does\n> something like:\n>\n>     c->active[i] = 0;\n>     c->nr--;\n>     p->active[i] = 1;\n>     p->nr++;\n>\n> , where 'i' is an index into the all_paths array. It looks like you are\n> effectively doing the first part of that with the bitmap_unset() call,\n> but I'm confused why you're iterating over paths here.\n>\n> The caller in process_parents() is iterating over all entries that are\n> treesame to the parent, bit by bit. So I think you can just bitmap_set()\n> in the parent directly here, but let me know if I am missing something.\n\nIt is an attempt from my side to optimize things further. I was thinking\na path could have been associated by another commit already. But now\nyou've brought this up, I don't think this no more.\n\nA bit can only be set in two places:\n\n* Initially when a commit is added from lm->rev.commits. We can only\n  have one commit in there, because we count `num_interesting` in\n  populate_paths_from_revs() and abort if it's more than 1.\n\n* Here in pass_to_parent(). A commit only passes a bit to one parent.\n\nSo I'll remove the extra guard in the next version.\n\n>> @@ -220,42 +282,197 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n>>  \treturn false;\n>>  }\n>>\n>> +static void process_parent(struct last_modified *lm,\n>> +\t\t\t   struct prio_queue *queue,\n>> +\t\t\t   struct commit *c, struct bitmap *active_c,\n>> +\t\t\t   struct commit *parent, int parent_i)\n>> +{\n>> +\tsize_t i;\n>> +\tstruct bitmap *active_p;\n>> +\n>> +\trepo_parse_commit(lm->rev.repo, parent);\n>> +\tactive_p = get_bitmap(lm, parent);\n>> +\n>> +\t/*\n>> +\t * The first time entering this function for this commit (i.e. first parent)\n>> +\t * see if Bloom filters will tell us it's worth to do the diff.\n>> +\t */\n>> +\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n>> +\t\tdiff_tree_oid(&parent->object.oid,\n>> +\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n>> +\t\tdiffcore_std(&lm->rev.diffopt);\n>> +\t}\n>> +\n>> +\t/*\n>> +\t * Otherwise, test each path for TREESAME-ness against the parent. If\n>\n> This \"otherwise\" is referencing a piece of the patch that doesn't appear\n> to be here directly, which is how we handle the special case of having\n> nothing in the diff queue, meaning we are treesame at the root.\n\nTrue, I shall drop the \"otherwise\" and rephrase further if needed.\n\n> In the GitHub version of this patch, we pass all active paths to the\n> parent, assign the PARENT1 flag if it doesn't already have it, and put\n> it in the queue as well.\n>\n> In your version, we'd skip past the next for-loop, and do the same\n> pass-to-parent dance below, along with inserting the parent into the\n> prio queue.\n\nThis is the \"shortcut\" I'm mentioning in my cover letter. In my testing\nit seemed it didn't provide any performance gains to keep it. I consider\nless code better code, so I left it out.\n\n> So I think that this is all functionally equivalent, but I had to work\n> through a little bit of the details here, mostly since I haven't looked\n> at or thought about this code in many years ;-).\n>\n>>  static int last_modified_run(struct last_modified *lm)\n>>  {\n>> +\tint max_count, queue_popped = 0;\n>> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n>> +\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n>> +\tstruct commit_list *list;\n>>  \tstruct last_modified_callback_data data = { .lm = lm };\n>>\n>>  \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n>>  \tlm->rev.diffopt.format_callback = last_modified_diff;\n>>  \tlm->rev.diffopt.format_callback_data = &data;\n>> +\tlm->rev.no_walk = 1;\n>\n> This one is new relative to the original patch. Why set no_walk here?\n\nThis comes from\nhttps://github.com/ttaylorr/git/commit/e8ea49705873d28f64b815bd00d14bdf6d48ca4d\n\nWell, it basically squashes various commits together. There are various\ncommits doing different things here. I don't think it's valuable for\nanyone to see the full history of the iterations at GitHub, that's why I\nsquashed it in.\n\nWould you consider it better to not set `no_walk`?\n\n>>  \tprepare_revision_walk(&lm->rev);\n>>\n>> -\twhile (hashmap_get_size(&lm->paths)) {\n>> -\t\tdata.commit = get_revision(&lm->rev);\n>> -\t\tif (!data.commit)\n>> -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n>> +\tmax_count = lm->rev.max_count;\n>> +\n>> +\tinit_commit_bitmaps(&lm->commit_bitmaps);\n>> +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n>> +\n>> +\t/*\n>> +\t * lm->rev.commits holds the set of boundary commits for our walk.\n>> +\t *\n>> +\t * Loop through each such commit, and place it in the appropriate queue.\n>> +\t */\n>> +\tfor (list = lm->rev.commits; list; list = list->next) {\n>\n> Hmm. In the original patch, we look at rev.pending, not rev.commits. The\n> rest of the patch looks good to me and looks like a faithful\n> representation of the original patch from GitHub's fork. Thanks for\n> working on this and making the new last-modified builtin faster ;-).\n\nEuh, interesting. I'll look into it.\n\nThanks for the support!\n\n-- \nCheers,\nToon\n"},{"id":"529078","messageId":"aPJYvYs8W6LrV+0Q@nand.local","threadId":"64332","inReplyTo":"20251017063039.GA3074253@coredump.intra.peff.net","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-17T14:54:53Z","receivedAt":"2025-10-17T14:54:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 17, 2025 at 02:30:39AM -0400, Jeff King wrote:\n> On Thu, Oct 16, 2025 at 07:38:36PM -0400, Taylor Blau wrote:\n>\n> > Looking through the backtrace, it looks like someone is calling\n> > mark_path() with a NULL oid, like so:\n> >\n> >     (gdb) bt\n> >     #0  __memcmp_evex_movbe ()\n> >         at ../sysdeps/x86_64/multiarch/memcmp-evex-movbe.S:132\n> >     #1  0x00005555555f2c32 in oideq (oid1=0x0, oid2=0x555555a5eeb0)\n> >         at ./hash.h:408\n> >     #2  0x00005555555f3523 in mark_path (path=0x555555a5eee8 \"a\", oid=0x0,\n> >         data=0x7fffffffd650) at builtin/last-modified.c:179\n> >\n> > , which makes sense, since at the end of the main loop we call\n> > mark_path() on all remaining active paths to indicate that they were\n> > modified by whatever commit we just popped off the queue.\n>\n> Hmm, sounds like the mark_path() discussion from:\n>\n>   https://lore.kernel.org/git/aHmPHcNQYlhGo8JB@nand.local/\n>\n> coming home to roost. I'm sure you already knew that, but there's maybe\n> an interesting process observation here: in pulling a battle-tested\n> implementation apart into patches to be applied in chunks, we ended up\n> missing a critical part of that original implementation and getting a\n> bug.\n\nHmm. Is that what happened in this case, though?\n\nIn GitHub's version of this code, mark_path() didn't have the NULL-ness\ncheck on 'oid' until we added the \"--go-faster\" mode, which is where\nthis patch is derived from. Looking at the original changes from\nGitHub's side:\n\n--- 8< ---\ndiff --git a/blame-tree.c b/blame-tree.c\n--- a/blame-tree.c\n+++ b/blame-tree.c\n@@ -119,28 +142,38 @@\n static void mark_path(const char *path, const struct object_id *oid,\n \t\t      struct blame_tree_callback_data *data)\n {\n \tstruct blame_tree_entry *ent;\n+\tstruct commit_active_paths *active;\n\n \t/* Is it even a path that we are interested in? */\n \tent = hashmap_get_entry_from_hash(data->paths, strhash(path), path,\n \t\t\t\t\t  struct blame_tree_entry, hashent);\n \tif (!ent)\n \t\treturn;\n\n \t/* Have we already blamed a commit? */\n \tif (ent->commit)\n \t\treturn;\n+\n+\t/* Are we inactive on the current commit? */\n+\tif (data->go_faster) {\n+\t\tactive = active_paths_at(&active_paths, data->commit);\n+\t\tif (active && active->active &&\n+\t\t    !active->active[ent->diff_idx])\n+\t\t\treturn;\n+\t}\n+\n \t/*\n \t * Is it arriving at a version of interest, or is it from a side branch\n \t * which did not contribute to the final state?\n \t */\n-\tif (oidcmp(oid, &ent->oid))\n+\tif (oid && oidcmp(oid, &ent->oid))\n \t\treturn;\n\n \tent->commit = data->commit;\n \tdata->num_interesting--;\n \tif (data->callback)\n \t\tdata->callback(path, data->commit, data->callback_data);\n \thashmap_remove(data->paths, &ent->hashent, path);\n }\n--- >8 ---\n\n, where the above was generated with:\n\n    $ git log -1 --oneline 0603f6d9c3c040c914c1412fab972252c4a765c4 \\\n        -L:mark_path:blame-tree.c\n\n(in this case, 0603f6d9c3 is the hash of the commit that originally\nintroduced these changes on the GitHub side).\n\nSo I don't think that it's the case that we somehow missed this portion\nof the changes when pulling the series apart, but rather that the check\nwas added later on, and not correctly pulled into the version that was\nsubmitted here.\n\nI was wondering if perhaps I had made an error when pulling these\npatches out of GitHub's fork, but even in my b0ae8b3cc0 (blame-tree:\nintroduce '--go-faster' mode, 2025-03-27) from my fork, you can see the\nsame diff in mark_path() as above.\n\n> It's not like we didn't know that was a risk, of course, and the payoff\n> was getting a fresh look at the patches (to improve them and maybe even\n> fix latent bugs). So it's probably something to just live with. But I\n> wonder if/how we could mitigate that risk. When I reorganize patches in\n> a tricky way locally, I often eyeball the diff of the end states\n> (whatever mess I had originally, versus the result of the \"clean\"\n> version), and that might have shown the omission here.\n>\n> I'm not sure if that would have helped here or not. The \"end state\" of\n> the battle-tested version is really GitHub's internal fork. But maybe\n> your original patches extracted from that (tb/blame-tree in your fork, I\n> think) applied on top of the same base point (e.g., the current tip of\n> master) might be an interesting comparison? Or maybe not. The earlier\n> rounds have may have had other adjustments which introduce a bunch of\n> noise.\n\nI share your feeling here in genreal, but I think in this particular\ncase the patches were pulled out correctly (at least with respect to the\nchanges here in mark_path()), and that check was simply dropped or not\nproperly carried over when the patch we're discussing here was written.\n\n> > Nice, I am glad to see that we are using a bitmap here rather than the\n> > hacky 'char *' that we had originally written. I seem to remember that\n> > there was a tiny slow-down when using bitmaps, but can't find the\n> > discussion anymore. (It wasn't in the internal PR that I originally\n> > opened, and I no longer can read messages that far back in history.)\n> >\n> > It might be worth benchmarking here to see if using a 'char *' is\n> > faster. Of course, that's 8x worse in terms of memory usage, but not a\n> > huge deal given both the magnitude and typical number of directory\n> > elements (you'd need 1024^2 entries in a single tree to occupy even a\n> > single MiB of heap).\n>\n> I doubt the memory usage matters too much. We throw away each bitmap\n> after we finish processing its associated commit, so our max memory is\n> really the size of the bitmap/char array times the size of the queue (so\n> effectively the width of the history graph). So yeah, I too would be\n> curious if the performance is actually better with chars.\n>\n> I also wonder how often we pass an unchanged bitmap to our parents\n> (e.g., for the common case that a commit has a single parent, and does\n> not touch any of the active paths, the active set will be the same for\n> both). There's probably an easy-ish optimization to avoid allocating a\n> new bitmap, and to just transfer ownership via pointer.\n\nFunny enough, while we don't have this optimization in the original\nversion of this code, we did handle being TREESAME at the root tree as a\nspecial case in the original blame-tree.c code. Toon dropped that change\nhere which I commented on earlier, but that would be a good opportunity\nto optimize this case.\n\nI don't think we ever bothered to measure how often we were able to just\npass all active path(s) up to the parent, probably because the original\ncode didn't actually use the optimization you're talking about here, and\ninstead did:\n\n    if (!diff_queued_diff.nr) {\n        for (i = 0; i < bt->all_paths_nr; i++) {\n            if (active_c->active[i])\n                pass_to_parent(active_c, active_p, i);\n        }\n\n        if (!(parent->object.flags & PARENT1)) {\n            parent->object.flags |= PARENT1;\n            prio_queue_put(queue, parent);\n\n            ret = 1;\n            goto cleanup;\n        }\n    }\n\n, so that case was just handled specially, but not optimized. But I\ndon't know that you can just pass the bitmap up directly, since the\nparent may already have some bits set if we reached it along some\ndifferent path.\n\nI thought that we had to AND NOT out the bits in lm->scratch here, but\nthose are only set for non-TREESAME paths, so lm->scratch is going to be\nall zeros in that case.\n\nI think you could reasonably do something like the following on top of\nToon's patch, though:\n\n--- 8< ---\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex 40e520ba18..1a9ab3b2b0 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -303,6 +303,18 @@ static void process_parent(struct last_modified *lm,\n \t\tdiffcore_std(&lm->rev.diffopt);\n \t}\n\n+\tif (!diff_queued_diff.nr) {\n+\t\tbitmap_or(active_p, active_c);\n+\t\tfor (i = 0; i < active_c->word_alloc; i++)\n+\t\t\tactive_c->words[i] = 0;\n+\n+\t\tif (!(parent->object.flags & PARENT1)) {\n+\t\t\tparent->object.flags |= PARENT1;\n+\t\t\tprio_queue_put(queue, parent);\n+\t\t}\n+\t\tgoto cleanup;\n+\t}\n+\n \t/*\n \t * Otherwise, test each path for TREESAME-ness against the parent. If\n \t * a path is TREESAME, pass it on to this parent.\n@@ -330,6 +342,7 @@ static void process_parent(struct last_modified *lm,\n \t\tprio_queue_put(queue, parent);\n \t}\n\n+cleanup:\n \tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n \tdiff_queued_diff.nr = 0;\n \tdiff_queue_clear(&diff_queued_diff);\n--- >8 ---\n\n> > Likewise, I wonder if we should have elemtype here be just 'struct\n> > bitmap'. Unfortunately I don't think the EWAH code has a function like:\n> >\n> >     void bitmap_init(struct bitmap *);\n> >\n> > and only has ones that allocate for us. So we may consider adding one,\n> > or creating a dummy bitmap and copying its contents, or otherwise.\n>\n> I thought that, too, though it does change the max memory use a bit.\n> Right now we are storing one pointer per commit (the \"struct bitmap *\")\n> and that is true whether we have processed the commit or not (it is\n> populated while the commit is in the queue, and then NULL after). If we\n> stored the struct directly, that's twice as many bytes (the eword_t\n> pointer, plus a size_t), and it's per commit.\n\nMmm, good point. I wrote this thinking that the commit_slab was going to\nend up a little gross under this patch, with the slab itself having type\n'struct bitmap ***', but I agree with everything you wrote here.\n\n> PS I tried building tb/blame-tree from your repo because I was poking at\n>    how some of it worked (having forgotten everything I ever knew about\n>    it by this point). It does work, but needs this:\n>\n> diff --git a/blame-tree.c b/blame-tree.c\n> index 6addac7b0b..2448f2caf4 100644\n> --- a/blame-tree.c\n> +++ b/blame-tree.c\n> @@ -800,7 +800,6 @@ static int process_parent(struct blame_tree *bt,\n>  \t\tint k = diff2idx(bt, fp->two->path);\n>  \t\tif (0 <= k && active_c->active[k])\n>  \t\t\tscratch[k] = 1;\n> -\t\tdiff_free_filepair(fp);\n>  \t}\n>  \tfor (i = 0; i < bt->all_paths_nr; i++) {\n>  \t\tif (active_c->active[i] && !scratch[i])\n>\n>   on top, since otherwise we try to double-free the filepairs. I'd guess\n>   it is a victim of rebasing across a5aecb2cdc (diff: improve lifecycle\n>   management of diff queues, 2024-09-30), which swapped out\n>   DIFF_QUEUE_CLEAR(), which left freeing the responsibility of the\n>   caller, for diff_queue_clear() which handles that itself.\n\nAh, good catch. When I pulled those patches out a while ago, I think I\nwrote something like, \"this should more or less work, but doesn't, and\nI'll leave it as an exercise to the reader to figure out why ;-).\"\n\nThanks,\nTaylor\n"},{"id":"529240","messageId":"20251021082021.GF259661@coredump.intra.peff.net","threadId":"64332","inReplyTo":"aPJYvYs8W6LrV+0Q@nand.local","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-10-21T08:20:21Z","receivedAt":"2025-10-21T08:20:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Oct 17, 2025 at 10:54:53AM -0400, Taylor Blau wrote:\n\n> > Hmm, sounds like the mark_path() discussion from:\n> >\n> >   https://lore.kernel.org/git/aHmPHcNQYlhGo8JB@nand.local/\n> >\n> > coming home to roost. I'm sure you already knew that, but there's maybe\n> > an interesting process observation here: in pulling a battle-tested\n> > implementation apart into patches to be applied in chunks, we ended up\n> > missing a critical part of that original implementation and getting a\n> > bug.\n> \n> Hmm. Is that what happened in this case, though?\n> [...]\n> I was wondering if perhaps I had made an error when pulling these\n> patches out of GitHub's fork, but even in my b0ae8b3cc0 (blame-tree:\n> introduce '--go-faster' mode, 2025-03-27) from my fork, you can see the\n> same diff in mark_path() as above.\n\nYeah, I think the patches in your fork are correct, and it got lost in\nToon's rewrite. It is probably naive to think we could diff the endpoint\n(your fork vs Toon's patches) to find such changes, though. There have\nbeen too many other cleanups and changes as it was upstreamed. So you\ncan ignore most of my other email as philosophical musing.\n\n> [...some more clever optimizations...]\n\nAll of that looked plausibly correct to me. ;) I'll leave it to Toon to\nexperiment with it for correctness and performance improvements.\n\n-Peff\n"},{"id":"529245","messageId":"87cy6gtym2.fsf@iotcl.com","threadId":"64332","inReplyTo":"87jz0tu3yh.fsf@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-21T09:04:05Z","receivedAt":"2025-10-21T09:04:24Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"> Taylor Blau <me@ttaylorr.com> writes:\n\n>> Nice, I am glad to see that we are using a bitmap here rather than the\n>> hacky 'char *' that we had originally written. I seem to remember that\n>> there was a tiny slow-down when using bitmaps, but can't find the\n>> discussion anymore. (It wasn't in the internal PR that I originally\n>> opened, and I no longer can read messages that far back in history.)\n>>\n>> It might be worth benchmarking here to see if using a 'char *' is\n>> faster. Of course, that's 8x worse in terms of memory usage, but not a\n>> huge deal given both the magnitude and typical number of directory\n>> elements (you'd need 1024^2 entries in a single tree to occupy even a\n>> single MiB of heap).\n\nUsing ewah bitmaps is slightly faster, although the difference is almost\nneglible.\n\n    Benchmark 1: bitmap-ewah\n      Time (mean ± σ):     793.1 ms ±   6.2 ms    [User: 755.1 ms, System: 35.2 ms]\n      Range (min … max):   784.7 ms … 804.8 ms    10 runs\n\n    Benchmark 2: bitmap-chars\n      Time (mean ± σ):     808.9 ms ±  11.2 ms    [User: 770.8 ms, System: 35.4 ms]\n      Range (min … max):   800.2 ms … 830.5 ms    10 runs\n\n    Summary\n      bitmap-ewah ran\n        1.02 ± 0.02 times faster than bitmap-chars\n\nAnd ewah bitmap being more memory efficient, it makes more sense to keep\nusing those.\n\n>> Likewise, I wonder if we should have elemtype here be just 'struct\n>> bitmap'. Unfortunately I don't think the EWAH code has a function like:\n>>\n>>     void bitmap_init(struct bitmap *);\n>>\n>> and only has ones that allocate for us. So we may consider adding one,\n>> or creating a dummy bitmap and copying its contents, or otherwise.\n\nI've done some testing, and to do so I've made bitmap_grow() public.\n\n    Benchmark 1: bitmap-as-pointers\n      Time (mean ± σ):     783.7 ms ±   8.9 ms    [User: 744.1 ms, System: 37.5 ms]\n      Range (min … max):   774.4 ms … 803.4 ms    10 runs\n\n    Benchmark 2: bitmap-as-values\n      Time (mean ± σ):     856.7 ms ±  10.5 ms    [User: 816.0 ms, System: 38.1 ms]\n      Range (min … max):   845.7 ms … 872.5 ms    10 runs\n\n    Summary\n      bitmap-as-pointers ran\n        1.09 ± 0.02 times faster than bitmap-as-values\n\nIt seems using ewah bitmaps as pointers is faster than using bitmaps as\nvalues. I must admit I'm surprised as well, but in case you want to\ndouble check, here's the patch:\n\n------------------------ >8 ------------------------\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex c1316e1019..f607c47506 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -47,7 +47,7 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n  * Hold a bitmap for each commit we're working with. Each bit represents a path\n  * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n  */\n-define_commit_slab(commit_bitmaps, struct bitmap *);\n+define_commit_slab(commit_bitmaps, struct bitmap);\n\n struct last_modified {\n        struct hashmap paths;\n@@ -65,11 +65,12 @@ struct last_modified {\n\n static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n {\n-       struct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);\n-       if (!*bitmap)\n-               *bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n+       struct bitmap *bm = commit_bitmaps_at(&lm->commit_bitmaps, c);\n+       if (!bm->word_alloc) {\n+               bitmap_grow(bm, lm->all_paths_nr);\n+       }\n\n-       return *bitmap;\n+       return bm;\n }\n\n static void last_modified_release(struct last_modified *lm)\n@@ -442,7 +443,8 @@ static int last_modified_run(struct last_modified *lm)\n                }\n\n cleanup:\n-               bitmap_free(active_c);\n+               free(active_c->words);\n+               active_c->word_alloc = 0;\n        }\n\n        if (hashmap_get_size(&lm->paths))\ndiff --git a/ewah/bitmap.c b/ewah/bitmap.c\nindex 55928dada8..2500e3a0d7 100644\n--- a/ewah/bitmap.c\n+++ b/ewah/bitmap.c\n@@ -42,7 +42,7 @@ struct bitmap *bitmap_dup(const struct bitmap *src)\n        return dst;\n }\n\n-static void bitmap_grow(struct bitmap *self, size_t word_alloc)\n+void bitmap_grow(struct bitmap *self, size_t word_alloc)\n {\n        size_t old_size = self->word_alloc;\n        ALLOC_GROW(self->words, word_alloc, self->word_alloc);\ndiff --git a/ewah/ewok.h b/ewah/ewok.h\nindex c29d354236..3316807572 100644\n--- a/ewah/ewok.h\n+++ b/ewah/ewok.h\n@@ -188,6 +188,7 @@ struct bitmap *bitmap_word_alloc(size_t word_alloc);\n struct bitmap *bitmap_dup(const struct bitmap *src);\n void bitmap_set(struct bitmap *self, size_t pos);\n void bitmap_unset(struct bitmap *self, size_t pos);\n+void bitmap_grow(struct bitmap *self, size_t word_alloc);\n int bitmap_get(struct bitmap *self, size_t pos);\n void bitmap_free(struct bitmap *self);\n int bitmap_equals(struct bitmap *self, struct bitmap *other);\n\n\n-- \nCheers,\nToon\n"},{"id":"529263","messageId":"20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com","threadId":"64332","inReplyTo":"20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com","subject":"[PATCH v2] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-21T12:56:19Z","receivedAt":"2025-10-21T12:56:50Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"The current implementation of git-last-modified(1) works by doing a\nrevision walk, and inspecting the diff at each level of that walk to\nannotate entries remaining in the hashmap of paths. In other words, if\nthe diff at some level touches a path which has not yet been associated\nwith a commit, then that commit becomes associated with the path.\n\nWhile a perfectly reasonable implementation, it can perform poorly in\neither one of two scenarios:\n\n  1. There are many entries of interest, in which case there is simply\n     a lot of work to do.\n\n  2. Or, there are (even a few) entries which have not been updated in a\n     long time, and so we must walk through a lot of history in order to\n     find a commit that touches that path.\n\nThis patch rewrites the last-modified implementation that addresses the\nsecond point. The idea behind the algorithm is to propagate a set of\n'active' paths (a path is 'active' if it does not yet belong to a\ncommit) up to parents and do a truncated revision walk.\n\nThe walk is truncated because it does not produce a revision for every\nchange in the original pathspec, but rather only for active paths.\n\nMore specifically, consider a priority queue of commits sorted by\ngeneration number. First, enqueue the set of boundary commits with all\npaths in the original spec marked as interesting.\n\nThen, while the queue is not empty, do the following:\n\n  1. Pop an element, say, 'c', off of the queue, making sure that 'c'\n     isn't reachable by anything in the '--not' set.\n\n  2. For each parent 'p' (with index 'parent_i') of 'c', do the\n     following:\n\n     a. Compute the diff between 'c' and 'p'.\n     b. Pass any active paths that are TREESAME from 'c' to 'p'.\n     c. If 'p' has any active paths, push it onto the queue.\n\n  3. Any path that remains active on 'c' is associated to that commit.\n\nThis ends up being equivalent to doing something like 'git log -1 --\n$path' for each path simultaneously. But, it allows us to go much faster\nthan the original implementation by limiting the number of diffs we\ncompute, since we can avoid parts of history that would have been\nconsidered by the revision walk in the original implementation, but are\nknown to be uninteresting to us because we have already marked all paths\nin that area to be inactive.\n\nTo avoid computing many first-parent diffs, add another trick on top of\nthis and check if all paths active in 'c' are DEFINITELY NOT in c's\nBloom filter. Since the commit-graph only stores first-parent diffs in\nthe Bloom filters, we can only apply this trick to first-parent diffs.\n\nComparing the performance of this new algorithm shows about a 2.5x\nimprovement on git.git:\n\n    Benchmark 1: master   no bloom\n      Time (mean ± σ):      2.868 s ±  0.023 s    [User: 2.811 s, System: 0.051 s]\n      Range (min … max):    2.847 s …  2.926 s    10 runs\n\n    Benchmark 2: master with bloom\n      Time (mean ± σ):     949.9 ms ±  15.2 ms    [User: 907.6 ms, System: 39.5 ms]\n      Range (min … max):   933.3 ms … 971.2 ms    10 runs\n\n    Benchmark 3: HEAD     no bloom\n      Time (mean ± σ):     782.0 ms ±   6.3 ms    [User: 740.7 ms, System: 39.2 ms]\n      Range (min … max):   776.4 ms … 798.2 ms    10 runs\n\n    Benchmark 4: HEAD   with bloom\n      Time (mean ± σ):     307.1 ms ±   1.7 ms    [User: 276.4 ms, System: 29.9 ms]\n      Range (min … max):   303.7 ms … 309.5 ms    10 runs\n\n    Summary\n      HEAD   with bloom ran\n        2.55 ± 0.02 times faster than HEAD     no bloom\n        3.09 ± 0.05 times faster than master with bloom\n        9.34 ± 0.09 times faster than master   no bloom\n\nIn short, the existing implementation is comparably fast *with* Bloom\nfilters as the new implementation is *without* Bloom filters. So, most\nrepositories should get a dramatic speed-up by just deploying this (even\nwithout computing Bloom filters), and all repositories should get faster\nstill when computing Bloom filters.\n\nWhen comparing a more extreme example of\n`git last-modified -- COPYING t`, the difference is even 5 times better:\n\n    Benchmark 1: master\n      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n      Range (min … max):    4.308 s …  4.509 s    10 runs\n\n    Benchmark 2: HEAD\n      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n      Range (min … max):   810.6 ms … 881.2 ms    10 runs\n\n    Summary\n      HEAD ran\n        5.29 ± 0.16 times faster than master\n\nAs an added benefit, results are more consistent now. For example\nimplementation in 'master' gives:\n\n    $ git log --max-count=1 --format=%H -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\n\n    $ git last-modified -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n\n    $ git last-modified | grep pkt-line.h\n    5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n\nWith the changes in this patch the results of git-last-modified(1)\nalways match those of `git log --max-count=1`.\n\nOne thing to note though, the results might be outputted in a different\norder than before. This is not considerd to be an issue because nowhere\nis documented the order is guaranteed.\n\nBased-on-patches-by: Derrick Stolee <stolee@gmail.com>\nBased-on-patches-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\nThe subcommand git-last-modified(1) was based on the patches shared by\nTaylor and the folks at GitHub[1]. That version used an alternative\nimplementation to make it \"go faster\". When I was working on upstreaming\nthose patches, I dropped the patches[2] for this implementation, because\nI didn't see significant improvements.\n\nThis series revives those changes. I did more thorough deep dive through\nthe code and the algorithm and got the code working a lot faster. The\nbenchmark results can be found in the commit message.\n\nSome changes compared to GitHub's version include:\n\n * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n   `struct commit_active_paths`.\n\n * Removed shortcut code that handled the case when commit and parent\n   are fully treesame, and instead always checked 'active_c' whether the\n   next parent is worth looking at.\n\n * Modified comments and commit message to make the algorithm more\n   clear (at least to me).\n\n * Mentioned the use of PARENT1 and PARENT2 in object.h.\n\n * Removed the use of any global variables.\n\n * Less conditions are checked in mark_path() because the hashmap of\n   'paths' is considered the single-source of truth.\n\n * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n   hashmap no more.\n\n[1]: https://lore.kernel.org/git/Z+XJ+1L3PnC9Dyba@nand.local/\n[2]: https://lore.kernel.org/git/20250630-toon-new-blame-tree-v3-0-3516025dc3bc@iotcl.com/\n---\nChanges in v2:\n- Add benchmark results comparing repositories with and without Bloom\n  filters in commit message.\n- Add Stolee and Taylor in the commit message trailers.\n- Fix segfault by checking if 'oid' is set in mark_path().\n- Remove hashmap lookup in pass_to_parent().\n- Remove manually calling diff_free_filepair().\n- Rename commit slab bitmap to \"active_paths_bitmap\".\n- Link to v1: https://lore.kernel.org/r/20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com\n\nRange-diff versus v1\n\n1:  f7d169e846 ! 1:  e2aa8e1fa0 last-modified: implement faster algorithm\n    @@ Commit message\n         Bloom filter. Since the commit-graph only stores first-parent diffs in\n         the Bloom filters, we can only apply this trick to first-parent diffs.\n\n    -    Comparing the performance of this new algorithm shows about a 2.6x\n    +    Comparing the performance of this new algorithm shows about a 2.5x\n         improvement on git.git:\n\n    -        Benchmark 1: master\n    -          Time (mean ± σ):      3.077 s ±  0.055 s    [User: 3.017 s, System: 0.051 s]\n    -          Range (min … max):    2.947 s …  3.127 s    10 runs\n    +        Benchmark 1: master   no bloom\n    +          Time (mean ± σ):      2.868 s ±  0.023 s    [User: 2.811 s, System: 0.051 s]\n    +          Range (min … max):    2.847 s …  2.926 s    10 runs\n\n    -        Benchmark 2: HEAD\n    -          Time (mean ± σ):      1.181 s ±  0.010 s    [User: 1.139 s, System: 0.038 s]\n    -          Range (min … max):    1.169 s …  1.194 s    10 runs\n    +        Benchmark 2: master with bloom\n    +          Time (mean ± σ):     949.9 ms ±  15.2 ms    [User: 907.6 ms, System: 39.5 ms]\n    +          Range (min … max):   933.3 ms … 971.2 ms    10 runs\n    +\n    +        Benchmark 3: HEAD     no bloom\n    +          Time (mean ± σ):     782.0 ms ±   6.3 ms    [User: 740.7 ms, System: 39.2 ms]\n    +          Range (min … max):   776.4 ms … 798.2 ms    10 runs\n    +\n    +        Benchmark 4: HEAD   with bloom\n    +          Time (mean ± σ):     307.1 ms ±   1.7 ms    [User: 276.4 ms, System: 29.9 ms]\n    +          Range (min … max):   303.7 ms … 309.5 ms    10 runs\n\n             Summary\n    -          HEAD ran\n    -            2.60 ± 0.05 times faster than master\n    +          HEAD   with bloom ran\n    +            2.55 ± 0.02 times faster than HEAD     no bloom\n    +            3.09 ± 0.05 times faster than master with bloom\n    +            9.34 ± 0.09 times faster than master   no bloom\n\n    -    But when comparing a more extreme example of\n    -    `git last-modified -- COPYING t`, the difference is a lot bigger:\n    +    In short, the existing implementation is comparably fast *with* Bloom\n    +    filters as the new implementation is *without* Bloom filters. So, most\n    +    repositories should get a dramatic speed-up by just deploying this (even\n    +    without computing Bloom filters), and all repositories should get faster\n    +    still when computing Bloom filters.\n    +\n    +    When comparing a more extreme example of\n    +    `git last-modified -- COPYING t`, the difference is even 5 times better:\n\n             Benchmark 1: master\n               Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n    @@ Commit message\n               HEAD ran\n                 5.29 ± 0.16 times faster than master\n\n    -    As an added benefit, this implementation gives more correct results. For\n    -    example implementation in 'master' gives:\n    +    As an added benefit, results are more consistent now. For example\n    +    implementation in 'master' gives:\n\n             $ git log --max-count=1 --format=%H -- pkt-line.h\n             15df15fe07ef66b51302bb77e393f3c5502629de\n    @@ Commit message\n         order than before. This is not considerd to be an issue because nowhere\n         is documented the order is guaranteed.\n\n    +    Based-on-patches-by: Derrick Stolee <stolee@gmail.com>\n         Based-on-patches-by: Taylor Blau <me@ttaylorr.com>\n    +    Signed-off-by: Taylor Blau <me@ttaylorr.com>\n         Signed-off-by: Toon Claes <toon@iotcl.com>\n\n      ## builtin/last-modified.c ##\n    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus\n     +\n     +\tconst char **all_paths;\n     +\tsize_t all_paths_nr;\n    -+\tstruct commit_bitmaps commit_bitmaps;\n    ++\tstruct commit_bitmaps active_paths_bitmap;\n     +\n     +\t/* 'scratch' bitmap to avoid allocating every proccess_parent() */\n     +\tstruct bitmap *scratch;\n    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus\n\n     +static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n     +{\n    -+\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);\n    ++\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->active_paths_bitmap, c);\n     +\tif (!*bitmap)\n     +\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n     +\n    @@ builtin/last-modified.c: static void last_modified_release(struct last_modified\n      }\n\n      struct last_modified_callback_data {\n    +@@ builtin/last-modified.c: static void mark_path(const char *path, const struct object_id *oid,\n    + \t * Is it arriving at a version of interest, or is it from a side branch\n    + \t * which did not contribute to the final state?\n    + \t */\n    +-\tif (!oideq(oid, &ent->oid))\n    ++\tif (oid && !oideq(oid, &ent->oid))\n    + \t\treturn;\n    +\n    + \tlast_modified_emit(data->lm, path, data->commit);\n     @@ builtin/last-modified.c: static void last_modified_diff(struct diff_queue_struct *q,\n      \t}\n      }\n    @@ builtin/last-modified.c: static void last_modified_diff(struct diff_queue_struct\n     +\t\t\t   struct bitmap *p,\n     +\t\t\t   size_t pos)\n     +{\n    -+\tstruct last_modified_entry *ent;\n    -+\tstruct hashmap_iter iter;\n    -+\n     +\tbitmap_unset(c, pos);\n    -+\n    -+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n    -+\t\tif (ent->diff_idx == pos) {\n    -+\t\t\tbitmap_set(p, pos);\n    -+\t\t\tbreak;\n    -+\t\t}\n    -+\t}\n    ++\tbitmap_set(p, pos);\n     +}\n     +\n     +static bool maybe_changed_path(struct last_modified *lm,\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t}\n     +\n     +\t/*\n    -+\t * Otherwise, test each path for TREESAME-ness against the parent. If\n    -+\t * a path is TREESAME, pass it on to this parent.\n    ++\t * Test each path for TREESAME-ness against the parent. If a path is\n    ++\t * TREESAME, pass it on to this parent.\n     +\t *\n     +\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n     +\t * Then, pass paths that *are* TREESAME and active to the parent.\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\tsize_t k = path_idx(lm, fp->two->path);\n     +\t\tif (0 <= k && bitmap_get(active_c, k))\n     +\t\t\tbitmap_set(lm->scratch, k);\n    -+\t\tdiff_free_filepair(fp);\n     +\t}\n     +\tfor (i = 0; i < lm->all_paths_nr; i++) {\n     +\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t}\n     +\n     +\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n    -+\tdiff_queued_diff.nr = 0;\n     +\tdiff_queue_clear(&diff_queued_diff);\n     +}\n     +\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n     +\tmax_count = lm->rev.max_count;\n     +\n    -+\tinit_commit_bitmaps(&lm->commit_bitmaps);\n    ++\tinit_commit_bitmaps(&lm->active_paths_bitmap);\n     +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n     +\n     +\t/*\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\n     +\t\t\tprio_queue_put(&queue, c);\n     +\t\t\tc->object.flags |= PARENT1;\n    -\n    --\t\tif (data.commit->object.flags & BOUNDARY) {\n    ++\n     +\t\t\tactive = get_bitmap(lm, c);\n     +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n     +\t\t\t\tbitmap_set(active, i);\n     +\t\t}\n     +\t}\n    -+\n    +\n    +-\t\tif (data.commit->object.flags & BOUNDARY) {\n     +\twhile (queue.nr) {\n     +\t\tint parent_i;\n     +\t\tstruct commit_list *p;\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\tif (bitmap_is_empty(active_c))\n     +\t\t\t\tbreak;\n     +\t\t}\n    -\n    --\t\tlog_tree_commit(&lm->rev, data.commit);\n    ++\n     +\t\t/*\n     +\t\t * Paths that remain active, or not TREESAME with any parent,\n     +\t\t * were changed by 'c'.\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n     +\t\t\t}\n     +\t\t}\n    -+\n    +\n    +-\t\tlog_tree_commit(&lm->rev, data.commit);\n     +cleanup:\n     +\t\tbitmap_free(active_c);\n      \t}\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\n     +\tclear_prio_queue(&not_queue);\n     +\tclear_prio_queue(&queue);\n    -+\tclear_commit_bitmaps(&lm->commit_bitmaps);\n    ++\tclear_commit_bitmaps(&lm->active_paths_bitmap);\n     +\tbitmap_free(lm->scratch);\n     +\n      \treturn 0;\n---\n builtin/last-modified.c  | 243 ++++++++++++++++++++++++++++++++++++++++++++---\n object.h                 |   1 +\n t/t8020-last-modified.sh |   2 +-\n 3 files changed, 230 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex ae8b36a2c3..e9050485a9 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -2,26 +2,32 @@\n #include \"bloom.h\"\n #include \"builtin.h\"\n #include \"commit-graph.h\"\n+#include \"commit-slab.h\"\n #include \"commit.h\"\n #include \"config.h\"\n-#include \"environment.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"environment.h\"\n+#include \"ewah/ewok.h\"\n #include \"hashmap.h\"\n #include \"hex.h\"\n-#include \"log-tree.h\"\n #include \"object-name.h\"\n #include \"object.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n \n+/* Remember to update object flag allocation in object.h */\n+#define PARENT1 (1u<<16) /* used instead of SEEN */\n+#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n+\n struct last_modified_entry {\n \tstruct hashmap_entry hashent;\n \tstruct object_id oid;\n \tstruct bloom_key key;\n+\tsize_t diff_idx;\n \tconst char path[FLEX_ARRAY];\n };\n \n@@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n \treturn strcmp(ent1->path, path ? path : ent2->path);\n }\n \n+/*\n+ * Hold a bitmap for each commit we're working with. Each bit represents a path\n+ * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n+ */\n+define_commit_slab(commit_bitmaps, struct bitmap *);\n+\n struct last_modified {\n \tstruct hashmap paths;\n \tstruct rev_info rev;\n \tbool recursive;\n \tbool show_trees;\n+\n+\tconst char **all_paths;\n+\tsize_t all_paths_nr;\n+\tstruct commit_bitmaps active_paths_bitmap;\n+\n+\t/* 'scratch' bitmap to avoid allocating every proccess_parent() */\n+\tstruct bitmap *scratch;\n };\n \n+static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->active_paths_bitmap, c);\n+\tif (!*bitmap)\n+\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n+\n+\treturn *bitmap;\n+}\n+\n static void last_modified_release(struct last_modified *lm)\n {\n \tstruct hashmap_iter iter;\n@@ -54,6 +82,8 @@ static void last_modified_release(struct last_modified *lm)\n \n \thashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent);\n \trelease_revisions(&lm->rev);\n+\n+\tfree(lm->all_paths);\n }\n \n struct last_modified_callback_data {\n@@ -146,7 +176,7 @@ static void mark_path(const char *path, const struct object_id *oid,\n \t * Is it arriving at a version of interest, or is it from a side branch\n \t * which did not contribute to the final state?\n \t */\n-\tif (!oideq(oid, &ent->oid))\n+\tif (oid && !oideq(oid, &ent->oid))\n \t\treturn;\n \n \tlast_modified_emit(data->lm, path, data->commit);\n@@ -196,7 +226,27 @@ static void last_modified_diff(struct diff_queue_struct *q,\n \t}\n }\n \n-static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n+static size_t path_idx(struct last_modified *lm, char *path)\n+{\n+\tstruct last_modified_entry *ent;\n+\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n+\t\t\t\t\t  struct last_modified_entry, hashent);\n+\n+\treturn ent ? ent->diff_idx : -1;\n+}\n+\n+static void pass_to_parent(struct last_modified *lm,\n+\t\t\t   struct bitmap *c,\n+\t\t\t   struct bitmap *p,\n+\t\t\t   size_t pos)\n+{\n+\tbitmap_unset(c, pos);\n+\tbitmap_set(p, pos);\n+}\n+\n+static bool maybe_changed_path(struct last_modified *lm,\n+\t\t\t       struct commit *origin,\n+\t\t\t       struct bitmap *active)\n {\n \tstruct bloom_filter *filter;\n \tstruct last_modified_entry *ent;\n@@ -213,6 +263,9 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \t\treturn true;\n \n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tif (active && !bitmap_get(active, ent->diff_idx))\n+\t\t\tcontinue;\n+\n \t\tif (bloom_filter_contains(filter, &ent->key,\n \t\t\t\t\t  lm->rev.bloom_filter_settings))\n \t\t\treturn true;\n@@ -220,42 +273,195 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \treturn false;\n }\n \n+static void process_parent(struct last_modified *lm,\n+\t\t\t   struct prio_queue *queue,\n+\t\t\t   struct commit *c, struct bitmap *active_c,\n+\t\t\t   struct commit *parent, int parent_i)\n+{\n+\tsize_t i;\n+\tstruct bitmap *active_p;\n+\n+\trepo_parse_commit(lm->rev.repo, parent);\n+\tactive_p = get_bitmap(lm, parent);\n+\n+\t/*\n+\t * The first time entering this function for this commit (i.e. first parent)\n+\t * see if Bloom filters will tell us it's worth to do the diff.\n+\t */\n+\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n+\t\tdiff_tree_oid(&parent->object.oid,\n+\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n+\t\tdiffcore_std(&lm->rev.diffopt);\n+\t}\n+\n+\t/*\n+\t * Test each path for TREESAME-ness against the parent. If a path is\n+\t * TREESAME, pass it on to this parent.\n+\t *\n+\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n+\t * Then, pass paths that *are* TREESAME and active to the parent.\n+\t */\n+\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n+\t\tsize_t k = path_idx(lm, fp->two->path);\n+\t\tif (0 <= k && bitmap_get(active_c, k))\n+\t\t\tbitmap_set(lm->scratch, k);\n+\t}\n+\tfor (i = 0; i < lm->all_paths_nr; i++) {\n+\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n+\t\t\tpass_to_parent(lm, active_c, active_p, i);\n+\t}\n+\n+\t/*\n+\t * If parent has any active paths, put it on the queue (if not already).\n+\t */\n+\tif (!bitmap_is_empty(active_p) && !(parent->object.flags & PARENT1)) {\n+\t\tparent->object.flags |= PARENT1;\n+\t\tprio_queue_put(queue, parent);\n+\t}\n+\n+\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n+\tdiff_queue_clear(&diff_queued_diff);\n+}\n+\n static int last_modified_run(struct last_modified *lm)\n {\n+\tint max_count, queue_popped = 0;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit_list *list;\n \tstruct last_modified_callback_data data = { .lm = lm };\n \n \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n \tlm->rev.diffopt.format_callback = last_modified_diff;\n \tlm->rev.diffopt.format_callback_data = &data;\n+\tlm->rev.no_walk = 1;\n \n \tprepare_revision_walk(&lm->rev);\n \n-\twhile (hashmap_get_size(&lm->paths)) {\n-\t\tdata.commit = get_revision(&lm->rev);\n-\t\tif (!data.commit)\n-\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\tmax_count = lm->rev.max_count;\n+\n+\tinit_commit_bitmaps(&lm->active_paths_bitmap);\n+\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n+\n+\t/*\n+\t * lm->rev.commits holds the set of boundary commits for our walk.\n+\t *\n+\t * Loop through each such commit, and place it in the appropriate queue.\n+\t */\n+\tfor (list = lm->rev.commits; list; list = list->next) {\n+\t\tstruct commit *c = list->item;\n+\n+\t\tif (c->object.flags & BOTTOM) {\n+\t\t\tprio_queue_put(&not_queue, c);\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t} else if (!(c->object.flags & PARENT1)) {\n+\t\t\t/*\n+\t\t\t * If the commit is a starting point (and hasn't been\n+\t\t\t * seen yet), then initialize the set of interesting\n+\t\t\t * paths, too.\n+\t\t\t */\n+\t\t\tstruct bitmap *active;\n+\n+\t\t\tprio_queue_put(&queue, c);\n+\t\t\tc->object.flags |= PARENT1;\n+\n+\t\t\tactive = get_bitmap(lm, c);\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\t\t\tbitmap_set(active, i);\n+\t\t}\n+\t}\n \n-\t\tif (data.commit->object.flags & BOUNDARY) {\n+\twhile (queue.nr) {\n+\t\tint parent_i;\n+\t\tstruct commit_list *p;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tstruct bitmap *active_c = get_bitmap(lm, c);\n+\n+\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n+\t\t    (c->object.flags & PARENT2)) {\n+\t\t\t/*\n+\t\t\t * Either a boundary commit, or we have already seen too\n+\t\t\t * many others. Either way, stop here.\n+\t\t\t */\n+\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n+\t\t\tdata.commit = c;\n \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n-\t\t\t\t      &data.commit->object.oid, \"\",\n-\t\t\t\t      &lm->rev.diffopt);\n+\t\t\t\t      &c->object.oid,\n+\t\t\t\t      \"\", &lm->rev.diffopt);\n \t\t\tdiff_flush(&lm->rev.diffopt);\n+\t\t\tgoto cleanup;\n+\t\t}\n \n-\t\t\tbreak;\n+\t\t/*\n+\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n+\t\t * in the '--not' queue.\n+\t\t */\n+\t\trepo_parse_commit(lm->rev.repo, c);\n+\n+\t\twhile (not_queue.nr) {\n+\t\t\tstruct commit_list *np;\n+\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n+\n+\t\t\trepo_parse_commit(lm->rev.repo, n);\n+\n+\t\t\tfor (np = n->parents; np; np = np->next) {\n+\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n+\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n+\t\t\t\t\tnp->item->object.flags |= PARENT2;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n+\t\t\t\tbreak;\n \t\t}\n \n-\t\tif (!maybe_changed_path(lm, data.commit))\n-\t\t\tcontinue;\n+\t\t/*\n+\t\t * Look at each parent and pass on each path that's TREESAME\n+\t\t * with that parent. Stop early when no active paths remain.\n+\t\t */\n+\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n+\t\t\tprocess_parent(lm, &queue,\n+\t\t\t\t       c, active_c,\n+\t\t\t\t       p->item, parent_i);\n+\n+\t\t\tif (bitmap_is_empty(active_c))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/*\n+\t\t * Paths that remain active, or not TREESAME with any parent,\n+\t\t * were changed by 'c'.\n+\t\t */\n+\t\tif (!bitmap_is_empty(active_c))  {\n+\t\t\tdata.commit = c;\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\t\t\t\tif (bitmap_get(active_c, i))\n+\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n+\t\t\t}\n+\t\t}\n \n-\t\tlog_tree_commit(&lm->rev, data.commit);\n+cleanup:\n+\t\tbitmap_free(active_c);\n \t}\n \n+\tif (hashmap_get_size(&lm->paths))\n+\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\n+\tclear_prio_queue(&not_queue);\n+\tclear_prio_queue(&queue);\n+\tclear_commit_bitmaps(&lm->active_paths_bitmap);\n+\tbitmap_free(lm->scratch);\n+\n \treturn 0;\n }\n \n static int last_modified_init(struct last_modified *lm, struct repository *r,\n \t\t\t      const char *prefix, int argc, const char **argv)\n {\n+\tstruct hashmap_iter iter;\n+\tstruct last_modified_entry *ent;\n+\n \thashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);\n \n \trepo_init_revisions(r, &lm->rev, prefix);\n@@ -280,6 +486,13 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \tif (populate_paths_from_revs(lm) < 0)\n \t\treturn error(_(\"unable to setup last-modified\"));\n \n+\tlm->all_paths = xcalloc(hashmap_get_size(&lm->paths), sizeof(const char *));\n+\tlm->all_paths_nr = 0;\n+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tent->diff_idx = lm->all_paths_nr++;\n+\t\tlm->all_paths[ent->diff_idx] = ent->path;\n+\t}\n+\n \treturn 0;\n }\n \ndiff --git a/object.h b/object.h\nindex 8c3c1c46e1..fa504a09c0 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n  * http-push.c:                          11-----14\n  * commit-graph.c:                                15\n  * commit-reach.c:                                  16-----19\n+ * builtin/last-modified.c:                         1617\n  * sha1-name.c:                                              20\n  * list-objects-filter.c:                                      21\n  * bloom.c:                                                    2122\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 61f00bc15c..a4c1114ee2 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -57,9 +57,9 @@ test_expect_success 'last-modified recursive' '\n \n test_expect_success 'last-modified recursive with show-trees' '\n \tcheck_last_modified -r -t <<-\\EOF\n-\t3 a\n \t3 a/b\n \t3 a/b/file\n+\t3 a\n \t2 a/file\n \t1 file\n \tEOF\n\n---\nbase-commit: 133d151831d32bdcc02422599a3f26cef44f929b\nchange-id: 20251009-b4-toon-last-modified-faster-4c8956a95261\n\n"},{"id":"529264","messageId":"878qh4tnop.fsf@iotcl.com","threadId":"64332","inReplyTo":"87jz0tu3yh.fsf@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-21T13:00:06Z","receivedAt":"2025-10-21T13:00:18Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"> Taylor Blau <me@ttaylorr.com> writes:\n\n>> I'd suggest including those benchmarks as well, and potentially running\n>> them on linux.git, or another comparably larger open-source repository.\n>> git.git is large enough to show some interesting behavior, but I always\n>> have found it useful to compare the results against a larger repository\n>> as well.\n\nI've submitted v2 of my patch. In that version I included the benchmark\nfor a repo without and with Bloom filters. But I didn't include\nbenchmarks on linux.git. So for the record I'm sharing it here:\n\n    Benchmark 1: master   no bloom\n      Time (mean ± σ):     12.290 s ±  0.105 s    [User: 11.893 s, System: 0.370 s]\n      Range (min … max):   12.089 s … 12.461 s    10 runs\n\n    Benchmark 2: master with bloom\n      Time (mean ± σ):      1.536 s ±  0.072 s    [User: 1.418 s, System: 0.114 s]\n      Range (min … max):    1.500 s …  1.740 s    10 runs\n\n    Benchmark 3: HEAD     no bloom\n      Time (mean ± σ):     868.7 ms ±   3.0 ms    [User: 810.7 ms, System: 56.1 ms]\n      Range (min … max):   863.1 ms … 873.5 ms    10 runs\n\n    Benchmark 4: HEAD   with bloom\n      Time (mean ± σ):     110.0 ms ±   1.8 ms    [User: 89.3 ms, System: 20.3 ms]\n      Range (min … max):   106.6 ms … 114.2 ms    27 runs\n\n    Summary\n      HEAD   with bloom ran\n        7.90 ± 0.13 times faster than HEAD     no bloom\n       13.96 ± 0.69 times faster than master with bloom\n      111.73 ± 2.02 times faster than master   no bloom\n\n-- \nCheers,\nToon\n"},{"id":"529307","messageId":"xmqqy0p4uoqc.fsf@gitster.g","threadId":"64332","inReplyTo":"20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-10-21T17:52:11Z","receivedAt":"2025-10-21T17:52:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Toon Claes <toon@iotcl.com> writes:\n\n> +static size_t path_idx(struct last_modified *lm, char *path)\n> +{\n> +\tstruct last_modified_entry *ent;\n> +\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n> +\t\t\t\t\t  struct last_modified_entry, hashent);\n> +\n> +\treturn ent ? ent->diff_idx : -1;\n> +}\n\nsize_t is unsigned and cannot reutrn -1 sanely, unless the caller\nknows that ((size_t)-1) signals an error.  The compiler warns, and\nwe compile with -Werror, so we end up getting\n\n    builtin/last-modified.c: In function 'path_idx':\n    builtin/last-modified.c:235:38: error: operand of '?:' changes signedness from 'int' to 'size_t' {aka 'long unsigned int'} due to unsignedness of other operand [-Werror=sign-compare]\n      235 |         return ent ? ent->diff_idx : -1;\n          |                                      ^~\n\n> +static void pass_to_parent(struct last_modified *lm,\n> +\t\t\t   struct bitmap *c,\n> +\t\t\t   struct bitmap *p,\n> +\t\t\t   size_t pos)\n> +{\n> +\tbitmap_unset(c, pos);\n> +\tbitmap_set(p, pos);\n> +}\n\nMark lm as UNUSED, or we'd get \n\n    builtin/last-modified.c: In function 'pass_to_parent':\n    builtin/last-modified.c:238:50: error: unused parameter 'lm' [-Werror=unused-parameter]\n      238 | static void pass_to_parent(struct last_modified *lm,\n          |                            ~~~~~~~~~~~~~~~~~~~~~~^~\n\n> @@ -220,42 +273,195 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n>  \treturn false;\n>  }\n>  \n> +static void process_parent(struct last_modified *lm,\n> +\t\t\t   struct prio_queue *queue,\n> +\t\t\t   struct commit *c, struct bitmap *active_c,\n> +\t\t\t   struct commit *parent, int parent_i)\n> +{\n> +\tsize_t i;\n> +...\n> +\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n\nOur -Wsign-compare forces the compiler to give a stupid warning\nhere, that i is unsigned and diff_queued_diff.nr is signed.  \n\n    builtin/last-modified.c: In function 'process_parent':\n    builtin/last-modified.c:304:23: error: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Werror=sign-compare]\n      304 |         for (i = 0; i < diff_queued_diff.nr; i++) {\n          |                       ^\n\nYes, it is comparing unsigned with signed but so what?\n\nAs people may now know, my preference is to wean ourselves off of\nthis dogmatic trust in -Wsign-compare but those who disagree and want\nto remove #define DISABLE_SIGN_COMPARE_WARNINGS should help our poor\ncompiler here by telling it that this comparison is perfectly fine.\n\nWe know diff_queued_diff.nr is an int, and i is size_t, but we also\nknow diff_queued_diff.nr won't be negative (or we have much bigger\nproblems) and cannot be larger than what size_t can represent.\n\n> +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n> +\t\tsize_t k = path_idx(lm, fp->two->path);\n> +\t\tif (0 <= k && bitmap_get(active_c, k))\n> +\t\t\tbitmap_set(lm->scratch, k);\n> +\t}\n\nEarlier path_idx() wanted to signal an error by returning negative,\nbut the type is size_t that is unsigned so it cannot do so.  We\ninstead get\n\n    builtin/last-modified.c:307:23: error: comparison of unsigned expression in '>= 0' is always true [-Werror=type-limits]\n      307 |                 if (0 <= k && bitmap_get(active_c, k))\n          |                       ^~\n\nand in this case we actually deserve it (in the sense that this is\nnot the fault of dogmatic trust in -Wsign-compare; this is caused by\nusing size_t to count things).\n\nAnd the solution for this is *not* \"size_t\" -> \"ssize_t\", because\nssize_t is not \"store half the range of size_t with negative values\nreserved for something else like errors\".  Its width can be much\nnarrower (this came up in a separate thread very recently [*]).\nInstead we'd need something ugly like\n\n\tif (k != (size_t)-1 && bitmap_get(active_c, k))\n\nA quick band-aid patch to make it compile is attached at the end,\nbut it does not try to address the root causes, which are abuse of\nsize_t as count_t and religious use of \"-Wsign-compare\" [*].\n\n\n[Reference]\n\n* https://lore.kernel.org/git/9eafee4d-ea94-4382-ada0-58000d229d2e@gmail.com/\n* https://staticthinking.wordpress.com/2023/07/25/wsign-compare-is-garbage/\n\n\n builtin/last-modified.c | 11 +++++------\n 1 file changed, 5 insertions(+), 6 deletions(-)\n\ndiff --git c/builtin/last-modified.c w/builtin/last-modified.c\nindex e9050485a9..6135bcc584 100644\n--- c/builtin/last-modified.c\n+++ w/builtin/last-modified.c\n@@ -232,10 +232,10 @@ static size_t path_idx(struct last_modified *lm, char *path)\n \tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n \t\t\t\t\t  struct last_modified_entry, hashent);\n \n-\treturn ent ? ent->diff_idx : -1;\n+\treturn ent ? ent->diff_idx : (size_t)-1;\n }\n \n-static void pass_to_parent(struct last_modified *lm,\n+static void pass_to_parent(struct last_modified *lm UNUSED,\n \t\t\t   struct bitmap *c,\n \t\t\t   struct bitmap *p,\n \t\t\t   size_t pos)\n@@ -278,7 +278,6 @@ static void process_parent(struct last_modified *lm,\n \t\t\t   struct commit *c, struct bitmap *active_c,\n \t\t\t   struct commit *parent, int parent_i)\n {\n-\tsize_t i;\n \tstruct bitmap *active_p;\n \n \trepo_parse_commit(lm->rev.repo, parent);\n@@ -301,13 +300,13 @@ static void process_parent(struct last_modified *lm,\n \t * First, collect all paths that are *not* TREESAME in 'scratch'.\n \t * Then, pass paths that *are* TREESAME and active to the parent.\n \t */\n-\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n+\tfor (int i = 0; i < diff_queued_diff.nr; i++) {\n \t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n \t\tsize_t k = path_idx(lm, fp->two->path);\n-\t\tif (0 <= k && bitmap_get(active_c, k))\n+\t\tif (k != (size_t)-1 && bitmap_get(active_c, k))\n \t\t\tbitmap_set(lm->scratch, k);\n \t}\n-\tfor (i = 0; i < lm->all_paths_nr; i++) {\n+\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n \t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n \t\t\tpass_to_parent(lm, active_c, active_p, i);\n \t}\n\n"},{"id":"529341","messageId":"aPgkwnq87UeusC6v@nand.local","threadId":"64332","inReplyTo":"xmqqy0p4uoqc.fsf@gitster.g","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-22T00:26:42Z","receivedAt":"2025-10-22T00:26:44Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Oct 21, 2025 at 10:52:11AM -0700, Junio C Hamano wrote:\n> > +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n> > +\t\tsize_t k = path_idx(lm, fp->two->path);\n> > +\t\tif (0 <= k && bitmap_get(active_c, k))\n> > +\t\t\tbitmap_set(lm->scratch, k);\n> > +\t}\n>\n> Earlier path_idx() wanted to signal an error by returning negative,\n> but the type is size_t that is unsigned so it cannot do so.  We\n> instead get\n>\n>     builtin/last-modified.c:307:23: error: comparison of unsigned expression in '>= 0' is always true [-Werror=type-limits]\n>       307 |                 if (0 <= k && bitmap_get(active_c, k))\n>           |                       ^~\n>\n> and in this case we actually deserve it (in the sense that this is\n> not the fault of dogmatic trust in -Wsign-compare; this is caused by\n> using size_t to count things).\n>\n> And the solution for this is *not* \"size_t\" -> \"ssize_t\", because\n> ssize_t is not \"store half the range of size_t with negative values\n> reserved for something else like errors\".  Its width can be much\n> narrower (this came up in a separate thread very recently [*]).\n> Instead we'd need something ugly like\n>\n> \tif (k != (size_t)-1 && bitmap_get(active_c, k))\n>\n> A quick band-aid patch to make it compile is attached at the end,\n> but it does not try to address the root causes, which are abuse of\n> size_t as count_t and religious use of \"-Wsign-compare\" [*].\n>\n>\n> [Reference]\n>\n> * https://lore.kernel.org/git/9eafee4d-ea94-4382-ada0-58000d229d2e@gmail.com/\n> * https://staticthinking.wordpress.com/2023/07/25/wsign-compare-is-garbage/\n\nYeah, this is a true positive. I was curious if GitHub's version of the\ncode also returned \"-1\" from a function whose return type is unsigned,\nand in fact our version of this function (called diff2idx()) returns an\n'int'.\n\nPractically speaking that's probably OK, since we are unlikely to have\nso many active paths anyway (or if we did, we'd likely have other\nproblems to deal with ;-)), but it is gross nonetheless.\n\nI wonder if we should inline all of this into its own function and not\nexpose the bitmap index for a given path at all? Perhaps something like\nthe following (on top of Junio's other suggestions to get this compiling\nunder DEVELOPER=1):\n\n--- 8< ---\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex e9050485a9..ce3ae4fb3d 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -226,13 +226,16 @@ static void last_modified_diff(struct diff_queue_struct *q,\n \t}\n }\n\n-static size_t path_idx(struct last_modified *lm, char *path)\n+static void last_modified_mark_non_treesame(struct last_modified *lm,\n+\t\t\t\t\t    struct bitmap *active_c,\n+\t\t\t\t\t    char *path)\n {\n \tstruct last_modified_entry *ent;\n \tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n \t\t\t\t\t  struct last_modified_entry, hashent);\n\n-\treturn ent ? ent->diff_idx : -1;\n+\tif (ent && bitmap_get(active_c, ent->diff_idx))\n+\t\tbitmap_set(lm->scratch, ent->diff_idx);\n }\n\n static void pass_to_parent(struct last_modified *lm,\n@@ -303,9 +306,7 @@ static void process_parent(struct last_modified *lm,\n \t */\n \tfor (i = 0; i < diff_queued_diff.nr; i++) {\n \t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n-\t\tsize_t k = path_idx(lm, fp->two->path);\n-\t\tif (0 <= k && bitmap_get(active_c, k))\n-\t\t\tbitmap_set(lm->scratch, k);\n+\t\tlast_modified_mark_non_treesame(lm, active_c, fp->two->path);\n \t}\n \tfor (i = 0; i < lm->all_paths_nr; i++) {\n \t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n--- >8 ---\n\nThanks,\nTaylor\n"},{"id":"529342","messageId":"aPglIBiTYpH4I3UN@nand.local","threadId":"64332","inReplyTo":"aPgkwnq87UeusC6v@nand.local","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-22T00:28:16Z","receivedAt":"2025-10-22T00:28:18Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Oct 21, 2025 at 08:26:42PM -0400, Taylor Blau wrote:\n> -static size_t path_idx(struct last_modified *lm, char *path)\n> +static void last_modified_mark_non_treesame(struct last_modified *lm,\n> +\t\t\t\t\t    struct bitmap *active_c,\n> +\t\t\t\t\t    char *path)\n\nErr... this should be const, but otherwise I stand by what I wrote ;-).\n\nThanks,\nTaylor\n"},{"id":"529347","messageId":"xmqqecqv1trk.fsf@gitster.g","threadId":"64332","inReplyTo":"aPgkwnq87UeusC6v@nand.local","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-10-22T03:48:31Z","receivedAt":"2025-10-22T03:48:34Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> On Tue, Oct 21, 2025 at 10:52:11AM -0700, Junio C Hamano wrote:\n>> > +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n>> > +\t\tsize_t k = path_idx(lm, fp->two->path);\n>> > +\t\tif (0 <= k && bitmap_get(active_c, k))\n>> > +\t\t\tbitmap_set(lm->scratch, k);\n>> > +\t}\n>>\n>> Earlier path_idx() wanted to signal an error by returning negative,\n>> but the type is size_t that is unsigned so it cannot do so.  We\n>> instead get\n>>\n>>     builtin/last-modified.c:307:23: error: comparison of unsigned expression in '>= 0' is always true [-Werror=type-limits]\n>>       307 |                 if (0 <= k && bitmap_get(active_c, k))\n>>           |                       ^~\n>> ...\n> Yeah, this is a true positive. I was curious if GitHub's version of the\n> code also returned \"-1\" from a function whose return type is unsigned,\n> and in fact our version of this function (called diff2idx()) returns an\n> 'int'.\n\nYes, I think the tool is doing the right thing here, unlike \"hey you\nare comparing int with size_t\" we saw earlier, and is giving us a\nuseful diagnosis.\n\n> Practically speaking that's probably OK, since we are unlikely to have\n> so many active paths anyway (or if we did, we'd likely have other\n> problems to deal with ;-)), but it is gross nonetheless.\n\nThe case path_idx() returns -1 is an error case, not \"there are too\nmany paths we are following\" case.  I do not see what relevance the\nnumber of active paths has here.\n\n"},{"id":"529487","messageId":"20251023-b4-toon-last-modified-faster-v3-1-40a4ddbbadec@iotcl.com","threadId":"64332","inReplyTo":"20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com","subject":"[PATCH v3] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-23T07:50:14Z","receivedAt":"2025-10-23T07:50:53Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"The current implementation of git-last-modified(1) works by doing a\nrevision walk, and inspecting the diff at each level of that walk to\nannotate entries remaining in the hashmap of paths. In other words, if\nthe diff at some level touches a path which has not yet been associated\nwith a commit, then that commit becomes associated with the path.\n\nWhile a perfectly reasonable implementation, it can perform poorly in\neither one of two scenarios:\n\n  1. There are many entries of interest, in which case there is simply\n     a lot of work to do.\n\n  2. Or, there are (even a few) entries which have not been updated in a\n     long time, and so we must walk through a lot of history in order to\n     find a commit that touches that path.\n\nThis patch rewrites the last-modified implementation that addresses the\nsecond point. The idea behind the algorithm is to propagate a set of\n'active' paths (a path is 'active' if it does not yet belong to a\ncommit) up to parents and do a truncated revision walk.\n\nThe walk is truncated because it does not produce a revision for every\nchange in the original pathspec, but rather only for active paths.\n\nMore specifically, consider a priority queue of commits sorted by\ngeneration number. First, enqueue the set of boundary commits with all\npaths in the original spec marked as interesting.\n\nThen, while the queue is not empty, do the following:\n\n  1. Pop an element, say, 'c', off of the queue, making sure that 'c'\n     isn't reachable by anything in the '--not' set.\n\n  2. For each parent 'p' (with index 'parent_i') of 'c', do the\n     following:\n\n     a. Compute the diff between 'c' and 'p'.\n     b. Pass any active paths that are TREESAME from 'c' to 'p'.\n     c. If 'p' has any active paths, push it onto the queue.\n\n  3. Any path that remains active on 'c' is associated to that commit.\n\nThis ends up being equivalent to doing something like 'git log -1 --\n$path' for each path simultaneously. But, it allows us to go much faster\nthan the original implementation by limiting the number of diffs we\ncompute, since we can avoid parts of history that would have been\nconsidered by the revision walk in the original implementation, but are\nknown to be uninteresting to us because we have already marked all paths\nin that area to be inactive.\n\nTo avoid computing many first-parent diffs, add another trick on top of\nthis and check if all paths active in 'c' are DEFINITELY NOT in c's\nBloom filter. Since the commit-graph only stores first-parent diffs in\nthe Bloom filters, we can only apply this trick to first-parent diffs.\n\nComparing the performance of this new algorithm shows about a 2.5x\nimprovement on git.git:\n\n    Benchmark 1: master   no bloom\n      Time (mean ± σ):      2.868 s ±  0.023 s    [User: 2.811 s, System: 0.051 s]\n      Range (min … max):    2.847 s …  2.926 s    10 runs\n\n    Benchmark 2: master with bloom\n      Time (mean ± σ):     949.9 ms ±  15.2 ms    [User: 907.6 ms, System: 39.5 ms]\n      Range (min … max):   933.3 ms … 971.2 ms    10 runs\n\n    Benchmark 3: HEAD     no bloom\n      Time (mean ± σ):     782.0 ms ±   6.3 ms    [User: 740.7 ms, System: 39.2 ms]\n      Range (min … max):   776.4 ms … 798.2 ms    10 runs\n\n    Benchmark 4: HEAD   with bloom\n      Time (mean ± σ):     307.1 ms ±   1.7 ms    [User: 276.4 ms, System: 29.9 ms]\n      Range (min … max):   303.7 ms … 309.5 ms    10 runs\n\n    Summary\n      HEAD   with bloom ran\n        2.55 ± 0.02 times faster than HEAD     no bloom\n        3.09 ± 0.05 times faster than master with bloom\n        9.34 ± 0.09 times faster than master   no bloom\n\nIn short, the existing implementation is comparably fast *with* Bloom\nfilters as the new implementation is *without* Bloom filters. So, most\nrepositories should get a dramatic speed-up by just deploying this (even\nwithout computing Bloom filters), and all repositories should get faster\nstill when computing Bloom filters.\n\nWhen comparing a more extreme example of\n`git last-modified -- COPYING t`, the difference is even 5 times better:\n\n    Benchmark 1: master\n      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n      Range (min … max):    4.308 s …  4.509 s    10 runs\n\n    Benchmark 2: HEAD\n      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n      Range (min … max):   810.6 ms … 881.2 ms    10 runs\n\n    Summary\n      HEAD ran\n        5.29 ± 0.16 times faster than master\n\nAs an added benefit, results are more consistent now. For example\nimplementation in 'master' gives:\n\n    $ git log --max-count=1 --format=%H -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\n\n    $ git last-modified -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n\n    $ git last-modified | grep pkt-line.h\n    5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n\nWith the changes in this patch the results of git-last-modified(1)\nalways match those of `git log --max-count=1`.\n\nOne thing to note though, the results might be outputted in a different\norder than before. This is not considerd to be an issue because nowhere\nis documented the order is guaranteed.\n\nBased-on-patches-by: Derrick Stolee <stolee@gmail.com>\nBased-on-patches-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Toon Claes <toon@iotcl.com>\n---\nThe subcommand git-last-modified(1) was based on the patches shared by\nTaylor and the folks at GitHub[1]. That version used an alternative\nimplementation to make it \"go faster\". When I was working on upstreaming\nthose patches, I dropped the patches[2] for this implementation, because\nI didn't see significant improvements.\n\nThis series revives those changes. I did more thorough deep dive through\nthe code and the algorithm and got the code working a lot faster. The\nbenchmark results can be found in the commit message.\n\nSome changes compared to GitHub's version include:\n\n * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n   `struct commit_active_paths`.\n\n * Removed shortcut code that handled the case when commit and parent\n   are fully treesame, and instead always checked 'active_c' whether the\n   next parent is worth looking at.\n\n * Modified comments and commit message to make the algorithm more\n   clear (at least to me).\n\n * Mentioned the use of PARENT1 and PARENT2 in object.h.\n\n * Removed the use of any global variables.\n\n * Less conditions are checked in mark_path() because the hashmap of\n   'paths' is considered the single-source of truth.\n\n * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n   hashmap no more.\n\n[1]: https://lore.kernel.org/git/Z+XJ+1L3PnC9Dyba@nand.local/\n[2]: https://lore.kernel.org/git/20250630-toon-new-blame-tree-v3-0-3516025dc3bc@iotcl.com/\n---\nChanges in v3:\n- Make code cleanly compile with -Wsign-compare\n- Remove path_idx() and instead inline the code in the loop. This fixes\n  the sign comparison issue and the function was only used in one place\n  anyway.\n- Make all the memory leaks go away.\n- Small tweaks in naming and code comments.\n- Link to v2: https://lore.kernel.org/r/20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com\n\nChanges in v2:\n- Add benchmark results comparing repositories with and without Bloom\n  filters in commit message.\n- Add Stolee and Taylor in the commit message trailers.\n- Fix segfault by checking if 'oid' is set in mark_path().\n- Remove hashmap lookup in pass_to_parent().\n- Remove manually calling diff_free_filepair().\n- Rename commit slab bitmap to \"active_paths_bitmap\".\n- Link to v1: https://lore.kernel.org/r/20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com\n\nRange-diff against v2:\n\n1:  e131d0df85 ! 1:  8b1a5cc055 last-modified: implement faster algorithm\n    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus\n      }\n\n     +/*\n    -+ * Hold a bitmap for each commit we're working with. Each bit represents a path\n    -+ * in `lm->all_paths`. Active bit means the path still needs to be dealt with.\n    ++ * Hold a bitmap for each commit we're working with. In the bitmap, each bit\n    ++ * represents a path in `lm->all_paths`. An active bit indicates the path still\n    ++ * needs to be associated to a commit.\n     + */\n    -+define_commit_slab(commit_bitmaps, struct bitmap *);\n    ++define_commit_slab(active_paths_for_commit, struct bitmap *);\n     +\n      struct last_modified {\n      \tstruct hashmap paths;\n    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus\n     +\n     +\tconst char **all_paths;\n     +\tsize_t all_paths_nr;\n    -+\tstruct commit_bitmaps active_paths_bitmap;\n    ++\tstruct active_paths_for_commit active_paths;\n     +\n    -+\t/* 'scratch' bitmap to avoid allocating every proccess_parent() */\n    ++\t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n     +\tstruct bitmap *scratch;\n      };\n\n    -+static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)\n    ++static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n     +{\n    -+\tstruct bitmap **bitmap = commit_bitmaps_at(&lm->active_paths_bitmap, c);\n    ++\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n     +\tif (!*bitmap)\n    -+\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);\n    ++\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD + 1);\n     +\n     +\treturn *bitmap;\n     +}\n    ++\n    ++static void active_paths_free(struct last_modified *lm, struct commit *c)\n    ++{\n    ++\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n    ++\tif (*bitmap) {\n    ++\t\tbitmap_free(*bitmap);\n    ++\t\t*bitmap = NULL;\n    ++\t}\n    ++}\n     +\n      static void last_modified_release(struct last_modified *lm)\n      {\n    @@ builtin/last-modified.c: static void last_modified_diff(struct diff_queue_struct\n      }\n\n     -static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n    -+static size_t path_idx(struct last_modified *lm, char *path)\n    -+{\n    -+\tstruct last_modified_entry *ent;\n    -+\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n    -+\t\t\t\t\t  struct last_modified_entry, hashent);\n    -+\n    -+\treturn ent ? ent->diff_idx : -1;\n    -+}\n    -+\n    -+static void pass_to_parent(struct last_modified *lm,\n    -+\t\t\t   struct bitmap *c,\n    ++static void pass_to_parent(struct bitmap *c,\n     +\t\t\t   struct bitmap *p,\n     +\t\t\t   size_t pos)\n     +{\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\t   struct commit *c, struct bitmap *active_c,\n     +\t\t\t   struct commit *parent, int parent_i)\n     +{\n    -+\tsize_t i;\n     +\tstruct bitmap *active_p;\n     +\n     +\trepo_parse_commit(lm->rev.repo, parent);\n    -+\tactive_p = get_bitmap(lm, parent);\n    ++\tactive_p = active_paths_for(lm, parent);\n     +\n     +\t/*\n     +\t * The first time entering this function for this commit (i.e. first parent)\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n     +\t * Then, pass paths that *are* TREESAME and active to the parent.\n     +\t */\n    -+\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n    ++\tfor (int i = 0; i < diff_queued_diff.nr; i++) {\n     +\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n    -+\t\tsize_t k = path_idx(lm, fp->two->path);\n    -+\t\tif (0 <= k && bitmap_get(active_c, k))\n    -+\t\t\tbitmap_set(lm->scratch, k);\n    ++\t\tconst char *path = fp->two->path;\n    ++\t\tstruct last_modified_entry *ent =\n    ++\t\t\thashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n    ++\t\t\t\t\t\t    struct last_modified_entry, hashent);\n    ++\t\tif (ent) {\n    ++\t\t\tsize_t k = ent->diff_idx;\n    ++\t\t\tif (bitmap_get(active_c, k))\n    ++\t\t\t\tbitmap_set(lm->scratch, k);\n    ++\t\t}\n     +\t}\n    -+\tfor (i = 0; i < lm->all_paths_nr; i++) {\n    ++\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n     +\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n    -+\t\t\tpass_to_parent(lm, active_c, active_p, i);\n    ++\t\t\tpass_to_parent(active_c, active_p, i);\n     +\t}\n     +\n     +\t/*\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\tparent->object.flags |= PARENT1;\n     +\t\tprio_queue_put(queue, parent);\n     +\t}\n    ++\tif (!(parent->object.flags & PARENT1))\n    ++\t\tactive_paths_free(lm, parent);\n     +\n     +\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n     +\tdiff_queue_clear(&diff_queued_diff);\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     -\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n     +\tmax_count = lm->rev.max_count;\n     +\n    -+\tinit_commit_bitmaps(&lm->active_paths_bitmap);\n    ++\tinit_active_paths_for_commit(&lm->active_paths);\n     +\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n     +\n     +\t/*\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\tprio_queue_put(&queue, c);\n     +\t\t\tc->object.flags |= PARENT1;\n     +\n    -+\t\t\tactive = get_bitmap(lm, c);\n    ++\t\t\tactive = active_paths_for(lm, c);\n     +\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n     +\t\t\t\tbitmap_set(active, i);\n     +\t\t}\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\tint parent_i;\n     +\t\tstruct commit_list *p;\n     +\t\tstruct commit *c = prio_queue_get(&queue);\n    -+\t\tstruct bitmap *active_c = get_bitmap(lm, c);\n    ++\t\tstruct bitmap *active_c = active_paths_for(lm, c);\n     +\n     +\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n     +\t\t    (c->object.flags & PARENT2)) {\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n\n     -\t\tlog_tree_commit(&lm->rev, data.commit);\n     +cleanup:\n    -+\t\tbitmap_free(active_c);\n    ++\t\tactive_paths_free(lm, c);\n      \t}\n\n     +\tif (hashmap_get_size(&lm->paths))\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\n     +\tclear_prio_queue(&not_queue);\n     +\tclear_prio_queue(&queue);\n    -+\tclear_commit_bitmaps(&lm->active_paths_bitmap);\n    ++\tclear_active_paths_for_commit(&lm->active_paths);\n     +\tbitmap_free(lm->scratch);\n     +\n      \treturn 0;\n---\n builtin/last-modified.c  | 250 ++++++++++++++++++++++++++++++++++++++++++++---\n object.h                 |   1 +\n t/t8020-last-modified.sh |   2 +-\n 3 files changed, 237 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex ae8b36a2c3..c271d9585b 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -2,26 +2,32 @@\n #include \"bloom.h\"\n #include \"builtin.h\"\n #include \"commit-graph.h\"\n+#include \"commit-slab.h\"\n #include \"commit.h\"\n #include \"config.h\"\n-#include \"environment.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"environment.h\"\n+#include \"ewah/ewok.h\"\n #include \"hashmap.h\"\n #include \"hex.h\"\n-#include \"log-tree.h\"\n #include \"object-name.h\"\n #include \"object.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n \n+/* Remember to update object flag allocation in object.h */\n+#define PARENT1 (1u<<16) /* used instead of SEEN */\n+#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n+\n struct last_modified_entry {\n \tstruct hashmap_entry hashent;\n \tstruct object_id oid;\n \tstruct bloom_key key;\n+\tsize_t diff_idx;\n \tconst char path[FLEX_ARRAY];\n };\n \n@@ -37,13 +43,45 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n \treturn strcmp(ent1->path, path ? path : ent2->path);\n }\n \n+/*\n+ * Hold a bitmap for each commit we're working with. In the bitmap, each bit\n+ * represents a path in `lm->all_paths`. An active bit indicates the path still\n+ * needs to be associated to a commit.\n+ */\n+define_commit_slab(active_paths_for_commit, struct bitmap *);\n+\n struct last_modified {\n \tstruct hashmap paths;\n \tstruct rev_info rev;\n \tbool recursive;\n \tbool show_trees;\n+\n+\tconst char **all_paths;\n+\tsize_t all_paths_nr;\n+\tstruct active_paths_for_commit active_paths;\n+\n+\t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n+\tstruct bitmap *scratch;\n };\n \n+static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n+\tif (!*bitmap)\n+\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD + 1);\n+\n+\treturn *bitmap;\n+}\n+\n+static void active_paths_free(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n+\tif (*bitmap) {\n+\t\tbitmap_free(*bitmap);\n+\t\t*bitmap = NULL;\n+\t}\n+}\n+\n static void last_modified_release(struct last_modified *lm)\n {\n \tstruct hashmap_iter iter;\n@@ -54,6 +92,8 @@ static void last_modified_release(struct last_modified *lm)\n \n \thashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent);\n \trelease_revisions(&lm->rev);\n+\n+\tfree(lm->all_paths);\n }\n \n struct last_modified_callback_data {\n@@ -146,7 +186,7 @@ static void mark_path(const char *path, const struct object_id *oid,\n \t * Is it arriving at a version of interest, or is it from a side branch\n \t * which did not contribute to the final state?\n \t */\n-\tif (!oideq(oid, &ent->oid))\n+\tif (oid && !oideq(oid, &ent->oid))\n \t\treturn;\n \n \tlast_modified_emit(data->lm, path, data->commit);\n@@ -196,7 +236,17 @@ static void last_modified_diff(struct diff_queue_struct *q,\n \t}\n }\n \n-static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n+static void pass_to_parent(struct bitmap *c,\n+\t\t\t   struct bitmap *p,\n+\t\t\t   size_t pos)\n+{\n+\tbitmap_unset(c, pos);\n+\tbitmap_set(p, pos);\n+}\n+\n+static bool maybe_changed_path(struct last_modified *lm,\n+\t\t\t       struct commit *origin,\n+\t\t\t       struct bitmap *active)\n {\n \tstruct bloom_filter *filter;\n \tstruct last_modified_entry *ent;\n@@ -213,6 +263,9 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \t\treturn true;\n \n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tif (active && !bitmap_get(active, ent->diff_idx))\n+\t\t\tcontinue;\n+\n \t\tif (bloom_filter_contains(filter, &ent->key,\n \t\t\t\t\t  lm->rev.bloom_filter_settings))\n \t\t\treturn true;\n@@ -220,42 +273,202 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \treturn false;\n }\n \n+static void process_parent(struct last_modified *lm,\n+\t\t\t   struct prio_queue *queue,\n+\t\t\t   struct commit *c, struct bitmap *active_c,\n+\t\t\t   struct commit *parent, int parent_i)\n+{\n+\tstruct bitmap *active_p;\n+\n+\trepo_parse_commit(lm->rev.repo, parent);\n+\tactive_p = active_paths_for(lm, parent);\n+\n+\t/*\n+\t * The first time entering this function for this commit (i.e. first parent)\n+\t * see if Bloom filters will tell us it's worth to do the diff.\n+\t */\n+\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n+\t\tdiff_tree_oid(&parent->object.oid,\n+\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n+\t\tdiffcore_std(&lm->rev.diffopt);\n+\t}\n+\n+\t/*\n+\t * Test each path for TREESAME-ness against the parent. If a path is\n+\t * TREESAME, pass it on to this parent.\n+\t *\n+\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n+\t * Then, pass paths that *are* TREESAME and active to the parent.\n+\t */\n+\tfor (int i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n+\t\tconst char *path = fp->two->path;\n+\t\tstruct last_modified_entry *ent =\n+\t\t\thashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n+\t\t\t\t\t\t    struct last_modified_entry, hashent);\n+\t\tif (ent) {\n+\t\t\tsize_t k = ent->diff_idx;\n+\t\t\tif (bitmap_get(active_c, k))\n+\t\t\t\tbitmap_set(lm->scratch, k);\n+\t\t}\n+\t}\n+\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n+\t\t\tpass_to_parent(active_c, active_p, i);\n+\t}\n+\n+\t/*\n+\t * If parent has any active paths, put it on the queue (if not already).\n+\t */\n+\tif (!bitmap_is_empty(active_p) && !(parent->object.flags & PARENT1)) {\n+\t\tparent->object.flags |= PARENT1;\n+\t\tprio_queue_put(queue, parent);\n+\t}\n+\tif (!(parent->object.flags & PARENT1))\n+\t\tactive_paths_free(lm, parent);\n+\n+\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n+\tdiff_queue_clear(&diff_queued_diff);\n+}\n+\n static int last_modified_run(struct last_modified *lm)\n {\n+\tint max_count, queue_popped = 0;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit_list *list;\n \tstruct last_modified_callback_data data = { .lm = lm };\n \n \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n \tlm->rev.diffopt.format_callback = last_modified_diff;\n \tlm->rev.diffopt.format_callback_data = &data;\n+\tlm->rev.no_walk = 1;\n \n \tprepare_revision_walk(&lm->rev);\n \n-\twhile (hashmap_get_size(&lm->paths)) {\n-\t\tdata.commit = get_revision(&lm->rev);\n-\t\tif (!data.commit)\n-\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\tmax_count = lm->rev.max_count;\n+\n+\tinit_active_paths_for_commit(&lm->active_paths);\n+\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n+\n+\t/*\n+\t * lm->rev.commits holds the set of boundary commits for our walk.\n+\t *\n+\t * Loop through each such commit, and place it in the appropriate queue.\n+\t */\n+\tfor (list = lm->rev.commits; list; list = list->next) {\n+\t\tstruct commit *c = list->item;\n+\n+\t\tif (c->object.flags & BOTTOM) {\n+\t\t\tprio_queue_put(&not_queue, c);\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t} else if (!(c->object.flags & PARENT1)) {\n+\t\t\t/*\n+\t\t\t * If the commit is a starting point (and hasn't been\n+\t\t\t * seen yet), then initialize the set of interesting\n+\t\t\t * paths, too.\n+\t\t\t */\n+\t\t\tstruct bitmap *active;\n+\n+\t\t\tprio_queue_put(&queue, c);\n+\t\t\tc->object.flags |= PARENT1;\n+\n+\t\t\tactive = active_paths_for(lm, c);\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\t\t\tbitmap_set(active, i);\n+\t\t}\n+\t}\n \n-\t\tif (data.commit->object.flags & BOUNDARY) {\n+\twhile (queue.nr) {\n+\t\tint parent_i;\n+\t\tstruct commit_list *p;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tstruct bitmap *active_c = active_paths_for(lm, c);\n+\n+\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n+\t\t    (c->object.flags & PARENT2)) {\n+\t\t\t/*\n+\t\t\t * Either a boundary commit, or we have already seen too\n+\t\t\t * many others. Either way, stop here.\n+\t\t\t */\n+\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n+\t\t\tdata.commit = c;\n \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n-\t\t\t\t      &data.commit->object.oid, \"\",\n-\t\t\t\t      &lm->rev.diffopt);\n+\t\t\t\t      &c->object.oid,\n+\t\t\t\t      \"\", &lm->rev.diffopt);\n \t\t\tdiff_flush(&lm->rev.diffopt);\n+\t\t\tgoto cleanup;\n+\t\t}\n \n-\t\t\tbreak;\n+\t\t/*\n+\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n+\t\t * in the '--not' queue.\n+\t\t */\n+\t\trepo_parse_commit(lm->rev.repo, c);\n+\n+\t\twhile (not_queue.nr) {\n+\t\t\tstruct commit_list *np;\n+\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n+\n+\t\t\trepo_parse_commit(lm->rev.repo, n);\n+\n+\t\t\tfor (np = n->parents; np; np = np->next) {\n+\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n+\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n+\t\t\t\t\tnp->item->object.flags |= PARENT2;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n+\t\t\t\tbreak;\n \t\t}\n \n-\t\tif (!maybe_changed_path(lm, data.commit))\n-\t\t\tcontinue;\n+\t\t/*\n+\t\t * Look at each parent and pass on each path that's TREESAME\n+\t\t * with that parent. Stop early when no active paths remain.\n+\t\t */\n+\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n+\t\t\tprocess_parent(lm, &queue,\n+\t\t\t\t       c, active_c,\n+\t\t\t\t       p->item, parent_i);\n+\n+\t\t\tif (bitmap_is_empty(active_c))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/*\n+\t\t * Paths that remain active, or not TREESAME with any parent,\n+\t\t * were changed by 'c'.\n+\t\t */\n+\t\tif (!bitmap_is_empty(active_c))  {\n+\t\t\tdata.commit = c;\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\t\t\t\tif (bitmap_get(active_c, i))\n+\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n+\t\t\t}\n+\t\t}\n \n-\t\tlog_tree_commit(&lm->rev, data.commit);\n+cleanup:\n+\t\tactive_paths_free(lm, c);\n \t}\n \n+\tif (hashmap_get_size(&lm->paths))\n+\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\n+\tclear_prio_queue(&not_queue);\n+\tclear_prio_queue(&queue);\n+\tclear_active_paths_for_commit(&lm->active_paths);\n+\tbitmap_free(lm->scratch);\n+\n \treturn 0;\n }\n \n static int last_modified_init(struct last_modified *lm, struct repository *r,\n \t\t\t      const char *prefix, int argc, const char **argv)\n {\n+\tstruct hashmap_iter iter;\n+\tstruct last_modified_entry *ent;\n+\n \thashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);\n \n \trepo_init_revisions(r, &lm->rev, prefix);\n@@ -280,6 +493,13 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \tif (populate_paths_from_revs(lm) < 0)\n \t\treturn error(_(\"unable to setup last-modified\"));\n \n+\tlm->all_paths = xcalloc(hashmap_get_size(&lm->paths), sizeof(const char *));\n+\tlm->all_paths_nr = 0;\n+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tent->diff_idx = lm->all_paths_nr++;\n+\t\tlm->all_paths[ent->diff_idx] = ent->path;\n+\t}\n+\n \treturn 0;\n }\n \ndiff --git a/object.h b/object.h\nindex 8c3c1c46e1..fa504a09c0 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n  * http-push.c:                          11-----14\n  * commit-graph.c:                                15\n  * commit-reach.c:                                  16-----19\n+ * builtin/last-modified.c:                         1617\n  * sha1-name.c:                                              20\n  * list-objects-filter.c:                                      21\n  * bloom.c:                                                    2122\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 61f00bc15c..a4c1114ee2 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -57,9 +57,9 @@ test_expect_success 'last-modified recursive' '\n \n test_expect_success 'last-modified recursive with show-trees' '\n \tcheck_last_modified -r -t <<-\\EOF\n-\t3 a\n \t3 a/b\n \t3 a/b/file\n+\t3 a\n \t2 a/file\n \t1 file\n \tEOF\n\n---\nbase-commit: 133d151831d32bdcc02422599a3f26cef44f929b\nchange-id: 20251009-b4-toon-last-modified-faster-4c8956a95261\n\n"},{"id":"529488","messageId":"87347aqc65.fsf@iotcl.com","threadId":"64332","inReplyTo":"xmqqy0p4uoqc.fsf@gitster.g","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-23T08:01:38Z","receivedAt":"2025-10-23T08:02:04Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Toon Claes <toon@iotcl.com> writes:\n>\n>> +static size_t path_idx(struct last_modified *lm, char *path)\n>> +{\n>> +\tstruct last_modified_entry *ent;\n>> +\tent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n>> +\t\t\t\t\t  struct last_modified_entry, hashent);\n>> +\n>> +\treturn ent ? ent->diff_idx : -1;\n>> +}\n>\n> size_t is unsigned and cannot reutrn -1 sanely, unless the caller\n> knows that ((size_t)-1) signals an error.  The compiler warns, and\n> we compile with -Werror, so we end up getting\n>\n>     builtin/last-modified.c: In function 'path_idx':\n>     builtin/last-modified.c:235:38: error: operand of '?:' changes signedness from 'int' to 'size_t' {aka 'long unsigned int'} due to unsignedness of other operand [-Werror=sign-compare]\n>       235 |         return ent ? ent->diff_idx : -1;\n>           |                                      ^~\n\nWhoops, I didn't realize I wasn't compiling with the proper DEVELOPER\nsettings. I recently set up a new computer and didn't bring over all\nconfiguration correctly.\n\nI just sent out v3 and in that version I decided to solve this issue\ndifferently: inline the code from path_idx() in only place it was used.\n\n\n-- \nCheers,\nToon\n"},{"id":"529540","messageId":"aPrAyJYvWtlvmiEx@nand.local","threadId":"64332","inReplyTo":"87jz0tu3yh.fsf@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-23T23:56:56Z","receivedAt":"2025-10-23T23:56:58Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Fri, Oct 17, 2025 at 02:07:18PM +0200, Toon Claes wrote:\n> > Regardless of how you handle the above, I think that the commit slab\n> > name here is a little generic. I guess it's OK since this is only\n> > visible within this compilation unit, but perhaps something like\n> > \"active_paths_bitmap\" would be more descriptive.\n>\n> I struggled a lot naming this thing, so I'm open to suggestions.\n\nI think calling it \"active_paths_bitmap\" or similar conveys that this is\nsomehow specific to \"active paths\", and since the slab is static within\nthe last-modified builtin, I think that's fine. It's a little word-y, so\nif you have better ideas with fewer characters, I'm open to just about\nanything.\n\n> > Likewise, I wonder if we should have elemtype here be just 'struct\n> > bitmap'. Unfortunately I don't think the EWAH code has a function like:\n> >\n> >     void bitmap_init(struct bitmap *);\n> >\n> > and only has ones that allocate for us. So we may consider adding one,\n> > or creating a dummy bitmap and copying its contents, or otherwise.\n> >\n> >>  struct last_modified {\n> >>  \tstruct hashmap paths;\n> >>  \tstruct rev_info rev;\n> >>  \tbool recursive;\n> >>  \tbool show_trees;\n> >> +\n> >> +\tconst char **all_paths;\n> >> +\tsize_t all_paths_nr;\n> >\n> > I wonder if all_paths should be a strvec here? I think that this code\n> > was all written when the type was called argv_array (hilariously, that\n> > change took place towards the end of July, 2020, and the --go-faster\n> > code where this patch came from was written just a couple of weeks\n> > earlier.)\n>\n> Ahha, that might be a good idea. This might allow us to get rid of the\n> hashmap, which stops us from storing the paths twice. Not sure what the\n> impact on the performance would be, because the hashmap now is valuable\n> for path_idx() lookups.\n\nLooking at this a little further, I don't think I consider this worth\ndoing. Using a strvec here is awkward since last_modified_init() really\nwants to assign lm->all_paths based on each entry's diff_idx, which is\nnot what strvec.h is designed for.\n\nYou *could* use a string_list, and shove a pointer to the\nlast_modified_entry struct in the ->util field, but that is also\ninefficient since we remove paths from our hashmap as we mark them, and\nrepeating that in a string_list would be wasteful.\n\n> > In the GitHub version of this patch, we pass all active paths to the\n> > parent, assign the PARENT1 flag if it doesn't already have it, and put\n> > it in the queue as well.\n> >\n> > In your version, we'd skip past the next for-loop, and do the same\n> > pass-to-parent dance below, along with inserting the parent into the\n> > prio queue.\n>\n> This is the \"shortcut\" I'm mentioning in my cover letter. In my testing\n> it seemed it didn't provide any performance gains to keep it. I consider\n> less code better code, so I left it out.\n\nFair enough. I don't think that less code here results in a lack of\nclarity, so this seems alright to me. But in general I am not sure that\nI always agree that less code is better ;-).\n\n> > So I think that this is all functionally equivalent, but I had to work\n> > through a little bit of the details here, mostly since I haven't looked\n> > at or thought about this code in many years ;-).\n> >\n> >>  static int last_modified_run(struct last_modified *lm)\n> >>  {\n> >> +\tint max_count, queue_popped = 0;\n> >> +\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n> >> +\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n> >> +\tstruct commit_list *list;\n> >>  \tstruct last_modified_callback_data data = { .lm = lm };\n> >>\n> >>  \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n> >>  \tlm->rev.diffopt.format_callback = last_modified_diff;\n> >>  \tlm->rev.diffopt.format_callback_data = &data;\n> >> +\tlm->rev.no_walk = 1;\n> >\n> > This one is new relative to the original patch. Why set no_walk here?\n>\n> This comes from\n> https://github.com/ttaylorr/git/commit/e8ea49705873d28f64b815bd00d14bdf6d48ca4d\n>\n> Well, it basically squashes various commits together. There are various\n> commits doing different things here. I don't think it's valuable for\n> anyone to see the full history of the iterations at GitHub, that's why I\n> squashed it in.\n>\n> Would you consider it better to not set `no_walk`?\n\nHah, I forgot that we added this one later on. Adding it here in this\npatch makes sense to me.\n\nThanks,\nTaylor\n"},{"id":"529541","messageId":"aPrBYGa6HWUtTI4V@nand.local","threadId":"64332","inReplyTo":"87cy6gtym2.fsf@iotcl.com","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-23T23:59:28Z","receivedAt":"2025-10-23T23:59:30Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Oct 21, 2025 at 11:04:05AM +0200, Toon Claes wrote:\n> > Taylor Blau <me@ttaylorr.com> writes:\n>\n> >> Nice, I am glad to see that we are using a bitmap here rather than the\n> >> hacky 'char *' that we had originally written. I seem to remember that\n> >> there was a tiny slow-down when using bitmaps, but can't find the\n> >> discussion anymore. (It wasn't in the internal PR that I originally\n> >> opened, and I no longer can read messages that far back in history.)\n> >>\n> >> It might be worth benchmarking here to see if using a 'char *' is\n> >> faster. Of course, that's 8x worse in terms of memory usage, but not a\n> >> huge deal given both the magnitude and typical number of directory\n> >> elements (you'd need 1024^2 entries in a single tree to occupy even a\n> >> single MiB of heap).\n>\n> Using ewah bitmaps is slightly faster, although the difference is almost\n> neglible.\n>\n>     Benchmark 1: bitmap-ewah\n>       Time (mean ± σ):     793.1 ms ±   6.2 ms    [User: 755.1 ms, System: 35.2 ms]\n>       Range (min … max):   784.7 ms … 804.8 ms    10 runs\n>\n>     Benchmark 2: bitmap-chars\n>       Time (mean ± σ):     808.9 ms ±  11.2 ms    [User: 770.8 ms, System: 35.4 ms]\n>       Range (min … max):   800.2 ms … 830.5 ms    10 runs\n>\n>     Summary\n>       bitmap-ewah ran\n>         1.02 ± 0.02 times faster than bitmap-chars\n\nOK, makes sense, though just to clarify, \"bitmap-ewah\" is just a\nbog-standard \"struct bitmap\", right? That happens to come from the EWAH\nimplementation, but the bitmap itself is not being EWAH compressed,\nright?\n\n> And ewah bitmap being more memory efficient, it makes more sense to keep\n> using those.\n>\n> >> Likewise, I wonder if we should have elemtype here be just 'struct\n> >> bitmap'. Unfortunately I don't think the EWAH code has a function like:\n> >>\n> >>     void bitmap_init(struct bitmap *);\n> >>\n> >> and only has ones that allocate for us. So we may consider adding one,\n> >> or creating a dummy bitmap and copying its contents, or otherwise.\n>\n> I've done some testing, and to do so I've made bitmap_grow() public.\n>\n>     Benchmark 1: bitmap-as-pointers\n>       Time (mean ± σ):     783.7 ms ±   8.9 ms    [User: 744.1 ms, System: 37.5 ms]\n>       Range (min … max):   774.4 ms … 803.4 ms    10 runs\n>\n>     Benchmark 2: bitmap-as-values\n>       Time (mean ± σ):     856.7 ms ±  10.5 ms    [User: 816.0 ms, System: 38.1 ms]\n>       Range (min … max):   845.7 ms … 872.5 ms    10 runs\n>\n>     Summary\n>       bitmap-as-pointers ran\n>         1.09 ± 0.02 times faster than bitmap-as-values\n>\n> It seems using ewah bitmaps as pointers is faster than using bitmaps as\n> values. I must admit I'm surprised as well, but in case you want to\n> double check, here's the patch:\n\nI think this makes sense; the pointers are half as wide as a struct\nbitmap. Even though we're going through another layer of indirection, I\nthink that the smaller slab footprint results in better cache locality,\nand ultimately faster code. Thanks for testing it out.\n\nThanks,\nTaylor\n"},{"id":"529542","messageId":"aPrByfpOkQ7biyEI@nand.local","threadId":"64332","inReplyTo":"xmqqecqv1trk.fsf@gitster.g","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-24T00:01:13Z","receivedAt":"2025-10-24T00:01:16Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Tue, Oct 21, 2025 at 08:48:31PM -0700, Junio C Hamano wrote:\n> > Practically speaking that's probably OK, since we are unlikely to have\n> > so many active paths anyway (or if we did, we'd likely have other\n> > problems to deal with ;-)), but it is gross nonetheless.\n>\n> The case path_idx() returns -1 is an error case, not \"there are too\n> many paths we are following\" case.  I do not see what relevance the\n> number of active paths has here.\n\nI just meant that we are unlikely to ever have so many active paths at\nonce that (size_t)-1 would actually have a valid entry, or IOW that\nactive_paths_nr is smaller than 2^32-1.\n\nThanks,\nTaylor\n"},{"id":"529543","messageId":"aPrCaSOA/dclWye5@nand.local","threadId":"64332","inReplyTo":"20251023-b4-toon-last-modified-faster-v3-1-40a4ddbbadec@iotcl.com","subject":"Re: [PATCH v3] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-24T00:03:53Z","receivedAt":"2025-10-24T00:03:56Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 23, 2025 at 09:50:14AM +0200, Toon Claes wrote:\n> ---\n>  builtin/last-modified.c  | 250 ++++++++++++++++++++++++++++++++++++++++++++---\n>  object.h                 |   1 +\n>  t/t8020-last-modified.sh |   2 +-\n>  3 files changed, 237 insertions(+), 16 deletions(-)\n\nThis version looks good to me, thanks for porting it forward and\ncleaning it up, so it has my\n\n    Acked-by: Taylor Blau <me@ttaylorr.com>\n\nAs an aside, do you plan on upstreaming the blame-tree cache, (which I\nimagine would get renamed to last-modified cache)? Just curious.\n\nThanks,\nTaylor\n"},{"id":"529544","messageId":"xmqqtszpqgmy.fsf@gitster.g","threadId":"64332","inReplyTo":"aPrByfpOkQ7biyEI@nand.local","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-10-24T00:37:25Z","receivedAt":"2025-10-24T00:37:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> On Tue, Oct 21, 2025 at 08:48:31PM -0700, Junio C Hamano wrote:\n>> > Practically speaking that's probably OK, since we are unlikely to have\n>> > so many active paths anyway (or if we did, we'd likely have other\n>> > problems to deal with ;-)), but it is gross nonetheless.\n>>\n>> The case path_idx() returns -1 is an error case, not \"there are too\n>> many paths we are following\" case.  I do not see what relevance the\n>> number of active paths has here.\n>\n> I just meant that we are unlikely to ever have so many active paths at\n> once that (size_t)-1 would actually have a valid entry, or IOW that\n> active_paths_nr is smaller than 2^32-1.\n\nSo?  If path_idx() needed to signal an error, it will return (size_t)-1,\nbut as the compiler correctly caught, the code as written, i.e.\n\n\tk = path_idx(...);\n\tif (0 <= k) {\n\t\t/* did not error so we can safely use k */\n\t\t...\n\t}\n \nis outright buggy. I do not see why it is \"practically speaking\nthat's probably OK\".  It certainly does not matter if the number we\nwill receive in 'k' in the success case is expected to be\nsmall---the problem is only for an error case.\n\n"},{"id":"529689","messageId":"87sef4q11l.fsf@iotcl.com","threadId":"64332","inReplyTo":"aPrCaSOA/dclWye5@nand.local","subject":"Re: [PATCH v3] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-27T07:03:18Z","receivedAt":"2025-10-27T07:03:34Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> This version looks good to me, thanks for porting it forward and\n> cleaning it up, so it has my\n>\n>     Acked-by: Taylor Blau <me@ttaylorr.com>\n\nThanks for confirming!\n\n> As an aside, do you plan on upstreaming the blame-tree cache, (which I\n> imagine would get renamed to last-modified cache)? Just curious.\n\nCurrently that's not planned.\n\n-- \nCheers,\nToon\n"},{"id":"529736","messageId":"87ms5cpcpu.fsf@iotcl.com","threadId":"64332","inReplyTo":"aPrAyJYvWtlvmiEx@nand.local","subject":"Re: [PATCH] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-27T15:48:45Z","receivedAt":"2025-10-27T15:49:00Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n>> Ahha, that might be a good idea. This might allow us to get rid of the\n>> hashmap, which stops us from storing the paths twice. Not sure what the\n>> impact on the performance would be, because the hashmap now is valuable\n>> for path_idx() lookups.\n>\n> Looking at this a little further, I don't think I consider this worth\n> doing. Using a strvec here is awkward since last_modified_init() really\n> wants to assign lm->all_paths based on each entry's diff_idx, which is\n> not what strvec.h is designed for.\n\nYeah, I decided to leave it as is for now.\n\n> You *could* use a string_list, and shove a pointer to the\n> last_modified_entry struct in the ->util field, but that is also\n> inefficient since we remove paths from our hashmap as we mark them, and\n> repeating that in a string_list would be wasteful.\n\nThere was another idea I had. Instead of giving each commit a bitmap,\ngive each commit a hashmap, and pass the hashmap entries across commits.\nThis allows us to store paths only in once place and removes the need to\nallocate a fixed array `all_paths` again.\n\nBut in my measurements, this was about 30% slower than the solution I've\nsubmitted in v3. And it also complicates the memory management. So I've\nabandonned this idea.\n\n-- \nCheers,\nToon\n"},{"id":"529750","messageId":"aP/Gdl0kGJWklZdO@nand.local","threadId":"64332","inReplyTo":"xmqqtszpqgmy.fsf@gitster.g","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Taylor Blau","fromEmail":"me@ttaylorr.com","sentAt":"2025-10-27T19:22:30Z","receivedAt":"2025-10-27T19:22:37Z","isPatch":true,"sender":{"key":"me@ttaylorr.com","avatar":"https://avatars.githubusercontent.com/u/301000140?v=4"},"body":"On Thu, Oct 23, 2025 at 05:37:25PM -0700, Junio C Hamano wrote:\n> Taylor Blau <me@ttaylorr.com> writes:\n>\n> > On Tue, Oct 21, 2025 at 08:48:31PM -0700, Junio C Hamano wrote:\n> >> > Practically speaking that's probably OK, since we are unlikely to have\n> >> > so many active paths anyway (or if we did, we'd likely have other\n> >> > problems to deal with ;-)), but it is gross nonetheless.\n> >>\n> >> The case path_idx() returns -1 is an error case, not \"there are too\n> >> many paths we are following\" case.  I do not see what relevance the\n> >> number of active paths has here.\n> >\n> > I just meant that we are unlikely to ever have so many active paths at\n> > once that (size_t)-1 would actually have a valid entry, or IOW that\n> > active_paths_nr is smaller than 2^32-1.\n>\n> So?  If path_idx() needed to signal an error, it will return (size_t)-1,\n> but as the compiler correctly caught, the code as written, i.e.\n>\n> \tk = path_idx(...);\n> \tif (0 <= k) {\n> \t\t/* did not error so we can safely use k */\n> \t\t...\n> \t}\n>\n> is outright buggy. I do not see why it is \"practically speaking\n> that's probably OK\".  It certainly does not matter if the number we\n> will receive in 'k' in the success case is expected to be\n> small---the problem is only for an error case.\n\nI am not saying that we should continue to write \"if (0 <= k)\", since we\nwill clearly never take the else branch. I am trying to say that\npath_idx() *could* return (size_t)-1, and callers would be able to write\n\"if (k == (size_t)-1)\" to check for that error condition.\n\nMy observation was that there are unlikely to be so many active paths at\nany one time such that we'd ever want to return (size_t)-1 as a valid\nindex, and could always use it as an error sentinel.\n\nThanks,\nTaylor\n"},{"id":"529861","messageId":"87ldktrhe1.fsf@iotcl.com","threadId":"64332","inReplyTo":"aP/Gdl0kGJWklZdO@nand.local","subject":"Re: [PATCH v2] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-10-29T13:01:42Z","receivedAt":"2025-10-29T13:02:10Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Taylor Blau <me@ttaylorr.com> writes:\n\n> I am not saying that we should continue to write \"if (0 <= k)\", since we\n> will clearly never take the else branch. I am trying to say that\n> path_idx() *could* return (size_t)-1, and callers would be able to write\n> \"if (k == (size_t)-1)\" to check for that error condition.\n>\n> My observation was that there are unlikely to be so many active paths at\n> any one time such that we'd ever want to return (size_t)-1 as a valid\n> index, and could always use it as an error sentinel.\n\nYes, I agree. If the list grows to (size_t)-1 entries, I think we also\nrun into other issues.\n\nAnyhow, in the v3 I've submitted, I resolved it differently so no\nawkward type cast is needed.\n\n-- \nCheers,\nToon\n"},{"id":"530127","messageId":"20251103154726.26592-1-toon@iotcl.com","threadId":"64332","inReplyTo":"20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com","subject":"[PATCH v4] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-11-03T15:47:26Z","receivedAt":"2025-11-03T15:48:14Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"The current implementation of git-last-modified(1) works by doing a\nrevision walk, and inspecting the diff at each level of that walk to\nannotate entries remaining in the hashmap of paths. In other words, if\nthe diff at some level touches a path which has not yet been associated\nwith a commit, then that commit becomes associated with the path.\n\nWhile a perfectly reasonable implementation, it can perform poorly in\neither one of two scenarios:\n\n  1. There are many entries of interest, in which case there is simply\n     a lot of work to do.\n\n  2. Or, there are (even a few) entries which have not been updated in a\n     long time, and so we must walk through a lot of history in order to\n     find a commit that touches that path.\n\nThis patch rewrites the last-modified implementation that addresses the\nsecond point. The idea behind the algorithm is to propagate a set of\n'active' paths (a path is 'active' if it does not yet belong to a\ncommit) up to parents and do a truncated revision walk.\n\nThe walk is truncated because it does not produce a revision for every\nchange in the original pathspec, but rather only for active paths.\n\nMore specifically, consider a priority queue of commits sorted by\ngeneration number. First, enqueue the set of boundary commits with all\npaths in the original spec marked as interesting.\n\nThen, while the queue is not empty, do the following:\n\n  1. Pop an element, say, 'c', off of the queue, making sure that 'c'\n     isn't reachable by anything in the '--not' set.\n\n  2. For each parent 'p' (with index 'parent_i') of 'c', do the\n     following:\n\n     a. Compute the diff between 'c' and 'p'.\n     b. Pass any active paths that are TREESAME from 'c' to 'p'.\n     c. If 'p' has any active paths, push it onto the queue.\n\n  3. Any path that remains active on 'c' is associated to that commit.\n\nThis ends up being equivalent to doing something like 'git log -1 --\n$path' for each path simultaneously. But, it allows us to go much faster\nthan the original implementation by limiting the number of diffs we\ncompute, since we can avoid parts of history that would have been\nconsidered by the revision walk in the original implementation, but are\nknown to be uninteresting to us because we have already marked all paths\nin that area to be inactive.\n\nTo avoid computing many first-parent diffs, add another trick on top of\nthis and check if all paths active in 'c' are DEFINITELY NOT in c's\nBloom filter. Since the commit-graph only stores first-parent diffs in\nthe Bloom filters, we can only apply this trick to first-parent diffs.\n\nComparing the performance of this new algorithm shows about a 2.5x\nimprovement on git.git:\n\n    Benchmark 1: master   no bloom\n      Time (mean ± σ):      2.868 s ±  0.023 s    [User: 2.811 s, System: 0.051 s]\n      Range (min … max):    2.847 s …  2.926 s    10 runs\n\n    Benchmark 2: master with bloom\n      Time (mean ± σ):     949.9 ms ±  15.2 ms    [User: 907.6 ms, System: 39.5 ms]\n      Range (min … max):   933.3 ms … 971.2 ms    10 runs\n\n    Benchmark 3: HEAD     no bloom\n      Time (mean ± σ):     782.0 ms ±   6.3 ms    [User: 740.7 ms, System: 39.2 ms]\n      Range (min … max):   776.4 ms … 798.2 ms    10 runs\n\n    Benchmark 4: HEAD   with bloom\n      Time (mean ± σ):     307.1 ms ±   1.7 ms    [User: 276.4 ms, System: 29.9 ms]\n      Range (min … max):   303.7 ms … 309.5 ms    10 runs\n\n    Summary\n      HEAD   with bloom ran\n        2.55 ± 0.02 times faster than HEAD     no bloom\n        3.09 ± 0.05 times faster than master with bloom\n        9.34 ± 0.09 times faster than master   no bloom\n\nIn short, the existing implementation is comparably fast *with* Bloom\nfilters as the new implementation is *without* Bloom filters. So, most\nrepositories should get a dramatic speed-up by just deploying this (even\nwithout computing Bloom filters), and all repositories should get faster\nstill when computing Bloom filters.\n\nWhen comparing a more extreme example of\n`git last-modified -- COPYING t`, the difference is even 5 times better:\n\n    Benchmark 1: master\n      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]\n      Range (min … max):    4.308 s …  4.509 s    10 runs\n\n    Benchmark 2: HEAD\n      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]\n      Range (min … max):   810.6 ms … 881.2 ms    10 runs\n\n    Summary\n      HEAD ran\n        5.29 ± 0.16 times faster than master\n\nAs an added benefit, results are more consistent now. For example\nimplementation in 'master' gives:\n\n    $ git log --max-count=1 --format=%H -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\n\n    $ git last-modified -- pkt-line.h\n    15df15fe07ef66b51302bb77e393f3c5502629de\tpkt-line.h\n\n    $ git last-modified | grep pkt-line.h\n    5b49c1af03e600c286f63d9d9c9fb01403230b9f\tpkt-line.h\n\nWith the changes in this patch the results of git-last-modified(1)\nalways match those of `git log --max-count=1`.\n\nOne thing to note though, the results might be outputted in a different\norder than before. This is not considerd to be an issue because nowhere\nis documented the order is guaranteed.\n\nBased-on-patches-by: Derrick Stolee <stolee@gmail.com>\nBased-on-patches-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Taylor Blau <me@ttaylorr.com>\nSigned-off-by: Toon Claes <toon@iotcl.com>\n\n---\nThe subcommand git-last-modified(1) was based on the patches shared by\nTaylor and the folks at GitHub[1]. That version used an alternative\nimplementation to make it \"go faster\". When I was working on upstreaming\nthose patches, I dropped the patches[2] for this implementation, because\nI didn't see significant improvements.\n\nThis series revives those changes. I did more thorough deep dive through\nthe code and the algorithm and got the code working a lot faster. The\nbenchmark results can be found in the commit message.\n\nSome changes compared to GitHub's version include:\n\n * Use of `struct bitmap` from \"ewah/ewok.h\", instead of self-defined\n   `struct commit_active_paths`.\n\n * Removed shortcut code that handled the case when commit and parent\n   are fully treesame, and instead always checked 'active_c' whether the\n   next parent is worth looking at.\n\n * Modified comments and commit message to make the algorithm more\n   clear (at least to me).\n\n * Mentioned the use of PARENT1 and PARENT2 in object.h.\n\n * Removed the use of any global variables.\n\n * Less conditions are checked in mark_path() because the hashmap of\n   'paths' is considered the single-source of truth.\n\n * pass_to_parent() doesn't pass on when the path isn't in the 'paths'\n   hashmap no more.\n\n[1]: https://lore.kernel.org/git/Z+XJ+1L3PnC9Dyba@nand.local/\n[2]: https://lore.kernel.org/git/20250630-toon-new-blame-tree-v3-0-3516025dc3bc@iotcl.com/\n---\nChanges in v4:\n- Use CALLOC_ARRAY() instead of xcalloc() as identified by Junio using\n  'make coccicheck'.\n- Small formatting changes.\n- Link to v3: https://lore.kernel.org/all/20251023-b4-toon-last-modified-faster-v3-1-40a4ddbbadec@iotcl.com\n\nChanges in v3:\n- Make code cleanly compile with -Wsign-compare\n- Remove path_idx() and instead inline the code in the loop. This fixes\n  the sign comparison issue and the function was only used in one place\n  anyway.\n- Make all the memory leaks go away.\n- Small tweaks in naming and code comments.\n- Link to v2: https://lore.kernel.org/r/20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com\n\nChanges in v2:\n- Add benchmark results comparing repositories with and without Bloom\n  filters in commit message.\n- Add Stolee and Taylor in the commit message trailers.\n- Fix segfault by checking if 'oid' is set in mark_path().\n- Remove hashmap lookup in pass_to_parent().\n- Remove manually calling diff_free_filepair().\n- Rename commit slab bitmap to \"active_paths_bitmap\".\n- Link to v1: https://lore.kernel.org/r/20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com\n\nRange-diff against v3:\n\n1:  2d86f0406a ! 1:  9991283ec2 last-modified: implement faster algorithm\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\t\tbitmap_set(lm->scratch, k);\n     +\t\t}\n     +\t}\n    -+\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n    ++\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n     +\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n     +\t\t\tpass_to_parent(active_c, active_p, i);\n    -+\t}\n     +\n     +\t/*\n     +\t * If parent has any active paths, put it on the queue (if not already).\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\t * paths, too.\n     +\t\t\t */\n     +\t\t\tstruct bitmap *active;\n    -+\n    +\n    +-\t\tif (data.commit->object.flags & BOUNDARY) {\n     +\t\t\tprio_queue_put(&queue, c);\n     +\t\t\tc->object.flags |= PARENT1;\n     +\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t\t\tbitmap_set(active, i);\n     +\t\t}\n     +\t}\n    -\n    --\t\tif (data.commit->object.flags & BOUNDARY) {\n    ++\n     +\twhile (queue.nr) {\n     +\t\tint parent_i;\n     +\t\tstruct commit_list *p;\n    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm\n     +\t\t * Paths that remain active, or not TREESAME with any parent,\n     +\t\t * were changed by 'c'.\n     +\t\t */\n    -+\t\tif (!bitmap_is_empty(active_c))  {\n    ++\t\tif (!bitmap_is_empty(active_c)) {\n     +\t\t\tdata.commit = c;\n    -+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n    ++\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n     +\t\t\t\tif (bitmap_get(active_c, i))\n     +\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n    -+\t\t\t}\n     +\t\t}\n\n     -\t\tlog_tree_commit(&lm->rev, data.commit);\n    @@ builtin/last-modified.c: static int last_modified_init(struct last_modified *lm,\n      \tif (populate_paths_from_revs(lm) < 0)\n      \t\treturn error(_(\"unable to setup last-modified\"));\n\n    -+\tlm->all_paths = xcalloc(hashmap_get_size(&lm->paths), sizeof(const char *));\n    ++\tCALLOC_ARRAY(lm->all_paths, hashmap_get_size(&lm->paths));\n     +\tlm->all_paths_nr = 0;\n     +\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n     +\t\tent->diff_idx = lm->all_paths_nr++;\n\n---\n builtin/last-modified.c  | 248 ++++++++++++++++++++++++++++++++++++---\n object.h                 |   1 +\n t/t8020-last-modified.sh |   2 +-\n 3 files changed, 235 insertions(+), 16 deletions(-)\n\ndiff --git a/builtin/last-modified.c b/builtin/last-modified.c\nindex ae8b36a2c3..3028abd25e 100644\n--- a/builtin/last-modified.c\n+++ b/builtin/last-modified.c\n@@ -2,26 +2,32 @@\n #include \"bloom.h\"\n #include \"builtin.h\"\n #include \"commit-graph.h\"\n+#include \"commit-slab.h\"\n #include \"commit.h\"\n #include \"config.h\"\n-#include \"environment.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n #include \"environment.h\"\n+#include \"ewah/ewok.h\"\n #include \"hashmap.h\"\n #include \"hex.h\"\n-#include \"log-tree.h\"\n #include \"object-name.h\"\n #include \"object.h\"\n #include \"parse-options.h\"\n+#include \"prio-queue.h\"\n #include \"quote.h\"\n #include \"repository.h\"\n #include \"revision.h\"\n\n+/* Remember to update object flag allocation in object.h */\n+#define PARENT1 (1u<<16) /* used instead of SEEN */\n+#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */\n+\n struct last_modified_entry {\n \tstruct hashmap_entry hashent;\n \tstruct object_id oid;\n \tstruct bloom_key key;\n+\tsize_t diff_idx;\n \tconst char path[FLEX_ARRAY];\n };\n\n@@ -37,13 +43,45 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,\n \treturn strcmp(ent1->path, path ? path : ent2->path);\n }\n\n+/*\n+ * Hold a bitmap for each commit we're working with. In the bitmap, each bit\n+ * represents a path in `lm->all_paths`. An active bit indicates the path still\n+ * needs to be associated to a commit.\n+ */\n+define_commit_slab(active_paths_for_commit, struct bitmap *);\n+\n struct last_modified {\n \tstruct hashmap paths;\n \tstruct rev_info rev;\n \tbool recursive;\n \tbool show_trees;\n+\n+\tconst char **all_paths;\n+\tsize_t all_paths_nr;\n+\tstruct active_paths_for_commit active_paths;\n+\n+\t/* 'scratch' to avoid allocating a bitmap every process_parent() */\n+\tstruct bitmap *scratch;\n };\n\n+static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n+\tif (!*bitmap)\n+\t\t*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD + 1);\n+\n+\treturn *bitmap;\n+}\n+\n+static void active_paths_free(struct last_modified *lm, struct commit *c)\n+{\n+\tstruct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);\n+\tif (*bitmap) {\n+\t\tbitmap_free(*bitmap);\n+\t\t*bitmap = NULL;\n+\t}\n+}\n+\n static void last_modified_release(struct last_modified *lm)\n {\n \tstruct hashmap_iter iter;\n@@ -54,6 +92,8 @@ static void last_modified_release(struct last_modified *lm)\n\n \thashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent);\n \trelease_revisions(&lm->rev);\n+\n+\tfree(lm->all_paths);\n }\n\n struct last_modified_callback_data {\n@@ -146,7 +186,7 @@ static void mark_path(const char *path, const struct object_id *oid,\n \t * Is it arriving at a version of interest, or is it from a side branch\n \t * which did not contribute to the final state?\n \t */\n-\tif (!oideq(oid, &ent->oid))\n+\tif (oid && !oideq(oid, &ent->oid))\n \t\treturn;\n\n \tlast_modified_emit(data->lm, path, data->commit);\n@@ -196,7 +236,17 @@ static void last_modified_diff(struct diff_queue_struct *q,\n \t}\n }\n\n-static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n+static void pass_to_parent(struct bitmap *c,\n+\t\t\t   struct bitmap *p,\n+\t\t\t   size_t pos)\n+{\n+\tbitmap_unset(c, pos);\n+\tbitmap_set(p, pos);\n+}\n+\n+static bool maybe_changed_path(struct last_modified *lm,\n+\t\t\t       struct commit *origin,\n+\t\t\t       struct bitmap *active)\n {\n \tstruct bloom_filter *filter;\n \tstruct last_modified_entry *ent;\n@@ -213,6 +263,9 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \t\treturn true;\n\n \thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tif (active && !bitmap_get(active, ent->diff_idx))\n+\t\t\tcontinue;\n+\n \t\tif (bloom_filter_contains(filter, &ent->key,\n \t\t\t\t\t  lm->rev.bloom_filter_settings))\n \t\t\treturn true;\n@@ -220,42 +273,200 @@ static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)\n \treturn false;\n }\n\n+static void process_parent(struct last_modified *lm,\n+\t\t\t   struct prio_queue *queue,\n+\t\t\t   struct commit *c, struct bitmap *active_c,\n+\t\t\t   struct commit *parent, int parent_i)\n+{\n+\tstruct bitmap *active_p;\n+\n+\trepo_parse_commit(lm->rev.repo, parent);\n+\tactive_p = active_paths_for(lm, parent);\n+\n+\t/*\n+\t * The first time entering this function for this commit (i.e. first parent)\n+\t * see if Bloom filters will tell us it's worth to do the diff.\n+\t */\n+\tif (parent_i || maybe_changed_path(lm, c, active_c)) {\n+\t\tdiff_tree_oid(&parent->object.oid,\n+\t\t\t      &c->object.oid, \"\", &lm->rev.diffopt);\n+\t\tdiffcore_std(&lm->rev.diffopt);\n+\t}\n+\n+\t/*\n+\t * Test each path for TREESAME-ness against the parent. If a path is\n+\t * TREESAME, pass it on to this parent.\n+\t *\n+\t * First, collect all paths that are *not* TREESAME in 'scratch'.\n+\t * Then, pass paths that *are* TREESAME and active to the parent.\n+\t */\n+\tfor (int i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *fp = diff_queued_diff.queue[i];\n+\t\tconst char *path = fp->two->path;\n+\t\tstruct last_modified_entry *ent =\n+\t\t\thashmap_get_entry_from_hash(&lm->paths, strhash(path), path,\n+\t\t\t\t\t\t    struct last_modified_entry, hashent);\n+\t\tif (ent) {\n+\t\t\tsize_t k = ent->diff_idx;\n+\t\t\tif (bitmap_get(active_c, k))\n+\t\t\t\tbitmap_set(lm->scratch, k);\n+\t\t}\n+\t}\n+\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n+\t\t\tpass_to_parent(active_c, active_p, i);\n+\n+\t/*\n+\t * If parent has any active paths, put it on the queue (if not already).\n+\t */\n+\tif (!bitmap_is_empty(active_p) && !(parent->object.flags & PARENT1)) {\n+\t\tparent->object.flags |= PARENT1;\n+\t\tprio_queue_put(queue, parent);\n+\t}\n+\tif (!(parent->object.flags & PARENT1))\n+\t\tactive_paths_free(lm, parent);\n+\n+\tmemset(lm->scratch->words, 0x0, lm->scratch->word_alloc);\n+\tdiff_queue_clear(&diff_queued_diff);\n+}\n+\n static int last_modified_run(struct last_modified *lm)\n {\n+\tint max_count, queue_popped = 0;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };\n+\tstruct commit_list *list;\n \tstruct last_modified_callback_data data = { .lm = lm };\n\n \tlm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;\n \tlm->rev.diffopt.format_callback = last_modified_diff;\n \tlm->rev.diffopt.format_callback_data = &data;\n+\tlm->rev.no_walk = 1;\n\n \tprepare_revision_walk(&lm->rev);\n\n-\twhile (hashmap_get_size(&lm->paths)) {\n-\t\tdata.commit = get_revision(&lm->rev);\n-\t\tif (!data.commit)\n-\t\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\tmax_count = lm->rev.max_count;\n+\n+\tinit_active_paths_for_commit(&lm->active_paths);\n+\tlm->scratch = bitmap_word_alloc(lm->all_paths_nr);\n+\n+\t/*\n+\t * lm->rev.commits holds the set of boundary commits for our walk.\n+\t *\n+\t * Loop through each such commit, and place it in the appropriate queue.\n+\t */\n+\tfor (list = lm->rev.commits; list; list = list->next) {\n+\t\tstruct commit *c = list->item;\n+\n+\t\tif (c->object.flags & BOTTOM) {\n+\t\t\tprio_queue_put(&not_queue, c);\n+\t\t\tc->object.flags |= PARENT2;\n+\t\t} else if (!(c->object.flags & PARENT1)) {\n+\t\t\t/*\n+\t\t\t * If the commit is a starting point (and hasn't been\n+\t\t\t * seen yet), then initialize the set of interesting\n+\t\t\t * paths, too.\n+\t\t\t */\n+\t\t\tstruct bitmap *active;\n\n-\t\tif (data.commit->object.flags & BOUNDARY) {\n+\t\t\tprio_queue_put(&queue, c);\n+\t\t\tc->object.flags |= PARENT1;\n+\n+\t\t\tactive = active_paths_for(lm, c);\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\t\t\tbitmap_set(active, i);\n+\t\t}\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tint parent_i;\n+\t\tstruct commit_list *p;\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tstruct bitmap *active_c = active_paths_for(lm, c);\n+\n+\t\tif ((0 <= max_count && max_count < ++queue_popped) ||\n+\t\t    (c->object.flags & PARENT2)) {\n+\t\t\t/*\n+\t\t\t * Either a boundary commit, or we have already seen too\n+\t\t\t * many others. Either way, stop here.\n+\t\t\t */\n+\t\t\tc->object.flags |= PARENT2 | BOUNDARY;\n+\t\t\tdata.commit = c;\n \t\t\tdiff_tree_oid(lm->rev.repo->hash_algo->empty_tree,\n-\t\t\t\t      &data.commit->object.oid, \"\",\n-\t\t\t\t      &lm->rev.diffopt);\n+\t\t\t\t      &c->object.oid,\n+\t\t\t\t      \"\", &lm->rev.diffopt);\n \t\t\tdiff_flush(&lm->rev.diffopt);\n+\t\t\tgoto cleanup;\n+\t\t}\n\n-\t\t\tbreak;\n+\t\t/*\n+\t\t * Otherwise, make sure that 'c' isn't reachable from anything\n+\t\t * in the '--not' queue.\n+\t\t */\n+\t\trepo_parse_commit(lm->rev.repo, c);\n+\n+\t\twhile (not_queue.nr) {\n+\t\t\tstruct commit_list *np;\n+\t\t\tstruct commit *n = prio_queue_get(&not_queue);\n+\n+\t\t\trepo_parse_commit(lm->rev.repo, n);\n+\n+\t\t\tfor (np = n->parents; np; np = np->next) {\n+\t\t\t\tif (!(np->item->object.flags & PARENT2)) {\n+\t\t\t\t\tprio_queue_put(&not_queue, np->item);\n+\t\t\t\t\tnp->item->object.flags |= PARENT2;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tif (commit_graph_generation(n) < commit_graph_generation(c))\n+\t\t\t\tbreak;\n \t\t}\n\n-\t\tif (!maybe_changed_path(lm, data.commit))\n-\t\t\tcontinue;\n+\t\t/*\n+\t\t * Look at each parent and pass on each path that's TREESAME\n+\t\t * with that parent. Stop early when no active paths remain.\n+\t\t */\n+\t\tfor (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {\n+\t\t\tprocess_parent(lm, &queue,\n+\t\t\t\t       c, active_c,\n+\t\t\t\t       p->item, parent_i);\n+\n+\t\t\tif (bitmap_is_empty(active_c))\n+\t\t\t\tbreak;\n+\t\t}\n+\n+\t\t/*\n+\t\t * Paths that remain active, or not TREESAME with any parent,\n+\t\t * were changed by 'c'.\n+\t\t */\n+\t\tif (!bitmap_is_empty(active_c)) {\n+\t\t\tdata.commit = c;\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n+\t\t\t\tif (bitmap_get(active_c, i))\n+\t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n+\t\t}\n\n-\t\tlog_tree_commit(&lm->rev, data.commit);\n+cleanup:\n+\t\tactive_paths_free(lm, c);\n \t}\n\n+\tif (hashmap_get_size(&lm->paths))\n+\t\tBUG(\"paths remaining beyond boundary in last-modified\");\n+\n+\tclear_prio_queue(&not_queue);\n+\tclear_prio_queue(&queue);\n+\tclear_active_paths_for_commit(&lm->active_paths);\n+\tbitmap_free(lm->scratch);\n+\n \treturn 0;\n }\n\n static int last_modified_init(struct last_modified *lm, struct repository *r,\n \t\t\t      const char *prefix, int argc, const char **argv)\n {\n+\tstruct hashmap_iter iter;\n+\tstruct last_modified_entry *ent;\n+\n \thashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);\n\n \trepo_init_revisions(r, &lm->rev, prefix);\n@@ -280,6 +491,13 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,\n \tif (populate_paths_from_revs(lm) < 0)\n \t\treturn error(_(\"unable to setup last-modified\"));\n\n+\tCALLOC_ARRAY(lm->all_paths, hashmap_get_size(&lm->paths));\n+\tlm->all_paths_nr = 0;\n+\thashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {\n+\t\tent->diff_idx = lm->all_paths_nr++;\n+\t\tlm->all_paths[ent->diff_idx] = ent->path;\n+\t}\n+\n \treturn 0;\n }\n\ndiff --git a/object.h b/object.h\nindex 8c3c1c46e1..fa504a09c0 100644\n--- a/object.h\n+++ b/object.h\n@@ -75,6 +75,7 @@ void object_array_init(struct object_array *array);\n  * http-push.c:                          11-----14\n  * commit-graph.c:                                15\n  * commit-reach.c:                                  16-----19\n+ * builtin/last-modified.c:                         1617\n  * sha1-name.c:                                              20\n  * list-objects-filter.c:                                      21\n  * bloom.c:                                                    2122\ndiff --git a/t/t8020-last-modified.sh b/t/t8020-last-modified.sh\nindex 61f00bc15c..a4c1114ee2 100755\n--- a/t/t8020-last-modified.sh\n+++ b/t/t8020-last-modified.sh\n@@ -57,9 +57,9 @@ test_expect_success 'last-modified recursive' '\n\n test_expect_success 'last-modified recursive with show-trees' '\n \tcheck_last_modified -r -t <<-\\EOF\n-\t3 a\n \t3 a/b\n \t3 a/b/file\n+\t3 a\n \t2 a/file\n \t1 file\n \tEOF\n--\n2.51.2\n"},{"id":"530134","messageId":"xmqq7bw7ukvj.fsf@gitster.g","threadId":"64332","inReplyTo":"20251103154726.26592-1-toon@iotcl.com","subject":"Re: [PATCH v4] last-modified: implement faster algorithm","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-11-03T16:44:00Z","receivedAt":"2025-11-03T16:44:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Toon Claes <toon@iotcl.com> writes:\n\n> Changes in v4:\n> - Use CALLOC_ARRAY() instead of xcalloc() as identified by Junio using\n>   'make coccicheck'.\n> - Small formatting changes.\n> - Link to v3: https://lore.kernel.org/all/20251023-b4-toon-last-modified-faster-v3-1-40a4ddbbadec@iotcl.com\n\nSorry, but this came way after I started today's integration cycle,\nwhich included merging the fixed-up version to 'next'.  I saw some\n\"let's drop {} around the body of if/for with a single statement\"\nchanges but each of these single statements was not a simple\nstatement but an if-statement, and personally I feel that it is\nclearer to enclose them in {} (in other words, once the code is\nwritten in that way, it is not worth the patch noise to go and fix\nthem).  The only regrettable thing without v4 is the double space\nbetween \") {\" in the second hunk below X-<, but perhaps it is minor\nenough to leave it to the next person who touches the vicinity of\nthis code ;-).  If you feel strongly about them, please send in an\nincremental updates, but as I said, I do not think it is necessary.\n\nThanks.\n\ndiff --git a/b0ecbdc540 b/3028abd25e\nindex b0ecbdc540..3028abd25e 100644\n--- a/b0ecbdc540\n+++ b/3028abd25e\n@@ -312,10 +312,9 @@ static void process_parent(struct last_modified *lm,\n \t\t\t\tbitmap_set(lm->scratch, k);\n \t\t}\n \t}\n-\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n \t\tif (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))\n \t\t\tpass_to_parent(active_c, active_p, i);\n-\t}\n \n \t/*\n \t * If parent has any active paths, put it on the queue (if not already).\n@@ -440,12 +439,11 @@ static int last_modified_run(struct last_modified *lm)\n \t\t * Paths that remain active, or not TREESAME with any parent,\n \t\t * were changed by 'c'.\n \t\t */\n-\t\tif (!bitmap_is_empty(active_c))  {\n+\t\tif (!bitmap_is_empty(active_c)) {\n \t\t\tdata.commit = c;\n-\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++) {\n+\t\t\tfor (size_t i = 0; i < lm->all_paths_nr; i++)\n \t\t\t\tif (bitmap_get(active_c, i))\n \t\t\t\t\tmark_path(lm->all_paths[i], NULL, &data);\n-\t\t\t}\n \t\t}\n \n cleanup:\n"},{"id":"530194","messageId":"87ms51esxw.fsf@iotcl.com","threadId":"64332","inReplyTo":"xmqq7bw7ukvj.fsf@gitster.g","subject":"Re: [PATCH v4] last-modified: implement faster algorithm","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-11-04T15:08:43Z","receivedAt":"2025-11-04T15:09:08Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Toon Claes <toon@iotcl.com> writes:\n>\n>> Changes in v4:\n>> - Use CALLOC_ARRAY() instead of xcalloc() as identified by Junio using\n>>   'make coccicheck'.\n>> - Small formatting changes.\n>> - Link to v3: https://lore.kernel.org/all/20251023-b4-toon-last-modified-faster-v3-1-40a4ddbbadec@iotcl.com\n>\n> Sorry, but this came way after I started today's integration cycle,\n\nNo worries.\n\n> which included merging the fixed-up version to 'next'.\n\nWell, thank you.\n\n> I saw some\n> \"let's drop {} around the body of if/for with a single statement\"\n> changes but each of these single statements was not a simple\n> statement but an if-statement, and personally I feel that it is\n> clearer to enclose them in {} (in other words, once the code is\n> written in that way, it is not worth the patch noise to go and fix\n> them).\n\nUnderstood.\n\n> The only regrettable thing without v4 is the double space\n> between \") {\" in the second hunk below X-<, but perhaps it is minor\n> enough to leave it to the next person who touches the vicinity of\n> this code ;-). If you feel strongly about them, please send in an\n> incremental updates, but as I said, I do not think it is necessary.\n\nIt remained undiscovered by various reviewers and myself. I only noticed\nbecause I saw CI style-check mention this (also the reason I touched the\n{} on the for loops). So I don't mind leaving it this way.\n\n> Thanks.\n\n<3\n\n-- \nCheers,\nToon\n"},{"id":"530988","messageId":"4dc4c8cd-c0cc-4784-8fcf-defa3a051087@mit.edu","threadId":"64332","inReplyTo":"20251103154726.26592-1-toon@iotcl.com","subject":"t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Anders Kaseorg","fromEmail":"andersk@mit.edu","sentAt":"2025-11-19T11:34:26Z","receivedAt":"2025-11-19T11:34:47Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"t8020-last-modified.sh is broken on the s390x platform in v2.52.0. \nBisection implicates commit 2a04e8c293766a4976ceceb4c663dd2963e0339e \n“last-modified: implement faster algorithm” [1].\n\n$ uname -m\ns390x\n\n$ ./t8020-last-modified.sh\nok 1 - setup\nok 2 - cannot run last-modified on two trees\nok 3 - last-modified non-recursive\nok 4 - last-modified recursive\nok 5 - last-modified recursive with show-trees\nok 6 - last-modified non-recursive with show-trees\nok 7 - last-modified subdir\nok 8 - last-modified subdir recursive\nok 9 - last-modified from non-HEAD commit\nok 10 - last-modified from subdir defaults to root\nok 11 - last-modified from subdir uses relative pathspecs\nok 12 - limit last-modified traversal by count\nok 13 - limit last-modified traversal by commit\nok 14 - only last-modified files in the current tree\nok 15 - subdirectory modified via merge\nnot ok 16 - cross merge boundaries in blaming\n#\t\n#\t\tgit checkout HEAD^0 &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit m1 &&\n#\t\tgit checkout HEAD^ &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit m2 &&\n#\t\tgit merge m1 &&\n#\t\tcheck_last_modified <<-\\EOF\n#\t\tm2 m2.t\n#\t\tm1 m1.t\n#\t\tEOF\n#\t\nok 17 - last-modified merge for resolved conflicts\nok 18 - last-modified merge ignores content from branch\nnot ok 19 - last-modified merge undoes changes\n#\t\n#\t\tgit checkout HEAD^0 &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit b1 file A &&\n#\t\ttest_commit b2 file B &&\n#\t\ttest_commit b3 file C &&\n#\t\ttest_commit b4 file D &&\n#\t\tgit checkout b2 &&\n#\t\ttest_commit b5 file2 2 &&\n#\t\tgit checkout b4 &&\n#\t\tgit merge --no-commit --no-ff b5 &&\n#\t\tgit checkout b2 -- file &&\n#\t\tgit merge --continue &&\n#\t\tcheck_last_modified <<-\\EOF\n#\t\tb5 file2\n#\t\tb2 file\n#\t\tEOF\n#\t\nok 20 - last-modified complains about unknown arguments\n# failed 2 among 20 test(s)\n1..20\n\n$ ./t8020-last-modified.sh --verbose\n[…]\n\nexpecting success of 8020.16 'cross merge boundaries in blaming':\n\tgit checkout HEAD^0 &&\n\tgit rm -rf . &&\n\ttest_commit m1 &&\n\tgit checkout HEAD^ &&\n\tgit rm -rf . &&\n\ttest_commit m2 &&\n\tgit merge m1 &&\n\tcheck_last_modified <<-\\EOF\n\tm2 m2.t\n\tm1 m1.t\n\tEOF\n\nNote: switching to 'HEAD^0'.\n\nYou are in 'detached HEAD' state. You can look around, make experimental\nchanges and commit them, and you can discard any commits you make in this\nstate without impacting any branches by switching back to a branch.\n\nIf you want to create a new branch to retain commits you create, you may\ndo so (now or later) by using -c with the switch command. Example:\n\n   git switch -c <new-branch-name>\n\nOr undo this operation with:\n\n   git switch -\n\nTurn off this advice by setting config variable advice.detachedHead to false\n\nHEAD is now at 08525b6 remove a\nrm 'file'\n[detached HEAD 53e7187] m1\n  Author: A U Thor <author@example.com>\n  2 files changed, 1 insertion(+), 1 deletion(-)\n  delete mode 100644 file\n  create mode 100644 m1.t\nPrevious HEAD position was 53e7187 m1\nHEAD is now at 08525b6 remove a\nrm 'file'\n[detached HEAD 9b81a41] m2\n  Author: A U Thor <author@example.com>\n  2 files changed, 1 insertion(+), 1 deletion(-)\n  delete mode 100644 file\n  create mode 100644 m2.t\nMerge made by the 'ort' strategy.\n  m1.t | 1 +\n  1 file changed, 1 insertion(+)\n  create mode 100644 m1.t\n--- expect\t2025-11-19 11:28:57.966106204 +0000\n+++ actual\t2025-11-19 11:28:58.110112543 +0000\n@@ -1,2 +1,2 @@\n+ac29b6e974b49803f1c6ec5a705d1bf7dbfa7d2f m1.t\n  m2 m2.t\n-m1 m1.t\nnot ok 16 - cross merge boundaries in blaming\n#\t\n#\t\tgit checkout HEAD^0 &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit m1 &&\n#\t\tgit checkout HEAD^ &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit m2 &&\n#\t\tgit merge m1 &&\n#\t\tcheck_last_modified <<-\\EOF\n#\t\tm2 m2.t\n#\t\tm1 m1.t\n#\t\tEOF\n#\t\n\n[…]\n\nexpecting success of 8020.19 'last-modified merge undoes changes':\n\tgit checkout HEAD^0 &&\n\tgit rm -rf . &&\n\ttest_commit b1 file A &&\n\ttest_commit b2 file B &&\n\ttest_commit b3 file C &&\n\ttest_commit b4 file D &&\n\tgit checkout b2 &&\n\ttest_commit b5 file2 2 &&\n\tgit checkout b4 &&\n\tgit merge --no-commit --no-ff b5 &&\n\tgit checkout b2 -- file &&\n\tgit merge --continue &&\n\tcheck_last_modified <<-\\EOF\n\tb5 file2\n\tb2 file\n\tEOF\n\nHEAD is now at 7b0602a Merge tag 'a4' into HEAD\nrm 'file'\n[detached HEAD c48d0f6] b1\n  Author: A U Thor <author@example.com>\n  1 file changed, 1 insertion(+), 1 deletion(-)\n[detached HEAD ee27b37] b2\n  Author: A U Thor <author@example.com>\n  1 file changed, 1 insertion(+), 1 deletion(-)\n[detached HEAD c90ce7d] b3\n  Author: A U Thor <author@example.com>\n  1 file changed, 1 insertion(+), 1 deletion(-)\n[detached HEAD 317a439] b4\n  Author: A U Thor <author@example.com>\n  1 file changed, 1 insertion(+), 1 deletion(-)\nPrevious HEAD position was 317a439 b4\nHEAD is now at ee27b37 b2\n[detached HEAD 5526d49] b5\n  Author: A U Thor <author@example.com>\n  1 file changed, 1 insertion(+)\n  create mode 100644 file2\nPrevious HEAD position was 5526d49 b5\nHEAD is now at 317a439 b4\nAutomatic merge went well; stopped before committing as requested\n[detached HEAD da1857e] Merge tag 'b5' into HEAD\n  Author: A U Thor <author@example.com>\n--- expect\t2025-11-19 11:29:03.492349022 +0000\n+++ actual\t2025-11-19 11:29:03.648355864 +0000\n@@ -1,2 +1,2 @@\n-b5 file2\n-b2 file\n+da1857e0652b6f264c0038d684ddecddc273e506 file2\n+da1857e0652b6f264c0038d684ddecddc273e506 file\nnot ok 19 - last-modified merge undoes changes\n#\t\n#\t\tgit checkout HEAD^0 &&\n#\t\tgit rm -rf . &&\n#\t\ttest_commit b1 file A &&\n#\t\ttest_commit b2 file B &&\n#\t\ttest_commit b3 file C &&\n#\t\ttest_commit b4 file D &&\n#\t\tgit checkout b2 &&\n#\t\ttest_commit b5 file2 2 &&\n#\t\tgit checkout b4 &&\n#\t\tgit merge --no-commit --no-ff b5 &&\n#\t\tgit checkout b2 -- file &&\n#\t\tgit merge --continue &&\n#\t\tcheck_last_modified <<-\\EOF\n#\t\tb5 file2\n#\t\tb2 file\n#\t\tEOF\n#\t\n\nAnders\n\n[1] https://lore.kernel.org/git/20251103154726.26592-1-toon@iotcl.com/\n\n"},{"id":"530989","messageId":"3b24b6a3-61cc-4b9a-a823-f1e58fd9919b@app.fastmail.com","threadId":"64332","inReplyTo":"4dc4c8cd-c0cc-4784-8fcf-defa3a051087@mit.edu","subject":"Re: t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Kristoffer Haugsbakk","fromEmail":"kristofferhaugsbakk@fastmail.com","sentAt":"2025-11-19T13:49:00Z","receivedAt":"2025-11-19T13:49:23Z","isPatch":true,"sender":{"key":"kristofferhaugsbakk@fastmail.com","avatar":null},"body":"On Wed, Nov 19, 2025, at 12:34, Anders Kaseorg wrote:\n> t8020-last-modified.sh is broken on the s390x platform in v2.52.0.\n> Bisection implicates commit 2a04e8c293766a4976ceceb4c663dd2963e0339e\n> “last-modified: implement faster algorithm” [1].\n>\n\nDoes `./t8020-last-modified.sh --verbose` give any interesting output?\n\n>[snip]\n>\n> [1] https://lore.kernel.org/git/20251103154726.26592-1-toon@iotcl.com/\n"},{"id":"531006","messageId":"ceacc47b-9d29-4e32-9d83-6bd68279c83c@mit.edu","threadId":"64332","inReplyTo":"3b24b6a3-61cc-4b9a-a823-f1e58fd9919b@app.fastmail.com","subject":"Re: t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Anders Kaseorg","fromEmail":"andersk@mit.edu","sentAt":"2025-11-19T20:06:35Z","receivedAt":"2025-11-19T20:06:55Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On 11/19/25 05:49, Kristoffer Haugsbakk wrote:\n> On Wed, Nov 19, 2025, at 12:34, Anders Kaseorg wrote: >> t8020-last-modified.sh is broken on the s390x platform in v2.52.0. \n >> Bisection implicates commit >> \n2a04e8c293766a4976ceceb4c663dd2963e0339e “last-modified: implement >> \nfaster algorithm” [1]. > > Does `./t8020-last-modified.sh --verbose` \ngive any interesting > output?\nI quoted that output in my previous message. The failures in subtests 16 \nand 19 come with these diffs:\n\n--- expect    2025-11-19 11:28:57.966106204 +0000\n+++ actual    2025-11-19 11:28:58.110112543 +0000\n@@ -1,2 +1,2 @@\n+ac29b6e974b49803f1c6ec5a705d1bf7dbfa7d2f m1.t\n  m2 m2.t\n-m1 m1.t\n\n[…]\n\n--- expect    2025-11-19 11:29:03.492349022 +0000\n+++ actual    2025-11-19 11:29:03.648355864 +0000\n@@ -1,2 +1,2 @@\n-b5 file2\n-b2 file\n+da1857e0652b6f264c0038d684ddecddc273e506 file2\n+da1857e0652b6f264c0038d684ddecddc273e506 file\n\nAnders\n\n"},{"id":"531052","messageId":"20251120081611.GC1283645@coredump.intra.peff.net","threadId":"64332","inReplyTo":"ceacc47b-9d29-4e32-9d83-6bd68279c83c@mit.edu","subject":"Re: t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2025-11-20T08:16:11Z","receivedAt":"2025-11-20T08:16:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Nov 19, 2025 at 12:06:35PM -0800, Anders Kaseorg wrote:\n\n> On 11/19/25 05:49, Kristoffer Haugsbakk wrote:\n> > On Wed, Nov 19, 2025, at 12:34, Anders Kaseorg wrote: >>\n> > t8020-last-modified.sh is broken on the s390x platform in v2.52.0.\n> >> Bisection implicates commit >> 2a04e8c293766a4976ceceb4c663dd2963e0339e\n> “last-modified: implement >> faster algorithm” [1]. > > Does\n> `./t8020-last-modified.sh --verbose` give any interesting > output?\n> I quoted that output in my previous message. The failures in subtests 16 and\n> 19 come with these diffs:\n> \n> --- expect    2025-11-19 11:28:57.966106204 +0000\n> +++ actual    2025-11-19 11:28:58.110112543 +0000\n> @@ -1,2 +1,2 @@\n> +ac29b6e974b49803f1c6ec5a705d1bf7dbfa7d2f m1.t\n>  m2 m2.t\n> -m1 m1.t\n> \n> […]\n> \n> --- expect    2025-11-19 11:29:03.492349022 +0000\n> +++ actual    2025-11-19 11:29:03.648355864 +0000\n> @@ -1,2 +1,2 @@\n> -b5 file2\n> -b2 file\n> +da1857e0652b6f264c0038d684ddecddc273e506 file2\n> +da1857e0652b6f264c0038d684ddecddc273e506 file\n\nInterestingly, the commits it returns are merges. E.g., here is the\nstate after test 16:\n\n  $ git log --oneline --graph\n  *   ac29b6e (HEAD) Merge tag 'm1' into HEAD\n  |\\\n  | * 53e7187 (tag: m1) m1\n  * | 9b81a41 (tag: m2) m2\n  |/\n  * 08525b6 (master) remove a\n  * 664d121 (tag: 3) 3\n  * a732b0c (tag: 2) 2\n  * 1edf6f6 (tag: 1) 1\n\nThough it is also the first commit we start traversing from. The same is\ntrue after test 19 (da1857e is the tip of HEAD there). So I am not sure\nif the bug is \"we are not passing down blame from the merge\", or just\n\"we are not passing down blame at all\".\n\nI can't help but notice that this same failure is seen on s390x and HP\nNonStop[1], both of which are (I think) big-endian. And not on any of\nour usual little-endian platforms.\n\nI don't see anything that looks questionable in terms of casting or\ninteger handling in the patch that introduced the problem, though.\nProbably a long shot, but if you are able to build with \"make\nSANITIZE=address,undefined\" and re-run t8020, that would let us check\nfor endian-specific memory access issues.\n\n-Peff\n\n[1] https://lore.kernel.org/git/003901dc596c$40bfbd80$c23f3880$@nexbridge.com/\n"},{"id":"531405","messageId":"87y0nq14xm.fsf@iotcl.com","threadId":"64332","inReplyTo":"20251120081611.GC1283645@coredump.intra.peff.net","subject":"Re: t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Toon Claes","fromEmail":"toon@iotcl.com","sentAt":"2025-11-28T16:45:57Z","receivedAt":"2025-11-28T16:46:12Z","isPatch":true,"sender":{"key":"toon@iotcl.com","avatar":"https://avatars.githubusercontent.com/u/121621?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Nov 19, 2025 at 12:06:35PM -0800, Anders Kaseorg wrote:\n>\n>> The failures in subtests 16 and 19 come with these diffs:\n>> \n>> --- expect    2025-11-19 11:28:57.966106204 +0000\n>> +++ actual    2025-11-19 11:28:58.110112543 +0000\n>> @@ -1,2 +1,2 @@\n>> +ac29b6e974b49803f1c6ec5a705d1bf7dbfa7d2f m1.t\n>>  m2 m2.t\n>> -m1 m1.t\n>> \n>> […]\n>> \n>> --- expect    2025-11-19 11:29:03.492349022 +0000\n>> +++ actual    2025-11-19 11:29:03.648355864 +0000\n>> @@ -1,2 +1,2 @@\n>> -b5 file2\n>> -b2 file\n>> +da1857e0652b6f264c0038d684ddecddc273e506 file2\n>> +da1857e0652b6f264c0038d684ddecddc273e506 file\n\nKristoffer, thank you for reporting this bug. It seems there was a real\nbug in git-last-modified, which was uncovered by these tests running on\ns390x.\n\n> Interestingly, the commits it returns are merges. E.g., here is the\n> state after test 16:\n>\n>   $ git log --oneline --graph\n>   *   ac29b6e (HEAD) Merge tag 'm1' into HEAD\n>   |\\\n>   | * 53e7187 (tag: m1) m1\n>   * | 9b81a41 (tag: m2) m2\n>   |/\n>   * 08525b6 (master) remove a\n>   * 664d121 (tag: 3) 3\n>   * a732b0c (tag: 2) 2\n>   * 1edf6f6 (tag: 1) 1\n>\n> Though it is also the first commit we start traversing from. The same is\n> true after test 19 (da1857e is the tip of HEAD there). So I am not sure\n> if the bug is \"we are not passing down blame from the merge\", or just\n> \"we are not passing down blame at all\".\n>\n> I can't help but notice that this same failure is seen on s390x and HP\n> NonStop[1], both of which are (I think) big-endian. And not on any of\n> our usual little-endian platforms.\n\nPeff, thanks for the pointer. It costed me more time than I'd like to\nadmit, but I've reproduced and debugged the issue to find and fix the\nroot cause. The problem is bigger than on big-endian only, bug it was\nuncovered by this test running on a big-endian system.\n\nBoth, I've submitted a bug fix at:\nhttps://lore.kernel.org/git/20251128-toon-big-endian-ci-v1-1-80da0f629c1e@iotcl.com/\n\n-- \nCheers,\nToon\n"},{"id":"531407","messageId":"a7de959c-cedf-4a24-a45f-a28939ab5125@app.fastmail.com","threadId":"64332","inReplyTo":"87y0nq14xm.fsf@iotcl.com","subject":"Re: t8020-last-modified.sh failure on s390x (Re: [PATCH v4] last-modified: implement faster algorithm)","fromName":"Kristoffer Haugsbakk","fromEmail":"kristofferhaugsbakk@fastmail.com","sentAt":"2025-11-28T17:35:52Z","receivedAt":"2025-11-28T17:36:14Z","isPatch":true,"sender":{"key":"kristofferhaugsbakk@fastmail.com","avatar":null},"body":"On Fri, Nov 28, 2025, at 17:45, Toon Claes wrote:\n> Jeff King <peff@peff.net> writes:\n>[snip]\n>>> --- expect    2025-11-19 11:29:03.492349022 +0000\n>>> +++ actual    2025-11-19 11:29:03.648355864 +0000\n>>> @@ -1,2 +1,2 @@\n>>> -b5 file2\n>>> -b2 file\n>>> +da1857e0652b6f264c0038d684ddecddc273e506 file2\n>>> +da1857e0652b6f264c0038d684ddecddc273e506 file\n>\n> Kristoffer, thank you for reporting this bug. It seems there was a real\n> bug in git-last-modified, which was uncovered by these tests running on\n> s390x.\n\nTypo. r/Kristoffer/Anders/ :)\n"}]}