summaryrefslogtreecommitdiff
path: root/commit.c
diff options
context:
space:
mode:
authorJeff King <peff@peff.net>2014-07-14 01:53:54 -0400
committerJunio C Hamano <gitster@pobox.com>2014-07-15 11:02:56 -0700
commit73f43f220f0276012de50c84413fd61bf6aa307b (patch)
tree85fdc5b812e570aad41e942ff110b5f603b047a0 /commit.c
parente8f91e3df82a33b7e0b59c935cc4af892068baa2 (diff)
downloadgit-73f43f220f0276012de50c84413fd61bf6aa307b.tar.gz
paint_down_to_common: use prio_queue
When we are traversing to find merge bases, we keep our usual commit_list of commits to process, sorted by their commit timestamp. As we add each parent to the list, we have to spend "O(width of history)" to do the insertion, where the width of history is the number of simultaneous lines of development. If we instead use a heap-based priority queue, we can do these insertions in "O(log width)" time. This provides minor speedups to merge-base calculations (timings in linux.git, warm cache, best-of-five): [before] $ git merge-base HEAD v2.6.12 real 0m3.251s user 0m3.148s sys 0m0.104s [after] $ git merge-base HEAD v2.6.12 real 0m3.234s user 0m3.108s sys 0m0.128s That's only an 0.5% speedup, but it does help protect us against pathological cases. While we are munging the "interesting" function, we also take the opportunity to give it a more descriptive name, and convert the return value to an int (we returned the first interesting commit, but nobody ever looked at it). Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'commit.c')
-rw-r--r--commit.c42
1 files changed, 19 insertions, 23 deletions
diff --git a/commit.c b/commit.c
index acb74b55d4..1fc60c0109 100644
--- a/commit.c
+++ b/commit.c
@@ -786,45 +786,41 @@ void sort_in_topological_order(struct commit_list **list, enum rev_sort_order so
static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
-static struct commit *interesting(struct commit_list *list)
+static int queue_has_nonstale(struct prio_queue *queue)
{
- while (list) {
- struct commit *commit = list->item;
- list = list->next;
- if (commit->object.flags & STALE)
- continue;
- return commit;
+ int i;
+ for (i = 0; i < queue->nr; i++) {
+ struct commit *commit = queue->array[i].data;
+ if (!(commit->object.flags & STALE))
+ return 1;
}
- return NULL;
+ return 0;
}
/* all input commits in one and twos[] must have been parsed! */
static struct commit_list *paint_down_to_common(struct commit *one, int n, struct commit **twos)
{
- struct commit_list *list = NULL;
+ struct prio_queue queue = { compare_commits_by_commit_date };
struct commit_list *result = NULL;
int i;
one->object.flags |= PARENT1;
- commit_list_insert_by_date(one, &list);
- if (!n)
- return list;
+ if (!n) {
+ commit_list_append(one, &result);
+ return result;
+ }
+ prio_queue_put(&queue, one);
+
for (i = 0; i < n; i++) {
twos[i]->object.flags |= PARENT2;
- commit_list_insert_by_date(twos[i], &list);
+ prio_queue_put(&queue, twos[i]);
}
- while (interesting(list)) {
- struct commit *commit;
+ while (queue_has_nonstale(&queue)) {
+ struct commit *commit = prio_queue_get(&queue);
struct commit_list *parents;
- struct commit_list *next;
int flags;
- commit = list->item;
- next = list->next;
- free(list);
- list = next;
-
flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
@@ -843,11 +839,11 @@ static struct commit_list *paint_down_to_common(struct commit *one, int n, struc
if (parse_commit(p))
return NULL;
p->object.flags |= flags;
- commit_list_insert_by_date(p, &list);
+ prio_queue_put(&queue, p);
}
}
- free_commit_list(list);
+ clear_prio_queue(&queue);
return result;
}