tests/linux: use Akaros's CFLAGS
[akaros.git] / user / benchutil / measure.c
1 /* Copyright (c) 2013 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Userspace functions for various measurements.
6  *
7  * For now, this is built into parlib.  We can pull it out in the future.  Many
8  * of the larger functions are in flux. */
9
10 #include <math.h>
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include <string.h>
14 #include <sys/param.h>
15
16 #ifdef __ros__
17  #include <parlib/tsc-compat.h>
18  #include <benchutil/measure.h>
19 #else
20  #include "include/benchutil/measure.h"
21 #endif /* __ros__ */
22
23 /* Basic stats computation and printing.
24  *
25  * All of these expect a 2D collection of samples, where the first array is an
26  * array of arrays of samples.  The first array's members are something like
27  * per-thread samples, where each thread fills in its
28  * data[thread_id][sample_number].  The samples should be ordered in
29  * chronological order.  Ultimately, the sample needs to produce a uint64_t
30  * (e.g. TSC tick). */
31
32 static void init_stats(struct sample_stats *stats)
33 {
34         stats->avg_time = 0;
35         stats->var_time = 0;
36         stats->max_time = 0;
37         stats->min_time = UINT64_MAX;
38         stats->lat_50 = 0;
39         stats->lat_75 = 0;
40         stats->lat_90 = 0;
41         stats->lat_99 = 0;
42         stats->total_samples = 0;
43 }
44
45 /* Could have options for printing for how many rows we want, how much we want
46  * to trim the max/min, and how many samples per bin. */
47 void compute_stats(void **data, int nr_i, int nr_j, struct sample_stats *stats)
48 {
49         uint64_t sample_time, hist_max_time, hist_min_time,
50                  lat_max_time, lat_min_time;
51         size_t hist_idx, lat_idx, hist_bin_sz, lat_bin_sz;
52         float accum_samples = 0.0, coef_var;
53         unsigned int *hist_times;
54         unsigned int *lat_times;
55         unsigned int nr_hist_bins = 75; /* looks reasonable when printed */
56         unsigned int nr_lat_bins = 500; /* affects granularity of lat perc */
57         unsigned int max_dots_per_row = 45; /* looks good with 80-wide col */
58         unsigned int max_hist_bin = 0;
59         #define HI_COEF_VAR 1.0
60
61         init_stats(stats);
62         /* First pass, figure out the min, max, avg, etc. */
63         for (int i = 0; i < nr_i; i++) {
64                 for (int j = 0; j < nr_j; j++) {
65                         /* get_sample returns 0 on success.  o/w, skip the
66                          * sample */
67                         /* depending on semantics, we could break */
68                         if (stats->get_sample(data, i, j, &sample_time))
69                                 continue;
70                         stats->total_samples++;
71                         stats->avg_time += sample_time;
72                         stats->max_time = sample_time > stats->max_time ?
73                                 sample_time : stats->max_time;
74                         stats->min_time = sample_time < stats->min_time ?
75                                 sample_time : stats->min_time;
76                 }
77         }
78         if (stats->total_samples < 2) {
79                 printf("Not enough samples (%llu) for avg and var\n",
80                        stats->total_samples);
81                 return;
82         }
83         stats->avg_time /= stats->total_samples;
84         /* Second pass, compute the variance.  Want to do this before the
85          * histograms, so we can trim the serious outliers */
86         for (int i = 0; i < nr_i; i++) {
87                 for (int j = 0; j < nr_j; j++) {
88                         if (stats->get_sample(data, i, j, &sample_time))
89                                 continue;
90                         /* var: (sum_i=1..n { (x_i - xbar)^2 }) / (n - 1)
91                          *
92                          * for info on n vs n-1:
93                          * https://stats.stackexchange.com/questions/17890/what-is-the-difference-between-n-and-n-1-in-calculating-population-variance
94                          */
95                         stats->var_time += (sample_time - stats->avg_time) *
96                                            (sample_time - stats->avg_time);
97                 }
98         }
99         stats->var_time /= stats->total_samples - 1;
100         /* We have two histogram structures.  The main one is for printing, and
101          * the other is for computing latency percentiles.  The only real diff
102          * btw the two is the number of bins.  The latency one has a lot more,
103          * for finer granularity, and the regular one has fewer for better
104          * printing.
105          *
106          * Both have the same max and min bin values.  Any excesses get put in
107          * the smallest or biggest bin.  This keeps the granularity reasonable
108          * in the face of very large outliers.  Normally, I trim off anything
109          * outside 3 stddev.
110          * 
111          * High variation will throw off our histogram bins, so we adjust.  A
112          * coef_var > 1 is considered high variance.  The numbers I picked are
113          * just heuristics to catch SMM interference and make the output look
114          * nice. */
115         coef_var = sqrt(stats->var_time) / stats->avg_time;
116         if (coef_var > HI_COEF_VAR) {
117                 hist_max_time = stats->avg_time * 3;
118                 hist_min_time = stats->avg_time / 3;
119         } else {        /* 'normal' data */
120                 /* trimming the printable hist at 3 stddevs, which for normal
121                  * data is 99.7% of the data.  For most any data, it gets 89%
122                  * (Chebyshev's inequality) */
123                 hist_max_time = stats->avg_time + 3 * sqrt(stats->var_time);
124                 hist_min_time = stats->avg_time - 3 * sqrt(stats->var_time);
125                 if (hist_min_time > hist_max_time)
126                         hist_min_time = 0;
127         }
128         lat_max_time = hist_max_time;
129         lat_min_time = hist_min_time;
130         hist_bin_sz = (hist_max_time - hist_min_time) / nr_hist_bins + 1;
131         lat_bin_sz = (lat_max_time - lat_min_time) / nr_lat_bins + 1;
132         hist_times = malloc(sizeof(unsigned int) * nr_hist_bins);
133         lat_times = malloc(sizeof(unsigned int) * nr_lat_bins);
134         if (!hist_times || !lat_times) {
135                 perror("compute_stats failed to alloc hist/lat arrays:");
136                 free(hist_times);
137                 free(lat_times);
138                 return;
139         }
140         memset(hist_times, 0, sizeof(unsigned int) * nr_hist_bins);
141         memset(lat_times, 0, sizeof(unsigned int) * nr_lat_bins);
142         /* third pass, fill the bins for the histogram and latencies */
143         for (int i = 0; i < nr_i; i++) {
144                 for (int j = 0; j < nr_j; j++) {
145                         if (stats->get_sample(data, i, j, &sample_time))
146                                 continue;
147                         /* need to shift, offset by min_time.  anything too
148                          * small is 0 and will go into the first bin.  anything
149                          * too large will go into the last bin. */
150                         lat_idx = sample_time < lat_min_time
151                                   ? 0
152                                   : (sample_time - lat_min_time) / lat_bin_sz;
153                         lat_idx = MIN(lat_idx, nr_lat_bins - 1);
154                         lat_times[lat_idx]++;
155                         hist_idx = sample_time < hist_min_time
156                                    ? 0
157                                    : (sample_time - hist_min_time) /
158                                      hist_bin_sz;
159                         hist_idx = MIN(hist_idx, nr_hist_bins - 1);
160                         hist_times[hist_idx]++;
161                         /* useful for formatting the ***s */
162                         max_hist_bin = (hist_times[hist_idx] > max_hist_bin)
163                                        ? hist_times[hist_idx]
164                                        : max_hist_bin;
165                 }
166         }
167         /* Compute latency percentiles */
168         for (int i = 0; i < nr_lat_bins; i++) {
169                 accum_samples += lat_times[i];
170                 /* (i + 1), since we've just accumulated one bucket's worth */
171                 if (!stats->lat_50 &&
172                     accum_samples / stats->total_samples > 0.50)
173                         stats->lat_50 = (i + 1) * lat_bin_sz + lat_min_time;
174                 if (!stats->lat_75 &&
175                     accum_samples / stats->total_samples > 0.75)
176                         stats->lat_75 = (i + 1) * lat_bin_sz + lat_min_time;
177                 if (!stats->lat_90 &&
178                     accum_samples / stats->total_samples > 0.90)
179                         stats->lat_90 = (i + 1) * lat_bin_sz + lat_min_time;
180                 if (!stats->lat_99 &&
181                     accum_samples / stats->total_samples > 0.99)
182                         stats->lat_99 = (i + 1) * lat_bin_sz + lat_min_time;
183         }
184         for (int i = 0; i < nr_hist_bins; i++) {
185                 uint64_t interval_start = i * hist_bin_sz + hist_min_time;
186                 uint64_t interval_end = (i + 1) * hist_bin_sz + hist_min_time;
187
188                 /* customize the first and last entries */
189                 if (i == 0)
190                         interval_start = MIN(interval_start, stats->min_time);
191                 if (i == nr_hist_bins - 1) {
192                         interval_end = MAX(interval_end, stats->max_time);
193                         /* but not at the sake of formatting! (8 spaces) */
194                         interval_end = MIN(interval_end, 99999999);
195                 }
196                 printf("    [%8llu - %8llu] %7d: ", interval_start,
197                        interval_end, hist_times[i]);
198                 /* nr_dots = hist_times[i] * nr_dots_per_sample
199                  *         = hist_times[i] * (max_num_dots / max_hist_bin) */
200                 int nr_dots = hist_times[i] * max_dots_per_row / max_hist_bin;
201
202                 for (int j = 0; j < nr_dots; j++)
203                         printf("*");
204                 printf("\n");
205         }
206         printf("\n");
207         printf("Samples per dot: %d\n", max_hist_bin / max_dots_per_row);
208         printf("Total samples: %llu\n", stats->total_samples);
209         printf("Avg time   : %llu\n", stats->avg_time);
210         printf("Stdev time : %f\n", sqrt(stats->var_time));
211         printf("Coef Var   : %f\n", coef_var);
212         if (coef_var > HI_COEF_VAR)
213                 printf(
214                   "\tHigh coeff of var with serious outliers, adjusted bins\n");
215         /* numbers are overestimates by at most a lat bin */
216         printf("50/75/90/99: %d / %d / %d / %d (-<%ld)\n", stats->lat_50,
217                stats->lat_75, stats->lat_90, stats->lat_99, lat_bin_sz);
218         printf("Min / Max  : %llu / %llu\n", stats->min_time, stats->max_time);
219         printf("\n");
220         free(hist_times);
221         free(lat_times);
222 }
223
224 /* Prints the throughput of certain events over nr_steps of interval time.  Will
225  * print the overall throughput of the entire time (total events / steps),
226  * and print out each step up to nr_print_steps.
227  *
228  * Assumes a 2D data structure, where the events in each data[i][] (for a
229  * specific i) are in order.  The 'nr_i'es are typically threads or something
230  * similar.  nr_j would be how many samples per thread.  The func ptr should
231  * return the time of the data[i][j]'th event via *sample and return 0 on
232  * success, and any other value for 'no data'.  If start_time is 0, we'll start
233  * the clock right before the first event. */
234 void print_throughput(void **data, unsigned int nr_steps, uint64_t interval,
235                       unsigned int nr_print_steps, uint64_t start_time,
236                       int nr_i, int nr_j,
237                       int (*get_sample)(void **data, int i, int j,
238                                         uint64_t *sample))
239 {
240         uint64_t time_now, sample;
241         /* next_sample[] tracks each thread's next lock that was acquired */
242         unsigned int *next_sample;
243         unsigned int *step_events;
244         unsigned int most_step_events = 1;
245         unsigned int max_dots_per_row = 45; /* looks good with 80-wide col */
246         unsigned int total_events = 0;
247
248         if (!nr_steps)
249                 return;
250         nr_print_steps = MIN(nr_print_steps, nr_steps);
251         next_sample = malloc(sizeof(unsigned int) * nr_i);
252         step_events = malloc(sizeof(unsigned int) * nr_steps);
253         if (!next_sample || !step_events) {
254                 perror("print_throughput failed alloc:");
255                 free(next_sample);
256                 free(step_events);
257                 return;
258         }
259         memset(next_sample, 0, sizeof(unsigned int) * nr_i);
260         memset(step_events, 0, sizeof(unsigned int) * nr_steps);
261         if (start_time) {
262                 time_now = start_time;
263         } else {
264                 time_now = UINT64_MAX;
265                 /* Set the replay to start right before the first event */
266                 for (int i = 0; i < nr_i; i++) {
267                         if (get_sample(data, i, 0, &sample))
268                                 continue;
269                         time_now = MIN(time_now, sample);
270                 }
271                 if (time_now != 0)
272                         time_now--;
273         }
274         for (int k = 0; k < nr_steps; k++) {
275                 time_now += interval;
276                 /* for every 'thread', we'll figure out how many events
277                  * occurred, and advance next_sample to track the next one to
278                  * consider */
279                 for (int i = 0; i < nr_i; i++) {
280                         /* count nr locks that have happened, advance per thread
281                          * tracker */
282                         for ( ; next_sample[i] < nr_j; next_sample[i]++) {
283                                 /* skip this thread if it has no more data */
284                                 if (get_sample(data, i, next_sample[i],
285                                                &sample))
286                                         continue;
287                                 /* break when we found one that hasn't happened
288                                  * yet */
289                                 if (!(sample <= time_now))
290                                         break;
291                                 step_events[k]++;
292                         }
293                 }
294                 total_events += step_events[k];
295                 /* for dynamically scaling the *'s */
296                 most_step_events = MAX(most_step_events, step_events[k]);
297         }
298         if (nr_print_steps)
299                 printf("Events per dot: %d\n",
300                        most_step_events / max_dots_per_row);
301         for (int k = 0; k < nr_print_steps; k++) {
302                 /* Last step isn't accurate, will only be partially full */
303                 if (k == nr_steps - 1)
304                         break;
305                 printf("%6d: ", k);
306                 printf("%6d ", step_events[k]);
307                 /* nr_dots = step_events[k] * nr_dots_per_event
308                  *   = step_events[k] * (max_dots_per_row / most_step_events) */
309                 int nr_dots = step_events[k] * max_dots_per_row /
310                               most_step_events;
311                 for (int i = 0; i < nr_dots; i++)
312                         printf("*");
313                 printf("\n");
314         }
315         printf("Total events: %d, Avg events/step: %d\n", total_events,
316                total_events / nr_steps);
317         free(next_sample);
318         free(step_events);
319 }