bst_vs_heap_vs_hashmap.cpp 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. // https://cirosantilli.com/linux-kernel-module-cheat#bst-vs-heap-vs-hashmap
  2. #include <algorithm>
  3. #include <cassert>
  4. #include <chrono>
  5. #include <iostream>
  6. #include <queue>
  7. #include <random>
  8. #include <set>
  9. #include <unordered_set>
  10. #include <lkmc/m5ops.h>
  11. int main(int argc, char **argv) {
  12. typedef uint64_t I;
  13. std::vector<I> randoms;
  14. size_t i, n, granule, base;
  15. std::priority_queue<I> heap;
  16. std::set<I> bst;
  17. std::unordered_set<I> hashmap;
  18. unsigned int seed;
  19. size_t j = 0;
  20. // CLI arguments.
  21. if (argc > 1) {
  22. n = std::stoi(argv[1]);
  23. } else {
  24. n = 10;
  25. }
  26. if (argc > 2) {
  27. granule = std::stoi(argv[2]);
  28. } else {
  29. granule = 1;
  30. }
  31. if (argc > 3) {
  32. seed = std::stoi(argv[3]);
  33. } else {
  34. seed = std::random_device()();
  35. }
  36. // Action.
  37. for (i = 0; i < n; ++i) {
  38. randoms.push_back(i);
  39. }
  40. std::shuffle(randoms.begin(), randoms.end(), std::mt19937(seed));
  41. for (i = 0; i < n / granule; ++i) {
  42. #ifndef LKMC_M5OPS_ENABLE
  43. using clk = std::chrono::high_resolution_clock;
  44. decltype(clk::now()) start, end;
  45. #endif
  46. base = i * granule;
  47. // Heap.
  48. #ifdef LKMC_M5OPS_ENABLE
  49. LKMC_M5OPS_RESETSTATS;
  50. #else
  51. start = clk::now();
  52. for (j = 0; j < granule; ++j) {
  53. #endif
  54. heap.emplace(randoms[base + j]);
  55. #ifdef LKMC_M5OPS_ENABLE
  56. LKMC_M5OPS_DUMPSTATS;
  57. #else
  58. }
  59. end = clk::now();
  60. auto dt_heap = (end - start) / granule;
  61. #endif
  62. // BST.
  63. #ifdef LKMC_M5OPS_ENABLE
  64. LKMC_M5OPS_RESETSTATS;
  65. #else
  66. start = clk::now();
  67. for (j = 0; j < granule; ++j) {
  68. #endif
  69. bst.insert(randoms[base + j]);
  70. #ifdef LKMC_M5OPS_ENABLE
  71. LKMC_M5OPS_DUMPSTATS;
  72. #else
  73. }
  74. end = clk::now();
  75. auto dt_bst = (end - start) / granule;
  76. #endif
  77. // Hashmap.
  78. #ifdef LKMC_M5OPS_ENABLE
  79. LKMC_M5OPS_RESETSTATS;
  80. #else
  81. start = clk::now();
  82. for (j = 0; j < granule; ++j) {
  83. #endif
  84. hashmap.insert(randoms[base + j]);
  85. #ifdef LKMC_M5OPS_ENABLE
  86. LKMC_M5OPS_DUMPSTATS;
  87. #else
  88. }
  89. end = clk::now();
  90. auto dt_hashmap = (end - start) / granule;
  91. #endif
  92. #ifndef LKMC_M5OPS_ENABLE
  93. // Output.
  94. std::cout
  95. << base << " "
  96. << std::chrono::duration_cast<std::chrono::nanoseconds>(dt_heap).count() << " "
  97. << std::chrono::duration_cast<std::chrono::nanoseconds>(dt_bst).count() << " "
  98. << std::chrono::duration_cast<std::chrono::nanoseconds>(dt_hashmap).count() << std::endl
  99. ;
  100. #endif
  101. }
  102. // Sanity check.
  103. for (auto it = bst.rbegin(); it != bst.rend(); ++it) {
  104. assert(*it == heap.top());
  105. heap.pop();
  106. }
  107. }