From 217dcce072c268a9f404c3dcda89aa55c1a7423f Mon Sep 17 00:00:00 2001 From: Steven Grimm Date: Sun, 26 Nov 2006 21:33:47 +0000 Subject: Incorporate changes from "performance" branch (revisions 414-419). git-svn-id: http://code.sixapart.com/svn/memcached/trunk/server@450 b0b603af-a30f-0410-a34e-baf09ae79d0b --- assoc.c | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 130 insertions(+), 31 deletions(-) (limited to 'assoc.c') diff --git a/assoc.c b/assoc.c index 06cc40e..4f7a8ac 100644 --- a/assoc.c +++ b/assoc.c @@ -31,15 +31,6 @@ #include "memcached.h" -typedef unsigned long int ub4; /* unsigned 4-byte quantities */ -typedef unsigned char ub1; /* unsigned 1-byte quantities */ - -/* hard-code one million buckets, for now (2**20 == 4MB hash) */ -#define HASHPOWER 20 - -#define hashsize(n) ((ub4)1<<(n)) -#define hashmask(n) (hashsize(n)-1) - /* * Since the hash function does bit manipulation, it needs to know * whether it's big or little-endian. ENDIAN_LITTLE and ENDIAN_BIG @@ -459,25 +450,64 @@ uint32_t hash( const void *key, size_t length, uint32_t initval) #error Must define HASH_BIG_ENDIAN or HASH_LITTLE_ENDIAN #endif // hash_XXX_ENDIAN == 1 -static item** hashtable = 0; +typedef unsigned long int ub4; /* unsigned 4-byte quantities */ +typedef unsigned char ub1; /* unsigned 1-byte quantities */ + +/* how many powers of 2's worth of buckets we use */ +int hashpower = 16; + +#define hashsize(n) ((ub4)1<<(n)) +#define hashmask(n) (hashsize(n)-1) + +/* Main hash table. This is where we look except during expansion. */ +static item** primary_hashtable = 0; + +/* + * Previous hash table. During expansion, we look here for keys that haven't + * been moved over to the primary yet. + */ +static item** old_hashtable = 0; + +/* Number of items in the hash table. */ +static int hash_items = 0; + +/* Flag: Are we in the middle of expanding now? */ +static int expanding = 0; + +/* + * During expansion we migrate values with bucket granularity; this is how + * far we've gotten so far. Ranges from 0 .. hashsize(hashpower - 1) - 1. + */ +static int expand_bucket = 0; void assoc_init(void) { - unsigned int hash_size = hashsize(HASHPOWER) * sizeof(void*); - hashtable = malloc(hash_size); - if (! hashtable) { + unsigned int hash_size = hashsize(hashpower) * sizeof(void*); + primary_hashtable = malloc(hash_size); + if (! primary_hashtable) { fprintf(stderr, "Failed to init hashtable.\n"); exit(1); } - memset(hashtable, 0, hash_size); + memset(primary_hashtable, 0, hash_size); } -item *assoc_find(char *key) { - ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); - item *it = hashtable[hv]; +item *assoc_find(const char *key, size_t nkey) { + uint32_t hv = hash(key, nkey, 0); + item *it; + int oldbucket; + + if (expanding && + (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) + { + it = old_hashtable[oldbucket]; + } else { + it = primary_hashtable[hv & hashmask(hashpower)]; + } while (it) { - if (strcmp(key, ITEM_key(it)) == 0) + if ((nkey == it->nkey) && + (memcmp(key, ITEM_key(it), nkey) == 0)) { return it; + } it = it->h_next; } return 0; @@ -486,35 +516,104 @@ item *assoc_find(char *key) { /* returns the address of the item pointer before the key. if *item == 0, the item wasn't found */ -static item** _hashitem_before (char *key) { - ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); - item **pos = &hashtable[hv]; +static item** _hashitem_before (const char *key, size_t nkey) { + uint32_t hv = hash(key, nkey, 0); + item **pos; + int oldbucket; - while (*pos && strcmp(key, ITEM_key(*pos))) { + if (expanding && + (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) + { + pos = &old_hashtable[oldbucket]; + } else { + pos = &primary_hashtable[hv & hashmask(hashpower)]; + } + + while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) { pos = &(*pos)->h_next; } return pos; } +/* grows the hashtable to the next power of 2. */ +static void assoc_expand(void) { + old_hashtable = primary_hashtable; + + primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *)); + if (primary_hashtable) { + if (settings.verbose > 1) + fprintf(stderr, "Hash table expansion starting\n"); + hashpower++; + expanding = 1; + expand_bucket = 0; + assoc_move_next_bucket(); + } else { + primary_hashtable = old_hashtable; + /* Bad news, but we can keep running. */ + } +} + +/* migrates the next bucket to the primary hashtable if we're expanding. */ +void assoc_move_next_bucket(void) { + item *it, *next; + int bucket; + + if (expanding) { + for (it = old_hashtable[expand_bucket]; NULL != it; it = next) { + next = it->h_next; + + bucket = hash(ITEM_key(it), it->nkey, 0) & hashmask(hashpower); + it->h_next = primary_hashtable[bucket]; + primary_hashtable[bucket] = it; + } + + expand_bucket++; + if (expand_bucket == hashsize(hashpower - 1)) { + expanding = 0; + free(old_hashtable); + if (settings.verbose > 1) + fprintf(stderr, "Hash table expansion done\n"); + } + } +} + /* Note: this isn't an assoc_update. The key must not already exist to call this */ -int assoc_insert(char *key, item *it) { - ub4 hv; - assert(assoc_find(key) == 0); /* shouldn't have duplicately named things defined */ - hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); - it->h_next = hashtable[hv]; - hashtable[hv] = it; +int assoc_insert(item *it) { + uint32_t hv; + int oldbucket; + + assert(assoc_find(ITEM_key(it), it->nkey) == 0); /* shouldn't have duplicately named things defined */ + + hv = hash(ITEM_key(it), it->nkey, 0); + if (expanding && + (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket) + { + it->h_next = old_hashtable[oldbucket]; + old_hashtable[oldbucket] = it; + } else { + it->h_next = primary_hashtable[hv & hashmask(hashpower)]; + primary_hashtable[hv & hashmask(hashpower)] = it; + } + + hash_items++; + if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) { + assoc_expand(); + } + return 1; } -void assoc_delete(char *key) { - item **before = _hashitem_before(key); +void assoc_delete(const char *key, size_t nkey) { + item **before = _hashitem_before(key, nkey); + if (*before) { item *nxt = (*before)->h_next; (*before)->h_next = 0; /* probably pointless, but whatever. */ *before = nxt; + hash_items--; return; } - /* Note: we never actually get here. the callers don't delete things + /* Note: we never actually get here. the callers don't delete things they can't find. */ assert(*before != 0); } -- cgit v1.2.1