rand_util_unittest.cc 8.08 KB
Newer Older
gejun's avatar
gejun committed
1 2 3 4
// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6 7
#include "butil/rand_util.h"
#include "butil/fast_rand.h"
#include "butil/time.h"
gejun's avatar
gejun committed
8 9 10
#include <algorithm>
#include <limits>

11 12 13
#include "butil/logging.h"
#include "butil/memory/scoped_ptr.h"
#include "butil/time/time.h"
gejun's avatar
gejun committed
14 15 16 17 18 19 20 21 22 23
#include <gtest/gtest.h>

namespace {

const int kIntMin = std::numeric_limits<int>::min();
const int kIntMax = std::numeric_limits<int>::max();

}  // namespace

TEST(RandUtilTest, Sanity) {
24 25 26
    EXPECT_EQ(butil::RandInt(0, 0), 0);
    EXPECT_EQ(butil::RandInt(kIntMin, kIntMin), kIntMin);
    EXPECT_EQ(butil::RandInt(kIntMax, kIntMax), kIntMax);
gejun's avatar
gejun committed
27 28

    for (int i = 0; i < 10; ++i) {
29
        uint64_t value = butil::fast_rand_in(
gejun's avatar
gejun committed
30 31 32 33 34 35 36 37 38
            (uint64_t)0, std::numeric_limits<uint64_t>::max());
        if (value != std::numeric_limits<uint64_t>::min() &&
            value != std::numeric_limits<uint64_t>::max()) {
            break;
        } else {
            EXPECT_NE(9, i) << "Never meet random except min/max of uint64";
        }
    }
    for (int i = 0; i < 10; ++i) {
39
        int64_t value = butil::fast_rand_in(
gejun's avatar
gejun committed
40 41 42 43 44 45 46 47 48
            std::numeric_limits<int64_t>::min(),
            std::numeric_limits<int64_t>::max());
        if (value != std::numeric_limits<int64_t>::min() &&
            value != std::numeric_limits<int64_t>::max()) {
            break;
        } else {
            EXPECT_NE(9, i) << "Never meet random except min/max of int64";
        }
    }
49 50 51 52
    EXPECT_EQ(butil::fast_rand_in(-1, -1), -1);
    EXPECT_EQ(butil::fast_rand_in(1, 1), 1);
    EXPECT_EQ(butil::fast_rand_in(0, 0), 0);
    EXPECT_EQ(butil::fast_rand_in(std::numeric_limits<int64_t>::min(),
gejun's avatar
gejun committed
53 54
                                  std::numeric_limits<int64_t>::min()),
              std::numeric_limits<int64_t>::min());
55
    EXPECT_EQ(butil::fast_rand_in(std::numeric_limits<int64_t>::max(),
gejun's avatar
gejun committed
56 57
                                  std::numeric_limits<int64_t>::max()),
              std::numeric_limits<int64_t>::max());
58
    EXPECT_EQ(butil::fast_rand_in(std::numeric_limits<uint64_t>::min(),
gejun's avatar
gejun committed
59 60
                                  std::numeric_limits<uint64_t>::min()),
              std::numeric_limits<uint64_t>::min());
61
    EXPECT_EQ(butil::fast_rand_in(std::numeric_limits<uint64_t>::max(),
gejun's avatar
gejun committed
62 63 64 65 66 67
                                  std::numeric_limits<uint64_t>::max()),
              std::numeric_limits<uint64_t>::max());
}

TEST(RandUtilTest, RandDouble) {
    // Force 64-bit precision, making sure we're not in a 80-bit FPU register.
68
    volatile double number = butil::RandDouble();
gejun's avatar
gejun committed
69 70 71
    EXPECT_GT(1.0, number);
    EXPECT_LE(0.0, number);

72
    volatile double number2 = butil::fast_rand_double();
gejun's avatar
gejun committed
73 74 75 76 77 78 79 80
    EXPECT_GT(1.0, number2);
    EXPECT_LE(0.0, number2);
}

TEST(RandUtilTest, RandBytes) {
    const size_t buffer_size = 50;
    char buffer[buffer_size];
    memset(buffer, 0, buffer_size);
81
    butil::RandBytes(buffer, buffer_size);
gejun's avatar
gejun committed
82 83 84 85 86 87 88
    std::sort(buffer, buffer + buffer_size);
    // Probability of occurrence of less than 25 unique bytes in 50 random bytes
    // is below 10^-25.
    EXPECT_GT(std::unique(buffer, buffer + buffer_size) - buffer, 25);
}

TEST(RandUtilTest, RandBytesAsString) {
89
    std::string random_string = butil::RandBytesAsString(1);
gejun's avatar
gejun committed
90
    EXPECT_EQ(1U, random_string.size());
91
    random_string = butil::RandBytesAsString(145);
gejun's avatar
gejun committed
92 93 94 95 96 97 98 99 100 101 102 103 104
    EXPECT_EQ(145U, random_string.size());
    char accumulator = 0;
    for (size_t i = 0; i < random_string.size(); ++i) {
        accumulator |= random_string[i];
    }
    // In theory this test can fail, but it won't before the universe dies of
    // heat death.
    EXPECT_NE(0, accumulator);
}

