Git push performance problems with ~100K refs

Git push performance problems with ~100K refs

[Martin Fick]

Hello,

I am back to talk about git performance with lots of refs: 
~100K.  This time I am investigating pushes to a repo with 
about ~100K ref, a gerrit mirror which includes the gerrit 
changes.  When I push just a simple one line change to a 
file, the push takes about ~43s.  If I delete the changes
from the destination repo, this push takes about 6s.  This 
seems rather excessive to me, in fact given that the repo 
with 100K refs has more data in it and is more likely to 
have the objects I am pushing in it, if things are done 
right, it should be a faster push (in theory).

So, upon early investigation, I noticed that the time to 
push seems mostly determined by the receiving end which is 
processing all out for 100% on a CPU.  During this time 
period, the receiving end git commands look like this:

  git-receive-pack path/to/repo.git

and:

  git rev-list --objects --stdin --not --all

The latter of these two commands is the one burning CPU.

Does anyone have any hints as to what might be wrong with 
the receiving end algorithm that would cause a small change 
to use so much CPU?  Is there anything that can be done 
about it?  I noticed that the --all option will effectively 
feed  all the 100K refs to rev-list, is this really 
necessary?  Are there any tests that I can perform to help 
debug this?

I am using git 1.7.8.3 and I also tried 1.7.10.rc3, same 
results.

Thanks,

-Martin


-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum

Re: Git push performance problems with ~100K refs

[Junio C Hamano]

Martin Fick <mfick@codeaurora.org> writes:

> Does anyone have any hints as to what might be wrong with 
> the receiving end algorithm that would cause a small change 
> to use so much CPU?  Is there anything that can be done 
> about it?  I noticed that the --all option will effectively 
> feed all the 100K refs to rev-list, is this really 
> necessary?

It is trying to minimize the transfer cost.  By showing a ref to the
sending side, you prove you have chains of commits leading to that commit
and the sender knows that it does not have to send objects that are
reachable from that ref. One thing you could immediately do is de-dup the
100k refs but we may already do that in the current code.

> Are there any tests that I can perform to help 
> debug this?

You do not need to "help debug" it.  It's cause is already known: the
receiver exposes too many refs to the sending side.

We've talked about possible solutions but no concrete design nor code is
there yet.

Re: Git push performance problems with ~100K refs

[Martin Fick]

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

>Martin Fick <mfick@codeaurora.org> writes:
>
>> Does anyone have any hints as to what might be wrong with 
>> the receiving end algorithm that would cause a small change 
>> to use so much CPU?  Is there anything that can be done 
>> about it?  I noticed that the --all option will effectively 
>> feed all the 100K refs to rev-list, is this really 
>> necessary?
>
>It is trying to minimize the transfer cost.  By showing a ref to the
>sending side, you prove you have chains of commits leading to that
>commit
>and the sender knows that it does not have to send objects that are
>reachable from that ref. One thing you could immediately do is de-dup
>the
>100k refs but we may already do that in the current code.

I am sorry I don't quite understand what you are suggesting is taking up the CPU time?  It doesn't take that much CPU just to gather 100refs and send them to the other side, that would be i/o bound.  Could you explain what is happening on the receiving side that is so time consuming?

>> Are there any tests that I can perform to help 
>> debug this?
>
>You do not need to "help debug" it.  It's cause is already known: the
>receiver exposes too many refs to the sending side.

But wouldn't that cause excessive CPU for the sending side?  It did with jgit, but that can be remedied with a simple jgit fix.

Thanks for your insights,

-Martin

Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum

Re: Git push performance problems with ~100K refs

[Jeff King]

On Thu, Mar 29, 2012 at 08:43:06PM -0600, Martin Fick wrote:

> >It is trying to minimize the transfer cost.  By showing a ref to the
> >sending side, you prove you have chains of commits leading to that
> >commit
> >and the sender knows that it does not have to send objects that are
> >reachable from that ref. One thing you could immediately do is de-dup
> >the
> >100k refs but we may already do that in the current code.
> 
> I am sorry I don't quite understand what you are suggesting is taking
> up the CPU time?  It doesn't take that much CPU just to gather 100refs
> and send them to the other side, that would be i/o bound.  Could you
> explain what is happening on the receiving side that is so time
> consuming?

You said earlier that it is "git rev-list --objects --stdin --not --all"
taking up all the CPU. That is probably called by
check_everything_connected. And that is why it is slow when you push
even a small change, but fast when you push only a deletion (in the
latter case, we skip the check because there are no new objects).

As for why that rev-list is slow, my suspicion is that it may be
quadratic behavior in commit_list_insert_by_date as we process the set
of negative refs. Basically, we keep a priority queue of commits to be
processed in our graph walk, but the queue is stored as a linked list.
So insertion is O(n), and building a list of n items (especially if they
are not in sorted order) is O(n^2).

I've run into this before dealing with repos with many refs (at GitHub,
some of our alternates repositories hit 100K refs, although typically we
have a lot of duplicated refs, as we are storing identical tags from
many repositories).

But that's just a suspicion. I don't have time tonight to work out a
test case. Is it possible for you to run something like:

  # 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

That should replicate the slow behavior you are seeing. If that works,
try running the latter command under "perf"; my guess is that you will
see commit_list_insert_by_date as a hot-spot.

Even doing this simple test on a moderate repository (my git.git has
~1100 refs), commit_list_insert_by_date accounts for 10% of the CPU
according to perf.

-Peff

Re: Git push performance problems with ~100K refs

[Jeff King]

On Fri, Mar 30, 2012 at 05:32:08AM -0400, Jeff King wrote:

> But that's just a suspicion. I don't have time tonight to work out a
> test case. Is it possible for you to run something like:
> 
>   # 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
> 
> That should replicate the slow behavior you are seeing. If that works,
> try running the latter command under "perf"; my guess is that you will
> see commit_list_insert_by_date as a hot-spot.
> 
> Even doing this simple test on a moderate repository (my git.git has
> ~1100 refs), commit_list_insert_by_date accounts for 10% of the CPU
> according to perf.

Actually, I did have time for a simple test. Doing:

  git rev-list HEAD |
  while read sha1; do
    echo $sha1 refs/heads/$sha1
  done >>packed-refs
  git pack-refs

in git.git slows down the test above considerably, and perf reports 90%
of the time spent in commit_list_insert_by_date. So I think that is
indeed the problem.

At one point, I looked at replacing the commit_list implementation with
a heap-based priority queue, but unfortunately many parts of the code
depend on the list-like nature and would need to be rewritten. We might
be able to hack around it by at least adding all of the initial items to
an unordered list, then sorting it into its final form.

-Peff

Re: Git push performance problems with ~100K refs

[Martin Fick]

Jeff King <peff@peff.net> wrote:
>
>Actually, I did have time for a simple test. Doing:
>
>  git rev-list HEAD |
>  while read sha1; do
>    echo $sha1 refs/heads/$sha1
>  done >>packed-refs
>  git pack-refs
>
>in git.git slows down the test above considerably, and perf reports 90%
>of the time spent in commit_list_insert_by_date. So I think that is
>indeed the problem.
>
>At one point, I looked at replacing the commit_list implementation with
>a heap-based priority queue, but unfortunately many parts of the code
>depend on the list-like nature and would need to be rewritten. We might
>be able to hack around it by at least adding all of the initial items
>to
>an unordered list, then sorting it into its final form.

Thanks Peff for the explanation.  Jgit actually has the exact same problem, it slows down the pushing side.  Fortunately, in jgit it is well isolated and can easily be remedied by both the solutions you mention, and both work to speed it (jgit) up drastically!  I wonder if libgit2 suffers from the same problem?

This might be one of the last pieces to git ref scalability left?  Does this affect many other use cases, fetches?

-Martin


Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum

[PATCH 1/3] add mergesort() for linked lists

[René Scharfe]

This adds a generic bottom-up mergesort implementation for singly linked
lists.  It was inspired by Simon Tatham's webpage on the topic[1], but
not so much by his implementation -- for no good reason, really, just a
case of NIH.

[1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
As you can guess from the patch, I just love function pointers. :)  It
may be interesting to know how much overhead they add, but in the test
case you described (a ref for each revision of git.git) the call to
mergesort (wired up in patch 3) only contributes less than 1% of the cost
according to callgrind, including its callees.

WARNING!  This is fresh code, and while the algorithm is simple, it's
possible that I was still somehow able to sneak in a bug.

 .gitignore       |    1 +
 Makefile         |    3 +++
 mergesort.c      |   75 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 mergesort.h      |    9 +++++++
 test-mergesort.c |   52 +++++++++++++++++++++++++++++++++++++
 5 files changed, 140 insertions(+)
 create mode 100644 mergesort.c
 create mode 100644 mergesort.h
 create mode 100644 test-mergesort.c

diff --git a/.gitignore b/.gitignore
index 87fcc5f..225656a 100644
--- a/.gitignore
+++ b/.gitignore
@@ -180,6 +180,7 @@
 /test-index-version
 /test-line-buffer
 /test-match-trees
+/test-mergesort
 /test-mktemp
 /test-parse-options
 /test-path-utils
diff --git a/Makefile b/Makefile
index be1957a..b04d6ec 100644
--- a/Makefile
+++ b/Makefile
@@ -480,6 +480,7 @@ TEST_PROGRAMS_NEED_X += test-genrandom
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-line-buffer
 TEST_PROGRAMS_NEED_X += test-match-trees
+TEST_PROGRAMS_NEED_X += test-mergesort
 TEST_PROGRAMS_NEED_X += test-mktemp
 TEST_PROGRAMS_NEED_X += test-parse-options
 TEST_PROGRAMS_NEED_X += test-path-utils
@@ -590,6 +591,7 @@ LIB_H += log-tree.h
 LIB_H += mailmap.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
