Re: [PATCH 2/2] pack-objects: optimize "recency order"
From: Junio C Hamano <hidden>
Date: 2016-06-15 22:51:33
This updates the codepath to write commit objects so that when a commit is emitted, its parents are scheduled to be output next (but this does not go recursively), in the hope that it may help a typical "rev-list" traversal. I've tried various workloads from the previous message; while this patch does not regress any of them significantly, it does not seem to improve them significantly, either. builtin/pack-objects.c | 96 ++++++++++++++++++++++++++++++++++------------- 1 files changed, 69 insertions(+), 27 deletions(-)
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 27132bb..46ae610 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c@@ -487,6 +487,74 @@ static void add_family_to_write_order(struct object_entry **wo, add_descendants_to_write_order(wo, endp, root); } +static void add_commit_to_write_order(struct object_entry **wo, + int *endp, + struct object_entry *e) +{ + /* + * A typical rev-list traversal looks at the parent of a + * commit before deciding to emit the commit; if it ends up + * emitting this commit, it is likely that it needs an early + * access of its parents. + */ + struct commit *commit; + struct commit_list *parents; + + if (e->filled) + return; + add_to_write_order(wo, endp, e); + commit = lookup_commit(e->idx.sha1); + if (!commit || + (!commit->object.parsed && parse_commit(commit))) + die("BUG: calling add_commit with a non-commit???"); + for (parents = commit->parents; parents; parents = parents->next) { + struct object_entry *pe; + struct commit *parent = parents->item; + pe = locate_object_entry(parent->object.sha1); + if (pe) + add_to_write_order(wo, endp, pe); + } +} + +static int add_commits_to_write_order(struct object_entry **wo) +{ + int i, wo_end; + + /* + * Give the commits in the original recency order until + * we see a tagged tip. + */ + for (i = wo_end = 0; i < nr_objects; i++) { + if (objects[i].type != OBJ_COMMIT) + continue; + if (objects[i].tagged) + break; + add_commit_to_write_order(wo, &wo_end, &objects[i]); + } + + /* + * Then fill all the tagged tips. + */ + for (i = 0; i < nr_objects; i++) { + if (objects[i].type != OBJ_COMMIT) + continue; + if (objects[i].tagged) + add_commit_to_write_order(wo, &wo_end, &objects[i]); + } + + /* + * And then all remaining commits and tags. + */ + for (i = 0; i < nr_objects; i++) { + if (objects[i].type == OBJ_COMMIT) + add_commit_to_write_order(wo, &wo_end, &objects[i]); + else if (objects[i].type != OBJ_TAG) + add_to_write_order(wo, &wo_end, &objects[i]); + } + + return wo_end; +} + static struct object_entry **compute_write_order(void) { int i, wo_end;
@@ -519,33 +587,7 @@ static struct object_entry **compute_write_order(void) */ for_each_tag_ref(mark_tagged, NULL); - /* - * Give the commits in the original recency order until - * we see a tagged tip. - */ - for (i = wo_end = 0; i < nr_objects; i++) { - if (objects[i].tagged) - break; - add_to_write_order(wo, &wo_end, &objects[i]); - } - - /* - * Then fill all the tagged tips. - */ - for (; i < nr_objects; i++) { - if (objects[i].tagged) - add_to_write_order(wo, &wo_end, &objects[i]); - } - - /* - * And then all remaining commits and tags. - */ - for (i = 0; i < nr_objects; i++) { - if (objects[i].type != OBJ_COMMIT && - objects[i].type != OBJ_TAG) - continue; - add_to_write_order(wo, &wo_end, &objects[i]); - } + wo_end = add_commits_to_write_order(wo); /* * And then all the trees.