summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCedric Bail <cedric.bail@samsung.com>2013-09-26 14:51:54 +0900
committerCedric Bail <cedric.bail@samsung.com>2013-09-26 15:51:25 +0900
commit295babadb1675d1160b18c639dd6dcbe20b02cfb (patch)
treeb11683f51eb36b9a5c2e04e8542e56a5a6440b7b
parentd460f2954ad13c83738c164e5b6c18481afd942b (diff)
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.
-rw-r--r--src/lib/eina/eina_hash.c31
1 files changed, 22 insertions, 9 deletions
diff --git a/src/lib/eina/eina_hash.c b/src/lib/eina/eina_hash.c
index ffe74972de..eec34f939f 100644
--- a/src/lib/eina/eina_hash.c
+++ b/src/lib/eina/eina_hash.c
@@ -102,6 +102,7 @@ struct _Eina_Hash_Element
102{ 102{
103 EINA_RBTREE; 103 EINA_RBTREE;
104 Eina_Hash_Tuple tuple; 104 Eina_Hash_Tuple tuple;
105 int hash;
105}; 106};
106 107
107struct _Eina_Hash_Foreach_Data 108struct _Eina_Hash_Foreach_Data
@@ -172,18 +173,21 @@ _eina_hash_hash_rbtree_cmp_node(const Eina_Hash_Head *left,
172 173
173static inline int 174static inline int
174_eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_Element *hash_element, 175_eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_Element *hash_element,
175 const Eina_Hash_Tuple *tuple, 176 const Eina_Hash_Element *tuple,
176 EINA_UNUSED unsigned int key_length, 177 EINA_UNUSED unsigned int key_length,
177 Eina_Key_Cmp cmp) 178 Eina_Key_Cmp cmp)
178{ 179{
179 int result; 180 int result;
180 181
181 result = cmp(hash_element->tuple.key, 182 result = hash_element->hash - tuple->hash;
182 hash_element->tuple.key_length, 183 if (!result)
183 tuple->key, 184 result = cmp(hash_element->tuple.key,
184 tuple->key_length); 185 hash_element->tuple.key_length,
186 tuple->tuple.key,
187 tuple->tuple.key_length);
185 188
186 if (result == 0 && tuple->data && tuple->data != hash_element->tuple.data) 189 if (result == 0 && tuple->tuple.data &&
190 tuple->tuple.data != hash_element->tuple.data)
187 return 1; 191 return 1;
188 192
189 return result; 193 return result;
@@ -196,8 +200,10 @@ _eina_hash_key_rbtree_cmp_node(const Eina_Hash_Element *left,
196{ 200{
197 int result; 201 int result;
198 202
199 result = cmp(left->tuple.key, left->tuple.key_length, 203 result = left->hash - right->hash;
200 right->tuple.key, right->tuple.key_length); 204 if (result == 0)
205 result = cmp(left->tuple.key, left->tuple.key_length,
206 right->tuple.key, right->tuple.key_length);
201 207
202 if (result < 0) 208 if (result < 0)
203 return EINA_RBTREE_LEFT; 209 return EINA_RBTREE_LEFT;
@@ -214,6 +220,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
214 Eina_Hash_Element *new_hash_element = NULL; 220 Eina_Hash_Element *new_hash_element = NULL;
215 Eina_Hash_Head *hash_head; 221 Eina_Hash_Head *hash_head;
216 Eina_Error error = 0; 222 Eina_Error error = 0;
223 int original_key;
217 int hash_num; 224 int hash_num;
218 225
219 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); 226 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
@@ -224,6 +231,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
224 error = EINA_ERROR_OUT_OF_MEMORY; 231 error = EINA_ERROR_OUT_OF_MEMORY;
225 232
226 /* Apply eina mask to hash. */ 233 /* Apply eina mask to hash. */
234 original_key = key_hash;
227 hash_num = key_hash & hash->mask; 235 hash_num = key_hash & hash->mask;
228 key_hash &= EINA_HASH_RBTREE_MASK; 236 key_hash &= EINA_HASH_RBTREE_MASK;
229 237
@@ -272,6 +280,7 @@ eina_hash_add_alloc_by_hash(Eina_Hash *hash,
272 /* Setup the element */ 280 /* Setup the element */
273 new_hash_element->tuple.key_length = key_length; 281 new_hash_element->tuple.key_length = key_length;
274 new_hash_element->tuple.data = (void *)data; 282 new_hash_element->tuple.data = (void *)data;
283 new_hash_element->hash = original_key;
275 if (alloc_length > 0) 284 if (alloc_length > 0)
276 { 285 {
277 new_hash_element->tuple.key = (char *)(new_hash_element + 1); 286 new_hash_element->tuple.key = (char *)(new_hash_element + 1);
@@ -326,8 +335,10 @@ _eina_hash_find_by_hash(const Eina_Hash *hash,
326 Eina_Hash_Head **hash_head) 335 Eina_Hash_Head **hash_head)
327{ 336{
328 Eina_Hash_Element *hash_element; 337 Eina_Hash_Element *hash_element;
338 Eina_Hash_Element tmp;
329 int rb_hash = key_hash & EINA_HASH_RBTREE_MASK; 339 int rb_hash = key_hash & EINA_HASH_RBTREE_MASK;
330 340
341 tmp.hash = key_hash;
331 key_hash &= hash->mask; 342 key_hash &= hash->mask;
332 343
333 if (!hash->buckets) 344 if (!hash->buckets)
@@ -342,9 +353,11 @@ _eina_hash_find_by_hash(const Eina_Hash *hash,
342 if (!*hash_head) 353 if (!*hash_head)
343 return NULL; 354 return NULL;
344 355
356 tmp.tuple = *tuple;
357
345 hash_element = (Eina_Hash_Element *) 358 hash_element = (Eina_Hash_Element *)
346 eina_rbtree_inline_lookup((*hash_head)->head, 359 eina_rbtree_inline_lookup((*hash_head)->head,
347 tuple, 0, 360 &tmp, 0,
348 EINA_RBTREE_CMP_KEY_CB( 361 EINA_RBTREE_CMP_KEY_CB(
349 _eina_hash_key_rbtree_cmp_key_data), 362 _eina_hash_key_rbtree_cmp_key_data),
350 (const void *)hash->key_cmp_cb); 363 (const void *)hash->key_cmp_cb);