The merge-base functions internally keep a commit lists and
insert by date, which causes a linear search of the commit
list for each insertion. Let's use a priority queue instead.
Unfortunately, from my experiments, this didn't actually
cause any speedup.
Signed-off-by: Jeff King <peff@xxxxxxxx>
---
I'd probably split this into a few commits if we were really going to
apply it, but since it doesn't actually make anything faster, I doubt
the code churn is worth it.
commit.c | 78 ++++++++++++++++++++++++++++++++++++++--------------------------
1 file changed, 47 insertions(+), 31 deletions(-)
diff --git a/commit.c b/commit.c
index 380f4ec..c64ef94 100644
--- a/commit.c
+++ b/commit.c
@@ -7,6 +7,7 @@
#include "revision.h"
#include "notes.h"
#include "gpg-interface.h"
+#include "queue.h"
int save_commit_buffer = 1;
@@ -360,6 +361,15 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
return new_list;
}
+static void commit_list_append(struct commit *item, struct commit_list ***tail)
+{
+ struct commit_list *new_list = xmalloc(sizeof(*new_list));
+ new_list->item = item;
+ new_list->next = NULL;
+ **tail = new_list;
+ *tail = &new_list->next;
+}
+
unsigned commit_list_count(const struct commit_list *l)
{
unsigned c = 0;
@@ -422,6 +432,16 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
return ret;
}
+static int commit_datecmp(const void *va, const void *vb)
+{
+ const struct commit *a = va, *b = vb;
+ if (a->date < b->date)
+ return -1;
+ else if (a->date > b->date)
+ return 1;
+ return 0;
+}
+
void clear_commit_marks(struct commit *commit, unsigned int mark)
{
while (commit) {
@@ -569,22 +589,23 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
-static struct commit *interesting(struct commit_list *list)
+static int interesting(struct queue *q)
{
- while (list) {
- struct commit *commit = list->item;
- list = list->next;
+ int i;
+ for (i = 0; i < q->nr; i++) {
+ struct commit *commit = q->items[i];
if (commit->object.flags & STALE)
continue;
- return commit;
+ return 1;
}
- return NULL;
+ return 0;
}
static struct commit_list *merge_bases_many(struct commit *one, int n, struct commit **twos)
{
- struct commit_list *list = NULL;
- struct commit_list *result = NULL;
+ struct queue result = { commit_datecmp };
+ struct queue list = { commit_datecmp };
+ struct commit_list *ret = NULL, **tail = &ret;
int i;
for (i = 0; i < n; i++) {
@@ -593,7 +614,7 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
* We do not mark this even with RESULT so we do not
* have to clean it up.
*/
- return commit_list_insert(one, &result);
+ return commit_list_insert(one, &ret);
}
if (parse_commit(one))
@@ -604,28 +625,24 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
}
one->object.flags |= PARENT1;
- commit_list_insert_by_date(one, &list);
+ queue_insert(&list, one);
for (i = 0; i < n; i++) {
twos[i]->object.flags |= PARENT2;
- commit_list_insert_by_date(twos[i], &list);
+ queue_insert(&list, twos[i]);
}
- while (interesting(list)) {
+ while (interesting(&list)) {
struct commit *commit;
struct commit_list *parents;
- struct commit_list *next;
int flags;
- commit = list->item;
- next = list->next;
- free(list);
- list = next;
+ commit = queue_pop(&list);
flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
commit->object.flags |= RESULT;
- commit_list_insert_by_date(commit, &result);
+ queue_insert(&result, commit);
}
/* Mark parents of a found merge stale */
flags |= STALE;
@@ -639,21 +656,16 @@ static struct commit_list *merge_bases_many(struct commit *one, int n, struct co
if (parse_commit(p))
return NULL;
p->object.flags |= flags;
- commit_list_insert_by_date(p, &list);
+ queue_insert(&list, p);
}
}
/* Clean up the result to remove stale ones */
- free_commit_list(list);
- list = result; result = NULL;
- while (list) {
- struct commit_list *next = list->next;
- if (!(list->item->object.flags & STALE))
- commit_list_insert_by_date(list->item, &result);
- free(list);
- list = next;
- }
- return result;
+ while (result.nr)
+ commit_list_append(queue_pop(&result), &tail);
+ queue_clear(&result);
+ queue_clear(&list);
+ return ret;
}
struct commit_list *get_octopus_merge_bases(struct commit_list *in)
@@ -690,7 +702,8 @@ struct commit_list *get_merge_bases_many(struct commit *one,
{
struct commit_list *list;
struct commit **rslt, **others;
- struct commit_list *result;
+ struct commit_list *result, **tail = &result;
+ struct queue commit_queue = { commit_datecmp };
int cnt, i, j;
result = merge_bases_many(one, n, twos);
@@ -744,11 +757,14 @@ struct commit_list *get_merge_bases_many(struct commit *one,
list = list->next;
}
if (!list)
- commit_list_insert_by_date(rslt[i], &result);
+ queue_insert(&commit_queue, rslt[i]);
free_commit_list(list);
}
free(rslt);
free(others);
+ while (commit_queue.nr)
+ commit_list_append(queue_pop(&commit_queue), &tail);
+ queue_clear(&commit_queue);
return result;
}
--
1.7.12.35.g38689e3
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html