Hi all, The hash table (_xhash_ in jabberd2) solves the collision by using a bucket(unidirectional list), and just sets the key and value to null when zaping a element.
I guess the designment is to get a static element container, but what about if there are a great amount users registered while just a few of them are active? Meanwhile, the empty elements list will come to a bottleneck while getting an element not exists in the hash table. I've modify the _xhash_ in two options: 1 change the hash table bucket-list to bidirectional 2 add a free list for reusing the zapped elements. for these, the elements in _zen_ can be null but the bucket list just contains valuable elements. two patches are attached, while the second one is to print the stat of xhash, just for debug the initial size( _sm->users_/ _sm->sessions_ for example). Hope more explanation or discussion from here. Thanks. Eric
From 5ac310db2b0e95f636c62e232f3d019320453aac Mon Sep 17 00:00:00 2001 From: Eric Liang <[email protected]> Date: Mon, 8 Jun 2009 18:04:25 +0800 Subject: [PATCH] change the xhash list to bidirectional while adding free_list(unidirectional) to xhash for reusing the memory. --- util/xhash.c | 92 +++++++++++++++++++++++++++++++++++++-------------------- util/xhash.h | 2 + 2 files changed, 62 insertions(+), 32 deletions(-) diff --git a/util/xhash.c b/util/xhash.c index 7c3927f..55f401c 100644 --- a/util/xhash.c +++ b/util/xhash.c @@ -54,15 +54,26 @@ static xhn _xhash_node_new(xht h, int index) /* track total */ h->count++; - /* get existing empty one */ - for(n = &h->zen[i]; n != NULL; n = n->next) - if(n->key == NULL) - return n; + // if the zen[i] is empty, reuse it, else get a new one. + n = &h->zen[i]; + + if( n->key != NULL ) + { + if( h->free_list ) + { + n = h->free_list; + h->free_list = h->free_list->next; + }else + n = pmalloco(h->p, sizeof(_xhn)); + + //add it to the bucket list head. + n->prev = &h->zen[i]; + n->next = h->zen[i].next; + + if( n->next ) n->next->prev = n; + h->zen[i].next = n; + } - /* overflowing, new one! */ - n = pmalloco(h->p, sizeof(_xhn)); - n->next = h->zen[i].next; - h->zen[i].next = n; return n; } @@ -91,6 +102,8 @@ xht xhash_new(int prime) xnew->p = p; xnew->zen = pmalloco(p, sizeof(_xhn)*prime); /* array of xhn size of prime */ + xnew->free_list = NULL; + xnew->iter_bucket = -1; xnew->iter_node = NULL; @@ -156,27 +169,49 @@ void *xhash_get(xht h, const char *key) return xhash_getx(h,key,strlen(key)); } - -void xhash_zapx(xht h, const char *key, int len) +void xhash_zap_inner( xht h, xhn n, int index) { - xhn n; - - if(h == NULL || key == NULL || (n = _xhash_node_get(h, key, len, _xhasher(key,len))) == NULL) - return; + int i = index % h->prime; + + /* if we just killed the current iter, move to the next one */ + if(h->iter_node == n) + xhash_iter_next(h); + + // if element:n is in bucket list. + if( &h->zen[i] != n ) + { + n->prev->next = n->next; + n->next->prev = n->prev; -/* log_debug(ZONE,"zapping %s",key); */ + // add it to the free_list head. + n->prev = NULL; + n->next = h->free_list; + h->free_list = n; + } - /* kill an entry by zeroing out the key */ + //empty the value. n->key = NULL; n->val = NULL; /* dirty the xht and track the total */ h->dirty++; h->count--; +} - /* if we just killed the current iter, move to the next one */ - if(h->iter_node == n) - xhash_iter_next(h); +void xhash_zapx(xht h, const char *key, int len) +{ + xhn n; + int index; + + if( !h || !key ) return; + + index = _xhasher(key,len); + n = _xhash_node_get(h, key, len, index); + if( !n ) return; + +/* log_debug(ZONE,"zapping %s",key); */ + + xhash_zap_inner(h ,n, index ); } void xhash_zap(xht h, const char *key) @@ -275,22 +310,15 @@ int xhash_iter_next(xht h) { return 0; } -void xhash_iter_zap(xht h) { - if(h == NULL) return; - - if(h->iter_node == NULL) - return; +void xhash_iter_zap(xht h) +{ + int index; - /* pow */ - h->iter_node->key = NULL; - h->iter_node->val = NULL; + if( !h || !h->iter_node ) return; - /* dirty the xht and track the total */ - h->dirty++; - h->count--; + index = _xhasher( h->iter_node->key, strlen( h->iter_node->key ) ); - /* next one */ - xhash_iter_next(h); + xhash_zap_inner( h ,h->iter_node, index); } int xhash_iter_get(xht h, const char **key, void **val) { diff --git a/util/xhash.h b/util/xhash.h index 4b47483..46e8683 100644 --- a/util/xhash.h +++ b/util/xhash.h @@ -36,6 +36,7 @@ typedef struct xhn_struct { struct xhn_struct *next; + struct xhn_struct *prev; const char *key; void *val; } *xhn, _xhn; @@ -47,6 +48,7 @@ typedef struct xht_struct int dirty; int count; struct xhn_struct *zen; + struct xhn_struct *free_list; // list of zaped elements to be reused. int iter_bucket; xhn iter_node; } *xht, _xht; -- 1.6.0.4
From b4fc9562d8f475ae1dadf843f742986b37bc5805 Mon Sep 17 00:00:00 2001 From: Eric Liang <[email protected]> Date: Mon, 8 Jun 2009 18:15:13 +0800 Subject: [PATCH] add debug flag: XHASH_DEBUG and the state method for xhash: xhash_stat. --- util/xhash.c | 43 +++++++++++++++++++++++++++++++++++++++++-- util/xhash.h | 2 ++ 2 files changed, 43 insertions(+), 2 deletions(-) diff --git a/util/xhash.c b/util/xhash.c index 55f401c..e8e4a86 100644 --- a/util/xhash.c +++ b/util/xhash.c @@ -54,6 +54,10 @@ static xhn _xhash_node_new(xht h, int index) /* track total */ h->count++; +#ifdef XHASH_DEBUG + h->stat[i]++; +#endif + // if the zen[i] is empty, reuse it, else get a new one. n = &h->zen[i]; @@ -107,6 +111,13 @@ xht xhash_new(int prime) xnew->iter_bucket = -1; xnew->iter_node = NULL; +#ifdef XHASH_DEBUG + xnew->stat = malloc( sizeof(int)*prime ); + memset( xnew->stat, 0 , sizeof(int)*prime ); +#else + xnew->stat = NULL; +#endif + return xnew; } @@ -196,6 +207,10 @@ void xhash_zap_inner( xht h, xhn n, int index) /* dirty the xht and track the total */ h->dirty++; h->count--; + +#ifdef XHASH_DEBUG + h->stat[i]--; +#endif } void xhash_zapx(xht h, const char *key, int len) @@ -224,8 +239,32 @@ void xhash_free(xht h) { /* log_debug(ZONE,"hash free %X",h); */ - if(h != NULL) - pool_free(h->p); + if( !h ) return; + +#ifdef XHASH_DEBUG + free( h->stat ); +#endif + + pool_free(h->p); + +} + +void xhash_stat( xht h ) +{ +#ifdef XHASH_DEBUG + if( !h ) return; + + fprintf(stderr, "XHASH: table prime: %d , number of elements: %d\n", h->prime, h->count ); + + int i; + for( i = 0; i< h->prime ; ++i ) + { + if( h->stat[i] > 1 ) + fprintf(stderr, "%d: %d\t", i, h->stat[i]); + } + fprintf(stderr, "\n"); + +#endif } void xhash_walk(xht h, xhash_walker w, void *arg) diff --git a/util/xhash.h b/util/xhash.h index 46e8683..4878479 100644 --- a/util/xhash.h +++ b/util/xhash.h @@ -51,6 +51,7 @@ typedef struct xht_struct struct xhn_struct *free_list; // list of zaped elements to be reused. int iter_bucket; xhn iter_node; + int *stat; } *xht, _xht; typedef void (*xhash_walker_t)(xht h, const char *key, void *val, void *arg); @@ -62,6 +63,7 @@ JABBERD2_API void *xhash_get(xht h, const char *key); JABBERD2_API void *xhash_getx(xht h, const char *key, int len); JABBERD2_API void xhash_zap(xht h, const char *key); JABBERD2_API void xhash_zapx(xht h, const char *key, int len); +JABBERD2_API void xhash_stat(xht h); JABBERD2_API void xhash_free(xht h); typedef void (*xhash_walker)(xht h, const char *key, void *val, void *arg); JABBERD2_API void xhash_walk(xht h, xhash_walker w, void *arg); -- 1.6.0.4
signature.asc
Description: OpenPGP digital signature
