[PATCH v3] last-modified: implement faster algorithm

The current implementation of git-last-modified(1) works by doing a revision walk, and inspecting the diff at each level of that walk to annotate entries remaining in the hashmap of paths. In other words, if the diff at some level touches a path which has not yet been associated with a commit, then that commit becomes associated with the path.

While a perfectly reasonable implementation, it can perform poorly in either one of two scenarios:

  1. There are many entries of interest, in which case there is simply
     a lot of work to do.

  2. Or, there are (even a few) entries which have not been updated in a
     long time, and so we must walk through a lot of history in order to
     find a commit that touches that path.

This patch rewrites the last-modified implementation that addresses the second point. The idea behind the algorithm is to propagate a set of 'active' paths (a path is 'active' if it does not yet belong to a commit) up to parents and do a truncated revision walk.

The walk is truncated because it does not produce a revision for every change in the original pathspec, but rather only for active paths.

More specifically, consider a priority queue of commits sorted by generation number. First, enqueue the set of boundary commits with all paths in the original spec marked as interesting.

Then, while the queue is not empty, do the following:

  1. Pop an element, say, 'c', off of the queue, making sure that 'c'
     isn't reachable by anything in the '--not' set.

  2. For each parent 'p' (with index 'parent_i') of 'c', do the
     following:

     a. Compute the diff between 'c' and 'p'.
     b. Pass any active paths that are TREESAME from 'c' to 'p'.
     c. If 'p' has any active paths, push it onto the queue.

  3. Any path that remains active on 'c' is associated to that commit.

This ends up being equivalent to doing something like 'git log -1 -- $path' for each path simultaneously. But, it allows us to go much faster than the original implementation by limiting the number of diffs we compute, since we can avoid parts of history that would have been considered by the revision walk in the original implementation, but are known to be uninteresting to us because we have already marked all paths in that area to be inactive.

To avoid computing many first-parent diffs, add another trick on top of this and check if all paths active in 'c' are DEFINITELY NOT in c's Bloom filter. Since the commit-graph only stores first-parent diffs in the Bloom filters, we can only apply this trick to first-parent diffs.

Comparing the performance of this new algorithm shows about a 2.5x improvement on git.git:

    Benchmark 1: master   no bloom
      Time (mean ± σ):      2.868 s ±  0.023 s    [User: 2.811 s, System: 0.051 s]
      Range (min … max):    2.847 s …  2.926 s    10 runs

    Benchmark 2: master with bloom
      Time (mean ± σ):     949.9 ms ±  15.2 ms    [User: 907.6 ms, System: 39.5 ms]
      Range (min … max):   933.3 ms … 971.2 ms    10 runs

    Benchmark 3: HEAD     no bloom
      Time (mean ± σ):     782.0 ms ±   6.3 ms    [User: 740.7 ms, System: 39.2 ms]
      Range (min … max):   776.4 ms … 798.2 ms    10 runs

    Benchmark 4: HEAD   with bloom
      Time (mean ± σ):     307.1 ms ±   1.7 ms    [User: 276.4 ms, System: 29.9 ms]
      Range (min … max):   303.7 ms … 309.5 ms    10 runs

    Summary
      HEAD   with bloom ran
        2.55 ± 0.02 times faster than HEAD     no bloom
        3.09 ± 0.05 times faster than master with bloom
        9.34 ± 0.09 times faster than master   no bloom

In short, the existing implementation is comparably fast *with* Bloom filters as the new implementation is *without* Bloom filters. So, most repositories should get a dramatic speed-up by just deploying this (even without computing Bloom filters), and all repositories should get faster still when computing Bloom filters.

When comparing a more extreme example of `git last-modified -- COPYING t`, the difference is even 5 times better:

    Benchmark 1: master
      Time (mean ± σ):      4.372 s ±  0.057 s    [User: 4.286 s, System: 0.062 s]
      Range (min … max):    4.308 s …  4.509 s    10 runs

    Benchmark 2: HEAD
      Time (mean ± σ):     826.3 ms ±  22.3 ms    [User: 784.1 ms, System: 39.2 ms]
      Range (min … max):   810.6 ms … 881.2 ms    10 runs

    Summary
      HEAD ran
        5.29 ± 0.16 times faster than master

