Mercurial > dovecot > core-2.2

annotate src/lib/timing.c @ 22955:812e5c961328

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fts: Indexing virtual mailbox didn't always index the last mails
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 03 May 2018 18:33:00 +0300
parents cb108f786fb4
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
22713
cb108f786fb4 Updated copyright notices to include the year 2018.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 21390
diff changeset
1 /* Copyright (c) 2015-2018 Dovecot authors, see the included COPYING file */
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 #include "lib.h"
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 #include "timing.h"
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
5 #include "sort.h"
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
7 /* In order to have a vaguely accurate 95th percentile, you need way
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
8 more than 20 in your subsample. */
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
9 #define TIMING_SUBSAMPLING_BUFFER (20*24) /* 20*24 fits in a page */
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
10
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 struct timing {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 unsigned int count;
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
13 bool sorted;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
14 uint64_t min;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
15 uint64_t samples[TIMING_SUBSAMPLING_BUFFER];
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
16 uint64_t max;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
17 uint64_t sum;
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18 };
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 struct timing *timing_init(void)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 return i_new(struct timing, 1);
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 void timing_deinit(struct timing **_timing)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 i_free_and_null(*_timing);
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29
20198
1779df80df17 lib: Added timing_reset()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 19552
diff changeset
30 void timing_reset(struct timing *timing)
1779df80df17 lib: Added timing_reset()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 19552
diff changeset
31 {
21389
59437f8764c6 global: Replaced all instances of memset(p, 0, sizeof(*p)) with the new i_zero() macro.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 20199
diff changeset
32 i_zero(timing);
20198
1779df80df17 lib: Added timing_reset()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 19552
diff changeset
33 }
1779df80df17 lib: Added timing_reset()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 19552
diff changeset
34
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
35 void timing_add_usecs(struct timing *timing, uint64_t usecs)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
36 {
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
37 if (timing->count < TIMING_SUBSAMPLING_BUFFER) {
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
38 timing->samples[timing->count] = usecs;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
39 if (timing->count == 0)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
40 timing->min = timing->max = usecs;
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41 } else {
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
42 unsigned int count = timing->count;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
43 unsigned int idx;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
44 if (count > RAND_MAX >> 6)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
45 idx = (rand()*((uint64_t)RAND_MAX+1) + rand()) % count;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
46 else
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
47 idx = rand() % count;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
48 if (idx < TIMING_SUBSAMPLING_BUFFER)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
49 timing->samples[idx] = usecs;
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
50 }
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
51
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
52 timing->count++;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
53 timing->sum += usecs;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
54 if (timing->max < usecs)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
55 timing->max = usecs;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
56 if (timing->min > usecs)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
57 timing->min = usecs;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
58 timing->sorted = FALSE;
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
59 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
60
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
61 unsigned int timing_get_count(const struct timing *timing)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
62 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
63 return timing->count;
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
64 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
65
19183
a1c9e2cc574b lib: Added timing_get_sum()
Timo Sirainen <tss@iki.fi>
parents: 19173
diff changeset
66 uint64_t timing_get_sum(const struct timing *timing)
a1c9e2cc574b lib: Added timing_get_sum()
Timo Sirainen <tss@iki.fi>
parents: 19173
diff changeset
67 {
a1c9e2cc574b lib: Added timing_get_sum()
Timo Sirainen <tss@iki.fi>
parents: 19173
diff changeset
68 return timing->sum;
a1c9e2cc574b lib: Added timing_get_sum()
Timo Sirainen <tss@iki.fi>
parents: 19173
diff changeset
69 }
a1c9e2cc574b lib: Added timing_get_sum()
Timo Sirainen <tss@iki.fi>
parents: 19173
diff changeset
70
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
71 uint64_t timing_get_min(const struct timing *timing)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
72 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
73 return timing->min;
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
74 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
75
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
76 uint64_t timing_get_max(const struct timing *timing)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78 return timing->max;
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 }
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 uint64_t timing_get_avg(const struct timing *timing)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82 {
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
83 if (timing->count == 0)
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 return 0;
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
85
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
86 return (timing->sum + timing->count/2) / timing->count;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
87 }
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
88
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
89 static void timing_ensure_sorted(struct timing *timing)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
90 {
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
91 if (timing->sorted)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
92 return;
20199
a4744c321f18 lib: Fixed crashes in timing_get_median() and timing_get_95th()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 20198
diff changeset
93
a4744c321f18 lib: Fixed crashes in timing_get_median() and timing_get_95th()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 20198
diff changeset
94 unsigned int count = (timing->count < TIMING_SUBSAMPLING_BUFFER)
a4744c321f18 lib: Fixed crashes in timing_get_median() and timing_get_95th()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 20198
diff changeset
95 ? timing->count
a4744c321f18 lib: Fixed crashes in timing_get_median() and timing_get_95th()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 20198
diff changeset
96 : TIMING_SUBSAMPLING_BUFFER;
a4744c321f18 lib: Fixed crashes in timing_get_median() and timing_get_95th()
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 20198
diff changeset
97 i_qsort(timing->samples, count, sizeof(*timing->samples),
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
98 uint64_cmp);
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
99 timing->sorted = TRUE;
19147
9add45266550 lib: Added a simple timing.h API for tracking min/max/avg for events.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
100 }
19173
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
101
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
102 uint64_t timing_get_median(const struct timing *timing)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
103 {
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
104 if (timing->count == 0)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
105 return 0;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
106 /* cast-away const - reading requires sorting */
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
107 timing_ensure_sorted((struct timing *)timing);
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
108 unsigned int count = (timing->count < TIMING_SUBSAMPLING_BUFFER)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
109 ? timing->count
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
110 : TIMING_SUBSAMPLING_BUFFER;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
111 unsigned int idx1 = (count-1)/2, idx2 = count/2;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
112 return (timing->samples[idx1] + timing->samples[idx2]) / 2;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
113 }
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
114
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
115 uint64_t timing_get_95th(const struct timing *timing)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
116 {
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
117 if (timing->count == 0)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
118 return 0;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
119 /* cast-away const - reading requires sorting */
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
120 timing_ensure_sorted((struct timing *)timing);
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
121 unsigned int count = (timing->count < TIMING_SUBSAMPLING_BUFFER)
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
122 ? timing->count
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
123 : TIMING_SUBSAMPLING_BUFFER;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
124 unsigned int idx = count - count/20 - 1;
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
125 return timing->samples[idx];
2f492fac75b7 lib: timings - added quantiles
Phil Carmody <phil@dovecot.fi>
parents: 19147
diff changeset
126 }