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