gdunlap/sched-sim.hg

view stats.c @ 0:d27bb3c56e71

Inital commit.
author George Dunlap <gdunlap@xensource.com>
date Tue Oct 13 16:06:36 2009 +0100 (2009-10-13)
parents
children
line source
1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <assert.h>
5 #include "stats.h"
7 #define DEFAULT_SAMPLE_SIZE 10240
9 static struct {
10 int sample_size;
11 } opt = {
12 .sample_size = DEFAULT_SAMPLE_SIZE,
13 };
15 void set_sampel_size(int n)
16 {
17 opt.sample_size = n;
18 }
20 extern FILE *warn;
22 /* With compliments to "Numerical Recipes in C", which provided the algorithm
23 * and basic template for this function. */
24 #if 0
25 static long long percentile(long long * A, int N, int ple) {
26 int I, J, L, R, K;
28 long long X, W;
30 /* No samples! */
31 if ( N == 0 )
32 return 0;
34 /* Find K, the element # we want */
35 K=N*ple/100;
37 /* Set the left and right boundaries of the current search space */
38 L=0; R=N-1;
40 while(L < R) {
41 /* X: The value to order everything higher / lower than */
42 X=A[K];
44 /* Starting at the left and the right... */
45 I=L;
46 J=R;
48 do {
49 /* Find the first element on the left that is out-of-order w/ X */
50 while(A[I]<X)
51 I++;
52 /* Find the first element on the right that is out-of-order w/ X */
53 while(X<A[J])
54 J--;
56 /* If we found something out-of-order */
57 if(I<=J) {
58 /* Switch the values */
59 W=A[I];
60 A[I]=A[J];
61 A[J]=W;
63 /* And move on */
64 I++; J--;
65 }
66 } while (I <= J); /* Keep going until our pointers meet or pass */
68 /* Re-adjust L and R, based on which element we're looking for */
69 if(J<K)
70 L=I;
71 if(K<I)
72 R=J;
73 }
75 return A[K];
76 }
78 static float weighted_percentile(float * A, /* values */
79 unsigned long long * w, /* weights */
80 int N, /* total */
81 int ple) /* percentile */
82 {
83 int L, R, I, J, K;
84 unsigned long long L_weight, R_weight, I_weight, J_weight,
85 K_weight, N_weight;
87 float X, t1;
88 unsigned long long t2;
90 int progress;
92 /* Calculate total weight */
93 N_weight=0;
95 for(I=0; I<N; I++) {
96 assert(w[I]!=0);
97 N_weight += w[I];
98 }
100 /* Find K_weight, the target weight we want */
101 K_weight = N_weight * ple / 100;
103 /* Set the left and right boundaries of the current search space */
104 L=0;
105 L_weight = 0;
106 R=N-1;
107 R_weight = N_weight - w[R];
109 /* Search between L and R, narrowing down until we're done */
110 while(L < R) {
111 /* Chose an ordering value from right in the middle */
112 K = (L + R) >> 1;
113 /* X: The value to order everything higher / lower than */
114 X=A[K];
116 /* Starting at the left and the right... */
117 I=L; I_weight = L_weight;
118 J=R; J_weight = R_weight;
120 do {
121 /* Find the first element on the left that is out-of-order w/ X */
122 while(A[I]<X) {
123 I_weight += w[I];
124 I++;
125 }
126 /* Find the first element on the right that is out-of-order w/ X */
127 while(X<A[J]) {
128 J_weight -= w[J];
129 J--;
130 }
132 /* If we actually found something... */
133 if(I<=J) {
134 /* Switch the values */
135 t1=A[I];
136 A[I]=A[J];
137 A[J]=t1;
139 t2=w[I];
140 w[I]=w[J];
141 w[J]=t2;
143 /* And move in */
144 I_weight += w[I];
145 I++;
147 J_weight -= w[J];
148 J--;
149 }
150 } while (I <= J); /* Keep going until our pointers meet or pass */
152 progress = 0;
154 /* Re-adjust L and R, based on which element we're looking for */
155 if(J_weight<K_weight) {
156 progress = 1;
157 L=I; L_weight = I_weight;
158 }
159 if(K_weight<I_weight) {
160 progress = 1;
161 R=J; R_weight = J_weight;
162 }
163 }
165 return A[L];
166 }
167 #endif
169 static long long self_weighted_percentile(long long * A,
170 int N, /* total */
171 int ple) /* percentile */
172 {
173 int L, R, I, J, K;
174 long long L_weight, R_weight, I_weight, J_weight,
175 K_weight, N_weight;
177 long long X, t1;
179 int progress;
181 /* Calculate total weight */
182 N_weight=0;
184 for(I=0; I<N; I++) {
185 if(A[I] < 0)
186 fprintf(warn, "%s: Value %lld less than zero!\n",
187 __func__, A[I]);
188 assert(A[I]!=0);
189 N_weight += A[I];
190 }
192 /* Find K_weight, the target weight we want */
193 K_weight = N_weight * ple / 100;
195 /* Set the left and right boundaries of the current search space */
196 L=0;
197 L_weight = 0;
198 R=N-1;
199 R_weight = N_weight - A[R];
201 /* Search between L and R, narrowing down until we're done */
202 while(L < R) {
203 /* Chose an ordering value from right in the middle */
204 K = (L + R) >> 1;
205 /* X: The value to order everything higher / lower than */
206 X=A[K];
208 /* Starting at the left and the right... */
209 I=L; I_weight = L_weight;
210 J=R; J_weight = R_weight;
212 do {
213 /* Find the first element on the left that is out-of-order w/ X */
214 while(A[I]<X) {
215 I_weight += A[I];
216 I++;
217 }
218 /* Find the first element on the right that is out-of-order w/ X */
219 while(X<A[J]) {
220 J_weight -= A[J];
221 J--;
222 }
224 /* If we actually found something... */
225 if(I<=J) {
226 /* Switch the values */
227 t1=A[I];
228 A[I]=A[J];
229 A[J]=t1;
231 /* And move in */
232 I_weight += A[I];
233 I++;
235 J_weight -= A[J];
236 J--;
237 }
238 } while (I <= J); /* Keep going until our pointers meet or pass */
240 progress = 0;
242 /* Re-adjust L and R, based on which element we're looking for */
243 if(J_weight<K_weight) {
244 progress = 1;
245 L=I; L_weight = I_weight;
246 }
247 if(K_weight<I_weight) {
248 progress = 1;
249 R=J; R_weight = J_weight;
250 }
251 }
253 return A[L];
254 }
256 void update_cycles(struct cycle_summary *s, long long c) {
257 /* We don't know ahead of time how many samples there are, and working
258 * with dynamic stuff is a pain, and unnecessary. This algorithm will
259 * generate a sample set that approximates an even sample. We can
260 * then take the percentiles on this, and get an approximate value. */
261 int lap, index;
263 if ( c == 0 )
264 return;
266 if ( opt.sample_size ) {
267 lap = (s->count/opt.sample_size)+1;
268 index =s->count % opt.sample_size;
270 if((index - (lap/3))%lap == 0) {
271 if(!s->sample) {
272 s->sample = malloc(sizeof(*s->sample) * opt.sample_size);
273 if(!s->sample) {
274 fprintf(stderr, "%s: malloc failed!\n", __func__);
275 exit(1);
276 }
277 }
278 s->sample[index] = c;
279 }
280 }
282 if(c > 0) {
283 s->cycles += c;
284 } else {
285 s->cycles += -c;
286 }
287 s->count++;
288 }
290 void print_cycle_summary(struct cycle_summary *s,
291 tsc_t total, char *p) {
292 if(s->count) {
293 long long avg;
294 double percent;
296 avg = s->cycles / s->count;
298 if ( total )
299 percent = ((double)(s->cycles * 100)) / total;
301 if ( opt.sample_size ) {
302 long long p5, p50, p95;
303 int data_size = s->count;
305 if(data_size > opt.sample_size)
306 data_size = opt.sample_size;
308 p50 = self_weighted_percentile(s->sample, data_size, 50);
309 p5 = self_weighted_percentile(s->sample, data_size, 5);
310 p95 = self_weighted_percentile(s->sample, data_size, 95);
312 if ( total )
313 printf("%s: %7d %llu %5.2lf%% %6lld {%6lld|%6lld|%6lld}\n",
314 p, s->count,
315 s->cycles,
316 percent,
317 avg, p5, p50, p95);
318 else
319 printf("%s: %7d %llu %6lld {%6lld|%6lld|%6lld}\n",
320 p, s->count,
321 s->cycles,
322 avg, p5, p50, p95);
324 } else {
325 if ( total )
326 printf("%s: %7d %llu %5.2lf%% %6lld\n",
327 p, s->count,
328 s->cycles,
329 percent,
330 avg);
331 else
332 printf("%s: %7d %llu %6lld\n",
333 p, s->count,
334 s->cycles,
335 avg);
336 }
337 }
338 }