Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Development mailing list

Subject: Re: [OMPI devel] RFC: improve the hash function used byopal_hash_table_t
From: Alex A. Granovsky (gran_at_[hidden])
Date: 2013-06-11 17:54:56


Hello,

one of the best hash functions I know is crc32. It is not very expensive,
especially with modern CPUs where it is implemented as the CPU instruction.

Hope this helps.

Kind regards,
Alex Granovsky

-----Original Message-----
From: Nathan Hjelm
Sent: Wednesday, June 12, 2013 1:32 AM
To: Open MPI Developers
Subject: [OMPI devel] RFC: improve the hash function used
byopal_hash_table_t

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
_______________________________________________
devel mailing list
devel_at_[hidden]
http://www.open-mpi.org/mailman/listinfo.cgi/devel