non-throwing, non-allocating exception_wrapper
[folly.git] / folly / test / ThreadCachedArenaTest.cpp
1 /*
2  * Copyright 2017 Facebook, Inc.
3  *
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
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <folly/ThreadCachedArena.h>
18 #include <folly/Memory.h>
19
20 #include <map>
21 #include <mutex>
22 #include <thread>
23 #include <iterator>
24 #include <algorithm>
25 #include <random>
26 #include <unordered_map>
27
28 #include <glog/logging.h>
29
30 #include <folly/Range.h>
31 #include <folly/Benchmark.h>
32 #include <folly/portability/GTest.h>
33
34 using namespace folly;
35
36 namespace {
37
38 class ArenaTester {
39  public:
40   explicit ArenaTester(ThreadCachedArena& arena) : arena_(&arena) { }
41
42   void allocate(size_t count, size_t maxSize);
43   void verify();
44   void merge(ArenaTester&& other);
45
46  private:
47   std::mutex mergeMutex_;
48   std::vector<std::pair<uint8_t, Range<uint8_t*>>> areas_;
49   ThreadCachedArena* arena_;
50 };
51
52 void ArenaTester::allocate(size_t count, size_t maxSize) {
53   // Allocate chunks of memory of random sizes
54   std::mt19937 rnd;
55   std::uniform_int_distribution<uint32_t> sizeDist(1, maxSize - 1);
56   areas_.clear();
57   areas_.reserve(count);
58   for (size_t i = 0; i < count; i++) {
59     size_t size = sizeDist(rnd);
60     uint8_t* p = static_cast<uint8_t*>(arena_->allocate(size));
61     areas_.emplace_back(rnd() & 0xff, Range<uint8_t*>(p, size));
62   }
63
64   // Fill each area with a different value, to prove that they don't overlap
65   // Fill in random order.
66   std::random_shuffle(
67       areas_.begin(), areas_.end(),
68       [&rnd] (int n) -> int {
69         return std::uniform_int_distribution<uint32_t>(0, n-1)(rnd);
70       });
71
72   for (auto& p : areas_) {
73     std::fill(p.second.begin(), p.second.end(), p.first);
74   }
75 }
76
77 void ArenaTester::verify() {
78   for (auto& p : areas_) {
79     for (auto v : p.second) {
80       EXPECT_EQ(p.first, v);
81     }
82   }
83 }
84
85 void ArenaTester::merge(ArenaTester&& other) {
86   {
87     std::lock_guard<std::mutex> lock(mergeMutex_);
88     std::move(other.areas_.begin(), other.areas_.end(),
89               std::back_inserter(areas_));
90   }
91   other.areas_.clear();
92 }
93
94 }  // namespace
95
96 TEST(ThreadCachedArena, BlockSize) {
97   static const size_t alignment = alignof(std::max_align_t);
98   static const size_t requestedBlockSize = 64;
99
100   ThreadCachedArena arena(requestedBlockSize);
101   size_t blockSize = alignment;
102   uint8_t* prev = static_cast<uint8_t*>(arena.allocate(1));
103
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.
106   uint8_t* p;
107   while ((p = static_cast<uint8_t*>(arena.allocate(1))) ==
108          prev + alignment) {
109     prev = p;
110     blockSize += alignment;
111   }
112
113   VLOG(1) << "Requested block size: " << requestedBlockSize << ", actual: "
114           << blockSize;
115   EXPECT_LE(requestedBlockSize, blockSize);
116 }
117
118 TEST(ThreadCachedArena, SingleThreaded) {
119   static const size_t requestedBlockSize = 64;
120   ThreadCachedArena arena(requestedBlockSize);
121   EXPECT_EQ(arena.totalSize(), sizeof(ThreadCachedArena));
122
123   ArenaTester tester(arena);
124   tester.allocate(100, 100 << 10);
125   tester.verify();
126
127   EXPECT_GT(arena.totalSize(), sizeof(ThreadCachedArena));
128 }
129
130 TEST(ThreadCachedArena, MultiThreaded) {
131   static const size_t requestedBlockSize = 64;
132   ThreadCachedArena arena(requestedBlockSize);
133   ArenaTester mainTester(arena);
134
135   // Do this twice, to catch the possibility that memory from the first
136   // round gets freed
137   static const size_t numThreads = 20;
138   for (size_t i = 0; i < 2; i++) {
139     std::vector<std::thread> threads;
140     threads.reserve(numThreads);
141     for (size_t j = 0; j < numThreads; j++) {
142       threads.emplace_back(
143           [&arena, &mainTester] () {
144             ArenaTester tester(arena);
145             tester.allocate(500, 1 << 10);
146             tester.verify();
147             mainTester.merge(std::move(tester));
148           });
149     }
150     for (auto& t : threads) {
151       t.join();
152     }
153   }
154
155   mainTester.verify();
156 }
157
158 TEST(ThreadCachedArena, StlAllocator) {
159   typedef std::unordered_map<
160     int, int, std::hash<int>, std::equal_to<int>,
161     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
162
163   static const size_t requestedBlockSize = 64;
164   ThreadCachedArena arena(requestedBlockSize);
165
166   Map map {0, std::hash<int>(), std::equal_to<int>(),
167            StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
168
169   for (int i = 0; i < 1000; i++) {
170     map[i] = i;
171   }
172
173   for (int i = 0; i < 1000; i++) {
174     EXPECT_EQ(i, map[i]);
175   }
176 }
177
178 namespace {
179
180 static const int kNumValues = 10000;
181
182 BENCHMARK(bmUMStandard, iters) {
183   typedef std::unordered_map<int, int> Map;
184
185   while (iters--) {
186     Map map {0};
187     for (int i = 0; i < kNumValues; i++) {
188       map[i] = i;
189     }
190   }
191 }
192
193 BENCHMARK(bmUMArena, iters) {
194   typedef std::unordered_map<
195     int, int, std::hash<int>, std::equal_to<int>,
196     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
197
198   while (iters--) {
199     ThreadCachedArena arena;
200
201     Map map {0, std::hash<int>(), std::equal_to<int>(),
202              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
203                  &arena)};
204
205     for (int i = 0; i < kNumValues; i++) {
206       map[i] = i;
207     }
208   }
209 }
210
211 BENCHMARK_DRAW_LINE()
212
213 BENCHMARK(bmMStandard, iters) {
214   typedef std::map<int, int> Map;
215
216   while (iters--) {
217     Map map;
218     for (int i = 0; i < kNumValues; i++) {
219       map[i] = i;
220     }
221   }
222 }
223
224 BENCHMARK_DRAW_LINE()
225
226 BENCHMARK(bmMArena, iters) {
227   typedef std::map<
228     int, int, std::less<int>,
229     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
230
231   while (iters--) {
232     ThreadCachedArena arena;
233
234     Map map {std::less<int>(),
235              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
236                  &arena)};
237
238     for (int i = 0; i < kNumValues; i++) {
239       map[i] = i;
240     }
241   }
242 }
243
244 BENCHMARK_DRAW_LINE()
245
246 }  // namespace
247
248
249 // Benchmark                               Iters   Total t    t/iter iter/sec
250 // ----------------------------------------------------------------------------
251 // Comparing benchmarks: bmUMStandard,bmUMArena
252 //  + 143% bmUMStandard                     1570  2.005 s   1.277 ms  782.9
253 // *       bmUMArena                        3817  2.003 s   524.7 us  1.861 k
254 // ----------------------------------------------------------------------------
255 // Comparing benchmarks: bmMStandard,bmMArena
256 //  +79.0% bmMStandard                      1197  2.009 s   1.678 ms  595.8
257 // *       bmMArena                         2135  2.002 s   937.6 us  1.042 k
258 // ----------------------------------------------------------------------------
259
260 int main(int argc, char *argv[]) {
261   testing::InitGoogleTest(&argc, argv);
262   gflags::ParseCommandLineFlags(&argc, &argv, true);
263   auto ret = RUN_ALL_TESTS();
264   if (!ret && FLAGS_benchmark) {
265     folly::runBenchmarks();
266   }
267   return ret;
268 }