+LIB_H += mergesort.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
@@ -694,6 +696,7 @@ LIB_OBJS += mailmap.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
+LIB_OBJS += mergesort.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
diff --git a/mergesort.c b/mergesort.c
new file mode 100644
index 0000000..c0f1874
--- /dev/null
+++ b/mergesort.c
@@ -0,0 +1,75 @@
+#include "cache.h"
+#include "mergesort.h"
+
+#include "commit.h"
+
+struct mergesort_sublist {
+	void *ptr;
+	unsigned long len;
+};
+
+static void *get_nth_next(void *list, unsigned long n,
+			  void *(*get_next_fn)(const void *))
+{
+	while (n-- && list)
+		list = get_next_fn(list);
+	return list;
+}
+
+static void *pop_item(struct mergesort_sublist *l,
+		      void *(*get_next_fn)(const void *))
+{
+	void *p = l->ptr;
+	l->ptr = get_next_fn(l->ptr);
+	l->len = l->ptr ? (l->len - 1) : 0;
+	return p;
+}
+
+void *mergesort(void *list,
+		void *(*get_next_fn)(const void *),
+		void (*set_next_fn)(void *, void *),
+		int (*compare_fn)(const void *, const void *))
+{
+	unsigned long l;
+
+	if (!list)
+		return NULL;
+	for (l = 1; ; l *= 2) {
+		void *curr;
+		struct mergesort_sublist p, q;
+
+		p.ptr = list;
+		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+		if (!q.ptr)
+			break;
+		p.len = q.len = l;
+
+		if (compare_fn(p.ptr, q.ptr) > 0)
+			list = curr = pop_item(&q, get_next_fn);
+		else
+			list = curr = pop_item(&p, get_next_fn);
+
+		while (p.ptr) {
+			while (p.len || q.len) {
+				void *prev = curr;
+
+				if (!p.len)
+					curr = pop_item(&q, get_next_fn);
+				else if (!q.len)
+					curr = pop_item(&p, get_next_fn);
+				else if (compare_fn(p.ptr, q.ptr) > 0)
+					curr = pop_item(&q, get_next_fn);
+				else
+					curr = pop_item(&p, get_next_fn);
+				set_next_fn(prev, curr);
+			}
+			p.ptr = q.ptr;
+			p.len = l;
+			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+			q.len = q.ptr ? l : 0;
+
+		}
+		set_next_fn(curr, NULL);
+	}
+	return list;
+}
diff --git a/mergesort.h b/mergesort.h
new file mode 100644
index 0000000..d6e5f4a
--- /dev/null
+++ b/mergesort.h
@@ -0,0 +1,9 @@
+#ifndef MERGESORT_H
+#define MERGESORT_H
+
+void *mergesort(void *list,
+		void *(*get_next_fn)(const void *),
+		void (*set_next_fn)(void *, void *),
+		int (*compare_fn)(const void *, const void *));
+
+#endif
diff --git a/test-mergesort.c b/test-mergesort.c
new file mode 100644
index 0000000..02441ab
--- /dev/null
+++ b/test-mergesort.c
@@ -0,0 +1,52 @@
+#include "cache.h"
+#include "mergesort.h"
+
+struct line {
+	char *text;
+	struct line *next;
+};
+
+static void *get_next(const void *a)
+{
+	return ((const struct line *)a)->next;
+}
+
+static void set_next(void *a, void *b)
+{
+	((struct line *)a)->next = b;
+}
+
+static int compare_strings(const void *a, const void *b)
+{
+	const struct line *x = a, *y = b;
+	return strcmp(x->text, y->text);
+}
+
+int main(int argc, const char **argv)
+{
+	struct line *line, *p = NULL, *lines = NULL;
+	struct strbuf sb = STRBUF_INIT;
+
+	for (;;) {
+		if (strbuf_getwholeline_fd(&sb, 0, '\n'))
+			break;
+		line = xmalloc(sizeof(struct line));
+		line->text = strbuf_detach(&sb, NULL);
+		if (p) {
+			line->next = p->next;
+			p->next = line;
+		} else {
+			line->next = NULL;
+			lines = line;
+		}
+		p = line;
+	}
+
+	lines = mergesort(lines, get_next, set_next, compare_strings);
+
+	while (lines) {
+		printf("%s", lines->text);
+		lines = lines->next;
+	}
+	return 0;
+}
-- 
1.7.9.2

[PATCH 2/3] commit: use mergesort() in commit_list_sort_by_date()

[René Scharfe]

Replace the insertion sort in commit_list_sort_by_date() with a
call to the generic mergesort function.  This sets the stage for
using commit_list_sort_by_date() for larger lists, as shown in
the next patch.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
---
 commit.c |   29 +++++++++++++++++++++++------
 1 file changed, 23 insertions(+), 6 deletions(-)

diff --git a/commit.c b/commit.c
index 4b39c19..0d0c424 100644
--- a/commit.c
+++ b/commit.c
@@ -7,6 +7,7 @@
 #include "revision.h"
 #include "notes.h"
 #include "gpg-interface.h"
+#include "mergesort.h"
 
 int save_commit_buffer = 1;
 
@@ -390,15 +391,31 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm
 	return commit_list_insert(item, pp);
 }
 
+static int commit_list_compare_by_date(const void *a, const void *b)
+{
+	unsigned long a_date = ((const struct commit_list *)a)->item->date;
+	unsigned long b_date = ((const struct commit_list *)b)->item->date;
+	if (a_date < b_date)
+		return 1;
+	if (a_date > b_date)
+		return -1;
+	return 0;
+}
+
+static void *commit_list_get_next(const void *a)
+{
+	return ((const struct commit_list *)a)->next;
+}
+
+static void commit_list_set_next(void *a, void *next)
+{
+	((struct commit_list *)a)->next = next;
+}
 
 void commit_list_sort_by_date(struct commit_list **list)
 {
-	struct commit_list *ret = NULL;
-	while (*list) {
-		commit_list_insert_by_date((*list)->item, &ret);
-		*list = (*list)->next;
-	}
-	*list = ret;
+	*list = mergesort(*list, commit_list_get_next, commit_list_set_next,
+			  commit_list_compare_by_date);
 }
 
 struct commit *pop_most_recent_commit(struct commit_list **list,
-- 
1.7.9.2

[PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[René Scharfe]

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>
---
 commit.c   |   15 +++++++++++++++
 commit.h   |    1 +
 revision.c |    4 +++-
 3 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/commit.c b/commit.c
index 0d0c424..5ebbda0 100644
--- 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 154c0e3..f8d250d 100644
--- 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 b3554ed..92095f5 100644
--- a/revision.c
+++ b/revision.c
@@ -2076,11 +2076,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);
 
-- 
1.7.9.2

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Martin Fick]

"René Scharfe" <rene.scharfe@lsrfire.ath.cx> wrote:

>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.

Thanks for these René, I will see if I can try them out on Monday!

-Martin

Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

> 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.

This is one of these moments I am reminded why I am grateful to have you
in the community.  The first message from you in a topic that needs to
touch a quite core part of the system often is not a participation in the
discussion, but is a solution that is already well crafted.

Thanks, will queue.

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Martin Fick]

On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote:
> 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.

This speeds up my git push test on my repo with ~100K refs 
case from out ~43s to about ~10s.  Not bad, thanks!

The rest of the 10s do not seem to be spent with high CPU on 
either the pushing or the receiving side (only a very small 
100% burst on both sides near the end of the operation).  I 
also ran iotop on the receiving side and could not find any 
activity (of course, the repo is likely cached).  iftop does 
show a decent amount of traffic during this time, so perhaps 
we are finally approaching the protocol limit?  

But, I have my doubts on that to be honest.  The reason is 
because I am able to hack Gerrit to receive this push much 
faster (around 3.5s) by reusing a cached RevWalk.  Without 
the cached RevWalk, Gerrit (using jgit) is about the same as 
your new patch ~10s.  I am not saying that git is spending 
its time in the same place (but it may be) as jgit, but with 
jgit, the time I was able to save with the cached RevWalk 
was the time spent loading and parsing the RevCommits.  This 
could be the same thing that git is doing?  And while it may 
not be I/O (disk) bound so to speak since the packs are 
likely cached, it may still be memory bound on that I/O?  If 
it is memory bound, and not I/O(disk) or CPU bound, I guess 
it makes sense that git and jgit would perform about the 
same (10s)?

Thanks again for your patch,

-Martin

-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Shawn Pearce]

On Mon, Apr 2, 2012 at 09:24, Martin Fick <mfick@codeaurora.org> wrote:
> On Saturday, March 31, 2012 04:11:01 pm René Scharfe wrote:
>> 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.
>
> This speeds up my git push test on my repo with ~100K refs
> case from out ~43s to about ~10s.  Not bad, thanks!
>
> The rest of the 10s do not seem to be spent with high CPU on
> either the pushing or the receiving side (only a very small
> 100% burst on both sides near the end of the operation).  I
> also ran iotop on the receiving side and could not find any
> activity (of course, the repo is likely cached).  iftop does
> show a decent amount of traffic during this time, so perhaps
> we are finally approaching the protocol limit?

The protocol is basically two round trips, receive side tells push
side what it has, push side sends data, receive side sends
success/error response. It would be more traffic with SSH due to the
encryption and custom ACK messages that SSH runs to wrap the stream.

> But, I have my doubts on that to be honest.  The reason is
> because I am able to hack Gerrit to receive this push much
> faster (around 3.5s) by reusing a cached RevWalk.  Without
> the cached RevWalk, Gerrit (using jgit) is about the same as
> your new patch ~10s.  I am not saying that git is spending
> its time in the same place (but it may be) as jgit, but with
> jgit, the time I was able to save with the cached RevWalk
> was the time spent loading and parsing the RevCommits.  This
> could be the same thing that git is doing?  And while it may
> not be I/O (disk) bound so to speak since the packs are
> likely cached, it may still be memory bound on that I/O?  If
> it is memory bound, and not I/O(disk) or CPU bound, I guess
> it makes sense that git and jgit would perform about the
> same (10s)?

Git can't really do the same thing as "cache the RevWalk". Its
spawning a new process that needs to decompress and parse each commit
object to determine its timestamp so the commits can be sorted into
the priority queue. This is still an O(N) operation given N
references.

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Martin Fick]

On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:
> On Mon, Apr 2, 2012 at 09:24, Martin Fick 
<mfick@codeaurora.org> wrote:
> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe 
wrote:
> Git can't really do the same thing as "cache the
> RevWalk". Its spawning a new process that needs to
> decompress and parse each commit object to determine its
> timestamp so the commits can be sorted into the priority
> queue. This is still an O(N) operation given N
> references.

While I suspect this has been suggested before, an ondisk 
cache of commits to timestamps would probably help here with 
large repos.  Such a cache could make even new processes 
able to create this list much quicker.  Since this cache 
would contain immutable data, even if it is out of date it 
would likely provided significant improvements by providing 
most of the timestamps leaving only a few to parse from 
newer commits?

-Martin

-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Shawn Pearce]

On Mon, Apr 2, 2012 at 09:49, Martin Fick <mfick@codeaurora.org> wrote:
> On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:
>> On Mon, Apr 2, 2012 at 09:24, Martin Fick
> <mfick@codeaurora.org> wrote:
>> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe
> wrote:
>> Git can't really do the same thing as "cache the
>> RevWalk". Its spawning a new process that needs to
>> decompress and parse each commit object to determine its
>> timestamp so the commits can be sorted into the priority
>> queue. This is still an O(N) operation given N
>> references.
>
> While I suspect this has been suggested before, an ondisk
> cache of commits to timestamps would probably help here with
> large repos.  Such a cache could make even new processes
> able to create this list much quicker.  Since this cache
> would contain immutable data, even if it is out of date it
> would likely provided significant improvements by providing
> most of the timestamps leaving only a few to parse from
> newer commits?

Probably. But we tend to hate caches in Git because they can get stale
and need to be rebuilt, and are redundant with the base data. The
mythical "pack v4" work was going to approach this problem by storing
the commit timestamps uncompressed in a more machine friendly format.
Unfortunately the work has been stalled for years.

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Jeff King]

On Sun, Apr 01, 2012 at 12:11:01AM +0200, René Scharfe wrote:

> 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.

I think this is probably a sane thing to do, but I have two slight
misgivings:

  1. Is it worth the complexity of the linked-list mergesort? I was
     planning to just build an array, qsort it, and then put the results
     into a linked list. The patch for that is below for reference.

     It's a lot less code and complexity for the same performance
     (actually, I measured it at 1% faster, but that is probably
     negligible). The downside is that it is not nicely encapsulated in
     commit_list_sort_by_date(). We call the latter from two other
     places; I don't know if they can be fed with enough commits to
     actually benefit from the performance gain or not.

  2. I'm not super happy about fixing this one spot. This quadratic
     behavior comes up in a lot of places, and we're slowly hacking them
     one by one. E.g., this does nothing to help the same case in
     fetch-pack.c:mark_complete[1]. Nor does it help the fact that
     when we follow parents, we will do an O(n) insert_by_date for each
     commit we insert. The latter is largely saved by the locality of
     timestamps (i.e., timestamps of the parents of recently popped
     commits tend to be near the front of the list), as well as the hack
     in fce87ae (Fix quadratic performance in rewrite_one., 2008-07-12).

     So I wonder if in the long term we would benefit from a better data
     structure, which would make these problems just go away. That being
     said, there is a lot of code to be updated with such a change, so
     even if we do want to do that eventually, a quick fix like this is
     probably still a good thing.

-Peff

[1] I fixed the mark_complete thing in ea5f220 (fetch: avoid repeated
    commits in mark_complete, 2011-05-19), but only for exact-duplicate
    commits. The real-world case where it came up was an "alternates"
    repository that held refs for many clones (so we had hundreds or
    thousands of copies of each tag). But on a repository like the one
    we are testing on, I think it would be similarly slow.

