folly/test/ThreadCachedArenaTest.cpp

   1 /*
   2  * Copyright 2013 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/StlAllocator.h"
  19
  20 #include <mutex>
  21 #include <thread>
  22 #include <iterator>
  23 #include <algorithm>
  24 #include <random>
  25 #include <unordered_map>
  26
  27 #include <glog/logging.h>
  28 #include <gtest/gtest.h>
  29
  30 #include "folly/Range.h"
  31 #include "folly/Benchmark.h"
  32
  33 using namespace folly;
  34
  35 namespace {
  36
  37 class ArenaTester {
  38  public:
  39   explicit ArenaTester(ThreadCachedArena& arena) : arena_(&arena) { }
  40
  41   void allocate(size_t count, size_t maxSize);
  42   void verify();
  43   void merge(ArenaTester&& other);
  44
  45  private:
  46   std::mutex mergeMutex_;
  47   std::vector<std::pair<uint8_t, Range<uint8_t*>>> areas_;
  48   ThreadCachedArena* arena_;
  49 };
  50
  51 void ArenaTester::allocate(size_t count, size_t maxSize) {
  52   // Allocate chunks of memory of random sizes
  53   std::mt19937 rnd;
  54   std::uniform_int_distribution<uint32_t> sizeDist(1, maxSize - 1);
  55   areas_.clear();
  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));
  61   }
  62
  63   // Fill each area with a different value, to prove that they don't overlap
  64   // Fill in random order.
  65   std::random_shuffle(
  66       areas_.begin(), areas_.end(),
  67       [&rnd] (int n) -> int {
  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   struct Align { char c; } __attribute__((aligned));
  97   static const size_t alignment = alignof(Align);
  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   ArenaTester tester(arena);
 122   tester.allocate(100, 100 << 10);
 123   tester.verify();
 124 }
 125
 126 TEST(ThreadCachedArena, MultiThreaded) {
 127   static const size_t requestedBlockSize = 64;
 128   ThreadCachedArena arena(requestedBlockSize);
 129   ArenaTester mainTester(arena);
 130
 131   // Do this twice, to catch the possibility that memory from the first
 132   // round gets freed
 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);
 142             tester.verify();
 143             mainTester.merge(std::move(tester));
 144           });
 145     }
 146     for (auto& t : threads) {
 147       t.join();
 148     }
 149   }
 150
 151   mainTester.verify();
 152 }
 153
 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;
 158
 159   static const size_t requestedBlockSize = 64;
 160   ThreadCachedArena arena(requestedBlockSize);
 161
 162   Map map {0, std::hash<int>(), std::equal_to<int>(),
 163            StlAllocator<ThreadCachedArena, std::pair<const int, int>>(&arena)};
 164
 165   for (int i = 0; i < 1000; i++) {
 166     map[i] = i;
 167   }
 168
 169   for (int i = 0; i < 1000; i++) {
 170     EXPECT_EQ(i, map[i]);
 171   }
 172 }
 173
 174 namespace {
 175
 176 static const int kNumValues = 10000;
 177
 178 BENCHMARK(bmUMStandard, iters) {
 179   typedef std::unordered_map<int, int> Map;
 180
 181   while (iters--) {
 182     Map map {0};
 183     for (int i = 0; i < kNumValues; i++) {
 184       map[i] = i;
 185     }
 186   }
 187 }
 188
 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;
 193
 194   while (iters--) {
 195     ThreadCachedArena arena;
 196
 197     Map map {0, std::hash<int>(), std::equal_to<int>(),
 198              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 199                  &arena)};
 200
 201     for (int i = 0; i < kNumValues; i++) {
 202       map[i] = i;
 203     }
 204   }
 205 }
 206
 207 BENCHMARK_DRAW_LINE()
 208
 209 BENCHMARK(bmMStandard, iters) {
 210   typedef std::map<int, int> Map;
 211
 212   while (iters--) {
 213     Map map;
 214     for (int i = 0; i < kNumValues; i++) {
 215       map[i] = i;
 216     }
 217   }
 218 }
 219
 220 BENCHMARK_DRAW_LINE()
 221
 222 BENCHMARK(bmMArena, iters) {
 223   typedef std::map<
 224     int, int, std::less<int>,
 225     StlAllocator<ThreadCachedArena, std::pair<const int, int>>> Map;
 226
 227   while (iters--) {
 228     ThreadCachedArena arena;
 229
 230     Map map {std::less<int>(),
 231              StlAllocator<ThreadCachedArena, std::pair<const int, int>>(
 232                  &arena)};
 233
 234     for (int i = 0; i < kNumValues; i++) {
 235       map[i] = i;
 236     }
 237   }
 238 }
 239
 240 BENCHMARK_DRAW_LINE()
 241
 242 }  // namespace
 243
 244
 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 // ----------------------------------------------------------------------------
 255
 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();
 262   }
 263   return ret;
 264 }
 265