cedric pushed a commit to branch master.
http://git.enlightenment.org/core/efl.git/commit/?id=295babadb1675d1160b18c639dd6dcbe20b02cfb
commit 295babadb1675d1160b18c639dd6dcbe20b02cfb
Author: Cedric Bail <cedric.b...@samsung.com>
Date: Thu Sep 26 14:51:54 2013 +0900
eina: check if the complete hash match before checking if the key match
during children walk.
This give an interesting +15% for all Eina_Hash user whatever hash function
they use. The inlined
djb2 is still the fastest one and all other give very close result.
This idea was given by Lucas De Marchi's blog :
http://www.politreco.com/2013/09/optimizing-hash-table-with-kmod-as-testbed/
I do believe that rolling a crc32 implementation as a hash function should
give interesting result
in our test.
---
src/lib/eina/eina_hash.c | 31 ++++++++++++++++++++++---------
1 file changed, 22 insertions(+), 9 deletions(-)
diff --git a/src/lib/eina/eina_hash.c b/src/lib/eina/eina_hash.c
index ffe7497..eec34f9 100644
--- a/src/lib/eina/eina_hash.c
+++ b/src/lib/eina/eina_hash.c
@@ -102,6 +102,7 @@ struct _Eina_Hash_Element
{
EINA_RBTREE;
Eina_Hash_Tuple tuple;
+ int hash;
};
struct _Eina_Hash_Foreach_Data
@@ -172,18 +173,21 @@ _eina_hash_hash_rbtree_cmp_node(const Eina_Hash_Head
*left,
static inline int
_eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_Element *hash_element,
- const Eina_Hash_Tuple *tuple,
+ const Eina_Hash_Element *tuple,
EINA_UNUSED unsigned int key_length,
Eina_Key_Cmp cmp)
{
int result;
- result = cmp(hash_element->tuple.key,
- hash_element->tuple.key_length,
- tuple->key,
- tuple->key_length);
+ result = hash_element->hash - tuple->hash;
+ if (!result)
+ result = cmp(hash_element->tuple.key,
+ hash_element->tuple.key_length,
+ tuple->tuple.key,
+ tuple->tuple.key_length);
- if (result == 0 && tuple->data && tuple->data != hash_element->tuple.data)
+ if (result == 0 && tuple->tuple.data &&
+ tuple->tuple.data != hash_element->tuple.data)
return 1;
return result;
@@ -196,8 +200,10 @@ _eina_hash_key_rbtree_cmp_node(const Eina_Hash_Element
*left,
{
int result;
- result = cmp(left->tuple.key, left->tuple.key_length,
- right->tuple.key, right->tuple.key_length);
+ result = left->hash - right->hash;
+ if (result == 0)
+ result = cmp(left->tuple.key, left->tuple.key_length,
+ right->tuple.key, right->tuple.key_length);
if (result < 0)
return EINA_RBTREE_LEFT;
@@ -214,6 +220,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
Eina_Hash_Element *new_hash_element = NULL;
Eina_Hash_Head *hash_head;
Eina_Error error = 0;
+ int original_key;
int hash_num;
EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
@@ -224,6 +231,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
error = EINA_ERROR_OUT_OF_MEMORY;
/* Apply eina mask to hash. */
+ original_key = key_hash;
hash_num = key_hash & hash->mask;
key_hash &= EINA_HASH_RBTREE_MASK;
@@ -272,6 +280,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
/* Setup the element */
new_hash_element->tuple.key_length = key_length;
new_hash_element->tuple.data = (void *)data;
+ new_hash_element->hash = original_key;
if (alloc_length > 0)
{
new_hash_element->tuple.key = (char *)(new_hash_element + 1);
@@ -326,8 +335,10 @@ _eina_hash_find_by_hash(const Eina_Hash *hash,
Eina_Hash_Head **hash_head)
{
Eina_Hash_Element *hash_element;
+ Eina_Hash_Element tmp;
int rb_hash = key_hash & EINA_HASH_RBTREE_MASK;
+ tmp.hash = key_hash;
key_hash &= hash->mask;
if (!hash->buckets)
@@ -342,9 +353,11 @@ _eina_hash_find_by_hash(const Eina_Hash *hash,
if (!*hash_head)
return NULL;
+ tmp.tuple = *tuple;
+
hash_element = (Eina_Hash_Element *)
eina_rbtree_inline_lookup((*hash_head)->head,
- tuple, 0,
+ &tmp, 0,
EINA_RBTREE_CMP_KEY_CB(
_eina_hash_key_rbtree_cmp_key_data),
(const void *)hash->key_cmp_cb);
--
