1 /** Extensions to std.datetime_ex.benchmark. 2 3 Copyright: Per Nordlöw 2022-. 4 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 5 Authors: $(WEB Per Nordlöw) 6 7 TODO: Use ggplot or similar to visualize results. 8 */ 9 module nxt.benchmark_ex; 10 11 /** Behavior or reservation of space for a specific implicit length/size/count. 12 */ 13 enum ReserveSupport 14 { 15 no, ///< Reservation is not (yet) supported. 16 yes, ///< Reservation is supported. 17 always, ///< Reservation is not needed because of unconditional pre-allocation, either static or dynamic. 18 } 19 20 struct Results 21 { 22 import core.time : Duration; 23 @property void toString(Sink)(ref scope Sink sink) const 24 { 25 import std.format : formattedWrite; 26 foreach (memberName; __traits(allMembers, typeof(this))) 27 { 28 const member = __traits(getMember, this, memberName); 29 alias Member = typeof(member); 30 static if (is(immutable Member == immutable Duration)) 31 { 32 if (member == Member.init) 33 continue; 34 sink.formattedWrite("%s: %s ns/op", 35 memberName, 36 cast(double)(member).total!"nsecs" / elementCount); 37 } 38 } 39 } 40 string typeName; 41 size_t elementCount; 42 size_t runCount; 43 private Duration _insertWithoutGrowthTime; 44 private Duration _insertWithGrowthTime; 45 private Duration _removeTime; 46 private Duration _containsTime; 47 private Duration _inTime; 48 private Duration _rehashTime; 49 private Duration _inAfterRehashTime; 50 private Duration _indexTime; 51 private Duration _appendTime; 52 } 53 54 /// Number of run per benchmark. 55 debug 56 static immutable runCountDefault = 3; // lighter test in debug mode 57 else 58 static immutable runCountDefault = 10; 59 60 /// Formatting uses some extra space but should be removed when outputting to plots. 61 static immutable formatNsPerOp = "%6.1f ns/op"; 62 63 /** Benchmark append operation available in type `A` with test source `S`. 64 */ 65 Results benchmarkAppendable(A, Sample, Source)(in Source testSource, in size_t runCount = runCountDefault) 66 { 67 import core.time : Duration; 68 import std.datetime : MonoTime; 69 import std.conv : to; 70 import std.algorithm.searching : minElement, maxElement; 71 import std.stdio : writef, writefln; 72 73 ReserveSupport reserveSupport; 74 auto results = typeof(return)(A.stringof, testSource.length, runCount); 75 76 writef("- "); 77 78 scope spans = new Duration[runCount]; 79 80 A _ = makeWithRequestedCapacity!(A)(0, reserveSupport); 81 foreach (const runIx; 0 .. runCount) 82 { 83 A a = makeWithRequestedCapacity!(A)(results.elementCount, reserveSupport); 84 const start = MonoTime.currTime(); 85 foreach (immutable i; testSource) 86 { 87 static if (is(typeof(a ~= i))) 88 a ~= i; 89 else static if (is(typeof(a ~= i.to!Sample))) 90 a ~= i.to!Sample; 91 else static if (is(typeof(a.put(i)))) 92 a.put(i); 93 else static if (is(typeof(a.put(i.to!Sample)))) 94 a.put(i.to!Sample); 95 else 96 static assert(0, "Cannot append a `" ~ typeof(i).stringof ~ "` to a `" ~ A.stringof ~ "`"); 97 } 98 spans[runIx] = MonoTime.currTime() - start; 99 static if (__traits(hasMember, A, `clear`) && 100 is(typeof(a.clear()))) 101 a.clear(); 102 } 103 results._appendTime = spans[].minElement(); 104 writef("append (%s) (~=): "~formatNsPerOp, 105 reserveSupport == ReserveSupport.no ? "no growth" : "with growth", 106 cast(double)(results._appendTime).total!"nsecs" / results.elementCount); 107 108 writefln(` for %s`, A.stringof); 109 110 return results; 111 } 112 113 /** Benchmark set (container) type `A` with test source `S`. 114 */ 115 Results benchmarkSet(A, Sample, Source)(in Source testSource, in size_t runCount = runCountDefault) 116 // TODO: if (isSet!A) 117 { 118 import core.time : Duration; 119 import std.datetime : MonoTime; 120 import std.conv : to; 121 import std.stdio : writef, writefln, writeln; 122 import std.algorithm.searching : minElement, maxElement; 123 import nxt.address : AlignedAddress; 124 125 alias Address = AlignedAddress!1; 126 127 ReserveSupport reserveSupport; 128 scope spans = new Duration[runCount]; 129 auto results = typeof(return)(A.stringof, testSource.length, runCount); 130 131 writef("- "); 132 133 A a; 134 { // needs scope 135 foreach (const runIx; 0 .. runCount) 136 { 137 const start = MonoTime.currTime(); 138 foreach (immutable i; testSource) 139 { 140 static if (__traits(hasMember, A, `ElementType`) && 141 is(A.ElementType == ubyte[])) 142 a.insert(i.toUbytes); 143 else 144 { 145 static if (__traits(hasMember, A, `ElementType`)) 146 { 147 static if (is(A.ElementType == Address)) 148 const element = A.ElementType(i + 1); ///< Start at 1 instead of 0 because `Address` uses 0 for `nullValue`. 149 else static if (is(A.ElementType : string) || 150 is(typeof(A.ElementType(string.init)))) 151 const element = A.ElementType(to!string(i)); 152 else 153 const element = A.ElementType(i); 154 } 155 else 156 const element = i; 157 a.insert(element); 158 } 159 } 160 spans[runIx] = MonoTime.currTime() - start; 161 static if (__traits(hasMember, A, `clear`) && 162 is(typeof(a.clear()))) 163 if (runIx+1 != runCount) 164 a.clear(); // clear all but the last one needed in contains below 165 } 166 results._insertWithGrowthTime = spans[].minElement(); 167 writef("insert (with growth): "~formatNsPerOp, 168 cast(double)(results._insertWithGrowthTime).total!"nsecs" / results.elementCount); 169 } 170 171 { // needs scope 172 const start = MonoTime.currTime(); 173 size_t hitCount = 0; 174 foreach (immutable i; testSource) 175 { 176 static if (__traits(hasMember, A, `ElementType`) && 177 is(A.ElementType == ubyte[])) 178 hitCount += a.contains(i.toUbytes); 179 else 180 { 181 static if (__traits(hasMember, A, `ElementType`)) 182 { 183 static if (is(A.ElementType == Address)) 184 const element = A.ElementType(i + 1); ///< Start at 1 instead of 0 because `Address` uses 0 for `nullValue`. 185 else static if (is(A.ElementType : string) || 186 is(typeof(A.ElementType(string.init)))) 187 const element = A.ElementType(to!string(i)); 188 else 189 const element = A.ElementType(i); // wrap in `i` in `Nullable` 190 } 191 else 192 const element = i; 193 static if (__traits(hasMember, A, "contains")) 194 hitCount += a.contains(element); 195 else static if (is(typeof(a.contains(element)) == bool)) 196 hitCount += a.contains(element); 197 else static if (is(typeof(element in a) == bool)) 198 hitCount += element in a; 199 else 200 static assert(0, 201 "Cannot check that " ~ 202 typeof(a).stringof ~ 203 " contains " ~ 204 typeof(element).stringof); 205 } 206 } 207 const ok = hitCount == results.elementCount; // for side effect in output 208 results._containsTime = MonoTime.currTime() - start; 209 writef(", contains: "~formatNsPerOp~" ns/op (%s)", 210 cast(double)(results._containsTime).total!"nsecs" / results.elementCount, 211 ok ? "OK" : "ERR"); 212 } 213 214 const _ = makeWithRequestedCapacity!(A)(0, reserveSupport); 215 if (reserveSupport) 216 { 217 foreach (const runIx; 0 .. runCount) 218 { 219 A b = makeWithRequestedCapacity!(A)(results.elementCount, reserveSupport); 220 const start = MonoTime.currTime(); 221 foreach (immutable i; testSource) 222 { 223 static if (__traits(hasMember, A, `ElementType`) && 224 is(A.ElementType == ubyte[])) 225 b.insert(i.toUbytes); 226 else 227 { 228 static if (__traits(hasMember, A, `ElementType`)) 229 { 230 static if (is(A.ElementType == Address)) 231 const element = A.ElementType(i + 1); ///< Start at 1 instead of 0 because `Address` uses 0 for `nullValue`. 232 else static if (is(A.ElementType : string) || 233 is(typeof(A.ElementType(string.init)))) 234 const element = A.ElementType(to!string(i)); 235 else 236 const element = A.ElementType(i); // wrap in `i` in `Nullable` 237 } 238 else 239 const element = i; 240 b.insert(element); 241 } 242 } 243 spans[runIx] = MonoTime.currTime() - start; 244 static if (__traits(hasMember, A, `clear`) && 245 is(typeof(b.clear()))) 246 b.clear(); // TODO why does this fail for `RadixTreeMap`? 247 248 } 249 results._insertWithoutGrowthTime = spans[].minElement(); 250 writef(", insert (no growth): "~formatNsPerOp, 251 cast(double)(results._insertWithoutGrowthTime).total!"nsecs" / results.elementCount); 252 } 253 254 writef(` for %s`, A.stringof); 255 256 static if (__traits(hasMember, A, `binCounts`)) 257 writef(" %s", a.binCounts()); 258 static if (__traits(hasMember, A, `smallBinCapacity`)) 259 writef(" smallBinCapacity:%s", A.smallBinCapacity); 260 static if (__traits(hasMember, A, `averageProbeCount`)) 261 writef(" averageProbeCount:%s", a.averageProbeCount); 262 263 writeln(); 264 265 return results; 266 } 267 268 /** Benchmark map (container) type `A` with test source `S`. 269 */ 270 Results benchmarkMap(A, Sample, Source)(in Source testSource, in size_t runCount = runCountDefault) 271 // TODO: if (isMap!A || __traits(isAssociativeArray, A)) 272 { 273 import core.time : Duration; 274 import std.datetime : MonoTime; 275 import std.conv : to; 276 import std.stdio : writef, writefln, writeln; 277 import std.algorithm.searching : minElement, maxElement; 278 import nxt.address : AlignedAddress; 279 280 alias Address = AlignedAddress!1; 281 282 ReserveSupport reserveSupport; 283 scope spans = new Duration[runCount]; 284 auto results = typeof(return)(A.stringof, testSource.length, runCount); 285 286 writef("- "); 287 288 // determine key and value type. TODO: extract to trait `KeyValueType(A)` 289 static if (is(A : V[K], K, V)) { 290 alias KeyType = K; 291 alias ValueType = K; 292 } else { 293 // determine key type. TODO: extract to trait `KeyType(A)` 294 static if (is(A.KeyType)) { 295 alias KeyType = A.KeyType; 296 } else static if (is(typeof(A.KeyValue.key))) { // StringMap 297 alias KeyType = typeof(A.KeyValue.key); 298 } else static if (is(immutable typeof(A.keys()) == immutable K[], K)) { // emsi HashMap 299 alias KeyType = K; 300 } else static if (__traits(hasMember, A, "byKey")) { // emsi HashMap 301 import std.range.primitives : std_ElementType = ElementType; 302 alias KeyType = std_ElementType!(typeof(A.init.byKey())); 303 } else { 304 static assert(0, "Could not determine key type of " ~ A.stringof ~ " " ~ typeof(A.keys()).stringof); 305 } 306 // determine value type. TODO: extract to trait `ValueType(A)` 307 static if (is(A.ValueType)) { 308 alias ValueType = A.ValueType; 309 } else static if (is(typeof(A.KeyValue.value))) { // StringMap 310 alias ValueType = typeof(A.KeyValue.value); 311 } else static if (__traits(hasMember, A, "byValue")) { // emsi HashMap 312 import std.range.primitives : std_ElementType = ElementType; 313 alias ValueType = std_ElementType!(typeof(A.init.byValue())); 314 } else { 315 static assert(0, "Could not determine value type of " ~ A.stringof); 316 } 317 } 318 319 // determine element type. TODO: extract to trait `ElementType(A)` or reuse `std.primitives.ElementType` 320 static if (is(A.ElementType)) { 321 alias ElementType = A.ElementType; 322 } else static if (is(A.KeyValue)) { // StringMap 323 alias ElementType = A.KeyValue; 324 } else static if (__traits(hasMember, A, "byKeyValue") || // emsi HashMap 325 !is(typeof(A.init.byKeyValue) == void)) { 326 import std.range.primitives : std_ElementType = ElementType; 327 alias ElementType = std_ElementType!(typeof(A.init.byKeyValue())); 328 } else { 329 static assert(0, "Could not determine element type of " ~ A.stringof); 330 } 331 332 // allocate 333 const keys = iotaArrayOf!(KeyType)(0, results.elementCount); 334 335 A a; 336 337 // insert/opIndex without preallocation via void capacity(size_t) 338 { 339 foreach (const runIx; 0 .. runCount) 340 { 341 const start = MonoTime.currTime(); 342 foreach (immutable i; testSource) 343 { 344 static if (is(typeof(A.init.insert(ElementType.init)))) 345 { 346 static if (is(KeyType == Address)) 347 const element = ElementType(Address(keys[i] + 1), // avoid `Address.null Value` 348 ValueType.init); 349 else 350 const element = ElementType(keys[i], ValueType.init); 351 a.insert(element); 352 } 353 else 354 a[keys[i]] = ValueType.init; // AAs 355 } 356 spans[runIx] = MonoTime.currTime() - start; 357 } 358 results._insertWithGrowthTime = spans[].minElement(); 359 writef("insert (with growth): "~formatNsPerOp, 360 cast(double)(results._insertWithGrowthTime).total!"nsecs" / results.elementCount); 361 } 362 363 // contains 364 static if (is(typeof(A.init.contains(KeyType.init)) : bool)) 365 { 366 { 367 bool okAll = true; 368 foreach (const runIx; 0 .. runCount) 369 { 370 const start = MonoTime.currTime(); 371 size_t hitCount = 0; 372 foreach (immutable i; testSource) 373 { 374 static if (is(KeyType == Address)) 375 hitCount += a.contains(Address(keys[i] + 1)); // avoid `Address.nullValue` 376 else 377 hitCount += a.contains(keys[i]) ? 1 : 0; 378 } 379 const ok = hitCount == results.elementCount; // for side effect in output 380 if (!ok) 381 okAll = false; 382 spans[runIx] = MonoTime.currTime() - start; 383 } 384 results._containsTime = spans[].minElement(); 385 writef(", contains: "~formatNsPerOp~" ns/op (%s)", 386 cast(double)(results._containsTime).total!"nsecs" / results.elementCount, 387 okAll ? "OK" : "ERR"); 388 } 389 } 390 391 // in 392 { 393 bool okAll = true; 394 foreach (const runIx; 0 .. runCount) 395 { 396 const start = MonoTime.currTime(); 397 size_t hitCount = 0; 398 foreach (immutable i; testSource) 399 { 400 static if (is(KeyType == Address)) 401 hitCount += cast(bool)(Address(keys[i] + 1) in a); // avoid `Address.nullValue` 402 else 403 hitCount += cast(bool)(keys[i] in a); 404 } 405 const ok = hitCount == results.elementCount; // for side effect in output 406 if (!ok) 407 okAll = false; 408 spans[runIx] = MonoTime.currTime() - start; 409 } 410 results._inTime = spans[].minElement(); 411 writef(", in: "~formatNsPerOp~" ns/op (%s)", 412 cast(double)(results._inTime).total!"nsecs" / results.elementCount, 413 okAll ? "OK" : "ERR"); 414 } 415 416 // rehash (AAs) + in 417 static if (is(typeof(a.rehash()))) 418 { 419 // rehash 420 foreach (const runIx; 0 .. runCount) 421 { 422 const start = MonoTime.currTime(); 423 a.rehash(); 424 spans[runIx] = MonoTime.currTime() - start; 425 } 426 results._rehashTime = spans[].minElement(); 427 writef(", rehash: "~formatNsPerOp, 428 cast(double)(results._rehashTime).total!"nsecs" / results.elementCount); 429 // in 430 foreach (const runIx; 0 .. runCount) 431 { 432 const start = MonoTime.currTime(); 433 foreach (immutable i; testSource) 434 const hit = keys[i] in a; 435 spans[runIx] = MonoTime.currTime() - start; 436 } 437 results._inAfterRehashTime = spans[].minElement(); 438 writef(", in (after rehash): "~formatNsPerOp, 439 cast(double)(results._inAfterRehashTime).total!"nsecs" / results.elementCount); 440 } 441 442 A _ = makeWithRequestedCapacity!(A)(0, reserveSupport); 443 if (reserveSupport) 444 { 445 bool unsupported = false; 446 // insert/opIndex with preallocation via void capacity(size_t) 447 foreach (const runIx; 0 .. runCount) 448 { 449 A b = makeWithRequestedCapacity!(A)(results.elementCount, reserveSupport); 450 const start = MonoTime.currTime(); 451 foreach (immutable i; testSource) 452 { 453 static if (__traits(hasMember, A, "insert")) 454 { 455 static if (is(immutable A.KeyType == immutable Address)) 456 const key = Address(keys[i] + 1); // avoid `Address.nullValue` 457 else 458 const key = keys[i]; 459 static if (is(typeof(b.insert(key, ValueType.init)))) 460 b.insert(key, ValueType.init); 461 else static if (is(typeof(b.insert(ElementType(key, ValueType.init))))) 462 b.insert(ElementType(key, ValueType.init)); 463 else 464 { 465 pragma(msg, "Skipping unsupported insert for " ~ A.stringof); 466 unsupported = true; 467 } 468 } 469 else 470 b[keys[i]] = ValueType.init; 471 } 472 spans[runIx] = MonoTime.currTime() - start; 473 static if (__traits(hasMember, A, `clear`) && 474 is(typeof(b.clear()))) 475 b.clear(); 476 } 477 if (!unsupported) 478 { 479 results._insertWithoutGrowthTime = spans[].minElement(); 480 writef(", insert (no growth): "~formatNsPerOp, 481 cast(double)(results._insertWithoutGrowthTime).total!"nsecs" / results.elementCount); 482 } 483 } 484 485 writef(` for %s`, A.stringof); 486 487 static if (__traits(hasMember, A, `binCounts`)) 488 writef(" %s", a.binCounts()); 489 static if (__traits(hasMember, A, `smallBinCapacity`)) 490 writef(" smallBinCapacity:%s", A.smallBinCapacity); 491 static if (__traits(hasMember, A, `totalProbeCount`)) 492 writef(" averageProbeCount:%s", cast(double)a.totalProbeCount/a.length); 493 494 writeln(); 495 496 return results; 497 } 498 499 alias benchmarkAssociativeArray = benchmarkMap; 500 501 /** Make `A` and try setting its capacity to `results.elementCount`. 502 */ 503 auto makeWithRequestedCapacity(A)(size_t elementCount, out ReserveSupport reserveSupport) 504 { 505 static if (is(typeof(A.init.withCapacity(elementCount)))) 506 { 507 reserveSupport = ReserveSupport.yes; 508 return A.withCapacity(elementCount); 509 } 510 else 511 { 512 static if (is(A == class)) 513 auto a = new A(); 514 else static if (is(A == struct)) 515 auto a = A(); 516 else 517 A a; 518 519 static if (__traits(hasMember, A, `reserve`)) 520 { 521 static if (__traits(compiles, { a.reserve(elementCount); })) 522 { 523 a.reserve(elementCount); 524 reserveSupport = ReserveSupport.yes; 525 } 526 else static if (__traits(compiles, { a.reserve!uint(elementCount); })) 527 { 528 a.reserve!uint(elementCount); 529 reserveSupport = ReserveSupport.yes; 530 } 531 } 532 else static if (is(A == U[], U)) 533 { 534 // this doesn’t work aswell: 535 // import std.range.primitives : ElementType; 536 // return new ElementType!A[elementCount]; 537 a.reserve(elementCount); // See_Also: https://dlang.org/library/object/reserve.html 538 reserveSupport = ReserveSupport.yes; 539 return a; 540 } 541 else static if (is(A : V[K], K, V)) 542 { 543 static if (__traits(compiles, { a.reserve(elementCount); })) 544 { 545 a.reserve(elementCount); // builtin AA’s might get this later on 546 reserveSupport = ReserveSupport.yes; 547 } 548 } 549 else static if (is(typeof(a.reserve(elementCount)))) 550 { 551 a.reserve(elementCount); 552 reserveSupport = ReserveSupport.yes; 553 } 554 555 static if (__traits(isPOD, A)) 556 return a; 557 else 558 { 559 import std.algorithm.mutation : move; 560 return move(a); 561 } 562 } 563 } 564 565 T[] iotaArrayOf(T)(in size_t begin, in size_t end) 566 { 567 import std.typecons : Nullable; 568 569 typeof(return) es = new T[end]; 570 foreach (immutable i; begin .. end) 571 { 572 static if (is(typeof(T(i)))) // if possible 573 es[i] = T(i); // try normal construction 574 else 575 { 576 import std.conv : to; 577 static if (is(typeof(T(i)))) 578 es[i] = T(i); 579 else static if (is(typeof(T(i.to!string)))) 580 es[i] = T(i.to!string); 581 else static if (is(typeof(i.to!T))) 582 es[i] = i.to!T; 583 else static if (is(T == Nullable!(uint, uint.max))) // TODO: avoid this 584 es[i] = T(cast(uint)i); 585 else 586 static assert(0, "Cannot convert `" ~ typeof(i).stringof ~ "` to `" ~ T.stringof ~ "`"); 587 } 588 } 589 return es; 590 }