diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/tests/eina_bench_hash.c | 545 |
1 files changed, 545 insertions, 0 deletions
diff --git a/libraries/eina/src/tests/eina_bench_hash.c b/libraries/eina/src/tests/eina_bench_hash.c new file mode 100644 index 0000000..5b42318 --- /dev/null +++ b/libraries/eina/src/tests/eina_bench_hash.c | |||
@@ -0,0 +1,545 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2008 Cedric Bail | ||
3 | * | ||
4 | * This library is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU Lesser General Public | ||
6 | * License as published by the Free Software Foundation; either | ||
7 | * version 2.1 of the License, or (at your option) any later version. | ||
8 | * | ||
9 | * This library is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | * Lesser General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU Lesser General Public | ||
15 | * License along with this library; | ||
16 | * if not, see <http://www.gnu.org/licenses/>. | ||
17 | */ | ||
18 | |||
19 | #ifdef HAVE_CONFIG_H | ||
20 | # include "config.h" | ||
21 | #endif | ||
22 | |||
23 | #include <stdlib.h> | ||
24 | #include <stdio.h> | ||
25 | #include <string.h> | ||
26 | #include <time.h> | ||
27 | |||
28 | #ifdef EINA_BENCH_HAVE_GLIB | ||
29 | # include <glib.h> | ||
30 | #endif | ||
31 | |||
32 | #include "Evas_Data.h" | ||
33 | #include "Ecore_Data.h" | ||
34 | |||
35 | #include "eina_hash.h" | ||
36 | #include "eina_array.h" | ||
37 | #include "eina_bench.h" | ||
38 | #include "eina_rbtree.h" | ||
39 | #include "eina_convert.h" | ||
40 | |||
41 | #ifdef CITYHASH_BENCH | ||
42 | // Hash function for a byte array. | ||
43 | uint64_t CityHash64(const char *buf, size_t len); | ||
44 | |||
45 | static unsigned int | ||
46 | _eina_string_key_length(const char *key) | ||
47 | { | ||
48 | if (!key) | ||
49 | return 0; | ||
50 | |||
51 | return (int)strlen(key) + 1; | ||
52 | } | ||
53 | |||
54 | static int | ||
55 | _eina_string_key_cmp(const char *key1, __UNUSED__ int key1_length, | ||
56 | const char *key2, __UNUSED__ int key2_length) | ||
57 | { | ||
58 | return strcmp(key1, key2); | ||
59 | } | ||
60 | #endif | ||
61 | |||
62 | |||
63 | typedef struct _Eina_Bench_Rbtree Eina_Bench_Rbtree; | ||
64 | struct _Eina_Bench_Rbtree | ||
65 | { | ||
66 | Eina_Rbtree node; | ||
67 | char key[10]; | ||
68 | int value; | ||
69 | }; | ||
70 | |||
71 | static Eina_Rbtree_Direction | ||
72 | _eina_bench_rbtree_cmp(const Eina_Bench_Rbtree *left, | ||
73 | const Eina_Bench_Rbtree *right, | ||
74 | __UNUSED__ void *data) | ||
75 | { | ||
76 | if (!left) | ||
77 | return EINA_RBTREE_RIGHT; | ||
78 | |||
79 | if (!right) | ||
80 | return EINA_RBTREE_LEFT; | ||
81 | |||
82 | return strcmp(left->key, | ||
83 | right->key) < 0 ? EINA_RBTREE_LEFT : EINA_RBTREE_RIGHT; | ||
84 | } | ||
85 | |||
86 | static inline int | ||
87 | _eina_bench_rbtree_key(const Eina_Bench_Rbtree *node, | ||
88 | const char *key, | ||
89 | int length, | ||
90 | __UNUSED__ void *data) | ||
91 | { | ||
92 | return strncmp(node->key, key, length); | ||
93 | } | ||
94 | |||
95 | static void | ||
96 | _eina_bench_rbtree_free(Eina_Rbtree *node, __UNUSED__ void *data) | ||
97 | { | ||
98 | free(node); | ||
99 | } | ||
100 | |||
101 | static void | ||
102 | eina_bench_lookup_rbtree(int request) | ||
103 | { | ||
104 | Eina_Rbtree *root = NULL; | ||
105 | int i; | ||
106 | int j; | ||
107 | |||
108 | for (i = 0; i < request; ++i) | ||
109 | { | ||
110 | Eina_Bench_Rbtree *tmp; | ||
111 | |||
112 | tmp = malloc(sizeof (Eina_Bench_Rbtree)); | ||
113 | if (!tmp) | ||
114 | continue; | ||
115 | |||
116 | tmp->value = i; | ||
117 | eina_convert_itoa(i, tmp->key); | ||
118 | |||
119 | root = eina_rbtree_inline_insert(root, | ||
120 | &tmp->node, | ||
121 | EINA_RBTREE_CMP_NODE_CB( | ||
122 | _eina_bench_rbtree_cmp), | ||
123 | NULL); | ||
124 | } | ||
125 | |||
126 | srand(time(NULL)); | ||
127 | |||
128 | for (j = 0; j < 200; ++j) | ||
129 | for (i = 0; i < request; ++i) | ||
130 | { | ||
131 | Eina_Rbtree *tmp; | ||
132 | char tmp_key[10]; | ||
133 | |||
134 | eina_convert_itoa(rand() % request, tmp_key); | ||
135 | |||
136 | tmp = eina_rbtree_inline_lookup(root, | ||
137 | tmp_key, | ||
138 | 10, | ||
139 | EINA_RBTREE_CMP_KEY_CB( | ||
140 | _eina_bench_rbtree_key), | ||
141 | NULL); | ||
142 | } | ||
143 | |||
144 | eina_rbtree_delete(root, EINA_RBTREE_FREE_CB(_eina_bench_rbtree_free), NULL); | ||
145 | } | ||
146 | |||
147 | static void | ||
148 | eina_bench_lookup_murmur(int request) | ||
149 | { | ||
150 | Eina_Hash *hash = NULL; | ||
151 | int *tmp_val; | ||
152 | unsigned int i; | ||
153 | unsigned int j; | ||
154 | |||
155 | hash = eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length), | ||
156 | EINA_KEY_CMP(_eina_string_key_cmp), | ||
157 | EINA_KEY_HASH(eina_hash_murmur3), | ||
158 | free, | ||
159 | 8); | ||
160 | |||
161 | for (i = 0; i < (unsigned int)request; ++i) | ||
162 | { | ||
163 | char tmp_key[10]; | ||
164 | |||
165 | tmp_val = malloc(sizeof (int)); | ||
166 | |||
167 | if (!tmp_val) | ||
168 | continue; | ||
169 | |||
170 | eina_convert_itoa(i, tmp_key); | ||
171 | *tmp_val = i; | ||
172 | |||
173 | eina_hash_add(hash, tmp_key, tmp_val); | ||
174 | } | ||
175 | |||
176 | srand(time(NULL)); | ||
177 | |||
178 | for (j = 0; j < 200; ++j) | ||
179 | for (i = 0; i < (unsigned int)request; ++i) | ||
180 | { | ||
181 | char tmp_key[10]; | ||
182 | |||
183 | eina_convert_itoa(rand() % request, tmp_key); | ||
184 | tmp_val = eina_hash_find(hash, tmp_key); | ||
185 | } | ||
186 | |||
187 | eina_hash_free(hash); | ||
188 | } | ||
189 | |||
190 | #ifdef CITYHASH_BENCH | ||
191 | static void | ||
192 | eina_bench_lookup_cityhash(int request) | ||
193 | { | ||
194 | Eina_Hash *hash = NULL; | ||
195 | int *tmp_val; | ||
196 | unsigned int i; | ||
197 | unsigned int j; | ||
198 | |||
199 | hash = eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length), | ||
200 | EINA_KEY_CMP(_eina_string_key_cmp), | ||
201 | EINA_KEY_HASH(CityHash64), | ||
202 | free, | ||
203 | 8); | ||
204 | |||
205 | for (i = 0; i < (unsigned int)request; ++i) | ||
206 | { | ||
207 | char tmp_key[10]; | ||
208 | |||
209 | tmp_val = malloc(sizeof (int)); | ||
210 | |||
211 | if (!tmp_val) | ||
212 | continue; | ||
213 | |||
214 | eina_convert_itoa(i, tmp_key); | ||
215 | *tmp_val = i; | ||
216 | |||
217 | eina_hash_add(hash, tmp_key, tmp_val); | ||
218 | } | ||
219 | |||
220 | srand(time(NULL)); | ||
221 | |||
222 | for (j = 0; j < 200; ++j) | ||
223 | for (i = 0; i < (unsigned int)request; ++i) | ||
224 | { | ||
225 | char tmp_key[10]; | ||
226 | |||
227 | eina_convert_itoa(rand() % request, tmp_key); | ||
228 | tmp_val = eina_hash_find(hash, tmp_key); | ||
229 | } | ||
230 | |||
231 | eina_hash_free(hash); | ||
232 | } | ||
233 | #endif | ||
234 | |||
235 | static void | ||
236 | eina_bench_lookup_superfast(int request) | ||
237 | { | ||
238 | Eina_Hash *hash = NULL; | ||
239 | int *tmp_val; | ||
240 | unsigned int i; | ||
241 | unsigned int j; | ||
242 | |||
243 | hash = eina_hash_string_superfast_new(free); | ||
244 | |||
245 | for (i = 0; i < (unsigned int)request; ++i) | ||
246 | { | ||
247 | char tmp_key[10]; | ||
248 | |||
249 | tmp_val = malloc(sizeof (int)); | ||
250 | |||
251 | if (!tmp_val) | ||
252 | continue; | ||
253 | |||
254 | eina_convert_itoa(i, tmp_key); | ||
255 | *tmp_val = i; | ||
256 | |||
257 | eina_hash_add(hash, tmp_key, tmp_val); | ||
258 | } | ||
259 | |||
260 | srand(time(NULL)); | ||
261 | |||
262 | for (j = 0; j < 200; ++j) | ||
263 | for (i = 0; i < (unsigned int)request; ++i) | ||
264 | { | ||
265 | char tmp_key[10]; | ||
266 | |||
267 | eina_convert_itoa(rand() % request, tmp_key); | ||
268 | tmp_val = eina_hash_find(hash, tmp_key); | ||
269 | } | ||
270 | |||
271 | eina_hash_free(hash); | ||
272 | } | ||
273 | |||
274 | static void | ||
275 | eina_bench_lookup_djb2(int request) | ||
276 | { | ||
277 | Eina_Hash *hash = NULL; | ||
278 | int *tmp_val; | ||
279 | unsigned int i; | ||
280 | unsigned int j; | ||
281 | |||
282 | hash = eina_hash_string_djb2_new(free); | ||
283 | |||
284 | for (i = 0; i < (unsigned int)request; ++i) | ||
285 | { | ||
286 | char tmp_key[10]; | ||
287 | |||
288 | tmp_val = malloc(sizeof (int)); | ||
289 | |||
290 | if (!tmp_val) | ||
291 | continue; | ||
292 | |||
293 | eina_convert_itoa(i, tmp_key); | ||
294 | *tmp_val = i; | ||
295 | |||
296 | eina_hash_add(hash, tmp_key, tmp_val); | ||
297 | } | ||
298 | |||
299 | srand(time(NULL)); | ||
300 | |||
301 | for (j = 0; j < 200; ++j) | ||
302 | for (i = 0; i < (unsigned int)request; ++i) | ||
303 | { | ||
304 | char tmp_key[10]; | ||
305 | |||
306 | eina_convert_itoa(rand() % request, tmp_key); | ||
307 | |||
308 | tmp_val = eina_hash_find(hash, tmp_key); | ||
309 | } | ||
310 | |||
311 | eina_hash_free(hash); | ||
312 | } | ||
313 | |||
314 | typedef struct _Eina_Bench_DJB2 Eina_Bench_DJB2; | ||
315 | struct _Eina_Bench_DJB2 | ||
316 | { | ||
317 | char *key; | ||
318 | int value; | ||
319 | }; | ||
320 | |||
321 | static void | ||
322 | eina_bench_lookup_djb2_inline(int request) | ||
323 | { | ||
324 | Eina_Hash *hash = NULL; | ||
325 | Eina_Bench_DJB2 *elm; | ||
326 | unsigned int i; | ||
327 | unsigned int j; | ||
328 | |||
329 | hash = eina_hash_string_djb2_new(free); | ||
330 | |||
331 | for (i = 0; i < (unsigned int)request; ++i) | ||
332 | { | ||
333 | int length; | ||
334 | |||
335 | elm = malloc(sizeof (Eina_Bench_DJB2) + 10); | ||
336 | if (!elm) | ||
337 | continue; | ||
338 | |||
339 | elm->key = (char *)(elm + 1); | ||
340 | |||
341 | length = eina_convert_itoa(i, elm->key) + 1; | ||
342 | elm->value = i; | ||
343 | |||
344 | eina_hash_direct_add_by_hash(hash, elm->key, length, | ||
345 | eina_hash_djb2(elm->key, length), elm); | ||
346 | } | ||
347 | |||
348 | srand(time(NULL)); | ||
349 | |||
350 | for (j = 0; j < 200; ++j) | ||
351 | for (i = 0; i < (unsigned int)request; ++i) | ||
352 | { | ||
353 | char tmp_key[10]; | ||
354 | int length = 6; | ||
355 | |||
356 | length = eina_convert_itoa(rand() % request, tmp_key) + 1; | ||
357 | |||
358 | elm = | ||
359 | eina_hash_find_by_hash(hash, tmp_key, length, | ||
360 | eina_hash_djb2(tmp_key, length)); | ||
361 | } | ||
362 | |||
363 | eina_hash_free(hash); | ||
364 | } | ||
365 | |||
366 | #ifdef EINA_BENCH_HAVE_GLIB | ||
367 | typedef struct _Eina_Bench_Glib Eina_Bench_Glib; | ||
368 | struct _Eina_Bench_Glib | ||
369 | { | ||
370 | char *key; | ||
371 | int value; | ||
372 | }; | ||
373 | |||
374 | static void | ||
375 | eina_bench_lookup_ghash(int request) | ||
376 | { | ||
377 | Eina_Bench_Glib *elm; | ||
378 | GHashTable *hash; | ||
379 | unsigned int i; | ||
380 | unsigned int j; | ||
381 | |||
382 | hash = g_hash_table_new_full(g_str_hash, g_str_equal, NULL, free); | ||
383 | |||
384 | for (i = 0; i < (unsigned int)request; ++i) | ||
385 | { | ||
386 | elm = malloc(sizeof (Eina_Bench_Glib) + 10); | ||
387 | if (!elm) | ||
388 | continue; | ||
389 | |||
390 | elm->key = (char *)(elm + 1); | ||
391 | |||
392 | eina_convert_itoa(i, elm->key); | ||
393 | elm->value = i; | ||
394 | |||
395 | g_hash_table_insert(hash, elm->key, elm); | ||
396 | } | ||
397 | |||
398 | srand(time(NULL)); | ||
399 | |||
400 | for (j = 0; j < 200; ++j) | ||
401 | for (i = 0; i < (unsigned int)request; ++i) | ||
402 | { | ||
403 | char tmp_key[10]; | ||
404 | |||
405 | eina_convert_itoa(rand() % request, tmp_key); | ||
406 | |||
407 | elm = g_hash_table_lookup(hash, tmp_key); | ||
408 | } | ||
409 | |||
410 | g_hash_table_destroy(hash); | ||
411 | } | ||
412 | #endif | ||
413 | |||
414 | static void | ||
415 | eina_bench_lookup_evas(int request) | ||
416 | { | ||
417 | Evas_Hash *hash = NULL; | ||
418 | Eina_Array *array = NULL; | ||
419 | int *tmp_val; | ||
420 | Eina_Array_Iterator it; | ||
421 | unsigned int i; | ||
422 | unsigned int j; | ||
423 | |||
424 | array = eina_array_new(10000); | ||
425 | |||
426 | for (i = 0; i < (unsigned int)request; ++i) | ||
427 | { | ||
428 | char tmp_key[10]; | ||
429 | |||
430 | tmp_val = malloc(sizeof (int)); | ||
431 | |||
432 | if (!tmp_val) | ||
433 | continue; | ||
434 | |||
435 | eina_convert_itoa(i, tmp_key); | ||
436 | *tmp_val = i; | ||
437 | |||
438 | hash = evas_hash_add(hash, tmp_key, tmp_val); | ||
439 | |||
440 | eina_array_push(array, tmp_val); | ||
441 | } | ||
442 | |||
443 | srand(time(NULL)); | ||
444 | |||
445 | for (j = 0; j < 200; ++j) | ||
446 | for (i = 0; i < (unsigned int)request; ++i) | ||
447 | { | ||
448 | char tmp_key[10]; | ||
449 | |||
450 | eina_convert_itoa(rand() % request, tmp_key); | ||
451 | |||
452 | tmp_val = evas_hash_find(hash, tmp_key); | ||
453 | } | ||
454 | |||
455 | evas_hash_free(hash); | ||
456 | |||
457 | EINA_ARRAY_ITER_NEXT(array, i, tmp_val, it) | ||
458 | free(tmp_val); | ||
459 | |||
460 | eina_array_free(array); | ||
461 | } | ||
462 | |||
463 | typedef struct _Eina_Bench_Ecore Eina_Bench_Ecore; | ||
464 | struct _Eina_Bench_Ecore | ||
465 | { | ||
466 | char *key; | ||
467 | int value; | ||
468 | }; | ||
469 | |||
470 | static void | ||
471 | eina_bench_lookup_ecore(int request) | ||
472 | { | ||
473 | Ecore_Hash *hash = NULL; | ||
474 | Eina_Bench_Ecore *elm; | ||
475 | unsigned int i; | ||
476 | unsigned int j; | ||
477 | |||
478 | hash = ecore_hash_new(ecore_str_hash, ecore_str_compare); | ||
479 | |||
480 | ecore_hash_free_key_cb_set(hash, NULL); | ||
481 | ecore_hash_free_value_cb_set(hash, free); | ||
482 | |||
483 | for (i = 0; i < (unsigned int)request; ++i) | ||
484 | { | ||
485 | elm = malloc(sizeof (Eina_Bench_Ecore) + 10); | ||
486 | if (!elm) | ||
487 | continue; | ||
488 | |||
489 | elm->key = (char *)(elm + 1); | ||
490 | eina_convert_itoa(i, elm->key); | ||
491 | elm->value = i; | ||
492 | |||
493 | ecore_hash_set(hash, elm->key, elm); | ||
494 | } | ||
495 | |||
496 | srand(time(NULL)); | ||
497 | |||
498 | for (j = 0; j < 200; ++j) | ||
499 | for (i = 0; i < (unsigned int)request; ++i) | ||
500 | { | ||
501 | char tmp_key[10]; | ||
502 | |||
503 | eina_convert_itoa(rand() % request, tmp_key); | ||
504 | |||
505 | elm = ecore_hash_get(hash, tmp_key); | ||
506 | } | ||
507 | |||
508 | ecore_hash_destroy(hash); | ||
509 | } | ||
510 | |||
511 | void eina_bench_hash(Eina_Benchmark *bench) | ||
512 | { | ||
513 | eina_benchmark_register(bench, "superfast-lookup", | ||
514 | EINA_BENCHMARK( | ||
515 | eina_bench_lookup_superfast), 10, 10000, 10); | ||
516 | eina_benchmark_register(bench, "djb2-lookup", | ||
517 | EINA_BENCHMARK( | ||
518 | eina_bench_lookup_djb2), 10, 10000, 10); | ||
519 | eina_benchmark_register(bench, "djb2-lookup-inline", | ||
520 | EINA_BENCHMARK( | ||
521 | eina_bench_lookup_djb2_inline), 10, 10000, 10); | ||
522 | eina_benchmark_register(bench, "murmur", | ||
523 | EINA_BENCHMARK( | ||
524 | eina_bench_lookup_murmur), 10, 10000, 10); | ||
525 | #ifdef CITYHASH_BENCH | ||
526 | eina_benchmark_register(bench, "cityhash", | ||
527 | EINA_BENCHMARK( | ||
528 | eina_bench_lookup_cityhash), 10, 10000, 10); | ||
529 | #endif | ||
530 | eina_benchmark_register(bench, "rbtree", | ||
531 | EINA_BENCHMARK( | ||
532 | eina_bench_lookup_rbtree), 10, 10000, 10); | ||
533 | #ifdef EINA_BENCH_HAVE_GLIB | ||
534 | eina_benchmark_register(bench, "ghash-lookup", | ||
535 | EINA_BENCHMARK( | ||
536 | eina_bench_lookup_ghash), 10, 10000, 10); | ||
537 | #endif | ||
538 | eina_benchmark_register(bench, "evas-lookup", | ||
539 | EINA_BENCHMARK( | ||
540 | eina_bench_lookup_evas), 10, 10000, 10); | ||
541 | eina_benchmark_register(bench, "ecore-lookup", | ||
542 | EINA_BENCHMARK( | ||
543 | eina_bench_lookup_ecore), 10, 10000, 10); | ||
544 | |||
545 | } | ||