fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/9kVHQw
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!