Commit 1bbacc9ff617b67831dbfce5e1b04e1bd8571aa0
2014-02-04T16:46:43
Avoid extra copying in pqueue operations This tweaks the pqueue_up and pqueue_down routines so that they will not do full element swaps but instead carry over the state of the previous loop iteration and only assign elements for which we know the final position. This will avoid a little bit of data assignment which should improve performance in theory. Also got rid of some vector helpers that I'm no longer using.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
diff --git a/src/pqueue.c b/src/pqueue.c
index cc31a8f..172cf43 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -35,32 +35,47 @@ int git_pqueue_init(
static void pqueue_up(git_pqueue *pq, size_t el)
{
size_t parent_el = PQUEUE_PARENT_OF(el);
+ void *kid = git_vector_get(pq, el);
- while (el > 0 && git_vector_cmp_elements(pq, parent_el, el) > 0) {
- git_vector_swap_elements(pq, el, parent_el);
+ while (el > 0) {
+ void *parent = pq->contents[parent_el];
+
+ if (pq->_cmp(parent, kid) <= 0)
+ break;
+
+ pq->contents[el] = parent;
el = parent_el;
parent_el = PQUEUE_PARENT_OF(el);
}
+
+ pq->contents[el] = kid;
}
static void pqueue_down(git_pqueue *pq, size_t el)
{
- size_t last = git_pqueue_size(pq);
+ void *parent = git_vector_get(pq, el), *kid, *rkid;
while (1) {
- size_t kid = PQUEUE_LCHILD_OF(el), rkid = PQUEUE_RCHILD_OF(el);
- if (kid >= last)
+ size_t kid_el = PQUEUE_LCHILD_OF(el);
+
+ if ((kid = git_vector_get(pq, kid_el)) == NULL)
break;
- if (rkid < last && git_vector_cmp_elements(pq, kid, rkid) > 0)
- kid = rkid;
- if (git_vector_cmp_elements(pq, el, kid) < 0)
+ if ((rkid = git_vector_get(pq, kid_el + 1)) != NULL &&
+ pq->_cmp(kid, rkid) > 0) {
+ kid = rkid;
+ kid_el += 1;
+ }
+
+ if (pq->_cmp(parent, kid) < 0)
break;
- git_vector_swap_elements(pq, el, kid);
- el = kid;
+ pq->contents[el] = kid;
+ el = kid_el;
}
+
+ pq->contents[el] = parent;
}
int git_pqueue_insert(git_pqueue *pq, void *item)
diff --git a/src/vector.h b/src/vector.h
index f983c55..f825685 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -108,14 +108,4 @@ GIT_INLINE(void) git_vector_set_cmp(git_vector *v, git_vector_cmp cmp)
}
}
-/** Swap two elements */
-#define git_vector_swap_elements(V, P1, P2) do { \
- void *__t = (V)->contents[P1]; \
- (V)->contents[P1] = (V)->contents[P2]; \
- (V)->contents[P2] = __t; } while (0)
-
-/** Compare two elements */
-#define git_vector_cmp_elements(V, P1, P2) \
- (V)->_cmp(git_vector_get(V,P1), git_vector_get(V,P2))
-
#endif