From fee6ab18e7e9a38203bf8eb95d114ac837578aa7 Mon Sep 17 00:00:00 2001 From: Alexander Gavrilov Date: Mon, 5 Nov 2018 19:14:40 +0300 Subject: 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 --- source/blender/bmesh/operators/bmo_connect_pair.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'source/blender/bmesh/operators/bmo_connect_pair.c') diff --git a/source/blender/bmesh/operators/bmo_connect_pair.c b/source/blender/bmesh/operators/bmo_connect_pair.c index b9e5cd927c3..3b3766b6f3a 100644 --- a/source/blender/bmesh/operators/bmo_connect_pair.c +++ b/source/blender/bmesh/operators/bmo_connect_pair.c @@ -94,7 +94,7 @@ // #define DEBUG_PRINT typedef struct PathContext { - Heap *states; + FastHeap *states; float matrix[3][3]; float axis_sep; @@ -331,7 +331,7 @@ static PathLinkState *state_link_add_test( /* after adding a link so we use the updated 'state->dist' */ if (is_new) { - BLI_heap_insert(pc->states, state->dist, state); + BLI_fastheap_insert(pc->states, state->dist, state); } return state; @@ -640,7 +640,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) /* setup context */ { - pc.states = BLI_heap_new(); + pc.states = BLI_fastheap_new(); pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP); } @@ -655,18 +655,18 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) PathLinkState *state; state = MEM_callocN(sizeof(*state), __func__); state_link_add(&pc, state, (BMElem *)pc.v_a, NULL); - BLI_heap_insert(pc.states, state->dist, state); + BLI_fastheap_insert(pc.states, state->dist, state); } - while (!BLI_heap_is_empty(pc.states)) { + while (!BLI_fastheap_is_empty(pc.states)) { #ifdef DEBUG_PRINT - printf("\n%s: stepping %u\n", __func__, BLI_heap_len(pc.states)); + printf("\n%s: stepping %u\n", __func__, BLI_fastheap_len(pc.states)); #endif - while (!BLI_heap_is_empty(pc.states)) { - PathLinkState *state = BLI_heap_pop_min(pc.states); + while (!BLI_fastheap_is_empty(pc.states)) { + PathLinkState *state = BLI_fastheap_pop_min(pc.states); /* either we insert this into 'pc.states' or its freed */ bool continue_search; @@ -679,7 +679,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) state_best = *state; /* we're done, exit all loops */ - BLI_heap_clear(pc.states, MEM_freeN); + BLI_fastheap_clear(pc.states, MEM_freeN); continue_search = false; } else if (state_step(&pc, state)) { @@ -696,7 +696,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) } if (continue_search) { - BLI_heap_insert(pc.states, state->dist, state); + BLI_fastheap_insert(pc.states, state->dist, state); } else { MEM_freeN(state); @@ -732,7 +732,7 @@ void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op) BLI_mempool_destroy(pc.link_pool); - BLI_heap_free(pc.states, MEM_freeN); + BLI_fastheap_free(pc.states, MEM_freeN); #if 1 if (state_best.link_last) { -- cgit v1.2.3