folly/test/RandomTest.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/Random.h>
  18
  19 #include <algorithm>
  20 #include <random>
  21 #include <thread>
  22 #include <unordered_set>
  23 #include <vector>
  24
  25 #include <glog/logging.h>
  26
  27 #include <folly/portability/GTest.h>
  28
  29 using namespace folly;
  30
  31 TEST(Random, StateSize) {
  32   using namespace folly::detail;
  33
  34   // uint_fast32_t is uint64_t on x86_64, w00t
  35   EXPECT_EQ(
  36       sizeof(uint_fast32_t) / 4 + 3, StateSizeT<std::minstd_rand0>::value);
  37   EXPECT_EQ(624, StateSizeT<std::mt19937>::value);
  38 #if FOLLY_HAVE_EXTRANDOM_SFMT19937
  39   EXPECT_EQ(624, StateSizeT<__gnu_cxx::sfmt19937>::value);
  40 #endif
  41   EXPECT_EQ(24, StateSizeT<std::ranlux24_base>::value);
  42 }
  43
  44 TEST(Random, Simple) {
  45   uint32_t prev = 0, seed = 0;
  46   for (int i = 0; i < 1024; ++i) {
  47     EXPECT_NE(seed = randomNumberSeed(), prev);
  48     prev = seed;
  49   }
  50 }
  51
  52 TEST(Random, FixedSeed) {
  53   // clang-format off
  54   struct ConstantRNG {
  55     typedef uint32_t result_type;
  56     result_type operator()() {
  57       return 4; // chosen by fair dice roll.
  58                 // guaranteed to be random.
  59     }
  60     static constexpr result_type min() {
  61       return std::numeric_limits<result_type>::min();
  62     }
  63     static constexpr result_type max() {
  64       return std::numeric_limits<result_type>::max();
  65     }
  66   };
  67   // clang-format on
  68
  69   ConstantRNG gen;
  70
  71   // Pick a constant random number...
  72   auto value = Random::rand32(10, gen);
  73
  74   // Loop to make sure it really is constant.
  75   for (int i = 0; i < 1024; ++i) {
  76     auto result = Random::rand32(10, gen);
  77     EXPECT_EQ(value, result);
  78   }
  79 }
  80
  81 TEST(Random, MultiThreaded) {
  82   const int n = 100;
  83   std::vector<uint32_t> seeds(n);
  84   std::vector<std::thread> threads;
  85   for (int i = 0; i < n; ++i) {
  86     threads.push_back(std::thread([i, &seeds] {
  87       seeds[i] = randomNumberSeed();
  88     }));
  89   }
  90   for (auto& t : threads) {
  91     t.join();
  92   }
  93   std::sort(seeds.begin(), seeds.end());
  94   for (int i = 0; i < n-1; ++i) {
  95     EXPECT_LT(seeds[i], seeds[i+1]);
  96   }
  97 }
  98
  99 TEST(Random, sanity) {
 100   // edge cases
 101   EXPECT_EQ(folly::Random::rand32(0), 0);
 102   EXPECT_EQ(folly::Random::rand32(12, 12), 0);
 103   EXPECT_EQ(folly::Random::rand64(0), 0);
 104   EXPECT_EQ(folly::Random::rand64(12, 12), 0);
 105
 106   // 32-bit repeatability, uniqueness
 107   constexpr int kTestSize = 1000;
 108   {
 109     std::vector<uint32_t> vals;
 110     folly::Random::DefaultGenerator rng;
 111     rng.seed(0xdeadbeef);
 112     for (int i = 0; i < kTestSize; ++i) {
 113       vals.push_back(folly::Random::rand32(rng));
 114     }
 115     rng.seed(0xdeadbeef);
 116     for (int i = 0; i < kTestSize; ++i) {
 117       EXPECT_EQ(vals[i], folly::Random::rand32(rng));
 118     }
 119     EXPECT_EQ(
 120         vals.size(),
 121         std::unordered_set<uint32_t>(vals.begin(), vals.end()).size());
 122   }
 123
 124   // 64-bit repeatability, uniqueness
 125   {
 126     std::vector<uint64_t> vals;
 127     folly::Random::DefaultGenerator rng;
 128     rng.seed(0xdeadbeef);
 129     for (int i = 0; i < kTestSize; ++i) {
 130       vals.push_back(folly::Random::rand64(rng));
 131     }
 132     rng.seed(0xdeadbeef);
 133     for (int i = 0; i < kTestSize; ++i) {
 134       EXPECT_EQ(vals[i], folly::Random::rand64(rng));
 135     }
 136     EXPECT_EQ(
 137         vals.size(),
 138         std::unordered_set<uint64_t>(vals.begin(), vals.end()).size());
 139   }
 140 }