As an added benefit, results are more consistent now. For example implementation in 'master' gives:

    $ git log --max-count=1 --format=%H -- pkt-line.h
    15df15fe07ef66b51302bb77e393f3c5502629de

    $ git last-modified -- pkt-line.h
    15df15fe07ef66b51302bb77e393f3c5502629de	pkt-line.h

    $ git last-modified | grep pkt-line.h
    5b49c1af03e600c286f63d9d9c9fb01403230b9f	pkt-line.h

With the changes in this patch the results of git-last-modified(1) always match those of `git log --max-count=1`.

One thing to note though, the results might be outputted in a different order than before. This is not considerd to be an issue because nowhere is documented the order is guaranteed.

Based-on-patches-by: Derrick Stolee <stolee@gmail.com>
Based-on-patches-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Toon Claes <toon@iotcl.com>
---
The subcommand git-last-modified(1) was based on the patches shared by
Taylor and the folks at GitHub[1]. That version used an alternative
implementation to make it "go faster". When I was working on upstreaming
those patches, I dropped the patches[2] 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 bitmap` from "ewah/ewok.h", instead of self-defined
   `struct 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.

[1]: https://lore.kernel.org/git/Z+XJ+1L3PnC9Dyba@nand.local/
[2]: https://lore.kernel.org/git/20250630-toon-new-blame-tree-v3-0-3516025dc3bc@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

Range-diff against v2:

1:  e131d0df85 ! 1:  8b1a5cc055 last-modified: implement faster algorithm
    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus
      }

     +/*
    -+ * Hold a bitmap for each commit we're working with. Each bit represents a path
    -+ * in `lm->all_paths`. Active bit means the path still needs to be dealt with.
    ++ * Hold a bitmap for each commit we're working with. In the bitmap, each bit
    ++ * represents a path in `lm->all_paths`. An active bit indicates the path still
    ++ * needs to be associated to a commit.
     + */
    -+define_commit_slab(commit_bitmaps, struct bitmap *);
    ++define_commit_slab(active_paths_for_commit, struct bitmap *);
     +
      struct last_modified {
      	struct hashmap paths;
    @@ builtin/last-modified.c: static int last_modified_entry_hashcmp(const void *unus
     +
     +	const char **all_paths;
     +	size_t all_paths_nr;
    -+	struct commit_bitmaps active_paths_bitmap;
    ++	struct active_paths_for_commit active_paths;
     +
    -+	/* 'scratch' bitmap to avoid allocating every proccess_parent() */
    ++	/* 'scratch' to avoid allocating a bitmap every process_parent() */
     +	struct bitmap *scratch;
      };

    -+static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)
    ++static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
     +{
    -+	struct bitmap **bitmap = commit_bitmaps_at(&lm->active_paths_bitmap, c);
    ++	struct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);
     +	if (!*bitmap)
    -+		*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);
    ++		*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD + 1);
     +
     +	return *bitmap;
     +}
    ++
    ++static void active_paths_free(struct last_modified *lm, struct commit *c)
    ++{
    ++	struct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);
    ++	if (*bitmap) {
    ++		bitmap_free(*bitmap);
    ++		*bitmap = NULL;
    ++	}
    ++}
     +
      static void last_modified_release(struct last_modified *lm)
      {
    @@ builtin/last-modified.c: static void last_modified_diff(struct diff_queue_struct
      }

     -static bool maybe_changed_path(struct last_modified *lm, struct commit *origin)
    -+static size_t path_idx(struct last_modified *lm, char *path)
    -+{
    -+	struct last_modified_entry *ent;
    -+	ent = hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,
    -+					  struct last_modified_entry, hashent);
    -+
    -+	return ent ? ent->diff_idx : -1;
    -+}
    -+
    -+static void pass_to_parent(struct last_modified *lm,
    -+			   struct bitmap *c,
    ++static void pass_to_parent(struct bitmap *c,
     +			   struct bitmap *p,
     +			   size_t pos)
     +{
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +			   struct commit *c, struct bitmap *active_c,
     +			   struct commit *parent, int parent_i)
     +{
    -+	size_t i;
     +	struct bitmap *active_p;
     +
     +	repo_parse_commit(lm->rev.repo, parent);
    -+	active_p = get_bitmap(lm, parent);
    ++	active_p = active_paths_for(lm, parent);
     +
     +	/*
     +	 * The first time entering this function for this commit (i.e. first parent)
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +	 * First, collect all paths that are *not* TREESAME in 'scratch'.
     +	 * Then, pass paths that *are* TREESAME and active to the parent.
     +	 */
    -+	for (i = 0; i < diff_queued_diff.nr; i++) {
    ++	for (int i = 0; i < diff_queued_diff.nr; i++) {
     +		struct diff_filepair *fp = diff_queued_diff.queue[i];
    -+		size_t k = path_idx(lm, fp->two->path);
    -+		if (0 <= k && bitmap_get(active_c, k))
    -+			bitmap_set(lm->scratch, k);
    ++		const char *path = fp->two->path;
    ++		struct last_modified_entry *ent =
    ++			hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,
    ++						    struct last_modified_entry, hashent);
    ++		if (ent) {
    ++			size_t k = ent->diff_idx;
    ++			if (bitmap_get(active_c, k))
    ++				bitmap_set(lm->scratch, k);
    ++		}
     +	}
    -+	for (i = 0; i < lm->all_paths_nr; i++) {
    ++	for (size_t i = 0; i < lm->all_paths_nr; i++) {
     +		if (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))
    -+			pass_to_parent(lm, active_c, active_p, i);
    ++			pass_to_parent(active_c, active_p, i);
     +	}
     +
     +	/*
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +		parent->object.flags |= PARENT1;
     +		prio_queue_put(queue, parent);
     +	}
    ++	if (!(parent->object.flags & PARENT1))
    ++		active_paths_free(lm, parent);
     +
     +	memset(lm->scratch->words, 0x0, lm->scratch->word_alloc);
     +	diff_queue_clear(&diff_queued_diff);
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     -			BUG("paths remaining beyond boundary in last-modified");
     +	max_count = lm->rev.max_count;
     +
    -+	init_commit_bitmaps(&lm->active_paths_bitmap);
    ++	init_active_paths_for_commit(&lm->active_paths);
     +	lm->scratch = bitmap_word_alloc(lm->all_paths_nr);
     +
     +	/*
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +			prio_queue_put(&queue, c);
     +			c->object.flags |= PARENT1;
     +
    -+			active = get_bitmap(lm, c);
    ++			active = active_paths_for(lm, c);
     +			for (size_t i = 0; i < lm->all_paths_nr; i++)
     +				bitmap_set(active, i);
     +		}
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +		int parent_i;
     +		struct commit_list *p;
     +		struct commit *c = prio_queue_get(&queue);
    -+		struct bitmap *active_c = get_bitmap(lm, c);
    ++		struct bitmap *active_c = active_paths_for(lm, c);
     +
     +		if ((0 <= max_count && max_count < ++queue_popped) ||
     +		    (c->object.flags & PARENT2)) {
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm

     -		log_tree_commit(&lm->rev, data.commit);
     +cleanup:
    -+		bitmap_free(active_c);
    ++		active_paths_free(lm, c);
      	}

     +	if (hashmap_get_size(&lm->paths))
    @@ builtin/last-modified.c: static bool maybe_changed_path(struct last_modified *lm
     +
     +	clear_prio_queue(&not_queue);
     +	clear_prio_queue(&queue);
    -+	clear_commit_bitmaps(&lm->active_paths_bitmap);
    ++	clear_active_paths_for_commit(&lm->active_paths);
     +	bitmap_free(lm->scratch);
     +
      	return 0;
---
 builtin/last-modified.c  | 250 ++++++++++++++++++++++++++++++++++++++++++++---
 object.h                 |   1 +
 t/t8020-last-modified.sh |   2 +-
 3 files changed, 237 insertions(+), 16 deletions(-)