1 /******************************************************************************* 2 3 A timing statistics counter for any sort of transaction that takes a 4 microsecond to a second to complete. Collects the following statistical 5 information: 6 - a logarithmic time histogram with bins from ≥1µs to <1s, three bins per 7 power of ten in a stepping of 1 .. 2 .. 5 .., plus one bin for each <1µs 8 and ≥1s, 9 - the total number of transactions and the aggregated total completion time. 10 11 To reset all counters to zero use `TimeHistogram.init`. 12 13 copyright: Copyright (c) 2018 dunnhumby Germany GmbH. All rights reserved. 14 15 License: 16 Boost Software License Version 1.0. See LICENSE.txt for details. 17 18 *******************************************************************************/ 19 20 module ocean.math.TimeHistogram; 21 22 import ocean.transition; 23 24 /// ditto 25 struct TimeHistogram 26 { 27 import ocean.transition; 28 import ocean.core.Traits : FieldName; 29 30 /*************************************************************************** 31 32 The total aggregated transaction completion time in µs. 33 34 ***************************************************************************/ 35 36 public ulong total_time_micros; 37 38 /*************************************************************************** 39 40 The total number of transactions. 41 42 ***************************************************************************/ 43 44 public uint count; 45 46 /*************************************************************************** 47 48 The bins of the timing histogram. The stepping of the lower bounds of 49 the bins is, in µs: 50 51 0: 0; 52 1: 1; 2: 2; 3: 5; 53 4: 10; 5: 20; 6: 50; 54 7: 100; 8: 200; 9: 500; 55 10: 1,000; 11: 2,000; 12: 5,000; 56 13: 10,000; 14: 20,000; 15: 50,000; 57 16: 100,000; 17: 200,000; 18: 500,000; 58 19: 1,000,000 59 60 ***************************************************************************/ 61 62 public uint[20] bins; 63 64 /*************************************************************************** 65 66 Struct with one uint field per bin (see this.bins), named as follows: 67 from_0us ("from 0 microseconds"), from_1us, from_2us, from_5us, 68 from_10us, from_20us, from_50us, from_100us, from_200us, from_500us, 69 from_1ms, from_2ms, ..., 70 from_1s ("from 1 second") 71 72 Useful, for example, for logging the whole histogram. 73 74 ***************************************************************************/ 75 76 public struct Bins 77 { 78 /*********************************************************************** 79 80 Interprets the passed bins array as a Bins instance. 81 82 Params: 83 array = bins array to reinterpret 84 85 Returns: 86 the passed bins array as a Bins instance 87 88 ***********************************************************************/ 89 90 public static Bins fromArray ( typeof(TimeHistogram.bins) array ) 91 { 92 return *(cast(Bins*)array.ptr); 93 } 94 95 /*********************************************************************** 96 97 Sanity check that the offset of the fields of this struct match the 98 offsets of the elements of a TimeHistogram.bins array. (i.e. that 99 the fromArray() function can work as intended.) 100 101 ***********************************************************************/ 102 103 static assert(fieldOffsetsCorrect()); 104 105 /*********************************************************************** 106 107 Returns: 108 true if the offset of the fields of this struct match the 109 offsets of the elements of a TimeHistogram.bins array 110 111 ***********************************************************************/ 112 113 private static bool fieldOffsetsCorrect ( ) 114 { 115 foreach ( i, field; typeof(Bins.tupleof) ) 116 if ( Bins.tupleof[i].offsetof != i * TimeHistogram.init.bins[i].sizeof ) 117 return false; 118 return true; 119 } 120 121 /*********************************************************************** 122 123 CTFE generator of the fields of this struct. 124 125 Params: 126 suffixes = metric suffixes for the series of fields 127 128 Returns: 129 code for the series of fields dividing the specified order of 130 magnitude range into bands of [1, 2, 5]. (See unittest for 131 examples.) 132 133 ***********************************************************************/ 134 135 private static istring divisionBinVariables ( istring[] suffixes ) 136 in 137 { 138 assert(suffixes.length > 0); 139 } 140 body 141 { 142 enum type = typeof(TimeHistogram.bins[0]).stringof; 143 144 istring res; 145 146 res ~= type ~ " from_0" ~ suffixes[0] ~ ";"; 147 148 foreach ( suffix; suffixes[0..$-1] ) 149 foreach ( zeros; ["", "0", "00"] ) 150 foreach ( div; ["1", "2", "5"] ) 151 res ~= type ~ " from_" ~ div ~ zeros ~ suffix ~ ";"; 152 153 res ~= type ~ " from_1" ~ suffixes[$-1] ~ ";"; 154 155 return res; 156 } 157 158 unittest 159 { 160 test!("==")(divisionBinVariables(["us"]), "uint from_0us;uint from_1us;"); 161 test!("==")(divisionBinVariables(["us", "ms"]), 162 "uint from_0us;uint from_1us;uint from_2us;uint from_5us;uint from_10us;uint from_20us;uint from_50us;uint from_100us;uint from_200us;uint from_500us;uint from_1ms;"); 163 } 164 165 /*********************************************************************** 166 167 Fields. 168 169 ***********************************************************************/ 170 171 mixin(divisionBinVariables(["us", "ms", "s"])); 172 } 173 174 /*************************************************************************** 175 176 The number of fields of Bins must equal the length of the fixed-length 177 array this.bins. 178 179 ***************************************************************************/ 180 181 static assert(Bins.tupleof.length == bins.length); 182 183 /*************************************************************************** 184 185 Counts a transaction that took `us` µs to complete by incrementing the 186 corresponding histogram bin and the total number of transactions and 187 adding `us` to the total transaction time. 188 189 Params: 190 us = the transaction completion time in microseconds 191 192 Returns: 193 us 194 195 ***************************************************************************/ 196 197 public ulong countMicros ( ulong us ) 198 { 199 (&this).count++; 200 (&this).total_time_micros += us; 201 (&this).bins[binIndex(us)]++; 202 return us; 203 } 204 205 /*************************************************************************** 206 207 Returns: 208 the mean time (in microseconds) taken by each transaction (may, of 209 course, be NaN, if this.count == 0) 210 211 ***************************************************************************/ 212 213 public double mean_time_micros ( ) 214 in 215 { 216 assert((&this).count || !(&this).total_time_micros); 217 } 218 body 219 { 220 return cast(double)(&this).total_time_micros / (&this).count; 221 } 222 223 /*************************************************************************** 224 225 Gets the count of transactions in the specified bin. 226 227 Params: 228 bin_name = string name of the bin to get the count for. Must match 229 the name of one of the fields of Bins 230 231 Returns: 232 the number of transactions in the specified bin 233 234 ***************************************************************************/ 235 236 public ulong countFor ( istring bin_name ) ( ) 237 { 238 mixin("static assert(is(typeof(Bins.init." ~ bin_name ~ ")));"); 239 240 mixin("const offset = Bins.init." ~ bin_name ~ ".offsetof;"); 241 enum index = offset / this.bins[0].sizeof; 242 return this.bins[index]; 243 } 244 245 unittest 246 { 247 TimeHistogram histogram; 248 histogram.countMicros(7); 249 test!("==")(histogram.countFor!("from_5us")(), 1); 250 } 251 252 /*************************************************************************** 253 254 Returns: 255 the complete histogram as a Bins struct 256 257 ***************************************************************************/ 258 259 public Bins stats ( ) 260 { 261 return Bins.fromArray((&this).bins); 262 } 263 264 unittest 265 { 266 TimeHistogram histogram; 267 histogram.countMicros(7); 268 auto bins = histogram.stats(); 269 test!("==")(bins.from_5us, 1); 270 } 271 272 /*************************************************************************** 273 274 Calculates the bin index `i` from `us`: 275 276 - If us = 0 then i = 0. 277 - Otherwise, if us < 1_000_000 then i = floor(log_10(us) * 3) + 1. 278 - Otherwise i = bins.length - 1. 279 280 Params: 281 us = the microseconds value to calculate the bin index from 282 283 Returns: 284 the bin index. 285 286 ***************************************************************************/ 287 288 private static size_t binIndex ( size_t us ) 289 { 290 if (!us) 291 return 0; 292 293 static Immut!(size_t[4][2]) powers_of_10 = [ 294 [1, 10, 100, 1_000], 295 [1_000, 10_000, 100_000, 1_000_000] 296 ]; 297 298 foreach (size_t i, p1000; powers_of_10) 299 { 300 if (us < p1000[$ - 1]) 301 { 302 foreach (size_t j, p; p1000[1 .. $]) 303 { 304 if (us < p) 305 { 306 auto b = (i * cast(uint)(p1000.length - 1) + j) * 3 + 1; 307 if (us >= (p1000[j] * 2)) 308 { 309 b++; 310 b += (us >= (p / 2)); 311 } 312 return b; 313 } 314 } 315 assert(false); 316 } 317 } 318 319 return TimeHistogram.bins.length - 1; 320 } 321 } 322 323 version (UnitTest) 324 { 325 import ocean.core.Test; 326 } 327 328 unittest 329 { 330 TimeHistogram th; 331 332 // Tests if `expected` matches a) the sum of all bin counters and 333 // b) th.count. 334 void checkBinSum ( uint expected, istring f = __FILE__, int ln = __LINE__ ) 335 { 336 uint sum = 0; 337 foreach (bin; th.bins) 338 sum += bin; 339 test!("==")(th.count, sum, f, ln); 340 test!("==")(sum, expected, f, ln); 341 } 342 343 // 0µs: Should increment bins[0] and `count` to 1 and leave `total == 0`. 344 // All other bins should remain 0. 345 th.countMicros(0); 346 test!("==")(th.total_time_micros, 0); 347 test!("==")(th.count, 1); 348 test!("==")(th.bins[0], 1); 349 test!("==")(th.stats.from_0us, 1); 350 test!("==")(th.countFor!("from_0us"), 1); 351 foreach (bin; th.bins[1 .. $]) 352 test!("==")(bin, 0); 353 checkBinSum(1); 354 355 // 1.500ms: Should increment bins[10] to 1, `count` to 2 and `total` to 1500 356 // and leave bin[0] == 1. All other bins should remain 0. 357 th.countMicros(1500); 358 test!("==")(th.total_time_micros, 1500); 359 test!("==")(th.count, 2); 360 test!("==")(th.bins[0], 1); 361 test!("==")(th.stats.from_0us, 1); 362 test!("==")(th.countFor!("from_0us"), 1); 363 test!("==")(th.bins[10], 1); 364 test!("==")(th.stats.from_1ms, 1); 365 test!("==")(th.countFor!("from_1ms"), 1); 366 checkBinSum(2); 367 foreach (i, bin; th.bins) 368 { 369 switch (i) 370 { 371 default: 372 test!("==")(th.bins[i], 0); 373 goto case; 374 case 0, 10: 375 } 376 } 377 378 // 1,234.567890s (more than 0.999999s): Should increment bins[$ - 1] to 1, 379 // `count` to 3 and `total` to 1,234,567,890 + 1500 and leave bin[0] == 1 380 // and bin[10] == 1. All other bins should remain 0. 381 th.countMicros(1_234_567_890); 382 test!("==")(th.total_time_micros, 1_234_567_890 + 1500); 383 test!("==")(th.count, 3); 384 test!("==")(th.bins[0], 1); 385 test!("==")(th.stats.from_0us, 1); 386 test!("==")(th.countFor!("from_0us"), 1); 387 test!("==")(th.bins[10], 1); 388 test!("==")(th.stats.from_1ms, 1); 389 test!("==")(th.countFor!("from_1ms"), 1); 390 test!("==")(th.bins[$ - 1], 1); 391 test!("==")(th.stats.from_1s, 1); 392 test!("==")(th.countFor!("from_1s"), 1); 393 checkBinSum(3); 394 foreach (i, bin; th.bins) 395 { 396 switch (i) 397 { 398 default: 399 test!("==")(th.bins[i], 0); 400 goto case; 401 case 0, 10, th.bins.length - 1: 402 } 403 } 404 } 405 406 unittest 407 { 408 test!("==")(TimeHistogram.binIndex(0), 0); 409 test!("==")(TimeHistogram.binIndex(1), 1); 410 test!("==")(TimeHistogram.binIndex(555), 9); 411 test!("==")(TimeHistogram.binIndex(999_999), TimeHistogram.bins.length - 2); 412 test!("==")(TimeHistogram.binIndex(1_000_000), TimeHistogram.bins.length - 1); 413 test!("==")(TimeHistogram.binIndex(ulong.max), TimeHistogram.bins.length - 1); 414 }