// AtomicHashArray private constructor --
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
AtomicHashArray(size_t capacity, KeyT emptyKey, KeyT lockedKey,
KeyT erasedKey, double _maxLoadFactor, size_t cacheSize)
: capacity_(capacity),
* ret.index is set to capacity_.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
findInternal(const KeyT key_in) {
DCHECK_NE(key_in, kEmptyKey_);
DCHECK_NE(key_in, kLockedKey_);
DCHECK_NE(key_in, kErasedKey_);
for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
;
- idx = probeNext(idx, numProbes)) {
+ idx = ProbeFcn()(idx, numProbes, capacity_)) {
const KeyT key = acquireLoadKey(cells_[idx]);
if (LIKELY(EqualFcn()(key, key_in))) {
return SimpleRetT(idx, true);
// if we hit an empty element, this key does not exist
return SimpleRetT(capacity_, false);
}
+ // NOTE: the way we count numProbes must be same in find(), insert(),
+ // and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
* default.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
template <typename... ArgTs>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SimpleRetT
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
insertInternal(KeyT key_in, ArgTs&&... vCtorArgs) {
const short NO_NEW_INSERTS = 1;
const short NO_PENDING_INSERTS = 2;
continue;
}
+
+ // NOTE: the way we count numProbes must be same in find(),
+ // insert(), and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
return SimpleRetT(capacity_, false);
}
- idx = probeNext(idx, numProbes);
+ idx = ProbeFcn()(idx, numProbes, capacity_);
}
}
* touch it either.
*/
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+size_t AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
erase(KeyT key_in) {
CHECK_NE(key_in, kEmptyKey_);
CHECK_NE(key_in, kLockedKey_);
CHECK_NE(key_in, kErasedKey_);
+
for (size_t idx = keyToAnchorIdx(key_in), numProbes = 0;
;
- idx = probeNext(idx, numProbes)) {
+ idx = ProbeFcn()(idx, numProbes, capacity_)) {
DCHECK_LT(idx, capacity_);
value_type* cell = &cells_[idx];
KeyT currentKey = acquireLoadKey(*cell);
// If another thread succeeds in erasing our key, we'll stop our search.
return 0;
}
+
+ // NOTE: the way we count numProbes must be same in find(), insert(),
+ // and erase(). Otherwise it may break probing.
++numProbes;
if (UNLIKELY(numProbes >= capacity_)) {
// probed every cell...fail
}
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
typename AtomicHashArray<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::SmartPtr
-AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::SmartPtr
+AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
create(size_t maxSize, const Config& c) {
CHECK_LE(c.maxLoadFactor, 1.0);
CHECK_GT(c.maxLoadFactor, 0.0);
}
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
destroy(AtomicHashArray* p) {
assert(p);
// clear -- clears all keys and values in the map and resets all counters
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
-void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
+void AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
clear() {
FOR_EACH_RANGE(i, 0, capacity_) {
if (cells_[i].first != kEmptyKey_) {
// Iterator implementation
template <class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
template <class ContT, class IterVal>
-struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::aha_iterator
+struct AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ aha_iterator
: boost::iterator_facade<aha_iterator<ContT,IterVal>,
IterVal,
boost::forward_traversal_tag>
namespace folly {
+struct AtomicHashArrayLinearProbeFcn
+{
+ inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
+ idx += 1; // linear probing
+
+ // Avoid modulus because it's slow
+ return LIKELY(idx < capacity) ? idx : (idx - capacity);
+ }
+};
+
+struct AtomicHashArrayQuadraticProbeFcn
+{
+ inline size_t operator()(size_t idx, size_t numProbes, size_t capacity) const{
+ idx += numProbes; // quadratic probing
+
+ // Avoid modulus because it's slow
+ return LIKELY(idx < capacity) ? idx : (idx - capacity);
+ }
+};
+
template <class KeyT, class ValueT,
class HashFcn = std::hash<KeyT>,
class EqualFcn = std::equal_to<KeyT>,
- class Allocator = std::allocator<char>>
+ class Allocator = std::allocator<char>,
+ class ProbeFcn = AtomicHashArrayLinearProbeFcn>
class AtomicHashMap;
template <class KeyT, class ValueT,
class HashFcn = std::hash<KeyT>,
class EqualFcn = std::equal_to<KeyT>,
- class Allocator = std::allocator<char>>
+ class Allocator = std::allocator<char>,
+ class ProbeFcn = AtomicHashArrayLinearProbeFcn>
class AtomicHashArray : boost::noncopyable {
static_assert((std::is_convertible<KeyT,int32_t>::value ||
std::is_convertible<KeyT,int64_t>::value ||
/* Private data and helper functions... */
private:
- friend class AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>;
+friend class AtomicHashMap<KeyT,
+ ValueT,
+ HashFcn,
+ EqualFcn,
+ Allocator,
+ ProbeFcn>;
struct SimpleRetT { size_t idx; bool success;
SimpleRetT(size_t i, bool s) : idx(i), success(s) {}
SimpleRetT() = default;
};
+
+
template <typename... ArgTs>
SimpleRetT insertInternal(KeyT key, ArgTs&&... vCtorArgs);
return LIKELY(probe < capacity_) ? probe : hashVal % capacity_;
}
- inline size_t probeNext(size_t idx, size_t /*numProbes*/) {
- //idx += numProbes; // quadratic probing
- idx += 1; // linear probing
- // Avoid modulus because it's slow
- return LIKELY(idx < capacity_) ? idx : (idx - capacity_);
- }
+
}; // AtomicHashArray
} // namespace folly
// AtomicHashMap constructor -- Atomic wrapper that allows growth
// This class has a lot of overhead (184 Bytes) so only use for big maps
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
AtomicHashMap(size_t finalSizeEst, const Config& config)
: kGrowthFrac_(config.growthFactor < 0 ?
1.0 - config.maxLoadFactor : config.growthFactor) {
}
// emplace --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
template <typename... ArgTs>
std::pair<typename AtomicHashMap<KeyT, ValueT, HashFcn,
- EqualFcn, Allocator>::iterator, bool>
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ EqualFcn, Allocator, ProbeFcn>::iterator, bool>
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
emplace(key_type k, ArgTs&&... vCtorArgs) {
SimpleRetT ret = insertInternal(k, std::forward<ArgTs>(vCtorArgs)...);
SubMap* subMap = subMaps_[ret.i].load(std::memory_order_relaxed);
}
// insertInternal -- Allocates new sub maps as existing ones fill up.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
template <typename... ArgTs>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
insertInternal(key_type key, ArgTs&&... vCtorArgs) {
beginInsertInternal:
auto nextMapIdx = // this maintains our state
}
// find --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-find(KeyT k) {
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::find(
+ KeyT k) {
SimpleRetT ret = findInternal(k);
if (!ret.success) {
return end();
return iterator(this, ret.i, subMap->makeIter(ret.j));
}
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
typename AtomicHashMap<KeyT, ValueT,
- HashFcn, EqualFcn, Allocator>::const_iterator
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+ HashFcn, EqualFcn, Allocator, ProbeFcn>::const_iterator
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
find(KeyT k) const {
return const_cast<AtomicHashMap*>(this)->find(k);
}
// findInternal --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-findInternal(const KeyT k) const {
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ findInternal(const KeyT k) const {
SubMap* const primaryMap = subMaps_[0].load(std::memory_order_relaxed);
typename SubMap::SimpleRetT ret = primaryMap->findInternal(k);
if (LIKELY(ret.idx != primaryMap->capacity_)) {
}
// findAtInternal -- see encodeIndex() for details.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::SimpleRetT
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ SimpleRetT
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
findAtInternal(uint32_t idx) const {
uint32_t subMapIdx, subMapOffset;
if (idx & kSecondaryMapBit_) {
}
// erase --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::size_type
-AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+typename AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ size_type
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
erase(const KeyT k) {
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
FOR_EACH_RANGE(i, 0, numMaps) {
}
// capacity -- summation of capacities of all submaps
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
capacity() const {
size_t totalCap(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// spaceRemaining --
// number of new insertions until current submaps are all at max load
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
spaceRemaining() const {
size_t spaceRem(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// clear -- Wipes all keys and values from primary map and destroys
// all secondary maps. Not thread safe.
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+void AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
clear() {
subMaps_[0].load(std::memory_order_relaxed)->clear();
int const numMaps = numMapsAllocated_
}
// size --
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+size_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
size() const {
size_t totalSize(0);
int const numMaps = numMapsAllocated_.load(std::memory_order_acquire);
// 31 1
// 27-30 which subMap
// 0-26 subMap offset (index_ret input)
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-inline uint32_t AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::
-encodeIndex(uint32_t subMap, uint32_t offset) {
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+inline uint32_t
+AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ encodeIndex(uint32_t subMap, uint32_t offset) {
DCHECK_EQ(offset & kSecondaryMapBit_, 0); // offset can't be too big
if (subMap == 0) return offset;
// Make sure subMap isn't too big
// Iterator implementation
-template <typename KeyT, typename ValueT,
- typename HashFcn, typename EqualFcn, typename Allocator>
-template<class ContT, class IterVal, class SubIt>
-struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator>::ahm_iterator
- : boost::iterator_facade<ahm_iterator<ContT,IterVal,SubIt>,
- IterVal,
- boost::forward_traversal_tag>
-{
+template <typename KeyT,
+ typename ValueT,
+ typename HashFcn,
+ typename EqualFcn,
+ typename Allocator,
+ typename ProbeFcn>
+template <class ContT, class IterVal, class SubIt>
+struct AtomicHashMap<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>::
+ ahm_iterator : boost::iterator_facade<ahm_iterator<ContT, IterVal, SubIt>,
+ IterVal,
+ boost::forward_traversal_tag> {
explicit ahm_iterator() : ahm_(0) {}
// Conversion ctor for interoperability between const_iterator and
};
template<class KeyT, class ValueT,
- class HashFcn, class EqualFcn, class Allocator>
+ class HashFcn, class EqualFcn, class Allocator, class ProbeFcn>
class AtomicHashMap : boost::noncopyable {
- typedef AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator> SubMap;
+typedef AtomicHashArray<KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn>
+ SubMap;
public:
typedef KeyT key_type;
}; // AtomicHashMap
+template <class KeyT,
+ class ValueT,
+ class HashFcn = std::hash<KeyT>,
+ class EqualFcn = std::equal_to<KeyT>,
+ class Allocator = std::allocator<char>>
+using QuadraticProbingAtomicHashMap =
+ AtomicHashMap<KeyT,
+ ValueT,
+ HashFcn,
+ EqualFcn,
+ Allocator,
+ AtomicHashArrayQuadraticProbeFcn>;
} // namespace folly
#include <folly/AtomicHashMap-inl.h>
to<ValueT>(i + 3));
}
-template<class KeyT, class ValueT, class Allocator = std::allocator<char>>
+template <class KeyT,
+ class ValueT,
+ class Allocator = std::allocator<char>,
+ class ProbeFcn = AtomicHashArrayLinearProbeFcn>
void testMap() {
typedef AtomicHashArray<KeyT, ValueT, std::hash<KeyT>,
- std::equal_to<KeyT>, Allocator> MyArr;
+ std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
auto arr = MyArr::create(150);
map<KeyT, ValueT> ref;
for (int i = 0; i < 100; ++i) {
}
}
-template<class KeyT, class ValueT, class Allocator = std::allocator<char>>
+template<class KeyT, class ValueT,
+ class Allocator = std::allocator<char>,
+ class ProbeFcn = AtomicHashArrayLinearProbeFcn>
void testNoncopyableMap() {
typedef AtomicHashArray<KeyT, std::unique_ptr<ValueT>, std::hash<KeyT>,
- std::equal_to<KeyT>, Allocator> MyArr;
+ std::equal_to<KeyT>, Allocator, ProbeFcn> MyArr;
+
auto arr = MyArr::create(250);
for (int i = 0; i < 100; i++) {
arr->insert(make_pair(i,std::unique_ptr<ValueT>(new ValueT(i))));
TEST(Aha, InsertErase_i32_i32) {
testMap<int32_t, int32_t>();
testMap<int32_t, int32_t, MmapAllocator<char>>();
+ testMap<int32_t, int32_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int32_t, int32_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
testNoncopyableMap<int32_t, int32_t>();
testNoncopyableMap<int32_t, int32_t, MmapAllocator<char>>();
+ testNoncopyableMap<int32_t, int32_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testNoncopyableMap<int32_t, int32_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, InsertErase_i64_i32) {
testMap<int64_t, int32_t>();
testMap<int64_t, int32_t, MmapAllocator<char>>();
+ testMap<int64_t, int32_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int64_t, int32_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
testNoncopyableMap<int64_t, int32_t>();
testNoncopyableMap<int64_t, int32_t, MmapAllocator<char>>();
+ testNoncopyableMap<int64_t, int32_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testNoncopyableMap<int64_t, int32_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, InsertErase_i64_i64) {
testMap<int64_t, int64_t>();
testMap<int64_t, int64_t, MmapAllocator<char>>();
+ testMap<int64_t, int64_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int64_t, int64_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
testNoncopyableMap<int64_t, int64_t>();
testNoncopyableMap<int64_t, int64_t, MmapAllocator<char>>();
+ testNoncopyableMap<int64_t, int64_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testNoncopyableMap<int64_t, int64_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, InsertErase_i32_i64) {
testMap<int32_t, int64_t>();
testMap<int32_t, int64_t, MmapAllocator<char>>();
+ testMap<int32_t, int64_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int32_t, int64_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
testNoncopyableMap<int32_t, int64_t>();
testNoncopyableMap<int32_t, int64_t, MmapAllocator<char>>();
+ testNoncopyableMap<int32_t, int64_t,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testNoncopyableMap<int32_t, int64_t,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, InsertErase_i32_str) {
testMap<int32_t, string>();
testMap<int32_t, string, MmapAllocator<char>>();
+ testMap<int32_t, string,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int32_t, string,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, InsertErase_i64_str) {
testMap<int64_t, string>();
testMap<int64_t, string, MmapAllocator<char>>();
+ testMap<int64_t, string,
+ std::allocator<char>, AtomicHashArrayQuadraticProbeFcn>();
+ testMap<int64_t, string,
+ MmapAllocator<char>, AtomicHashArrayQuadraticProbeFcn>();
}
TEST(Aha, Create_cstr_i64) {
typedef AtomicHashMap<KeyT,ValueT> AHMapT;
typedef AHMapT::value_type RecordT;
typedef AtomicHashArray<KeyT,ValueT> AHArrayT;
-
AHArrayT::Config config;
+typedef folly::QuadraticProbingAtomicHashMap<KeyT,ValueT> QPAHMapT;
+QPAHMapT::Config qpConfig;
static AHArrayT::SmartPtr globalAHA(nullptr);
static std::unique_ptr<AHMapT> globalAHM;
+static std::unique_ptr<QPAHMapT> globalQPAHM;
// Generate a deterministic value based on an input key
static int genVal(int key) {
return nullptr;
}
+void* qpInsertThread(void* jj) {
+ int64_t j = (int64_t) jj;
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ globalQPAHM->insert(key, genVal(key));
+ }
+ return nullptr;
+}
+
void* insertThreadArr(void* jj) {
int64_t j = (int64_t) jj;
for (int i = 0; i < numOpsPerThread; ++i) {
EXPECT_EQ(globalAHM->size(), FLAGS_numBMElements);
}
+void loadGlobalQPAhm() {
+ std::cout << "loading global QPAHM with " << FLAGS_numThreads
+ << " threads...\n";
+ uint64_t start = nowInUsec();
+ globalQPAHM.reset(new QPAHMapT(maxBMElements, qpConfig));
+ numOpsPerThread = FLAGS_numBMElements / FLAGS_numThreads;
+ runThreads(qpInsertThread);
+ uint64_t elapsed = nowInUsec() - start;
+ std::cout << " took " << elapsed / 1000 << " ms (" <<
+ (elapsed * 1000 / FLAGS_numBMElements) << " ns/insert).\n";
+ EXPECT_EQ(globalQPAHM->size(), FLAGS_numBMElements);
+}
+
}
BENCHMARK(st_aha_find, iters) {
}
}
+BENCHMARK(st_qpahm_find, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ }
+}
+
BENCHMARK_DRAW_LINE()
BENCHMARK(mt_ahm_miss, iters) {
});
}
+BENCHMARK(mt_qpahm_miss, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = i + j * numOpsPerThread * 100;
+ folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
+ }
+ return nullptr;
+ });
+}
+
BENCHMARK(st_ahm_miss, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
for (size_t i = 0; i < iters; i++) {
}
}
+BENCHMARK(st_qpahm_miss, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i + iters * 100);
+ folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
+ }
+}
+
BENCHMARK(mt_ahm_find_insert_mix, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
numOpsPerThread = iters / FLAGS_numThreads;
});
}
+
+BENCHMARK(mt_qpahm_find_insert_mix, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ if (i % 128) { // ~1% insert mix
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ } else {
+ KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
+ globalQPAHM->insert(key, genVal(key));
+ }
+ }
+ return nullptr;
+ });
+}
+
BENCHMARK(mt_aha_find, iters) {
CHECK_LE(iters, FLAGS_numBMElements);
numOpsPerThread = iters / FLAGS_numThreads;
});
}
+BENCHMARK(mt_qpahm_find, iters) {
+ CHECK_LE(iters, FLAGS_numBMElements);
+ numOpsPerThread = iters / FLAGS_numThreads;
+ runThreads([](void* jj) -> void* {
+ int64_t j = (int64_t) jj;
+ while (!runThreadsCreatedAllThreads.load());
+ for (int i = 0; i < numOpsPerThread; ++i) {
+ KeyT key = randomizeKey(i + j * numOpsPerThread);
+ folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
+ }
+ return nullptr;
+ });
+}
+
KeyT k;
BENCHMARK(st_baseline_modulus_and_random, iters) {
for (size_t i = 0; i < iters; ++i) {
runThreads(insertThread);
}
+BENCHMARK(mt_qpahm_insert, iters) {
+ BENCHMARK_SUSPEND {
+ globalQPAHM.reset(new QPAHMapT(int(iters * LF), qpConfig));
+ numOpsPerThread = iters / FLAGS_numThreads;
+ }
+ runThreads(qpInsertThread);
+}
+
BENCHMARK(st_ahm_insert, iters) {
folly::BenchmarkSuspender susp;
std::unique_ptr<AHMapT> ahm(new AHMapT(int(iters * LF), config));
}
}
+BENCHMARK(st_qpahm_insert, iters) {
+ folly::BenchmarkSuspender susp;
+ std::unique_ptr<QPAHMapT> ahm(new QPAHMapT(int(iters * LF), qpConfig));
+ susp.dismiss();
+
+ for (size_t i = 0; i < iters; i++) {
+ KeyT key = randomizeKey(i);
+ ahm->insert(key, genVal(key));
+ }
+}
+
void benchmarkSetup() {
config.maxLoadFactor = FLAGS_maxLoadFactor;
+ qpConfig.maxLoadFactor = FLAGS_maxLoadFactor;
configRace.maxLoadFactor = 0.5;
int numCores = sysconf(_SC_NPROCESSORS_ONLN);
loadGlobalAha();
loadGlobalAhm();
+ loadGlobalQPAhm();
string numIters = folly::to<string>(
std::min(1000000, int(FLAGS_numBMElements)));
}
/*
-Benchmarks run on dual Xeon X5650's @ 2.67GHz w/hyperthreading enabled
- (12 physical cores, 12 MB cache, 72 GB RAM)
+loading global AHA with 8 threads...
+ took 487 ms (40 ns/insert).
+loading global AHM with 8 threads...
+ took 478 ms (39 ns/insert).
+loading global QPAHM with 8 threads...
+ took 478 ms (39 ns/insert).
Running AHM benchmarks on machine with 24 logical cores.
num elements per map: 12000000
num threads for mt tests: 24
AHM load factor: 0.75
-Benchmark Iters Total t t/iter iter/sec
-------------------------------------------------------------------------------
-Comparing benchmarks: BM_mt_aha_find,BM_mt_ahm_find
-* BM_mt_aha_find 1000000 7.767 ms 7.767 ns 122.8 M
- +0.81% BM_mt_ahm_find 1000000 7.83 ms 7.83 ns 121.8 M
-------------------------------------------------------------------------------
-Comparing benchmarks: BM_st_aha_find,BM_st_ahm_find
-* BM_st_aha_find 1000000 57.83 ms 57.83 ns 16.49 M
- +77.9% BM_st_ahm_find 1000000 102.9 ms 102.9 ns 9.27 M
-------------------------------------------------------------------------------
-BM_mt_ahm_miss 1000000 2.937 ms 2.937 ns 324.7 M
-BM_st_ahm_miss 1000000 164.2 ms 164.2 ns 5.807 M
-BM_mt_ahm_find_insert_mix 1000000 8.797 ms 8.797 ns 108.4 M
-BM_mt_ahm_insert 1000000 17.39 ms 17.39 ns 54.83 M
-BM_st_ahm_insert 1000000 106.8 ms 106.8 ns 8.93 M
-BM_st_baseline_modulus_and_rando 1000000 6.223 ms 6.223 ns 153.2 M
+============================================================================
+folly/test/AtomicHashMapTest.cpp relative time/iter iters/s
+============================================================================
+st_aha_find 92.63ns 10.80M
+st_ahm_find 107.78ns 9.28M
+st_qpahm_find 90.69ns 11.03M
+----------------------------------------------------------------------------
+mt_ahm_miss 2.09ns 477.36M
+mt_qpahm_miss 1.37ns 728.82M
+st_ahm_miss 241.07ns 4.15M
+st_qpahm_miss 223.17ns 4.48M
+mt_ahm_find_insert_mix 8.05ns 124.24M
+mt_qpahm_find_insert_mix 9.10ns 109.85M
+mt_aha_find 6.82ns 146.68M
+mt_ahm_find 7.95ns 125.77M
+mt_qpahm_find 6.81ns 146.83M
+st_baseline_modulus_and_random 6.02ns 166.03M
+mt_ahm_insert 14.29ns 69.97M
+mt_qpahm_insert 11.68ns 85.61M
+st_ahm_insert 125.39ns 7.98M
+st_qpahm_insert 128.76ns 7.77M
+============================================================================
*/
projects / folly.git / commitdiff