blender
/
blender
136
406
Fork 590
Code Issues 6.2k Pull Requests 763 Projects 19 Wiki Activity

Sculpt-dev: Replace usage of smallhash with ghash 

SmallHash doesn't deal with repeated removals
and insertions very well.
This commit is contained in:
Joseph Eagar 2021-11-13 18:57:39 -08:00
parent c88701178b
commit 2e782109fc
5 changed files with 28 additions and 26 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

6
source/blender/blenkernel/intern/pbvh_bmesh.c
View File

@ -342,9 +342,11 @@ static void pbvh_print_mem_size(PBVH *pbvh)
#ifdef WITH_BM_ID_FREELIST
if (bm->idmap.free_idx_map) {
printf("free_idx_map: nentries %d, size %d\n",
printf("freelist length: %d\n", bm->idmap.freelist_len);
/* printf("free_idx_map: nentries %d, size %d: nfreecells: %d\n",
bm->idmap.free_idx_map->nentries,
bm->idmap.free_idx_map->nbuckets);
bm->idmap.free_idx_map->nbuckets,
bm->idmap.free_idx_map->nfreecells);*/
}
#endif
}

25
source/blender/blenlib/intern/smallhash.c
View File

@ -192,8 +192,8 @@ BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
/* NOTE: there are always more buckets than entries,
* so we know there will always be a free bucket if the key isn't found. */
for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@ -212,8 +212,8 @@ BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uint
uintptr_t h = smallhash_key(key);
uintptr_t hoff = 1;
for (e = &sh->buckets[h % sh->nbuckets]; smallhash_val_is_used(e->val);
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; smallhash_val_is_used(e->val);
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
/* pass */
}
@ -321,8 +321,8 @@ bool BLI_smallhash_ensure_p(SmallHash *sh, uintptr_t key, void ***item)
/* NOTE: there are always more buckets than entries,
* so we know there will always be a free bucket if the key isn't found. */
for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@ -334,7 +334,10 @@ bool BLI_smallhash_ensure_p(SmallHash *sh, uintptr_t key, void ***item)
if (e->val == SMHASH_CELL_FREE || e->val == SMHASH_CELL_UNUSED) {
sh->nentries++;
sh->nfreecells--;
if (e->val == SMHASH_CELL_FREE) {
sh->nfreecells--;
}
ret = false;
e->val = NULL;
@ -408,8 +411,8 @@ bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key)
uintptr_t h = smallhash_key(key);
uintptr_t hoff = 1;
for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e->val != SMHASH_CELL_FREE;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
if (e->key == key) {
/* should never happen because unused keys are zero'd */
BLI_assert(e->val != SMHASH_CELL_UNUSED);
@ -605,8 +608,8 @@ double BLI_smallhash_calc_quality(SmallHash *sh)
uintptr_t h = smallhash_key(e_final->key);
uintptr_t hoff = 1;
for (e = &sh->buckets[h % sh->nbuckets]; e != e_final;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) {
for (e = &sh->buckets[h % (uintptr_t)sh->nbuckets]; e != e_final;
h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % (uintptr_t)sh->nbuckets]) {
count += 1;
}

2
source/blender/bmesh/bmesh_class.h
View File

@ -391,7 +391,7 @@ typedef struct BMesh {
/* maps ids to their position within the freelist
only used if freelist is bigger then a certain size,
see FREELIST_HASHMAP_THRESHOLD_HIGH in bmesh_construct.c.*/
struct SmallHash *free_idx_map;
struct GHash *free_idx_map;
#else
struct RangeTreeUInt *idtree;
#endif

18
source/blender/bmesh/intern/bmesh_construct.c
View File

@ -55,17 +55,15 @@ static void bm_id_freelist_check_hashmap(BMesh *bm)
{
if (!bm->idmap.free_idx_map && bm->idmap.freelist_len >= FREELIST_HASHMAP_THRESHOLD_HIGH) {
printf("switching on freelist idx map\n");
bm->idmap.free_idx_map = MEM_callocN(sizeof(SmallHash), "free_idx_map");
BLI_smallhash_init_ex(bm->idmap.free_idx_map, bm->idmap.freelist_len);
bm->idmap.free_idx_map = BLI_ghash_ptr_new("free_idx_map");
for (int i = 0; i < bm->idmap.freelist_len; i++) {
BLI_smallhash_insert(
bm->idmap.free_idx_map, (uintptr_t)bm->idmap.freelist[i], POINTER_FROM_INT(i));
BLI_ghash_insert(
bm->idmap.free_idx_map, POINTER_FROM_UINT(bm->idmap.freelist[i]), POINTER_FROM_INT(i));
}
}
else if (bm->idmap.free_idx_map && bm->idmap.freelist_len <= FREELIST_HASHMAP_THRESHOLD_LOW) {
BLI_smallhash_release(bm->idmap.free_idx_map);
MEM_freeN(bm->idmap.free_idx_map);
BLI_ghash_free(bm->idmap.free_idx_map, NULL, NULL);
bm->idmap.free_idx_map = NULL;
printf("switching off freelist idx map\n");
@ -81,7 +79,7 @@ static uint bm_id_freelist_pop(BMesh *bm)
uint id = bm->idmap.freelist[i];
if (bm->idmap.free_idx_map) {
BLI_smallhash_remove(bm->idmap.free_idx_map, (uintptr_t) id);
BLI_ghash_remove(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), NULL, NULL);
}
return id;
@ -118,7 +116,7 @@ void bm_id_freelist_take(BMesh *bm, uint id)
BLI_BITMAP_DISABLE(bm->idmap.free_ids, id);
if (bm->idmap.free_idx_map) {
void **val = BLI_smallhash_lookup_p(bm->idmap.free_idx_map, (uintptr_t)id);
void **val = BLI_ghash_lookup_p(bm->idmap.free_idx_map, POINTER_FROM_UINT(id));
if (val) {
int i = POINTER_AS_INT(*val);
@ -128,7 +126,7 @@ void bm_id_freelist_take(BMesh *bm, uint id)
bm->idmap.freelist_len--;
}
BLI_smallhash_remove(bm->idmap.free_idx_map, (uintptr_t)id);
BLI_ghash_remove(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), NULL, NULL);
}
else {
for (int i = 0; i < bm->idmap.freelist_len; i++) {
@ -176,7 +174,7 @@ void bm_id_freelist_push(BMesh *bm, uint id)
if (bm->idmap.free_idx_map) {
void **val;
if (!BLI_smallhash_ensure_p(bm->idmap.free_idx_map, (uintptr_t)id, &val)) {
if (!BLI_ghash_ensure_p(bm->idmap.free_idx_map, POINTER_FROM_UINT(id), &val)) {
*val = POINTER_FROM_INT(bm->idmap.freelist_len - 1);
}
}

3
source/blender/bmesh/intern/bmesh_mesh.c
View File

@ -286,8 +286,7 @@ void BM_mesh_data_free(BMesh *bm)
#ifdef WITH_BM_ID_FREELIST
if (bm->idmap.free_idx_map) {
BLI_smallhash_release(bm->idmap.free_idx_map);
MEM_freeN(bm->idmap.free_idx_map);
BLI_ghash_free(bm->idmap.free_idx_map, NULL, NULL);
bm->idmap.free_idx_map = NULL;
}
#endif