From 08968cb5fc9edcec75729a0180259cb2fd3aca30 Mon Sep 17 00:00:00 2001 From: Brian Aker Date: Sun, 25 Nov 2007 14:01:18 -0800 Subject: [PATCH] Added MEMCACHED_HASH_HSIEH. --- ChangeLog | 2 ++ THANKS | 1 + include/memcached.h | 1 + lib/Makefile.am | 1 + lib/common.h | 1 + lib/hsieh_hash.c | 65 +++++++++++++++++++++++++++++++++++++++++++ lib/memcached_hash.c | 5 ++++ lib/memcached_stats.c | 14 +++++----- tests/function.c | 10 +++++++ 9 files changed, 93 insertions(+), 7 deletions(-) create mode 100644 lib/hsieh_hash.c diff --git a/ChangeLog b/ChangeLog index 14b627de..338adce1 100644 --- a/ChangeLog +++ b/ChangeLog @@ -6,6 +6,8 @@ did not need to be enabled to be enabled (performance issue). * Rewrote bounds checking code for get calls. * "make test" now starts its own memcached servers. + * Added Hseih hash (MEMCACHED_HASH_HSIEH), which is showing about 7% + performance over standard hash. 0.10 Tue Nov 20 23:22:31 PST 2007 * Added append binary test. diff --git a/THANKS b/THANKS index 1aea2bf0..d5ee9764 100644 --- a/THANKS +++ b/THANKS @@ -3,3 +3,4 @@ Cal Heldenbrand - Awesome feedback on performance Dustin Sallings - Insight into protocol Tobias Luetke - Performance Feedback Andre Cruz - Help with getting the CRC Hash function to match other connectors +Brian Pontz - Hsieh hash diff --git a/include/memcached.h b/include/memcached.h index bf50f456..4e60cca0 100644 --- a/include/memcached.h +++ b/include/memcached.h @@ -87,6 +87,7 @@ typedef enum { MEMCACHED_HASH_FNV1_32, MEMCACHED_HASH_FNV1A_32, MEMCACHED_HASH_KETAMA, + MEMCACHED_HASH_HSIEH, } memcached_hash; typedef enum { diff --git a/lib/Makefile.am b/lib/Makefile.am index 8a96e41e..62673bc9 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -26,6 +26,7 @@ noinst_HEADERS = libmemcached_probes.h \ lib_LTLIBRARIES = libmemcached.la libmemcached_la_SOURCES = crc.c \ + hsieh_hash.c \ memcached.c \ memcached_auto.c \ memcached_behavior.c \ diff --git a/lib/common.h b/lib/common.h index 73913c1c..d4a7baca 100644 --- a/lib/common.h +++ b/lib/common.h @@ -51,6 +51,7 @@ typedef enum { void md5_signature(unsigned char *key, unsigned int length, unsigned char *result); uint32_t hash_crc32(const char *data, size_t data_len); +uint32_t hsieh_hash(char *key, size_t key_length); memcached_return memcached_connect(memcached_st *ptr, unsigned int server_key); memcached_return memcached_response(memcached_st *ptr, diff --git a/lib/hsieh_hash.c b/lib/hsieh_hash.c new file mode 100644 index 00000000..9f42a94d --- /dev/null +++ b/lib/hsieh_hash.c @@ -0,0 +1,65 @@ +/* By Paul Hsieh (C) 2004, 2005. Covered under the Paul Hsieh + * derivative license. + * See: http://www.azillionmonkeys.com/qed/weblicense.html for license + * details. + * http://www.azillionmonkeys.com/qed/hash.html +*/ + +#include "common.h" + +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif + +uint32_t hsieh_hash(char *key, size_t key_length) +{ + uint32_t hash = 0, tmp; + int rem; + + if (key_length <= 0 || key == NULL) return 0; + + rem = key_length & 3; + key_length >>= 2; + + /* Main loop */ + for (;key_length > 0; key_length--) { + hash += get16bits (key); + tmp = (get16bits (key+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + key += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits (key); + hash ^= hash << 16; + hash ^= key[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (key); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *key; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + diff --git a/lib/memcached_hash.c b/lib/memcached_hash.c index 32e82e76..9cc846a8 100644 --- a/lib/memcached_hash.c +++ b/lib/memcached_hash.c @@ -77,6 +77,11 @@ unsigned int memcached_generate_hash(memcached_st *ptr, char *key, size_t key_le hash= internal_generate_ketama_md5(key, key_length); break; } + case MEMCACHED_HASH_HSIEH: + { + hash= hsieh_hash(key, key_length); + break; + } } WATCHPOINT_ASSERT(hash); diff --git a/lib/memcached_stats.c b/lib/memcached_stats.c index aea66875..04ef31ba 100644 --- a/lib/memcached_stats.c +++ b/lib/memcached_stats.c @@ -93,27 +93,27 @@ static void set_data(memcached_stat_st *stat, char *key, char *value) } else if (!memcmp("connection_structures", key, strlen("connection_structures"))) { - //stat->connection_structures= strtol(value, (char **)NULL, 10); + stat->connection_structures= strtol(value, (char **)NULL, 10); } else if (!memcmp("cmd_get", key, strlen("cmd_get"))) { - //stat->cmd_get= strtoll(value, (char **)NULL, 10); + stat->cmd_get= strtoll(value, (char **)NULL, 10); } else if (!memcmp("cmd_set", key, strlen("cmd_set"))) { - //stat->cmd_set= strtoll(value, (char **)NULL, 10); + stat->cmd_set= strtoll(value, (char **)NULL, 10); } else if (!memcmp("get_hits", key, strlen("get_hits"))) { - //stat->get_hits= strtoll(value, (char **)NULL, 10); + stat->get_hits= strtoll(value, (char **)NULL, 10); } else if (!memcmp("get_misses", key, strlen("get_misses"))) { - //stat->get_misses= (uint64_t)strtoll(value, (char **)NULL, 10); + stat->get_misses= (uint64_t)strtoll(value, (char **)NULL, 10); } else if (!memcmp("evictions", key, strlen("evictions"))) { - //stat->evictions= (uint64_t)strtoll(value, (char **)NULL, 10); + stat->evictions= (uint64_t)strtoll(value, (char **)NULL, 10); } else if (!memcmp("bytes_read", key, strlen("bytes_read"))) { @@ -125,7 +125,7 @@ static void set_data(memcached_stat_st *stat, char *key, char *value) } else if (!memcmp("limit_maxbytes", key, strlen("limit_maxbytes"))) { - //stat->limit_maxbytes= strtol(value, (char **)NULL, 10); + stat->limit_maxbytes= strtol(value, (char **)NULL, 10); } else if (!memcmp("threads", key, strlen("threads"))) { diff --git a/tests/function.c b/tests/function.c index 4ab8fc26..b5af2b50 100644 --- a/tests/function.c +++ b/tests/function.c @@ -1576,6 +1576,14 @@ memcached_return pre_crc(memcached_st *memc) return MEMCACHED_SUCCESS; } +memcached_return pre_hsieh(memcached_st *memc) +{ + memcached_hash value= MEMCACHED_HASH_HSIEH; + memcached_behavior_set(memc, MEMCACHED_BEHAVIOR_HASH, &value); + + return MEMCACHED_SUCCESS; +} + memcached_return pre_hash_fnv1_64(memcached_st *memc) { memcached_hash value= MEMCACHED_HASH_FNV1_64; @@ -1786,6 +1794,7 @@ collection_st collection[] ={ {"nodelay", pre_nodelay, 0, tests}, {"md5", pre_md5, 0, tests}, {"crc", pre_crc, 0, tests}, + {"hsieh", pre_hsieh, 0, tests}, {"fnv1_64", pre_hash_fnv1_64, 0, tests}, {"fnv1a_64", pre_hash_fnv1a_64, 0, tests}, {"fnv1_32", pre_hash_fnv1_32, 0, tests}, @@ -1801,6 +1810,7 @@ collection_st collection[] ={ {"result", 0, 0, result_tests}, {"user", 0, 0, user_tests}, {"generate", 0, 0, generate_tests}, + {"generate_hsieh", pre_hsieh, 0, generate_tests}, {"generate_nonblock", pre_nonblock, 0, generate_tests}, {0, 0, 0, 0} }; -- 2.30.2