From 0bfc92ff8e16c76b8a01ace39f3e98b2beeda795 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Mon, 12 Nov 2012 05:53:43 +0000 Subject: BM_iter_as_arrayN() can now take an optional existing array argument, useful to avoid many small malloc's by passing a fixes size stack variable instead. Will give some speedup to edge-split modifier and bevel. --- source/blender/blenkernel/intern/mesh.c | 2 +- source/blender/bmesh/bmesh_class.h | 10 +++++-- source/blender/bmesh/intern/bmesh_construct.c | 4 +-- source/blender/bmesh/intern/bmesh_core.c | 33 +++++++++++++--------- .../blender/bmesh/intern/bmesh_decimate_dissolve.c | 4 +-- source/blender/bmesh/intern/bmesh_interp.c | 20 ++++++------- source/blender/bmesh/intern/bmesh_iterators.c | 10 +++++-- source/blender/bmesh/intern/bmesh_iterators.h | 3 +- source/blender/bmesh/intern/bmesh_polygon.c | 6 ++-- source/blender/bmesh/intern/bmesh_queries.c | 2 +- source/blender/bmesh/operators/bmo_bevel.c | 8 ++++-- source/blender/bmesh/operators/bmo_create.c | 6 ++-- source/blender/bmesh/operators/bmo_extrude.c | 4 +-- source/blender/editors/mesh/editmesh_knife.c | 4 +-- source/blender/editors/uvedit/uvedit_unwrap_ops.c | 2 +- 15 files changed, 70 insertions(+), 48 deletions(-) diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index 068059dc29a..fd5af6a20bb 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -3011,7 +3011,7 @@ float BKE_mesh_calc_poly_area(MPoly *mpoly, MLoop *loopstart, MLoop *l_iter = loopstart; float area, polynorm_local[3], (*vertexcos)[3]; const float *no = polynormal ? polynormal : polynorm_local; - BLI_array_fixedstack_declare(vertexcos, BM_NGON_STACK_SIZE, mpoly->totloop, __func__); + BLI_array_fixedstack_declare(vertexcos, BM_DEFAULT_NGON_STACK_SIZE, mpoly->totloop, __func__); /* pack vertex cos into an array for area_poly_v3 */ for (i = 0; i < mpoly->totloop; i++, l_iter++) { diff --git a/source/blender/bmesh/bmesh_class.h b/source/blender/bmesh/bmesh_class.h index cff7da78ef2..32ae7824739 100644 --- a/source/blender/bmesh/bmesh_class.h +++ b/source/blender/bmesh/bmesh_class.h @@ -243,10 +243,16 @@ enum { # define BM_FACE_FIRST_LOOP(p) ((p)->l_first) #endif -/* size to use for static arrays when dealing with NGons, +/** + * size to use for stack arrays when dealing with NGons, * alloc after this limit is reached. * this value is rather arbitrary */ -#define BM_NGON_STACK_SIZE 32 +#define BM_DEFAULT_NGON_STACK_SIZE 32 +/** + * size to use for stack arrays dealing with connected mesh data + * verts of faces, edges of vert - etc. + * often used with #BM_iter_as_arrayN() */ +#define BM_DEFAULT_ITER_STACK_SIZE 16 /* avoid inf loop, this value is arbitrary * but should not error on valid cases */ diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index eae78c6cc25..81405079a56 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -174,9 +174,9 @@ void BM_face_copy_shared(BMesh *bm, BMFace *f) BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble) { BMEdge **edges2 = NULL; - BLI_array_staticdeclare(edges2, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(edges2, BM_DEFAULT_NGON_STACK_SIZE); BMVert **verts = NULL; - BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); BMFace *f = NULL; BMEdge *e; BMVert *v, *ev1, *ev2; diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 0910dd82701..c0c550b0def 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -195,8 +195,8 @@ BMFace *BM_face_copy(BMesh *bm, BMFace *f, const short copyverts, const short co { BMVert **verts = NULL; BMEdge **edges = NULL; - BLI_array_fixedstack_declare(verts, BM_NGON_STACK_SIZE, f->len, __func__); - BLI_array_fixedstack_declare(edges, BM_NGON_STACK_SIZE, f->len, __func__); + BLI_array_fixedstack_declare(verts, BM_DEFAULT_NGON_STACK_SIZE, f->len, __func__); + BLI_array_fixedstack_declare(edges, BM_DEFAULT_NGON_STACK_SIZE, f->len, __func__); BMLoop *l_iter; BMLoop *l_first; BMLoop *l_copy; @@ -558,7 +558,7 @@ static void bm_kill_only_loop(BMesh *bm, BMLoop *l) void BM_face_edges_kill(BMesh *bm, BMFace *f) { BMEdge **edges = NULL; - BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE); BMLoop *l_iter; BMLoop *l_first; int i; @@ -582,7 +582,7 @@ void BM_face_edges_kill(BMesh *bm, BMFace *f) void BM_face_verts_kill(BMesh *bm, BMFace *f) { BMVert **verts = NULL; - BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); BMLoop *l_iter; BMLoop *l_first; int i; @@ -734,7 +734,7 @@ static int bm_loop_reverse_loop(BMesh *bm, BMFace *f const int do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS); BMLoop *l_iter, *oldprev, *oldnext; BMEdge **edar = NULL; - BLI_array_fixedstack_declare(edar, BM_NGON_STACK_SIZE, len, __func__); + BLI_array_fixedstack_declare(edar, BM_DEFAULT_NGON_STACK_SIZE, len, __func__); int i, j, edok; for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) { @@ -937,9 +937,9 @@ BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const short do_del BMEdge **edges = NULL; BMEdge **deledges = NULL; BMVert **delverts = NULL; - BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE); - BLI_array_staticdeclare(deledges, BM_NGON_STACK_SIZE); - BLI_array_staticdeclare(delverts, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE); + BLI_array_staticdeclare(deledges, BM_DEFAULT_NGON_STACK_SIZE); + BLI_array_staticdeclare(delverts, BM_DEFAULT_NGON_STACK_SIZE); BMVert *v1 = NULL, *v2 = NULL; const char *err = NULL; int i, tote = 0; @@ -1587,7 +1587,7 @@ BMEdge *bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv, const short check_edge_dou if (LIKELY(radlen)) { BMLoop **loops = NULL; - BLI_array_fixedstack_declare(loops, BM_NGON_STACK_SIZE, radlen, __func__); + BLI_array_fixedstack_declare(loops, BM_DEFAULT_NGON_STACK_SIZE, radlen, __func__); killoop = ke->l; @@ -1808,23 +1808,28 @@ BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) */ int BM_vert_splice(BMesh *bm, BMVert *v, BMVert *v_target) { - BMEdge *e; - + void *loops_stack[BM_DEFAULT_ITER_STACK_SIZE]; BMLoop **loops; int i, loops_tot; + BMEdge *e; + /* verts already spliced */ if (v == v_target) { return FALSE; } /* we can't modify the vert while iterating so first allocate an array of loops */ - loops = BM_iter_as_arrayN(bm, BM_LOOPS_OF_VERT, v, &loops_tot); - if (loops) { + loops = BM_iter_as_arrayN(bm, BM_LOOPS_OF_VERT, v, &loops_tot, + (void **)loops_stack, BM_DEFAULT_ITER_STACK_SIZE); + + if (LIKELY(loops != NULL)) { for (i = 0; i < loops_tot; i++) { loops[i]->v = v_target; } - MEM_freeN(loops); + if (loops != (BMLoop **)loops_stack) { + MEM_freeN(loops); + } } /* move all the edges from v's disk to vtarget's disk */ diff --git a/source/blender/bmesh/intern/bmesh_decimate_dissolve.c b/source/blender/bmesh/intern/bmesh_decimate_dissolve.c index d1371a18160..fb78050988d 100644 --- a/source/blender/bmesh/intern/bmesh_decimate_dissolve.c +++ b/source/blender/bmesh/intern/bmesh_decimate_dissolve.c @@ -231,8 +231,8 @@ void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const int do_ int vinput_len; int einput_len; - BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len); - BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len); + BMVert **vinput_arr = BM_iter_as_arrayN(bm, BM_VERTS_OF_MESH, NULL, &vinput_len, NULL, 0); + BMEdge **einput_arr = BM_iter_as_arrayN(bm, BM_EDGES_OF_MESH, NULL, &einput_len, NULL, 0); BM_mesh_decimate_dissolve_ex(bm, angle_limit, do_dissolve_boundaries, vinput_arr, vinput_len, diff --git a/source/blender/bmesh/intern/bmesh_interp.c b/source/blender/bmesh/intern/bmesh_interp.c index 508b3b8fcdf..caf9f3c70d5 100644 --- a/source/blender/bmesh/intern/bmesh_interp.c +++ b/source/blender/bmesh/intern/bmesh_interp.c @@ -174,9 +174,9 @@ void BM_face_interp_from_face(BMesh *bm, BMFace *target, BMFace *source) void **blocks = NULL; float (*cos)[3] = NULL, *w = NULL; - BLI_array_fixedstack_declare(cos, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(w, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(blocks, BM_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(cos, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(w, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(blocks, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); int i; BM_elem_attrs_copy(bm, bm, source, target); @@ -613,10 +613,10 @@ void BM_loop_interp_from_face(BMesh *bm, BMLoop *target, BMFace *source, void **vblocks = NULL; float (*cos)[3] = NULL, co[3], *w = NULL; float cent[3] = {0.0f, 0.0f, 0.0f}; - BLI_array_fixedstack_declare(cos, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(w, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(blocks, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(vblocks, BM_NGON_STACK_SIZE, do_vertex ? source->len : 0, __func__); + BLI_array_fixedstack_declare(cos, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(w, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(blocks, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(vblocks, BM_DEFAULT_NGON_STACK_SIZE, do_vertex ? source->len : 0, __func__); int i, ax, ay; BM_elem_attrs_copy(bm, bm, source, target->f); @@ -689,9 +689,9 @@ void BM_vert_interp_from_face(BMesh *bm, BMVert *v, BMFace *source) void **blocks = NULL; float (*cos)[3] = NULL, *w = NULL; float cent[3] = {0.0f, 0.0f, 0.0f}; - BLI_array_fixedstack_declare(cos, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(w, BM_NGON_STACK_SIZE, source->len, __func__); - BLI_array_fixedstack_declare(blocks, BM_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(cos, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(w, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); + BLI_array_fixedstack_declare(blocks, BM_DEFAULT_NGON_STACK_SIZE, source->len, __func__); int i; i = 0; diff --git a/source/blender/bmesh/intern/bmesh_iterators.c b/source/blender/bmesh/intern/bmesh_iterators.c index 1cb95d94e9b..51a3776c21d 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.c +++ b/source/blender/bmesh/intern/bmesh_iterators.c @@ -116,10 +116,14 @@ int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, cons * * Caller needs to free the array. */ -void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len) +void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len, + /* optional static vars to avoid an alloc */ + void **stack_array, int stack_array_size) { BMIter iter; + BLI_assert(stack_array_size == 0 || (stack_array_size && stack_array)); + /* we can't rely on coun't being set */ switch (itype) { case BM_VERTS_OF_MESH: @@ -137,7 +141,9 @@ void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len) if (BM_iter_init(&iter, bm, itype, data) && iter.count > 0) { BMElem *ele; - BMElem **array = MEM_mallocN(sizeof(ele) * iter.count, __func__); + BMElem **array = iter.count > stack_array_size ? + MEM_mallocN(sizeof(ele) * iter.count, __func__) : + stack_array; int i = 0; *r_len = iter.count; /* set before iterating */ diff --git a/source/blender/bmesh/intern/bmesh_iterators.h b/source/blender/bmesh/intern/bmesh_iterators.h index 3c42b3d610c..c0eefc2a3aa 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.h +++ b/source/blender/bmesh/intern/bmesh_iterators.h @@ -125,7 +125,8 @@ __attribute__((warn_unused_result)) #endif ; int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len); -void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len) +void *BM_iter_as_arrayN(BMesh *bm, const char itype, void *data, int *r_len, + void **stack_array, int stack_array_size) #ifdef __GNUC__ __attribute__((warn_unused_result)) #endif diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 98edceb30a2..35213c83097 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -162,7 +162,7 @@ float BM_face_calc_area(BMFace *f) float area; int i; - BLI_array_fixedstack_declare(verts, BM_NGON_STACK_SIZE, f->len, __func__); + BLI_array_fixedstack_declare(verts, BM_DEFAULT_NGON_STACK_SIZE, f->len, __func__); BM_ITER_ELEM_INDEX (l, &iter, f, BM_LOOPS_OF_FACE, i) { copy_v3_v3(verts[i], l->v->co); @@ -965,8 +965,8 @@ void BM_face_legal_splits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len) float fac1 = 1.0000001f, fac2 = 0.9f; //9999f; //0.999f; int i, j, a = 0, clen; - BLI_array_fixedstack_declare(projverts, BM_NGON_STACK_SIZE, f->len, "projvertsb"); - BLI_array_fixedstack_declare(edgeverts, BM_NGON_STACK_SIZE * 2, len * 2, "edgevertsb"); + BLI_array_fixedstack_declare(projverts, BM_DEFAULT_NGON_STACK_SIZE, f->len, "projvertsb"); + BLI_array_fixedstack_declare(edgeverts, BM_DEFAULT_NGON_STACK_SIZE * 2, len * 2, "edgevertsb"); i = 0; l = BM_iter_new(&iter, bm, BM_LOOPS_OF_FACE, f); diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 205108395e6..cae9b5b3b83 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -1393,7 +1393,7 @@ int BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len) int BM_face_exists_multi_edge(BMEdge **earr, int len) { BMVert **varr; - BLI_array_fixedstack_declare(varr, BM_NGON_STACK_SIZE, len, __func__); + BLI_array_fixedstack_declare(varr, BM_DEFAULT_NGON_STACK_SIZE, len, __func__); int ok; int i, i_next; diff --git a/source/blender/bmesh/operators/bmo_bevel.c b/source/blender/bmesh/operators/bmo_bevel.c index 7fededd0635..e18920fc98e 100644 --- a/source/blender/bmesh/operators/bmo_bevel.c +++ b/source/blender/bmesh/operators/bmo_bevel.c @@ -1265,8 +1265,10 @@ static void rebuild_polygon(BMesh *bm, BevelParams *bp, BMFace *f) /* All polygons touching v need rebuilding because beveling v has made new vertices */ static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert *v) { + void *faces_stack[BM_DEFAULT_ITER_STACK_SIZE]; int faces_len, f_index; - BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len); + BMFace **faces = BM_iter_as_arrayN(bm, BM_FACES_OF_VERT, v, &faces_len, + faces_stack, BM_DEFAULT_ITER_STACK_SIZE); if (LIKELY(faces != NULL)) { for (f_index = 0; f_index < faces_len; f_index++) { @@ -1275,7 +1277,9 @@ static void bevel_rebuild_existing_polygons(BMesh *bm, BevelParams *bp, BMVert * BM_face_kill(bm, f); } - MEM_freeN(faces); + if (faces != (BMFace **)faces_stack) { + MEM_freeN(faces); + } } } diff --git a/source/blender/bmesh/operators/bmo_create.c b/source/blender/bmesh/operators/bmo_create.c index 093f567d995..49a2f959063 100644 --- a/source/blender/bmesh/operators/bmo_create.c +++ b/source/blender/bmesh/operators/bmo_create.c @@ -168,7 +168,7 @@ static void rotsys_reverse(BMEdge *UNUSED(e), BMVert *v, EdgeData *edata, VertDa BMEdge **edges = NULL; BMEdge *e_first; BMEdge *e; - BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE); int i, totedge; e = e_first = vdata[BM_elem_index_get(v)].e; @@ -359,10 +359,10 @@ static void init_rotsys(BMesh *bm, EdgeData *edata, VertData *vdata) BMIter iter; BMEdge *e; BMEdge **edges = NULL; - BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE); BMVert *v; /* BMVert **verts = NULL; */ - /* BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE); */ /* UNUSE */ + /* BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); */ /* UNUSE */ int i; BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { diff --git a/source/blender/bmesh/operators/bmo_extrude.c b/source/blender/bmesh/operators/bmo_extrude.c index 627351ead11..71048e18335 100644 --- a/source/blender/bmesh/operators/bmo_extrude.c +++ b/source/blender/bmesh/operators/bmo_extrude.c @@ -595,10 +595,10 @@ static void solidify_add_thickness(BMesh *bm, const float dist) /* array for passing verts to angle_poly_v3 */ float **verts = NULL; - BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); /* array for receiving angles from angle_poly_v3 */ float *face_angles = NULL; - BLI_array_staticdeclare(face_angles, BM_NGON_STACK_SIZE); + BLI_array_staticdeclare(face_angles, BM_DEFAULT_NGON_STACK_SIZE); BM_mesh_elem_index_ensure(bm, BM_VERT); diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c index 82447cc0168..5ba85115b2f 100644 --- a/source/blender/editors/mesh/editmesh_knife.c +++ b/source/blender/editors/mesh/editmesh_knife.c @@ -2573,8 +2573,8 @@ static void knife_make_chain_cut(KnifeTool_OpData *kcd, BMFace *f, ListBase *cha int nco = BLI_countlist(chain) - 1; float (*cos)[3] = NULL; KnifeVert **kverts; - BLI_array_fixedstack_declare(cos, BM_NGON_STACK_SIZE, nco, __func__); - BLI_array_fixedstack_declare(kverts, BM_NGON_STACK_SIZE, nco, __func__); + BLI_array_fixedstack_declare(cos, BM_DEFAULT_NGON_STACK_SIZE, nco, __func__); + BLI_array_fixedstack_declare(kverts, BM_DEFAULT_NGON_STACK_SIZE, nco, __func__); kfe = ((Ref *)chain->first)->ref; v1 = kfe->v1->v ? kfe->v1->v : kfe->v2->v; diff --git a/source/blender/editors/uvedit/uvedit_unwrap_ops.c b/source/blender/editors/uvedit/uvedit_unwrap_ops.c index f615902eedf..fc60c5a3a0f 100644 --- a/source/blender/editors/uvedit/uvedit_unwrap_ops.c +++ b/source/blender/editors/uvedit/uvedit_unwrap_ops.c @@ -1414,7 +1414,7 @@ static void uv_map_mirror(BMEditMesh *em, BMFace *efa, MTexPoly *UNUSED(tf)) BMIter liter; MLoopUV *luv; float **uvs = NULL; - BLI_array_fixedstack_declare(uvs, BM_NGON_STACK_SIZE, efa->len, __func__); + BLI_array_fixedstack_declare(uvs, BM_DEFAULT_NGON_STACK_SIZE, efa->len, __func__); float dx; int i, mi; -- cgit v1.2.3