Add performance improvements to git-last-modified(1)
The subcommand git-last-modified(1) was based on the patches shared by Taylor and the folks at GitHub1. That version used an alternative implementation to make it "go faster". When I was working on upstreaming those patches, I dropped the patches2 for this implementation, because I didn't see significant improvements.
This series revives those changes. I did more thorough deep dive through the code and the algorithm and got the code working a lot faster. The benchmark results can be found in the commit message.
Some changes compared to GitHub's version include:
-
Use of
struct bitmapfrom "ewah/ewok.h", instead of self-definedstruct commit_active_paths. -
Removed shortcut code that handled the case when commit and parent are fully treesame, and instead always checked 'active_c' whether the next parent is worth looking at.
-
Modified comments and commit message to make the algorithm more clear (at least to me).
-
Mentioned the use of PARENT1 and PARENT2 in object.h.
-
Removed the use of any global variables.
-
Less conditions are checked in mark_path() because the hashmap of 'paths' is considered the single-source of truth.
-
pass_to_parent() doesn't pass on when the path isn't in the 'paths' hashmap no more.
Cc: Karthik Nayak karthik.188@gmail.com Cc: Justin Tobler jltobler@gmail.com Cc: Taylor Blau me@ttaylorr.com Cc: "D. Ben Knoble" ben.knoble@gmail.com Signed-off-by: Toon Claes toon@iotcl.com
Changes in v3:
- Make code cleanly compile with -Wsign-compare
- Remove path_idx() and instead inline the code in the loop. This fixes the sign comparison issue and the function was only used in one place anyway.
- Make all the memory leaks go away.
- Small tweaks in naming and code comments.
- Link to v2: https://lore.kernel.org/r/20251021-b4-toon-last-modified-faster-v2-1-f6dcbc26fc5c@iotcl.com
Changes in v2:
- Add benchmark results comparing repositories with and without Bloom filters in commit message.
- Add Stolee and Taylor in the commit message trailers.
- Fix segfault by checking if 'oid' is set in mark_path().
- Remove hashmap lookup in pass_to_parent().
- Remove manually calling diff_free_filepair().
- Rename commit slab bitmap to "active_paths_bitmap".
- Link to v1: https://lore.kernel.org/r/20251016-b4-toon-last-modified-faster-v1-1-85dca8a29e5c@iotcl.com