From fbc08ea177f8284d10c62ad39de51edb21af88b0 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= <rene.scharfe@lsrfire.ath.cx>
Date: Sun, 1 Apr 2012 00:11:01 +0200
Subject: revision: insert unsorted, then sort in prepare_revision_walk()

Speed up prepare_revision_walk() by adding commits without sorting
to the commit_list and at the end sort the list in one go.  Thanks
to mergesort() working behind the scenes, this is a lot faster for
large numbers of commits than the current insert sort.

Also introduce and use commit_list_reverse(), to keep the ordering
of commits sharing the same commit date unchanged.  That's because
commit_list_insert_by_date() sorts commits with descending date,
but adds later entries with the same date entries last, while
commit_list_insert() always inserts entries at the top.  The
following commit_list_sort_by_date() keeps the order of entries
sharing the same date.

Jeff's test case, in a repo with lots of refs, was to run:

  # make a new commit on top of HEAD, but not yet referenced
  sha1=`git commit-tree HEAD^{tree} -p HEAD </dev/null`

  # now do the same "connected" test that receive-pack would do
  git rev-list --objects $sha1 --not --all

With a git.git with a ref for each revision, master needs (best of
five):

	real	0m2.210s
	user	0m2.188s
	sys	0m0.016s

And with this patch:

	real	0m0.480s
	user	0m0.456s
	sys	0m0.020s

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 revision.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

(limited to 'revision.c')

diff --git a/revision.c b/revision.c
index 064e351084..a75a1d7201 100644
--- a/revision.c
+++ b/revision.c
@@ -2054,11 +2054,13 @@ int prepare_revision_walk(struct rev_info *revs)
 		if (commit) {
 			if (!(commit->object.flags & SEEN)) {
 				commit->object.flags |= SEEN;
-				commit_list_insert_by_date(commit, &revs->commits);
+				commit_list_insert(commit, &revs->commits);
 			}
 		}
 		e++;
 	}
+	commit_list_reverse(&revs->commits);
+	commit_list_sort_by_date(&revs->commits);
 	if (!revs->leak_pending)
 		free(list);
 
-- 
cgit v1.2.1