[Bf-blender-cvs] [fee6ab18e7e] blender2.8: BLI_heap: implement a limited but faster version of heap.
Alexander Gavrilov
noreply at git.blender.org
Mon Nov 5 19:04:31 CET 2018
Commit: fee6ab18e7e9a38203bf8eb95d114ac837578aa7
Author: Alexander Gavrilov
Date: Mon Nov 5 19:14:40 2018 +0300
Branches: blender2.8
https://developer.blender.org/rBfee6ab18e7e9a38203bf8eb95d114ac837578aa7
BLI_heap: implement a limited but faster version of heap.
If the user only needs insertion and removal from top, there is
no need to allocate and manage separate HeapNode objects: the
data can be stored directly in the main tree array.
This measured a 24% FPS increase on a ~50% heap-heavy workload.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D3898
===================================================================
M source/blender/blenkernel/intern/pbvh_bmesh.c
M source/blender/blenlib/BLI_heap.h
M source/blender/blenlib/intern/BLI_heap.c
M source/blender/blenlib/intern/astar.c
M source/blender/bmesh/operators/bmo_connect_pair.c
M source/blender/bmesh/tools/bmesh_path.c
M source/blender/editors/curve/editcurve_select.c
M source/blender/editors/mesh/editmesh_tools.c
M source/blender/modifiers/intern/MOD_skin.c
M tests/gtests/blenlib/BLI_heap_test.cc
===================================================================
diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c
index e32a5d0681e..0180bdc9e4d 100644
--- a/source/blender/blenkernel/intern/pbvh_bmesh.c
+++ b/source/blender/blenkernel/intern/pbvh_bmesh.c
@@ -721,7 +721,7 @@ static void pbvh_bmesh_node_drop_orig(PBVHNode *node)
struct EdgeQueue;
typedef struct EdgeQueue {
- Heap *heap;
+ FastHeap *heap;
const float *center;
float center_proj[3]; /* for when we use projected coords. */
float radius_squared;
@@ -840,7 +840,7 @@ static void edge_queue_insert(
BMVert **pair = BLI_mempool_alloc(eq_ctx->pool);
pair[0] = e->v1;
pair[1] = e->v2;
- BLI_heap_insert(eq_ctx->q->heap, priority, pair);
+ BLI_fastheap_insert(eq_ctx->q->heap, priority, pair);
#ifdef USE_EDGEQUEUE_TAG
BLI_assert(EDGE_QUEUE_TEST(e) == false);
EDGE_QUEUE_ENABLE(e);
@@ -1008,7 +1008,7 @@ static void long_edge_queue_create(
PBVH *bvh, const float center[3], const float view_normal[3],
float radius, const bool use_frontface, const bool use_projected)
{
- eq_ctx->q->heap = BLI_heap_new();
+ eq_ctx->q->heap = BLI_fastheap_new();
eq_ctx->q->center = center;
eq_ctx->q->radius_squared = radius * radius;
eq_ctx->q->limit_len_squared = bvh->bm_max_edge_len * bvh->bm_max_edge_len;
@@ -1070,7 +1070,7 @@ static void short_edge_queue_create(
PBVH *bvh, const float center[3], const float view_normal[3],
float radius, const bool use_frontface, const bool use_projected)
{
- eq_ctx->q->heap = BLI_heap_new();
+ eq_ctx->q->heap = BLI_fastheap_new();
eq_ctx->q->center = center;
eq_ctx->q->radius_squared = radius * radius;
eq_ctx->q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len;
@@ -1237,8 +1237,8 @@ static bool pbvh_bmesh_subdivide_long_edges(
{
bool any_subdivided = false;
- while (!BLI_heap_is_empty(eq_ctx->q->heap)) {
- BMVert **pair = BLI_heap_pop_min(eq_ctx->q->heap);
+ while (!BLI_fastheap_is_empty(eq_ctx->q->heap)) {
+ BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap);
BMVert *v1 = pair[0], *v2 = pair[1];
BMEdge *e;
@@ -1454,8 +1454,8 @@ static bool pbvh_bmesh_collapse_short_edges(
/* deleted verts point to vertices they were merged into, or NULL when removed. */
GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts");
- while (!BLI_heap_is_empty(eq_ctx->q->heap)) {
- BMVert **pair = BLI_heap_pop_min(eq_ctx->q->heap);
+ while (!BLI_fastheap_is_empty(eq_ctx->q->heap)) {
+ BMVert **pair = BLI_fastheap_pop_min(eq_ctx->q->heap);
BMVert *v1 = pair[0], *v2 = pair[1];
BLI_mempool_free(eq_ctx->pool, pair);
pair = NULL;
@@ -1961,7 +1961,7 @@ bool BKE_pbvh_bmesh_update_topology(
short_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius, use_frontface, use_projected);
modified |= pbvh_bmesh_collapse_short_edges(
&eq_ctx, bvh, &deleted_faces);
- BLI_heap_free(q.heap, NULL);
+ BLI_fastheap_free(q.heap, NULL);
BLI_mempool_destroy(queue_pool);
}
@@ -1976,7 +1976,7 @@ bool BKE_pbvh_bmesh_update_topology(
long_edge_queue_create(&eq_ctx, bvh, center, view_normal, radius, use_frontface, use_projected);
modified |= pbvh_bmesh_subdivide_long_edges(
&eq_ctx, bvh, &edge_loops);
- BLI_heap_free(q.heap, NULL);
+ BLI_fastheap_free(q.heap, NULL);
BLI_mempool_destroy(queue_pool);
}
diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h
index 35c8df3075c..08adb0d538c 100644
--- a/source/blender/blenlib/BLI_heap.h
+++ b/source/blender/blenlib/BLI_heap.h
@@ -54,4 +54,19 @@ void *BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT
/* only for gtest */
bool BLI_heap_is_valid(const Heap *heap);
+/* Simplified version of the heap that only supports insertion and removal from top. */
+
+struct FastHeap;
+typedef struct FastHeap FastHeap;
+
+FastHeap *BLI_fastheap_new_ex(unsigned int tot_reserve) ATTR_WARN_UNUSED_RESULT;
+FastHeap *BLI_fastheap_new(void) ATTR_WARN_UNUSED_RESULT;
+void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1);
+void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1);
+void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr) ATTR_NONNULL(1);
+bool BLI_fastheap_is_empty(const FastHeap *heap) ATTR_NONNULL(1);
+unsigned int BLI_fastheap_len(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+float BLI_fastheap_top_value(const FastHeap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+void *BLI_fastheap_pop_min(FastHeap *heap) ATTR_NONNULL(1);
+
#endif /* __BLI_HEAP_H__ */
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index c785c1ac012..cef3eb2dafb 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -73,6 +73,17 @@ struct Heap {
} nodes;
};
+typedef struct FastHeapNode {
+ float value;
+ void *ptr;
+} FastHeapNode;
+
+struct FastHeap {
+ uint size;
+ uint bufsize;
+ FastHeapNode *tree;
+};
+
/** \name Internal Functions
* \{ */
@@ -441,3 +452,191 @@ bool BLI_heap_is_valid(const Heap *heap)
}
/** \} */
+
+/** \name FastHeap Internal Functions
+ * \{ */
+
+static void fastheap_down(FastHeap *heap, uint start_i, const FastHeapNode *init)
+{
+#if 1
+ /* The compiler isn't smart enough to realize that all computations
+ * using index here can be modified to work with byte offset. */
+ uint8_t *const tree_buf = (uint8_t*)heap->tree;
+
+#define OFFSET(i) (i * (uint)sizeof(FastHeapNode))
+#define NODE(offset) (*(FastHeapNode*)(tree_buf + (offset)))
+#else
+ FastHeapNode *const tree = heap->tree;
+
+#define OFFSET(i) (i)
+#define NODE(i) tree[i]
+#endif
+
+#define HEAP_LEFT_OFFSET(i) (((i) << 1) + OFFSET(1))
+
+ const uint size = OFFSET(heap->size);
+
+ /* Pull the active node values into locals. This allows spilling
+ * the data from registers instead of literally swapping nodes. */
+ float active_val = init->value;
+ void *active_ptr = init->ptr;
+
+ /* Prepare the first iteration and spill value. */
+ uint i = OFFSET(start_i);
+
+ NODE(i).value = active_val;
+
+ for (;;) {
+ const uint l = HEAP_LEFT_OFFSET(i);
+ const uint r = l + OFFSET(1); /* right */
+
+ /* Find the child with the smallest value. */
+ uint smallest = i;
+
+ if (LIKELY(l < size) && NODE(l).value < active_val) {
+ smallest = l;
+ }
+ if (LIKELY(r < size) && NODE(r).value < NODE(smallest).value) {
+ smallest = r;
+ }
+
+ if (UNLIKELY(smallest == i)) {
+ break;
+ }
+
+ /* Move the smallest child into the current node.
+ * Skip padding: for some reason that makes it faster here. */
+ NODE(i).value = NODE(smallest).value;
+ NODE(i).ptr = NODE(smallest).ptr;
+
+ /* Proceed to next iteration and spill value. */
+ i = smallest;
+ NODE(i).value = active_val;
+ }
+
+ /* Spill the pointer into the final position of the node. */
+ NODE(i).ptr = active_ptr;
+
+#undef NODE
+#undef OFFSET
+#undef HEAP_LEFT_OFFSET
+}
+
+static void fastheap_up(FastHeap *heap, uint i, float active_val, void *active_ptr)
+{
+ FastHeapNode *const tree = heap->tree;
+
+ while (LIKELY(i > 0)) {
+ const uint p = HEAP_PARENT(i);
+
+ if (active_val >= tree[p].value) {
+ break;
+ }
+
+ tree[i] = tree[p];
+ i = p;
+ }
+
+ tree[i].value = active_val;
+ tree[i].ptr = active_ptr;
+}
+
+/** \} */
+
+/** \name Public FastHeap API
+ * \{ */
+
+/**
+ * Creates a new fast heap, which only supports insertion and removal from top.
+ *
+ * \note Use when the size of the heap is known in advance.
+ */
+FastHeap *BLI_fastheap_new_ex(uint tot_reserve)
+{
+ FastHeap *heap = MEM_mallocN(sizeof(FastHeap), __func__);
+ /* ensure we have at least one so we can keep doubling it */
+ heap->size = 0;
+ heap->bufsize = MAX2(1u, tot_reserve);
+ heap->tree = MEM_mallocN(heap->bufsize * sizeof(FastHeapNode), "BLIFastHeapTree");
+ return heap;
+}
+
+FastHeap *BLI_fastheap_new(void)
+{
+ return BLI_fastheap_new_ex(1);
+}
+
+void BLI_fastheap_free(FastHeap *heap, HeapFreeFP ptrfreefp)
+{
+ if (ptrfreefp) {
+ for (uint i = 0; i < heap->size; i++) {
+ ptrfreefp(heap->tree[i].ptr);
+ }
+ }
+
+ MEM_freeN(heap->tree);
+ MEM_freeN(heap);
+}
+
+void BLI_fastheap_clear(FastHeap *heap, HeapFreeFP ptrfreefp)
+{
+ if (ptrfreefp) {
+ for (uint i = 0; i < heap->size; i++) {
+ ptrfreefp(heap->tree[i].ptr);
+ }
+ }
+
+ heap->size = 0;
+}
+
+/**
+ * Insert heap node with a value (often a 'cost') and pointer into the heap,
+ * duplicate values are allowed.
+ */
+void BLI_fastheap_insert(FastHeap *heap, float value, void *ptr)
+{
+ if (UNLIKELY(heap->size >= heap->bufsize)) {
+ heap->bufsize *= 2;
+ heap->tree = MEM_reallocN(heap->tree, heap->bufsize * sizeof(*heap->tree));
+ }
+
+ fastheap_up(heap, heap->size++, value, ptr);
+}
+
+bool BLI_fastheap_is_empty(const FastHeap *heap)
+{
+ return (heap->size == 0);
+}
+
+uint BLI_fastheap_len(const FastHeap *heap)
+{
+ return heap->size;
+}
+
+/**
+ * Return the lowest value of the heap.
+ */
+float BLI_fastheap_top_value(const FastHeap *heap)
+{
+ BLI_assert(heap->size != 0);
+
+ return heap->tree[0].value;
+}
+
+/**
+ * Pop the top node off the heap and return it's pointer.
+ */
+void *BLI_fastheap_pop_min(FastHeap *heap)
+{
+ BLI_assert(heap->size != 0);
+
+ void *ptr = heap->tree[0].ptr;
+
+ if (--heap->size) {
+ fastheap_down(heap, 0, &heap->tree[heap->size]);
+ }
+
+ return ptr;
+}
+
+/** \} */
diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c
index 86c1faad096..54c80def972 100644
--- a/source/blender/blenlib/intern/astar.c
+++ b/source/blender/blenlib/intern/astar.c
@@ -206,7 +206,7 @@ bool BLI_astar_graph_solve(
BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, astar_f_cost f_cost_cb,
BLI_AStarSolution *r_solution, const int max_steps)
{
- Heap *todo_nodes;
+ FastHeap *todo_nodes;
BLI_bitmap *done_nodes = r_solution->done_nodes;
int *prev_nodes = r_solution->prev_nodes;
@@ -225,13 +225,13 @@ bool BLI_astar_graph_solve(
return true;
}
- todo_nodes = BLI_heap_new();
- BLI_heap_insert(todo_nodes,
- f_cost_cb(as_graph, r
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list