[PATCH] Optimization for git-rev-list --objects

[PATCH] Optimization for git-rev-list --objects

[Alexandre Julliard]

When building a large list of objects, most of the time is spent in
created_object() inserting the objects in the sorted list. This patch
splits the list in 256 sublists to reduce the impact of the O(n^2)
list insertion.

On the WineHQ repository (220,000 objects), the patch reduces the time
needed for a 'git-rev-list --objects HEAD' from 2 minutes to 20 seconds.

Signed-off-by: Alexandre Julliard <julliard@winehq.org>

---

 fsck-objects.c |   66 +++++++++++++++++++++++++++++---------------------------
 name-rev.c     |    9 ++++----
 object.c       |   24 ++++++++++----------
 object.h       |    4 ++-
 4 files changed, 53 insertions(+), 50 deletions(-)

68f8fcb7f5883ecc44a80e822e0b78ee8efd9eb9
diff --git a/fsck-objects.c b/fsck-objects.c
index 9950be2..5bdb21e 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -58,45 +58,47 @@ static int objwarning(struct object *obj
 
 static void check_connectivity(void)
 {
-	int i;
+	int i, j;
 
 	/* Look up all the requirements, warn about missing objects.. */
-	for (i = 0; i < nr_objs; i++) {
-		struct object *obj = objs[i];
+	for (i = 0; i < 256; i++) {
+		for (j = 0; j < nr_objs[i]; j++) {
+			struct object *obj = objs[i][j];
 
-		if (!obj->parsed) {
-			if (!standalone && has_sha1_file(obj->sha1))
-				; /* it is in pack */
-			else
-				printf("missing %s %s\n",
-				       obj->type, sha1_to_hex(obj->sha1));
-			continue;
-		}
+			if (!obj->parsed) {
+				if (!standalone && has_sha1_file(obj->sha1))
+					; /* it is in pack */
+				else
+					printf("missing %s %s\n",
+					       obj->type, sha1_to_hex(obj->sha1));
+				continue;
+			}
 
-		if (obj->refs) {
-			const struct object_refs *refs = obj->refs;
-			unsigned j;
-			for (j = 0; j < refs->count; j++) {
-				struct object *ref = refs->ref[j];
-				if (ref->parsed ||
-				    (!standalone && has_sha1_file(ref->sha1)))
-					continue;
-				printf("broken link from %7s %s\n",
-				       obj->type, sha1_to_hex(obj->sha1));
-				printf("              to %7s %s\n",
-				       ref->type, sha1_to_hex(ref->sha1));
+			if (obj->refs) {
+				const struct object_refs *refs = obj->refs;
+				unsigned k;
+				for (k = 0; k < refs->count; k++) {
+					struct object *ref = refs->ref[k];
+					if (ref->parsed ||
+					    (!standalone && has_sha1_file(ref->sha1)))
+						continue;
+					printf("broken link from %7s %s\n",
+					       obj->type, sha1_to_hex(obj->sha1));
+					printf("              to %7s %s\n",
+					       ref->type, sha1_to_hex(ref->sha1));
+				}
 			}
-		}
 
-		if (show_unreachable && !(obj->flags & REACHABLE)) {
-			printf("unreachable %s %s\n",
-			       obj->type, sha1_to_hex(obj->sha1));
-			continue;
-		}
+			if (show_unreachable && !(obj->flags & REACHABLE)) {
+				printf("unreachable %s %s\n",
+				       obj->type, sha1_to_hex(obj->sha1));
+				continue;
+			}
 
-		if (!obj->used) {
-			printf("dangling %s %s\n", obj->type, 
-			       sha1_to_hex(obj->sha1));
+			if (!obj->used) {
+				printf("dangling %s %s\n", obj->type, 
+				       sha1_to_hex(obj->sha1));
+			}
 		}
 	}
 }
diff --git a/name-rev.c b/name-rev.c
index bbadb91..9a8d086 100644
--- a/name-rev.c
+++ b/name-rev.c
@@ -230,11 +230,12 @@ int main(int argc, char **argv)
 				fwrite(p_start, p - p_start, 1, stdout);
 		}
 	} else if (all) {
-		int i;
+		int i, j;
 
-		for (i = 0; i < nr_objs; i++)
-			printf("%s %s\n", sha1_to_hex(objs[i]->sha1),
-					get_rev_name(objs[i]));
+		for (i = 0; i < 256; i++)
+			for (j = 0; j < nr_objs[i]; j++)
+				printf("%s %s\n", sha1_to_hex(objs[i][j]->sha1),
+						get_rev_name(objs[i][j]));
 	} else
 		for ( ; revs; revs = revs->next)
 			printf("%s %s\n", revs->name, get_rev_name(revs->item));
diff --git a/object.c b/object.c
index 1577f74..fcd4d0c 100644
--- a/object.c
+++ b/object.c
@@ -5,19 +5,19 @@
 #include "commit.h"
 #include "tag.h"
 
-struct object **objs;
-int nr_objs;
-static int obj_allocs;
+struct object **objs[256];
+int nr_objs[256];
+static int obj_allocs[256];
 
 int track_object_refs = 1;
 
 static int find_object(const unsigned char *sha1)
 {
-	int first = 0, last = nr_objs;
+	int first = 0, last = nr_objs[*sha1];
 
         while (first < last) {
                 int next = (first + last) / 2;
-                struct object *obj = objs[next];
+                struct object *obj = objs[*sha1][next];
                 int cmp;
 
                 cmp = memcmp(sha1, obj->sha1, 20);
@@ -36,7 +36,7 @@ struct object *lookup_object(const unsig
 {
 	int pos = find_object(sha1);
 	if (pos >= 0)
-		return objs[pos];
+		return objs[*sha1][pos];
 	return NULL;
 }
 
@@ -54,17 +54,17 @@ void created_object(const unsigned char 
 		die("Inserting %s twice\n", sha1_to_hex(sha1));
 	pos = -pos-1;
 
-	if (obj_allocs == nr_objs) {
-		obj_allocs = alloc_nr(obj_allocs);
-		objs = xrealloc(objs, obj_allocs * sizeof(struct object *));
+	if (obj_allocs[*sha1] == nr_objs[*sha1]) {
+		obj_allocs[*sha1] = alloc_nr(obj_allocs[*sha1]);
+		objs[*sha1] = xrealloc(objs[*sha1], obj_allocs[*sha1] * sizeof(struct object *));
 	}
 
 	/* Insert it into the right place */
-	memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * 
+	memmove(objs[*sha1] + pos + 1, objs[*sha1] + pos, (nr_objs[*sha1] - pos) * 
 		sizeof(struct object *));
 
-	objs[pos] = obj;
-	nr_objs++;
+	objs[*sha1][pos] = obj;
+	nr_objs[*sha1]++;
 }
 
 struct object_refs *alloc_object_refs(unsigned count)
diff --git a/object.h b/object.h
index 0e76182..dcd6ac4 100644
--- a/object.h
+++ b/object.h
@@ -23,8 +23,8 @@ struct object {
 };
 
 extern int track_object_refs;
-extern int nr_objs;
-extern struct object **objs;
+extern int nr_objs[256];
+extern struct object **objs[256];
 
 /** Internal only **/
 struct object *lookup_object(const unsigned char *sha1);
-- 
1.1.6.g68f8


-- 
Alexandre Julliard
julliard@winehq.org

[PATCH] Use a hashtable for objects instead of a sorted list

[Johannes Schindelin]

In a simple test, this brings down the CPU time from 47 sec to 22 sec.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>

---

	On Sat, 11 Feb 2006, Alexandre Julliard wrote:

	> When building a large list of objects, most of the time is spent in
	> created_object() inserting the objects in the sorted list. This patch
	> splits the list in 256 sublists to reduce the impact of the O(n^2)
	> list insertion.

	Your patch brought down the CPU time to 27 sec in my test.

 fsck-objects.c |    5 +++-
 name-rev.c     |    7 +++---
 object.c       |   67 +++++++++++++++++++++++++++++++++-----------------------
 object.h       |    2 +-
 4 files changed, 48 insertions(+), 33 deletions(-)

diff --git a/fsck-objects.c b/fsck-objects.c
index 9950be2..6439d55 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -61,9 +61,12 @@ static void check_connectivity(void)
 	int i;
 
 	/* Look up all the requirements, warn about missing objects.. */
-	for (i = 0; i < nr_objs; i++) {
+	for (i = 0; i < obj_allocs; i++) {
 		struct object *obj = objs[i];
 
+		if (!obj)
+			continue;
+
 		if (!obj->parsed) {
 			if (!standalone && has_sha1_file(obj->sha1))
 				; /* it is in pack */
diff --git a/name-rev.c b/name-rev.c
index bdaa59b..08faa54 100644
--- a/name-rev.c
+++ b/name-rev.c
@@ -303,9 +303,10 @@ int main(int argc, char **argv)
 	} else if (all) {
 		int i;
 
-		for (i = 0; i < nr_objs; i++)
-			printf("%s %s\n", sha1_to_hex(objs[i]->sha1),
-					get_rev_name(objs[i]));
+		for (i = 0; i < obj_allocs; i++)
+			if (objs[i])
+				printf("%s %s\n", sha1_to_hex(objs[i]->sha1),
+						get_rev_name(objs[i]));
 	} else
 		for ( ; revs; revs = revs->next)
 			printf("%s %s\n", revs->name, get_rev_name(revs->item));
diff --git a/object.c b/object.c
index 1577f74..3259862 100644
--- a/object.c
+++ b/object.c
@@ -6,30 +6,32 @@
 #include "tag.h"
 
 struct object **objs;
-int nr_objs;
-static int obj_allocs;
+static int nr_objs;
+int obj_allocs;
 
 int track_object_refs = 1;
 
+static int hashtable_index(const unsigned char *sha1)
+{
+	unsigned int i = *(unsigned int *)sha1;
+	return (int)(i % obj_allocs);
+}
+
 static int find_object(const unsigned char *sha1)
 {
-	int first = 0, last = nr_objs;
+	int i = hashtable_index(sha1);
+
+	if (!objs)
+		return -1;
 
-        while (first < last) {
-                int next = (first + last) / 2;
-                struct object *obj = objs[next];
-                int cmp;
-
-                cmp = memcmp(sha1, obj->sha1, 20);
-                if (!cmp)
-                        return next;
-                if (cmp < 0) {
-                        last = next;
-                        continue;
-                }
-                first = next+1;
-        }
-        return -first-1;
+	while (objs[i]) {
+		if (memcmp(sha1, objs[i]->sha1, 20) == 0)
+			return i;
+		i++;
+		if (i == obj_allocs)
+			i = 0;
+	}
+	return -1 - i;
 }
 
 struct object *lookup_object(const unsigned char *sha1)
@@ -42,7 +44,7 @@ struct object *lookup_object(const unsig
 
 void created_object(const unsigned char *sha1, struct object *obj)
 {
-	int pos = find_object(sha1);
+	int pos;
 
 	obj->parsed = 0;
 	memcpy(obj->sha1, sha1, 20);
@@ -50,18 +52,27 @@ void created_object(const unsigned char 
 	obj->refs = NULL;
 	obj->used = 0;
 
-	if (pos >= 0)
-		die("Inserting %s twice\n", sha1_to_hex(sha1));
-	pos = -pos-1;
-
-	if (obj_allocs == nr_objs) {
-		obj_allocs = alloc_nr(obj_allocs);
+	if (obj_allocs - 1 <= nr_objs * 2) {
+		int i, count = obj_allocs;
+		obj_allocs = (obj_allocs < 32 ? 32 : 2 * obj_allocs);
 		objs = xrealloc(objs, obj_allocs * sizeof(struct object *));
+		memset(objs + count, 0, (obj_allocs - count)
+				* sizeof(struct object *));
+		for (i = 0; i < count; i++)
+			if (objs[i]) {
+				int j = find_object(objs[i]->sha1);
+				if (j != i) {
+					j = -1 - j;
+					objs[j] = objs[i];
+					objs[i] = NULL;
+				}
+			}
 	}
 
-	/* Insert it into the right place */
-	memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * 
-		sizeof(struct object *));
+	pos = find_object(sha1);
+	if (pos >= 0)
+		die("Inserting %s twice\n", sha1_to_hex(sha1));
+	pos = -pos-1;
 
 	objs[pos] = obj;
 	nr_objs++;
diff --git a/object.h b/object.h
index 0e76182..e08afbd 100644
--- a/object.h
+++ b/object.h
@@ -23,7 +23,7 @@ struct object {
 };
 
 extern int track_object_refs;
-extern int nr_objs;
+extern int obj_allocs;
 extern struct object **objs;
 
 /** Internal only **/

Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> In a simple test, this brings down the CPU time from 47 sec to 22 sec.

I was planning to take Alexandre's patch, but the approach your
patch takes feels more correct -- it scales with the number of
objects you need to handle, instead of having fixed 256
hashbuckets.

BTW, your version dumped core in hashtable_index immediately
after I started "git-rev-list --objects HEAD".  How did you get
_any_ CPU time?

I am not sure expecting that object name pointers are always
(unsigned int *) aligned as your patch does is OK.  We may want
to have something like the attached patch on top of yours.

I am also interested to find out how much the rehashing you do
when you update obj_allocs to a larger value is costing.

Alexandle, if you have a chance, could you try Johannes' patch
on your workload to see if it works OK for you?

-- >8 --
[PATCH] do not assume object name pointers are uint aligned.

Also fix an obvious bug that caused it dump core at my first
attempt.  There might be others but I did not actively look for
them.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---
diff --git a/object.c b/object.c
index 3259862..59e5e36 100644
--- a/object.c
+++ b/object.c
@@ -13,17 +13,24 @@ int track_object_refs = 1;
 
 static int hashtable_index(const unsigned char *sha1)
 {
-	unsigned int i = *(unsigned int *)sha1;
-	return (int)(i % obj_allocs);
+	int cnt;
+	unsigned int ix = *sha1++;
+
+	for (cnt = 1; cnt < sizeof(unsigned int); cnt++) {
+		ix <<= 8;
+		ix |= *sha1++;
+	}
+	return (int)(ix % obj_allocs);
 }
 
 static int find_object(const unsigned char *sha1)
 {
-	int i = hashtable_index(sha1);
+	int i;
 
 	if (!objs)
 		return -1;
 
+	i = hashtable_index(sha1);
 	while (objs[i]) {
 		if (memcmp(sha1, objs[i]->sha1, 20) == 0)
 			return i;

Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Alexandre Julliard]

Junio C Hamano <junkio@cox.net> writes:

> I am also interested to find out how much the rehashing you do
> when you update obj_allocs to a larger value is costing.
>
> Alexandle, if you have a chance, could you try Johannes' patch
> on your workload to see if it works OK for you?

It works great for me, CPU time is down to 15 sec instead of 20 sec
with my patch.

-- 
Alexandre Julliard
julliard@winehq.org

Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Junio C Hamano]

Alexandre Julliard <julliard@winehq.org> writes:

> Junio C Hamano <junkio@cox.net> writes:
>
>> Alexandle, if you have a chance, could you try Johannes' patch
>> on your workload to see if it works OK for you?
>
> It works great for me, CPU time is down to 15 sec instead of 20 sec
> with my patch.

Thanks.  Now we have three independent numbers to back up that
Johannes is the winner....

Grrrrrrr.  Please, DO NOT USE THIS ONE YET.

At least, not with your production repository.

I am trying to nail it down but it appears at least fsck-objects
using this version gives bogus results.  I am first trying to
see if my primary working repository is sane.

Oh, and thanks again for your initial patch, which was what
started this drastic improvement.

Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Johannes Schindelin]

Hi,

On Sun, 12 Feb 2006, Junio C Hamano wrote:

> Alexandre Julliard <julliard@winehq.org> writes:
> 
> > Junio C Hamano <junkio@cox.net> writes:
> >
> >> Alexandle, if you have a chance, could you try Johannes' patch
> >> on your workload to see if it works OK for you?
> >
> > It works great for me, CPU time is down to 15 sec instead of 20 sec
> > with my patch.
> 
> Thanks.  Now we have three independent numbers to back up that
> Johannes is the winner....
> 
> Grrrrrrr.  Please, DO NOT USE THIS ONE YET.
> 
> At least, not with your production repository.
> 
> I am trying to nail it down but it appears at least fsck-objects
> using this version gives bogus results.  I am first trying to
> see if my primary working repository is sane.
> 
> Oh, and thanks again for your initial patch, which was what
> started this drastic improvement.

I am sorry! I tested fsck, but only *once*, since I did not think such a 
creepy bug was in there. And then, I had to run to sing Beethoven's Missa 
Solemnis, and missed all the action about this patch.

Just a few remarks around the comments in this thread:

- the doubling of obj_allocs is arbitrary. Originally, I planned to do the 
growing much faster, which would have been helped by the fact. But it 
turned out my thinking was defective. So, you can grow the hashtable by 
whatever you like (doubling is quite effective, though).

- hashtable has expected O(1) insertion, and that is what boosts the 
performance. Since the table growing is linear in the number of objects 
(both size and computing time), and all operations afterwards are linear 
on the table, *and the hash is already computed*, the hashtable is 
preferrable over other data structures (sorted list has O(n) insertion 
time, and tree still O(log n)).

- the bug Junio fixed was not triggered here, since I did all the testing 
on my venerable iBook. The PowerPC architecture evidently aligns 
all pointers to 32-bit, so I could reinterpret the pointer as to an 
unsigned int. Note that there is a small overhead in Junio's version, but 
it is probably not worth the hassle to make that a compile time option. 
But I agree with Florian that memcpy would be more efficient.

- Arithmetic and Boolean operations on 32-bit integers typically are 
handled very efficiently in modern 32-bit CPUs, so there should be no 
reason to use "&" instead of "%" (especially since understanding the code 
wouldn't be helped by that).

Ciao,
Dscho

Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Florian Weimer]

* Junio C. Hamano:

>  static int hashtable_index(const unsigned char *sha1)
>  {
> -	unsigned int i = *(unsigned int *)sha1;
> -	return (int)(i % obj_allocs);
> +	int cnt;

> +	unsigned int ix = *sha1++;
> +
> +	for (cnt = 1; cnt < sizeof(unsigned int); cnt++) {
> +		ix <<= 8;
> +		ix |= *sha1++;
> +	}

memcpy(&ix, sha1, sizeof(ix));

(GCC should do the rest.)

> +	return (int)(ix % obj_allocs);
>  }

return (int)(ix & (obj_allocs - 1));

AFAICS, obj_allocs is a power of two.

***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Junio C Hamano]

Florian Weimer <fw@deneb.enyo.de> writes:

> (GCC should do the rest.)
>...
> AFAICS, obj_allocs is a power of two.

Yes, I already have something like these in my tree (the latter
did not help much as far as I could tell, though).

****HOWEVER****

Do not use this (not just my patch but with the whole hashtable
version) in your production repository yet.

I've got a mysterious corruption and bogus output from
fsck-objects, and have been tracking it (see the timestamp of
this message).

1.2.0 will most likely to be be *delayed*.  I have to first make
sure my private repository is sane.  Grrrrrrrr.

***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Junio C Hamano]

I've pushed things out to "master" and "next" branch.

Quite a lot of things.

One thing that I expected to be there is not.  It is the
hashtable patch.  It is in "pu".

I once had it in my private "next", but dropped it before
pushing things out.

The problem does not seem to trigger with casual use, but I
found that with a clone from my primary repository with '-l -s'
(that is, a clone that uses alternates mechanism to borrow from
my primary repository), fsck-objects built with the patch seems
to report bogus things "missing".  I have not traced it fully;
instead I ended up spending most of the night (I noticed it at
around 01:30 and now it is 05:30 so that's about four hours)
recovering some of my refs and double checking if my primary
repository is not corrupt X-<.  At least, the primary repository
looks sane now.

With luck, I would muster enough energy to figure it out, but I
need some sleep first.

The problem seems to be very elusive.  I took a snapshot of the
two repositories involved, so that I can use them as an isolated
test case (the one is my primary repository and the other one is
the "-l -s" clone). The problem is repeatable, but the SHA1 of
the file the broken fsck-objects reports to be missing is
different from the one I observed in the first experiment with
the real repositories.  It appears it has something to do with
the directory listing order of fsck-objects, which in turn means
the reproduction of the problem is related to memory allocation
patterns, so maybe valgrind would help.  On the other hand, even
if I published a tarball of these two repositories somewhere,
other people (or myself) who extract the tarball would probably
not see the same SHA1 reported as missing X-<.

Anyway, I've pushed them out before crashing, after I double
checked that versions built from my "master" and "next" do not
seem to show the problem, while with the one in "pu", the first
patch after merging "next" in it being the said patch, exhibits
the problem.

Re: ***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Johannes Schindelin]

Hi,

On Sun, 12 Feb 2006, Junio C Hamano wrote:

> The problem does not seem to trigger with casual use, but I
> found that with a clone from my primary repository with '-l -s'
> (that is, a clone that uses alternates mechanism to borrow from
> my primary repository), fsck-objects built with the patch seems
> to report bogus things "missing".  I have not traced it fully;
> instead I ended up spending most of the night (I noticed it at
> around 01:30 and now it is 05:30 so that's about four hours)
> recovering some of my refs and double checking if my primary
> repository is not corrupt X-<.  At least, the primary repository
> looks sane now.

Could it be the shallow thing?

+
+void for_each_object(void (*fn)(struct object *))
+{
+       int i;
+       for (i = 0; i < nr_objs; i++)
+               fn(objs[i]);
+}

This will not work with the hashtable. It has to be something like


void for_each_object(void (*fn)(struct object *))
{
       int i;
       for (i = 0; i < obj_allocs; i++)
               if (objs[i])
			fn(objs[i]);
}

This error did not trigger here, since I don't use shallow clones.

Again, sorry for the inconvenience, Junio.

Hth,
Dscho

Re: ***DONTUSE*** Re: [PATCH] Use a hashtable for objects instead of a sorted list

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Could it be the shallow thing?

No, I do not think so.  In the current "master", "next", "pu"
picture, "pu" merges js/obj with the "8856cc69" commit and then
shallow and bind comes later.  That merged version is what I am
testing, and also its second parent, which is "master" plus
hashtable.  In either case, shallow and bind are not part of the
picture.

> Again, sorry for the inconvenience, Junio.

That is not your fault, and I did not mean to sound I am unhappy
about *you*.  I am indeed unhappy because I did not see anything
obviously or subtly wrong with your patch after I moved call to
hashtable_index() in find_object().

But I think Linus nailed it.  I'll see if I can understand his
explanation.

Re: [PATCH] Optimization for git-rev-list --objects

[Linus Torvalds]

On Sat, 11 Feb 2006, Alexandre Julliard wrote:
> 
> When building a large list of objects, most of the time is spent in
> created_object() inserting the objects in the sorted list. This patch
> splits the list in 256 sublists to reduce the impact of the O(n^2)
> list insertion.
> 
> On the WineHQ repository (220,000 objects), the patch reduces the time
> needed for a 'git-rev-list --objects HEAD' from 2 minutes to 20 seconds.

Goodie. However, I wonder if we care about the sorting at _all_.

The sorting really only helps "find_object()", and the thing is, we could 
certainly do that other ways too. Keeping a sorted list is kind of 
senseless, when the data is so amenable to be kept in a tree.

We could add left/right pointers to each object, and just keep them in a 
tree. We probably don't even need any fancy balancing, since hashing means 
that we could just keep the first object we ever allocate as the root, and 
things should normally be pretty damn balanced.

Then we could do:

	static struct object *root = NULL;

	static struct object **lookup_object_position(unsigned char *sha1)
	{
		struct object **p = &root;

		for (;;) {
			struct object *object = *p;
			int sign;

			if (!object)
				break;
			sign = memcmp(sha1, object->sha1, 20)
			if (!sign)
				break;
			p = &object->left;
			if (sign < 0)
				continue;
			p = &object->right;
		}
		return p;
	}

and now we _trivially_ have:

	struct object *lookup_object(unsigned char *sha1)
	{
		return *lookup_object_position(unsigned char *sha1);
	}

	void created_object(struct object **pos, unsigned char *sha1, struct object *n)
	{
		memcpy(n->sha1, sha1, 20);
		*pos = n;
	}

and the "lookup_or_create()" functions would become

	struct tag *lookup_tag(unsigned char *sha1)
	{
		struct object **p = lookup_object_position(sha1);
		struct object *object;

		object = *p;
		if (!object) {
			struct tag *ret = xmalloc(sizeof(struct tag));
			memset(ret, 0, sizeof(struct tag));
			created_object(p, sha1, &ret->object);
			ret->object.type = tag_type;
			return ret;
		}
		if (!object->type)
			obj->type = tag_type;

		if (object->type != tag_type) {
			error("Object %s is a %s, not a tag",
				sha1_to_hex(sha1), obj->type);
			return NULL;
		}
		return (struct tag *)obj;
	}

etc etc.

Hmm? That would be a lot faster than what we have now, I suspect, and none 
of the ops are expensive.

Anybody want to try this approach?

		Linus

Re: [PATCH] Optimization for git-rev-list --objects

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Hmm? That would be a lot faster than what we have now, I suspect, and none 
> of the ops are expensive.
>
> Anybody want to try this approach?

I am game.  I was looking at Johannes' patch that uses growing
circular hash and having the same thought.

[PATCH] binary-tree-based objects.

[Junio C Hamano]

This implements Linus' idea to keep objects in a binary tree,
instead of using the linear array as we currently do.

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

 * I haven't benched this seriously yet.  One datapoint:

	time git-rev-list --objects v2.6.15..linus | wc -l

   are 53sec vs 22sec improvement with the same output.

 fsck-objects.c |   36 +++++++++++++++++----------------
 name-rev.c     |   17 +++++++++++-----
 object.c       |   61 +++++++++++++++++++++-----------------------------------
 object.h       |    3 ++-
 4 files changed, 55 insertions(+), 62 deletions(-)

3c160f4d94cf16db5dc9c603e98ebacbe9ac4ca7
diff --git a/fsck-objects.c b/fsck-objects.c
index 9950be2..28a7c1b 100644
--- a/fsck-objects.c
+++ b/fsck-objects.c
@@ -56,23 +56,21 @@ static int objwarning(struct object *obj
 }
 
 
-static void check_connectivity(void)
+static void check_connectivity(struct object *obj)
 {
-	int i;
-
 	/* Look up all the requirements, warn about missing objects.. */
-	for (i = 0; i < nr_objs; i++) {
-		struct object *obj = objs[i];
-
-		if (!obj->parsed) {
-			if (!standalone && has_sha1_file(obj->sha1))
-				; /* it is in pack */
-			else
-				printf("missing %s %s\n",
-				       obj->type, sha1_to_hex(obj->sha1));
-			continue;
-		}
+ again:
+	if (!obj)
+		return;
 
+	if (!obj->parsed) {
+		if (!standalone && has_sha1_file(obj->sha1))
+			; /* it is in pack */
+		else
+			printf("missing %s %s\n",
+			       obj->type, sha1_to_hex(obj->sha1));
+	}
+	else {
 		if (obj->refs) {
 			const struct object_refs *refs = obj->refs;
 			unsigned j;
@@ -91,14 +89,16 @@ static void check_connectivity(void)
 		if (show_unreachable && !(obj->flags & REACHABLE)) {
 			printf("unreachable %s %s\n",
 			       obj->type, sha1_to_hex(obj->sha1));
-			continue;
 		}
-
-		if (!obj->used) {
+		else if (!obj->used) {
 			printf("dangling %s %s\n", obj->type, 
 			       sha1_to_hex(obj->sha1));
 		}
 	}
+	if (obj->left && obj->right)
+		check_connectivity(obj->left);
+	obj = obj->right ? obj->right : obj->left;
+	goto again;
 }
 
 /*
@@ -556,6 +556,6 @@ int main(int argc, char **argv)
 		}
 	}
 
-	check_connectivity();
+	check_connectivity(objs_root);
 	return 0;
 }
diff --git a/name-rev.c b/name-rev.c
index bbadb91..a4fecfb 100644
--- a/name-rev.c
+++ b/name-rev.c
@@ -120,6 +120,17 @@ static const char* get_rev_name(struct o
 	return buffer;
 }
 	
+void show_all_names(struct object *obj)
+{
+	while (obj) {
+		printf("%s %s\n", sha1_to_hex(obj->sha1), get_rev_name(obj));
+		if (obj->left && obj->right)
+			show_all_names(obj->left);
+		obj = obj->right ? obj->right : obj->left;
+	}
+}
+
+
 int main(int argc, char **argv)
 {
 	struct object_list *revs = NULL;
@@ -230,11 +241,7 @@ int main(int argc, char **argv)
 				fwrite(p_start, p - p_start, 1, stdout);
 		}
 	} else if (all) {
-		int i;
-
-		for (i = 0; i < nr_objs; i++)
-			printf("%s %s\n", sha1_to_hex(objs[i]->sha1),
-					get_rev_name(objs[i]));
+		show_all_names(objs_root);
 	} else
 		for ( ; revs; revs = revs->next)
 			printf("%s %s\n", revs->name, get_rev_name(revs->item));
diff --git a/object.c b/object.c
index 1577f74..a1b0729 100644
--- a/object.c
+++ b/object.c
@@ -5,65 +5,50 @@
 #include "commit.h"
 #include "tag.h"
 
-struct object **objs;
+struct object *objs_root;
 int nr_objs;
-static int obj_allocs;
 
 int track_object_refs = 1;
 
-static int find_object(const unsigned char *sha1)
+static struct object **lookup_object_position(const unsigned char *sha1)
 {
-	int first = 0, last = nr_objs;
+	struct object **p = &objs_root;
 
-        while (first < last) {
-                int next = (first + last) / 2;
-                struct object *obj = objs[next];
-                int cmp;
-
-                cmp = memcmp(sha1, obj->sha1, 20);
-                if (!cmp)
-                        return next;
-                if (cmp < 0) {
-                        last = next;
-                        continue;
-                }
-                first = next+1;
-        }
-        return -first-1;
+	for (;;) {
+		struct object *object = *p;
+		int sign;
+
+		if (!object)
+			break;
+		sign = memcmp(sha1, object->sha1, 20);
+		if (!sign)
+			break;
+		p = &object->left;
+		if (sign < 0)
+			continue;
+		p = &object->right;
+	}
+	return p;
 }
 
 struct object *lookup_object(const unsigned char *sha1)
 {
-	int pos = find_object(sha1);
-	if (pos >= 0)
-		return objs[pos];
-	return NULL;
+	return *lookup_object_position(sha1);
 }
 
 void created_object(const unsigned char *sha1, struct object *obj)
 {
-	int pos = find_object(sha1);
+	struct object **op = lookup_object_position(sha1);
 
 	obj->parsed = 0;
 	memcpy(obj->sha1, sha1, 20);
 	obj->type = NULL;
 	obj->refs = NULL;
 	obj->used = 0;
-
-	if (pos >= 0)
+	obj->left = obj->right = NULL;
+	if (*op)
 		die("Inserting %s twice\n", sha1_to_hex(sha1));
-	pos = -pos-1;
-
-	if (obj_allocs == nr_objs) {
-		obj_allocs = alloc_nr(obj_allocs);
-		objs = xrealloc(objs, obj_allocs * sizeof(struct object *));
-	}
-
-	/* Insert it into the right place */
-	memmove(objs + pos + 1, objs + pos, (nr_objs - pos) * 
-		sizeof(struct object *));
-
-	objs[pos] = obj;
+	*op = obj;
 	nr_objs++;
 }
 
diff --git a/object.h b/object.h
index 0e76182..32b276d 100644
--- a/object.h
+++ b/object.h
@@ -19,12 +19,13 @@ struct object {
 	unsigned char sha1[20];
 	const char *type;
 	struct object_refs *refs;
+	struct object *left, *right;
 	void *util;
 };
 
 extern int track_object_refs;
 extern int nr_objs;
-extern struct object **objs;
+extern struct object *objs_root;
 
 /** Internal only **/
 struct object *lookup_object(const unsigned char *sha1);
-- 
1.1.6.g69c5

Re: [PATCH] binary-tree-based objects.

[Linus Torvalds]

On Sat, 11 Feb 2006, Junio C Hamano wrote:
> 
>  * I haven't benched this seriously yet.  One datapoint:
> 
> 	time git-rev-list --objects v2.6.15..linus | wc -l
> 
>    are 53sec vs 22sec improvement with the same output.

Another datapoint: doing 

	time git-rev-list --objects HEAD > /dev/null 

three times in a row (to verify that the numbers are stable - they very 
clearly are).

Before:
	real    0m41.322s	user    0m40.612s	sys     0m0.492s
	real    0m40.797s	user    0m40.140s	sys     0m0.468s
	real    0m40.433s	user    0m40.016s	sys     0m0.412s

After:
	real    0m22.542s	user    0m22.080s	sys     0m0.448s
	real    0m22.660s	user    0m22.336s	sys     0m0.312s
	real    0m22.671s	user    0m22.236s	sys     0m0.292s

and doing some trivial oprofile runs shows that the object lookup is no 
longer dominant (my libc's don't have symbol information, so I don't get 
good profile data, but it shows that libc and libz are the biggest issues, 
with memcmp and malloc/free apparently being much bigger issues than the 
object lookup).

			Linus

Re: [PATCH] binary-tree-based objects.

[Linus Torvalds]

On Sat, 11 Feb 2006, Linus Torvalds wrote:
> 
> Before:
> 	real    0m41.322s	user    0m40.612s	sys     0m0.492s
> 	real    0m40.797s	user    0m40.140s	sys     0m0.468s
> 	real    0m40.433s	user    0m40.016s	sys     0m0.412s
> 
> After:
> 	real    0m22.542s	user    0m22.080s	sys     0m0.448s
> 	real    0m22.660s	user    0m22.336s	sys     0m0.312s
> 	real    0m22.671s	user    0m22.236s	sys     0m0.292s

And just so you wouldn't think that all my machines are slow..

Before:
	real    0m28.645s	user    0m28.366s	sys     0m0.280s
	real    0m28.700s	user    0m28.486s	sys     0m0.212s

After:
	real    0m16.566s	user    0m16.373s	sys     0m0.196s
	real    0m16.512s	user    0m16.277s	sys     0m0.236s

so there (that's all with current kernel HEAD, mostly packed).

Now, I haven't compared it to the other suggested fixes (hashing, and the 
256-way bucket-sorting), but I obviously prefer the tree approach because 
it's my idea (and my ideas are _always_ superior) and because it's so dang 
simple.

If somebody shows that the other approaches are faster, then I guess I'll 
just have to sulk in a corner and grown quietly at people.

		Linus

Re: [PATCH] binary-tree-based objects.

[Linus Torvalds]

On Sat, 11 Feb 2006, Linus Torvalds wrote:
> 
> If somebody shows that the other approaches are faster, then I guess I'll 
> just have to sulk in a corner and grown quietly at people.

growl. growL. With an 'L'!

		Linus

Re: [PATCH] binary-tree-based objects.

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Sat, 11 Feb 2006, Linus Torvalds wrote:
>> 
>> If somebody shows that the other approaches are faster, then I guess I'll 
>> just have to sulk in a corner and grown quietly at people.
>
> growl. growL. With an 'L'!

I do not get it.

But my impression was the circular hash with trivial fixes were
the fastest.  I am benching them now.

Re: [PATCH] binary-tree-based objects.

[Junio C Hamano]

Junio C Hamano <junkio@cox.net> writes:

> Linus Torvalds <torvalds@osdl.org> writes:
>
>> On Sat, 11 Feb 2006, Linus Torvalds wrote:
>>> 
>>> If somebody shows that the other approaches are faster, then I guess I'll 
>>> just have to sulk in a corner and grown quietly at people.
>>
>> growl. growL. With an 'L'!
>
> I do not get it.
> ...

I first suspected you just meant the typo (s/grown/growl/) but
it probably is that you really meant GROWL (and sulk).

It turns out that Johannes (with my patch to fix possible
unsigned int alignment issue and the initial call to
find_object()) is the clear winner.

        base   - tip of "master"
        lt-obj - the binary tree without balancing
        aj-obj - Alexandre's 256-way buckets
        js-obj - Johannes' circular hash

Although I have _not_ double checked the correctness of them, I
did not see major flaw in any of them.

base/git-rev-list --objects v2.6.14..linus
real	2m32.088s	user	2m2.830s	sys	0m0.890s
real	2m6.614s	user	2m1.860s	sys	0m0.660s
real	2m13.776s	user	2m2.450s	sys	0m0.590s
real	2m6.062s	user	2m2.420s	sys	0m0.690s
real	2m15.567s	user	2m3.170s	sys	0m0.900s

lt-obj/git-rev-list --objects v2.6.14..linus
real	0m42.889s	user	0m40.170s	sys	0m0.570s
real	0m44.247s	user	0m40.320s	sys	0m0.530s
real	0m40.891s	user	0m40.110s	sys	0m0.500s
real	0m41.874s	user	0m40.090s	sys	0m0.530s
real	0m41.596s	user	0m40.050s	sys	0m0.600s

aj-obj/git-rev-list --objects v2.6.14..linus
real	0m36.842s	user	0m36.200s	sys	0m0.490s
real	0m37.178s	user	0m36.740s	sys	0m0.390s
real	0m37.222s	user	0m36.540s	sys	0m0.610s
real	0m36.924s	user	0m36.410s	sys	0m0.360s
real	0m37.341s	user	0m36.150s	sys	0m0.620s

js-obj/git-rev-list --objects v2.6.14..linus
real	0m24.689s	user	0m24.120s	sys	0m0.390s
real	0m24.753s	user	0m24.020s	sys	0m0.360s
real	0m27.650s	user	0m24.470s	sys	0m0.440s
real	0m33.480s	user	0m24.030s	sys	0m0.460s
real	0m25.329s	user	0m24.490s	sys	0m0.390s


base/git-name-rev --all
real	0m4.193s	user	0m4.060s	sys	0m0.130s
real	0m4.179s	user	0m4.100s	sys	0m0.080s
real	0m4.210s	user	0m4.040s	sys	0m0.150s
real	0m4.162s	user	0m4.100s	sys	0m0.060s
real	0m4.697s	user	0m4.100s	sys	0m0.120s

lt-obj/git-name-rev --all
real	0m2.199s	user	0m2.120s	sys	0m0.080s
real	0m2.186s	user	0m2.110s	sys	0m0.080s
real	0m2.187s	user	0m2.150s	sys	0m0.040s
real	0m2.817s	user	0m2.150s	sys	0m0.070s
real	0m2.323s	user	0m2.170s	sys	0m0.050s

aj-obj/git-name-rev --all
real	0m2.136s	user	0m2.050s	sys	0m0.080s
real	0m2.164s	user	0m2.080s	sys	0m0.060s
real	0m2.143s	user	0m2.070s	sys	0m0.070s
real	0m2.141s	user	0m2.080s	sys	0m0.060s
real	0m2.154s	user	0m2.070s	sys	0m0.090s

js-obj/git-name-rev --all
real	0m2.047s	user	0m2.010s	sys	0m0.040s
real	0m2.040s	user	0m1.970s	sys	0m0.070s
real	0m2.025s	user	0m1.970s	sys	0m0.060s
real	0m2.170s	user	0m2.020s	sys	0m0.030s
real	0m2.046s	user	0m2.010s	sys	0m0.030s

Re: [PATCH] binary-tree-based objects.

[Linus Torvalds]

On Sat, 11 Feb 2006, Junio C Hamano wrote:
> 
> It turns out that Johannes (with my patch to fix possible
> unsigned int alignment issue and the initial call to
> find_object()) is the clear winner.

Having looked at it, I will have to agree. Johannes' approach looks 
pretty clean, and has the same memory overhead mine has (two pointers per 
object in the hash - one used, one empty), but has a lot fewer memcmp() 
calls and pointer chasing.

So I'll growl softly but concur. Johannes' code isn't even very complex.

		Linus

Re: [PATCH] binary-tree-based objects.

[Linus Torvalds]

On Sat, 11 Feb 2006, Linus Torvalds wrote:
> 
> Before:
> 	real    0m41.322s	user    0m40.612s	sys     0m0.492s
> After:
> 	real    0m22.542s	user    0m22.080s	sys     0m0.448s
Johannes:
	real    0m13.814s	user    0m13.492s	sys     0m0.296s

> And just so you wouldn't think that all my machines are slow..
> 
> Before:
> 	real    0m28.645s	user    0m28.366s	sys     0m0.280s
> After:
> 	real    0m16.566s	user    0m16.373s	sys     0m0.196s
Johannes:
	real    0m10.239s	user    0m10.029s	sys     0m0.208s

So the hashing thing is indeed the clear winner.

Make it so. 

		Linus