15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2008, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All Rights Reserved. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Daniel Ford 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Checks basic properties of the sampler 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config_for_unittests.h" 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdlib.h> // defines posix_memalign 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> // for the printf at the end 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined HAVE_STDINT_H 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h> // to get uintptr_t 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined HAVE_INTTYPES_H 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <inttypes.h> // another place uintptr_t might be defined 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/types.h> 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <iostream> 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <vector> 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <cmath> 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/commandlineflags.h" 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sampler.h" // The Sampler class being tested 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::sort; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::min; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::max; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::vector; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using std::abs; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)vector<void (*)()> g_testlist; // the tests to run 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define TEST(a, b) \ 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Test_##a##_##b { \ 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Test_##a##_##b() { g_testlist.push_back(&Run); } \ 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void Run(); \ 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; \ 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static Test_##a##_##b g_test_##a##_##b; \ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Test_##a##_##b::Run() 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int RUN_ALL_TESTS() { 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<void (*)()>::const_iterator it; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (it = g_testlist.begin(); it != g_testlist.end(); ++it) { 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (*it)(); // The test will error-exit if there's a problem. 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(stderr, "\nPassed %d tests\n\nPASS\n", (int)g_testlist.size()); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef LOG // defined in base/logging.h 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ideally, we'd put the newline at the end, but this hack puts the 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// newline at the end of the previous log message, which is good enough :-) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LOG(level) std::cerr << "\n" 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static std::string StringPrintf(const char* format, ...) { 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char buf[256]; // should be big enough for all logging 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) va_list ap; 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) va_start(ap, format); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) perftools_vsnprintf(buf, sizeof(buf), format, ap); 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) va_end(ap); 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return buf; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<typename T> class scoped_array { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array(T* p) : p_(p) { } 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~scoped_array() { delete[] p_; } 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const T* get() const { return p_; } 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T* get() { return p_; } 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T& operator[](int i) { return p_[i]; } 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) T* p_; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note that these tests are stochastic. 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This mean that the chance of correct code passing the test is, 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the case of 5 standard deviations: 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kSigmas=5: ~99.99994267% 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the case of 4 standard deviations: 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kSigmas=4: ~99.993666% 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const double kSigmas = 4; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const size_t kSamplingInterval = 512*1024; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests that GetSamplePeriod returns the expected value 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// which is 1<<19 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, TestGetSamplePeriod) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t sample_period; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sample_period = sampler.GetSamplePeriod(); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GT(sample_period, 0); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests of the quality of the random numbers generated 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This uses the Anderson Darling test for uniformity. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See "Evaluating the Anderson-Darling Distribution" by Marsaglia 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for details. 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Short cut version of ADinf(z), z>0 (from Marsaglia) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This returns the p-value for Anderson Darling statistic in 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the limit as n-> infinity. For finite n, apply the error fix below. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double AndersonDarlingInf(double z) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (z < 2) { 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exp(-1.2337141 / z) / sqrt(z) * (2.00012 + (0.247105 - 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * z) * z) * z) * z) * z); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return exp( - exp(1.0776 - (2.30695 - (0.43424 - (0.082433 - 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (0.008056 - 0.0003146 * z) * z) * z) * z) * z)); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Corrects the approximation error in AndersonDarlingInf for small values of n 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Add this to AndersonDarlingInf to get a better approximation 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (from Marsaglia) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double AndersonDarlingErrFix(int n, double x) { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (x > 0.8) { 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (-130.2137 + (745.2337 - (1705.091 - (1950.646 - 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (1116.360 - 255.7844 * x) * x) * x) * x) * x) / n; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double cutoff = 0.01265 + 0.1757 / n; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double t; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (x < cutoff) { 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t = x / cutoff; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t = sqrt(t) * (1 - t) * (49 * t - 102); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t = (x - cutoff) / (0.8 - cutoff); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t = -0.00022633 + (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * t) * t) * t) * t) * t; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return t * (0.04213 + 0.01365 / n) / n; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the AndersonDarling p-value given n and the value of the statistic 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double AndersonDarlingPValue(int n, double z) { 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad = AndersonDarlingInf(z); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double errfix = AndersonDarlingErrFix(n, ad); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ad + errfix; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double AndersonDarlingStatistic(int n, double* random_sample) { 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad_sum = 0; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ad_sum += (2*i + 1) * log(random_sample[i] * (1 - random_sample[n-1-i])); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad_statistic = - n - 1/static_cast<double>(n) * ad_sum; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ad_statistic; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests if the array of doubles is uniformly distributed. 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Returns the p-value of the Anderson Darling Statistic 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for the given set of sorted random doubles 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See "Evaluating the Anderson-Darling Distribution" by 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Marsaglia and Marsaglia for details. 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double AndersonDarlingTest(int n, double* random_sample) { 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad_statistic = AndersonDarlingStatistic(n, random_sample); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("AD stat = %f, n=%d\n", ad_statistic, n); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double p = AndersonDarlingPValue(n, ad_statistic); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Test the AD Test. The value of the statistic should go to zero as n->infty 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Not run as part of regular tests 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ADTestTest(int n) { 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array<double> random_sample(new double[n]); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) random_sample[i] = (i+0.01)/n; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sort(random_sample.get(), random_sample.get() + n); 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad_stat = AndersonDarlingStatistic(n, random_sample.get()); 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("Testing the AD test. n=%d, ad_stat = %f", 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n, ad_stat); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Print the CDF of the distribution of the Anderson-Darling Statistic 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Used for checking the Anderson-Darling Test 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Not run as part of regular tests 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ADCDF() { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i < 40; i++) { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double x = i/10.0; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "x= " << x << " adpv= " 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << AndersonDarlingPValue(100, x) << ", " 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) << AndersonDarlingPValue(1000, x); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Testing that NextRandom generates uniform 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// random numbers. 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Applies the Anderson-Darling test for uniformity 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestNextRandom(int n) { 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t x = 1; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This assumes that the prng returns 48 bit numbers 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t max_prng_value = static_cast<uint64_t>(1)<<48; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Initialize 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i <= 20; i++) { // 20 mimics sampler.Init() 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x = sampler.NextRandom(x); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array<uint64_t> int_random_sample(new uint64_t[n]); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Collect samples 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int_random_sample[i] = x; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x = sampler.NextRandom(x); 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First sort them... 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sort(int_random_sample.get(), int_random_sample.get() + n); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array<double> random_sample(new double[n]); 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Convert them to uniform randoms (in the range [0,1]) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) random_sample[i] = static_cast<double>(int_random_sample[i])/max_prng_value; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now compute the Anderson-Darling statistic 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double ad_pvalue = AndersonDarlingTest(n, random_sample.get()); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("pvalue for AndersonDarlingTest " 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "with n= %d is p= %f\n", n, ad_pvalue); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GT(min(ad_pvalue, 1 - ad_pvalue), 0.0001); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << StringPrintf("prng is not uniform, %d\n", n); 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, TestNextRandom_MultipleValues) { 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestNextRandom(10); // Check short-range correlation 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestNextRandom(100); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestNextRandom(1000); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestNextRandom(10000); // Make sure there's no systematic error 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests that PickNextSamplePeriod generates 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// geometrically distributed random numbers. 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// First converts to uniforms then applied the 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Anderson-Darling test for uniformity. 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestPickNextSample(int n) { 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array<uint64_t> int_random_sample(new uint64_t[n]); 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sample_period = sampler.GetSamplePeriod(); 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ones_count = 0; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int_random_sample[i] = sampler.PickNextSamplingPoint(); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(int_random_sample[i], 1); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (int_random_sample[i] == 1) { 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ones_count += 1; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LT(ones_count, 4); // << " out of " << i << " samples."; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First sort them... 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sort(int_random_sample.get(), int_random_sample.get() + n); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scoped_array<double> random_sample(new double[n]); 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Convert them to uniform random numbers 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // by applying the geometric CDF 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; i++) { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) random_sample[i] = 1 - exp(-static_cast<double>(int_random_sample[i]) 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) / sample_period); 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now compute the Anderson-Darling statistic 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double geom_ad_pvalue = AndersonDarlingTest(n, random_sample.get()); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("pvalue for geometric AndersonDarlingTest " 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "with n= %d is p= %f\n", n, geom_ad_pvalue); 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GT(min(geom_ad_pvalue, 1 - geom_ad_pvalue), 0.0001); 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << "PickNextSamplingPoint does not produce good " 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // "geometric/exponential random numbers\n"; 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, TestPickNextSample_MultipleValues) { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestPickNextSample(10); // Make sure the first few are good (enough) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestPickNextSample(100); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestPickNextSample(1000); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TestPickNextSample(10000); // Make sure there's no systematic error 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is superceeded by the Anderson-Darling Test 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and it not run now. 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests how fast nearby values are spread out with LRand64 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The purpose of this code is to determine how many 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// steps to apply to the seed during initialization 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void TestLRand64Spread() { 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t current_value; 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("Testing LRand64 Spread\n"); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i < 10; i++) { 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("%d ", i); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_value = i; 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int j = 1; j < 100; j++) { 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_value = sampler.NextRandom(current_value); 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << current_value; 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Test for Fastlog2 code 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We care about the percentage error because we're using this 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for choosing step sizes, so "close" is relative to the size of 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the step we would get if we used the built-in log function 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, FastLog2) { 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double max_ratio_error = 0; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (double d = -1021.9; d < 1; d+= 0.13124235) { 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double e = pow(2.0, d); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double truelog = log(e) / log(2.0); // log_2(e) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double fastlog = sampler.FastLog2(e); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_ratio_error = max(max_ratio_error, 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max(truelog/fastlog-1, fastlog/truelog-1)); 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(max_ratio_error, 0.01); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << StringPrintf("d = %f, e=%f, truelog = %f, fastlog= %f\n", 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // d, e, truelog, fastlog); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("Fastlog2: max_ratio_error = %f\n", 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) max_ratio_error); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Futher tests 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool CheckMean(size_t mean, int num_samples) { 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t total = 0; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < num_samples; i++) { 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) total += sampler.PickNextSamplingPoint(); 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double empirical_mean = total / static_cast<double>(num_samples); 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double expected_sd = mean / pow(num_samples * 1.0, 0.5); 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return(fabs(mean-empirical_mean) < expected_sd * kSigmas); 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Prints a sequence so you can look at the distribution 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void OutputSequence(int sequence_length) { 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t next_step; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i< sequence_length; i++) { 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_step = sampler.PickNextSamplingPoint(); 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << next_step; 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)double StandardDeviationsErrorInSample( 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int total_samples, int picked_samples, 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int alloc_size, int sampling_interval) { 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double p = 1 - exp(-(static_cast<double>(alloc_size) / sampling_interval)); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double expected_samples = total_samples * p; 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double sd = pow(p*(1-p)*total_samples, 0.5); 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return((picked_samples - expected_samples) / sd); 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, LargeAndSmallAllocs_CombinedTest) { 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int counter_big = 0; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int counter_small = 0; 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size_big = 129*8*1024+1; 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size_small = 1024*8; 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_iters = 128*4*8; 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate in mixed chunks 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < num_iters; i++) { 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sampler.SampleAllocation(size_big)) { 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_big += 1; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < 129; i++) { 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sampler.SampleAllocation(size_small)) { 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) counter_small += 1; 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Now test that there are the right number of each 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double large_allocs_sds = 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StandardDeviationsErrorInSample(num_iters, counter_big, 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_big, kSamplingInterval); 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double small_allocs_sds = 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StandardDeviationsErrorInSample(num_iters*129, counter_small, 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_small, kSamplingInterval); 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("large_allocs_sds = %f\n", large_allocs_sds); 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("small_allocs_sds = %f\n", small_allocs_sds); 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(fabs(large_allocs_sds), kSigmas); 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(fabs(small_allocs_sds), kSigmas); 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests whether the mean is about right over 1000 samples 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, IsMeanRight) { 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(CheckMean(kSamplingInterval, 1000)); 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This flag is for the OldSampler class to use 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const int64 FLAGS_mock_tcmalloc_sample_parameter = 1<<19; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A cut down and slightly refactored version of the old Sampler 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class OldSampler { 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Init(uint32_t seed); 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Cleanup() {} 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Record allocation of "k" bytes. Return true iff allocation 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // should be sampled 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool SampleAllocation(size_t k); 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Generate a geometric with mean 1M (or FLAG value) 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PickNextSample(size_t k); 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Initialize the statics for the Sample class 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static void InitStatics() { 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sample_period = 1048583; 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t bytes_until_sample_; 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t rnd_; // Cheap random number generator 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static uint64_t sample_period; 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Should be a prime just above a power of 2: 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2, 5, 11, 17, 37, 67, 131, 257, 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 521, 1031, 2053, 4099, 8209, 16411, 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 32771, 65537, 131101, 262147, 524309, 1048583, 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2097169, 4194319, 8388617, 16777259, 33554467 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Statics for OldSampler 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uint64_t OldSampler::sample_period; 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void OldSampler::Init(uint32_t seed) { 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Initialize PRNG -- run it for a bit to get to good values 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (seed != 0) { 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd_ = seed; 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd_ = 12345; 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes_until_sample_ = 0; 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < 100; i++) { 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PickNextSample(sample_period * 2); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A cut-down version of the old PickNextSampleRoutine 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void OldSampler::PickNextSample(size_t k) { 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make next "random" number 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // x^32+x^22+x^2+x^1+1 is a primitive polynomial for random numbers 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint32_t kPoly = (1 << 22) | (1 << 2) | (1 << 1) | (1 << 0); 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32_t r = rnd_; 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd_ = (r << 1) ^ ((static_cast<int32_t>(r) >> 31) & kPoly); 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Next point is "rnd_ % (sample_period)". I.e., average 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // increment is "sample_period/2". 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int flag_value = FLAGS_mock_tcmalloc_sample_parameter; 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int last_flag_value = -1; 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (flag_value != last_flag_value) { 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // There should be a spinlock here, but this code is 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for benchmarking only. 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sample_period = 1048583; 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_flag_value = flag_value; 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes_until_sample_ += rnd_ % sample_period; 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (k > (static_cast<size_t>(-1) >> 2)) { 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If the user has asked for a huge allocation then it is possible 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for the code below to loop infinitely. Just return (note that 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this throws off the sampling accuracy somewhat, but a user who 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is allocating more than 1G of memory at a time can live with a 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // minor inaccuracy in profiling of small allocations, and also 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // would rather not wait for the loop below to terminate). 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (bytes_until_sample_ < k) { 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Increase bytes_until_sample_ by enough average sampling periods 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (sample_period >> 1) to allow us to sample past the current 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // allocation. 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes_until_sample_ += (sample_period >> 1); 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes_until_sample_ -= k; 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline bool OldSampler::SampleAllocation(size_t k) { 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (bytes_until_sample_ < k) { 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PickNextSample(k); 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes_until_sample_ -= k; 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This checks that the stated maximum value for the 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tcmalloc_sample_parameter flag never overflows bytes_until_sample_ 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, bytes_until_sample_Overflow_Underflow) { 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t one = 1; 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // sample_parameter = 0; // To test the edge case 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t sample_parameter_array[4] = {0, 1, one<<19, one<<58}; 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < 4; i++) { 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t sample_parameter = sample_parameter_array[i]; 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "sample_parameter = " << sample_parameter; 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double sample_scaling = - log(2.0) * sample_parameter; 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Take the top 26 bits as the random number 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (This plus the 1<<26 sampling bound give a max step possible of 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1209424308 bytes.) 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t prng_mod_power = 48; // Number of bits in prng 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // First, check the largest_prng value 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t largest_prng_value = (static_cast<uint64_t>(1)<<48) - 1; 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double q = (largest_prng_value >> (prng_mod_power - 26)) + 1.0; 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("q = %f\n", q); 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("FastLog2(q) = %f\n", sampler.FastLog2(q)); 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("log2(q) = %f\n", log(q)/log(2.0)); 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Replace min(sampler.FastLog2(q) - 26, 0.0) with 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (sampler.FastLog2(q) - 26.000705) when using that optimization 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t smallest_sample_step 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = static_cast<uint64_t>(min(sampler.FastLog2(q) - 26, 0.0) 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * sample_scaling + 1); 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Smallest sample step is " << smallest_sample_step; 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t cutoff = static_cast<uint64_t>(10) 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (sample_parameter/(one<<24) + 1); 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Acceptable value is < " << cutoff; 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This checks that the answer is "small" and positive 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(smallest_sample_step, cutoff); 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Next, check with the smallest prng value 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t smallest_prng_value = 0; 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) q = (smallest_prng_value >> (prng_mod_power - 26)) + 1.0; 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << StringPrintf("q = %f\n", q); 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Replace min(sampler.FastLog2(q) - 26, 0.0) with 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (sampler.FastLog2(q) - 26.000705) when using that optimization 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t largest_sample_step 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) = static_cast<uint64_t>(min(sampler.FastLog2(q) - 26, 0.0) 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * sample_scaling + 1); 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Largest sample step is " << largest_sample_step; 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(largest_sample_step, one<<63); 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(largest_sample_step, smallest_sample_step); 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Test that NextRand is in the right range. Unfortunately, this is a 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// stochastic test which could miss problems. 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, NextRand_range) { 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t one = 1; 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The next number should be (one << 48) - 1 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t max_value = (one << 48) - 1; 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t x = (one << 55); 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int n = 22; // 27; 5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Running sampler.NextRandom 1<<" << n << " times"; 5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i <= (1<<n); i++) { // 20 mimics sampler.Init() 5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x = sampler.NextRandom(x); 5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(x, max_value); 5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests certain arithmetic operations to make sure they compute what we 5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// expect them too (for testing across different platforms) 5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, arithmetic_1) { 5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t rnd; // our 48 bit random number, which we don't trust 5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t prng_mod_power = 48; 5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t one = 1; 5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd = one; 5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t max_value = (one << 48) - 1; 5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i <= (1>>27); i++) { // 20 mimics sampler.Init() 6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd = sampler.NextRandom(rnd); 6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LE(rnd, max_value); 6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double q = (rnd >> (prng_mod_power - 26)) + 1.0; 6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(q, 0); // << rnd << " " << prng_mod_power; 6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Test some potentially out of bounds value for rnd 6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 1; i <= 66; i++) { 6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rnd = one << i; 6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double q = (rnd >> (prng_mod_power - 26)) + 1.0; 6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "rnd = " << rnd << " i=" << i << " q=" << q; 6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(q, 0); 6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << " rnd=" << rnd << " i=" << i << " prng_mod_power" << prng_mod_power; 6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void test_arithmetic(uint64_t rnd) { 6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint64_t prng_mod_power = 48; // Number of bits in prng 6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t shifted_rnd = rnd >> (prng_mod_power - 26); 6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(shifted_rnd, 0); 6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_LT(shifted_rnd, (1<<26)); 6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << shifted_rnd; 6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << static_cast<double>(shifted_rnd); 6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(static_cast<double>(static_cast<uint32_t>(shifted_rnd)), 0); 6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << " rnd=" << rnd << " srnd=" << shifted_rnd; 6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GE(static_cast<double>(shifted_rnd), 0); 6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // << " rnd=" << rnd << " srnd=" << shifted_rnd; 6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double q = static_cast<double>(shifted_rnd) + 1.0; 6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GT(q, 0); 6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Tests certain arithmetic operations to make sure they compute what we 6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// expect them too (for testing across different platforms) 6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// know bad values under with -c dbg --cpu piii for _some_ binaries: 6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// rnd=227453640600554 6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// shifted_rnd=54229173 6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (hard to reproduce) 6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sampler, arithmetic_2) { 6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t rnd = 227453640600554LL; 6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) test_arithmetic(rnd); 6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// It's not really a test, but it's good to know 6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(Sample, size_of_class) { 6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::Sampler sampler; 6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sampler.Init(1); 6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Size of Sampler class is: " << sizeof(tcmalloc::Sampler); 6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG(INFO) << "Size of Sampler object is: " << sizeof(sampler); 6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Make sure sampling is enabled, or the tests won't work right. 6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DECLARE_int64(tcmalloc_sample_parameter); 6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int main(int argc, char **argv) { 6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (FLAGS_tcmalloc_sample_parameter == 0) 6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FLAGS_tcmalloc_sample_parameter = 524288; 6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return RUN_ALL_TESTS(); 6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 658