folly/test/ThreadCachedArenaTest.cpp

   1 /*
   2  * Copyright 2016 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 #include <gtest/gtest.h>
  30
  31 #include <folly/Range.h>
  32 #include <folly/Benchmark.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   struct Align { char c; } __attribute__((__aligned__));
  98   static const size_t alignment = alignof(Align);
  99   static const size_t requestedBlockSize = 64;
 100
 101   ThreadCachedArena arena(requestedBlockSize);
 102   size_t blockSize = alignment;
 103   uint8_t* prev = static_cast<uint8_t*>(arena.allocate(1));
 104
 105   // Keep allocating until we're no longer one single alignment away from the
 106   // previous allocation -- that's when we've gotten to the next block.
 107   uint8_t* p;
 108   while ((p = static_cast<uint8_t*>(arena.allocate(1))) ==
 109          prev + alignment) {
 110     prev = p;
 111     blockSize += alignment;
 112   }
 113
 114   VLOG(1) << "Requested block size: " << requestedBlockSize << ", actual: "
 115           << blockSize;
 116   EXPECT_LE(requestedBlockSize, blockSize);
 117 }
 118
 119 TEST(ThreadCachedArena, SingleThreaded) {
 120   static const size_t requestedBlockSize = 64;
 121   ThreadCachedArena arena(requestedBlockSize);
 122   EXPECT_EQ(arena.totalSize(), sizeof(ThreadCachedArena));
 123
 124   ArenaTester tester(arena);
 125   tester.allocate(100, 100 << 10);
 126   tester.verify();
 127
 128   EXPECT_GT(arena.totalSize(), sizeof(ThreadCachedArena));
 129 }
 130
 131 TEST(ThreadCachedArena, MultiThreaded) {
 132   static const size_t requestedBlockSize = 64;
 133   ThreadCachedArena arena(requestedBlockSize);
 134   ArenaTester mainTester(arena);
 135
 136   // Do this twice, to catch the possibility that memory from the first
 137   // round gets freed
 138   static const size_t numThreads = 20;
 139   for (size_t i = 0; i < 2; i++) {
 140     std::vector<std::thread> threads;
 141     threads.reserve(numThreads);
 142     for (size_t j = 0; j < numThreads; j++) {
 143       threads.emplace_back(
 144           [&arena, &mainTester] () {
 145             ArenaTester tester(arena);
 146             tester.allocate(500, 1 << 10);
 147             tester.verify();
 148             mainTester.merge(std::move(tester));
 149           });
 150     }
 151     for (auto& t : threads) {
 152       t.join();
 153     }
 154   }
 155
 156   mainTester.verify();
 157 }
 158
 159 TEST(ThreadCachedArena, StlAllocator) {
 160   typedef std::unordered_map<
 161     int, int, std::hash<int>, std::equal_to<int>,
 162     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
 163
 164   static const size_t requestedBlockSize = 64;
 165   ThreadCachedArena arena(requestedBlockSize);
 166
 167   Map map {0, std::hash<int>(), std::equal_to<int>(),
 168            StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
 169
 170   for (int i = 0; i < 1000; i++) {
 171     map[i] = i;
 172   }
 173
 174   for (int i = 0; i < 1000; i++) {
 175     EXPECT_EQ(i, map[i]);
 176   }
 177 }
 178
 179 namespace {
 180
 181 static const int kNumValues = 10000;
 182
 183 BENCHMARK(bmUMStandard, iters) {
 184   typedef std::unordered_map<int, int> Map;
 185
 186   while (iters--) {
 187     Map map {0};
 188     for (int i = 0; i < kNumValues; i++) {
 189       map[i] = i;
 190     }
 191   }
 192 }
 193
 194 BENCHMARK(bmUMArena, iters) {
 195   typedef std::unordered_map<
 196     int, int, std::hash<int>, std::equal_to<int>,
 197     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
 198
 199   while (iters--) {
 200     ThreadCachedArena arena;
 201
 202     Map map {0, std::hash<int>(), std::equal_to<int>(),
 203              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 204                  &arena)};
 205
 206     for (int i = 0; i < kNumValues; i++) {
 207       map[i] = i;
 208     }
 209   }
 210 }
 211
 212 BENCHMARK_DRAW_LINE()
 213
 214 BENCHMARK(bmMStandard, iters) {
 215   typedef std::map<int, int> Map;
 216
 217   while (iters--) {
 218     Map map;
 219     for (int i = 0; i < kNumValues; i++) {
 220       map[i] = i;
 221     }
 222   }
 223 }
 224
 225 BENCHMARK_DRAW_LINE()
 226
 227 BENCHMARK(bmMArena, iters) {
 228   typedef std::map<
 229     int, int, std::less<int>,
 230     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
 231
 232   while (iters--) {
 233     ThreadCachedArena arena;
 234
 235     Map map {std::less<int>(),
 236              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 237                  &arena)};
 238
 239     for (int i = 0; i < kNumValues; i++) {
 240       map[i] = i;
 241     }
 242   }
 243 }
 244
 245 BENCHMARK_DRAW_LINE()
 246
 247 }  // namespace
 248
 249
 250 // Benchmark                               Iters   Total t    t/iter iter/sec
 251 // ----------------------------------------------------------------------------
 252 // Comparing benchmarks: bmUMStandard,bmUMArena
 253 //  + 143% bmUMStandard                     1570  2.005 s   1.277 ms  782.9
 254 // *       bmUMArena                        3817  2.003 s   524.7 us  1.861 k
 255 // ----------------------------------------------------------------------------
 256 // Comparing benchmarks: bmMStandard,bmMArena
 257 //  +79.0% bmMStandard                      1197  2.009 s   1.678 ms  595.8
 258 // *       bmMArena                         2135  2.002 s   937.6 us  1.042 k
 259 // ----------------------------------------------------------------------------
 260
 261 int main(int argc, char *argv[]) {
 262   testing::InitGoogleTest(&argc, argv);
 263   gflags::ParseCommandLineFlags(&argc, &argv, true);
 264   auto ret = RUN_ALL_TESTS();
 265   if (!ret && FLAGS_benchmark) {
 266     folly::runBenchmarks();
 267   }
 268   return ret;
 269 }