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>

diff --git a/commit.c b/commit.c
index b9ce569442cdaf6fc401901427bfac5727f9739a..0759b2ca655d8d5839fe46cba477135414d0826c 100644 (file)
--- a/commit.c
+++ b/commit.c
@@ -361,6 +361,21 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
        return new_list;
 }
 
+void commit_list_reverse(struct commit_list **list_p)
+{
+       struct commit_list *prev = NULL, *curr = *list_p, *next;
+
+       if (!list_p)
+               return;
+       while (curr) {
+               next = curr->next;
+               curr->next = prev;
+               prev = curr;
+               curr = next;
+       }
+       *list_p = prev;
+}
+
 unsigned commit_list_count(const struct commit_list *l)
 {
        unsigned c = 0;

diff --git a/commit.h b/commit.h
index 154c0e34ff7d2dbaddcfb66b74d26697ffba6381..f8d250d6f64cacf463d7fd9525759978f008bcca 100644 (file)
--- a/commit.h
+++ b/commit.h
@@ -57,6 +57,7 @@ unsigned commit_list_count(const struct commit_list *l);
 struct commit_list *commit_list_insert_by_date(struct commit *item,
                                    struct commit_list **list);
 void commit_list_sort_by_date(struct commit_list **list);
+void commit_list_reverse(struct commit_list **list_p);
 
 void free_commit_list(struct commit_list *list);
 

diff --git a/revision.c b/revision.c
index 064e35108478431e82ec08464203fe119f24c1d6..a75a1d7201ea6e4ea26fa95665a24b2716bb07d0 100644 (file)
--- 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);