Re: git pull takes ~8 seconds on up-to-date Linux git tree

From: Junio C Hamano <gitster@pobox.com>
Date: Oct 5, 2012, 20:34 UTC
Message-ID: <7vehlcu091.fsf@alter.siamese.dyndns.org>
In-Reply-To: <7vmx01x3s4.fsf@alter.siamese.dyndns.org>

Junio C Hamano <gitster@pobox.com> writes:

Show 6 quoted lines

> Here is a tested (in the sense that it passes the test suite, and
> also in the sense that an empty pull in the kernel history gives
> quick turnaround) patch.  As I do not think we would want to revert
> 5802f81 (fmt-merge-msg: discard needless merge parents, 2012-04-18)
> which was a correctness fix, I think we would rather want to do
> something like this.

OK, I think I am convinced myself that this patch is the right fix.

The performance regression Markus saw is in fmt-merge-message, and it is caused by the updated remove_redundant() that is used by get_merge_bases_many() and reduce_heads(). On the topic branch, all callers of reduce_heads() were passing commits that are already parsed, but before the topic was merged to 'master', we added one more caller to reduce_heads() on the 'master' front that passed an unparsed commit, which is why the problem surfaced at that merge.

It might make sense to assert or die in commit_list_insert_by_date() when a caller mistakenly pass an unparsed commit object to prevent this kind of breakages in the future.

Show 47 quoted lines

> -- >8 --
> Subject: paint_down_to_common(): parse commit before relying on its timestamp
>
> When refactoring the merge-base computation to reduce the pairwise
> O(n*(n-1)) traversals to parallel O(n) traversals, the code forgot
> that timestamp based heuristics needs each commit to have been
> parsed.  This caused an empty "git pull" to spend cycles, traversing
> the history all the way down to 0 (because an unparsed commit object
> has 0 timestamp, and any other commit object with positive timestamp
> will be processed for its parents, all getting parsed), only to come
> up with a merge message to be used.
>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
>  commit.c | 5 +++++
>  1 file changed, 5 insertions(+)
>
> diff --git i/commit.c w/commit.c
> index 0246767..213bc98 100644
> --- i/commit.c
> +++ w/commit.c
> @@ -609,6 +609,7 @@ static struct commit *interesting(struct commit_list *list)
>  	return NULL;
>  }
>  
> +/* all input commits in one and twos[] must have been parsed! */
>  static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
>  {
>  	struct commit_list *list = NULL;
> @@ -617,6 +618,8 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
>  
>  	one->object.flags |= PARENT1;
>  	commit_list_insert_by_date(one, &list);
> +	if (!n)
> +		return list;
>  	for (i = 0; i < n; i++) {
>  		twos[i]->object.flags |= PARENT2;
>  		commit_list_insert_by_date(twos[i], &list);
> @@ -737,6 +740,8 @@ static int remove_redundant(struct commit **array, int cnt)
>  	redundant = xcalloc(cnt, 1);
>  	filled_index = xmalloc(sizeof(*filled_index) * (cnt - 1));
>  
> +	for (i = 0; i < cnt; i++)
> +		parse_commit(array[i]);
>  	for (i = 0; i < cnt; i++) {
>  		struct commit_list *common;
>