| 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 | }
|