/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <cstddef>
#include <functional>
#include <map>
#include <string>
#include <unordered_map>
#include <glog/logging.h>
#include <folly/Benchmark.h>
#include <folly/Conv.h>
#include <folly/Format.h>
#include <folly/Function.h>
#include <folly/hash/Hash.h>
#include <folly/init/Init.h>
#include <folly/portability/GFlags.h>
#include <folly/container/F14Map.h>
using namespace folly;
// Depending the max load factor and the rehashing policy, the map size could
// affect benchmark results quite a bit. For example, a map that's just rehashed
// could have a lower probability of collisions, but the rehash time would get
// counted toward the operation that triggered the rehash.
DEFINE_int32(
map_size_min,
11,
"min number of entries to benchmark each map with (inclusive)");
DEFINE_int32(
map_size_max,
100000,
"max number of entries to benchmark each map with (inclusive)");
DEFINE_int32(
map_size_step, 32, "multiplier for each benchmark between iterations");
//////// Key related preparation ////////
namespace {
static const std::string kPadding("0123456789012345678901234567890123");
struct NonSSOString : public std::string {
template <typename... Args>
explicit NonSSOString(Args&&... args)
: std::string(std::string(std::forward<Args>(args)...) + kPadding) {}
NonSSOString(NonSSOString const&) = default;
NonSSOString& operator=(NonSSOString const&) = default;
NonSSOString(NonSSOString&&) = default;
NonSSOString& operator=(NonSSOString&&) = default;
};
} // namespace
namespace std {
template <>
struct hash<NonSSOString> {
size_t operator()(const NonSSOString& s) const { return hash<string>()(s); }
};
template <>
struct __is_fast_hash<hash<NonSSOString>> : public std::false_type {};
static_assert(
__cache_default<string, hash<string>>::value ==
__cache_default<NonSSOString, hash<NonSSOString>>::value,
"To draw a fair comparison, the policy of whether to cache hash codes "
"for NonSSOString keys should be the same as for std::string keys.");
} // namespace std
namespace folly {
template <typename K>
struct IsAvalanchingHasher<std::hash<NonSSOString>, K> : std::true_type {};
} // namespace folly
const int kSalt = 0x619abc7e;
template <typename K>
K keyGen(uint32_t key) {
return folly::to<K>(hash::jenkins_rev_mix32(key ^ kSalt));
}
template <>
NonSSOString keyGen<NonSSOString>(uint32_t key) {
return NonSSOString(to<std::string>(key));
}
template <class K>
std::vector<K>& keyList(int /*max*/ = 0) {
static std::vector<K> keys;
return keys;
}
template <class K>
void prepare(size_t max) {
auto& keys = keyList<K>();
if (keys.size() < max) {
for (auto key = keys.size(); key < max; ++key) {
keys.push_back(keyGen<K>(key));
}
}
}
template <class K>
const K& key(int index) {
return keyList<K>()[index];
}
template <typename TArray>
TArray value(int i) {
// quick and dirty hack, since we don't test for correctness, ignore any
// narrowing that might happen.
return {static_cast<typename TArray::value_type>(i)};
}
template <template <class, class> class Map, class K, class V, class Test>
void benchmarkFilledMap(int runs, int size, const Test& test, int div = 1) {
BenchmarkSuspender braces;
Map<K, V> map(size);
prepare<K>(size);
for (int i = 0; i < size; i += div) {
auto& k = key<K>(i);
map.insert(std::pair<K, V>(k, value<V>(i * 3)));
}
folly::makeUnpredictable(map);
braces.dismissing([&] {
for (int r = 0; r < runs; ++r) {
test(map);
}
});
}
template <template <class, class> class Map, class K, class V, class Test>
void benchmarkManyFilledMapsByKey(
int runs, int size, const Test& test, int div = 1) {
BenchmarkSuspender braces;
Map<K, V> maps[64];
std::vector<K> toInsert;
prepare<K>(size);
for (int i = 0; i < size; ++i) {
auto& k = key<K>(i);
toInsert.push_back(k);
}
for (int i = 0; i * div < size; ++i) {
maps[i % 64].insert(std::pair<K, V>(toInsert[i], value<V>(i * 3)));
}
std::random_shuffle(toInsert.begin(), toInsert.end());
folly::makeUnpredictable(maps);
folly::makeUnpredictable(toInsert);
braces.dismissing([&] {
for (int r = 0; r < runs; ++r) {
for (int i = 0; i < size; i += div) {
test(maps[i % 64], toInsert[i]);
}
}
});
}
template <template <class, class> class Map, class K, class V, class Test>
void benchmarkFilledMapByKey(
int runs, int size, const Test& test, int div = 1) {
BenchmarkSuspender braces;
Map<K, V> map(size);
std::vector<K> toInsert;
prepare<K>(size);
for (int i = 0; i < size; ++i) {
auto& k = key<K>(i);
toInsert.push_back(k);
}
for (int i = 0; i * div < size; ++i) {
map.insert(std::pair<K, V>(toInsert[i], value<V>(i * 3)));
}
std::random_shuffle(toInsert.begin(), toInsert.end());
folly::makeUnpredictable(map);
folly::makeUnpredictable(toInsert);
braces.dismissing([&] {
for (int r = 0; r < runs; ++r) {
for (int i = 0; i < size; i += div) {
test(map, toInsert[i]);
}
}
});
}
template <
template <class, class>
class Map,
class K,
class V,
class... Args,
class Test>
void benchmarkFromEmptyArgs(int runs, int size, Test test, Args... args) {
BenchmarkSuspender braces;
prepare<K>(size);
for (int r = 0; r < runs; ++r) {
Map<K, V> map{args...};
folly::makeUnpredictable(map);
braces.dismissing([&] {
for (int i = 0; i < size; ++i) {
test(map, i);
}
});
}
}
template <template <class, class> class Map, class K, class V>
void benchmarkInsert(int runs, int size) {
benchmarkFromEmptyArgs<Map, K, V>(
runs,
size,
[](Map<K, V>& m, int i) {
m.insert(std::pair<K, V>(key<K>(i), value<V>(i)));
},
unsigned(size));
}
template <template <class, class> class Map, class K, class V>
void benchmarkInsertGrow(int runs, int size) {
benchmarkFromEmptyArgs<Map, K, V>(runs, size, [](Map<K, V>& m, int i) {
m.insert(std::pair<K, V>(key<K>(i), value<V>(i)));
});
}
template <template <class, class> class Map, class K, class V>
void benchmarkInsertSqBr(int runs, int size) {
benchmarkFromEmptyArgs<Map, K, V>(
runs, size, [](Map<K, V>& m, int i) { m[key<K>(i)] = value<V>(i); });
}
template <template <class, class> class Map, class K, class V>
void benchmarkFind(int runs, int size) {
int x = 0;
benchmarkFilledMapByKey<Map, K, V>(
runs,
size,
[&](Map<K, V>& m, const K& key) {
auto found = m.find(key);
if (found != m.end()) {
x ^= found->second[0];
folly::doNotOptimizeAway(x);
}
},
2);
}
template <template <class, class> class Map, class K, class V>
void benchmarkManyFind(int runs, int size) {
int x = 0;
benchmarkManyFilledMapsByKey<Map, K, V>(
runs,
size,
[&](Map<K, V>& m, const K& key) {
auto found = m.find(key);
if (found != m.end()) {
x ^= found->second[0];
folly::doNotOptimizeAway(x);
}
},
2);
}
template <template <class, class> class Map, class K, class V>
void benchmarkSqBrFind(int runs, int size) {
int x = 0;
benchmarkFilledMapByKey<Map, K, V>(
runs,
size,
[&](Map<K, V>& m, const K& key) {
x ^= m[key][0];
folly::doNotOptimizeAway(x);
},
2);
}
template <template <class, class> class Map, class K, class V>
void benchmarkErase(int runs, int size) {
for (int i = 0; i < runs; ++i) {
benchmarkFilledMapByKey<Map, K, V>(
1, size, [&](Map<K, V>& m, const K& key) { m.erase(key); }, 2);
}
}
template <template <class, class> class Map, class K, class V>
void benchmarkDtor(int runs, int size) {
for (int i = 0; i < runs; ++i) {
benchmarkFilledMap<Map, K, V>(
1,
size,
[&](Map<K, V>& m) {
Map<K, V> toDestruct;
swap(m, toDestruct);
},
2);
}
}
template <template <class, class> class Map, class K, class V>
void benchmarkClear(int runs, int size) {
for (int i = 0; i < runs; ++i) {
benchmarkFilledMap<Map, K, V>(1, size, [&](Map<K, V>& m) { m.clear(); }, 1);
}
}
template <template <class, class> class Map, class K, class V>
void benchmarkCopyCtor(int runs, int size) {
Map<K, V> n;
for (int i = 0; i < runs; ++i) {
benchmarkFilledMap<Map, K, V>(1, size, [&](Map<K, V>& m) { n = m; }, 1);
folly::doNotOptimizeAway(n);
}
}
template <template <class, class> class Map, class K, class V>
void benchmarkIter(int runs, int size) {
int x = 0;
benchmarkFilledMap<Map, K, V>(runs, size, [&](Map<K, V>& m) {
for (auto& entry : m) {
x ^= entry.second[0];
}
});
folly::doNotOptimizeAway(x);
}
template <template <class, class> class Map, class K, class V>
void benchmarkSparseIter(int runs, int size) {
int x = 0;
benchmarkFilledMap<Map, K, V>(
runs,
size,
[&](Map<K, V>& m) {
for (auto& entry : m) {
x ^= entry.second[0];
}
},
8);
folly::doNotOptimizeAway(x);
}
template <template <class, class> class Map, class K, class V>
void benchmarkCtorWithCapacity(int runs, int size) {
for (int ii = 0; ii < runs; ++ii) {
Map<K, V> map(size);
folly::doNotOptimizeAway(map);
}
}
template <class K, class V>
using unord = std::unordered_map<K, V>;
template <class K, class V>
using f14val = F14ValueMap<K, V>;
template <class K, class V>
using f14node = F14NodeMap<K, V>;
template <class K, class V>
using f14vec = F14VectorMap<K, V>;
void runAllHashMapTests() {
using std::map;
using std::string;
std::vector<string> testOrder;
map<size_t,
map<string,
map<string, map<string, map<string, std::function<int(int)>>>>>>
tests;
#define Z(test, map, key, value_size) \
for (auto size = FLAGS_map_size_min; size <= FLAGS_map_size_max; \
size *= FLAGS_map_size_step) { \
auto value = folly::sformat("a[{}]", #value_size); \
tests[size][#test][#key][value][#map] = [=](int iters) { \
benchmark##test<map, key, std::array<uint8_t, value_size>>(iters, size); \
return iters; \
}; \
}
#define Y(test, map) \
Z(test, map, uint64_t, 1) \
Z(test, map, std::string, 1) \
Z(test, map, NonSSOString, 1) \
Z(test, map, uint64_t, 128) \
Z(test, map, std::string, 128) \
Z(test, map, NonSSOString, 128)
#define X(test) \
testOrder.push_back(#test); \
Y(test, unord) \
Y(test, f14val) \
Y(test, f14node) \
Y(test, f14vec)
X(Insert);
X(InsertSqBr);
X(InsertGrow);
X(Find);
X(ManyFind);
X(SqBrFind);
X(Erase);
X(Iter);
X(SparseIter);
X(Clear);
X(Dtor);
X(CopyCtor);
X(CtorWithCapacity);
#undef X
#undef Y
#undef Z
for (auto& size : tests) {
for (auto& test : testOrder) {
for (auto& key : size.second[test]) {
for (auto& value : key.second) {
bool isBaseline = true;
for (auto& map : value.second) {
addBenchmark(
__FILE__,
folly::sformat(
"{}{} {:>8}<{}, {}>[{}]",
isBaseline ? "" : "%",
test,
map.first,
key.first,
value.first,
size.first),
std::move(map.second));
isBaseline = false;
}
addBenchmark(__FILE__, "-", [](int iters) { return iters; });
}
}
}
}
}
int main(int argc, char** argv) {
folly::Init init(&argc, &argv);
gflags::SetCommandLineOptionWithMode(
"bm_max_iters", "100000", gflags::SET_FLAG_IF_DEFAULT);
gflags::SetCommandLineOptionWithMode(
"bm_min_iters", "10000", gflags::SET_FLAG_IF_DEFAULT);
gflags::SetCommandLineOptionWithMode(
"bm_max_secs", "1", gflags::SET_FLAG_IF_DEFAULT);
LOG(INFO) << "Preparing benchmark...";
runAllHashMapTests();
LOG(INFO) << "Running benchmark, which could take tens of minutes...";
runBenchmarks();
return 0;
}
Codebase Browser
folly