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