File: matt.cc

package info (click to toggle)
parallel-hashmap 1.4.1%2Bds-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid, trixie
  • size: 3,872 kB
  • sloc: cpp: 20,492; ansic: 1,114; python: 492; makefile: 85; haskell: 56; perl: 43; sh: 23
file content (140 lines) | stat: -rw-r--r-- 4,700 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <chrono>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <random>
#include <parallel_hashmap/phmap.h>
#include <parallel_hashmap/btree.h>

// -------------------------------------------------------------------
// -------------------------------------------------------------------
class Timer
{
public:
    Timer(std::string name) : _name(std::move(name)), _start(std::chrono::high_resolution_clock::now()) {}

    ~Timer() 
    {
        std::chrono::duration<float> elapsed_seconds = std::chrono::high_resolution_clock::now() - _start;
        printf("%s: %.3fs\n", _name.c_str(), elapsed_seconds.count());
    }

private:
    std::string _name;
    std::chrono::high_resolution_clock::time_point _start;
};

// --------------------------------------------------------------------------
//  from: https://github.com/preshing/RandomSequence
// --------------------------------------------------------------------------
class RSU
{
private:
    uint32_t m_index;
    uint32_t m_intermediateOffset;

    static uint32_t permuteQPR(uint32_t x)
    {
        static const uint32_t prime = 4294967291u;
        if (x >= prime)
            return x;  // The 5 integers out of range are mapped to themselves.
        uint32_t residue = ((unsigned long long) x * x) % prime;
        return (x <= prime / 2) ? residue : prime - residue;
    }

public:
    RSU(uint32_t seedBase, uint32_t seedOffset)
    {
        m_index = permuteQPR(permuteQPR(seedBase) + 0x682f0161);
        m_intermediateOffset = permuteQPR(permuteQPR(seedOffset) + 0x46790905);
    }

    uint32_t next()
    {
        return permuteQPR((permuteQPR(m_index++) + m_intermediateOffset) ^ 0x5bf03635);
    }
};

using Perturb = std::function<void (std::vector<uint64_t> &)>;

// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
template<class Set, size_t N>
void test(const char *name, const Perturb &perturb1, const Perturb& /* perturb2 */)
{
    //phmap::btree_set<uint64_t> s;
    Set s;

    unsigned int seed = 76687;
	RSU rsu(seed, seed + 1);

    for (uint32_t i=0; i<N; ++i)
        s.insert(rsu.next());

    std::vector<uint64_t> order(s.begin(), s.end()); // contains sorted, randomly generated keys (when using phmap::btree_set)
                                                     // or keys in the final order of a Set (when using Set).

    perturb1(order);                      // either keep them in same order, or shuffle them

#if 0
    order.resize(N/4);
    perturb2(order);
#endif

    Timer t(name); // start timer
    Set c;
    //c.reserve(order.size());               // whether this "reserve()" is present or not makes a huge difference
    c.insert(order.begin(), order.end());  // time for inserting the same keys into the set
                                           // should not depend on them being sorted or not.
}

// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
template <class T, size_t N>
using pset = phmap::parallel_flat_hash_set<T, 
                                           phmap::priv::hash_default_hash<T>,
                                           phmap::priv::hash_default_eq<T>,
                                           phmap::priv::Allocator<T>, // alias for std::allocator
                                           N>;

// --------------------------------------------------------------------------
// --------------------------------------------------------------------------
int main()
{
    auto shuffle = [](std::vector<uint64_t> &order) { 
        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(order.begin(), order.end(), g); 
    };

    auto noop = [](std::vector<uint64_t> &) {};

    auto perturb2 = noop;

    constexpr uint32_t num_keys = 10000000;
    using T = uint64_t;

    test<phmap::flat_hash_set<T>, num_keys>("flat_hash_set ordered ", noop, perturb2);

    test<phmap::flat_hash_set<T>, num_keys>("flat_hash_set shuffled", shuffle, perturb2);

    test<pset<T, 4>, num_keys>("parallel (16) ordered ", noop, perturb2);

    test<pset<T, 4>, num_keys>("parallel (16) shuffled", shuffle, perturb2);

    test<pset<T, 6>, num_keys>("parallel (64) ordered ", noop, perturb2);

    test<pset<T, 6>, num_keys>("parallel (64) shuffled", shuffle, perturb2);

    test<pset<T, 8>, num_keys>("parallel (256) ordered ", noop, perturb2);

    test<pset<T, 8>, num_keys>("parallel (256) shuffled", shuffle, perturb2);
}