From a4b27831693eed988bcdf957bbe9ad7609e7bdf7 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 22 Oct 2012 03:25:53 +0000 Subject: small optimization for BLI_heap(), give some speedup in decimeter. - use unsigned ints only (where mixing signed/unsigned) - turn heap_swap into an inline function, add SWAP_TVAL macro to swap values using a temp value as storage. - added type checking SHIFT3/4 macros also style cleanup for CTR_Map --- source/blender/blenlib/BLI_heap.h | 2 +- source/blender/blenlib/BLI_utildefines.h | 87 +++++++++++------- source/blender/blenlib/intern/BLI_heap.c | 120 ++++++++++++++----------- source/blender/modifiers/intern/MOD_decimate.c | 2 + 4 files changed, 128 insertions(+), 83 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h index adbbf266b4e..c0941e00c9b 100644 --- a/source/blender/blenlib/BLI_heap.h +++ b/source/blender/blenlib/BLI_heap.h @@ -57,7 +57,7 @@ void BLI_heap_remove(Heap *heap, HeapNode *node); int BLI_heap_is_empty(Heap *heap); /* Return the size of the heap. */ -int BLI_heap_size(Heap *heap); +unsigned int BLI_heap_size(Heap *heap); /* Return the top node of the heap. This is the node with the lowest value. */ HeapNode *BLI_heap_top(Heap *heap); diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 47c2256c1e1..0dab51154eb 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -41,34 +41,6 @@ #endif -#define ELEM(a, b, c) ((a) == (b) || (a) == (c)) -#define ELEM3(a, b, c, d) (ELEM(a, b, c) || (a) == (d) ) -#define ELEM4(a, b, c, d, e) (ELEM(a, b, c) || ELEM(a, d, e) ) -#define ELEM5(a, b, c, d, e, f) (ELEM(a, b, c) || ELEM3(a, d, e, f) ) -#define ELEM6(a, b, c, d, e, f, g) (ELEM(a, b, c) || ELEM4(a, d, e, f, g) ) -#define ELEM7(a, b, c, d, e, f, g, h) (ELEM3(a, b, c, d) || ELEM4(a, e, f, g, h) ) -#define ELEM8(a, b, c, d, e, f, g, h, i) (ELEM4(a, b, c, d, e) || ELEM4(a, f, g, h, i) ) -#define ELEM9(a, b, c, d, e, f, g, h, i, j) (ELEM4(a, b, c, d, e) || ELEM5(a, f, g, h, i, j) ) -#define ELEM10(a, b, c, d, e, f, g, h, i, j, k) (ELEM4(a, b, c, d, e) || ELEM6(a, f, g, h, i, j, k) ) -#define ELEM11(a, b, c, d, e, f, g, h, i, j, k, l) (ELEM4(a, b, c, d, e) || ELEM7(a, f, g, h, i, j, k, l) ) - -/* shift around elements */ -#define SHIFT3(type, a, b, c) { \ - type tmp; \ - tmp = a; \ - a = c; \ - c = b; \ - b = tmp; \ -} (void)0 -#define SHIFT4(type, a, b, c, d) { \ - type tmp; \ - tmp = a; \ - a = d; \ - d = c; \ - c = b; \ - b = tmp; \ -} (void)0 - /* min/max */ #define MIN2(x, y) ( (x) < (y) ? (x) : (y) ) #define MIN3(x, y, z) MIN2(MIN2((x), (y)), (z) ) @@ -116,22 +88,28 @@ /* Causes warning: * incompatible types when assigning to type 'Foo' from type 'Bar' * ... the compiler optimizes away the temp var */ -#ifndef CHECK_TYPE #ifdef __GNUC__ #define CHECK_TYPE(var, type) { \ __typeof(var) *__tmp; \ __tmp = (type *)NULL; \ (void)__tmp; \ } (void)0 + +#define CHECK_TYPE_PAIR(var_a, var_b) { \ + __typeof(var_a) *__tmp; \ + __tmp = (__typeof(var_b) *)NULL; \ + (void)__tmp; \ +} (void)0 #else -#define CHECK_TYPE(var, type) -#endif +# define CHECK_TYPE(var, type) +# define CHECK_TYPE_PAIR(var_a, var_b) #endif /* can be used in simple macros */ #define CHECK_TYPE_INLINE(val, type) \ ((void)(((type *)0) != (val))) + #ifndef SWAP # define SWAP(type, a, b) { \ type sw_ap; \ @@ -143,6 +121,53 @@ } (void)0 #endif +/* swap with a temp value */ +#define SWAP_TVAL(tval, a, b) { \ + CHECK_TYPE_PAIR(tval, a); \ + CHECK_TYPE_PAIR(tval, b); \ + (tval) = (a); \ + (a) = (b); \ + (b) = (tval); \ +} (void)0 + + +#define ELEM(a, b, c) ((a) == (b) || (a) == (c)) +#define ELEM3(a, b, c, d) (ELEM(a, b, c) || (a) == (d) ) +#define ELEM4(a, b, c, d, e) (ELEM(a, b, c) || ELEM(a, d, e) ) +#define ELEM5(a, b, c, d, e, f) (ELEM(a, b, c) || ELEM3(a, d, e, f) ) +#define ELEM6(a, b, c, d, e, f, g) (ELEM(a, b, c) || ELEM4(a, d, e, f, g) ) +#define ELEM7(a, b, c, d, e, f, g, h) (ELEM3(a, b, c, d) || ELEM4(a, e, f, g, h) ) +#define ELEM8(a, b, c, d, e, f, g, h, i) (ELEM4(a, b, c, d, e) || ELEM4(a, f, g, h, i) ) +#define ELEM9(a, b, c, d, e, f, g, h, i, j) (ELEM4(a, b, c, d, e) || ELEM5(a, f, g, h, i, j) ) +#define ELEM10(a, b, c, d, e, f, g, h, i, j, k) (ELEM4(a, b, c, d, e) || ELEM6(a, f, g, h, i, j, k) ) +#define ELEM11(a, b, c, d, e, f, g, h, i, j, k, l) (ELEM4(a, b, c, d, e) || ELEM7(a, f, g, h, i, j, k, l) ) + +/* shift around elements */ +#define SHIFT3(type, a, b, c) { \ + type tmp; \ + CHECK_TYPE(a, type); \ + CHECK_TYPE(b, type); \ + CHECK_TYPE(c, type); \ + tmp = a; \ + a = c; \ + c = b; \ + b = tmp; \ +} (void)0 + +#define SHIFT4(type, a, b, c, d) { \ + type tmp; \ + CHECK_TYPE(a, type); \ + CHECK_TYPE(b, type); \ + CHECK_TYPE(c, type); \ + CHECK_TYPE(d, type); \ + tmp = a; \ + a = d; \ + d = c; \ + c = b; \ + b = tmp; \ +} (void)0 + + #define ABS(a) ( (a) < 0 ? (-(a)) : (a) ) #define FTOCHAR(val) ((val) <= 0.0f) ? 0 : (((val) > (1.0f - 0.5f / 255.0f)) ? 255 : (char)((255.0f * (val)) + 0.5f)) diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c index 5a33e998561..3f88e336325 100644 --- a/source/blender/blenlib/intern/BLI_heap.c +++ b/source/blender/blenlib/intern/BLI_heap.c @@ -40,9 +40,9 @@ /***/ struct HeapNode { - void *ptr; - float value; - int index; + void *ptr; + float value; + unsigned int index; }; struct Heap { @@ -54,54 +54,40 @@ struct Heap { HeapNode **tree; }; +/* internal functions */ + #define HEAP_PARENT(i) ((i - 1) >> 1) #define HEAP_LEFT(i) ((i << 1) + 1) #define HEAP_RIGHT(i) ((i << 1) + 2) #define HEAP_COMPARE(a, b) (a->value < b->value) -// #define HEAP_EQUALS(a, b) (a->value == b->value) // UNUSED -#define HEAP_SWAP(heap, i, j) \ - { \ - SWAP(int, heap->tree[i]->index, heap->tree[j]->index); \ - SWAP(HeapNode *, heap->tree[i], heap->tree[j]); \ - } (void)0 -/***/ +#if 0 /* UNUSED */ +#define HEAP_EQUALS(a, b) (a->value == b->value) +#endif -/* use when the size of the heap is known in advance */ -Heap *BLI_heap_new_ex(unsigned int tot_reserve) +BLI_INLINE void heap_swap(Heap *heap, const unsigned int i, const unsigned int j) { - Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__); - heap->bufsize = tot_reserve; - heap->tree = (HeapNode **)MEM_mallocN(tot_reserve * sizeof(HeapNode *), "BLIHeapTree"); - heap->arena = BLI_memarena_new(1 << 16, "heap arena"); - return heap; +#if 0 + SWAP(unsigned int, heap->tree[i]->index, heap->tree[j]->index); + SWAP(HeapNode *, heap->tree[i], heap->tree[j]); +#else + HeapNode **tree = heap->tree; + union { + unsigned int index; + HeapNode *node; + } tmp; + SWAP_TVAL(tmp.index, tree[i]->index, tree[j]->index); + SWAP_TVAL(tmp.node, tree[i], tree[j]); +#endif } -Heap *BLI_heap_new(void) -{ - return BLI_heap_new_ex(1); -} - -void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) -{ - int i; - - if (ptrfreefp) - for (i = 0; i < heap->size; i++) - ptrfreefp(heap->tree[i]->ptr); - - MEM_freeN(heap->tree); - BLI_memarena_free(heap->arena); - MEM_freeN(heap); -} - -static void BLI_heap_down(Heap *heap, int i) +static void heap_down(Heap *heap, unsigned int i) { while (1) { - int size = heap->size, smallest; - int l = HEAP_LEFT(i); - int r = HEAP_RIGHT(i); + unsigned int size = heap->size,smallest ; + unsigned int l = HEAP_LEFT(i); + unsigned int r = HEAP_RIGHT(i); smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i; @@ -111,30 +97,62 @@ static void BLI_heap_down(Heap *heap, int i) if (smallest == i) break; - HEAP_SWAP(heap, i, smallest); + heap_swap(heap, i, smallest); i = smallest; } } -static void BLI_heap_up(Heap *heap, int i) +static void heap_up(Heap *heap, unsigned int i) { while (i > 0) { - int p = HEAP_PARENT(i); + unsigned int p = HEAP_PARENT(i); if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) break; - HEAP_SWAP(heap, p, i); + heap_swap(heap, p, i); i = p; } } + +/***/ + +/* use when the size of the heap is known in advance */ +Heap *BLI_heap_new_ex(unsigned int tot_reserve) +{ + Heap *heap = (Heap *)MEM_callocN(sizeof(Heap), __func__); + heap->bufsize = tot_reserve; + heap->tree = (HeapNode **)MEM_mallocN(tot_reserve * sizeof(HeapNode *), "BLIHeapTree"); + heap->arena = BLI_memarena_new(1 << 16, "heap arena"); + + return heap; +} + +Heap *BLI_heap_new(void) +{ + return BLI_heap_new_ex(1); +} + +void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) +{ + unsigned int i; + + if (ptrfreefp) + for (i = 0; i < heap->size; i++) + ptrfreefp(heap->tree[i]->ptr); + + MEM_freeN(heap->tree); + BLI_memarena_free(heap->arena); + MEM_freeN(heap); +} + HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) { HeapNode *node; if ((heap->size + 1) > heap->bufsize) { - int newsize = heap->bufsize * 2; + unsigned int newsize = heap->bufsize * 2; HeapNode **newtree; newtree = (HeapNode **)MEM_mallocN(newsize * sizeof(*newtree), __func__); @@ -160,7 +178,7 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) heap->size++; - BLI_heap_up(heap, heap->size - 1); + heap_up(heap, heap->size - 1); return node; } @@ -170,7 +188,7 @@ int BLI_heap_is_empty(Heap *heap) return (heap->size == 0); } -int BLI_heap_size(Heap *heap) +unsigned int BLI_heap_size(Heap *heap) { return heap->size; } @@ -190,10 +208,10 @@ void *BLI_heap_popmin(Heap *heap) if (heap->size == 1) heap->size--; else { - HEAP_SWAP(heap, 0, heap->size - 1); + heap_swap(heap, 0, heap->size - 1); heap->size--; - BLI_heap_down(heap, 0); + heap_down(heap, 0); } return ptr; @@ -201,12 +219,12 @@ void *BLI_heap_popmin(Heap *heap) void BLI_heap_remove(Heap *heap, HeapNode *node) { - int i = node->index; + unsigned int i = node->index; while (i > 0) { - int p = HEAP_PARENT(i); + unsigned int p = HEAP_PARENT(i); - HEAP_SWAP(heap, p, i); + heap_swap(heap, p, i); i = p; } diff --git a/source/blender/modifiers/intern/MOD_decimate.c b/source/blender/modifiers/intern/MOD_decimate.c index 7bcf56a1bfc..d55bc7ab9b1 100644 --- a/source/blender/modifiers/intern/MOD_decimate.c +++ b/source/blender/modifiers/intern/MOD_decimate.c @@ -49,6 +49,8 @@ #include "BKE_tessmesh.h" #include "bmesh.h" +// #define USE_TIMEIT + #ifdef USE_TIMEIT # include "PIL_time.h" #endif -- cgit v1.2.3