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