From 7ef85aa41ff57cbe5395f83d4ea23b651287b78d Mon Sep 17 00:00:00 2001 From: Joseph Eagar Date: Sat, 23 Jan 2010 11:25:20 +0000 Subject: Initial results of my profiling of the animation system. Basically two simple changes, changes, I pulled in the faster ghash in bmesh (which uses mempools for allocation, providing a substanstial speedup in some cases, and also I inlined some of the functions), and I changed __inline to __forceinline for inlining of math functions. I also removed the timer in the view3d zoom op (ctrl-middlemouse) that was making it nonfunctional. Why was that there? --- source/blender/blenlib/BLI_ghash.h | 164 +++++++++++++++++++++++++++++++++---- 1 file changed, 147 insertions(+), 17 deletions(-) (limited to 'source/blender/blenlib/BLI_ghash.h') diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h index c9a8b1b841f..5c1c06b78ac 100644 --- a/source/blender/blenlib/BLI_ghash.h +++ b/source/blender/blenlib/BLI_ghash.h @@ -32,31 +32,49 @@ #ifndef BLI_GHASH_H #define BLI_GHASH_H -#ifdef __cplusplus -extern "C" { -#endif +#include "stdio.h" +#include "stdlib.h" +#include "string.h" -struct GHash; -typedef struct GHash GHash; +#include "BKE_utildefines.h" +#include "MEM_guardedalloc.h" -typedef struct GHashIterator { - GHash *gh; - int curBucket; - struct Entry *curEntry; -} GHashIterator; +#include "BLI_mempool.h" +#include "BLI_blenlib.h" typedef unsigned int (*GHashHashFP) (void *key); typedef int (*GHashCmpFP) (void *a, void *b); typedef void (*GHashKeyFreeFP) (void *key); typedef void (*GHashValFreeFP) (void *val); +typedef struct Entry { + struct Entry *next; + + void *key, *val; +} Entry; + +typedef struct GHash { + GHashHashFP hashfp; + GHashCmpFP cmpfp; + + Entry **buckets; + struct BLI_mempool *entrypool; + int nbuckets, nentries, cursize; +} GHash; + +typedef struct GHashIterator { + GHash *gh; + int curBucket; + struct Entry *curEntry; +} GHashIterator; + GHash* BLI_ghash_new (GHashHashFP hashfp, GHashCmpFP cmpfp); void BLI_ghash_free (GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); -void BLI_ghash_insert (GHash *gh, void *key, void *val); -int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); -void* BLI_ghash_lookup (GHash *gh, void *key); -int BLI_ghash_haskey (GHash *gh, void *key); +//BM_INLINE void BLI_ghash_insert (GHash *gh, void *key, void *val); +//BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp); +//BM_INLINE void* BLI_ghash_lookup (GHash *gh, void *key); +//BM_INLINE int BLI_ghash_haskey (GHash *gh, void *key); int BLI_ghash_size (GHash *gh); @@ -129,9 +147,121 @@ int BLI_ghashutil_strcmp (void *a, void *b); unsigned int BLI_ghashutil_inthash (void *ptr); int BLI_ghashutil_intcmp(void *a, void *b); -#ifdef __cplusplus -} -#endif +/*begin of macro-inlined functions*/ +extern unsigned int hashsizes[]; +#if 0 +#define BLI_ghash_insert(gh, _k, _v){\ + unsigned int _hash= (gh)->hashfp(_k)%gh->nbuckets;\ + Entry *_e= BLI_mempool_alloc((gh)->entrypool);\ + _e->key= _k;\ + _e->val= _v;\ + _e->next= (gh)->buckets[_hash];\ + (gh)->buckets[_hash]= _e;\ + if (++(gh)->nentries>(gh)->nbuckets*3) {\ + Entry *_e, **_old= (gh)->buckets;\ + int _i, _nold= (gh)->nbuckets;\ + (gh)->nbuckets= hashsizes[++(gh)->cursize];\ + (gh)->buckets= malloc((gh)->nbuckets*sizeof(*(gh)->buckets));\ + memset((gh)->buckets, 0, (gh)->nbuckets*sizeof(*(gh)->buckets));\ + for (_i=0; _i<_nold; _i++) {\ + for (_e= _old[_i]; _e;) {\ + Entry *_n= _e->next;\ + _hash= (gh)->hashfp(_e->key)%(gh)->nbuckets;\ + _e->next= (gh)->buckets[_hash];\ + (gh)->buckets[_hash]= _e;\ + _e= _n;\ + }\ + }\ + free(_old); } } #endif +/*---------inlined functions---------*/ +BM_INLINE void BLI_ghash_insert(GHash *gh, void *key, void *val) { + unsigned int hash= gh->hashfp(key)%gh->nbuckets; + Entry *e= (Entry*) BLI_mempool_alloc(gh->entrypool); + + e->key= key; + e->val= val; + e->next= gh->buckets[hash]; + gh->buckets[hash]= e; + + if (++gh->nentries>(float)gh->nbuckets/2) { + Entry *e, **old= gh->buckets; + int i, nold= gh->nbuckets; + + gh->nbuckets= hashsizes[++gh->cursize]; + gh->buckets= (Entry**)MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets"); + memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets)); + + for (i=0; inext; + + hash= gh->hashfp(e->key)%gh->nbuckets; + e->next= gh->buckets[hash]; + gh->buckets[hash]= e; + + e= n; + } + } + + MEM_freeN(old); + } +} + +BM_INLINE void* BLI_ghash_lookup(GHash *gh, void *key) +{ + if(gh) { + unsigned int hash= gh->hashfp(key)%gh->nbuckets; + Entry *e; + + for (e= gh->buckets[hash]; e; e= e->next) + if (gh->cmpfp(key, e->key)==0) + return e->val; + } + return NULL; +} + +BM_INLINE int BLI_ghash_remove (GHash *gh, void *key, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) +{ + unsigned int hash= gh->hashfp(key)%gh->nbuckets; + Entry *e; + Entry *p = 0; + + for (e= gh->buckets[hash]; e; e= e->next) { + if (gh->cmpfp(key, e->key)==0) { + Entry *n= e->next; + + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(e->val); + BLI_mempool_free(gh->entrypool, e); + + + e= n; + if (p) + p->next = n; + else + gh->buckets[hash] = n; + + --gh->nentries; + return 1; + } + p = e; + } + + return 0; +} + +BM_INLINE int BLI_ghash_haskey(GHash *gh, void *key) { + unsigned int hash= gh->hashfp(key)%gh->nbuckets; + Entry *e; + + for (e= gh->buckets[hash]; e; e= e->next) + if (gh->cmpfp(key, e->key)==0) + return 1; + + return 0; +} + +#endif -- cgit v1.2.3