)]}'
{
  "commit": "2a04e8c293766a4976ceceb4c663dd2963e0339e",
  "tree": "35f834644bda49615c4fca78d5d356d447e51cbf",
  "parents": [
    "a99f379adf116d53eb11957af5bab5214915f91d"
  ],
  "author": {
    "name": "Toon Claes",
    "email": "toon@iotcl.com",
    "time": "Thu Oct 23 09:50:14 2025 +0200"
  },
  "committer": {
    "name": "Junio C Hamano",
    "email": "gitster@pobox.com",
    "time": "Mon Nov 03 07:25:41 2025 -0800"
  },
  "message": "last-modified: implement faster algorithm\n\nThe 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\u0027active\u0027 paths (a path is \u0027active\u0027 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, \u0027c\u0027, off of the queue, making sure that \u0027c\u0027\n     isn\u0027t reachable by anything in the \u0027--not\u0027 set.\n\n  2. For each parent \u0027p\u0027 (with index \u0027parent_i\u0027) of \u0027c\u0027, do the\n     following:\n\n     a. Compute the diff between \u0027c\u0027 and \u0027p\u0027.\n     b. Pass any active paths that are TREESAME from \u0027c\u0027 to \u0027p\u0027.\n     c. If \u0027p\u0027 has any active paths, push it onto the queue.\n\n  3. Any path that remains active on \u0027c\u0027 is associated to that commit.\n\nThis ends up being equivalent to doing something like \u0027git log -1 --\n$path\u0027 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 \u0027c\u0027 are DEFINITELY NOT in c\u0027s\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 \u0027master\u0027 gives:\n\n    $ git log --max-count\u003d1 --format\u003d%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\u003d1`.\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 \u003cstolee@gmail.com\u003e\nBased-on-patches-by: Taylor Blau \u003cme@ttaylorr.com\u003e\nSigned-off-by: Taylor Blau \u003cme@ttaylorr.com\u003e\nSigned-off-by: Toon Claes \u003ctoon@iotcl.com\u003e\nAcked-by: Taylor Blau \u003cme@ttaylorr.com\u003e\n[jc: tweaked use of xcalloc() to unbreak coccicheck]\nSigned-off-by: Junio C Hamano \u003cgitster@pobox.com\u003e\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "ae8b36a2c3515c6a3931b04bad6c95fae36ac592",
      "old_mode": 33188,
      "old_path": "builtin/last-modified.c",
      "new_id": "b0ecbdc5400d137b7e147c8f91f43210cf8236e0",
      "new_mode": 33188,
      "new_path": "builtin/last-modified.c"
    },
    {
      "type": "modify",
      "old_id": "8c3c1c46e1bf04e8e51d7b72c88bc352077c54d0",
      "old_mode": 33188,
      "old_path": "object.h",
      "new_id": "fa504a09c0a48dbab1a3f108cc438267ffc89cd4",
      "new_mode": 33188,
      "new_path": "object.h"
    },
    {
      "type": "modify",
      "old_id": "61f00bc15c3b2d170d981038f0ebb48fd4bf31c2",
      "old_mode": 33261,
      "old_path": "t/t8020-last-modified.sh",
      "new_id": "a4c1114ee28f7fca858e425c0eeb69f3f5c98d0f",
      "new_mode": 33261,
      "new_path": "t/t8020-last-modified.sh"
    }
  ]
}