folly/memory/test/ThreadCachedArenaTest.cpp

   1 /*
   2  * Copyright 2012-present 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/memory/ThreadCachedArena.h>
  18
  19 #include <algorithm>
  20 #include <iterator>
  21 #include <map>
  22 #include <mutex>
  23 #include <random>
  24 #include <thread>
  25 #include <unordered_map>
  26
  27 #include <glog/logging.h>
  28
  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>
  34
  35 using namespace folly;
  36
  37 namespace {
  38
  39 class ArenaTester {
  40  public:
  41   explicit ArenaTester(ThreadCachedArena& arena) : arena_(&arena) { }
  42
  43   void allocate(size_t count, size_t maxSize);
  44   void verify();
  45   void merge(ArenaTester&& other);
  46
  47  private:
  48   std::mutex mergeMutex_;
  49   std::vector<std::pair<uint8_t, Range<uint8_t*>>> areas_;
  50   ThreadCachedArena* arena_;
  51 };
  52
  53 void ArenaTester::allocate(size_t count, size_t maxSize) {
  54   // Allocate chunks of memory of random sizes
  55   std::mt19937 rnd;
  56   std::uniform_int_distribution<uint32_t> sizeDist(1, maxSize - 1);
  57   areas_.clear();
  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));
  63   }
  64
  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);
  69   });
  70
  71   for (auto& p : areas_) {
  72     std::fill(p.second.begin(), p.second.end(), p.first);
  73   }
  74 }
  75
  76 void ArenaTester::verify() {
  77   for (auto& p : areas_) {
  78     for (auto v : p.second) {
  79       EXPECT_EQ(p.first, v);
  80     }
  81   }
  82 }
  83
  84 void ArenaTester::merge(ArenaTester&& other) {
  85   {
  86     std::lock_guard<std::mutex> lock(mergeMutex_);
  87     std::move(other.areas_.begin(), other.areas_.end(),
  88               std::back_inserter(areas_));
  89   }
  90   other.areas_.clear();
  91 }
  92
  93 } // namespace
  94
  95 TEST(ThreadCachedArena, BlockSize) {
  96   static const size_t alignment = max_align_v;
  97   static const size_t requestedBlockSize = 64;
  98
  99   ThreadCachedArena arena(requestedBlockSize);
 100   size_t blockSize = alignment;
 101   uint8_t* prev = static_cast<uint8_t*>(arena.allocate(1));
 102
 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.
 105   uint8_t* p;
 106   while ((p = static_cast<uint8_t*>(arena.allocate(1))) ==
 107          prev + alignment) {
 108     prev = p;
 109     blockSize += alignment;
 110   }
 111
 112   VLOG(1) << "Requested block size: " << requestedBlockSize << ", actual: "
 113           << blockSize;
 114   EXPECT_LE(requestedBlockSize, blockSize);
 115 }
 116
 117 TEST(ThreadCachedArena, SingleThreaded) {
 118   static const size_t requestedBlockSize = 64;
 119   ThreadCachedArena arena(requestedBlockSize);
 120   EXPECT_EQ(arena.totalSize(), sizeof(ThreadCachedArena));
 121
 122   ArenaTester tester(arena);
 123   tester.allocate(100, 100 << 10);
 124   tester.verify();
 125
 126   EXPECT_GT(arena.totalSize(), sizeof(ThreadCachedArena));
 127 }
 128
 129 TEST(ThreadCachedArena, MultiThreaded) {
 130   static const size_t requestedBlockSize = 64;
 131   ThreadCachedArena arena(requestedBlockSize);
 132   ArenaTester mainTester(arena);
 133
 134   // Do this twice, to catch the possibility that memory from the first
 135   // round gets freed
 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);
 145             tester.verify();
 146             mainTester.merge(std::move(tester));
 147           });
 148     }
 149     for (auto& t : threads) {
 150       t.join();
 151     }
 152   }
 153
 154   mainTester.verify();
 155 }
 156
 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;
 161
 162   static const size_t requestedBlockSize = 64;
 163   ThreadCachedArena arena(requestedBlockSize);
 164
 165   Map map {0, std::hash<int>(), std::equal_to<int>(),
 166            StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
 167
 168   for (int i = 0; i < 1000; i++) {
 169     map[i] = i;
 170   }
 171
 172   for (int i = 0; i < 1000; i++) {
 173     EXPECT_EQ(i, map[i]);
 174   }
 175 }
 176
 177 namespace {
 178
 179 static const int kNumValues = 10000;
 180
 181 BENCHMARK(bmUMStandard, iters) {
 182   typedef std::unordered_map<int, int> Map;
 183
 184   while (iters--) {
 185     Map map {0};
 186     for (int i = 0; i < kNumValues; i++) {
 187       map[i] = i;
 188     }
 189   }
 190 }
 191
 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;
 196
 197   while (iters--) {
 198     ThreadCachedArena arena;
 199
 200     Map map {0, std::hash<int>(), std::equal_to<int>(),
 201              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 202                  &arena)};
 203
 204     for (int i = 0; i < kNumValues; i++) {
 205       map[i] = i;
 206     }
 207   }
 208 }
 209
 210 BENCHMARK_DRAW_LINE()
 211
 212 BENCHMARK(bmMStandard, iters) {
 213   typedef std::map<int, int> Map;
 214
 215   while (iters--) {
 216     Map map;
 217     for (int i = 0; i < kNumValues; i++) {
 218       map[i] = i;
 219     }
 220   }
 221 }
 222
 223 BENCHMARK_DRAW_LINE()
 224
 225 BENCHMARK(bmMArena, iters) {
 226   typedef std::map<
 227     int, int, std::less<int>,
 228     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
 229
 230   while (iters--) {
 231     ThreadCachedArena arena;
 232
 233     Map map {std::less<int>(),
 234              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 235                  &arena)};
 236
 237     for (int i = 0; i < kNumValues; i++) {
 238       map[i] = i;
 239     }
 240   }
 241 }
 242
 243 BENCHMARK_DRAW_LINE()
 244
 245 } // namespace
 246
 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 // ----------------------------------------------------------------------------
 257
 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();
 264   }
 265   return ret;
 266 }