1 | #include <set>
|
2 | #include <unordered_set>
|
3 |
|
4 | #include "mycpp/common.h"
|
5 | #include "vendor/greatest.h"
|
6 |
|
7 | // Make sure we don't have the "hash pileup" problem
|
8 | TEST unordered_set_bucket_test() {
|
9 | std::unordered_set<void *> set;
|
10 | // 1 bucket!
|
11 | log("bucket_count = %d", set.bucket_count());
|
12 |
|
13 | for (int i = 0; i < 1000; ++i) {
|
14 | void *p = malloc(1);
|
15 | // log("p = %p", p);
|
16 |
|
17 | std::hash<void *> hasher;
|
18 | int h = hasher(p);
|
19 | // This is just the low bits!
|
20 | // log("std::hash<void*>(pp) = %x", h);
|
21 | (void)h;
|
22 |
|
23 | set.insert(p);
|
24 | log("bucket %d", set.bucket(p));
|
25 | }
|
26 | // 1493 buckets, avoids power of 2 problem
|
27 | log("bucket_count = %d", set.bucket_count());
|
28 |
|
29 | PASS();
|
30 | }
|
31 |
|
32 | // Benchmark to test hashing against malloc()
|
33 | TEST hash_speed_test() {
|
34 | std::unordered_set<void *> hash_set;
|
35 | std::set<void *> tree_set;
|
36 | int n = 10e3; // change to 10e6 for significant benchmark
|
37 | // int n = 10e6;
|
38 | for (int i = 0; i < n; ++i) {
|
39 | // TODO: use random size workload too
|
40 | void *p = malloc(1);
|
41 | hash_set.insert(p);
|
42 | tree_set.insert(p);
|
43 | }
|
44 | log("hash_set size = %d", hash_set.size());
|
45 | log("bucket_count = %d", hash_set.bucket_count());
|
46 | log("tree_set size = %d", tree_set.size());
|
47 |
|
48 | PASS();
|
49 | }
|
50 |
|
51 | void do_mod(int n, int divisor) {
|
52 | int sum = 0;
|
53 | for (int i = 0; i < n; ++i) {
|
54 | sum += i % divisor;
|
55 | }
|
56 | log("sum = %d", sum);
|
57 | }
|
58 |
|
59 | TEST modulus_benchmark() {
|
60 | // 830 ms
|
61 | // do_mod(1<<30, 8);
|
62 |
|
63 | // 1.11 s
|
64 | // do_mod(1<<30, 7);
|
65 |
|
66 | // 900 ms seconds
|
67 | do_mod(1 << 30, 6);
|
68 |
|
69 | PASS();
|
70 | }
|
71 |
|
72 | GREATEST_MAIN_DEFS();
|
73 |
|
74 | int main(int argc, char **argv) {
|
75 | // gHeap.Init(MiB(64));
|
76 |
|
77 | GREATEST_MAIN_BEGIN();
|
78 |
|
79 | RUN_TEST(unordered_set_bucket_test);
|
80 | RUN_TEST(hash_speed_test);
|
81 | // RUN_TEST(modulus_benchmark);
|
82 |
|
83 | GREATEST_MAIN_END(); /* display results */
|
84 | return 0;
|
85 | }
|