[Bf-blender-cvs] [a70589e439b] blender2.8: BLI_heap: optimize heap_swap, heap_down and heap_up.
Alexander Gavrilov
noreply at git.blender.org
Mon Nov 5 15:18:33 CET 2018
Commit: a70589e439b3fb00fb5c54971df823931a8d00eb
Author: Alexander Gavrilov
Date: Sun Nov 4 12:17:09 2018 +0300
Branches: blender2.8
https://developer.blender.org/rBa70589e439b3fb00fb5c54971df823931a8d00eb
BLI_heap: optimize heap_swap, heap_down and heap_up.
The index field of nodes is supposed to be its actual index, so
there is no need to read it in swap. On a 64-bit processor i and
j are already in registers, so this removes two memory reads.
In addition, cache the tree pointer, use branch hints, and
put the most frequently accessed 'value' field at 0 offset.
Produced a 20% FPS improvement for a 50% heap-heavy workload.
===================================================================
M source/blender/blenlib/intern/BLI_heap.c
===================================================================
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index 17a15f93266..c785c1ac012 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -38,9 +38,9 @@
/***/
struct HeapNode {
- void *ptr;
float value;
uint index;
+ void *ptr;
};
struct HeapNode_Chunk {
@@ -87,8 +87,14 @@ struct Heap {
BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
{
-
-#if 0
+#if 1
+ HeapNode **tree = heap->tree;
+ HeapNode *pi = tree[i], *pj = tree[j];
+ pi->index = j;
+ tree[j] = pi;
+ pj->index = i;
+ tree[i] = pj;
+#elif 0
SWAP(uint, heap->tree[i]->index, heap->tree[j]->index);
SWAP(HeapNode *, heap->tree[i], heap->tree[j]);
#else
@@ -105,6 +111,7 @@ BLI_INLINE void heap_swap(Heap *heap, const uint i, const uint j)
static void heap_down(Heap *heap, uint i)
{
/* size won't change in the loop */
+ HeapNode **const tree = heap->tree;
const uint size = heap->size;
while (1) {
@@ -112,14 +119,14 @@ static void heap_down(Heap *heap, uint i)
const uint r = HEAP_RIGHT(i);
uint smallest = i;
- if ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[smallest])) {
+ if (LIKELY(l < size) && HEAP_COMPARE(tree[l], tree[smallest])) {
smallest = l;
}
- if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest])) {
+ if (LIKELY(r < size) && HEAP_COMPARE(tree[r], tree[smallest])) {
smallest = r;
}
- if (smallest == i) {
+ if (UNLIKELY(smallest == i)) {
break;
}
@@ -130,10 +137,12 @@ static void heap_down(Heap *heap, uint i)
static void heap_up(Heap *heap, uint i)
{
- while (i > 0) {
+ HeapNode **const tree = heap->tree;
+
+ while (LIKELY(i > 0)) {
const uint p = HEAP_PARENT(i);
- if (HEAP_COMPARE(heap->tree[p], heap->tree[i])) {
+ if (HEAP_COMPARE(tree[p], tree[i])) {
break;
}
heap_swap(heap, p, i);
@@ -405,6 +414,9 @@ void *BLI_heap_node_ptr(const HeapNode *node)
static bool heap_is_minheap(const Heap *heap, uint root)
{
if (root < heap->size) {
+ if (heap->tree[root]->index != root) {
+ return false;
+ }
const uint l = HEAP_LEFT(root);
if (l < heap->size) {
if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) {
More information about the Bf-blender-cvs
mailing list