---
Here's the qsort-in-array patch, for reference.

diff --git a/revision.c b/revision.c
index b3554ed..22c26d0 100644
--- a/revision.c
+++ b/revision.c
@@ -2062,10 +2062,24 @@ static void set_children(struct rev_info *revs)
 	}
 }
 
+static int commit_compare_by_date(const void *va, const void *vb)
+{
+	const struct commit *a = va;
+	const struct commit *b = vb;
+	if (a->date < b->date)
+		return -1;
+	if (b->date < a->date)
+		return 1;
+	return 0;
+}
+
 int prepare_revision_walk(struct rev_info *revs)
 {
 	int nr = revs->pending.nr;
 	struct object_array_entry *e, *list;
+	struct commit **commits = NULL;
+	int commits_nr = 0, commits_alloc = 0;
+	int i;
 
 	e = list = revs->pending.objects;
 	revs->pending.nr = 0;
@@ -2076,11 +2090,17 @@ 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);
+				ALLOC_GROW(commits, commits_nr + 1, commits_alloc);
+				commits[commits_nr++] = commit;
 			}
 		}
 		e++;
 	}
+	qsort(commits, commits_nr, sizeof(*commits), commit_compare_by_date);
+	for (i = commits_nr - 1; i >= 0; i--)
+		commit_list_insert(commits[i], &revs->commits);
+	free(commits);
+
 	if (!revs->leak_pending)
 		free(list);
 

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Jeff King]

On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce wrote:

> Probably. But we tend to hate caches in Git because they can get stale
> and need to be rebuilt, and are redundant with the base data. The
> mythical "pack v4" work was going to approach this problem by storing
> the commit timestamps uncompressed in a more machine friendly format.
> Unfortunately the work has been stalled for years.

I'd love for packv4 to exist, but even once it does, it comes with its
own complications for network transfer (since we will have to translate
to/from packv2 on the wire).

Has anyone looked seriously at a new index format that stores the
redundant information in a more easily accessible way? It would increase
our disk usage, but for something like linux-2.6, only by 10MB per
32-bit word. On most of my systems I would gladly spare some extra RAM
for the disk cache if it meant I could avoid inflating a bunch of
objects. And this could easily be made optional for systems that don't
want to make the tradeoff (if it's not there, you fall back to the
current procedure; we could even store the data in a separate file to
retain indexv2 compatibility).

So it's sort-of a cache, in that it's redundant with the actual data.
But staleness and writing issues are a lot simpler, since it only gets
updated when we index the pack (and the pack index in general is a
similar concept; we are "caching" the location of the object in the
packfile, rather than doing a linear search to look it up each time).

-Peff

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Jeff King]

On Mon, Apr 02, 2012 at 04:37:28PM -0400, Jeff King wrote:

> Has anyone looked seriously at a new index format that stores the
> redundant information in a more easily accessible way? It would increase
> our disk usage, but for something like linux-2.6, only by 10MB per
> 32-bit word. On most of my systems I would gladly spare some extra RAM
> for the disk cache if it meant I could avoid inflating a bunch of
> objects.

Actually, that is an over-statement of the size. That would be a
per-object piece of metadata. A per-commit piece like timestamp would be
only 1M per 32-bit word in linux-2.6 (about 1/4 million commits). Or put
another way, we could store timestamps and 20-byte parent sha1s in about
11M.

-Peff

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[René Scharfe]

Am 02.04.2012 22:14, schrieb Jeff King:
> On Sun, Apr 01, 2012 at 12:11:01AM +0200, René Scharfe wrote:
>
>> 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.
>
> I think this is probably a sane thing to do, but I have two slight
> misgivings:
>
>    1. Is it worth the complexity of the linked-list mergesort? I was
>       planning to just build an array, qsort it, and then put the results
>       into a linked list. The patch for that is below for reference.
>
>       It's a lot less code and complexity for the same performance
>       (actually, I measured it at 1% faster, but that is probably
>       negligible). The downside is that it is not nicely encapsulated in
>       commit_list_sort_by_date(). We call the latter from two other
>       places; I don't know if they can be fed with enough commits to
>       actually benefit from the performance gain or not.

Using a temporary array here is just sad, because linked lists are 
already sortable, albeit not with qsort().  Your measurements seem to 
answer my question regarding the overhead of the callback functions of 
mergesort(), in any case. :)

Adding mergesort() only pays if we have other linked lists that we want 
to sort in-place.  I didn't search thoroughly for such a use case, but I 
think we tended to prefer arrays so far instead.

>       So I wonder if in the long term we would benefit from a better data
>       structure, which would make these problems just go away. That being
>       said, there is a lot of code to be updated with such a change, so
>       even if we do want to do that eventually, a quick fix like this is
>       probably still a good thing.

Using a more appropriate data structure sounds good in general. How 
about using a skip list?  (Or perhaps I need to lay the hammer of linked 
lists to rest for a while to stop seeing all data structures as the 
proverbial nails, or something. ;-)

> Here's the qsort-in-array patch, for reference.

It looks nice and to the point, but breaks several tests for me (t3508, 
t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).  Not sure why.

René

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Martin Fick]

On Monday, April 02, 2012 02:37:28 pm Jeff King wrote:
> On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce 
wrote:
> > Probably. But we tend to hate caches in Git because
> > they can get stale and need to be rebuilt, and are
> > redundant with the base data. The mythical "pack v4"
> > work was going to approach this problem by storing the
> > commit timestamps uncompressed in a more machine
> > friendly format. Unfortunately the work has been
> > stalled for years.
...

> So it's sort-of a cache, in that it's redundant with the
> actual data. But staleness and writing issues are a lot
> simpler, since it only gets updated when we index the
> pack (and the pack index in general is a similar
> concept; 
...
except that in the case of timestamps, it never even gets 
stale, it simply misses some entries or keeps entries around 
which should go away.  So even if the pack files are rebuilt 
and someone forgets to update the timestamp index, it 
shouldn't cause any problems:  the timestamps which are 
there should still work and likely will still be useful,

-Martin



-- 
Employee of Qualcomm Innovation Center, Inc. which is a 
member of Code Aurora Forum

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Nguyen Thai Ngoc Duy]

On Mon, Apr 2, 2012 at 11:51 PM, Shawn Pearce <spearce@spearce.org> wrote:
> On Mon, Apr 2, 2012 at 09:49, Martin Fick <mfick@codeaurora.org> wrote:
>> On Monday, April 02, 2012 10:39:59 am Shawn Pearce wrote:
>>> On Mon, Apr 2, 2012 at 09:24, Martin Fick
>> <mfick@codeaurora.org> wrote:
>>> > On Saturday, March 31, 2012 04:11:01 pm René Scharfe
>> wrote:
>>> Git can't really do the same thing as "cache the
>>> RevWalk". Its spawning a new process that needs to
>>> decompress and parse each commit object to determine its
>>> timestamp so the commits can be sorted into the priority
>>> queue. This is still an O(N) operation given N
>>> references.
>>
>> While I suspect this has been suggested before, an ondisk
>> cache of commits to timestamps would probably help here with
>> large repos.  Such a cache could make even new processes
>> able to create this list much quicker.  Since this cache
>> would contain immutable data, even if it is out of date it
>> would likely provided significant improvements by providing
>> most of the timestamps leaving only a few to parse from
>> newer commits?
>
> Probably. But we tend to hate caches in Git because they can get stale
> and need to be rebuilt, and are redundant with the base data. The
> mythical "pack v4" work was going to approach this problem by storing
> the commit timestamps uncompressed in a more machine friendly format.
> Unfortunately the work has been stalled for years.

which reminds me, hello Nico!

On Sat, Feb 18, 2012 at 10:34 PM, Nicolas Pitre <nico@fluxnic.net> wrote:
>> By the way, is latest packv4 code available somewhere to fetch?
>
> Well, not yet.  Incidentally, I'm going in the Caribbeans for a week in
> a week, with no kids and only my wife who is going to be busy with scuba
> diving activities.  Like I did last year, I'm going to take some time to
> pursue my work on Pack v4 during that time.  And I intend to publish it
> when I come back, whatever state it is in, so someone else can complete
> the work eventually (I have too much to do to spend significant time on
> Git these days).

How's the packv4 work going? Is it in a public place? I hope somebody
else may have spare time and be motivated enough to finish it.
-- 
Duy

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Nguyen Thai Ngoc Duy]

On Tue, Apr 3, 2012 at 3:37 AM, Jeff King <peff@peff.net> wrote:
> On Mon, Apr 02, 2012 at 09:51:21AM -0700, Shawn O. Pearce wrote:
>
>> Probably. But we tend to hate caches in Git because they can get stale
>> and need to be rebuilt, and are redundant with the base data. The
>> mythical "pack v4" work was going to approach this problem by storing
>> the commit timestamps uncompressed in a more machine friendly format.
>> Unfortunately the work has been stalled for years.
>
> I'd love for packv4 to exist, but even once it does, it comes with its
> own complications for network transfer (since we will have to translate
> to/from packv2 on the wire).
>
> Has anyone looked seriously at a new index format that stores the
> redundant information in a more easily accessible way? It would increase
> our disk usage, but for something like linux-2.6, only by 10MB per
> 32-bit word. On most of my systems I would gladly spare some extra RAM
> for the disk cache if it meant I could avoid inflating a bunch of
> objects. And this could easily be made optional for systems that don't
> want to make the tradeoff (if it's not there, you fall back to the
> current procedure; we could even store the data in a separate file to
> retain indexv2 compatibility).
>
> So it's sort-of a cache, in that it's redundant with the actual data.
> But staleness and writing issues are a lot simpler, since it only gets
> updated when we index the pack (and the pack index in general is a
> similar concept; we are "caching" the location of the object in the
> packfile, rather than doing a linear search to look it up each time).

