Re: [PATCH] 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.
> 

>     $ 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: Taylor Blau <me@ttaylorr.com>
> Signed-off-by: Toon Claes <toon@iotcl.com>
> ---

> diff --git a/builtin/last-modified.c b/builtin/last-modified.c
> index ae8b36a2c3..40e520ba18 100644
> --- a/builtin/last-modified.c
> +++ b/builtin/last-modified.c
> @@ -2,26 +2,32 @@
>  #include "bloom.h"
>  #include "builtin.h"
>  #include "commit-graph.h"
> +#include "commit-slab.h"
>  #include "commit.h"
>  #include "config.h"
> -#include "environment.h"
>  #include "diff.h"
>  #include "diffcore.h"
>  #include "environment.h"
> +#include "ewah/ewok.h"
>  #include "hashmap.h"
>  #include "hex.h"
> -#include "log-tree.h"
>  #include "object-name.h"
>  #include "object.h"
>  #include "parse-options.h"
> +#include "prio-queue.h"
>  #include "quote.h"
>  #include "repository.h"
>  #include "revision.h"
>  
> +/* Remember to update object flag allocation in object.h */

> +
>  struct last_modified_entry {
>  	struct hashmap_entry hashent;
>  	struct object_id oid;
>  	struct bloom_key key;
> +	size_t diff_idx;
>  	const char path[FLEX_ARRAY];
>  };
>  
> @@ -37,13 +43,35 @@ static int last_modified_entry_hashcmp(const void *unused UNUSED,
>  	return strcmp(ent1->path, path ? path : ent2->path);
>  }
>  
> +/*
> + * 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.
> + */
> +define_commit_slab(commit_bitmaps, struct bitmap *);

>  struct last_modified {
>  	struct hashmap paths;
>  	struct rev_info rev;
>  	bool recursive;
>  	bool show_trees;
> +
> +	const char **all_paths;
> +	size_t all_paths_nr;

> +	struct commit_bitmaps commit_bitmaps;
> +
> +	/* 'scratch' bitmap to avoid allocating every proccess_parent() */
> +	struct bitmap *scratch;
>  };
>  
> +static struct bitmap *get_bitmap(struct last_modified *lm, struct commit *c)
> +{
> +	struct bitmap **bitmap = commit_bitmaps_at(&lm->commit_bitmaps, c);
> +	if (!*bitmap)
> +		*bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD);
> +
> +	return *bitmap;
> +}
> +
>  static void last_modified_release(struct last_modified *lm)
>  {
>  	struct hashmap_iter iter;

>  static int last_modified_run(struct last_modified *lm)
>  {
> +	int max_count, queue_popped = 0;
> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
> +	struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
> +	struct commit_list *list;
>  	struct last_modified_callback_data data = { .lm = lm };
>  
>  	lm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;
>  	lm->rev.diffopt.format_callback = last_modified_diff;
>  	lm->rev.diffopt.format_callback_data = &data;
> +	lm->rev.no_walk = 1;
>  
>  	prepare_revision_walk(&lm->rev);
>  
> -	while (hashmap_get_size(&lm->paths)) {
> -		data.commit = get_revision(&lm->rev);
> -		if (!data.commit)
> -			BUG("paths remaining beyond boundary in last-modified");
> +	max_count = lm->rev.max_count;
> +
> +	init_commit_bitmaps(&lm->commit_bitmaps);
> +	lm->scratch = bitmap_word_alloc(lm->all_paths_nr);

> +	 *
> +	 * Loop through each such commit, and place it in the appropriate queue.
> +	 */
> +	for (list = lm->rev.commits; list; list = list->next) {
> +		struct commit *c = list->item;
> +
> +		if (c->object.flags & BOTTOM) {
> +			prio_queue_put(&not_queue, c);

> +			/*
> +			 * If the commit is a starting point (and hasn't been
> +			 * seen yet), then initialize the set of interesting
> +			 * paths, too.
> +			 */
> +			struct bitmap *active;
> +
> +			prio_queue_put(&queue, c);
> +			c->object.flags |= PARENT1;

> +		}
> +	}
> +
> +	while (queue.nr) {
> +		int parent_i;
> +		struct commit_list *p;
> +		struct commit *c = prio_queue_get(&queue);
> +		struct bitmap *active_c = get_bitmap(lm, c);
> +
> +		if ((0 <= max_count && max_count < ++queue_popped) ||
> +		    (c->object.flags & PARENT2)) {
> +			/*
> +			 * Either a boundary commit, or we have already seen too
> +			 * many others. Either way, stop here.
> +			 */
> +			c->object.flags |= PARENT2 | BOUNDARY;
> +			data.commit = c;
>  			diff_tree_oid(lm->rev.repo->hash_algo->empty_tree,
> -				      &data.commit->object.oid, "",
> -				      &lm->rev.diffopt);
> +				      &c->object.oid,
> +				      "", &lm->rev.diffopt);
>  			diff_flush(&lm->rev.diffopt);
> +			goto cleanup;
> +		}
>  
> -			break;
> +		/*
> +		 * Otherwise, make sure that 'c' isn't reachable from anything
> +		 * in the '--not' queue.
> +		 */
> +		repo_parse_commit(lm->rev.repo, c);
> +
> +		while (not_queue.nr) {
> +			struct commit_list *np;
> +			struct commit *n = prio_queue_get(&not_queue);
> +
> +			repo_parse_commit(lm->rev.repo, n);
> +
> +			for (np = n->parents; np; np = np->next) {
> +				if (!(np->item->object.flags & PARENT2)) {
> +					prio_queue_put(&not_queue, np->item);
> +					np->item->object.flags |= PARENT2;
> +				}
> +			}
> +
> +			if (commit_graph_generation(n) < commit_graph_generation(c))
> +				break;

>  		}
>  
> -		if (!maybe_changed_path(lm, data.commit))
> -			continue;
> +		/*
> +		 * Look at each parent and pass on each path that's TREESAME
> +		 * with that parent. Stop early when no active paths remain.
> +		 */
> +		for (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {
> +			process_parent(lm, &queue,
> +				       c, active_c,
> +				       p->item, parent_i);
> +
> +			if (bitmap_is_empty(active_c))
> +				break;
> +		}
>  
> -		log_tree_commit(&lm->rev, data.commit);
> +		/*
> +		 * Paths that remain active, or not TREESAME with any parent,
> +		 * were changed by 'c'.
> +		 */
> +		if (!bitmap_is_empty(active_c))  {
> +			data.commit = c;
> +			for (size_t i = 0; i < lm->all_paths_nr; i++) {
> +				if (bitmap_get(active_c, i))
> +					mark_path(lm->all_paths[i], NULL, &data);
> +			}
> +		}
> +
> +cleanup:
> +		bitmap_free(active_c);
>  	}
>  
> +	if (hashmap_get_size(&lm->paths))
> +		BUG("paths remaining beyond boundary in last-modified");
> +
> +	clear_prio_queue(&not_queue);
> +	clear_prio_queue(&queue);
> +	clear_commit_bitmaps(&lm->commit_bitmaps);
> +	bitmap_free(lm->scratch);
> +
>  	return 0;
>  }