Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |  

This web mail archive is frozen.

This page is part of a frozen web archive of this mailing list.

You can still navigate around this archive, but know that no new mails have been added to it since July of 2016.

Click here to be taken to the new web archives of this list; it includes all the mails that are in this frozen archive plus all new mails that have been sent to the list since it was migrated to the new archives.

Subject: [OMPI devel] RFC: improve the hash function used by opal_hash_table_t
From: Nathan Hjelm (hjelmn_at_[hidden])
Date: 2013-06-11 17:32:44


What: Implement a better hash function in opal_hash_table_t. The function is a simple one-at-a-time Jenkin's hash (see http://en.wikipedia.org/wiki/Jenkins_hash_function) and has good collision rates and isn't overly complex or slow.

Why: I am preparing an update to the MCA variable system (adding performance variables) which will include a hash-based lookup function (in preperation for the inevitable MPI_T_cvar/pvar/category lookup functions-- MPI 3.0 errata). The current hash function is not very good so now seems like a good time to update it.

When: Will push this to trunk on Thursday if there are no objections.

Patch below

Index: opal/class/opal_hash_table.c
===================================================================
--- opal/class/opal_hash_table.c (revision 28609)
+++ opal/class/opal_hash_table.c (working copy)
@@ -356,14 +356,20 @@
 static inline uint32_t opal_hash_value(size_t mask, const void *key,
                                        size_t keysize)
 {
- size_t h, i;
- const unsigned char *p;
-
- h = 0;
- p = (const unsigned char *)key;
- for (i = 0; i < keysize; i++, p++)
- h = HASH_MULTIPLIER*h + *p;
- return (uint32_t)(h & mask);
+ const unsigned char *p = (const unsigned char *) key;
+ uint32_t h = 0, i;
+
+ for (i = 0 ; i < keysize ; ++i, ++p) {
+ h += *p;
+ h += h << 10;
+ h ^= h >> 6;
+ }
+
+ h += h << 3;
+ h ^= h >> 11;
+ h += h << 15;
+
+ return h & (uint32_t) mask;
 }
 
 int opal_hash_table_get_value_ptr(opal_hash_table_t* ht, const void* key,

-Nathan