452 lines
14 KiB
C++
452 lines
14 KiB
C++
#include <inttypes.h>
|
|
|
|
#ifdef STL_UNORDERED
|
|
#include <unordered_map>
|
|
#define MAPNAME std::unordered_map
|
|
#define EXTRAARGS
|
|
#elif defined(SPARSEPP)
|
|
#define SPP_USE_SPP_ALLOC 1
|
|
#include <sparsepp/spp.h>
|
|
#define MAPNAME spp::sparse_hash_map
|
|
#define EXTRAARGS
|
|
#elif defined(ABSEIL_FLAT)
|
|
#include "absl/container/flat_hash_map.h"
|
|
#define MAPNAME absl::flat_hash_map
|
|
#define EXTRAARGS
|
|
#elif defined(PHMAP_FLAT)
|
|
#include "parallel_hashmap/phmap.h"
|
|
#define MAPNAME phmap::flat_hash_map
|
|
#define NMSP phmap
|
|
#define EXTRAARGS
|
|
#elif defined(ABSEIL_PARALLEL_FLAT) || defined(PHMAP)
|
|
#if defined(ABSEIL_PARALLEL_FLAT)
|
|
#include "absl/container/parallel_flat_hash_map.h"
|
|
#define MAPNAME absl::parallel_flat_hash_map
|
|
#define NMSP absl
|
|
#define MTX absl::Mutex
|
|
#else
|
|
#if 1
|
|
// use Abseil's mutex... faster
|
|
#include "absl/synchronization/mutex.h"
|
|
#define MTX absl::Mutex
|
|
#else
|
|
#include <mutex>
|
|
#define MTX std::mutex
|
|
#endif
|
|
|
|
#include "parallel_hashmap/phmap.h"
|
|
#define MAPNAME phmap::parallel_flat_hash_map
|
|
#define NMSP phmap
|
|
#endif
|
|
|
|
#define MT_SUPPORT 2
|
|
#if MT_SUPPORT == 1
|
|
// create the parallel_flat_hash_map without internal mutexes, for when
|
|
// we programatically ensure that each thread uses different internal submaps
|
|
// --------------------------------------------------------------------------
|
|
#define EXTRAARGS , NMSP::priv::hash_default_hash<K>, \
|
|
NMSP::priv::hash_default_eq<K>, \
|
|
std::allocator<std::pair<const K, V>>, 4, NMSP::NullMutex
|
|
#elif MT_SUPPORT == 2
|
|
// create the parallel_flat_hash_map with internal mutexes, for when
|
|
// we read/write the same parallel_flat_hash_map from multiple threads,
|
|
// without any special precautions.
|
|
// --------------------------------------------------------------------------
|
|
#define EXTRAARGS , NMSP::priv::hash_default_hash<K>, \
|
|
NMSP::priv::hash_default_eq<K>, \
|
|
std::allocator<std::pair<const K, V>>, 4, MTX
|
|
#else
|
|
#define EXTRAARGS
|
|
#endif
|
|
|
|
#endif
|
|
|
|
#define xstr(s) str(s)
|
|
#define str(s) #s
|
|
|
|
template <class K, class V>
|
|
using HashT = MAPNAME<K, V EXTRAARGS>;
|
|
|
|
using hash_t = HashT<int64_t, int64_t>;
|
|
using str_hash_t = HashT<const char *, int64_t>;
|
|
|
|
const char *program_slug = xstr(MAPNAME); // "_4";
|
|
|
|
#include <cassert>
|
|
#include <ctime>
|
|
#include <cstring>
|
|
#include <cstdlib>
|
|
#include <cstdio>
|
|
#include <cmath>
|
|
#include <thread>
|
|
#include <chrono>
|
|
#include <ostream>
|
|
#include "parallel_hashmap/meminfo.h"
|
|
#include <vector>
|
|
using std::vector;
|
|
|
|
int64_t _abs(int64_t x) { return (x < 0) ? -x : x; }
|
|
|
|
|
|
// --------------------------------------------------------------------------
|
|
class Timer
|
|
{
|
|
typedef std::chrono::high_resolution_clock high_resolution_clock;
|
|
typedef std::chrono::milliseconds milliseconds;
|
|
|
|
public:
|
|
explicit Timer(bool run = false) { if (run) reset(); }
|
|
void reset() { _start = high_resolution_clock::now(); }
|
|
|
|
milliseconds elapsed() const
|
|
{
|
|
return std::chrono::duration_cast<milliseconds>(high_resolution_clock::now() - _start);
|
|
}
|
|
|
|
private:
|
|
high_resolution_clock::time_point _start;
|
|
};
|
|
|
|
|
|
// --------------------------------------------------------------------------
|
|
// from: https://github.com/preshing/RandomSequence
|
|
// --------------------------------------------------------------------------
|
|
class RSU
|
|
{
|
|
private:
|
|
unsigned int m_index;
|
|
unsigned int m_intermediateOffset;
|
|
|
|
static unsigned int permuteQPR(unsigned int x)
|
|
{
|
|
static const unsigned int prime = 4294967291u;
|
|
if (x >= prime)
|
|
return x; // The 5 integers out of range are mapped to themselves.
|
|
unsigned int residue = ((unsigned long long) x * x) % prime;
|
|
return (x <= prime / 2) ? residue : prime - residue;
|
|
}
|
|
|
|
public:
|
|
RSU(unsigned int seedBase, unsigned int seedOffset)
|
|
{
|
|
m_index = permuteQPR(permuteQPR(seedBase) + 0x682f0161);
|
|
m_intermediateOffset = permuteQPR(permuteQPR(seedOffset) + 0x46790905);
|
|
}
|
|
|
|
unsigned int next()
|
|
{
|
|
return permuteQPR((permuteQPR(m_index++) + m_intermediateOffset) ^ 0x5bf03635);
|
|
}
|
|
};
|
|
|
|
// --------------------------------------------------------------------------
|
|
char * new_string_from_integer(int num)
|
|
{
|
|
int ndigits = num == 0 ? 1 : (int)log10(num) + 1;
|
|
char * str = (char *)malloc(ndigits + 1);
|
|
sprintf(str, "%d", num);
|
|
return str;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class T>
|
|
void _fill(vector<T> &v)
|
|
{
|
|
srand(1); // for a fair/deterministic comparison
|
|
for (size_t i = 0, sz = v.size(); i < sz; ++i)
|
|
v[i] = (T)(i * 10 + rand() % 10);
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class T>
|
|
void _shuffle(vector<T> &v)
|
|
{
|
|
for (size_t n = v.size(); n >= 2; --n)
|
|
std::swap(v[n - 1], v[static_cast<unsigned>(rand()) % n]);
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class T, class HT>
|
|
Timer _fill_random(vector<T> &v, HT &hash)
|
|
{
|
|
_fill<T>(v);
|
|
_shuffle<T>(v);
|
|
|
|
Timer timer(true);
|
|
|
|
for (size_t i = 0, sz = v.size(); i < sz; ++i)
|
|
hash.insert(typename HT::value_type(v[i], 0));
|
|
return timer;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
void out(const char* test, int64_t cnt, const Timer &t)
|
|
{
|
|
printf("%s,time,%lld,%s,%f\n", test, cnt, program_slug, (float)((double)t.elapsed().count() / 1000));
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
void outmem(const char* test, int64_t cnt, uint64_t mem)
|
|
{
|
|
printf("%s,memory,%lld,%s,%lld\n", test, cnt, program_slug, mem);
|
|
}
|
|
|
|
static bool all_done = false;
|
|
static int64_t num_keys[16] = { 0 };
|
|
static int64_t loop_idx = 0;
|
|
static int64_t inner_cnt = 0;
|
|
static const char *test = "random";
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class HT>
|
|
void _fill_random_inner(int64_t cnt, HT &hash, RSU &rsu)
|
|
{
|
|
for (int64_t i=0; i<cnt; ++i)
|
|
{
|
|
hash.insert(typename HT::value_type(rsu.next(), 0));
|
|
++num_keys[0];
|
|
}
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class HT>
|
|
void _fill_random_inner_mt(int64_t cnt, HT &hash, RSU &rsu)
|
|
{
|
|
constexpr int64_t num_threads = 8; // has to be a power of two
|
|
std::unique_ptr<std::thread> threads[num_threads];
|
|
|
|
auto thread_fn = [&hash, cnt, num_threads](int64_t thread_idx, RSU rsu) {
|
|
#if MT_SUPPORT
|
|
size_t modulo = hash.subcnt() / num_threads; // subcnt() returns the number of submaps
|
|
|
|
for (int64_t i=0; i<cnt; ++i) // iterate over all values
|
|
{
|
|
unsigned int key = rsu.next(); // get next key to insert
|
|
#if MT_SUPPORT == 1
|
|
size_t hashval = hash.hash(key); // compute its hash
|
|
size_t idx = hash.subidx(hashval); // compute the submap index for this hash
|
|
if (idx / modulo == thread_idx) // if the submap is suitable for this thread
|
|
#elif MT_SUPPORT == 2
|
|
if (i % num_threads == thread_idx)
|
|
#endif
|
|
{
|
|
hash.insert(typename HT::value_type(key, 0)); // insert the value
|
|
++(num_keys[thread_idx]); // increment count of inserted values
|
|
}
|
|
}
|
|
#endif
|
|
};
|
|
|
|
// create and start 8 threads - each will insert in their own submaps
|
|
// thread 0 will insert the keys whose hash direct them to submap0 or submap1
|
|
// thread 1 will insert the keys whose hash direct them to submap2 or submap3
|
|
// --------------------------------------------------------------------------
|
|
for (int64_t i=0; i<num_threads; ++i)
|
|
threads[i].reset(new std::thread(thread_fn, i, rsu));
|
|
|
|
// rsu passed by value to threads... we need to increment the reference object
|
|
for (int64_t i=0; i<cnt; ++i)
|
|
rsu.next();
|
|
|
|
// wait for the threads to finish their work and exit
|
|
for (int64_t i=0; i<num_threads; ++i)
|
|
threads[i]->join();
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
size_t total_num_keys()
|
|
{
|
|
size_t n = 0;
|
|
for (int i=0; i<16; ++i)
|
|
n += num_keys[i];
|
|
return n;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class HT>
|
|
Timer _fill_random2(int64_t cnt, HT &hash)
|
|
{
|
|
test = "random";
|
|
unsigned int seed = 76687;
|
|
RSU rsu(seed, seed + 1);
|
|
|
|
Timer timer(true);
|
|
const int64_t num_loops = 10;
|
|
inner_cnt = cnt / num_loops;
|
|
|
|
for (int i=0; i<16; ++i)
|
|
num_keys[i] = 0;
|
|
|
|
for (loop_idx=0; loop_idx<num_loops; ++loop_idx)
|
|
{
|
|
#if 1 && MT_SUPPORT
|
|
// multithreaded insert
|
|
_fill_random_inner_mt(inner_cnt, hash, rsu);
|
|
#else
|
|
_fill_random_inner(inner_cnt, hash, rsu);
|
|
#endif
|
|
out(test, total_num_keys(), timer);
|
|
}
|
|
fprintf(stderr, "inserted %.2lfM\n", (double)hash.size() / 1000000);
|
|
return timer;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class T, class HT>
|
|
Timer _lookup(vector<T> &v, HT &hash, size_t &num_present)
|
|
{
|
|
_fill_random(v, hash);
|
|
|
|
num_present = 0;
|
|
size_t max_val = v.size() * 10;
|
|
Timer timer(true);
|
|
|
|
for (size_t i = 0, sz = v.size(); i < sz; ++i)
|
|
{
|
|
num_present += (size_t)(hash.find(v[i]) != hash.end());
|
|
num_present += (size_t)(hash.find((T)(rand() % max_val)) != hash.end());
|
|
}
|
|
return timer;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
template <class T, class HT>
|
|
Timer _delete(vector<T> &v, HT &hash)
|
|
{
|
|
_fill_random(v, hash);
|
|
_shuffle(v); // don't delete in insertion order
|
|
|
|
Timer timer(true);
|
|
|
|
for(size_t i = 0, sz = v.size(); i < sz; ++i)
|
|
hash.erase(v[i]);
|
|
return timer;
|
|
}
|
|
|
|
// --------------------------------------------------------------------------
|
|
void memlog()
|
|
{
|
|
std::this_thread::sleep_for(std::chrono::milliseconds(10));
|
|
uint64_t nbytes_old_out = spp::GetProcessMemoryUsed();
|
|
uint64_t nbytes_old = spp::GetProcessMemoryUsed(); // last non outputted mem measurement
|
|
outmem(test, 0, nbytes_old);
|
|
int64_t last_loop = 0;
|
|
|
|
while (!all_done)
|
|
{
|
|
uint64_t nbytes = spp::GetProcessMemoryUsed();
|
|
|
|
if ((double)_abs(nbytes - nbytes_old_out) / nbytes_old_out > 0.03 ||
|
|
(double)_abs(nbytes - nbytes_old) / nbytes_old > 0.01)
|
|
{
|
|
if ((double)(nbytes - nbytes_old) / nbytes_old > 0.03)
|
|
outmem(test, total_num_keys() - 1, nbytes_old);
|
|
outmem(test, total_num_keys(), nbytes);
|
|
nbytes_old_out = nbytes;
|
|
last_loop = loop_idx;
|
|
}
|
|
else if (loop_idx > last_loop)
|
|
{
|
|
outmem(test, total_num_keys(), nbytes);
|
|
nbytes_old_out = nbytes;
|
|
last_loop = loop_idx;
|
|
}
|
|
nbytes_old = nbytes;
|
|
|
|
std::this_thread::sleep_for(std::chrono::milliseconds(1));
|
|
}
|
|
}
|
|
|
|
|
|
// --------------------------------------------------------------------------
|
|
int main(int argc, char ** argv)
|
|
{
|
|
int64_t i, value = 0;
|
|
|
|
if(argc <= 2)
|
|
return 1;
|
|
|
|
int64_t num_keys = atoi(argv[1]);
|
|
|
|
hash_t hash;
|
|
str_hash_t str_hash;
|
|
|
|
srand(1); // for a fair/deterministic comparison
|
|
Timer timer(true);
|
|
|
|
#if MT_SUPPORT
|
|
if (!strcmp(program_slug,"absl::parallel_flat_hash_map") ||
|
|
!strcmp(program_slug,"phmap::parallel_flat_hash_map"))
|
|
program_slug = xstr(MAPNAME) "_mt";
|
|
#endif
|
|
|
|
std::thread t1(memlog);
|
|
|
|
try
|
|
{
|
|
if(!strcmp(argv[2], "sequential"))
|
|
{
|
|
for(i = 0; i < num_keys; i++)
|
|
hash.insert(hash_t::value_type(i, value));
|
|
}
|
|
#if 0
|
|
else if(!strcmp(argv[2], "random"))
|
|
{
|
|
vector<int64_t> v(num_keys);
|
|
timer = _fill_random(v, hash);
|
|
out("random", num_keys, timer);
|
|
}
|
|
#endif
|
|
else if(!strcmp(argv[2], "random"))
|
|
{
|
|
fprintf(stderr, "size = %d\n", sizeof(hash));
|
|
timer = _fill_random2(num_keys, hash);
|
|
//out("random", num_keys, timer);
|
|
//fprintf(stderr, "inserted %llu\n", hash.size());
|
|
}
|
|
else if(!strcmp(argv[2], "lookup"))
|
|
{
|
|
vector<int64_t> v(num_keys);
|
|
size_t num_present;
|
|
|
|
timer = _lookup(v, hash, num_present);
|
|
//fprintf(stderr, "found %llu\n", num_present);
|
|
}
|
|
else if(!strcmp(argv[2], "delete"))
|
|
{
|
|
vector<int64_t> v(num_keys);
|
|
timer = _delete(v, hash);
|
|
}
|
|
else if(!strcmp(argv[2], "sequentialstring"))
|
|
{
|
|
for(i = 0; i < num_keys; i++)
|
|
str_hash.insert(str_hash_t::value_type(new_string_from_integer(i), value));
|
|
}
|
|
else if(!strcmp(argv[2], "randomstring"))
|
|
{
|
|
for(i = 0; i < num_keys; i++)
|
|
str_hash.insert(str_hash_t::value_type(new_string_from_integer((int)rand()), value));
|
|
}
|
|
else if(!strcmp(argv[2], "deletestring"))
|
|
{
|
|
for(i = 0; i < num_keys; i++)
|
|
str_hash.insert(str_hash_t::value_type(new_string_from_integer(i), value));
|
|
timer.reset();
|
|
for(i = 0; i < num_keys; i++)
|
|
str_hash.erase(new_string_from_integer(i));
|
|
}
|
|
|
|
|
|
//printf("%f\n", (float)((double)timer.elapsed().count() / 1000));
|
|
fflush(stdout);
|
|
//std::this_thread::sleep_for(std::chrono::seconds(1000));
|
|
}
|
|
catch (...)
|
|
{
|
|
}
|
|
|
|
all_done = true;
|
|
t1.join();
|
|
return 0;
|
|
}
|