Re: Some git performance measurements..
- From
Linus Torvalds <torvalds@linux-foundation.org>
- Date
- Nov 30, 2007, 02:21 UTC
- Message-ID
- <alpine.LFD.0.9999.0711291812530.8458@woody.linux-foundation.org>
- In-Reply-To
- <finmvm$da8$1@ger.gmane.org>
On Fri, 30 Nov 2007, Jakub Narebski wrote:
Show 5 quoted lines
> > 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;