c_cpp/lib/klib/test/khash_keith.c

   1 /*
   2  * This is an optimized version of the following C++ program:
   3  *
   4  *   http://keithlea.com/javabench/src/cpp/hash.cpp
   5  *
   6  * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the
   7  * Java implementation is twice as fast as the C++ version. In fact, this is
   8  * only because the C++ implementation is substandard. Most importantly, Keith
   9  * is using "sprintf()" to convert an integer to a string, which is known to be
  10  * extremely inefficient.
  11  */
  12 #include <stdio.h>
  13 #include "khash.h"
  14 KHASH_MAP_INIT_STR(str, int)
  15
  16 inline void int2str(int c, int base, char *ret)
  17 {
  18         const char *tab = "0123456789abcdef";
  19         if (c == 0) ret[0] = '0', ret[1] = 0;
  20         else {
  21                 int l, x, y;
  22                 char buf[16];
  23                 for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base];
  24                 if (c < 0) buf[l++] = '-';
  25                 for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x];
  26                 ret[y] = 0;
  27         }
  28 }
  29
  30 #ifndef _USE_STRDUP
  31 #define BLOCK_SIZE 0x100000
  32 int main(int argc, char *argv[])
  33 {
  34         char **mem = 0;
  35         int i, l, n = 1000000, ret, block_end = 0, curr = 0, c = 0;
  36         khash_t(str) *h;
  37         h = kh_init(str);
  38         if (argc > 1) n = atoi(argv[1]);
  39         mem = malloc(sizeof(void*));
  40         mem[0] = malloc(BLOCK_SIZE); // memory buffer to avoid memory fragmentation
  41         curr = block_end = 0;
  42         for (i = 1; i <= n; ++i) {
  43                 char buf[16];
  44                 int2str(i, 16, buf);
  45                 khint_t k = kh_put(str, h, buf, &ret);
  46                 l = strlen(buf) + 1;
  47                 if (block_end + l > BLOCK_SIZE) {
  48                         ++curr; block_end = 0;
  49                         mem = realloc(mem, (curr + 1) * sizeof(void*));
  50                         mem[curr] = malloc(BLOCK_SIZE);
  51                 }
  52                 memcpy(mem[curr] + block_end, buf, l);
  53                 kh_key(h, k) = mem[curr] + block_end;
  54                 block_end += l;
  55                 kh_val(h, k) = i;
  56         }
  57         for (i = 1; i <= n; ++i) {
  58                 char buf[16];
  59                 int2str(i, 10, buf);
  60                 khint_t k = kh_get(str, h, buf);
  61                 if (k != kh_end(h)) ++c;
  62         }
  63         printf("%d\n", c);
  64         for (ret = 0; ret <= curr; ++ret) free(mem[ret]);
  65         free(mem);
  66         kh_destroy(str, h);
  67         return 0;
  68 }
  69 #else // _USE_STRDUP
  70 int main(int argc, char *argv[])
  71 {
  72         int i, l, n = 1000000, ret, c = 0;
  73         khash_t(str) *h;
  74         khint_t k;
  75         h = kh_init(str);
  76         if (argc > 1) n = atoi(argv[1]);
  77         for (i = 1; i <= n; ++i) {
  78                 char buf[16];
  79                 int2str(i, 16, buf);
  80                 k = kh_put(str, h, strdup(buf), &ret);
  81                 kh_val(h, k) = i;
  82         }
  83         for (i = 1; i <= n; ++i) {
  84                 char buf[16];
  85                 int2str(i, 10, buf);
  86                 k = kh_get(str, h, buf);
  87                 if (k != kh_end(h)) ++c;
  88         }
  89         for (k = kh_begin(h); k != kh_end(h); ++k) // explicitly freeing memory takes 10-20% CPU time.
  90                 if (kh_exist(h, k)) free((char*)kh_key(h, k));
  91         printf("%d\n", c);
  92         kh_destroy(str, h);
  93         return 0;
  94 }
  95 #endif