I think I have something like that, (generate a machine-friendly
commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's
separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx
files. It does improve rev-list time, but I'd rather wait for packv4,
or at least be sure that packv4 will not come anytime soon, before
pushing the cache route.
-- 
Duy

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Martin Fick]

Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> we could even store the data in a separate file to
>> retain indexv2 compatibility).
>>
>> So it's sort-of a cache, in that it's redundant with the actual data.
>> But staleness and writing issues are a lot simpler, since it only
>gets
>> updated when we index the pack (and the pack index in general is a
>> similar concept; we are "caching" the location of the object in the
>> packfile, rather than doing a linear search to look it up each time).
>
>I think I have something like that, (generate a machine-friendly
>commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's
>separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx
>files. It does improve rev-list time, but I'd rather wait for packv4,
>or at least be sure that packv4 will not come anytime soon, before
>pushing the cache route.

I would love to try those patches out if you have them?

-Martin

Employee of Qualcomm Innovation Center,Inc. which is a member of Code Aurora Forum

[PATCH 0/3] Commit cache

[Nguyễn Thái Ngọc Duy]

On Tue, Apr 3, 2012 at 12:55 PM, Martin Fick <mfick@codeaurora.org> wrote:
> Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>>> we could even store the data in a separate file to
>>> retain indexv2 compatibility).
>>>
>>> So it's sort-of a cache, in that it's redundant with the actual data.
>>> But staleness and writing issues are a lot simpler, since it only
>>gets
>>> updated when we index the pack (and the pack index in general is a
>>> similar concept; we are "caching" the location of the object in the
>>> packfile, rather than doing a linear search to look it up each time).
>>
>>I think I have something like that, (generate a machine-friendly
>>commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's
>>separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx
>>files. It does improve rev-list time, but I'd rather wait for packv4,
>>or at least be sure that packv4 will not come anytime soon, before
>>pushing the cache route.
>
> I would love to try those patches out if you have them?

There you go. Note that these patches are not of high quality. I did not even
run "make test". To create commit cache, simply run index-pack, e.g.

$ git repack -ad
$ git index-pack --stdin < .git/objects/pack/pack-XXX.pack

It will create two more files, pack-XXX.sha1 and pack-XXX.sidx. On
linux-2.6.git, "git rev-list --all --quiet HEAD" takes 1.9s with the
patches and 6.6s without. Disk usage:

total 531M
 56M pack-ab843186bdfb00956c1b1c0cdb4ed5e4aa3e549e.idx
460M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.pack
9.7M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.sha1
5.3M pack-ab843185bdfb00956c1b1c0cdb4ed5e4aa3e549e.sidx

Nguyễn Thái Ngọc Duy (3):
  parse_commit_buffer: rename a confusing variable name
  Add commit cache to help speed up commit traversal
  Add parse_commit_for_rev() to take advantage of sha1-cache

 Makefile             |    3 +
 builtin/index-pack.c |  113 ++++++++++++++++++++++++++++++++++-
 builtin/reflog.c     |    2 +-
 cache.h              |    9 +++
 commit.c             |   46 +++++++++++---
 commit.h             |    1 +
 log-tree.c           |    2 +-
 pack-write.c         |   11 +++-
 pack.h               |    1 +
 revision.c           |   10 ++--
 sha1_cache.c         |  161 ++++++++++++++++++++++++++++++++++++++++++++++++++
 sha1_cache.h         |    6 ++
 sha1_file.c          |   12 ++++-
 test-sha1-cache.c    |   19 ++++++
 upload-pack.c        |    2 +-
 walker.c             |    2 +-
 16 files changed, 377 insertions(+), 23 deletions(-)
 create mode 100644 sha1_cache.c
 create mode 100644 sha1_cache.h
 create mode 100644 test-sha1-cache.c

-- 
1.7.3.1.256.g2539c.dirty

[PATCH 1/3] parse_commit_buffer: rename a confusing variable name

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/commit.c b/commit.c
index 4b39c19..946ea70 100644
--- a/commit.c
+++ b/commit.c
@@ -252,7 +252,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 {
 	const char *tail = buffer;
 	const char *bufptr = buffer;
-	unsigned char parent[20];
+	unsigned char sha1[20];
 	struct commit_list **pptr;
 	struct commit_graft *graft;
 
@@ -262,10 +262,10 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 	tail += size;
 	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
 		return error("bogus commit object %s", sha1_to_hex(item->object.sha1));
-	if (get_sha1_hex(bufptr + 5, parent) < 0)
+	if (get_sha1_hex(bufptr + 5, sha1) < 0)
 		return error("bad tree pointer in commit %s",
 			     sha1_to_hex(item->object.sha1));
-	item->tree = lookup_tree(parent);
+	item->tree = lookup_tree(sha1);
 	bufptr += 46; /* "tree " + "hex sha1" + "\n" */
 	pptr = &item->parents;
 
@@ -274,7 +274,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 		struct commit *new_parent;
 
 		if (tail <= bufptr + 48 ||
-		    get_sha1_hex(bufptr + 7, parent) ||
+		    get_sha1_hex(bufptr + 7, sha1) ||
 		    bufptr[47] != '\n')
 			return error("bad parents in commit %s", sha1_to_hex(item->object.sha1));
 		bufptr += 48;
@@ -284,7 +284,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 		 */
 		if (graft && (graft->nr_parent < 0 || grafts_replace_parents))
 			continue;
-		new_parent = lookup_commit(parent);
+		new_parent = lookup_commit(sha1);
 		if (new_parent)
 			pptr = &commit_list_insert(new_parent, pptr)->next;
 	}
-- 
1.7.3.1.256.g2539c.dirty

[PATCH 2/3] Add commit cache to help speed up commit traversal

[Nguyễn Thái Ngọc Duy]

This patch extracts tree, parent sha-1 and committer date of packed
commits that have exactly one parent out. So that revision traversal
code can avoid inflating commit for these sha-1. The assumption is
commits with one parent dominate.

Two new files are created per pack: one file contains sha-1 and dates.
The other file contains commit sha-1 mapping to the offset in the former
file.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile             |    3 +
 builtin/index-pack.c |  113 ++++++++++++++++++++++++++++++++++-
 cache.h              |    9 +++
 pack-write.c         |   11 +++-
 pack.h               |    1 +
 sha1_cache.c         |  161 ++++++++++++++++++++++++++++++++++++++++++++++++++
 sha1_cache.h         |    6 ++
 sha1_file.c          |   12 ++++-
 test-sha1-cache.c    |   19 ++++++
 9 files changed, 331 insertions(+), 4 deletions(-)
 create mode 100644 sha1_cache.c
 create mode 100644 sha1_cache.h
 create mode 100644 test-sha1-cache.c

diff --git a/Makefile b/Makefile
index 87fb30a..fced758 100644
--- a/Makefile
+++ b/Makefile
@@ -481,6 +481,7 @@ TEST_PROGRAMS_NEED_X += test-sha1
 TEST_PROGRAMS_NEED_X += test-sigchain
 TEST_PROGRAMS_NEED_X += test-subprocess
 TEST_PROGRAMS_NEED_X += test-svn-fe
+TEST_PROGRAMS_NEED_X += test-sha1-cache
 
 TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))
 
@@ -606,6 +607,7 @@ LIB_H += run-command.h
 LIB_H += sequencer.h
 LIB_H += sha1-array.h
 LIB_H += sha1-lookup.h
+LIB_H += sha1_cache.h
 LIB_H += sideband.h
 LIB_H += sigchain.h
 LIB_H += strbuf.h
@@ -722,6 +724,7 @@ LIB_OBJS += setup.o
 LIB_OBJS += sequencer.o
 LIB_OBJS += sha1-array.o
 LIB_OBJS += sha1-lookup.o
+LIB_OBJS += sha1_cache.o
 LIB_OBJS += sha1_file.o
 LIB_OBJS += sha1_name.o
 LIB_OBJS += shallow.o
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index dd1c5c9..67673ef 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -15,6 +15,7 @@ static const char index_pack_usage[] =
 
 struct object_entry {
 	struct pack_idx_entry idx;
+	off_t commit_offset;
 	unsigned long size;
 	unsigned int hdr_size;
 	enum object_type type;
@@ -63,6 +64,7 @@ static int nr_resolved_deltas;
 static int from_stdin;
 static int strict;
 static int verbose;
+static int write_cache = 1;
 
 static struct progress *progress;
 
@@ -75,6 +77,13 @@ static git_SHA_CTX input_ctx;
 static uint32_t input_crc32;
 static int input_fd, output_fd, pack_fd;
 
+static int cache_fd;
+static int cache_written;
+static uint32_t cache_nr;
+static char cache_filename[PATH_MAX];
+static const char *cache_idxname;
+static unsigned char cache_sha1[20];
+
 static int mark_link(struct object *obj, int type, void *data)
 {
 	if (!obj)
@@ -682,6 +691,58 @@ static int compare_delta_entry(const void *a, const void *b)
 				   objects[delta_b->obj_no].type);
 }
 
+static unsigned long parse_commit_date(const char *buf, const char *tail)
+{
+	const char *dateptr;
+
+	if (buf + 6 >= tail)
+		return 0;
+	if (memcmp(buf, "author", 6))
+		return 0;
+	while (buf < tail && *buf++ != '\n')
+		/* nada */;
+	if (buf + 9 >= tail)
+		return 0;
+	if (memcmp(buf, "committer", 9))
+		return 0;
+	while (buf < tail && *buf++ != '>')
+		/* nada */;
+	if (buf >= tail)
+		return 0;
+	dateptr = buf;
+	while (buf < tail && *buf++ != '\n')
+		/* nada */;
+	if (buf >= tail)
+		return 0;
+	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
+	return strtoul(dateptr, NULL, 10);
+}
+
+static void write_commit_sha1(struct object_entry *obj, const char *data)
+{
+	unsigned char sha1[20];
+	if (!obj->commit_offset &&
+	    !memcmp(data, "tree ", 5) &&
+	    !memcmp(data + 45, "\nparent ", 8) &&
+	    memcmp(data + 45 + 48, "\nparent ", 8)) {
+		uint32_t date;
+		obj->commit_offset = cache_written;
+		cache_nr++;
+
+		get_sha1_hex(data + 5, sha1);
+		cache_written += xwrite(cache_fd, sha1, 20);
+		get_sha1_hex(data + 5 + 48, sha1);
+		cache_written += xwrite(cache_fd, sha1, 20);
+		date = parse_commit_date(data + 5 + 48 + 41, data + obj->size);
+		date = htonl(date);
+		cache_written += xwrite(cache_fd, &date, 4);
+	}
+#if 0
+	hashclr(sha1);
+	cache_written += xwrite(cache_fd, sha1, 20);
+#endif
+}
+
 /* Parse all objects and return the pack content SHA1 hash */
 static void parse_pack_objects(unsigned char *sha1)
 {
@@ -707,8 +768,13 @@ static void parse_pack_objects(unsigned char *sha1)
 			nr_deltas++;
 			delta->obj_no = i;
 			delta++;
-		} else
+		} else {
 			sha1_object(data, obj->size, obj->type, obj->idx.sha1);
+
+			/* We assume that commits are never deltified */
+			if (write_cache && obj->real_type == OBJ_COMMIT)
+				write_commit_sha1(obj, data);
+		}
 		free(data);
 		display_progress(progress, i+1);
 	}
@@ -919,6 +985,18 @@ static void final(const char *final_pack_name, const char *curr_pack_name,
 	} else if (from_stdin)
 		chmod(final_pack_name, 0444);
 
