folly/experimental/test/CodingTestUtils.h

   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 #pragma once
  18
  19 #include <algorithm>
  20 #include <fstream>
  21 #include <limits>
  22 #include <random>
  23 #include <string>
  24 #include <vector>
  25 #include <unordered_set>
  26 #include <glog/logging.h>
  27
  28 #include <folly/portability/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 // Test previousValue only if Reader has it.
  77 template <class... Args>
  78 void maybeTestPreviousValue(Args&&...) { }
  79
  80 // Make all the arguments template because if the types are not exact,
  81 // the above overload will be picked (for example i could be size_t or
  82 // ssize_t).
  83 template <class Vector, class Reader, class Index>
  84 auto maybeTestPreviousValue(const Vector& data, Reader& reader, Index i)
  85   -> decltype(reader.previousValue(), void()) {
  86   if (i != 0) {
  87     EXPECT_EQ(reader.previousValue(), data[i - 1]);
  88   }
  89 }
  90
  91 template <class Reader, class List>
  92 void testNext(const std::vector<uint32_t>& data, const List& list) {
  93   Reader reader(list);
  94   EXPECT_FALSE(reader.valid());
  95
  96   for (size_t i = 0; i < data.size(); ++i) {
  97     EXPECT_TRUE(reader.next());
  98     EXPECT_TRUE(reader.valid());
  99     EXPECT_EQ(reader.value(), data[i]);
 100     EXPECT_EQ(reader.position(), i);
 101     maybeTestPreviousValue(data, reader, i);
 102   }
 103   EXPECT_FALSE(reader.next());
 104   EXPECT_FALSE(reader.valid());
 105   EXPECT_EQ(reader.position(), reader.size());
 106 }
 107
 108 template <class Reader, class List>
 109 void testSkip(const std::vector<uint32_t>& data, const List& list,
 110               size_t skipStep) {
 111   CHECK_GT(skipStep, 0);
 112   Reader reader(list);
 113
 114   for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
 115     EXPECT_TRUE(reader.skip(skipStep));
 116     EXPECT_TRUE(reader.valid());
 117     EXPECT_EQ(reader.value(), data[i]);
 118     EXPECT_EQ(reader.position(), i);
 119     maybeTestPreviousValue(data, reader, i);
 120   }
 121   EXPECT_FALSE(reader.skip(skipStep));
 122   EXPECT_FALSE(reader.valid());
 123   EXPECT_EQ(reader.position(), reader.size());
 124   EXPECT_FALSE(reader.next());
 125 }
 126
 127 template <class Reader, class List>
 128 void testSkip(const std::vector<uint32_t>& data, const List& list) {
 129   for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
 130     testSkip<Reader, List>(data, list, skipStep);
 131   }
 132   for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
 133     testSkip<Reader, List>(data, list, skipStep);
 134   }
 135 }
 136
 137 template <class Reader, class List>
 138 void testSkipTo(const std::vector<uint32_t>& data, const List& list,
 139                 size_t skipToStep) {
 140   CHECK_GT(skipToStep, 0);
 141   Reader reader(list);
 142
 143   const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
 144   uint32_t value = delta;
 145   auto it = data.begin();
 146   while (true) {
 147     it = std::lower_bound(it, data.end(), value);
 148     if (it == data.end()) {
 149       EXPECT_FALSE(reader.skipTo(value));
 150       break;
 151     }
 152     EXPECT_TRUE(reader.skipTo(value));
 153     EXPECT_TRUE(reader.valid());
 154     EXPECT_EQ(reader.value(), *it);
 155     EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
 156     value = reader.value() + delta;
 157     maybeTestPreviousValue(data, reader, std::distance(data.begin(), it));
 158   }
 159   EXPECT_FALSE(reader.valid());
 160   EXPECT_EQ(reader.position(), reader.size());
 161   EXPECT_FALSE(reader.next());
 162 }
 163
 164 template <class Reader, class List>
 165 void testSkipTo(const std::vector<uint32_t>& data, const List& list) {
 166   for (size_t steps = 10; steps < 100; steps += 10) {
 167     testSkipTo<Reader, List>(data, list, steps);
 168   }
 169   for (size_t steps = 100; steps <= 1000; steps += 100) {
 170     testSkipTo<Reader, List>(data, list, steps);
 171   }
 172   testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
 173   {
 174     // Skip to the first element.
 175     Reader reader(list);
 176     EXPECT_TRUE(reader.skipTo(data[0]));
 177     EXPECT_EQ(reader.value(), data[0]);
 178     EXPECT_EQ(reader.position(), 0);
 179   }
 180   {
 181     // Skip past the last element.
 182     Reader reader(list);
 183     EXPECT_FALSE(reader.skipTo(data.back() + 1));
 184     EXPECT_FALSE(reader.valid());
 185     EXPECT_EQ(reader.position(), reader.size());
 186     EXPECT_FALSE(reader.next());
 187   }
 188   {
 189     // Skip to maximum integer.
 190     Reader reader(list);
 191     using ValueType = typename Reader::ValueType;
 192     EXPECT_FALSE(reader.skipTo(std::numeric_limits<ValueType>::max()));
 193     EXPECT_FALSE(reader.valid());
 194     EXPECT_EQ(reader.position(), reader.size());
 195     EXPECT_FALSE(reader.next());
 196   }
 197 }
 198
 199 template <class Reader, class List>
 200 void testJump(const std::vector<uint32_t>& data, const List& list) {
 201   std::mt19937 gen;
 202   std::vector<size_t> is(data.size());
 203   for (size_t i = 0; i < data.size(); ++i) {
 204     is[i] = i;
 205   }
 206   std::shuffle(is.begin(), is.end(), gen);
 207   if (Reader::EncoderType::forwardQuantum == 0) {
 208     is.resize(std::min<size_t>(is.size(), 100));
 209   }
 210
 211   Reader reader(list);
 212   for (auto i : is) {
 213     EXPECT_TRUE(reader.jump(i));
 214     EXPECT_EQ(reader.value(), data[i]);
 215     EXPECT_EQ(reader.position(), i);
 216     maybeTestPreviousValue(data, reader, i);
 217   }
 218   EXPECT_FALSE(reader.jump(data.size()));
 219   EXPECT_FALSE(reader.valid());
 220   EXPECT_EQ(reader.position(), reader.size());
 221 }
 222
 223 template <class Reader, class List>
 224 void testJumpTo(const std::vector<uint32_t>& data, const List& list) {
 225   CHECK(!data.empty());
 226
 227   Reader reader(list);
 228
 229   std::mt19937 gen;
 230   std::uniform_int_distribution<> values(0, data.back());
 231   const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
 232   for (size_t i = 0; i < iters; ++i) {
 233     const uint32_t value = values(gen);
 234     auto it = std::lower_bound(data.begin(), data.end(), value);
 235     CHECK(it != data.end());
 236     EXPECT_TRUE(reader.jumpTo(value));
 237     EXPECT_EQ(reader.value(), *it);
 238     EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
 239   }
 240
 241   EXPECT_TRUE(reader.jumpTo(0));
 242   EXPECT_EQ(reader.value(), data[0]);
 243   EXPECT_EQ(reader.position(), 0);
 244
 245   EXPECT_TRUE(reader.jumpTo(data.back()));
 246   EXPECT_EQ(reader.value(), data.back());
 247   EXPECT_EQ(reader.position(), reader.size() - 1);
 248
 249   EXPECT_FALSE(reader.jumpTo(data.back() + 1));
 250   EXPECT_FALSE(reader.valid());
 251   EXPECT_EQ(reader.position(), reader.size());
 252 }
 253
 254 template <class Reader, class Encoder>
 255 void testEmpty() {
 256   const typename Encoder::ValueType* const data = nullptr;
 257   auto list = Encoder::encode(data, data);
 258   {
 259     Reader reader(list);
 260     EXPECT_FALSE(reader.next());
 261     EXPECT_EQ(reader.size(), 0);
 262   }
 263   {
 264     Reader reader(list);
 265     EXPECT_FALSE(reader.skip(1));
 266     EXPECT_FALSE(reader.skip(10));
 267     EXPECT_FALSE(reader.jump(0));
 268     EXPECT_FALSE(reader.jump(10));
 269   }
 270   {
 271     Reader reader(list);
 272     EXPECT_FALSE(reader.skipTo(1));
 273     EXPECT_FALSE(reader.jumpTo(1));
 274   }
 275 }
 276
 277 template <class Reader, class Encoder>
 278 void testAll(const std::vector<uint32_t>& data) {
 279   auto list = Encoder::encode(data.begin(), data.end());
 280   testNext<Reader>(data, list);
 281   testSkip<Reader>(data, list);
 282   testSkipTo<Reader>(data, list);
 283   testJump<Reader>(data, list);
 284   testJumpTo<Reader>(data, list);
 285   list.free();
 286 }
 287
 288 template <class Reader, class List>
 289 void bmNext(const List& list, const std::vector<uint32_t>& data, size_t iters) {
 290   if (data.empty()) {
 291     return;
 292   }
 293
 294   Reader reader(list);
 295   for (size_t i = 0; i < iters; ++i) {
 296     if (LIKELY(reader.next())) {
 297       folly::doNotOptimizeAway(reader.value());
 298     } else {
 299       reader.reset();
 300     }
 301   }
 302 }
 303
 304 template <class Reader, class List>
 305 void bmSkip(const List& list,
 306             const std::vector<uint32_t>& /* data */,
 307             size_t logAvgSkip,
 308             size_t iters) {
 309   size_t avg = (size_t(1) << logAvgSkip);
 310   size_t base = avg - (avg >> 2);
 311   size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
 312
 313   Reader reader(list);
 314   for (size_t i = 0; i < iters; ++i) {
 315     size_t skip = base + (i & mask);
 316     if (LIKELY(reader.skip(skip))) {
 317       folly::doNotOptimizeAway(reader.value());
 318     } else {
 319       reader.reset();
 320     }
 321   }
 322 }
 323
 324 template <class Reader, class List>
 325 void bmSkipTo(const List& list, const std::vector<uint32_t>& data,
 326               size_t logAvgSkip, size_t iters) {
 327   size_t avg = (size_t(1) << logAvgSkip);
 328   size_t base = avg - (avg >> 2);
 329   size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;
 330
 331   Reader reader(list);
 332   for (size_t i = 0, j = -1; i < iters; ++i) {
 333     size_t skip = base + (i & mask);
 334     j += skip;
 335     if (j >= data.size()) {
 336       reader.reset();
 337       j = -1;
 338     }
 339
 340     reader.skipTo(data[j]);
 341     folly::doNotOptimizeAway(reader.value());
 342   }
 343 }
 344
 345 template <class Reader, class List>
 346 void bmJump(const List& list, const std::vector<uint32_t>& data,
 347             const std::vector<size_t>& order, size_t iters) {
 348   CHECK(!data.empty());
 349   CHECK_EQ(data.size(), order.size());
 350
 351   Reader reader(list);
 352   for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
 353     if (j == order.size()) j = 0;
 354     reader.jump(order[j]);
 355     folly::doNotOptimizeAway(reader.value());
 356   }
 357 }
 358
 359 template <class Reader, class List>
 360 void bmJumpTo(const List& list, const std::vector<uint32_t>& data,
 361               const std::vector<size_t>& order, size_t iters) {
 362   CHECK(!data.empty());
 363   CHECK_EQ(data.size(), order.size());
 364
 365   Reader reader(list);
 366   for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
 367     if (j == order.size()) j = 0;
 368     reader.jumpTo(data[order[j]]);
 369     folly::doNotOptimizeAway(reader.value());
 370   }
 371 }
 372
 373 }}  // namespaces