gdunlap/sched-sim.hg

annotate stats.c @ 17:03ad237559b4

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