2 * Copyright 2013 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/ThreadCachedArena.h"
18 #include "folly/Memory.h"
25 #include <unordered_map>
27 #include <glog/logging.h>
28 #include <gtest/gtest.h>
30 #include "folly/Range.h"
31 #include "folly/Benchmark.h"
33 using namespace folly;
39 explicit ArenaTester(ThreadCachedArena& arena) : arena_(&arena) { }
41 void allocate(size_t count, size_t maxSize);
43 void merge(ArenaTester&& other);
46 std::mutex mergeMutex_;
47 std::vector<std::pair<uint8_t, Range<uint8_t*>>> areas_;
48 ThreadCachedArena* arena_;
51 void ArenaTester::allocate(size_t count, size_t maxSize) {
52 // Allocate chunks of memory of random sizes
54 std::uniform_int_distribution<uint32_t> sizeDist(1, maxSize - 1);
56 areas_.reserve(count);
57 for (size_t i = 0; i < count; i++) {
58 size_t size = sizeDist(rnd);
59 uint8_t* p = static_cast<uint8_t*>(arena_->allocate(size));
60 areas_.emplace_back(rnd() & 0xff, Range<uint8_t*>(p, size));
63 // Fill each area with a different value, to prove that they don't overlap
64 // Fill in random order.
66 areas_.begin(), areas_.end(),
67 [&rnd] (int n) -> int {
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 struct Align { char c; } __attribute__((aligned));
97 static const size_t alignment = alignof(Align);
98 static const size_t requestedBlockSize = 64;
100 ThreadCachedArena arena(requestedBlockSize);
101 size_t blockSize = alignment;
102 uint8_t* prev = static_cast<uint8_t*>(arena.allocate(1));
104 // Keep allocating until we're no longer one single alignment away from the
105 // previous allocation -- that's when we've gotten to the next block.
107 while ((p = static_cast<uint8_t*>(arena.allocate(1))) ==
110 blockSize += alignment;
113 VLOG(1) << "Requested block size: " << requestedBlockSize << ", actual: "
115 EXPECT_LE(requestedBlockSize, blockSize);
118 TEST(ThreadCachedArena, SingleThreaded) {
119 static const size_t requestedBlockSize = 64;
120 ThreadCachedArena arena(requestedBlockSize);
121 ArenaTester tester(arena);
122 tester.allocate(100, 100 << 10);
126 TEST(ThreadCachedArena, MultiThreaded) {
127 static const size_t requestedBlockSize = 64;
128 ThreadCachedArena arena(requestedBlockSize);
129 ArenaTester mainTester(arena);
131 // Do this twice, to catch the possibility that memory from the first
133 static const size_t numThreads = 20;
134 for (size_t i = 0; i < 2; i++) {
135 std::vector<std::thread> threads;
136 threads.reserve(numThreads);
137 for (size_t j = 0; j < numThreads; j++) {
138 threads.emplace_back(
139 [&arena, &mainTester] () {
140 ArenaTester tester(arena);
141 tester.allocate(500, 1 << 10);
143 mainTester.merge(std::move(tester));
146 for (auto& t : threads) {
154 TEST(ThreadCachedArena, StlAllocator) {
155 typedef std::unordered_map<
156 int, int, std::hash<int>, std::equal_to<int>,
157 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
159 static const size_t requestedBlockSize = 64;
160 ThreadCachedArena arena(requestedBlockSize);
162 Map map {0, std::hash<int>(), std::equal_to<int>(),
163 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
165 for (int i = 0; i < 1000; i++) {
169 for (int i = 0; i < 1000; i++) {
170 EXPECT_EQ(i, map[i]);
176 static const int kNumValues = 10000;
178 BENCHMARK(bmUMStandard, iters) {
179 typedef std::unordered_map<int, int> Map;
183 for (int i = 0; i < kNumValues; i++) {
189 BENCHMARK(bmUMArena, iters) {
190 typedef std::unordered_map<
191 int, int, std::hash<int>, std::equal_to<int>,
192 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
195 ThreadCachedArena arena;
197 Map map {0, std::hash<int>(), std::equal_to<int>(),
198 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
201 for (int i = 0; i < kNumValues; i++) {
207 BENCHMARK_DRAW_LINE()
209 BENCHMARK(bmMStandard, iters) {
210 typedef std::map<int, int> Map;
214 for (int i = 0; i < kNumValues; i++) {
220 BENCHMARK_DRAW_LINE()
222 BENCHMARK(bmMArena, iters) {
224 int, int, std::less<int>,
225 StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
228 ThreadCachedArena arena;
230 Map map {std::less<int>(),
231 StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
234 for (int i = 0; i < kNumValues; i++) {
240 BENCHMARK_DRAW_LINE()
245 // Benchmark Iters Total t t/iter iter/sec
246 // ----------------------------------------------------------------------------
247 // Comparing benchmarks: bmUMStandard,bmUMArena
248 // + 143% bmUMStandard 1570 2.005 s 1.277 ms 782.9
249 // * bmUMArena 3817 2.003 s 524.7 us 1.861 k
250 // ----------------------------------------------------------------------------
251 // Comparing benchmarks: bmMStandard,bmMArena
252 // +79.0% bmMStandard 1197 2.009 s 1.678 ms 595.8
253 // * bmMArena 2135 2.002 s 937.6 us 1.042 k
254 // ----------------------------------------------------------------------------
256 int main(int argc, char *argv[]) {
257 testing::InitGoogleTest(&argc, argv);
258 google::ParseCommandLineFlags(&argc, &argv, true);
259 auto ret = RUN_ALL_TESTS();
260 if (!ret && FLAGS_benchmark) {
261 folly::runBenchmarks();