1/*
2 * Copyright (c) 2007-2012, ETH Zurich.
3 * All rights reserved.
4 *
5 * This file is distributed under the terms in the attached LICENSE file.
6 * If you do not find this file, copies can be found by writing to:
7 * ETH Zurich D-INFK, Universitaetstrasse 6, CH-8092 Zurich. Attn: Systems Group.
8 */
9
10#include <stdlib.h>
11#include <stdio.h>
12#include <string.h>
13#include <assert.h>
14#include <bench.h>
15#include <limits.h>
16
17bench_ctl_t *bench_ctl_init(enum bench_ctl_mode mode,
18                            size_t              dimensions,
19                            size_t              min_runs)
20{
21    bench_ctl_t *ctl;
22
23    ctl = calloc(1, sizeof(*ctl));
24    ctl->mode = mode;
25    ctl->result_dimensions = dimensions;
26    ctl->min_runs = min_runs;
27
28    if (mode == BENCH_MODE_FIXEDRUNS) {
29        ctl->data = calloc(min_runs * dimensions, sizeof(*ctl->data));
30    } else {
31        assert(!"NYI");
32    }
33
34    return ctl;
35}
36
37void bench_ctl_destroy(bench_ctl_t *ctl)
38{
39    free(ctl->data);
40    free(ctl);
41}
42
43void bench_ctl_dry_runs(bench_ctl_t *ctl,
44                        size_t       dry_runs)
45{
46    ctl->dry_runs = dry_runs;
47}
48
49bool bench_ctl_add_run(bench_ctl_t *ctl,
50                       cycles_t* result)
51{
52    cycles_t *dst;
53
54    if (ctl->result_count == ctl->min_runs) {
55        return true;
56    }
57
58    dst = ctl->data + ctl->result_count * ctl->result_dimensions;
59    memcpy(dst, result, sizeof(dst) * ctl->result_dimensions);
60
61    ctl->result_count++;
62
63    return ctl->result_count == ctl->min_runs;
64}
65
66void bench_ctl_dump_csv(bench_ctl_t *ctl,
67                        const char  *prefix,
68                        uint64_t tscperus)
69{
70    size_t i, j;
71    cycles_t *v;
72    size_t dim = ctl->result_dimensions;
73
74#if BENCH_DUMP_OCTAVE
75    printf("%s = [\n", prefix);
76    for (i = 0; i < ctl->result_count; i++) {
77        printf("    ");
78        v = ctl->data + i * dim;
79        for (j = 0; j < dim; j++) {
80            printf("%"PRIu64", %f", v[j], v[j]/(float)tscperus);
81            if (j != dim - 1) {
82                printf(",");
83            }
84        }
85        printf(";\n");
86    }
87    printf("];\n");
88#else
89
90    for (i = 0; i < ctl->result_count; i++) {
91        printf("%% %s", prefix);
92
93        v = ctl->data + i * dim;
94        for (j = 0; j < dim; j++) {
95            printf("%"PRIu64", %f", v[j], v[j]/(float)tscperus);
96            if (j != dim - 1) {
97                printf(",");
98            }
99        }
100        printf("\n");
101    }
102#endif
103    fflush(stdout);
104}
105
106
107
108static cycles_t *get_array(bench_ctl_t *ctl,
109                          size_t dimension)
110{
111    cycles_t *array = calloc(ctl->result_count, sizeof(cycles_t));
112    assert(array != NULL);
113
114    for (size_t i = 0; i < ctl->result_count; i++) {
115        array[i] = *(ctl->data + (ctl->result_dimensions * i
116                    + dimension));
117    }
118    return array;
119}
120
121static cycles_t *do_sorting(cycles_t *array,
122                            size_t len)
123{
124    size_t i, j;
125    cycles_t *sorted_array = array;
126    cycles_t temp_holder;
127
128
129    // sort the array
130    for (i = 0; i < len; ++i) {
131        for (j = i; j < len; ++j) {
132            if (sorted_array[i] > sorted_array[j]) {
133                temp_holder = sorted_array[i];
134                sorted_array[i] = sorted_array[j];
135                sorted_array[j] = temp_holder;
136            }
137        } // end for: j
138    } // end for: i
139    return sorted_array;
140} // end function: do_sorting
141
142void bench_ctl_dump_analysis(bench_ctl_t *ctl,
143                             size_t dimension,
144                             const char *prefix,
145                             cycles_t tscperus)
146{
147    size_t len = ctl->result_count;
148    cycles_t *array = get_array(ctl, dimension);
149
150#if BENCH_DUMP_OCTAVE
151    cycles_t avg, std_dev;
152    bench_stddev(array, len, 0, &avg, &std_dev);
153#endif
154
155    cycles_t *final_array =  do_sorting(array, len);
156
157    size_t max99 = (size_t)((0.99 * len) + 0.5);
158#if BENCH_DUMP_OCTAVE
159
160    // printf("\% [name]  [runs]  [avg]  [stdev]  [min]  [med]  [P99]  [max]\n");
161
162    //printf("%% %s\n%"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64", %"PRIu64
163    //       ", %"PRIu64"; \n", prefix,(uint64_t)len, avg, std_dev, final_array[len/2],
164    //       final_array[0], final_array[max99-1], final_array[len-1]);
165
166    printf("%% %s, %"PRIu64", %f, %f, %f, %f, %f, %f;\n",prefix, (uint64_t)len,
167           (avg /(float)tscperus), (std_dev / ((float)tscperus*(float)tscperus)),
168           (final_array[len/2]/(float)tscperus), (final_array[0]/(float)tscperus),
169           (final_array[max99-1]/(float)tscperus),(final_array[len-1]/(float)tscperus));
170#else
171    printf("run [%"PRIu64"], med_pos[%"PRIu64"], min_pos[%"PRIu64"], "
172           "P99[%"PRIu64"], max[%"PRIu64"]\n",
173           (uint64_t)len,
174           (uint64_t)(len/2),
175           (uint64_t)0,
176           (uint64_t)(max99-1),
177           (uint64_t)(len-1));
178
179    printf("run [%"PRIu64"], med[%"PRIu64"], min[%"PRIu64"], "
180           "P99[%"PRIu64"], max[%"PRIu64"]\n",
181           (uint64_t)len,
182           (uint64_t)final_array[len/2],
183           (uint64_t)final_array[0],
184           (uint64_t)final_array[max99-1],
185           (uint64_t)final_array[len-1]);
186
187    printf("run [%"PRIu64"], med[%f], min[%f], "
188           "P99[%f], max[%f]\n",
189           (uint64_t)len,
190           (final_array[len/2]/(float)tscperus),
191           (final_array[0]/(float)tscperus),
192           (final_array[max99-1]/(float)tscperus),
193           (final_array[len-1]/(float)tscperus));
194
195    printf("%s, %"PRIu64" %f %f %f %f\n",
196           prefix,
197           (uint64_t)len,
198           (final_array[len/2]/(float)tscperus),
199           (final_array[0]/(float)tscperus),
200           (final_array[max99-1]/(float)tscperus),
201           (final_array[len-1]/(float)tscperus));
202#endif
203} // end function: bench_ctl_dump_analysis
204
205
206
207
208/**
209 * \brief computes the differences of two time stamps with respecting overflow
210 *
211 * This function also accounts for the overhead when taking timestamps
212 *
213 * \param tsc_start timestamp of start
214 * \param tsc_end   timestamp of end
215 *
216 * \return elaped cycles
217 */
218cycles_t bench_time_diff(cycles_t tsc_start, cycles_t tsc_end)
219{
220    cycles_t result;
221    if (tsc_end < tsc_start) {
222        result = (LONG_MAX - tsc_start) + tsc_end;
223    } else {
224        result = (tsc_end - tsc_start);
225    }
226    return result;
227}
228
229/**
230 * \brief Compute averages
231 *
232 * If certain datapoints should be ignored, they should be marked with
233 * #BENCH_IGNORE_WATERMARK
234 */
235cycles_t bench_avg(cycles_t *array, size_t len)
236{
237    cycles_t sum = 0;
238    size_t count = 0;
239
240    // Discarding some initial observations
241    for (size_t i = len >> 3; i < len; i++) {
242        if (array[i] != BENCH_IGNORE_WATERMARK) {
243            sum += array[i];
244            count++;
245        }
246    }
247
248    return sum / count;
249}
250
251
252/**
253 * \brief computes the standard deviation s^2 of the sample data
254 *
255 * \param array         array of data to analyze
256 * \param len           size of the array
257 * \param correction    apply Bessel's correction (using N-1 instead of N)
258 * \param ret_avg       returns the average of the sample
259 * \param ret_stddev    returns the standard deviation squared of the sample
260 */
261void bench_stddev(cycles_t *array, size_t len, uint8_t correction,
262                  cycles_t *ret_avg, cycles_t *ret_stddev)
263{
264    cycles_t avg = bench_avg(array, len);
265
266    cycles_t sum = 0;
267    size_t count = 0;
268    /// discard some initiali observations
269    for (size_t i = len >> 3; i < len; i++) {
270        if (array[i] != BENCH_IGNORE_WATERMARK) {
271            cycles_t subsum = array[i] - avg;
272            sum += (subsum * subsum);
273            count++;
274        }
275    }
276
277    cycles_t std_dev = 0;
278    if (correction && count > 1) {
279        std_dev = sum / (count - 1);
280    } else {
281        std_dev = sum / count;
282    }
283
284    if (ret_avg) {
285        *ret_avg = avg;
286    }
287
288    if (ret_stddev) {
289        *ret_stddev = std_dev;
290    }
291}
292
293
294