src/tests/eina_bench_hash.c

   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            /* Suppress warnings as we really don't want to do anything. */
 143            (void) tmp;
 144         }
 145
 146    eina_rbtree_delete(root, EINA_RBTREE_FREE_CB(_eina_bench_rbtree_free), NULL);
 147 }
 148
 149 static void
 150 eina_bench_lookup_murmur(int request)
 151 {
 152    Eina_Hash *hash = NULL;
 153    int *tmp_val;
 154    unsigned int i;
 155    unsigned int j;
 156
 157    hash = eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
 158                         EINA_KEY_CMP(_eina_string_key_cmp),
 159                         EINA_KEY_HASH(eina_hash_murmur3),
 160                         free,
 161                         8);
 162
 163    for (i = 0; i < (unsigned int)request; ++i)
 164      {
 165         char tmp_key[10];
 166
 167         tmp_val = malloc(sizeof (int));
 168
 169         if (!tmp_val)
 170            continue;
 171
 172         eina_convert_itoa(i, tmp_key);
 173         *tmp_val = i;
 174
 175         eina_hash_add(hash, tmp_key, tmp_val);
 176      }
 177
 178    srand(time(NULL));
 179
 180    for (j = 0; j < 200; ++j)
 181       for (i = 0; i < (unsigned int)request; ++i)
 182         {
 183            char tmp_key[10];
 184
 185            eina_convert_itoa(rand() % request, tmp_key);
 186            tmp_val = eina_hash_find(hash, tmp_key);
 187         }
 188
 189    eina_hash_free(hash);
 190 }
 191
 192 #ifdef CITYHASH_BENCH
 193 static void
 194 eina_bench_lookup_cityhash(int request)
 195 {
 196    Eina_Hash *hash = NULL;
 197    int *tmp_val;
 198    unsigned int i;
 199    unsigned int j;
 200
 201    hash = eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
 202                         EINA_KEY_CMP(_eina_string_key_cmp),
 203                         EINA_KEY_HASH(CityHash64),
 204                         free,
 205                         8);
 206
 207    for (i = 0; i < (unsigned int)request; ++i)
 208      {
 209         char tmp_key[10];
 210
 211         tmp_val = malloc(sizeof (int));
 212
 213         if (!tmp_val)
 214            continue;
 215
 216         eina_convert_itoa(i, tmp_key);
 217         *tmp_val = i;
 218
 219         eina_hash_add(hash, tmp_key, tmp_val);
 220      }
 221
 222    srand(time(NULL));
 223
 224    for (j = 0; j < 200; ++j)
 225       for (i = 0; i < (unsigned int)request; ++i)
 226         {
 227            char tmp_key[10];
 228
 229            eina_convert_itoa(rand() % request, tmp_key);
 230            tmp_val = eina_hash_find(hash, tmp_key);
 231         }
 232
 233    eina_hash_free(hash);
 234 }
 235 #endif
 236
 237 static void
 238 eina_bench_lookup_superfast(int request)
 239 {
 240    Eina_Hash *hash = NULL;
 241    int *tmp_val;
 242    unsigned int i;
 243    unsigned int j;
 244
 245    hash = eina_hash_string_superfast_new(free);
 246
 247    for (i = 0; i < (unsigned int)request; ++i)
 248      {
 249         char tmp_key[10];
 250
 251         tmp_val = malloc(sizeof (int));
 252
 253         if (!tmp_val)
 254            continue;
 255
 256         eina_convert_itoa(i, tmp_key);
 257         *tmp_val = i;
 258
 259         eina_hash_add(hash, tmp_key, tmp_val);
 260      }
 261
 262    srand(time(NULL));
 263
 264    for (j = 0; j < 200; ++j)
 265       for (i = 0; i < (unsigned int)request; ++i)
 266         {
 267            char tmp_key[10];
 268
 269            eina_convert_itoa(rand() % request, tmp_key);
 270            tmp_val = eina_hash_find(hash, tmp_key);
 271         }
 272
 273    eina_hash_free(hash);
 274 }
 275
 276 static void
 277 eina_bench_lookup_djb2(int request)
 278 {
 279    Eina_Hash *hash = NULL;
 280    int *tmp_val;
 281    unsigned int i;
 282    unsigned int j;
 283
 284    hash = eina_hash_string_djb2_new(free);
 285
 286    for (i = 0; i < (unsigned int)request; ++i)
 287      {
 288         char tmp_key[10];
 289
 290         tmp_val = malloc(sizeof (int));
 291
 292         if (!tmp_val)
 293            continue;
 294
 295         eina_convert_itoa(i, tmp_key);
 296         *tmp_val = i;
 297
 298         eina_hash_add(hash, tmp_key, tmp_val);
 299      }
 300
 301    srand(time(NULL));
 302
 303    for (j = 0; j < 200; ++j)
 304       for (i = 0; i < (unsigned int)request; ++i)
 305         {
 306            char tmp_key[10];
 307
 308            eina_convert_itoa(rand() % request, tmp_key);
 309
 310            tmp_val = eina_hash_find(hash, tmp_key);
 311         }
 312
 313    eina_hash_free(hash);
 314 }
 315
 316 typedef struct _Eina_Bench_DJB2 Eina_Bench_DJB2;
 317 struct _Eina_Bench_DJB2
 318 {
 319    char *key;
 320    int value;
 321 };
 322
 323 static void
 324 eina_bench_lookup_djb2_inline(int request)
 325 {
 326    Eina_Hash *hash = NULL;
 327    Eina_Bench_DJB2 *elm;
 328    unsigned int i;
 329    unsigned int j;
 330
 331    hash = eina_hash_string_djb2_new(free);
 332
 333    for (i = 0; i < (unsigned int)request; ++i)
 334      {
 335         int length;
 336
 337         elm = malloc(sizeof (Eina_Bench_DJB2) + 10);
 338         if (!elm)
 339            continue;
 340
 341         elm->key = (char *)(elm + 1);
 342
 343         length = eina_convert_itoa(i, elm->key) + 1;
 344         elm->value = i;
 345
 346         eina_hash_direct_add_by_hash(hash, elm->key, length,
 347                                      eina_hash_djb2(elm->key, length), elm);
 348      }
 349
 350    srand(time(NULL));
 351
 352    for (j = 0; j < 200; ++j)
 353       for (i = 0; i < (unsigned int)request; ++i)
 354         {
 355            char tmp_key[10];
 356            int length = 6;
 357
 358            length = eina_convert_itoa(rand() % request, tmp_key) + 1;
 359
 360            elm =
 361               eina_hash_find_by_hash(hash, tmp_key, length,
 362                                      eina_hash_djb2(tmp_key, length));
 363         }
 364
 365    eina_hash_free(hash);
 366 }
 367
 368 #ifdef EINA_BENCH_HAVE_GLIB
 369 typedef struct _Eina_Bench_Glib Eina_Bench_Glib;
 370 struct _Eina_Bench_Glib
 371 {
 372    char *key;
 373    int value;
 374 };
 375
 376 static void
 377 eina_bench_lookup_ghash(int request)
 378 {
 379    Eina_Bench_Glib *elm;
 380    GHashTable *hash;
 381    unsigned int i;
 382    unsigned int j;
 383
 384    hash = g_hash_table_new_full(g_str_hash, g_str_equal, NULL, free);
 385
 386    for (i = 0; i < (unsigned int)request; ++i)
 387      {
 388         elm = malloc(sizeof (Eina_Bench_Glib) + 10);
 389         if (!elm)
 390            continue;
 391
 392         elm->key = (char *)(elm + 1);
 393
 394         eina_convert_itoa(i, elm->key);
 395         elm->value = i;
 396
 397         g_hash_table_insert(hash, elm->key, elm);
 398      }
 399
 400    srand(time(NULL));
 401
 402    for (j = 0; j < 200; ++j)
 403       for (i = 0; i < (unsigned int)request; ++i)
 404         {
 405            char tmp_key[10];
 406
 407            eina_convert_itoa(rand() % request, tmp_key);
 408
 409            elm = g_hash_table_lookup(hash, tmp_key);
 410         }
 411
 412    g_hash_table_destroy(hash);
 413 }
 414 #endif
 415
 416 static void
 417 eina_bench_lookup_evas(int request)
 418 {
 419    Evas_Hash *hash = NULL;
 420    Eina_Array *array = NULL;
 421    int *tmp_val;
 422    Eina_Array_Iterator it;
 423    unsigned int i;
 424    unsigned int j;
 425
 426    array = eina_array_new(10000);
 427
 428    for (i = 0; i < (unsigned int)request; ++i)
 429      {
 430         char tmp_key[10];
 431
 432         tmp_val = malloc(sizeof (int));
 433
 434         if (!tmp_val)
 435            continue;
 436
 437         eina_convert_itoa(i, tmp_key);
 438         *tmp_val = i;
 439
 440         hash = evas_hash_add(hash, tmp_key, tmp_val);
 441
 442         eina_array_push(array, tmp_val);
 443      }
 444
 445    srand(time(NULL));
 446
 447    for (j = 0; j < 200; ++j)
 448       for (i = 0; i < (unsigned int)request; ++i)
 449         {
 450            char tmp_key[10];
 451
 452            eina_convert_itoa(rand() % request, tmp_key);
 453
 454            tmp_val = evas_hash_find(hash, tmp_key);
 455         }
 456
 457    evas_hash_free(hash);
 458
 459    EINA_ARRAY_ITER_NEXT(array, i, tmp_val, it)
 460      free(tmp_val);
 461
 462    eina_array_free(array);
 463 }
 464
 465 typedef struct _Eina_Bench_Ecore Eina_Bench_Ecore;
 466 struct _Eina_Bench_Ecore
 467 {
 468    char *key;
 469    int value;
 470 };
 471
 472 static void
 473 eina_bench_lookup_ecore(int request)
 474 {
 475    Ecore_Hash *hash = NULL;
 476    Eina_Bench_Ecore *elm;
 477    unsigned int i;
 478    unsigned int j;
 479
 480    hash = ecore_hash_new(ecore_str_hash, ecore_str_compare);
 481
 482    ecore_hash_free_key_cb_set(hash, NULL);
 483    ecore_hash_free_value_cb_set(hash, free);
 484
 485    for (i = 0; i < (unsigned int)request; ++i)
 486      {
 487         elm = malloc(sizeof (Eina_Bench_Ecore) + 10);
 488         if (!elm)
 489            continue;
 490
 491         elm->key = (char *)(elm + 1);
 492         eina_convert_itoa(i, elm->key);
 493         elm->value = i;
 494
 495         ecore_hash_set(hash, elm->key, elm);
 496      }
 497
 498    srand(time(NULL));
 499
 500    for (j = 0; j < 200; ++j)
 501       for (i = 0; i < (unsigned int)request; ++i)
 502         {
 503            char tmp_key[10];
 504
 505            eina_convert_itoa(rand() % request, tmp_key);
 506
 507            elm = ecore_hash_get(hash, tmp_key);
 508         }
 509
 510    ecore_hash_destroy(hash);
 511 }
 512
 513 void eina_bench_hash(Eina_Benchmark *bench)
 514 {
 515    eina_benchmark_register(bench, "superfast-lookup",
 516                            EINA_BENCHMARK(
 517                               eina_bench_lookup_superfast),   10, 10000, 10);
 518    eina_benchmark_register(bench, "djb2-lookup",
 519                            EINA_BENCHMARK(
 520                               eina_bench_lookup_djb2),        10, 10000, 10);
 521    eina_benchmark_register(bench, "djb2-lookup-inline",
 522                            EINA_BENCHMARK(
 523                               eina_bench_lookup_djb2_inline), 10, 10000, 10);
 524    eina_benchmark_register(bench, "murmur",
 525                            EINA_BENCHMARK(
 526                               eina_bench_lookup_murmur),      10, 10000, 10);
 527 #ifdef CITYHASH_BENCH
 528    eina_benchmark_register(bench, "cityhash",
 529                            EINA_BENCHMARK(
 530                               eina_bench_lookup_cityhash),    10, 10000, 10);
 531 #endif
 532    eina_benchmark_register(bench, "rbtree",
 533                            EINA_BENCHMARK(
 534                               eina_bench_lookup_rbtree),      10, 10000, 10);
 535 #ifdef EINA_BENCH_HAVE_GLIB
 536    eina_benchmark_register(bench, "ghash-lookup",
 537                            EINA_BENCHMARK(
 538                               eina_bench_lookup_ghash),       10, 10000, 10);
 539 #endif
 540    eina_benchmark_register(bench, "evas-lookup",
 541                            EINA_BENCHMARK(
 542                               eina_bench_lookup_evas),        10, 10000, 10);
 543    eina_benchmark_register(bench, "ecore-lookup",
 544                            EINA_BENCHMARK(
 545                               eina_bench_lookup_ecore),       10, 10000, 10);
 546
 547 }