// Make sure that it is still appropriate to use RandGenerator in conjunction
// with std::random_shuffle().
TEST(RandUtilTest, RandGeneratorForRandomShuffle) {
105
    EXPECT_EQ(butil::RandGenerator(1), 0U);
gejun's avatar
gejun committed
106 107 108 109 110 111 112 113 114
    EXPECT_LE(std::numeric_limits<ptrdiff_t>::max(),
              std::numeric_limits<int64_t>::max());
}

TEST(RandUtilTest, RandGeneratorIsUniform) {
    // Verify that RandGenerator has a uniform distribution. This is a
    // regression test that consistently failed when RandGenerator was
    // implemented this way:
    //
115
    //   return butil::RandUint64() % max;
gejun's avatar
gejun committed
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133
    //
    // A degenerate case for such an implementation is e.g. a top of
    // range that is 2/3rds of the way to MAX_UINT64, in which case the
    // bottom half of the range would be twice as likely to occur as the
    // top half. A bit of calculus care of jar@ shows that the largest
    // measurable delta is when the top of the range is 3/4ths of the
    // way, so that's what we use in the test.
    const uint64_t kTopOfRange = (std::numeric_limits<uint64_t>::max() / 4ULL) * 3ULL;
    const uint64_t kExpectedAverage = kTopOfRange / 2ULL;
    const uint64_t kAllowedVariance = kExpectedAverage / 50ULL;  // +/- 2%
    const int kMinAttempts = 1000;
    const int kMaxAttempts = 1000000;

    for (int round = 0; round < 2; ++round) {
        LOG(INFO) << "Use " << (round == 0 ? "RandUtil" : "fast_rand");
        double cumulative_average = 0.0;
        int count = 0;
        while (count < kMaxAttempts) {
134 135
            uint64_t value = (round == 0 ? butil::RandGenerator(kTopOfRange)
                              : butil::fast_rand_less_than(kTopOfRange));
gejun's avatar
gejun committed
136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
            cumulative_average = (count * cumulative_average + value) / (count + 1);

            // Don't quit too quickly for things to start converging, or we may have
            // a false positive.
            if (count > kMinAttempts &&
                kExpectedAverage - kAllowedVariance < cumulative_average &&
                cumulative_average < kExpectedAverage + kAllowedVariance) {
                break;
            }

            ++count;
        }

        ASSERT_LT(count, kMaxAttempts) << "Expected average was " <<
            kExpectedAverage << ", average ended at " << cumulative_average;
    }
}

TEST(RandUtilTest, RandUint64ProducesBothValuesOfAllBits) {
    // This tests to see that our underlying random generator is good
    // enough, for some value of good enough.
    const uint64_t kAllZeros = 0ULL;
    const uint64_t kAllOnes = ~kAllZeros;

    for (int round = 0; round < 2; ++round) {
        LOG(INFO) << "Use " << (round == 0 ? "RandUtil" : "fast_rand");
        uint64_t found_ones = kAllZeros;
        uint64_t found_zeros = kAllOnes;
        bool fail = true;
        for (size_t i = 0; i < 1000; ++i) {
166
            uint64_t value = (round == 0 ? butil::RandUint64() : butil::fast_rand());
gejun's avatar
gejun committed
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
            found_ones |= value;
            found_zeros &= value;

            if (found_zeros == kAllZeros && found_ones == kAllOnes) {
                fail = false;
                break;
            }
        }
        if (fail) {
            FAIL() << "Didn't achieve all bit values in maximum number of tries.";
        }
    }
}

// Benchmark test for RandBytes().  Disabled since it's intentionally slow and
// does not test anything that isn't already tested by the existing RandBytes()
// tests.
TEST(RandUtilTest, DISABLED_RandBytesPerf) {
    // Benchmark the performance of |kTestIterations| of RandBytes() using a
    // buffer size of |kTestBufferSize|.
    const int kTestIterations = 10;
    const size_t kTestBufferSize = 1 * 1024 * 1024;

    scoped_ptr<uint8_t[]> buffer(new uint8_t[kTestBufferSize]);
191
    const butil::TimeTicks now = butil::TimeTicks::HighResNow();
gejun's avatar
gejun committed
192
    for (int i = 0; i < kTestIterations; ++i) {
193
        butil::RandBytes(buffer.get(), kTestBufferSize);
gejun's avatar
gejun committed
194
    }
195
    const butil::TimeTicks end = butil::TimeTicks::HighResNow();
gejun's avatar
gejun committed
196 197 198 199 200 201 202 203 204

    LOG(INFO) << "RandBytes(" << kTestBufferSize << ") took: "
              << (end - now).InMicroseconds() << "ms";
}

TEST(RandUtilTest, fast_rand_perf) {
    const int kTestIterations = 1000000;
    const int kRange = 17;
    uint64_t s = 0;
205
    butil::Timer tm;
gejun's avatar
gejun committed
206 207
    tm.start();
    for (int i = 0; i < kTestIterations; ++i) {
208
        s += butil::fast_rand_less_than(kRange);
gejun's avatar
gejun committed
209 210 211
    }
    tm.stop();
    LOG(INFO) << "Each fast_rand_less_than took " << tm.n_elapsed() / kTestIterations
212
              << " ns, "
gejun's avatar
gejun committed
213
#if !defined(NDEBUG)
214
              << " (debugging version)";
gejun's avatar
gejun committed
215
#else
216
             ;
gejun's avatar
gejun committed
217 218
#endif
}