fork download
  1. #include <unordered_map>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. #include <chrono>
  6.  
  7. #include <cstdio>
  8. #include <cstdlib>
  9. #include <ctime>
  10. #include <cmath>
  11.  
  12. template<typename T> struct cast_to_uint
  13. {
  14. // This is identical to std::hash, but it optimizes differently!
  15. constexpr std::size_t operator()(T const* k) const
  16. {
  17. return reinterpret_cast<size_t>(k);
  18. }
  19. };
  20.  
  21. template<typename T, unsigned int N> struct right_shift
  22. {
  23. // This actually makes sense for N = 2 or N = 3, since the low 3 bits
  24. // are always zero, for larger N this only discards entropy.
  25. // Surprisingly, this is not at all a bad hash, most of the time
  26. // among the fastest three!
  27. constexpr std::size_t operator()(T const* k) const
  28. {
  29. return (size_t) k>>N;
  30. }
  31. };
  32.  
  33. template<typename T> struct simple_xorshift
  34. {
  35. // Marsaglia PRNG used to hash bits, large shifts used
  36. // to fill the constant low zero-bits with entropy
  37. // Mixes bits very well considering it's about 2x the speed of murmur,
  38. // but no overall advantage in hash table performance
  39. std::size_t operator()(T const* k) const
  40. {
  41. unsigned int x = (unsigned int) k;
  42. x ^= x >> 11;
  43. x ^= x << 7;
  44. x ^= x >> 12;
  45. return x;
  46. }
  47. };
  48.  
  49. template<typename T> struct double_xorshift
  50. {
  51. // Same as above, but combining two different generators
  52. // Sadly 50% slower on x86 due to lack of registers
  53. // (amd64 implementation should be +/- 1 clock tick of simple version)
  54. std::size_t operator()(T const* k) const
  55. {
  56. unsigned int x = (unsigned int) k;
  57. unsigned int y = x;
  58. x ^= x << 14;
  59. x ^= x >> 13;
  60. x ^= x << 15;
  61. y ^= y << 11;
  62. y ^= y >> 19;
  63. y ^= y << 8;
  64.  
  65. return x+y;
  66. }
  67. };
  68.  
  69. template<typename T> struct djb2
  70. {
  71. // standard implementation,
  72. // hardcoded input size = 4
  73. std::size_t operator()(T const* k) const
  74. {
  75. unsigned int x = (unsigned int) k;
  76. unsigned int h = 5381;
  77. h = h*33 + (x & 0xff);
  78. h = h*33 + (x>>8 & 0xff);
  79. h = h*33 + (x>>16 & 0xff);
  80. h = h*33 + (x>>24 & 0xff);
  81. return h;
  82. }
  83. };
  84.  
  85. template<typename T> struct djb2_mod
  86. {
  87. // Same as above, except for using larger seed so
  88. // overflow happens earlier (since only 4 bytes of input)
  89. std::size_t operator()(T const* k) const
  90. {
  91. unsigned int x = (unsigned int) k;
  92. unsigned int h = 715225739;
  93. h = h*33 + (x & 0xff);
  94. h = h*33 + (x>>8 & 0xff);
  95. h = h*33 + (x>>16 & 0xff);
  96. h = h*33 + (x>>24 & 0xff);
  97. return h;
  98. }
  99. };
  100.  
  101. template<typename T> struct sdbm
  102. {
  103. // Standard implementation, hardcoded input size = 4
  104. std::size_t operator()(T const* k) const
  105. {
  106. unsigned int x = (unsigned int) k;
  107. unsigned int h = 0;
  108.  
  109. h = h * 65599 + (x & 0xff);
  110. h = h * 65599 + (x>>8 & 0xff);
  111. h = h * 65599 + (x>>16 & 0xff);
  112. h = h * 65599 + (x>>24 & 0xff);
  113. return h;
  114. }
  115. };
  116.  
  117. template<typename T> struct yet_another_lc
  118. {
  119. // Same design as djb and sdbm, using different prime multiplier.
  120. // This is the last one of about 50 different primes beween 7 and 17 bits
  121. // that I've tried. None truly performed any better (though some did worse).
  122. // This proves the common knowledge that finding a good (or better) hash function
  123. // is very hard.
  124. std::size_t operator()(T const* k) const
  125. {
  126. unsigned int x = (unsigned int) k;
  127. unsigned int h = 174440041;
  128.  
  129. h = h * 257 + (x & 0xff);
  130. h = h * 257 + (x>>8 & 0xff);
  131. h = h * 257 + (x>>16 & 0xff);
  132. h = h * 257 + (x>>24 & 0xff);
  133. return h;
  134. }
  135. };
  136.  
  137. template<typename T> struct murmur2
  138. {
  139. // Hardcoded input size = 4
  140. std::size_t operator()(T const* k) const
  141. {
  142. const unsigned int m = 0x5bd1e995;
  143.  
  144. uint32_t h = 4;
  145.  
  146. unsigned int d = (unsigned int) k;
  147.  
  148. d *= m;
  149. d ^= d >> 24;
  150. d *= m;
  151.  
  152. h *= m;
  153. h ^= d;
  154.  
  155.  
  156. h ^= h >> 13;
  157. h *= m;
  158. h ^= h >> 15;
  159.  
  160. return h;
  161. }
  162. };
  163.  
  164. template<typename T> struct murmur3
  165. {
  166. // Hardcoded input size = 4.
  167. // Omitted xor with input size in the final mix step, as that's a constant,
  168. // and this only flips a single bit (waste of CPU cycles).
  169.  
  170. template<int r> constexpr uint32_t rotl(uint32_t x) { return (x << r) | (x >> (32 - r)); }
  171.  
  172. unsigned int fmix32( unsigned int h ) const
  173. {
  174. h ^= h >> 16;
  175. h *= 0x85ebca6b;
  176. h ^= h >> 13;
  177. h *= 0xc2b2ae35;
  178. h ^= h >> 16;
  179. return h;
  180. }
  181.  
  182. std::size_t operator()(T const* k) const
  183. {
  184. constexpr unsigned int c1 = 0xcc9e2d51;
  185. constexpr unsigned int c2 = 0x1b873593;
  186.  
  187. unsigned int h = (unsigned int) k;
  188.  
  189. h *= c1;
  190. h = rotl<15>(h);
  191. h *= c2;
  192.  
  193. h = rotl<13>(h);
  194. h = h*5+0xe6546b64;
  195.  
  196. return fmix32(h);
  197. }
  198. };
  199.  
  200. // Copy-paste as posted on SO
  201. template<typename Tval>
  202. struct MyTemplatePointerHash1 {
  203. size_t operator()(const Tval* val) const {
  204. static const size_t shift = (size_t)log2(1 + sizeof(Tval));
  205. return (size_t)(val) >> shift;
  206. }
  207. };
  208.  
  209. // Copy-paste as posted on SO
  210. struct BasileStarynkevitch {
  211. size_t operator()(const void* val) const {
  212. uintptr_t ad = (uintptr_t) val;
  213. return (size_t) ((13*ad) ^ (ad >> 15));
  214. }
  215. };
  216.  
  217.  
  218.  
  219. template<typename H> void benchmark_hash(const char* name)
  220. {
  221. using namespace std::chrono;
  222.  
  223. printf("%-25s ", name);
  224. H hash;
  225.  
  226. {
  227. auto start = system_clock::now();
  228.  
  229. int unused = 0;
  230. for(unsigned int i = 0; i < 4*1000*1000*1000; ++i)
  231. unused += hash((int*)i);
  232. __attribute__ (( unused )) volatile int optimizer_sink = unused;
  233.  
  234. auto stop = system_clock::now();
  235. printf("%-10lld\n", duration_cast<milliseconds>(stop - start).count());
  236. }
  237. }
  238.  
  239.  
  240. template<typename T, typename H> void test(std::vector<T*> const& vec, unsigned int bucket_count, const char* name)
  241. {
  242. using namespace std::chrono;
  243.  
  244. printf("%-25s ", name);
  245.  
  246. {
  247. auto start = system_clock::now();
  248.  
  249. for(unsigned int iterations = 0; iterations < 50; ++iterations)
  250. {
  251. std::unordered_map<T*, int, H> map(bucket_count);
  252. for(auto& elem : vec) map.insert(std::pair<T*, int>(elem, 1));
  253. }
  254. auto stop = system_clock::now();
  255. printf("%-10lld ", duration_cast<milliseconds>(stop - start).count());
  256. }
  257.  
  258. {
  259. std::unordered_map<T*, int, H> map(bucket_count);
  260.  
  261. for(auto& elem : vec) map.insert(std::pair<T*, int>(elem, 1));
  262.  
  263. auto start = system_clock::now();
  264.  
  265. int unused = 0;
  266. for(unsigned int i = 0; i < 100*1000*1000; ++i)
  267. {
  268. auto it = map.find(vec[(rand() ^ (rand()<<16)) % vec.size()]);
  269. unused += it->second;
  270. }
  271. __attribute__ (( unused )) volatile int optimizer_sink = unused;
  272.  
  273. auto stop = system_clock::now();
  274. printf("%-10lld ", duration_cast<milliseconds>(stop - start).count());
  275. }
  276.  
  277.  
  278. puts("");
  279. fflush(stdout);
  280. }
  281.  
  282.  
  283. template<typename T> void do_tests(unsigned int num_elements, bool shuffle)
  284. {
  285. puts ("--------------------------------");
  286. printf("sizeof(T) = %u\n", sizeof(T));
  287. printf("sizeof(T*) = %u\n", sizeof(T*));
  288. printf("insertion order = %s\n\n", (shuffle ? "random" : "sequential"));
  289. printf("dataset size = %8u elements\n", num_elements);
  290.  
  291. std::vector<T*> vec;
  292. vec.reserve(num_elements);
  293.  
  294. for(unsigned int i = 0; i < num_elements; ++i)
  295. vec.push_back(new T);
  296.  
  297. for(auto& elem : vec)
  298. delete elem; // don't actually need these, only need the addresses
  299.  
  300. if(shuffle) std::random_shuffle(vec.begin(), vec.end());
  301.  
  302. unsigned int seed = time(0); // random, but identical access pattern for all tests
  303.  
  304. printf("%-25s %-10s %-10s\n", "name", "insert", "access");
  305.  
  306. srand(seed); test<T, std::hash<T*>> (vec, num_elements, "std::hash");
  307. srand(seed); test<T, cast_to_uint<T>> (vec, num_elements, "reinterpret_cast");
  308. srand(seed); test<T, djb2<T>> (vec, num_elements, "djb2");
  309. srand(seed); test<T, djb2_mod<T>> (vec, num_elements, "djb2_mod");
  310. srand(seed); test<T, sdbm<T>> (vec, num_elements, "sdbm");
  311. srand(seed); test<T, yet_another_lc<T>> (vec, num_elements, "yet_another_lc");
  312. srand(seed); test<T, murmur2<T>> (vec, num_elements, "murmur2");
  313. srand(seed); test<T, murmur3<T>> (vec, num_elements, "murmur3");
  314. srand(seed); test<T, simple_xorshift<T>> (vec, num_elements, "simple_xorshift");
  315. srand(seed); test<T, double_xorshift<T>> (vec, num_elements, "double_xorshift");
  316. srand(seed); test<T, right_shift<T, 2>> (vec, num_elements, "right_shift_2");
  317. srand(seed); test<T, right_shift<T, 3>> (vec, num_elements, "right_shift_3");
  318. srand(seed); test<T, right_shift<T, 4>> (vec, num_elements, "right_shift_4");
  319. srand(seed); test<T, right_shift<T, 5>> (vec, num_elements, "right_shift_5");
  320. srand(seed); test<T, right_shift<T, 8>> (vec, num_elements, "right_shift_8");
  321. srand(seed); test<T, right_shift<T, 12>> (vec, num_elements, "right_shift_12");
  322. srand(seed); test<T, MyTemplatePointerHash1<T>> (vec, num_elements, "MyTemplatePointerHash1");
  323. srand(seed); test<T, BasileStarynkevitch> (vec, num_elements, "BasileStarynkevitch");
  324. puts("");
  325. }
  326.  
  327.  
  328.  
  329. #include <windows.h>
  330.  
  331. struct object64 { char x[64]; };
  332. struct object256 { char x[256]; };
  333. struct object1024 { char x[1024]; };
  334.  
  335. int main()
  336. {
  337. timeBeginPeriod(1);
  338.  
  339. puts("Benchmarking hash funcs...");
  340. benchmark_hash<std::hash<int*>> ("std::hash");
  341. benchmark_hash<cast_to_uint<int>> ("reinterpret_cast");
  342. benchmark_hash<djb2<int>> ("djb2");
  343. benchmark_hash<djb2_mod<int>> ("djb2_mod");
  344. benchmark_hash<sdbm<int>> ("sdbm");
  345. benchmark_hash<yet_another_lc<int>> ("yet_another_lc");
  346. benchmark_hash<murmur2<int>> ("murmur2");
  347. benchmark_hash<murmur3<int>> ("murmur3");
  348. benchmark_hash<simple_xorshift<int>> ("simple_xorshift");
  349. benchmark_hash<double_xorshift<int>> ("double_xorshift");
  350. benchmark_hash<right_shift<int, 2>> ("right_shift_2");
  351. benchmark_hash<right_shift<int, 3>> ("right_shift_3");
  352. benchmark_hash<right_shift<int, 4>> ("right_shift_4");
  353. benchmark_hash<right_shift<int, 5>> ("right_shift_5");
  354. benchmark_hash<right_shift<int, 8>> ("right_shift_8");
  355. benchmark_hash<right_shift<int, 12>> ("right_shift_12");
  356. benchmark_hash<MyTemplatePointerHash1<int>> ("MyTemplatePointerHash1");
  357. benchmark_hash<BasileStarynkevitch> ("BasileStarynkevitch");
  358.  
  359. puts("");
  360.  
  361. do_tests<int>(50000, false);
  362. do_tests<int>(50000, true);
  363. do_tests<int>(1000000, false);
  364. do_tests<int>(1000000, true);
  365.  
  366.  
  367. do_tests<object64>(50000, false);
  368. do_tests<object64>(50000, true);
  369. do_tests<object64>(1000000, false);
  370. do_tests<object64>(1000000, true);
  371.  
  372. do_tests<object256>(50000, false);
  373. do_tests<object256>(50000, true);
  374. do_tests<object256>(1000000, false);
  375. do_tests<object256>(1000000, true);
  376.  
  377. do_tests<object1024>(50000, false);
  378. do_tests<object1024>(50000, true);
  379. do_tests<object1024>(1000000, false);
  380. do_tests<object1024>(1000000, true);
  381.  
  382.  
  383. timeEndPeriod(1);
  384.  
  385. return 0;
  386. }
  387.  
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
In file included from /usr/include/c++/4.8/unordered_map:35:0,
                 from prog.cpp:1:
/usr/include/c++/4.8/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support is currently experimental, and must be enabled with the -std=c++11 or -std=gnu++11 compiler options.
 #error This file requires compiler and library support for the \
  ^
prog.cpp:15:2: warning: identifier ‘constexpr’ is a keyword in C++11 [-Wc++0x-compat]
  constexpr std::size_t operator()(T const* k) const
  ^
prog.cpp:329:21: fatal error: windows.h: No such file or directory
 #include <windows.h>
                     ^
compilation terminated.
stdout
Standard output is empty