2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include <folly/memory/ThreadCachedArena.h>
25 #include <unordered_map>
27 #include <glog/logging.h>
29 #include <folly/Benchmark.h>
30 #include <folly/Memory.h>
31 #include <folly/Range.h>
32 #include <folly/lang/Align.h>
33 #include <folly/portability/GTest.h>
35 using namespace folly;
41 explicit ArenaTester(ThreadCachedArena& arena) : arena_(&arena) { }
43 void allocate(size_t count, size_t maxSize);
45 void merge(ArenaTester&& other);
48 std::mutex mergeMutex_;
49 std::vector<std::pair<uint8_t, Range<uint8_t*>>> areas_;
50 ThreadCachedArena* arena_;
53 void ArenaTester::allocate(size_t count, size_t maxSize) {
54 // Allocate chunks of memory of random sizes
56 std::uniform_int_distribution<uint32_t> sizeDist(1, maxSize - 1);
58 areas_.reserve(count);
59 for (size_t i = 0; i < count; i++) {
60 size_t size = sizeDist(rnd);
61 uint8_t* p = static_cast<uint8_t*>(arena_->allocate(size));
62 areas_.emplace_back(uint8_t(rnd() & 0xff), Range<uint8_t*>(p, size));
65 // Fill each area with a different value, to prove that they don't overlap
66 // Fill in random order.
67 std::random_shuffle(areas_.begin(), areas_.end(), [&rnd](ptrdiff_t n) {
68 return std::uniform_int_distribution<uint32_t>(0, n - 1)(rnd);
71 for (auto& p : areas_) {
72 std::fill(p.second.begin(), p.second.end(), p.first);
76 void ArenaTester::verify() {
77 for (auto& p : areas_) {
78 for (auto v : p.second) {
79 EXPECT_EQ(p.first, v);
84 void ArenaTester::merge(ArenaTester&& other) {
86 std::lock_guard<std::mutex> lock(mergeMutex_);
87 std::move(other.areas_.begin(), other.areas_.end(),
88 std::back_inserter(areas_));
95 TEST(ThreadCachedArena, BlockSize) {
96 static const size_t alignment = max_align_v;
97 static const size_t requestedBlockSize = 64;
99 ThreadCachedArena arena(requestedBlockSize);
100 size_t blockSize = alignment;
101 uint8_t* prev = static_cast<uint8_t*>(arena.allocate(1));
103 // Keep allocating until we're no longer one single alignment away from the
104 // previous allocation -- that's when we've gotten to the next block.
106 while ((p = static_cast<uint8_t*>(arena.allocate(1))) ==
109 blockSize += alignment;
112 VLOG(1) << "Requested block size: " << requestedBlockSize << ", actual: "
114 EXPECT_LE(requestedBlockSize, blockSize);
117 TEST(ThreadCachedArena, SingleThreaded) {
118 static const size_t requestedBlockSize = 64;
119 ThreadCachedArena arena(requestedBlockSize);
120 EXPECT_EQ(arena.totalSize(), sizeof(ThreadCachedArena));
122 ArenaTester tester(arena);
123 tester.allocate(100, 100 << 10);
126 EXPECT_GT(arena.totalSize(), sizeof(ThreadCachedArena));
129 TEST(ThreadCachedArena, MultiThreaded) {
130 static const size_t requestedBlockSize = 64;
131 ThreadCachedArena arena(requestedBlockSize);
132 ArenaTester mainTester(arena);
134 // Do this twice, to catch the possibility that memory from the first
136 static const size_t numThreads = 20;
137 for (size_t i = 0; i < 2; i++) {
138 std::vector<std::thread> threads;
139 threads.reserve(numThreads);
140 for (size_t j = 0; j < numThreads; j++) {
141 threads.emplace_back(
142 [&arena, &mainTester] () {
143 ArenaTester tester(arena);
144 tester.allocate(500, 1 << 10);
146 mainTester.merge(std::move(tester));
149 for (auto& t : threads) {
157 TEST(ThreadCachedArena, StlAllocator) {
158 typedef std::unordered_map<
159 int, int, std::hash<int>, std::equal_to<int>,
160 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
162 static const size_t requestedBlockSize = 64;
163 ThreadCachedArena arena(requestedBlockSize);
165 Map map {0, std::hash<int>(), std::equal_to<int>(),
166 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
168 for (int i = 0; i < 1000; i++) {
172 for (int i = 0; i < 1000; i++) {
173 EXPECT_EQ(i, map[i]);
179 static const int kNumValues = 10000;
181 BENCHMARK(bmUMStandard, iters) {
182 typedef std::unordered_map<int, int> Map;
186 for (int i = 0; i < kNumValues; i++) {
192 BENCHMARK(bmUMArena, iters) {
193 typedef std::unordered_map<
194 int, int, std::hash<int>, std::equal_to<int>,
195 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
198 ThreadCachedArena arena;
200 Map map {0, std::hash<int>(), std::equal_to<int>(),
201 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
204 for (int i = 0; i < kNumValues; i++) {
210 BENCHMARK_DRAW_LINE()
212 BENCHMARK(bmMStandard, iters) {
213 typedef std::map<int, int> Map;
217 for (int i = 0; i < kNumValues; i++) {
223 BENCHMARK_DRAW_LINE()
225 BENCHMARK(bmMArena, iters) {
227 int, int, std::less<int>,
228 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
231 ThreadCachedArena arena;
233 Map map {std::less<int>(),
234 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
237 for (int i = 0; i < kNumValues; i++) {
243 BENCHMARK_DRAW_LINE()
247 // Benchmark Iters Total t t/iter iter/sec
248 // ----------------------------------------------------------------------------
249 // Comparing benchmarks: bmUMStandard,bmUMArena
250 // + 143% bmUMStandard 1570 2.005 s 1.277 ms 782.9
251 // * bmUMArena 3817 2.003 s 524.7 us 1.861 k
252 // ----------------------------------------------------------------------------
253 // Comparing benchmarks: bmMStandard,bmMArena
254 // +79.0% bmMStandard 1197 2.009 s 1.678 ms 595.8
255 // * bmMArena 2135 2.002 s 937.6 us 1.042 k
256 // ----------------------------------------------------------------------------
258 int main(int argc, char *argv[]) {
259 testing::InitGoogleTest(&argc, argv);
260 gflags::ParseCommandLineFlags(&argc, &argv, true);
261 auto ret = RUN_ALL_TESTS();
262 if (!ret && FLAGS_benchmark) {
263 folly::runBenchmarks();