diff options
author | Junio C Hamano <gitster@pobox.com> | 2019-04-25 10:41:18 +0300 |
---|---|---|
committer | Junio C Hamano <gitster@pobox.com> | 2019-04-25 10:41:18 +0300 |
commit | d9d65e9f6ab3f5f1525ae8c86dfbab5978adf846 (patch) | |
tree | e8d0a34dd1f117cd6c7672934f5967d7aea75f43 | |
parent | 4d8c4da9508384fc6e6a66189d759609f195cd5e (diff) | |
parent | 8320b1dbe7d160ea08dec931cf17dc39682bfb91 (diff) |
Merge branch 'jk/revision-rewritten-parents-in-prio-queue'
Performance fix for "rev-list --parents -- pathspec".
* jk/revision-rewritten-parents-in-prio-queue:
revision: use a prio_queue to hold rewritten parents
-rw-r--r-- | revision.c | 58 | ||||
-rwxr-xr-x | t/perf/p0001-rev-list.sh | 18 |
2 files changed, 54 insertions, 22 deletions
diff --git a/revision.c b/revision.c index 60553d829d..d4aaf0ef25 100644 --- a/revision.c +++ b/revision.c @@ -911,26 +911,11 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) commit->object.flags |= TREESAME; } -static void commit_list_insert_by_date_cached(struct commit *p, struct commit_list **head, - struct commit_list *cached_base, struct commit_list **cache) -{ - struct commit_list *new_entry; - - if (cached_base && p->date < cached_base->item->date) - new_entry = commit_list_insert_by_date(p, &cached_base->next); - else - new_entry = commit_list_insert_by_date(p, head); - - if (cache && (!*cache || p->date < (*cache)->item->date)) - *cache = new_entry; -} - static int process_parents(struct rev_info *revs, struct commit *commit, - struct commit_list **list, struct commit_list **cache_ptr) + struct commit_list **list, struct prio_queue *queue) { struct commit_list *parent = commit->parents; unsigned left_flag; - struct commit_list *cached_base = cache_ptr ? *cache_ptr : NULL; if (commit->object.flags & ADDED) return 0; @@ -966,7 +951,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit, continue; p->object.flags |= SEEN; if (list) - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + commit_list_insert_by_date(p, list); + if (queue) + prio_queue_put(queue, p); } return 0; } @@ -1006,7 +993,9 @@ static int process_parents(struct rev_info *revs, struct commit *commit, if (!(p->object.flags & SEEN)) { p->object.flags |= SEEN; if (list) - commit_list_insert_by_date_cached(p, list, cached_base, cache_ptr); + commit_list_insert_by_date(p, list); + if (queue) + prio_queue_put(queue, p); } if (revs->first_parent_only) break; @@ -3345,14 +3334,14 @@ int prepare_revision_walk(struct rev_info *revs) return 0; } -static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp) +static enum rewrite_result rewrite_one_1(struct rev_info *revs, + struct commit **pp, + struct prio_queue *queue) { - struct commit_list *cache = NULL; - for (;;) { struct commit *p = *pp; if (!revs->limited) - if (process_parents(revs, p, &revs->commits, &cache) < 0) + if (process_parents(revs, p, NULL, queue) < 0) return rewrite_one_error; if (p->object.flags & UNINTERESTING) return rewrite_one_ok; @@ -3366,6 +3355,31 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp } } +static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list) +{ + while (q->nr) { + struct commit *item = prio_queue_peek(q); + struct commit_list *p = *list; + + if (p && p->item->date >= item->date) + list = &p->next; + else { + p = commit_list_insert(item, list); + list = &p->next; /* skip newly added item */ + prio_queue_get(q); /* pop item */ + } + } +} + +static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp) +{ + struct prio_queue queue = { compare_commits_by_commit_date }; + enum rewrite_result ret = rewrite_one_1(revs, pp, &queue); + merge_queue_into_list(&queue, &revs->commits); + clear_prio_queue(&queue); + return ret; +} + int rewrite_parents(struct rev_info *revs, struct commit *commit, rewrite_parent_fn_t rewrite_parent) { diff --git a/t/perf/p0001-rev-list.sh b/t/perf/p0001-rev-list.sh index ebf172401b..3042a85666 100755 --- a/t/perf/p0001-rev-list.sh +++ b/t/perf/p0001-rev-list.sh @@ -14,6 +14,24 @@ test_perf 'rev-list --all --objects' ' git rev-list --all --objects >/dev/null ' +test_perf 'rev-list --parents' ' + git rev-list --parents HEAD >/dev/null +' + +test_expect_success 'create dummy file' ' + echo unlikely-to-already-be-there >dummy && + git add dummy && + git commit -m dummy +' + +test_perf 'rev-list -- dummy' ' + git rev-list HEAD -- dummy +' + +test_perf 'rev-list --parents -- dummy' ' + git rev-list --parents HEAD -- dummy +' + test_expect_success 'create new unreferenced commit' ' commit=$(git commit-tree HEAD^{tree} -p HEAD) && test_export commit |