folly/experimental/test/CodingTestUtils.h

   1 /*
   2  * Copyright 2015 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 #ifndef FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  18 #define FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H
  19
  20 #include <algorithm>
  21 #include <fstream>
  22 #include <limits>
  23 #include <random>
  24 #include <string>
  25 #include <vector>
  26 #include <unordered_set>
  27 #include <glog/logging.h>
  28 #include <gtest/gtest.h>
  29
  30 namespace folly { namespace compression {
  31
  32 template <class URNG>
  33 std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId, URNG&& g) {
  34   CHECK_LT(n, 2 * maxId);
  35   std::uniform_int_distribution<> uid(1, maxId);
  36   std::unordered_set<uint32_t> dataset;
  37   while (dataset.size() < n) {
  38     uint32_t value = uid(g);
  39     if (dataset.count(value) == 0) {
  40       dataset.insert(value);
  41     }
  42   }
  43
  44   std::vector<uint32_t> ids(dataset.begin(), dataset.end());
  45   std::sort(ids.begin(), ids.end());
  46   return ids;
  47 }
  48
  49 inline std::vector<uint32_t> generateRandomList(size_t n, uint32_t maxId) {
  50   std::mt19937 gen;
  51   return generateRandomList(n, maxId, gen);
  52 }
  53
  54 inline std::vector<uint32_t> generateSeqList(uint32_t minId, uint32_t maxId,
  55                                              uint32_t step = 1) {
  56   CHECK_LE(minId, maxId);
  57   CHECK_GT(step, 0);
  58   std::vector<uint32_t> ids;
  59   ids.reserve((maxId - minId) / step + 1);
  60   for (uint32_t i = minId; i <= maxId; i += step) {
  61     ids.push_back(i);
  62   }
  63   return ids;
  64 }
  65
  66 inline std::vector<uint32_t> loadList(const std::string& filename) {
  67   std::ifstream fin(filename);
  68   std::vector<uint32_t> result;
  69   uint32_t id;
  70   while (fin >> id) {
  71     result.push_back(id);
  72   }
  73   return result;
  74 }
  75
  76 template <class Reader, class List>
  77 void testNext(const std::vector<uint32_t>& data, const List& list) {
  78   Reader reader(list);
  79   EXPECT_EQ(reader.value(), 0);
  80   for (size_t i = 0; i < data.size(); ++i) {
  81     EXPECT_TRUE(reader.next());
  82     EXPECT_EQ(reader.value(), data[i]);
  83     EXPECT_EQ(reader.position(), i);
  84   }
  85   EXPECT_FALSE(reader.next());
  86   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
  87   EXPECT_EQ(reader.position(), reader.size());
  88 }
  89
  90 template <class Reader, class List>
  91 void testSkip(const std::vector<uint32_t>& data, const List& list,
  92               size_t skipStep) {
  93   CHECK_GT(skipStep, 0);
  94   Reader reader(list);
  95   EXPECT_EQ(reader.value(), 0);
  96   for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
  97     EXPECT_TRUE(reader.skip(skipStep));
  98     EXPECT_EQ(reader.value(), data[i]);
  99     EXPECT_EQ(reader.position(), i);
 100   }
 101   EXPECT_FALSE(reader.skip(skipStep));
 102   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 103   EXPECT_EQ(reader.position(), reader.size());
 104   EXPECT_FALSE(reader.next());
 105 }
 106
 107 template <class Reader, class List>
 108 void testSkip(const std::vector<uint32_t>& data, const List& list) {
 109   for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
 110     testSkip<Reader, List>(data, list, skipStep);
 111   }
 112   for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
 113     testSkip<Reader, List>(data, list, skipStep);
 114   }
 115 }
 116
 117 template <class Reader, class List>
 118 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
 119                 size_t skipToStep) {
 120   CHECK_GT(skipToStep, 0);
 121
 122   Reader reader(list);
 123   EXPECT_EQ(reader.value(), 0);
 124
 125   const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
 126   uint32_t value = delta;
 127   auto it = data.begin();
 128   while (true) {
 129     it = std::lower_bound(it, data.end(), value);
 130     if (it == data.end()) {
 131       EXPECT_FALSE(reader.skipTo(value));
 132       break;
 133     }
 134     EXPECT_TRUE(reader.skipTo(value));
 135     EXPECT_EQ(reader.value(), *it);
 136     value = reader.value() + delta;
 137   }
 138   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 139   EXPECT_EQ(reader.position(), reader.size());
 140   EXPECT_FALSE(reader.next());
 141 }
 142
 143 template <class Reader, class List>
 144 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
 145   for (size_t steps = 10; steps < 100; steps += 10) {
 146     testSkipTo<Reader, List>(data, list, steps);
 147   }
 148   for (size_t steps = 100; steps <= 1000; steps += 100) {
 149     testSkipTo<Reader, List>(data, list, steps);
 150   }
 151   testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
 152   {
 153     Reader reader(list);
 154     EXPECT_FALSE(reader.skipTo(data.back() + 1));
 155     EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 156     EXPECT_EQ(reader.position(), reader.size());
 157     EXPECT_FALSE(reader.next());
 158   }
 159 }
 160
 161 template <class Reader, class List>
 162 void testJump(const std::vector<uint32_t>& data, const List& list) {
 163   std::mt19937 gen;
 164   std::vector<size_t> is(data.size());
 165   for (size_t i = 0; i < data.size(); ++i) {
 166     is[i] = i;
 167   }
 168   std::shuffle(is.begin(), is.end(), gen);
 169   if (Reader::EncoderType::forwardQuantum == 0) {
 170     is.resize(std::min<size_t>(is.size(), 100));
 171   }
 172
 173   Reader reader(list);
 174   EXPECT_TRUE(reader.jump(0));
 175   EXPECT_EQ(reader.value(), 0);
 176   for (auto i : is) {
 177     EXPECT_TRUE(reader.jump(i + 1));
 178     EXPECT_EQ(reader.value(), data[i]);
 179     EXPECT_EQ(reader.position(), i);
 180   }
 181   EXPECT_FALSE(reader.jump(data.size() + 1));
 182   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 183   EXPECT_EQ(reader.position(), reader.size());
 184 }
 185
 186 template <class Reader, class List>
 187 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
 188   CHECK(!data.empty());
 189
 190   Reader reader(list);
 191
 192   std::mt19937 gen;
 193   std::uniform_int_distribution<> values(0, data.back());
 194   const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
 195   for (size_t i = 0; i < iters; ++i) {
 196     const uint32_t value = values(gen);
 197     auto it = std::lower_bound(data.begin(), data.end(), value);
 198     CHECK(it != data.end());
 199     EXPECT_TRUE(reader.jumpTo(value));
 200     EXPECT_EQ(reader.value(), *it);
 201     EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
 202   }
 203
 204   EXPECT_TRUE(reader.jumpTo(0));
 205   EXPECT_EQ(reader.value(), 0);
 206   EXPECT_EQ(reader.position(), -1);
 207
 208   if (data.front() > 0) {
 209     EXPECT_TRUE(reader.jumpTo(1));
 210     EXPECT_EQ(reader.value(), data.front());
 211     EXPECT_EQ(reader.position(), 0);
 212   }
 213
 214   EXPECT_TRUE(reader.jumpTo(data.back()));
 215   EXPECT_EQ(reader.value(), data.back());
 216   EXPECT_EQ(reader.position(), reader.size() - 1);
 217
 218   EXPECT_FALSE(reader.jumpTo(data.back() + 1));
 219   EXPECT_EQ(reader.value(), std::numeric_limits<uint32_t>::max());
 220   EXPECT_EQ(reader.position(), reader.size());
 221 }
 222
 223 template <class Reader, class Encoder>
 224 void testEmpty() {
 225   const typename Encoder::ValueType* const data = nullptr;
 226   auto list = Encoder::encode(data, data);
 227   {
 228     Reader reader(list);
 229     EXPECT_FALSE(reader.next());
 230     EXPECT_EQ(reader.size(), 0);
 231   }
 232   {
 233     Reader reader(list);
 234     EXPECT_FALSE(reader.skip(1));
 235     EXPECT_FALSE(reader.skip(10));
 236     EXPECT_FALSE(reader.jump(1));
 237     EXPECT_FALSE(reader.jump(10));
 238   }
 239   {
 240     Reader reader(list);
 241     EXPECT_FALSE(reader.skipTo(1));
 242     EXPECT_FALSE(reader.jumpTo(1));
 243   }
 244 }
 245
 246 template <class Reader, class Encoder>
 247 void testAll(const std::vector<uint32_t>& data) {
 248   auto list = Encoder::encode(data.begin(), data.end());
 249   testNext<Reader>(data, list);
 250   testSkip<Reader>(data, list);
 251   testSkipTo<Reader>(data, list);
 252   testJump<Reader>(data, list);
 253   testJumpTo<Reader>(data, list);
 254   list.free();
 255 }
 256
 257 template <class Reader, class List>
 258 void bmNext(const List& list, const std::vector<uint32_t>& data, size_t iters) {
 259   if (data.empty()) {
 260     return;
 261   }
 262
 263   Reader reader(list);
 264   for (size_t i = 0; i < iters; ++i) {
 265     if (LIKELY(reader.next())) {
 266       folly::doNotOptimizeAway(reader.value());
 267     } else {
 268       reader.reset();
 269     }
 270   }
 271 }
 272
 273 template <class Reader, class List>
 274 void bmSkip(const List& list, const std::vector<uint32_t>& data,
 275             size_t logAvgSkip, size_t iters) {
 276   size_t avg = (size_t(1) << logAvgSkip);
 277   size_t base = avg - (avg >> 2);
 278   size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
 279
 280   Reader reader(list);
 281   for (size_t i = 0; i < iters; ++i) {
 282     size_t skip = base + (i & mask);
 283     if (LIKELY(reader.skip(skip))) {
 284       folly::doNotOptimizeAway(reader.value());
 285     } else {
 286       reader.reset();
 287     }
 288   }
 289 }
 290
 291 template <class Reader, class List>
 292 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
 293               size_t logAvgSkip, size_t iters) {
 294   size_t avg = (size_t(1) << logAvgSkip);
 295   size_t base = avg - (avg >> 2);
 296   size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
 297
 298   Reader reader(list);
 299   for (size_t i = 0, j = -1; i < iters; ++i) {
 300     size_t skip = base + (i & mask);
 301     j += skip;
 302     if (j >= data.size()) {
 303       reader.reset();
 304       j = -1;
 305     }
 306
 307     reader.skipTo(data[j]);
 308     folly::doNotOptimizeAway(reader.value());
 309   }
 310 }
 311
 312 template <class Reader, class List>
 313 void bmJump(const List& list, const std::vector<uint32_t>& data,
 314             const std::vector<size_t>& order, size_t iters) {
 315   CHECK(!data.empty());
 316   CHECK_EQ(data.size(), order.size());
 317
 318   Reader reader(list);
 319   for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
 320     if (j == order.size()) j = 0;
 321     reader.jump(order[j]);
 322     folly::doNotOptimizeAway(reader.value());
 323   }
 324 }
 325
 326 template <class Reader, class List>
 327 void bmJumpTo(const List& list, const std::vector<uint32_t>& data,
 328               const std::vector<size_t>& order, size_t iters) {
 329   CHECK(!data.empty());
 330   CHECK_EQ(data.size(), order.size());
 331
 332   Reader reader(list);
 333   for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
 334     if (j == order.size()) j = 0;
 335     reader.jumpTo(data[order[j]]);
 336     folly::doNotOptimizeAway(reader.value());
 337   }
 338 }
 339
 340 }}  // namespaces
 341
 342 #endif  // FOLLY_EXPERIMENTAL_CODING_TEST_UTILS_H