1 /** 2 Various simple benchmarks for the `checkedint` package. 3 4 Copyright: Copyright Thomas Stuart Bockman 2015 5 License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0). 6 Authors: Thomas Stuart Bockman 7 **/ 8 module checkedint.tests.benchmark; 9 import checkedint, checkedint.flags, checkedint.traits; 10 alias IFP = IntFlagPolicy; 11 12 import std.algorithm, std.stdio; 13 import std.meta : AliasSeq; 14 15 @safe: 16 17 void benchMacro() 18 { 19 benchMacro!"trialPrimes"(); 20 benchMacro!"collatzSort"(); 21 } 22 23 ulong checkSum; 24 bool invalid; 25 void benchMacro(string testStr)() 26 { 27 import std.conv : to; 28 import std.datetime : benchmark, Duration; 29 30 mixin("alias test = " ~ testStr ~ ";"); 31 writeln(); 32 write("Running "); write(testStr); writeln("() benchmark... "); 33 function() @trusted { stdout.flush(); }(); 34 35 checkSum = 0; 36 test!int(); 37 enum trials = 3; 38 enum laps = 3; 39 const compSum = checkSum * laps * trials; 40 41 foreach (Vstr; AliasSeq!("int", "uint", "long", "ulong")) 42 { 43 foreach (Nstr; AliasSeq!( 44 Vstr, 45 "SafeInt!(" ~ Vstr ~ ", IFP.sticky)", 46 "SafeInt!(" ~ Vstr ~ ", IFP.asserts)", 47 "SafeInt!(" ~ Vstr ~ ", IFP.throws)", 48 "SmartInt!(" ~ Vstr ~ ", IFP.sticky)", 49 "SmartInt!(" ~ Vstr ~ ", IFP.asserts)", 50 "SmartInt!(" ~ Vstr ~ ", IFP.throws)")) 51 { 52 mixin("alias N = " ~ Nstr ~ ";"); 53 54 checkSum = 0; 55 invalid = false; 56 writef("%40s: ", Nstr); 57 58 auto best = Duration.max; 59 foreach (i; 0 .. trials) 60 { 61 const r = to!Duration(benchmark!(test!N)(laps)[0]) / laps; 62 if (r < best) 63 best = r; 64 } 65 66 if (checkSum != compSum) 67 write("!CHECKSUM "); 68 if (invalid) 69 write("!INVALID "); 70 writeln(to!Duration(best)); 71 } 72 } 73 74 writeln("DONE"); 75 } 76 77 template SafeFold(N) 78 { 79 template SafeFold(real folded) 80 { 81 alias BN = BasicScalar!N; 82 static assert(BN.min <= folded && folded <= BN.max); 83 enum SafeFold = cast(BN)folded; 84 } 85 } 86 87 // Unsafe high-speed shims: 88 private pragma(inline, true) 89 { 90 auto mulPow2(N, M)(const N left, const M exp) 91 { 92 return left << exp; 93 } 94 auto divPow2(N, M)(const N left, const M exp) 95 { 96 return left >> exp; 97 } 98 auto modPow2(N, M)(const N left, const M exp) 99 { 100 return left & ~(~cast(N)0 << exp); 101 } 102 103 auto idx(N)(const N num) 104 { 105 static if (isCheckedInt!N) 106 return num.idx; 107 else static if (isSigned!N) 108 return cast(ptrdiff_t)num; 109 else 110 return cast(size_t)num; 111 } 112 } 113 114 void trialPrimes(N)() 115 { 116 alias V = SafeFold!N; 117 118 static auto floorSqrt(N n) 119 { 120 assert(n >= V!0); 121 122 enum N maxT = isSigned!N? 123 V!((1414L.mulPow2((N.sizeof * 4) - 11)) - 1L) : 124 V!((1L.mulPow2(N.sizeof * 4)) - 1L); 125 N t = min((n/V!2 + V!1), maxT); 126 N r0 = t; 127 N sq0 = r0 * r0; 128 assert(n <= sq0); 129 130 while (t >= V!1) 131 { 132 if (sq0 < n) 133 { 134 const r1 = r0 + t; 135 const sq1 = r1 * r1; 136 137 if (sq1 <= n) 138 { 139 r0 = r1; 140 sq0 = sq1; 141 } 142 else 143 t /= V!2; 144 } 145 else if (sq0 > n) 146 { 147 r0 = r0 - t; 148 sq0 = r0 * r0; 149 150 t /= V!2; 151 } 152 else 153 break; 154 } 155 156 return r0; 157 } 158 159 enum PrimeCount = V!40_000; 160 N[PrimeCount] primes; 161 N[PrimeCount] primeRoots; 162 163 N p = V!0; 164 primes[idx(p)] = N.max; 165 N n = V!2; 166 while (true) 167 { 168 const N rootN = floorSqrt(n); 169 170 bool pass = true; 171 for (N dP = V!0; primes[idx(dP)] <= rootN; ++dP) 172 { 173 if (n % primes[idx(dP)] == V!0) 174 { 175 pass = false; 176 break; 177 } 178 } 179 180 if (pass) 181 { 182 primes[idx(p)] = n; 183 primeRoots[idx(p)] = rootN; 184 185 ++p; 186 if (p < PrimeCount) 187 primes[idx(p)] = N.max; 188 else 189 break; 190 } 191 192 ++n; 193 } 194 195 N subSum = V!0; 196 for (N pu = V!0; pu < PrimeCount; ++pu) 197 subSum += primeRoots[idx(pu)]; 198 checkSum += subSum.bscal; 199 invalid = invalid || IntFlags.local; 200 IntFlags.local.clear(); 201 202 /+for (N q = 0; q < p; ++q) { 203 write(primes[idx(q)]); 204 write(" : "); 205 write(primeRoots[idx(q)]); 206 if (q % 8 != 7) 207 write(", "); 208 else 209 writeln(); 210 } 211 writeln(); 212 stdin.readln();+/ 213 } 214 215 void collatzSort(N)() 216 { 217 alias V = SafeFold!N; 218 219 static void quickSort(N[] array, N lowX, N highX) 220 { 221 if (lowX >= highX) 222 return; 223 224 N pivotX = (lowX + highX).divPow2(1u); 225 N pivotV = array[idx(pivotX)]; 226 array[idx(pivotX)] = array[idx(highX)]; 227 array[idx(highX)] = pivotV; 228 229 N storeX = lowX; 230 N iX = lowX; 231 while (iX < highX) 232 { 233 const iV = array[idx(iX)]; 234 if (iV < pivotV) 235 { 236 array[idx(iX)] = array[idx(storeX)]; 237 array[idx(storeX)] = iV; 238 ++storeX; 239 } 240 ++iX; 241 } 242 pivotX = storeX; 243 244 pivotV = array[idx(pivotX)]; 245 array[idx(pivotX)] = array[idx(highX)]; 246 array[idx(highX)] = pivotV; 247 248 quickSort(array, lowX, pivotX - V!1); 249 quickSort(array, pivotX + V!1, highX); 250 } 251 252 enum N maxN = V!113_382; 253 N[idx(maxN)] finalIs; 254 255 for (N n = V!0; n < maxN; ++n) 256 { 257 N i = V!0; 258 N ai = n + V!1; 259 while (ai != V!1) 260 { 261 if (ai.modPow2(1u) == V!0) 262 ai = ai.divPow2(1u); 263 else 264 ai = V!3*ai + V!1; 265 266 ++i; 267 } 268 269 finalIs[idx(n)] = i; 270 } 271 272 quickSort(finalIs, N(V!0), maxN - V!1); 273 274 N subSum = finalIs[0]; 275 for (N x = V!1; x < maxN; ++x) 276 { 277 subSum += finalIs[idx(x)]; 278 if (finalIs[idx(x)] < finalIs[idx(x - V!1)]) 279 invalid = true; 280 } 281 checkSum += subSum.bscal; 282 invalid = invalid || IntFlags.local; 283 IntFlags.local.clear(); 284 }