+	if (write_cache) {
+		snprintf(name, sizeof(name), "%s/pack/pack-%s.sha1",
+			 get_object_directory(), sha1_to_hex(sha1));
+		if (move_temp_to_file(cache_filename, name))
+			die("cannot store commit cache file");
+
+		snprintf(name, sizeof(name), "%s/pack/pack-%s.sidx",
+			 get_object_directory(), sha1_to_hex(sha1));
+		if (move_temp_to_file(cache_idxname, name))
+			die("cannot store commit cache file");
+	}
+
 	if (final_index_name != curr_index_name) {
 		if (!final_index_name) {
 			snprintf(name, sizeof(name), "%s/pack/pack-%s.idx",
@@ -1120,6 +1198,8 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 				keep_msg = "";
 			} else if (!prefixcmp(arg, "--keep=")) {
 				keep_msg = arg + 7;
+			} else if (!strcmp(arg, "--no-cache")) {
+				write_cache = 0;
 			} else if (!prefixcmp(arg, "--pack_header=")) {
 				struct pack_header *hdr;
 				char *c;
@@ -1191,6 +1271,17 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	if (strict)
 		opts.flags |= WRITE_IDX_STRICT;
 
+	if (verify)
+		write_cache = 0;
+	if (write_cache) {
+		unsigned char sha1[20];
+		cache_fd = odb_mkstemp(cache_filename,
+				       sizeof(cache_filename),
+				       "pack/tmp_sha1_XXXXXX");
+		hashclr(sha1);
+		cache_written = xwrite(cache_fd, sha1, 20);
+	}
+
 	curr_pack = open_pack_file(pack_name);
 	parse_pack_header();
 	objects = xcalloc(nr_objects + 1, sizeof(struct object_entry));
@@ -1243,6 +1334,26 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	curr_index = write_idx_file(index_name, idx_objects, nr_objects, &opts, pack_sha1);
 	free(idx_objects);
 
+	if (write_cache) {
+		int nr;
+		struct pack_idx_entry **idx;
+
+		close(cache_fd);
+
+		idx = idx_objects = xmalloc((cache_nr) * sizeof(struct pack_idx_entry *));
+		for (nr = i = 0; i < nr_objects; i++) {
+			if (objects[i].commit_offset) {
+				objects[i].idx.offset = objects[i].commit_offset;
+				*idx++ = &objects[i].idx;
+				nr++;
+			}
+		}
+		assert(nr == cache_nr);
+		opts.flags |= WRITE_IDX_SHA1_CACHE;
+		cache_idxname = write_idx_file(NULL, idx_objects, cache_nr, &opts, cache_sha1);
+		free(idx_objects);
+	}
+
 	if (!verify)
 		final(pack_name, curr_pack,
 		      index_name, curr_index,
diff --git a/cache.h b/cache.h
index 9bd8c2d..fd3953f 100644
--- a/cache.h
+++ b/cache.h
@@ -972,6 +972,14 @@ struct pack_window {
 	unsigned int inuse_cnt;
 };
 
+struct sha1_cache {
+	const void *idx;
+	const void *data;
+	size_t idx_size;
+	size_t data_size;
+	uint32_t nr;
+};
+
 extern struct packed_git {
 	struct packed_git *next;
 	struct pack_window *windows;
@@ -984,6 +992,7 @@ extern struct packed_git {
 	int index_version;
 	time_t mtime;
 	int pack_fd;
+	struct sha1_cache commit_cache;
 	unsigned pack_local:1,
 		 pack_keep:1,
 		 do_not_close:1;
diff --git a/pack-write.c b/pack-write.c
index ca9e63b..6da977a 100644
--- a/pack-write.c
+++ b/pack-write.c
@@ -85,8 +85,11 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec
 		f = sha1fd(fd, index_name);
 	}
 
-	/* if last object's offset is >= 2^31 we should use index V2 */
-	index_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;
+	if (opts->flags & WRITE_IDX_SHA1_CACHE)
+		index_version = 2;
+	else
+		/* if last object's offset is >= 2^31 we should use index V2 */
+		index_version = need_large_offset(last_obj_offset, opts) ? 2 : opts->version;
 
 	/* index versions 2 and above need a header */
 	if (index_version >= 2) {
@@ -138,6 +141,9 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec
 	if (index_version >= 2) {
 		unsigned int nr_large_offset = 0;
 
+		if (opts->flags & WRITE_IDX_SHA1_CACHE)
+			goto skip_crc32;
+
 		/* write the crc32 table */
 		list = sorted_by_sha;
 		for (i = 0; i < nr_objects; i++) {
@@ -146,6 +152,7 @@ const char *write_idx_file(const char *index_name, struct pack_idx_entry **objec
 			sha1write(f, &crc32_val, 4);
 		}
 
+skip_crc32:
 		/* write the 32-bit offset table */
 		list = sorted_by_sha;
 		for (i = 0; i < nr_objects; i++) {
diff --git a/pack.h b/pack.h
index aa6ee7d..f002b6a 100644
--- a/pack.h
+++ b/pack.h
@@ -40,6 +40,7 @@ struct pack_idx_option {
 	/* flag bits */
 #define WRITE_IDX_VERIFY 01 /* verify only, do not write the idx file */
 #define WRITE_IDX_STRICT 02
+#define WRITE_IDX_SHA1_CACHE 04
 
 	uint32_t version;
 	uint32_t off32_limit;
diff --git a/sha1_cache.c b/sha1_cache.c
new file mode 100644
index 0000000..3f244bb
--- /dev/null
+++ b/sha1_cache.c
@@ -0,0 +1,161 @@
+#include "cache.h"
+#include "pack.h"
+#include "sha1_cache.h"
+
+static int git_open_noatime(const char *name)
+{
+	static int sha1_file_open_flag = O_NOATIME;
+
+	for (;;) {
+		int fd = open(name, O_RDONLY | sha1_file_open_flag);
+		if (fd >= 0)
+			return fd;
+
+		/* Might the failure be due to O_NOATIME? */
+		if (errno != ENOENT && sha1_file_open_flag) {
+			sha1_file_open_flag = 0;
+			continue;
+		}
+
+		return -1;
+	}
+}
+
+/*
+ * Commit cache format is basically pack index v2 except that:
+ * - no crc32 table
+ * - no large offset support
+ * - offset table contains offset in _this_ file, in the commit
+ *   cache section
+ * - the commit cache section follows offset table, each entry
+ *   consists of tree sha1, parent sha1 if any, and terminated
+ *   by null sha-1.
+ */
+
+int open_sha1_cache(struct sha1_cache *cache,
+		    const char *data_path, const char *idx_path)
+{
+	void *idx_map, *data;
+	struct pack_idx_header *hdr;
+	size_t idx_size, data_size;
+	uint32_t nr, i, *index;
+	int fd = git_open_noatime(idx_path);
+	struct stat st;
+
+	if (fd < 0)
+		return -1;
+	if (fstat(fd, &st)) {
+		close(fd);
+		return -1;
+	}
+	idx_size = xsize_t(st.st_size);
+	if (idx_size < 4 * 256 + 20 + 20) {
+		close(fd);
+		return error("index file %s is too small", idx_path);
+	}
+	idx_map = xmmap(NULL, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
+
+	fd = git_open_noatime(data_path);
+	if (fd < 0)
+		return -1;
+	if (fstat(fd, &st)) {
+		close(fd);
+		return -1;
+	}
+	data_size = xsize_t(st.st_size);
+	data = xmmap(NULL, data_size, PROT_READ, MAP_PRIVATE, fd, 0);
+	close(fd);
+
+	hdr = idx_map;
+	if (hdr->idx_signature != htonl(PACK_IDX_SIGNATURE))
+		return error("not a commit cache file %s", idx_path);
+	if (ntohl(hdr->idx_version) != 2)
+		return error("wrong version %s %d", idx_path, ntohl(hdr->idx_version));
+
+	nr = 0;
+	index = idx_map;
+	index += 2;  /* skip index header */
+	for (i = 0; i < 256; i++) {
+		uint32_t n = ntohl(index[i]);
+		if (n < nr) {
+			munmap(idx_map, idx_size);
+			return error("non-monotonic index %s", idx_path);
+		}
+		nr = n;
+	}
+
+	cache->idx = idx_map;
+	cache->idx_size = idx_size;
+	cache->nr = nr;
+	cache->data = data;
+	cache->data_size = data_size;
+	return 0;
+}
+
+static const void *object_offset(const struct sha1_cache *cache, uint32_t n)
+{
+	const unsigned char *index = cache->idx;
+	uint32_t off;
+	index += 4 * 256;
+	index += 8 + cache->nr * 20;
+	off = ntohl(*((uint32_t *)(index + 4 * n)));
+	return (const char *)cache->data + off;
+}
+
+const void *find_sha1_in_cache(const unsigned char *sha1)
+{
+	const uint32_t *level1_ofs;
+	const unsigned char *index;
+	unsigned hi, lo, stride;
+
+	struct packed_git *p = find_sha1_pack(sha1, packed_git);
+	if (!p)
+		return 0;
+
+	open_pack_index(p);
+	if (!p->commit_cache.nr)
+		return 0;
+
+	level1_ofs = p->commit_cache.idx;
+	index = p->commit_cache.idx;
+
+	/* skip header */
+	level1_ofs += 2;
+	index += 8;
+
+	/* fanout table */
+	index += 4 * 256;
+	hi = ntohl(level1_ofs[*sha1]);
+	lo = ((*sha1 == 0x0) ? 0 : ntohl(level1_ofs[*sha1 - 1]));
+	stride = 20;
+
+	do {
+		unsigned mi = (lo + hi) / 2;
+		int cmp = hashcmp(index + mi * stride, sha1);
+
+		if (!cmp)
+			return object_offset(&p->commit_cache, mi);
+		if (cmp > 0)
+			hi = mi;
+		else
+			lo = mi+1;
+	} while (lo < hi);
+	return NULL;
+}
+
+int has_commit_cache(const unsigned char *sha1,
+		     unsigned char *tree,
+		     unsigned char *parent,
+		     unsigned long *date)
+{
+	const unsigned char *data;
+	data = find_sha1_in_cache(sha1);
+	if (!data)
+		return 0;
+
+	hashcpy(tree, data);
+	hashcpy(parent, data + 20);
+	*date = ntohl(*((uint32_t*)(data + 40)));
+	return 1;
+}
diff --git a/sha1_cache.h b/sha1_cache.h
new file mode 100644
index 0000000..59823cf
--- /dev/null
+++ b/sha1_cache.h
@@ -0,0 +1,6 @@
+extern int open_sha1_cache(struct sha1_cache *cache,
+			   const char *data_path, const char *idx_path);
+extern const void *find_sha1_in_cache(const unsigned char *sha1);
+extern int has_commit_cache(const unsigned char *sha1,
+			    unsigned char *tree, unsigned char *parent,
+			    unsigned long *date);
diff --git a/sha1_file.c b/sha1_file.c
index 88f2151..fc2f460 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -19,6 +19,7 @@
 #include "pack-revindex.h"
 #include "sha1-lookup.h"
 #include "bulk-checkin.h"
+#include "sha1_cache.h"
 
 #ifndef O_NOATIME
 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -578,14 +579,23 @@ static int check_packed_git_idx(const char *path,  struct packed_git *p)
 int open_pack_index(struct packed_git *p)
 {
 	char *idx_name;
+	int baselen = strlen(p->pack_name) - strlen(".pack");
 	int ret;
 
 	if (p->index_data)
 		return 0;
 
 	idx_name = xstrdup(p->pack_name);
-	strcpy(idx_name + strlen(idx_name) - strlen(".pack"), ".idx");
+	strcpy(idx_name + baselen, ".idx");
 	ret = check_packed_git_idx(idx_name, p);
+	if (!ret) {
+		char *cache_name;
+		cache_name = xstrdup(p->pack_name);
+		strcpy(idx_name + baselen, ".sidx");
+		strcpy(cache_name + baselen, ".sha1");
+		open_sha1_cache(&p->commit_cache, cache_name, idx_name);
+		free(cache_name);
+	}
 	free(idx_name);
 	return ret;
 }
diff --git a/test-sha1-cache.c b/test-sha1-cache.c
new file mode 100644
index 0000000..7b7f32c
--- /dev/null
+++ b/test-sha1-cache.c
@@ -0,0 +1,19 @@
+#include "cache.h"
+#include "sha1_cache.h"
+
+int main(int argc, char **argv)
+{
+	unsigned char sha1[20];
+	unsigned char tree[20];
+	unsigned char parent[20];
+	unsigned long date;
+
+	setup_git_directory();
+	prepare_packed_git();
+	get_sha1_hex(argv[1], sha1);
+	if (!has_commit_cache(sha1, tree, parent, &date))
+		return 1;
+	printf("tree %s\nparent %s\ndate %ld\n",
+	       sha1_to_hex(tree), sha1_to_hex(parent), date);
+	return 0;
+}
-- 
1.7.3.1.256.g2539c.dirty

[PATCH 3/3] Add parse_commit_for_rev() to take advantage of sha1-cache

[Nguyễn Thái Ngọc Duy]

This function tries to lookup sha1-cache. If it's found, struct commit
is filled, no actual commit parsing is done. Otherwise parse_commit() is
called.

Because sha1-cache only has information enough for rev machinery (tree,
parent and date), this function is hardly suitable for general use.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/reflog.c |    2 +-
 commit.c         |   36 +++++++++++++++++++++++++++++++-----
 commit.h         |    1 +
 log-tree.c       |    2 +-
 revision.c       |   10 +++++-----
 upload-pack.c    |    2 +-
 walker.c         |    2 +-
 7 files changed, 41 insertions(+), 14 deletions(-)

diff --git a/builtin/reflog.c b/builtin/reflog.c
index 062d7da..b15ff98 100644
--- a/builtin/reflog.c
+++ b/builtin/reflog.c
@@ -240,7 +240,7 @@ static void mark_reachable(struct expire_reflog_cb *cb)
 		free(entry);
 		if (commit->object.flags & REACHABLE)
 			continue;
-		if (parse_commit(commit))
+		if (parse_commit_limited(commit))
 			continue;
 		commit->object.flags |= REACHABLE;
 		if (commit->date < expire_limit) {
diff --git a/commit.c b/commit.c
index 946ea70..aa32658 100644
--- a/commit.c
+++ b/commit.c
@@ -7,6 +7,7 @@
 #include "revision.h"
 #include "notes.h"
 #include "gpg-interface.h"
+#include "sha1_cache.h"
 
 int save_commit_buffer = 1;
 
@@ -28,7 +29,11 @@ static struct commit *check_commit(struct object *obj,
 struct commit *lookup_commit_reference_gently(const unsigned char *sha1,
 					      int quiet)
 {
-	struct object *obj = deref_tag(parse_object(sha1), NULL, 0);
+	struct object *obj;
+	struct commit *c = lookup_commit(sha1);
+	if (c)
+		return c;
+	obj = deref_tag(parse_object(sha1), NULL, 0);
 
 	if (!obj)
 		return NULL;
@@ -258,6 +263,12 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 
 	if (item->object.parsed)
 		return 0;
+
+	if (item->parents) {
+		free_commit_list(item->parents);
+		item->parents = NULL;
+	}
+
 	item->object.parsed = 1;
 	tail += size;
 	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
@@ -332,6 +343,21 @@ int parse_commit(struct commit *item)
 	return ret;
 }
 
+int parse_commit_limited(struct commit *c)
+{
+	unsigned char tree[20];
+	unsigned char parent[20];
+
+	if (c->object.parsed || c->parents)
+		return 0;
+	if (has_commit_cache(c->object.sha1, tree, parent, &c->date)) {
+		commit_list_insert(lookup_commit(parent), &c->parents);
+		c->tree = lookup_tree(tree);
+		return 0;
+	}
+	return parse_commit(c);
+}
+
 int find_commit_subject(const char *commit_buffer, const char **subject)
 {
 	const char *eol;
@@ -413,7 +439,7 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
 
 	while (parents) {
 		struct commit *commit = parents->item;
-		if (!parse_commit(commit) && !(commit->object.flags & mark)) {
+		if (!parse_commit_limited(commit) && !(commit->object.flags & mark)) {
 			commit->object.flags |= mark;
 			commit_list_insert_by_date(commit, list);
 		}
@@ -605,10 +631,10 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
 			return commit_list_insert(one, &result);
 	}
 
-	if (parse_commit(one))
+	if (parse_commit_limited(one))
 		return NULL;
 	for (i = 0; i < n; i++) {
-		if (parse_commit(twos[i]))
+		if (parse_commit_limited(twos[i]))
 			return NULL;
 	}
 
@@ -645,7 +671,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
 			parents = parents->next;
 			if ((p->object.flags & flags) == flags)
 				continue;
-			if (parse_commit(p))
+			if (parse_commit_limited(p))
 				return NULL;
 			p->object.flags |= flags;
 			commit_list_insert_by_date(p, &list);
diff --git a/commit.h b/commit.h
index 154c0e3..113303b 100644
--- a/commit.h
+++ b/commit.h
@@ -47,6 +47,7 @@ struct commit *lookup_commit_or_die(const unsigned char *sha1, const char *ref_n
 
 int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long size);
 int parse_commit(struct commit *item);
+int parse_commit_limited(struct commit *item);
 
 /* Find beginning and length of commit subject. */
 int find_commit_subject(const char *commit_buffer, const char **subject);
diff --git a/log-tree.c b/log-tree.c
index cea8756..047ddec 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -643,7 +643,7 @@ void show_log(struct rev_info *opt)
 		show_mergetag(opt, commit);
 	}
 
-	if (!commit->buffer)
+	if (!commit->buffer && parse_commit(commit) < 0)
 		return;
 
 	/*
diff --git a/revision.c b/revision.c
index c97d834..4c229fd 100644
--- a/revision.c
+++ b/revision.c
@@ -273,7 +273,7 @@ static struct commit *handle_commit(struct rev_info *revs, struct object *object
 	 */
 	if (object->type == OBJ_COMMIT) {
 		struct commit *commit = (struct commit *)object;
-		if (parse_commit(commit) < 0)
+		if (parse_commit_limited(commit) < 0)
 			die("unable to parse commit %s", name);
 		if (flags & UNINTERESTING) {
 			commit->object.flags |= UNINTERESTING;
@@ -465,7 +465,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 		 */
 		if (revs->first_parent_only && nth_parent++)
 			break;
-		if (parse_commit(p) < 0)
+		if (parse_commit_limited(p) < 0)
 			die("cannot simplify commit %s (because of %s)",
 			    sha1_to_hex(commit->object.sha1),
 			    sha1_to_hex(p->object.sha1));
@@ -498,7 +498,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 				 * IOW, we pretend this parent is a
 				 * "root" commit.
 				 */
-				if (parse_commit(p) < 0)
+				if (parse_commit_limited(p) < 0)
 					die("cannot simplify commit %s (invalid %s)",
 					    sha1_to_hex(commit->object.sha1),
 					    sha1_to_hex(p->object.sha1));
@@ -561,7 +561,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 			parent = parent->next;
 			if (p)
 				p->object.flags |= UNINTERESTING;
-			if (parse_commit(p) < 0)
+			if (parse_commit_limited(p) < 0)
 				continue;
 			if (p->parents)
 				mark_parents_uninteresting(p);
@@ -588,7 +588,7 @@ static int add_parents_to_list(struct rev_info *revs, struct commit *commit,
 	for (parent = commit->parents; parent; parent = parent->next) {
 		struct commit *p = parent->item;
 
-		if (parse_commit(p) < 0)
+		if (parse_commit_limited(p) < 0)
 			return -1;
 		if (revs->show_source && !p->util)
 			p->util = commit->util;
diff --git a/upload-pack.c b/upload-pack.c
index bb08e2e..d30e604 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -694,7 +694,7 @@ static void receive_needs(void)
 				/* make sure the real parents are parsed */
 				unregister_shallow(object->sha1);
 				object->parsed = 0;
-				if (parse_commit((struct commit *)object))
+				if (parse_commit_limited((struct commit *)object))
 					die("invalid commit");
 				parents = ((struct commit *)object)->parents;
 				while (parents) {
diff --git a/walker.c b/walker.c
index be389dc..7b818f5 100644
--- a/walker.c
+++ b/walker.c
@@ -71,7 +71,7 @@ static struct commit_list *complete = NULL;
 
 static int process_commit(struct walker *walker, struct commit *commit)
 {
-	if (parse_commit(commit))
+	if (parse_commit_limited(commit))
 		return -1;
 
 	while (complete && complete->item->date >= commit->date) {
-- 
1.7.3.1.256.g2539c.dirty

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Jeff King]

On Tue, Apr 03, 2012 at 12:54:05AM +0200, René Scharfe wrote:

> >   1. Is it worth the complexity of the linked-list mergesort? I was
> >      planning to just build an array, qsort it, and then put the results
> >      into a linked list. The patch for that is below for reference.
>
> Using a temporary array here is just sad, because linked lists are
> already sortable, albeit not with qsort().  Your measurements seem to
> answer my question regarding the overhead of the callback functions
> of mergesort(), in any case. :)

I agree it is a little gross. The main impetus was shortened code, since
we get qsort for free. However, after reading Simon's page that you
referenced and reading your code carefully, I'm beginning to think that
the linked-list mergesort is pretty damn cool (I hadn't seen it before).
After all, mergesort without the auxiliary space should be better than
qsort.

So let's go with your patches.

> [...]
> It looks nice and to the point, but breaks several tests for me
> (t3508, t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).
> Not sure why.

I probably screwed up the reversal or something. My patch was a quick "I
was thinking of this direction" and I didn't actually test it well.

> >      So I wonder if in the long term we would benefit from a better data
> >      structure, which would make these problems just go away. That being
> >      said, there is a lot of code to be updated with such a change, so
> >      even if we do want to do that eventually, a quick fix like this is
> >      probably still a good thing.
> 
> Using a more appropriate data structure sounds good in general. How
> about using a skip list?  (Or perhaps I need to lay the hammer of
> linked lists to rest for a while to stop seeing all data structures
> as the proverbial nails, or something. ;-)

Actually, I think a skip list would make a lot of sense, as it mostly
retains the linked-list properties. When I tried converting it to a
heap-based priority queue, I seem to recall that there were some spots
that wanted to splice the commit list (among other things). Although I'm
not sure how splicing works in a skip list; I guess you'd have to do a
list merge.

-Peff

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Jeff King]

On Tue, Apr 03, 2012 at 04:40:36AM -0400, Jeff King wrote:

> > It looks nice and to the point, but breaks several tests for me
> > (t3508, t4013, t4041, t4202, t6003, t6009, t6016, t6018 and t7401).
> > Not sure why.
> 
> I probably screwed up the reversal or something. My patch was a quick "I
> was thinking of this direction" and I didn't actually test it well.

Ugh. Not that it matters now, but the patch below fixes my version.

Not only did I manage to screw up the reversal, but I also messed up the
calling convention for qsort. So the moral is that we should take 100
lines of your tested code over 5 lines of my junk. ;)

As a fun fact, I tried fixing the reversal by sorting low to high, and
then just doing the commit_list_insert calls in that order (since it
prepends). However, that loses the stability of the sort. It turns out
that t4207 fails in this case (though not reliably, since your commits
might or might not be made in the same second).

I had already checked your mergesort() implementation to be sure that it
is stable (and it is). But it's nice to know that t4207 also backs up
the analysis. :)

-Peff

---
diff --git a/revision.c b/revision.c
index 22c26d0..15bf30a 100644
--- a/revision.c
+++ b/revision.c
@@ -2064,11 +2064,11 @@ static void set_children(struct rev_info *revs)
 
 static int commit_compare_by_date(const void *va, const void *vb)
 {
-	const struct commit *a = va;
-	const struct commit *b = vb;
-	if (a->date < b->date)
+	const struct commit *a = *(const struct commit **)va;
+	const struct commit *b = *(const struct commit **)vb;
+	if (a->date > b->date)
 		return -1;
-	if (b->date < a->date)
+	if (b->date > a->date)
 		return 1;
 	return 0;
 }

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Nguyen Thai Ngoc Duy]

On Tue, Apr 3, 2012 at 10:49 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> Has anyone looked seriously at a new index format that stores the
>> redundant information in a more easily accessible way? It would increase
>> our disk usage, but for something like linux-2.6, only by 10MB per
>> 32-bit word. On most of my systems I would gladly spare some extra RAM
>> for the disk cache if it meant I could avoid inflating a bunch of
>> objects. And this could easily be made optional for systems that don't
>> want to make the tradeoff (if it's not there, you fall back to the
>> current procedure; we could even store the data in a separate file to
>> retain indexv2 compatibility).
>>
>> So it's sort-of a cache, in that it's redundant with the actual data.
>> But staleness and writing issues are a lot simpler, since it only gets
>> updated when we index the pack (and the pack index in general is a
>> similar concept; we are "caching" the location of the object in the
>> packfile, rather than doing a linear search to look it up each time).
>
> I think I have something like that, (generate a machine-friendly
> commit cache per pack, staying in $GIT_DIR/objects/pack/ too). It's
> separate cache staying in $GIT_DIR/objects/pack, just like pack-.idx
> files. It does improve rev-list time, but I'd rather wait for packv4,
> or at least be sure that packv4 will not come anytime soon, before
> pushing the cache route.

When I looked at commit cache for rev-list, I tried to cache trees too
but the result cache was too big. I managed to shrink the tree cache
down and measured the performance gain. Sorry no code here because
it's ugly, just numbers, but you can look at the cache generation code
at [1]

On linux-2.6.git, one 521MB pack, it generates a 356MB cache and a
30MB index companion. Though if you are willing to pay extra 5 seconds
for decompressing, then the cache can go down to 94MB. We can cut
nearly half "rev-list --objects --all" time with this cache
(uncompressed cache):

$ time ~/w/git/git rev-list --objects --all --quiet </dev/null
real    2m31.310s
user    2m28.735s
sys     0m1.604s

$ time TREE_CACHE=cache ~/w/git/git rev-list --objects --all --quiet </dev/null
real    1m6.810s
user    1m6.091s
sys     0m0.708s

 $ time ~/w/git/git rev-list --all --quiet </dev/null
real    0m14.261s  # should be cut down to one third with commit cache
user    0m14.088s
sys     0m0.171s

Not really good. "rev-list --objects"'s taking less than 30s would be
nicer. lookup_object() is on top from 'perf' report with cache on. Not
sure what to do with it.

[1] https://gist.github.com/2310819
-- 
Duy

Re: [PATCH 1/3] add mergesort() for linked lists

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

> This adds a generic bottom-up mergesort implementation for singly linked
> lists.  It was inspired by Simon Tatham's webpage on the topic[1], but
> not so much by his implementation -- for no good reason, really, just a
> case of NIH.
>
> [1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
>
> Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
> +void *mergesort(void *list,
> +		void *(*get_next_fn)(const void *),
> +		void (*set_next_fn)(void *, void *),
> +		int (*compare_fn)(const void *, const void *))
> +{
> +	unsigned long l;
> +
> +	if (!list)
> +		return NULL;
> +	for (l = 1; ; l *= 2) {
> +		void *curr;
> +		struct mergesort_sublist p, q;
> +
> +		p.ptr = list;
> +		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
> +		if (!q.ptr)
> +			break;
> +		p.len = q.len = l;
> +
> +		if (compare_fn(p.ptr, q.ptr) > 0)
> +			list = curr = pop_item(&q, get_next_fn);
> +		else
> +			list = curr = pop_item(&p, get_next_fn);
> +
> +		while (p.ptr) {
> +			while (p.len || q.len) {
> +				void *prev = curr;
> +
> +				if (!p.len)
> +					curr = pop_item(&q, get_next_fn);
> +				else if (!q.len)
> +					curr = pop_item(&p, get_next_fn);
> +				else if (compare_fn(p.ptr, q.ptr) > 0)
> +					curr = pop_item(&q, get_next_fn);
> +				else
> +					curr = pop_item(&p, get_next_fn);
> +				set_next_fn(prev, curr);
> +			}
> +			p.ptr = q.ptr;
> +			p.len = l;
> +			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
> +			q.len = q.ptr ? l : 0;
> +
> +		}
> +		set_next_fn(curr, NULL);
> +	}
> +	return list;
> +}

After seeing "I wrote it myself due to NIH", it strikes me a bit odd that
you still used "start from bunch of singleton sublist, elongating twice
per round as we go" structure from the original.

I wonder if it would be an improvement if you structured the loop so that:

 (1) the first sublist 'p' grabs as many elements in the ascending order
     as you find;

 (2) the second sublist 'q' begins at the end of the first sublist and
     grabs as many elements in the ascending order;

 (3) 'p' and 'q' are merge-sorted into the result list;

 (4) if your two sublists did not cover "list" in its entirety, process
     the remainder (i.e. where the second sublist stopped because of an
     unordered element) by going back to step (1); and

 (5) if you did not need to jump back to step (1) from step (4), then you
     had only two sublists (or less), so the result is sorted.  Otherwise,
     the result now has fewer ascending sublists than the original, so go
     back to (1) and iterate.

If the input is in a random order, this may end up doing the same number
of iterations as the original, but if the input is mostly sorted, wouldn't
it allow us to take advantage of the fact by starting with a longer
sublist in the earlier rounds?

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Shawn Pearce]

On Thu, Apr 5, 2012 at 06:02, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> On linux-2.6.git, one 521MB pack, it generates a 356MB cache and a
> 30MB index companion. Though if you are willing to pay extra 5 seconds
> for decompressing, then the cache can go down to 94MB. We can cut
> nearly half "rev-list --objects --all" time with this cache
> (uncompressed cache):
>
> $ time ~/w/git/git rev-list --objects --all --quiet </dev/null
> real    2m31.310s
> user    2m28.735s
> sys     0m1.604s
>
> $ time TREE_CACHE=cache ~/w/git/git rev-list --objects --all --quiet </dev/null
> real    1m6.810s
> user    1m6.091s
> sys     0m0.708s
>
>  $ time ~/w/git/git rev-list --all --quiet </dev/null
> real    0m14.261s  # should be cut down to one third with commit cache
> user    0m14.088s
> sys     0m0.171s
>
> Not really good. "rev-list --objects"'s taking less than 30s would be
> nicer. lookup_object() is on top from 'perf' report with cache on. Not
> sure what to do with it.


My officemate Colby and I came up with a better solution a few weeks
ago, but haven't really had a chance to discuss it in on the list. I
guess I should try to do that now. Like anything else, we went into
this work with some assumptions.

There are two operations we really wanted to improve the performance
of, `git rev-list --objects` for the two commonly used cases from
pack-objects, notably `rev-list --objects $WANT` and `rev-list
--objects $WANT --not $HAVE`. That is, clone and incrementally
fetching something when you have a common ancestor. I'm currently
ignoring shallow clone in this work as it tends to be a bit less
expensive on the object enumeration part.

Working from the linux repository, with roughly 2.2M objects, we can
assume the vast majority of these objects are stored in a pack file.
If we further assume these are mostly in a single pack file, we can
easily assign every packed object a unique integer. We do this by
assigning the N-th object in the pack integer N. You can already do
this by taking the pack index and computing the reverse index, sorted
by offset in pack. Finding the integer value for any SHA-1 is then a
matter of locating its offset in the normal index, and locating the
position of it in the reverse index... a O(2 log N) operation.

With all of the packed objects named by an integer [0, N) we can build
a series of bitmaps representing reachability. Given a commit, its
bitmap has every bit set for every object that `git rev-list --objects
$COMMIT_SHA1` would output. If the pack is built from a single branch
(e.g. a repository with no tags and only a master branch), that tip
commit would have every bit set in its bitmap, as all objects in the
pack are contained in the bitmap.

A bitmap of 2.2M objects is 2.2M bits in size, and is roughly 275 KiB
worth of data. But we can compress the bitmap using word aligned
hybrid compression (WAH) [1] and have it drop to about 1 KiB in size.

Packs have fairly good locality given that they are roughly ordered by
time. The further back in history you go, the bitmap for any given
commit will start to contain more zeros than ones, and the zeros will
be roughly consecutive as the regions of the pack are less full, so
the bitmap still compresses well.

We actually did an experiment computing the bitmaps for all of the
commits in the kernel repository, IIRC the largest ones were coming in
around 40 KiB in the middle of history, and then shrinking smaller
again as you got further back in history.

Assuming all bitmaps are around 20 KiB average size (most were in this
range), storing bitmaps for every commit costs around 4.2G. Not worth
it. However.

If we take the kernel history in rev-list and pick two commits that
are roughly ~10,000 commits apart from one another, JGit can compute
the rev-list --objects between these two commits in about 120
milliseconds (git-core should be faster, or at least comparable).

Given that, we don't have to store every bitmap. Instead you store the
bitmaps about every 10,000 commits. Now your bitmap storage is closer
to 1 MiB in size for the entire pack. This can be easily appended to
the end of the pack-*.idx file as a new section when the pack is
built. The packer can construct the necessary data during packing with
what I suspect relatively little additional cost to what its already
doing, as most of the required data is in memory or being touched
anyway.

Obviously that 10k distance between bitmaps is tuneable, and could be
a config variable. We could even make it a % of the pack size, with
Git automatically selecting equidistant points between commits in the
history such that the compressed bitmaps fit within the target
percentage. Repository owners could set this to e.g. 10% and let the
machine do the rest of the work. (10% of a 560M pack might be ~56M
worth of bitmaps or every ~2800 commits.)


Computing `rev-list objects $WANT` is just a matter of OR-ing together
the bitmaps that correspond to what the client asked for. WAH
compressed bitmaps can apply OR without decompressing, in ~5ms time
range, rather than 14.2s... or 90s.  :-)

Computing `rev-list objects $WANT --not $HAVE` is likewise an OR of
the $WANT and $HAVE groups, then a negation, which again can be done
directly on the compressed bitmaps.

When the client uses a $WANT or $HAVE that we don't have a direct
bitmap for, build the bitmap on the fly by running `rev-list $WANT`
(or $HAVE) until the revision traversal produces a commit that does
have a bitmap. Extend the bitmap with the additional objects that
aren't in the pack by assigning them new temporary integers that are
larger than the number of objects in the pack. Finish the operation
with the bitmaps.


To output the pack we don't even need to build up a huge list of
struct packed_obj in memory. Instead we iterate the set bits in the
bitmap, working off the compressed format. When an object has its bit
set, it needs to be sent to the client. The object can be found in the
pack by looking at the N-th position of the reverse index to get its
offset, or the N-th position in the reverse index to get its SHA-1.
Copying slices of pack data should be a pretty simple task. The bits
are already sorted by preferred pack order, since they came from a
pack, so the writer still produces a good stream. Obviously if you
want to change the ordering, or the deltas, aka repack -f, we need to
avoid using the bitmap ordering here.

There is some complication relating to swapping out delta compressed
form for non-delta compressed form if you cannot prove the peer has
the delta base that is currently being used. But with the bitmaps we
actually have a much more accurate representation of what the client
*actually* has. Instead of being limited to the common ancestor
negotiation point's trees, the $HAVE bitmap covers *every single
object to the beginning of time*. This significantly increases the
number of candidates available for delta reuse, because there are
better chances that the base we use is already available to the
client.

The $HAVE bitmap covering a much bigger section of history also means
we transmit fewer objects, which makes for a faster transfer for the
client. This often happens with cherry-picks or reverts across the
common ancestor cut point in the graph, where the peer already has the
relevant object(s) but we can't prove it from the limited section of
history we look at today. The $HAVE bitmap is much more comprehensive
picture of the client's state, making for a smaller transfer.


Having multiple packs is common, and does complicate this algorithm.
There are known ways to combine different bitmap indexes together to
create a single larger bitmap, mostly by applying a unique "base
prefix" to each bitmap's values. Its very common in the full text
search community to do this when incrementally updating a full text
index.

A process can assign each pack it observes a unique base prefix, and
then join together bitmaps across those packs to get a more complete
picture. Its not entirely that simple though because a commit in a
newer pack probably still references a parent in an older pack, and so
that commit in the newer pack doesn't have a complete bitmap.

One way out of this is to only produce bitmaps on a full GC, where the
entire repository is rewritten. If every 10k commits worth of history
costs about 100ms additional processing time to do object enumeration,
we only really have to do a major repack about every 100k commits when
processing is starting to come close to 1.2 seconds of CPU time. The
linux history has done ~220k commits in ~5 years, or 44k commits/year.
Asking a repository to do a full GC at least once per year so that
there only needs to be one set of bitmaps might be acceptable. :-)


The other operation that matters is `git rev-list --objects $NEW --not
--all`, which is done for a reachability test during receive of data
into a repository from the network (in either fetch or receive-pack).

If we know a pack was created locally by the git gc or git repack
command, we only need to run `git rev-list --objects $NEW` and stop
traversal for a section of the graph when we find a commit or object
that already exists in a locally created pack index. In other words we
don't use the "--not --all" bit and we instead we look at each object
coming out of the traversal to see if it is in a locally created pack,
if it exists in a pack's index we mark it UNINTERESTING and continue
the traversal. This would eliminate the need to parse and load --all
into the priority queue, instead we parse and insert only the commits
that are directly connected to the part of the $NEW graph we were just
given, and we only do that so we can stop traversal at the common
ancestor point(s) and avoid walking back to the root. It probably
isn't even necessary to parse or insert these commits, we just have to
tag them UNINTERESTING and avoid putting them into the priority queue.

However not all locally stored packs were locally created. Some are
created from the network (e.g. when the number of objects is > 100).
So for this optimization to work we need an additional chunk of
metadata written with the pack to say "this pack was made by git gc /
git repack and is trustworthy". This could be a new ".local" file
alongside .pack/.idx, or we could do a minor change to the .idx format
to allow a "source bit" to be written to say where the pack came from
(network or fast-import vs. local gc).


I think a lot of the other users of the commit graph / object graph
are just looking at small enough slices of history that walking
through 10k commits in 120 ms is acceptable response time to the human
running the command. So its not really pack v4. It only needs a few
MiB additional space on top of existing pack data, and is easily
stored onto the end of the local index file. But it gets us a lot of
improvement in some pretty tough areas.


I don't have any code to share, because we haven't written it yet. But
this should shave off some of the big corners within Git, with
relatively little additional disk usage.


[1] "Sorting improves word-aligned bitmap indexes", Daniel Lemire,
Owen Kaser, Kamel Aouiche
    http://arxiv.org/abs/0901.3751

Re: [PATCH 3/3] revision: insert unsorted, then sort in prepare_revision_walk()

[Nguyen Thai Ngoc Duy]

Hi,

Very insightful write-up. I'll need more time to read through again,
just some initial opinions.

On Sat, Apr 7, 2012 at 2:21 AM, Shawn Pearce <spearce@spearce.org> wrote:
> My officemate Colby and I came up with a better solution a few weeks
> ago, but haven't really had a chance to discuss it in on the list. I
> guess I should try to do that now. Like anything else, we went into
> this work with some assumptions.
>
> There are two operations we really wanted to improve the performance
> of, `git rev-list --objects` for the two commonly used cases from
> pack-objects, notably `rev-list --objects $WANT` and `rev-list
> --objects $WANT --not $HAVE`. That is, clone and incrementally
> fetching something when you have a common ancestor. I'm currently
> ignoring shallow clone in this work as it tends to be a bit less
> expensive on the object enumeration part.
>
> Working from the linux repository, with roughly 2.2M objects, we can
> assume the vast majority of these objects are stored in a pack file.
> If we further assume these are mostly in a single pack file, we can
> easily assign every packed object a unique integer. We do this by
> assigning the N-th object in the pack integer N. You can already do
> this by taking the pack index and computing the reverse index, sorted
> by offset in pack. Finding the integer value for any SHA-1 is then a
> matter of locating its offset in the normal index, and locating the
> position of it in the reverse index... a O(2 log N) operation.
>
> With all of the packed objects named by an integer [0, N) we can build
> a series of bitmaps representing reachability. Given a commit, its
> bitmap has every bit set for every object that `git rev-list --objects
> $COMMIT_SHA1` would output. If the pack is built from a single branch
> (e.g. a repository with no tags and only a master branch), that tip
> commit would have every bit set in its bitmap, as all objects in the
> pack are contained in the bitmap.
>
> ...
>
> Having multiple packs is common, and does complicate this algorithm.
> There are known ways to combine different bitmap indexes together to
> create a single larger bitmap, mostly by applying a unique "base
> prefix" to each bitmap's values. Its very common in the full text
> search community to do this when incrementally updating a full text
> index.

Common repos usually have a big pack as a result of clone and several
smaller packs. How about we create the bitmap for the largest pack
only and fall back to normal rev walking for the rest? We need to deal
with loose objects anyway. I wonder if we could also mark the boundary
objects for a given commits (i.e. another bitmap) so we can start
walking from there to get to other packs and loose objects.

The second bitmap hopefully compresses well. Not sure how it
complicates the want-have bitmap operations you describe above though.

> A process can assign each pack it observes a unique base prefix, and
> then join together bitmaps across those packs to get a more complete
> picture. Its not entirely that simple though because a commit in a
> newer pack probably still references a parent in an older pack, and so
> that commit in the newer pack doesn't have a complete bitmap.
>
> One way out of this is to only produce bitmaps on a full GC, where the
> entire repository is rewritten. If every 10k commits worth of history
> costs about 100ms additional processing time to do object enumeration,
> we only really have to do a major repack about every 100k commits when
> processing is starting to come close to 1.2 seconds of CPU time. The
> linux history has done ~220k commits in ~5 years, or 44k commits/year.
> Asking a repository to do a full GC at least once per year so that
> there only needs to be one set of bitmaps might be acceptable. :-)

I'd be happy for it to run, even once a month, as long as it is not
run automatically, unexpectedly and stops me from doing whatever I'm
doing, like "gc --auto".
-- 
Duy

Re: [PATCH 1/3] add mergesort() for linked lists

[René Scharfe]

Am 05.04.2012 21:17, schrieb Junio C Hamano:
> After seeing "I wrote it myself due to NIH", it strikes me a bit odd that
> you still used "start from bunch of singleton sublist, elongating twice
> per round as we go" structure from the original.

It's just becasue the dumb bottom-up approach is the most simple way to
implement merge sort.

> I wonder if it would be an improvement if you structured the loop so that:
> 
>   (1) the first sublist 'p' grabs as many elements in the ascending order
>       as you find;
> 
>   (2) the second sublist 'q' begins at the end of the first sublist and
>       grabs as many elements in the ascending order;
> 
>   (3) 'p' and 'q' are merge-sorted into the result list;
> 
>   (4) if your two sublists did not cover "list" in its entirety, process
>       the remainder (i.e. where the second sublist stopped because of an
>       unordered element) by going back to step (1); and
> 
>   (5) if you did not need to jump back to step (1) from step (4), then you
>       had only two sublists (or less), so the result is sorted.  Otherwise,
>       the result now has fewer ascending sublists than the original, so go
>       back to (1) and iterate.
> 
> If the input is in a random order, this may end up doing the same number
> of iterations as the original, but if the input is mostly sorted, wouldn't
> it allow us to take advantage of the fact by starting with a longer
> sublist in the earlier rounds?

This optimization speeds up the pre-sorted case but slows down the case of
a reversed pre-sorted list because we have to determine the length of the
sublists each time, while the dumb implementation already knows it.  I
didn't measure a significant difference for Jeff's test case.  Here's my
attempt at an implementation, for reference.

---
 mergesort.c |   61 +++++++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 41 insertions(+), 20 deletions(-)

diff --git a/mergesort.c b/mergesort.c
index c0f1874..3a61b9b 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -8,12 +8,37 @@ struct mergesort_sublist {
 	unsigned long len;
 };
 
-static void *get_nth_next(void *list, unsigned long n,
-			  void *(*get_next_fn)(const void *))
+static unsigned long run_length(const void *list,
+				struct mergesort_sublist *next_list,
+				void *(*get_next_fn)(const void *),
+				int (*compare_fn)(const void *, const void *))
 {
-	while (n-- && list)
-		list = get_next_fn(list);
-	return list;
+	unsigned long len = 1;
+
+	if (!list)
+		return 0;
+	for (;;) {
+		void *next = get_next_fn(list);
+
+		if (!next || compare_fn(list, next) > 0) {
+			if (next_list)
+				next_list->ptr = next;
+			break;
+		}
+		list = next;
+		len++;
+	}
+	return len;
+}
+
+static void set_next_pair(struct mergesort_sublist *p,
+			  struct mergesort_sublist *q, void *list,
+			  void *(*get_next_fn)(const void *),
+			  int (*compare_fn)(const void *, const void *))
+{
+	p->ptr = list;
+	p->len = run_length(p->ptr, q, get_next_fn, compare_fn);
+	q->len = q->ptr ? run_length(q->ptr, NULL, get_next_fn, compare_fn) : 0;
 }
 
 static void *pop_item(struct mergesort_sublist *l,
@@ -30,24 +55,16 @@ void *mergesort(void *list,
 		void (*set_next_fn)(void *, void *),
 		int (*compare_fn)(const void *, const void *))
 {
-	unsigned long l;
-
 	if (!list)
 		return NULL;
-	for (l = 1; ; l *= 2) {
+	for (;;) {
 		void *curr;
 		struct mergesort_sublist p, q;
 
-		p.ptr = list;
-		q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+		set_next_pair(&p, &q, list, get_next_fn, compare_fn);
 		if (!q.ptr)
 			break;
-		p.len = q.len = l;
-
-		if (compare_fn(p.ptr, q.ptr) > 0)
-			list = curr = pop_item(&q, get_next_fn);
-		else
-			list = curr = pop_item(&p, get_next_fn);
+		list = curr = pop_item(&q, get_next_fn);
 
 		while (p.ptr) {
 			while (p.len || q.len) {
@@ -63,10 +80,14 @@ void *mergesort(void *list,
 					curr = pop_item(&p, get_next_fn);
 				set_next_fn(prev, curr);
 			}
-			p.ptr = q.ptr;
-			p.len = l;
-			q.ptr = get_nth_next(p.ptr, l, get_next_fn);
-			q.len = q.ptr ? l : 0;
+
+			set_next_pair(&p, &q, q.ptr, get_next_fn, compare_fn);
+			if (q.ptr) {
+				void *prev = curr;
+
+				curr = pop_item(&q, get_next_fn);
+				set_next_fn(prev, curr);
+			}
 
 		}
 		set_next_fn(curr, NULL);
-- 
1.7.10

Re: [PATCH 1/3] add mergesort() for linked lists

[Junio C Hamano]

René Scharfe <rene.scharfe@lsrfire.ath.cx> writes:

> Am 05.04.2012 21:17, schrieb Junio C Hamano:
>> After seeing "I wrote it myself due to NIH", it strikes me a bit odd that
>> you still used "start from bunch of singleton sublist, elongating twice
>> per round as we go" structure from the original.
>
> It's just becasue the dumb bottom-up approach is the most simple way to
> implement merge sort.
> ...
> This optimization speeds up the pre-sorted case but slows down the case of
> a reversed pre-sorted list because we have to determine the length of the
> sublists each time,...

Ah, I somehow missed that point.  Thanks.

Re: [PATCH 1/3] add mergesort() for linked lists

[Stephen Boyd]

On 03/31/2012 03:10 PM, René Scharfe wrote:
> diff --git a/mergesort.c b/mergesort.c
> new file mode 100644
> index 0000000..c0f1874
> --- /dev/null
> +++ b/mergesort.c
> @@ -0,0 +1,75 @@
> +#include "cache.h"
> +#include "mergesort.h"
> +
> +#include "commit.h"

This is an unnecessary include, right?

diff --git a/mergesort.c b/mergesort.c
index c0f1874..d084c60 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -1,8 +1,6 @@
 #include "cache.h"
 #include "mergesort.h"

-#include "commit.h"
-
 struct mergesort_sublist {
        void *ptr;
        unsigned long len;

Re: [PATCH 1/3] add mergesort() for linked lists

[Junio C Hamano]

Stephen Boyd <bebarino@gmail.com> writes:

> On 03/31/2012 03:10 PM, René Scharfe wrote:
>> diff --git a/mergesort.c b/mergesort.c
>> new file mode 100644
>> index 0000000..c0f1874
>> --- /dev/null
>> +++ b/mergesort.c
>> @@ -0,0 +1,75 @@
>> +#include "cache.h"
>> +#include "mergesort.h"
>> +
>> +#include "commit.h"
>
> This is an unnecessary include, right?
>
> diff --git a/mergesort.c b/mergesort.c
> index c0f1874..d084c60 100644
> --- a/mergesort.c
> +++ b/mergesort.c
> @@ -1,8 +1,6 @@
>  #include "cache.h"
>  #include "mergesort.h"
>
> -#include "commit.h"
> -
>  struct mergesort_sublist {
>         void *ptr;
>         unsigned long len;

Yes. I'll squash in, as I tentatively kicked many topics out of 'next' and
this was among them.