1/*
2 Copyright (c) 2005-2019 Intel Corporation
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/**
18 The test checks that for different ranges of random numbers (from 0 to
19 [MinThread, MaxThread]) generated with different seeds the probability
20 of each number in the range deviates from the ideal random distribution
21 by no more than AcceptableDeviation percent.
22**/
23
24#define HARNESS_DEFAULT_MIN_THREADS 2
25#define HARNESS_DEFAULT_MAX_THREADS 32
26
27#define HARNESS_DEFINE_PRIVATE_PUBLIC 1
28#include "harness_inject_scheduler.h"
29
30#define TEST_TOTAL_SEQUENCE 0
31
32#include "harness.h"
33#include "tbb/atomic.h"
34
35//! Coefficient defining tolerable deviation from ideal random distribution
36const double AcceptableDeviation = 2.1;
37//! Tolerable probability of failure to achieve tolerable distribution
38const double AcceptableProbabilityOfOutliers = 1e-5;
39//! Coefficient defining the length of random numbers series used to estimate the distribution
40/** Number of random values generated per each range element. I.e. the larger is
41 the range, the longer is the series of random values. **/
42const uintptr_t SeriesBaseLen = 100;
43//! Number of random numbers series to generate
44const uintptr_t NumSeries = 100;
45//! Number of random number generation series with different seeds
46const uintptr_t NumSeeds = 100;
47
48tbb::atomic<uintptr_t> NumHighOutliers;
49tbb::atomic<uintptr_t> NumLowOutliers;
50
51inline void CheckProbability ( double probability, double expectedProbability, int index, int numIndices, void* seed ) {
52 double lowerBound = expectedProbability / AcceptableDeviation,
53 upperBound = expectedProbability * AcceptableDeviation;
54 if ( probability < lowerBound ) {
55 if ( !NumLowOutliers )
56 REMARK( "Warning: Probability %.3f of hitting index %d among %d elements is out of acceptable range (%.3f - %.3f) for seed %p\n",
57 probability, index, numIndices, lowerBound, upperBound, seed );
58 ++NumLowOutliers;
59 }
60 else if ( probability > upperBound ) {
61 if ( !NumHighOutliers )
62 REMARK( "Warning: Probability %.3f of hitting index %d among %d elements is out of acceptable range (%.3f - %.3f) for seed %p\n",
63 probability, index, numIndices, lowerBound, upperBound, seed );
64 ++NumHighOutliers;
65 }
66}
67
68struct CheckDistributionBody {
69 void operator() ( int id ) const {
70 uintptr_t randomRange = id + MinThread;
71 uintptr_t *curHits = new uintptr_t[randomRange]
72#if TEST_TOTAL_SEQUENCE
73 , *totalHits = new uintptr_t[randomRange]
74#endif
75 ;
76 double expectedProbability = 1./randomRange;
77 // Loop through different seeds
78 for ( uintptr_t i = 0; i < NumSeeds; ++i ) {
79 // Seed value mimics the one used by the TBB task scheduler
80 void* seed = (char*)&curHits + i * 16;
81 tbb::internal::FastRandom random( seed );
82 // According to Section 3.2.1.2 of Volume 2 of Knuth's Art of Computer Programming
83 // the following conditions must be hold for m=2^32:
84 ASSERT((random.c&1)!=0, "c is relatively prime to m");
85 ASSERT((random.a-1)%4==0, "a-1 is a multiple of p, for every prime p dividing m."
86 " And a-1 is a multiple of 4, if m is a multiple of 4");
87
88 memset( curHits, 0, randomRange * sizeof(uintptr_t) );
89#if TEST_TOTAL_SEQUENCE
90 memset( totalHits, 0, randomRange * sizeof(uintptr_t) );
91#endif
92 const uintptr_t seriesLen = randomRange * SeriesBaseLen,
93 experimentLen = NumSeries * seriesLen;
94 uintptr_t *curSeries = new uintptr_t[seriesLen], // circular buffer
95 randsGenerated = 0;
96 // Initialize statistics
97 while ( randsGenerated < seriesLen ) {
98 uintptr_t idx = random.get() % randomRange;
99 ++curHits[idx];
100#if TEST_TOTAL_SEQUENCE
101 ++totalHits[idx];
102#endif
103 curSeries[randsGenerated++] = idx;
104 }
105 while ( randsGenerated < experimentLen ) {
106 for ( uintptr_t j = 0; j < randomRange; ++j ) {
107 CheckProbability( double(curHits[j])/seriesLen, expectedProbability, j, randomRange, seed );
108#if TEST_TOTAL_SEQUENCE
109 CheckProbability( double(totalHits[j])/randsGenerated, expectedProbability, j, randomRange, seed );
110#endif
111 }
112 --curHits[curSeries[randsGenerated % seriesLen]];
113 int idx = random.get() % randomRange;
114 ++curHits[idx];
115#if TEST_TOTAL_SEQUENCE
116 ++totalHits[idx];
117#endif
118 curSeries[randsGenerated++ % seriesLen] = idx;
119 }
120 delete [] curSeries;
121 }
122 delete [] curHits;
123#if TEST_TOTAL_SEQUENCE
124 delete [] totalHits;
125#endif
126 }
127};
128
129struct rng {
130 tbb::internal::FastRandom my_fast_random;
131 rng (unsigned seed):my_fast_random(seed) {}
132 unsigned short operator()(){return my_fast_random.get();}
133};
134
135template <std::size_t seriesLen >
136struct SingleCheck{
137 bool operator()(unsigned seed)const{
138 std::size_t series1[seriesLen]={0};
139 std::size_t series2[seriesLen]={0};
140 std::generate(series1,series1+seriesLen,rng(seed));
141 std::generate(series2,series2+seriesLen,rng(seed));
142 return std::equal(series1,series1+seriesLen,series2);
143 }
144};
145
146template <std::size_t seriesLen ,size_t seedsNum>
147struct CheckReproducibilityBody:NoAssign{
148 unsigned short seeds[seedsNum];
149 const std::size_t grainSize;
150 CheckReproducibilityBody(std::size_t GrainSize): grainSize(GrainSize){
151 //first generate seeds to check on, and make sure that sequence is reproducible
152 ASSERT(SingleCheck<seedsNum>()(0),"Series generated by FastRandom must be reproducible");
153 std::generate(seeds,seeds+seedsNum,rng(0));
154 }
155
156 void operator()(int id)const{
157 for (size_t i=id*grainSize; (i<seedsNum)&&(i< ((id+1)*grainSize));++i ){
158 ASSERT(SingleCheck<seriesLen>()(i),"Series generated by FastRandom must be reproducible");
159 }
160 }
161
162};
163#include "tbb/tbb_thread.h"
164
165int TestMain () {
166 ASSERT( AcceptableDeviation < 100, NULL );
167 MinThread = max(MinThread, 2);
168 MaxThread = max(MinThread, MaxThread);
169 double NumChecks = double(NumSeeds) * (MaxThread - MinThread + 1) * (MaxThread + MinThread) / 2.0 * (SeriesBaseLen * NumSeries - SeriesBaseLen);
170 REMARK( "Number of distribution quality checks %g\n", NumChecks );
171 NumLowOutliers = NumHighOutliers = 0;
172 // Parallelism is used in this test only to speed up the long serial checks
173 // Essentially it is a loop over random number ranges
174 // Ideally tbb::parallel_for could be used to parallelize the outermost loop
175 // in CheckDistributionBody, but it is not used to avoid unit test contamination.
176 int P = tbb::tbb_thread::hardware_concurrency();
177 enum {reproducibilitySeedsToTest=1000};
178 enum {reproducibilitySeriesLen=100};
179 CheckReproducibilityBody<reproducibilitySeriesLen,reproducibilitySeedsToTest> CheckReproducibility(reproducibilitySeedsToTest/MaxThread);
180 while ( MinThread <= MaxThread ) {
181 int ThreadsToRun = min(P, MaxThread - MinThread + 1);
182 REMARK("Checking random range [%d;%d)\n", MinThread, MinThread+ThreadsToRun);
183 NativeParallelFor( ThreadsToRun, CheckDistributionBody() );
184 NativeParallelFor( ThreadsToRun, CheckReproducibility );
185 MinThread += P;
186 }
187 double observedProbabilityOfOutliers = (NumLowOutliers + NumHighOutliers) / NumChecks;
188 if ( observedProbabilityOfOutliers > AcceptableProbabilityOfOutliers ) {
189 if ( NumLowOutliers )
190 REPORT( "Warning: %d cases of too low probability of a given number detected\n", (int)NumLowOutliers );
191 if ( NumHighOutliers )
192 REPORT( "Warning: %d cases of too high probability of a given number detected\n", (int)NumHighOutliers );
193 ASSERT( observedProbabilityOfOutliers <= AcceptableProbabilityOfOutliers, NULL );
194 }
195 return Harness::Done;
196}
197