Task 1 (Lockfree Multivalue Hashmap) Assignment

Scaffold Head

#include <algorithm> #include <iostream> #include <cstdint> #include <vector> #include <atomic> #include <limits> #include "include/hpc_helpers.hpp" struct murmur_integer_finalizer_hash_uint32_t { // this hash function is magic, nobody knows why uint32_t operator() ( uint32_t x) const { x ^= x >> 16; x *= 0x85ebca6b; x ^= x >> 13; x *= 0xc2b2ae35; x ^= x >> 16; return x; } }; template < typename key_t, typename val_t> struct entry_t { // empty key is encoded as 11111111...1 static constexpr key_t empty_key = std::numeric_limits<key_t>::max(); static constexpr val_t empty_val = std::numeric_limits<val_t>::max(); key_t key; val_t val; void set ( const key_t& key_, const key_t& val_) { key = key_; val = val_; } void set_empty () { set(empty_key, empty_val); } }; template < typename key_t, // data type for keys typename val_t, // data type for values typename fun_t> // hash function acting on keys struct hashmap_t { typedef entry_t<key_t, val_t> slot_t; const uint64_t capacity, num_probes; const fun_t hash_function; std::atomic<slot_t> * slots; hashmap_t ( uint64_t capacity_, fun_t hash_function_) : capacity (capacity_), num_probes (capacity_), hash_function(hash_function_) { // create array of atomic slots slots = new std::atomic<slot_t>[capacity]; // prepare empty slot for initialization slot_t empty_slot; empty_slot.set_empty(); // initialize them with empty slots for (uint64_t index = 0; index < capacity; index++) slots[index].store(empty_slot); } ~hashmap_t () { delete [] slots; } bool is_lock_free () { return slots[0].is_lock_free(); }

Scaffold Foot

std::vector<val_t> query ( key_t key) const { // here we store the values std::vector<val_t> values; // you cannot insert empty keys if (key == slot_t::empty_key) return values; // traverse the probing sequence until you hit an empty slot const uint64_t offset = hash_function(key); for (uint64_t probe = 0; probe < num_probes; probe++) { // linear probing scheme const uint64_t index = (offset+probe) % capacity; // here we can read using relaxed memory order since there no // causal dependencies between individual accesses const slot_t slot = slots[index].load(std::memory_order_relaxed); if (slot.key == key) values.push_back(slot.val); if (slot.key == slot_t::empty_key) { std::sort(values.begin(), values.end()); return values; } } std::sort(values.begin(), values.end()); return values; } }; int main () { typedef uint32_t key_t; typedef uint32_t val_t; const uint64_t capacity = 1UL << 5; murmur_integer_finalizer_hash_uint32_t hash; hashmap_t<key_t, val_t, decltype(hash)> hashmap(capacity, hash); if(!hashmap.is_lock_free()) std::cout << "WARNING: Using slow mutexes!" << std::endl; TIMERSTART(insert) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) if(!hashmap.insert(index, index)) std::cout << "ERROR: Insertion failure: " << index << std::endl; TIMERSTOP(insert) TIMERSTART(update) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) if(!hashmap.insert(index, index+1)) std::cout << "ERROR: Insertion failure: " << index << std::endl; TIMERSTOP(update) TIMERSTART(query_existing_keys) # pragma omp parallel for for (uint64_t index = 0; index < capacity*19/40; index++) { const auto& result = hashmap.query(index); if (!(result.size() == 2 && result[0] == std::min(val_t(index), val_t(index+1)) && result[1] == std::max(val_t(index), val_t(index+1)))) std::cout << "ERROR: Query failure: " << index << std::endl; } TIMERSTOP(query_existing_keys) TIMERSTART(query_nonexisting_keys) # pragma omp parallel for for (uint64_t index = capacity*19/40; index < capacity; index++) { const auto& result = hashmap.query(index); if (result.size()) std::cout << "ERROR: Query failure: " << index << std::endl; } TIMERSTOP(query_nonexisting_keys) std::cout << "Parallel programming is fun!" << std::endl; }

Start time:

Do 09 Jan 2020 12:00:00

End time:

Mi 15 Jan 2020 11:00:00

General test timeout:

10.0 seconds

Tests

Parallel programming is fun!