From 09a52f18b6d8bd77cbffd746f72e866e1740505f Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sat, 24 Aug 2013 17:33:47 +0000 Subject: ghash: reserve size when its known or can be guessed close enough. also avoid allocs per node in pbvh_bmesh_node_limit_ensure() --- source/blender/blenkernel/intern/object_deform.c | 2 +- source/blender/blenkernel/intern/pbvh.c | 5 +++-- source/blender/blenkernel/intern/pbvh_bmesh.c | 24 ++++++++++++++-------- source/blender/blenkernel/intern/treehash.c | 2 +- source/blender/bmesh/intern/bmesh_log.c | 6 +++--- source/blender/bmesh/intern/bmesh_mesh.c | 6 +++--- source/blender/bmesh/intern/bmesh_operators.c | 2 +- source/blender/bmesh/intern/bmesh_walkers.c | 10 ++++----- source/blender/bmesh/intern/bmesh_walkers_impl.c | 17 +++++++-------- source/blender/editors/curve/editcurve.c | 2 +- source/blender/editors/mesh/meshtools.c | 2 +- source/blender/makesdna/intern/dna_genfile.c | 2 +- source/blender/windowmanager/intern/wm.c | 5 +++-- source/blender/windowmanager/intern/wm_operators.c | 3 ++- 14 files changed, 47 insertions(+), 41 deletions(-) diff --git a/source/blender/blenkernel/intern/object_deform.c b/source/blender/blenkernel/intern/object_deform.c index 9cb7c91decd..77c5e57f382 100644 --- a/source/blender/blenkernel/intern/object_deform.c +++ b/source/blender/blenkernel/intern/object_deform.c @@ -79,7 +79,7 @@ bool *BKE_objdef_validmap_get(Object *ob, const int defbase_tot) return NULL; } - gh = BLI_ghash_str_new("BKE_objdef_validmap_get gh"); + gh = BLI_ghash_str_new_ex("BKE_objdef_validmap_get gh", defbase_tot); /* add all names to a hash table */ for (dg = ob->defbase.first; dg; dg = dg->next) { diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c index 3907f4d8082..df227b6accb 100644 --- a/source/blender/blenkernel/intern/pbvh.c +++ b/source/blender/blenkernel/intern/pbvh.c @@ -277,11 +277,12 @@ static void build_mesh_leaf_node(PBVH *bvh, PBVHNode *node) GHash *map; int i, j, totface; - map = BLI_ghash_int_new("build_mesh_leaf_node gh"); - node->uniq_verts = node->face_verts = 0; totface = node->totprim; + /* reserve size is rough guess */ + map = BLI_ghash_int_new_ex("build_mesh_leaf_node gh", 2 * totface); + node->face_vert_indices = MEM_callocN(sizeof(int) * 4 * totface, "bvh node face vert indices"); diff --git a/source/blender/blenkernel/intern/pbvh_bmesh.c b/source/blender/blenkernel/intern/pbvh_bmesh.c index 5aae6276a79..455ffd90ada 100644 --- a/source/blender/blenkernel/intern/pbvh_bmesh.c +++ b/source/blender/blenkernel/intern/pbvh_bmesh.c @@ -140,8 +140,8 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index) c2 = &bvh->nodes[children + 1]; c1->flag |= PBVH_Leaf; c2->flag |= PBVH_Leaf; - c1->bm_faces = BLI_ghash_ptr_new("bm_faces"); - c2->bm_faces = BLI_ghash_ptr_new("bm_faces"); + c1->bm_faces = BLI_ghash_ptr_new_ex("bm_faces", BLI_ghash_size(n->bm_faces) / 2); + c2->bm_faces = BLI_ghash_ptr_new_ex("bm_faces", BLI_ghash_size(n->bm_faces) / 2); /* Partition the parent node's faces between the two children */ GHASH_ITER (gh_iter, n->bm_faces) { @@ -227,19 +227,26 @@ static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index) static int pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index) { GHash *prim_bbc; + GHash *bm_faces; + int bm_faces_size; GHashIterator gh_iter; + BBC *bbc_array; + unsigned int i; - if (BLI_ghash_size(bvh->nodes[node_index].bm_faces) <= bvh->leaf_limit) { + bm_faces = bvh->nodes[node_index].bm_faces; + bm_faces_size = BLI_ghash_size(bm_faces); + if (bm_faces_size <= bvh->leaf_limit) { /* Node limit not exceeded */ return FALSE; } /* For each BMFace, store the AABB and AABB centroid */ - prim_bbc = BLI_ghash_ptr_new("prim_bbc"); + prim_bbc = BLI_ghash_ptr_new_ex("prim_bbc", bm_faces_size); + bbc_array = MEM_callocN(sizeof(BBC) * bm_faces_size, "BBC"); - GHASH_ITER (gh_iter, bvh->nodes[node_index].bm_faces) { + GHASH_ITER_INDEX (gh_iter, bm_faces, i) { BMFace *f = BLI_ghashIterator_getKey(&gh_iter); - BBC *bbc = MEM_callocN(sizeof(BBC), "BBC"); + BBC *bbc = &bbc_array[i]; BMLoop *l_iter; BMLoop *l_first; @@ -255,7 +262,8 @@ static int pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index) pbvh_bmesh_node_split(bvh, prim_bbc, node_index); - BLI_ghash_free(prim_bbc, NULL, MEM_freeN); + BLI_ghash_free(prim_bbc, NULL, NULL); + MEM_freeN(bbc_array); return TRUE; } @@ -1071,7 +1079,7 @@ void BKE_pbvh_build_bmesh(PBVH *bvh, BMesh *bm, int smooth_shading, n = bvh->nodes = MEM_callocN(sizeof(PBVHNode), "PBVHNode"); bvh->totnode = 1; n->flag = PBVH_Leaf; - n->bm_faces = BLI_ghash_ptr_new("bm_faces"); + n->bm_faces = BLI_ghash_ptr_new_ex("bm_faces", bvh->bm->totface); BM_ITER_MESH (f, &iter, bvh->bm, BM_FACES_OF_MESH) { BLI_ghash_insert(n->bm_faces, f, NULL); } diff --git a/source/blender/blenkernel/intern/treehash.c b/source/blender/blenkernel/intern/treehash.c index 19a9ede31ea..3258bb47fc1 100644 --- a/source/blender/blenkernel/intern/treehash.c +++ b/source/blender/blenkernel/intern/treehash.c @@ -102,7 +102,7 @@ static void fill_treehash(void *treehash, BLI_mempool *treestore) void *BKE_treehash_create_from_treestore(BLI_mempool *treestore) { - GHash *treehash = BLI_ghash_new(tse_hash, tse_cmp, "treehash"); + GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_count(treestore)); fill_treehash(treehash, treestore); return treehash; } diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c index 09fdb0c73f6..30728636a58 100644 --- a/source/blender/bmesh/intern/bmesh_log.c +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -407,7 +407,7 @@ static int uint_compare(const void *a_v, const void *b_v) */ static GHash *bm_log_compress_ids_to_indices(unsigned int *ids, int totid) { - GHash *map = BLI_ghash_int_new(AT); + GHash *map = BLI_ghash_int_new_ex(AT, totid); int i; qsort(ids, totid, sizeof(*ids), uint_compare); @@ -441,8 +441,8 @@ BMLog *BM_log_create(BMesh *bm) BMLog *log = MEM_callocN(sizeof(*log), AT); log->unused_ids = range_tree_uint_alloc(0, (unsigned)-1); - log->id_to_elem = BLI_ghash_ptr_new(AT); - log->elem_to_id = BLI_ghash_ptr_new(AT); + log->id_to_elem = BLI_ghash_ptr_new_ex(AT, bm->totvert + bm->totface); + log->elem_to_id = BLI_ghash_ptr_new_ex(AT, bm->totvert + bm->totface); /* Assign IDs to all existing vertices and faces */ bm_log_assign_ids(bm, log); diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index 64368390444..5ab6fe72f77 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -674,7 +674,7 @@ void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx) int *new_idx = NULL; /* Init the old-to-new vert pointers mapping */ - vptr_map = BLI_ghash_ptr_new("BM_mesh_remap vert pointers mapping"); + vptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap vert pointers mapping", bm->totvert); /* Make a copy of all vertices. */ verts_pool = MEM_callocN(sizeof(BMVert *) * totvert, "BM_mesh_remap verts pool"); @@ -708,7 +708,7 @@ void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx) int *new_idx = NULL; /* Init the old-to-new vert pointers mapping */ - eptr_map = BLI_ghash_ptr_new("BM_mesh_remap edge pointers mapping"); + eptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap edge pointers mapping", bm->totedge); /* Make a copy of all vertices. */ edges_pool = MEM_callocN(sizeof(BMEdge *) * totedge, "BM_mesh_remap edges pool"); @@ -741,7 +741,7 @@ void BM_mesh_remap(BMesh *bm, int *vert_idx, int *edge_idx, int *face_idx) int *new_idx = NULL; /* Init the old-to-new vert pointers mapping */ - fptr_map = BLI_ghash_ptr_new("BM_mesh_remap face pointers mapping"); + fptr_map = BLI_ghash_ptr_new_ex("BM_mesh_remap face pointers mapping", bm->totface); /* Make a copy of all vertices. */ faces_pool = MEM_callocN(sizeof(BMFace *) * totface, "BM_mesh_remap faces pool"); diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c index b71d5a7e7d4..0483fa20dec 100644 --- a/source/blender/bmesh/intern/bmesh_operators.c +++ b/source/blender/bmesh/intern/bmesh_operators.c @@ -341,7 +341,7 @@ void _bmo_slot_copy(BMOpSlot slot_args_src[BMO_OP_MAX_SLOTS], const char *slot_n } if (!slot_dst->data.ghash) { - slot_dst->data.ghash = BLI_ghash_ptr_new("bmesh operator 2"); + slot_dst->data.ghash = BLI_ghash_ptr_new_ex("bmesh operator 2", BLI_ghash_size(slot_src->data.ghash)); } for (BLI_ghashIterator_init(&it, slot_src->data.ghash); diff --git a/source/blender/bmesh/intern/bmesh_walkers.c b/source/blender/bmesh/intern/bmesh_walkers.c index 80b85ab6edd..c9e36541db7 100644 --- a/source/blender/bmesh/intern/bmesh_walkers.c +++ b/source/blender/bmesh/intern/bmesh_walkers.c @@ -87,8 +87,8 @@ void BMW_init(BMWalker *walker, BMesh *bm, int type, walker->mask_edge = mask_edge; walker->mask_face = mask_face; - walker->visithash = BLI_ghash_ptr_new("bmesh walkers 1"); - walker->secvisithash = BLI_ghash_ptr_new("bmesh walkers sec 1"); + walker->visithash = BLI_ghash_ptr_new("bmesh walkers"); + walker->secvisithash = BLI_ghash_ptr_new("bmesh walkers sec"); if (UNLIKELY(type >= BMW_MAXWALKERS || type < 0)) { fprintf(stderr, @@ -253,8 +253,6 @@ void BMW_reset(BMWalker *walker) BMW_state_remove(walker); } walker->depth = 0; - BLI_ghash_free(walker->visithash, NULL, NULL); - BLI_ghash_free(walker->secvisithash, NULL, NULL); - walker->visithash = BLI_ghash_ptr_new("bmesh walkers 1"); - walker->secvisithash = BLI_ghash_ptr_new("bmesh walkers sec 1"); + BLI_ghash_clear(walker->visithash, NULL, NULL); + BLI_ghash_clear(walker->secvisithash, NULL, NULL); } diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index 2baa78856f4..2fbda777dcc 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -494,8 +494,7 @@ static void bmw_LoopWalker_begin(BMWalker *walker, void *data) lwalk->lastv = lwalk->startv = BM_edge_other_vert(owalk.cur, lwalk->lastv); - BLI_ghash_free(walker->visithash, NULL, NULL); - walker->visithash = BLI_ghash_ptr_new("bmesh walkers 2"); + BLI_ghash_clear(walker->visithash, NULL, NULL); BLI_ghash_insert(walker->visithash, owalk.cur, NULL); } @@ -751,12 +750,10 @@ static void bmw_FaceLoopWalker_begin(BMWalker *walker, void *data) *lwalk = owalk; lwalk->no_calc = false; - BLI_ghash_free(walker->secvisithash, NULL, NULL); - walker->secvisithash = BLI_ghash_ptr_new("bmesh walkers 3"); + BLI_ghash_clear(walker->secvisithash, NULL, NULL); BLI_ghash_insert(walker->secvisithash, lwalk->l->e, NULL); - BLI_ghash_free(walker->visithash, NULL, NULL); - walker->visithash = BLI_ghash_ptr_new("bmesh walkers 3"); + BLI_ghash_clear(walker->visithash, NULL, NULL); BLI_ghash_insert(walker->visithash, lwalk->l->f, NULL); } @@ -806,8 +803,9 @@ static void *bmw_FaceLoopWalker_step(BMWalker *walker) lwalk->no_calc = false; } - BLI_ghash_insert(walker->secvisithash, l->e, NULL); - BLI_ghash_insert(walker->visithash, l->f, NULL); + /* both may already exist */ + BLI_ghash_reinsert(walker->secvisithash, l->e, NULL, NULL, NULL); + BLI_ghash_reinsert(walker->visithash, l->f, NULL, NULL, NULL); } return f; @@ -858,8 +856,7 @@ static void bmw_EdgeringWalker_begin(BMWalker *walker, void *data) lwalk->l = lwalk->l->radial_next; } - BLI_ghash_free(walker->visithash, NULL, NULL); - walker->visithash = BLI_ghash_ptr_new("bmesh walkers 4"); + BLI_ghash_clear(walker->visithash, NULL, NULL); BLI_ghash_insert(walker->visithash, lwalk->l->e, NULL); } diff --git a/source/blender/editors/curve/editcurve.c b/source/blender/editors/curve/editcurve.c index 660f8098a38..01559a007ef 100644 --- a/source/blender/editors/curve/editcurve.c +++ b/source/blender/editors/curve/editcurve.c @@ -674,7 +674,7 @@ static GHash *dupli_keyIndexHash(GHash *keyindex) GHash *gh; GHashIterator *hashIter; - gh = BLI_ghash_ptr_new("dupli_keyIndex gh"); + gh = BLI_ghash_ptr_new_ex("dupli_keyIndex gh", BLI_ghash_size(keyindex)); for (hashIter = BLI_ghashIterator_new(keyindex); BLI_ghashIterator_done(hashIter) == false; diff --git a/source/blender/editors/mesh/meshtools.c b/source/blender/editors/mesh/meshtools.c index 4ae48b99bb8..ce1cacdfb3a 100644 --- a/source/blender/editors/mesh/meshtools.c +++ b/source/blender/editors/mesh/meshtools.c @@ -1135,7 +1135,7 @@ int *mesh_get_x_mirror_faces(Object *ob, BMEditMesh *em) mesh_octree_table(ob, em, NULL, 'e'); - fhash = BLI_ghash_new(mirror_facehash, mirror_facecmp, "mirror_facehash gh"); + fhash = BLI_ghash_new_ex(mirror_facehash, mirror_facecmp, "mirror_facehash gh", me->totface); for (a = 0, mf = mface; a < me->totface; a++, mf++) BLI_ghash_insert(fhash, mf, mf); diff --git a/source/blender/makesdna/intern/dna_genfile.c b/source/blender/makesdna/intern/dna_genfile.c index 1225821102a..ed7f6f5d765 100644 --- a/source/blender/makesdna/intern/dna_genfile.c +++ b/source/blender/makesdna/intern/dna_genfile.c @@ -530,7 +530,7 @@ static void init_structDNA(SDNA *sdna, bool do_endian_swap) #ifdef WITH_DNA_GHASH /* create a ghash lookup to speed up */ - sdna->structs_map = BLI_ghash_str_new("init_structDNA gh"); + sdna->structs_map = BLI_ghash_str_new_ex("init_structDNA gh", sdna->nr_structs); for (nr = 0; nr < sdna->nr_structs; nr++) { sp = sdna->structs[nr]; diff --git a/source/blender/windowmanager/intern/wm.c b/source/blender/windowmanager/intern/wm.c index 89c0cde2e88..a109c2cbd7b 100644 --- a/source/blender/windowmanager/intern/wm.c +++ b/source/blender/windowmanager/intern/wm.c @@ -226,7 +226,7 @@ void WM_uilisttype_freelink(uiListType *ult) /* called on initialize WM_init() */ void WM_uilisttype_init(void) { - uilisttypes_hash = BLI_ghash_str_new("uilisttypes_hash gh"); + uilisttypes_hash = BLI_ghash_str_new_ex("uilisttypes_hash gh", 16); } void WM_uilisttype_free(void) @@ -279,7 +279,8 @@ void WM_menutype_freelink(MenuType *mt) /* called on initialize WM_init() */ void WM_menutype_init(void) { - menutypes_hash = BLI_ghash_str_new("menutypes_hash gh"); + /* reserve size is set based on blender default setup */ + menutypes_hash = BLI_ghash_str_new_ex("menutypes_hash gh", 512); } void WM_menutype_free(void) diff --git a/source/blender/windowmanager/intern/wm_operators.c b/source/blender/windowmanager/intern/wm_operators.c index 7af69670cd4..a68d6daa96f 100644 --- a/source/blender/windowmanager/intern/wm_operators.c +++ b/source/blender/windowmanager/intern/wm_operators.c @@ -4142,7 +4142,8 @@ void wm_operatortype_free(void) /* called on initialize WM_init() */ void wm_operatortype_init(void) { - global_ops_hash = BLI_ghash_str_new("wm_operatortype_init gh"); + /* reserve size is set based on blender default setup */ + global_ops_hash = BLI_ghash_str_new_ex("wm_operatortype_init gh", 2048); WM_operatortype_append(WM_OT_window_duplicate); WM_operatortype_append(WM_OT_read_history); -- cgit v1.2.3