Re: [PATCH] last-modified: implement faster algorithm

> Ok so if I understand correctly, the optimization here is that as we
> perform the revision walk, the set of paths we look for at each commit
> monotonically decreases as changed paths are identified. Prior to this,
> we were always checking all paths for each commit even though a path may
> have already found the commit that last modified it.

> [snip]
>> As an added benefit, this implementation gives more correct results. For
>> example implementation in 'master' gives:
>
> s/implementation/the implementation/

>> +#define PARENT1 (1u<<16) /* used instead of SEEN */
>> +#define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */
>
> Naive question: why do we use these object flags instead of the ones
> mentioned?

>> +
>>  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 *);
>
> Why do we need a path bitmap for each commit? My understanding is that
> we check commits in a certain order as dictated by the priority queue.
> As soon as the commit that last-modified a path has been identified,
> wouldn't we always want the remaining commits processed to only check
> the outstanding paths?

>>  struct last_modified {
>>  	struct hashmap paths;
>>  	struct rev_info rev;
>>  	bool recursive;
>>  	bool show_trees;
>> +
>> +	const char **all_paths;
>> +	size_t all_paths_nr;
>
> It is not immediately obvious to me why we have both `paths` and
> `all_paths`. From my understanding, `all_paths` is defining the path
> order for the bitmap. If this is the case, maybe it would be worth
> explaining in a comment?

> [snip]
>>  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);
>
> It looks like we initialize and release both `commit_bitmaps` and
> `scratch` here in `last_modified_run()`. Any reason we wouldn't want to
> move this to `last_modified_{init,release}()`?

>> +
>> +	/*
>> +	 * lm->rev.commits holds the set of boundary commits for our walk.
>
> Naive question: would it be more correct ...

>> +	 *
>> +	 * 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);
>
> Ok so commits with the BOTTOM flag are at the boundary of the
> "interesting" commit graph. Thus they are not included in the search and
> added to the "not_queue".
>
>> +			c->object.flags |= PARENT2;
>
> What is the meaning behind the name PARENT2 in this context? From my
> understanding we are using this flag to denote a commit we are not
> interested in.

>
>> +		} else if (!(c->object.flags & PARENT1)) {
>
> Same question about PARENT1. It seems to be used to just denote commits
> that we have already encountered. The names confuse me a bit though.

>> +			/*
>> +			 * 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;
>
> We queue the commit and mark it as seen. Makes sense.
>
>> -		if (data.commit->object.flags & BOUNDARY) {
>> +			active = get_bitmap(lm, c);
>> +			for (size_t i = 0; i < lm->all_paths_nr; i++)
>> +				bitmap_set(active, i);
>
> Here we set up the path bitmap for the commit. At this point, all paths
> are still "active" and thus set accordingly. I'm still not entirely sure
> though if we really need a path bitmap per commit.

>> +		}
>> +	}
>> +
>> +	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 the generation number of 'c' is higher than 'n' we know 'c' cannot be
> an ancestor of 'n' and thus we continue on. Makes sense.

>>  		}
>>  
>> -		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;
>>  }
> [snip]
>
> I've taken an initial look a this patch and have mostly questions so
> far. Just FYI, after applying this patch locally, the last-modified
> tests seem to be failing. The command seems to be segfaulting, but I
> haven't looked into it further.