From 4c042f21450eb6a4c8e1d16d6a7def45d48ceaf2 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 9 May 2013 12:46:35 +0000 Subject: bmesh: optimize bmesh_vert_separate, redice allocs (best cast it wont do any allocs). gives approx 16% overall speedup to edgesplit modifier. also reduce size of smallhash stack, was 521, which got doubled and was quite large on the stack. reduce to 64. --- source/blender/blenlib/BLI_smallhash.h | 2 +- source/blender/bmesh/intern/bmesh_core.c | 76 ++++++++++++++++++++------------ 2 files changed, 49 insertions(+), 29 deletions(-) diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h index 84cd68e9d9c..b6acc06159a 100644 --- a/source/blender/blenlib/BLI_smallhash.h +++ b/source/blender/blenlib/BLI_smallhash.h @@ -43,7 +43,7 @@ typedef struct { } SmallHashEntry; /*how much stack space to use before dynamically allocating memory*/ -#define SMSTACKSIZE 521 +#define SMSTACKSIZE 64 typedef struct SmallHash { SmallHashEntry *table; SmallHashEntry _stacktable[SMSTACKSIZE]; diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index bec9d5c4d1a..92bab258d5c 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -30,6 +30,7 @@ #include "BLI_math_vector.h" #include "BLI_listbase.h" #include "BLI_array.h" +#include "BLI_smallhash.h" #include "BLF_translation.h" @@ -1890,45 +1891,62 @@ bool BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target) */ bool bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len) { - BMEdge **stack = NULL; - BLI_array_staticdeclare(stack, BM_DEFAULT_ITER_STACK_SIZE); + const int v_edgetot = BM_vert_face_count(v); + BMEdge **stack = BLI_array_alloca(stack, v_edgetot); + unsigned int _stack_i; + + /* */ +#define STACK_INIT(stack) ((void)stack, (void)(_stack_i = 0)) +#define STACK_PUSH(stack, val) (void)((stack)[_stack_i++] = val) +#define STACK_POP(stack) ((void)0, (_stack_i ? ((stack)[--_stack_i]) : NULL)) +#define STACK_FREE(stack) ((void)stack) + + SmallHash visithash; BMVert **verts = NULL; - GHash *visithash; BMIter eiter, liter; BMLoop *l; BMEdge *e; int i, maxindex; BMLoop *l_new; - visithash = BLI_ghash_ptr_new(__func__); + BLI_smallhash_init(&visithash); + + STACK_INIT(stack); maxindex = 0; BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - if (BLI_ghash_haskey(visithash, e)) { + if (BLI_smallhash_haskey(&visithash, (uintptr_t)e)) { continue; } - /* Prime the stack with this unvisited edge */ - BLI_array_append(stack, e); - /* Considering only edges and faces incident on vertex v, walk * the edges & faces and assign an index to each connected set */ - while ((e = BLI_array_pop(stack))) { - BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex)); - - BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) { - l_new = (l->v == v) ? l->prev : l->next; - if (!BLI_ghash_haskey(visithash, l_new->e)) { - BLI_array_append(stack, l_new->e); - } + do { + BLI_smallhash_insert(&visithash, (uintptr_t)e, SET_INT_IN_POINTER(maxindex)); + + if (e->l) { + BMLoop *l_iter, *l_first; + l_iter = l_first = e->l; + do { + l_new = (l_iter->v == v) ? l_iter->prev : l_iter->next; + if (!BLI_smallhash_haskey(&visithash, (uintptr_t)l_new->e)) { + STACK_PUSH(stack, l_new->e); + } + } while ((l_iter = l_iter->radial_next) != l_first); } - } + } while ((e = STACK_POP(stack))); maxindex++; } /* Make enough verts to split v for each group */ - verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__); + if (r_vout != NULL) { + verts = MEM_callocN(sizeof(BMVert *) * maxindex, __func__); + } + else { + verts = BLI_array_alloca(verts, maxindex); + } + verts[0] = v; for (i = 1; i < maxindex; i++) { verts[i] = BM_vert_create(bm, v->co, v, 0); @@ -1961,23 +1979,23 @@ bool bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len * by modifying data it loops over [#30632], this re-uses the 'stack' variable which is a bit * bad practice but save alloc'ing a new array - note, the comment above is useful, keep it * if you are tidying up code - campbell */ - BLI_array_empty(stack); + STACK_INIT(stack); BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { if (l->v == v) { - BLI_array_append(stack, (BMEdge *)l); + STACK_PUSH(stack, (BMEdge *)l); } } - while ((l = (BMLoop *)(BLI_array_pop(stack)))) { - if ((i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e)))) { + while ((l = (BMLoop *)(STACK_POP(stack)))) { + if ((i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)l->e)))) { l->v = verts[i]; } } #endif - BLI_array_free(stack); + STACK_FREE(stack); BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { - i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e)); + i = GET_INT_FROM_POINTER(BLI_smallhash_lookup(&visithash, (uintptr_t)e)); if (i == 0) { continue; } @@ -1988,7 +2006,7 @@ bool bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len bmesh_disk_edge_append(e, verts[i]); } - BLI_ghash_free(visithash, NULL, NULL); + BLI_smallhash_release(&visithash); for (i = 0; i < maxindex; i++) { BM_CHECK_ELEMENT(verts[i]); @@ -2001,9 +2019,11 @@ bool bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len if (r_vout != NULL) { *r_vout = verts; } - else { - MEM_freeN(verts); - } + +#undef STACK_INIT +#undef STACK_PUSH +#undef STACK_POP +#undef STACK_FREE return true; } -- cgit v1.2.3