Re: Some git performance measurements..

[Linus Torvalds <torvalds@linux-foundation.org>]

On Fri, 30 Nov 2007, Jakub Narebski wrote:
> 
> Isn't there a better way to do this sorting? What is needed here is
> (stable) _bucket_ sort / _pigeonhole_ sort (or counting sort), which
> is O(n); quicksort is perhaps simpler to use, but I'm not sure if
> faster in this situation.

Actually, I doubt you need to do any sorting at all: what would be easiest 
would be to simply change "traverse_commit_list()" to use different lists 
for different object types, and just output them in type order (semi-sane 
order choice: commits first, then tags, then trees, and finally blobs).

Ta-daa! All done! Magic! No sorting required, because all the objects got 
output in the right order without any extra sort phase!

Something like the appended (untested! lots of! exclamation marks! 
Really!)

		Linus

---
 list-objects.c |   36 ++++++++++++++++++++++--------------
 1 files changed, 22 insertions(+), 14 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index 4ef58e7..a046f37 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -49,7 +49,6 @@ static void process_blob(struct rev_info *revs,
  */
 static void process_gitlink(struct rev_info *revs,
 			    const unsigned char *sha1,
-			    struct object_array *p,
 			    struct name_path *path,
 			    const char *name)
 {
@@ -58,7 +57,8 @@ static void process_gitlink(struct rev_info *revs,
 
 static void process_tree(struct rev_info *revs,
 			 struct tree *tree,
-			 struct object_array *p,
+			 struct object_array *trees,
+			 struct object_array *blobs,
 			 struct name_path *path,
 			 const char *name)
 {
@@ -75,7 +75,7 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
 	obj->flags |= SEEN;
 	name = xstrdup(name);
-	add_object(obj, p, path, name);
+	add_object(obj, trees, path, name);
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -86,14 +86,14 @@ static void process_tree(struct rev_info *revs,
 		if (S_ISDIR(entry.mode))
 			process_tree(revs,
 				     lookup_tree(entry.sha1),
-				     p, &me, entry.path);
+				     trees, blobs, &me, entry.path);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
-					p, &me, entry.path);
+					&me, entry.path);
 		else
 			process_blob(revs,
 				     lookup_blob(entry.sha1),
-				     p, &me, entry.path);
+				     blobs, &me, entry.path);
 	}
 	free(tree->buffer);
 	tree->buffer = NULL;
@@ -138,10 +138,12 @@ void traverse_commit_list(struct rev_info *revs,
 {
 	int i;
 	struct commit *commit;
-	struct object_array objects = { 0, 0, NULL };
+	struct object_array tags = { 0, 0, NULL };
+	struct object_array trees = { 0, 0, NULL };
+	struct object_array blobs = { 0, 0, NULL };
 
 	while ((commit = get_revision(revs)) != NULL) {
-		process_tree(revs, commit->tree, &objects, NULL, "");
+		process_tree(revs, commit->tree, &trees, &blobs, NULL, "");
 		show_commit(commit);
 	}
 	for (i = 0; i < revs->pending.nr; i++) {
@@ -152,25 +154,31 @@ void traverse_commit_list(struct rev_info *revs,
 			continue;
 		if (obj->type == OBJ_TAG) {
 			obj->flags |= SEEN;
-			add_object_array(obj, name, &objects);
+			add_object_array(obj, name, &tags);
 			continue;
 		}
 		if (obj->type == OBJ_TREE) {
-			process_tree(revs, (struct tree *)obj, &objects,
+			process_tree(revs, (struct tree *)obj, &trees, &blobs,
 				     NULL, name);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
-			process_blob(revs, (struct blob *)obj, &objects,
+			process_blob(revs, (struct blob *)obj, &blobs,
 				     NULL, name);
 			continue;
 		}
 		die("unknown pending object %s (%s)",
 		    sha1_to_hex(obj->sha1), name);
 	}
-	for (i = 0; i < objects.nr; i++)
-		show_object(&objects.objects[i]);
-	free(objects.objects);
+	for (i = 0; i < tags.nr; i++)
+		show_object(&tags.objects[i]);
+	for (i = 0; i < trees.nr; i++)
+		show_object(&trees.objects[i]);
+	for (i = 0; i < blobs.nr; i++)
+		show_object(&blobs.objects[i]);
+	free(tags.objects);
+	free(trees.objects);
+	free(blobs.objects);
 	if (revs->pending.nr) {
 		free(revs->pending.objects);
 		revs->pending.nr = 0;