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 }