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 ++++++++++++++++++++--- source/blender/blenlib/BLI_math_inline.h | 2 +- source/blender/blenlib/intern/BLI_ghash.c | 144 ++++---------------- source/blender/blenlib/intern/math_base_inline.c | 2 +- source/blender/blenlib/intern/threads.c | 18 +++ 5 files changed, 193 insertions(+), 137 deletions(-) (limited to 'source/blender/blenlib') 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 diff --git a/source/blender/blenlib/BLI_math_inline.h b/source/blender/blenlib/BLI_math_inline.h index d742af26ac0..f8220681bb7 100644 --- a/source/blender/blenlib/BLI_math_inline.h +++ b/source/blender/blenlib/BLI_math_inline.h @@ -37,7 +37,7 @@ extern "C" { #ifdef BLI_MATH_INLINE #ifdef _MSC_VER -#define MINLINE static __inline +#define MINLINE static __forceinline #else #define MINLINE static inline #endif diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c index 80cd507520c..214975ab4ef 100644 --- a/source/blender/blenlib/intern/BLI_ghash.c +++ b/source/blender/blenlib/intern/BLI_ghash.c @@ -33,17 +33,20 @@ #include "MEM_guardedalloc.h" #include "BLI_ghash.h" +#include "BLI_mempool.h" #include "BLO_sys_types.h" // for intptr_t support +#include "BKE_utildefines.h" + #ifdef HAVE_CONFIG_H #include #endif /***/ -static unsigned int hashsizes[]= { - 1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, +unsigned int hashsizes[]= { + 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459 @@ -51,124 +54,27 @@ static unsigned int hashsizes[]= { /***/ -typedef struct Entry Entry; -struct Entry { - Entry *next; - - void *key, *val; -}; - -struct GHash { - GHashHashFP hashfp; - GHashCmpFP cmpfp; - - Entry **buckets; - int nbuckets, nentries, cursize; -}; - /***/ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp) { GHash *gh= MEM_mallocN(sizeof(*gh), "GHash"); gh->hashfp= hashfp; gh->cmpfp= cmpfp; - + gh->entrypool = BLI_mempool_create(sizeof(Entry), 1024, 1024, 0); + gh->cursize= 0; gh->nentries= 0; gh->nbuckets= hashsizes[gh->cursize]; - gh->buckets= malloc(gh->nbuckets*sizeof(*gh->buckets)); + gh->buckets= MEM_mallocN(gh->nbuckets*sizeof(*gh->buckets), "buckets"); memset(gh->buckets, 0, gh->nbuckets*sizeof(*gh->buckets)); return gh; } -void BLI_ghash_insert(GHash *gh, void *key, void *val) { - unsigned int hash= gh->hashfp(key)%gh->nbuckets; - Entry *e= malloc(sizeof(*e)); - - e->key= key; - e->val= val; - 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; inext; - - hash= gh->hashfp(e->key)%gh->nbuckets; - e->next= gh->buckets[hash]; - gh->buckets[hash]= e; - - e= n; - } - } - - free(old); - } -} - -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; -} - -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); - free(e); - - - e= n; - if (p) - p->next = n; - else - gh->buckets[hash] = n; - - --gh->nentries; - return 1; - } - p = e; - } - - return 0; -} - -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; -} +#ifdef BLI_ghash_insert +#undef BLI_ghash_insert +#endif int BLI_ghash_size(GHash *gh) { return gh->nentries; @@ -177,21 +83,23 @@ int BLI_ghash_size(GHash *gh) { void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp) { int i; - for (i=0; inbuckets; i++) { - Entry *e; - - for (e= gh->buckets[i]; e; ) { - Entry *n= e->next; - - if (keyfreefp) keyfreefp(e->key); - if (valfreefp) valfreefp(e->val); - free(e); + if (keyfreefp || valfreefp) { + for (i=0; inbuckets; i++) { + Entry *e; - e= n; + for (e= gh->buckets[i]; e; ) { + Entry *n= e->next; + + if (keyfreefp) keyfreefp(e->key); + if (valfreefp) valfreefp(e->val); + + e= n; + } } } - free(gh->buckets); + MEM_freeN(gh->buckets); + BLI_mempool_destroy(gh->entrypool); gh->buckets = 0; gh->nentries = 0; gh->nbuckets = 0; @@ -201,7 +109,7 @@ void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreef /***/ GHashIterator *BLI_ghashIterator_new(GHash *gh) { - GHashIterator *ghi= malloc(sizeof(*ghi)); + GHashIterator *ghi= MEM_mallocN(sizeof(*ghi), "ghash iterator"); ghi->gh= gh; ghi->curEntry= NULL; ghi->curBucket= -1; @@ -225,7 +133,7 @@ void BLI_ghashIterator_init(GHashIterator *ghi, GHash *gh) { } } void BLI_ghashIterator_free(GHashIterator *ghi) { - free(ghi); + MEM_freeN(ghi); } void *BLI_ghashIterator_getKey(GHashIterator *ghi) { diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c index 71a0d2cc654..e228e25c4d6 100644 --- a/source/blender/blenlib/intern/math_base_inline.c +++ b/source/blender/blenlib/intern/math_base_inline.c @@ -110,7 +110,7 @@ MINLINE float shell_angle_to_dist(const float angle) /* used for zoom values*/ MINLINE float power_of_2(float val) { - return (float)pow(2, ceil(log(val) / log(2))); + return (float)pow(2.0, ceil(log((double)val) / log(2.0))); } MINLINE float minf(float a, float b) diff --git a/source/blender/blenlib/intern/threads.c b/source/blender/blenlib/intern/threads.c index 9df746276bd..ad89a61a2a7 100644 --- a/source/blender/blenlib/intern/threads.c +++ b/source/blender/blenlib/intern/threads.c @@ -524,6 +524,7 @@ void *BLI_thread_queue_pop(ThreadQueue *queue) static void wait_timeout(struct timespec *timeout, int ms) { +#ifndef WIN32 struct timeval now; ldiv_t div_result; long x; @@ -539,6 +540,23 @@ static void wait_timeout(struct timespec *timeout, int ms) } timeout->tv_nsec = x*1000; +#else + time_t now; + ldiv_t div_result; + long x; + + time(&now); + div_result = ldiv(ms, 1000); + timeout->tv_sec = now + div_result.quot; + x = (now*1000) + (div_result.rem*1000); + + if (x >= 1000000) { + timeout->tv_sec++; + x -= 1000000; + } + + timeout->tv_nsec = x*1000; +#endif } void *BLI_thread_queue_pop_timeout(ThreadQueue *queue, int ms) -- cgit v1.2.3