"Fossies" - the Fresh Open Source Software Archive

Member "ponyc-0.33.2/benchmark/libponyrt/ds/hash.cc" (3 Feb 2020, 12626 Bytes) of package /linux/misc/ponyc-0.33.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hash.cc" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 0.33.1_vs_0.33.2.

    1 #include <benchmark/benchmark.h>
    2 #include <platform.h>
    3 
    4 #include <stdlib.h>
    5 #include <stdint.h>
    6 
    7 #include <ds/fun.h>
    8 #include <ds/hash.h>
    9 #include <mem/pool.h>
   10 #include <iostream>
   11 
   12 #define INITIAL_SIZE 8
   13 #define BELOW_HALF (INITIAL_SIZE + (2 - 1)) / 2
   14 
   15 typedef struct hash_elem_t hash_elem_t;
   16 
   17 DECLARE_HASHMAP(testmap, testmap_t, hash_elem_t)
   18 
   19 class HashMapBench: public ::benchmark::Fixture
   20 {
   21   protected:
   22     testmap_t _map;
   23 
   24     virtual void SetUp(const ::benchmark::State& st);
   25     virtual void TearDown(const ::benchmark::State& st);
   26 
   27     hash_elem_t* get_element();
   28     void put_elements(size_t count);
   29     void delete_elements(size_t del_count, size_t count);
   30 
   31   public:
   32     static size_t hash_tst(hash_elem_t* p);
   33     static bool cmp_tst(hash_elem_t* a, hash_elem_t* b);
   34     static void free_elem(hash_elem_t* p);
   35     static void free_buckets(size_t size, void* p);
   36 };
   37 
   38 DEFINE_HASHMAP(testmap, testmap_t, hash_elem_t, HashMapBench::hash_tst,
   39   HashMapBench::cmp_tst, HashMapBench::free_elem)
   40 
   41 struct hash_elem_t
   42 {
   43   size_t key;
   44   size_t val;
   45 };
   46 
   47 void HashMapBench::SetUp(const ::benchmark::State& st)
   48 {
   49   if (st.thread_index == 0) {
   50     // range(0) == initial size of hashmap
   51     testmap_init(&_map, static_cast<size_t>(st.range(0)));
   52     // range(1) == # of items to insert
   53     put_elements(static_cast<size_t>(st.range(1)));
   54     srand(635356);
   55   }
   56 }
   57 
   58 void HashMapBench::TearDown(const ::benchmark::State& st)
   59 {
   60   if (st.thread_index == 0) {
   61     testmap_destroy(&_map);
   62   }
   63 }
   64 
   65 void HashMapBench::put_elements(size_t count)
   66 {
   67   hash_elem_t* curr = NULL;
   68 
   69   for(size_t i = 0; i < count; i++)
   70   {
   71     curr = get_element();
   72     curr->key = i;
   73 
   74     testmap_put(&_map, curr);
   75   }
   76 }
   77 
   78 void HashMapBench::delete_elements(size_t del_pct, size_t count)
   79 {
   80   hash_elem_t* e1 = get_element();
   81   size_t del_count = (del_pct * count) / 100;
   82   size_t final_count = (del_count > count) ? 0 : count - del_count;
   83 
   84   // delete random items until map size is as small as required
   85   while(testmap_size(&_map) > final_count)
   86   {
   87     e1->key = (size_t)rand() % count;
   88 
   89     hash_elem_t* d = testmap_remove(&_map, e1);
   90     if(d != NULL)
   91       free_elem(d);
   92   }
   93   free_elem(e1);
   94 }
   95 
   96 hash_elem_t* HashMapBench::get_element()
   97 {
   98   return POOL_ALLOC(hash_elem_t);
   99 }
  100 
  101 size_t HashMapBench::hash_tst(hash_elem_t* p)
  102 {
  103   return ponyint_hash_size(p->key);
  104 }
  105 
  106 bool HashMapBench::cmp_tst(hash_elem_t* a, hash_elem_t* b)
  107 {
  108   return a->key == b->key;
  109 }
  110 
  111 void HashMapBench::free_elem(hash_elem_t* p)
  112 {
  113   POOL_FREE(hash_elem_t, p);
  114 }
  115 
  116 BENCHMARK_DEFINE_F(HashMapBench, HashDestroy$)(benchmark::State& st) {
  117   testmap_destroy(&_map);
  118   size_t sz = static_cast<size_t>(st.range(0));
  119   while (st.KeepRunning()) {
  120     st.PauseTiming();
  121     testmap_init(&_map, sz);
  122     // exclude time to fill map to exactly 50%
  123     size_t old_size = _map.contents.size;
  124     put_elements(old_size/2);
  125     if(testmap_size(&_map) != (size_t)(old_size/2))
  126     {
  127       st.SkipWithError("Map should be exactly half filled!");
  128       break; // Needed to skip the rest of the iteration.
  129     }
  130     st.ResumeTiming();
  131     // destroy map
  132     testmap_destroy(&_map);
  133   }
  134   testmap_init(&_map, sz);
  135   st.SetItemsProcessed((int64_t)st.iterations());
  136 }
  137 
  138 BENCHMARK_REGISTER_F(HashMapBench, HashDestroy$)->RangeMultiplier(2)->Ranges({{1, 32<<10}, {0, 0}});
  139 
  140 BENCHMARK_DEFINE_F(HashMapBench, HashResize$)(benchmark::State& st) {
  141   size_t old_size = 0;
  142   size_t count = static_cast<size_t>(st.range(0));
  143   while (st.KeepRunning()) {
  144     st.PauseTiming();
  145     if(_map.contents.size == old_size)
  146     {
  147       std::cout << "Shouldn't happen b: count: " << testmap_size(&_map) << ", size: "
  148         << _map.contents.size << ", old_size: " << old_size << std::endl;
  149       st.SkipWithError("Map should have resized!");
  150       break; // Needed to skip the rest of the iteration.
  151     }
  152     testmap_destroy(&_map);
  153     testmap_init(&_map, count);
  154     // exclude time to fill map to exactly 50%
  155     old_size = _map.contents.size;
  156     put_elements(old_size/2);
  157     if(testmap_size(&_map) != (size_t)(old_size/2))
  158     {
  159       st.SkipWithError("Map should be exactly half filled!");
  160       break; // Needed to skip the rest of the iteration.
  161     }
  162     hash_elem_t* curr = get_element();
  163     curr->key = (old_size/2) + 1;
  164     st.ResumeTiming();
  165     testmap_put(&_map, curr);
  166   }
  167   st.SetItemsProcessed((int64_t)st.iterations());
  168 }
  169 
  170 BENCHMARK_REGISTER_F(HashMapBench, HashResize$)->RangeMultiplier(2)->Ranges({{1, 32<<10}, {0, 0}});
  171 
  172 BENCHMARK_DEFINE_F(HashMapBench, HashNext)(benchmark::State& st) {
  173   while (st.KeepRunning()) {
  174     size_t ind = HASHMAP_UNKNOWN;
  175     for(size_t i = 0; i < testmap_size(&_map); i++) {
  176       hash_elem_t* n = testmap_next(&_map, &ind);
  177       if(n == NULL)
  178       {
  179         st.SkipWithError("Item shouldn't be NULL!");
  180         break; // Needed to skip the rest of the iteration.
  181       }
  182     }
  183     hash_elem_t* n = testmap_next(&_map, &ind);
  184     if(n != NULL)
  185     {
  186       st.SkipWithError("Item should be NULL!");
  187       break; // Needed to skip the rest of the iteration.
  188     }
  189   }
  190   st.SetItemsProcessed((int64_t)(st.iterations() * (testmap_size(&_map) + 1)));
  191 }
  192 
  193 BENCHMARK_REGISTER_F(HashMapBench, HashNext)->RangeMultiplier(2)->Ranges({{1, 32<<10}, {1, 32}});
  194 BENCHMARK_REGISTER_F(HashMapBench, HashNext)->RangeMultiplier(2)->Ranges({{1, 1}, {1, 32<<10}});
  195 
  196 BENCHMARK_DEFINE_F(HashMapBench, HashPut)(benchmark::State& st) {
  197   hash_elem_t* curr = get_element();
  198   size_t i = 0;
  199   size_t mod = static_cast<size_t>(st.range(0));
  200   while (st.KeepRunning()) {
  201     curr->key = i & mod;
  202 
  203     // put item
  204     testmap_put(&_map, curr);
  205     i++;
  206   }
  207   st.SetItemsProcessed((int64_t)st.iterations());
  208   for(i = 0; i < _map.contents.size; i++)
  209     testmap_clearindex(&_map, i);
  210   free_elem(curr);
  211 }
  212 
  213 BENCHMARK_REGISTER_F(HashMapBench, HashPut)->RangeMultiplier(2)->Ranges({{32<<10, 32<<10}, {0, 0}});
  214 
  215 BENCHMARK_DEFINE_F(HashMapBench, HashPutResize)(benchmark::State& st) {
  216   hash_elem_t* curr = get_element();
  217   size_t i = 1;
  218   while (st.KeepRunning()) {
  219     curr->key = i;
  220 
  221     // put item
  222     testmap_put(&_map, curr);
  223     i++;
  224   }
  225   st.SetItemsProcessed((int64_t)st.iterations());
  226   for(i = 0; i < _map.contents.size; i++)
  227     testmap_clearindex(&_map, i);
  228   free_elem(curr);
  229 }
  230 
  231 BENCHMARK_REGISTER_F(HashMapBench, HashPutResize)->RangeMultiplier(2)->Ranges({{1, 1}, {0, 0}});
  232 
  233 BENCHMARK_DEFINE_F(HashMapBench, HashPutNew)(benchmark::State& st) {
  234   hash_elem_t* curr = NULL;
  235   size_t i = 0;
  236   size_t mod = static_cast<size_t>(st.range(0));
  237   while (st.KeepRunning()) {
  238     if(curr == NULL)
  239       curr = get_element();
  240     curr->key = i & mod;
  241 
  242     // put item
  243     curr = testmap_put(&_map, curr);
  244     i++;
  245   }
  246   if(curr != NULL)
  247     free_elem(curr);
  248   st.SetItemsProcessed((int64_t)st.iterations());
  249 }
  250 
  251 BENCHMARK_REGISTER_F(HashMapBench, HashPutNew)->RangeMultiplier(2)->Ranges({{32<<10, 32<<10}, {0, 0}});
  252 
  253 BENCHMARK_DEFINE_F(HashMapBench, HashPutNewResize)(benchmark::State& st) {
  254   hash_elem_t* curr = NULL;
  255   size_t i = 1;
  256   while (st.KeepRunning()) {
  257     curr = get_element();
  258     curr->key = i;
  259 
  260     // put item
  261     testmap_put(&_map, curr);
  262     i++;
  263   }
  264   st.SetItemsProcessed((int64_t)st.iterations());
  265 }
  266 
  267 BENCHMARK_REGISTER_F(HashMapBench, HashPutNewResize)->RangeMultiplier(2)->Ranges({{1, 1}, {0, 0}});
  268 
  269 BENCHMARK_DEFINE_F(HashMapBench, HashRemove$_)(benchmark::State& st) {
  270   size_t sz = static_cast<size_t>(st.range(2));
  271   hash_elem_t* curr = get_element();
  272   hash_elem_t** a =
  273     (hash_elem_t**)ponyint_pool_alloc_size(sz * sizeof(hash_elem_t*));
  274   for(size_t i = 0; i < sz; i++)
  275   {
  276     a[i] = get_element();
  277     a[i]->key = i;
  278   }
  279   while (st.KeepRunning()) {
  280     st.PauseTiming();
  281     for(size_t i = 0; i < sz; i++)
  282       testmap_put(&_map, a[i]);
  283     st.ResumeTiming();
  284     for(size_t i = 0; i < sz; i++)
  285     {
  286       curr->key = i;
  287       // remove item
  288       testmap_remove(&_map, curr);
  289     }
  290   }
  291   st.SetItemsProcessed((int64_t)(st.iterations() * sz));
  292   for(size_t i = 0; i < sz; i++)
  293     free_elem(a[i]);
  294   free_elem(curr);
  295   ponyint_pool_free_size(sz, a);
  296 }
  297 
  298 BENCHMARK_REGISTER_F(HashMapBench, HashRemove$_)->RangeMultiplier(2)->Ranges({{32<<10, 32<<10}, {0, 0}, {1<<10, 64<<10}});
  299 
  300 BENCHMARK_DEFINE_F(HashMapBench, HashSearch)(benchmark::State& st) {
  301   hash_elem_t* e1 = get_element();
  302   size_t map_count = testmap_size(&_map);
  303   size_t map_count_mask = map_count - 1;
  304   size_t* a = (size_t*)ponyint_pool_alloc_size(map_count * sizeof(size_t));
  305   size_t index = HASHMAP_UNKNOWN;
  306   size_t incr = static_cast<size_t>(st.range(1));
  307   if(st.range(2) == 0) {
  308     for(size_t i = 0; i < map_count; i++) {
  309       hash_elem_t* n = testmap_next(&_map, &index);
  310       if(n != NULL) {
  311         a[i] = n->key;
  312       }
  313     }
  314     size_t t = 0;
  315     size_t r = 0;
  316     for(size_t i = 0; i < map_count; i++) {
  317       r = (size_t)rand() & map_count_mask;
  318       t = a[r];
  319       a[r] = a[i];
  320       a[i] = t;
  321     }
  322   } else {
  323     for(size_t i = 0; i < map_count; i++) {
  324       a[i] = (size_t)rand() + incr;
  325     }
  326   }
  327 
  328   index = HASHMAP_UNKNOWN;
  329   size_t j = 0;
  330   while (st.KeepRunning()) {
  331     e1->key = a[j & map_count_mask];
  332     testmap_get(&_map, e1, &index);
  333     j++;
  334   }
  335   st.SetItemsProcessed((int64_t)st.iterations());
  336   ponyint_pool_free_size(map_count, a);
  337   free_elem(e1);
  338   e1 = nullptr;
  339 }
  340 
  341 BENCHMARK_REGISTER_F(HashMapBench, HashSearch)->RangeMultiplier(2)->Ranges({{1, 1}, {1<<10, 32<<10}, {0, 1}});
  342 
  343 BENCHMARK_DEFINE_F(HashMapBench, HashSearchDeletes)(benchmark::State& st) {
  344   size_t count = static_cast<size_t>(st.range(1));
  345   // range(2) == % of items to delete at random
  346   delete_elements(static_cast<size_t>(st.range(2)), count);
  347   hash_elem_t* e1 = get_element();
  348   size_t* a = NULL;
  349   size_t map_count = testmap_size(&_map);
  350   // we're testing our pathological case
  351   if(map_count == 0)
  352   {
  353     for(size_t i = 0; i < _map.contents.size; i++) {
  354       e1->key = i;
  355 
  356       // putindex item
  357       testmap_putindex(&_map, e1, i);
  358 
  359       // remove item
  360       testmap_removeindex(&_map, i);
  361     }
  362     // put item so it's not empty
  363     hash_elem_t* e2 = get_element();
  364     e2->key = count - 1;
  365     testmap_put(&_map, e2);
  366   }
  367   map_count = testmap_size(&_map);
  368   size_t array_size = ponyint_next_pow2(map_count);
  369   size_t array_size_mask = array_size - 1;
  370   array_size = array_size < 128 ? 128 : array_size;
  371   a = (size_t*)ponyint_pool_alloc_size(array_size * sizeof(size_t));
  372   size_t ind = HASHMAP_UNKNOWN;
  373   if(st.range(3) == 0) {
  374     for(size_t i = 0; i < array_size; i++) {
  375       if(i < map_count) {
  376         hash_elem_t* n = testmap_next(&_map, &ind);
  377         if(n != NULL) {
  378           a[i] = n->key;
  379         }
  380       } else {
  381         a[i] = a[(size_t)rand() % map_count];
  382       }
  383     }
  384     size_t t = 0;
  385     size_t r = 0;
  386     for(size_t i = 0; i < array_size; i++) {
  387       r = (size_t)rand() & array_size_mask;
  388       t = a[r];
  389       a[r] = a[i];
  390       a[i] = t;
  391     }
  392   } else {
  393     for(size_t i = 0; i < array_size; i++) {
  394       a[i] = (size_t)rand() + count;
  395     }
  396   }
  397 
  398   ind = HASHMAP_UNKNOWN;
  399   size_t j = 0;
  400   while (st.KeepRunning()) {
  401     e1->key = a[j & array_size_mask];
  402     testmap_get(&_map, e1, &ind);
  403     j++;
  404   }
  405   st.SetItemsProcessed((int64_t)st.iterations());
  406   ponyint_pool_free_size(array_size, a);
  407   free_elem(e1);
  408   e1 = nullptr;
  409 }
  410 
  411 BENCHMARK_REGISTER_F(HashMapBench, HashSearchDeletes)
  412   ->Args({1, 1<<10, 64, 0})
  413   ->Args({1, 2<<10, 64, 0})
  414   ->Args({1, 4<<10, 64, 0})
  415   ->Args({1, 8<<10, 64, 0})
  416   ->Args({1, 16<<10, 64, 0})
  417   ->Args({1, 32<<10, 64, 0})
  418   ->Args({1, 1<<10, 90, 0})
  419   ->Args({1, 2<<10, 90, 0})
  420   ->Args({1, 4<<10, 90, 0})
  421   ->Args({1, 8<<10, 90, 0})
  422   ->Args({1, 16<<10, 90, 0})
  423   ->Args({1, 32<<10, 90, 0})
  424   ->Args({1, 1<<10, 99, 0})
  425   ->Args({1, 2<<10, 99, 0})
  426   ->Args({1, 4<<10, 99, 0})
  427   ->Args({1, 8<<10, 99, 0})
  428   ->Args({1, 16<<10, 99, 0})
  429   ->Args({1, 32<<10, 99, 0})
  430   ->Args({1, 1<<10, 101, 0})
  431   ->Args({1, 2<<10, 101, 0})
  432   ->Args({1, 4<<10, 101, 0})
  433   ->Args({1, 8<<10, 101, 0})
  434   ->Args({1, 16<<10, 101, 0})
  435   ->Args({1, 32<<10, 101, 0})
  436   ->Args({1, 1<<10, 64, 1})
  437   ->Args({1, 2<<10, 64, 1})
  438   ->Args({1, 4<<10, 64, 1})
  439   ->Args({1, 8<<10, 64, 1})
  440   ->Args({1, 16<<10, 64, 1})
  441   ->Args({1, 32<<10, 64, 1})
  442   ->Args({1, 1<<10, 90, 1})
  443   ->Args({1, 2<<10, 90, 1})
  444   ->Args({1, 4<<10, 90, 1})
  445   ->Args({1, 8<<10, 90, 1})
  446   ->Args({1, 16<<10, 90, 1})
  447   ->Args({1, 32<<10, 90, 1})
  448   ->Args({1, 1<<10, 99, 1})
  449   ->Args({1, 2<<10, 99, 1})
  450   ->Args({1, 4<<10, 99, 1})
  451   ->Args({1, 8<<10, 99, 1})
  452   ->Args({1, 16<<10, 99, 1})
  453   ->Args({1, 32<<10, 99, 1})
  454   ->Args({1, 1<<10, 101, 1})
  455   ->Args({1, 2<<10, 101, 1})
  456   ->Args({1, 4<<10, 101, 1})
  457   ->Args({1, 8<<10, 101, 1})
  458   ->Args({1, 16<<10, 101, 1})
  459   ->Args({1, 32<<10, 101, 1});