gdunlap/sched-sim.hg

diff 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 diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/stats.c	Tue Oct 13 16:06:36 2009 +0100
     1.3 @@ -0,0 +1,339 @@
     1.4 +#include <stdlib.h>
     1.5 +#include <stdio.h>
     1.6 +#include <assert.h>
     1.7 +
     1.8 +#include "stats.h"
     1.9 +
    1.10 +#define DEFAULT_SAMPLE_SIZE 10240
    1.11 +
    1.12 +static struct {
    1.13 +    int sample_size;
    1.14 +} opt = {
    1.15 +    .sample_size = DEFAULT_SAMPLE_SIZE,
    1.16 +};
    1.17 +
    1.18 +void set_sampel_size(int n)
    1.19 +{
    1.20 +    opt.sample_size = n;
    1.21 +}
    1.22 +
    1.23 +extern FILE *warn;
    1.24 +
    1.25 +/* With compliments to "Numerical Recipes in C", which provided the algorithm
    1.26 + * and basic template for this function. */
    1.27 +#if 0
    1.28 +static long long percentile(long long * A, int N, int ple) {
    1.29 +    int I, J, L, R, K;
    1.30 +
    1.31 +    long long X, W;
    1.32 +
    1.33 +    /* No samples! */
    1.34 +    if ( N == 0 )
    1.35 +        return 0;
    1.36 +
    1.37 +    /* Find K, the element # we want */
    1.38 +    K=N*ple/100;
    1.39 +
    1.40 +    /* Set the left and right boundaries of the current search space */
    1.41 +    L=0; R=N-1;
    1.42 +
    1.43 +    while(L < R) {
    1.44 +        /* X: The value to order everything higher / lower than */
    1.45 +        X=A[K];
    1.46 +
    1.47 +        /* Starting at the left and the right... */
    1.48 +        I=L;
    1.49 +        J=R;
    1.50 +
    1.51 +        do {
    1.52 +            /* Find the first element on the left that is out-of-order w/ X */
    1.53 +            while(A[I]<X)
    1.54 +                I++;
    1.55 +            /* Find the first element on the right that is out-of-order w/ X */
    1.56 +            while(X<A[J])
    1.57 +                J--;
    1.58 +
    1.59 +            /* If we found something out-of-order */
    1.60 +            if(I<=J) {
    1.61 +                /* Switch the values */
    1.62 +                W=A[I];
    1.63 +                A[I]=A[J];
    1.64 +                A[J]=W;
    1.65 +
    1.66 +                /* And move on */
    1.67 +                I++; J--;
    1.68 +            }
    1.69 +        } while (I <= J); /* Keep going until our pointers meet or pass */
    1.70 +    
    1.71 +        /* Re-adjust L and R, based on which element we're looking for */
    1.72 +        if(J<K)
    1.73 +            L=I;
    1.74 +        if(K<I)
    1.75 +            R=J;
    1.76 +    }
    1.77 +
    1.78 +    return A[K];
    1.79 +}
    1.80 +
    1.81 +static float weighted_percentile(float * A, /* values */
    1.82 +                                       unsigned long long * w, /* weights */
    1.83 +                                       int N,                  /* total */
    1.84 +                                       int ple)                /* percentile */
    1.85 +{
    1.86 +    int L, R, I, J, K;
    1.87 +    unsigned long long L_weight, R_weight, I_weight, J_weight,
    1.88 +        K_weight, N_weight;
    1.89 +
    1.90 +    float X, t1;
    1.91 +    unsigned long long t2;
    1.92 +
    1.93 +    int progress;
    1.94 +
    1.95 +    /* Calculate total weight */
    1.96 +    N_weight=0;
    1.97 +
    1.98 +    for(I=0; I<N; I++) {
    1.99 +        assert(w[I]!=0);
   1.100 +        N_weight += w[I];
   1.101 +    }
   1.102 +
   1.103 +    /* Find K_weight, the target weight we want */
   1.104 +    K_weight = N_weight * ple / 100;
   1.105 +
   1.106 +    /* Set the left and right boundaries of the current search space */
   1.107 +    L=0;
   1.108 +    L_weight = 0;
   1.109 +    R=N-1;
   1.110 +    R_weight = N_weight - w[R];
   1.111 +
   1.112 +    /* Search between L and R, narrowing down until we're done */
   1.113 +    while(L < R) {
   1.114 +        /* Chose an ordering value from right in the middle */
   1.115 +        K = (L + R) >> 1;
   1.116 +        /* X: The value to order everything higher / lower than */
   1.117 +        X=A[K];
   1.118 +
   1.119 +        /* Starting at the left and the right... */
   1.120 +        I=L; I_weight = L_weight;
   1.121 +        J=R; J_weight = R_weight;
   1.122 +
   1.123 +        do {
   1.124 +            /* Find the first element on the left that is out-of-order w/ X */
   1.125 +            while(A[I]<X) {
   1.126 +                I_weight += w[I];
   1.127 +                I++;
   1.128 +            }
   1.129 +            /* Find the first element on the right that is out-of-order w/ X */
   1.130 +            while(X<A[J]) {
   1.131 +                J_weight -= w[J];
   1.132 +                J--;
   1.133 +            }
   1.134 +
   1.135 +            /* If we actually found something... */
   1.136 +            if(I<=J) {
   1.137 +                /* Switch the values */
   1.138 +                t1=A[I];
   1.139 +                A[I]=A[J];
   1.140 +                A[J]=t1;
   1.141 +
   1.142 +                t2=w[I];
   1.143 +                w[I]=w[J];
   1.144 +                w[J]=t2;
   1.145 +
   1.146 +                /* And move in */
   1.147 +                I_weight += w[I];
   1.148 +                I++;
   1.149 +
   1.150 +                J_weight -= w[J];
   1.151 +                J--;
   1.152 +            }
   1.153 +        } while (I <= J); /* Keep going until our pointers meet or pass */
   1.154 +
   1.155 +        progress = 0;
   1.156 +    
   1.157 +        /* Re-adjust L and R, based on which element we're looking for */
   1.158 +        if(J_weight<K_weight) {
   1.159 +            progress = 1;
   1.160 +            L=I; L_weight = I_weight;
   1.161 +        }
   1.162 +        if(K_weight<I_weight) {
   1.163 +            progress = 1;
   1.164 +            R=J; R_weight = J_weight;
   1.165 +        }
   1.166 +    }
   1.167 +
   1.168 +    return A[L];
   1.169 +}
   1.170 +#endif
   1.171 +
   1.172 +static long long self_weighted_percentile(long long * A,
   1.173 +                                   int N,            /* total */
   1.174 +                                   int ple)          /* percentile */
   1.175 +{
   1.176 +    int L, R, I, J, K;
   1.177 +    long long L_weight, R_weight, I_weight, J_weight,
   1.178 +        K_weight, N_weight;
   1.179 +
   1.180 +    long long X, t1;
   1.181 +
   1.182 +    int progress;
   1.183 +
   1.184 +    /* Calculate total weight */
   1.185 +    N_weight=0;
   1.186 +
   1.187 +    for(I=0; I<N; I++) {
   1.188 +        if(A[I] < 0)
   1.189 +            fprintf(warn, "%s: Value %lld less than zero!\n",
   1.190 +                    __func__, A[I]);
   1.191 +        assert(A[I]!=0);
   1.192 +        N_weight += A[I];
   1.193 +    }
   1.194 +
   1.195 +    /* Find K_weight, the target weight we want */
   1.196 +    K_weight = N_weight * ple / 100;
   1.197 +
   1.198 +    /* Set the left and right boundaries of the current search space */
   1.199 +    L=0;
   1.200 +    L_weight = 0;
   1.201 +    R=N-1;
   1.202 +    R_weight = N_weight - A[R];
   1.203 +
   1.204 +    /* Search between L and R, narrowing down until we're done */
   1.205 +    while(L < R) {
   1.206 +        /* Chose an ordering value from right in the middle */
   1.207 +        K = (L + R) >> 1;
   1.208 +        /* X: The value to order everything higher / lower than */
   1.209 +        X=A[K];
   1.210 +
   1.211 +        /* Starting at the left and the right... */
   1.212 +        I=L; I_weight = L_weight;
   1.213 +        J=R; J_weight = R_weight;
   1.214 +
   1.215 +        do {
   1.216 +            /* Find the first element on the left that is out-of-order w/ X */
   1.217 +            while(A[I]<X) {
   1.218 +                I_weight += A[I];
   1.219 +                I++;
   1.220 +            }
   1.221 +            /* Find the first element on the right that is out-of-order w/ X */
   1.222 +            while(X<A[J]) {
   1.223 +                J_weight -= A[J];
   1.224 +                J--;
   1.225 +            }
   1.226 +
   1.227 +            /* If we actually found something... */
   1.228 +            if(I<=J) {
   1.229 +                /* Switch the values */
   1.230 +                t1=A[I];
   1.231 +                A[I]=A[J];
   1.232 +                A[J]=t1;
   1.233 +
   1.234 +                /* And move in */
   1.235 +                I_weight += A[I];
   1.236 +                I++;
   1.237 +
   1.238 +                J_weight -= A[J];
   1.239 +                J--;
   1.240 +            }
   1.241 +        } while (I <= J); /* Keep going until our pointers meet or pass */
   1.242 +
   1.243 +        progress = 0;
   1.244 +    
   1.245 +        /* Re-adjust L and R, based on which element we're looking for */
   1.246 +        if(J_weight<K_weight) {
   1.247 +            progress = 1;
   1.248 +            L=I; L_weight = I_weight;
   1.249 +        }
   1.250 +        if(K_weight<I_weight) {
   1.251 +            progress = 1;
   1.252 +            R=J; R_weight = J_weight;
   1.253 +        }
   1.254 +    }
   1.255 +
   1.256 +    return A[L];
   1.257 +}
   1.258 +
   1.259 +void update_cycles(struct cycle_summary *s, long long c) {
   1.260 +/* We don't know ahead of time how many samples there are, and working
   1.261 + * with dynamic stuff is a pain, and unnecessary.  This algorithm will
   1.262 + * generate a sample set that approximates an even sample.  We can
   1.263 + * then take the percentiles on this, and get an approximate value. */
   1.264 +    int lap, index;
   1.265 +
   1.266 +    if ( c == 0 )
   1.267 +        return;
   1.268 +
   1.269 +    if ( opt.sample_size ) {
   1.270 +        lap = (s->count/opt.sample_size)+1;
   1.271 +        index =s->count % opt.sample_size;
   1.272 +
   1.273 +        if((index - (lap/3))%lap == 0) {
   1.274 +            if(!s->sample) {
   1.275 +                s->sample = malloc(sizeof(*s->sample) * opt.sample_size);
   1.276 +                if(!s->sample) {
   1.277 +                    fprintf(stderr, "%s: malloc failed!\n", __func__);
   1.278 +                    exit(1);
   1.279 +                }
   1.280 +            }
   1.281 +            s->sample[index] = c;
   1.282 +        }
   1.283 +    }
   1.284 +
   1.285 +    if(c > 0) {
   1.286 +        s->cycles += c;
   1.287 +    } else {
   1.288 +        s->cycles += -c;
   1.289 +    }
   1.290 +    s->count++;
   1.291 +}
   1.292 +
   1.293 +void print_cycle_summary(struct cycle_summary *s,
   1.294 +                         tsc_t total, char *p) {
   1.295 +    if(s->count) {
   1.296 +        long long avg;
   1.297 +        double percent;
   1.298 +
   1.299 +        avg = s->cycles / s->count;
   1.300 +
   1.301 +        if ( total )
   1.302 +            percent = ((double)(s->cycles * 100)) / total;
   1.303 +
   1.304 +        if ( opt.sample_size ) {
   1.305 +            long long p5, p50, p95;
   1.306 +            int data_size = s->count;
   1.307 +
   1.308 +            if(data_size > opt.sample_size)
   1.309 +                data_size = opt.sample_size;
   1.310 +
   1.311 +            p50 = self_weighted_percentile(s->sample, data_size, 50);
   1.312 +            p5 = self_weighted_percentile(s->sample, data_size, 5);
   1.313 +            p95 = self_weighted_percentile(s->sample, data_size, 95);
   1.314 +
   1.315 +            if ( total )
   1.316 +                printf("%s: %7d %llu %5.2lf%% %6lld {%6lld|%6lld|%6lld}\n",
   1.317 +                       p, s->count,
   1.318 +                       s->cycles,
   1.319 +                       percent,
   1.320 +                       avg, p5, p50, p95);
   1.321 +            else
   1.322 +                printf("%s: %7d %llu %6lld {%6lld|%6lld|%6lld}\n",
   1.323 +                       p, s->count,
   1.324 +                       s->cycles,
   1.325 +                       avg, p5, p50, p95);
   1.326 +                
   1.327 +        } else {
   1.328 +            if ( total )
   1.329 +                printf("%s: %7d %llu %5.2lf%% %6lld\n",
   1.330 +                       p, s->count, 
   1.331 +                       s->cycles,
   1.332 +                       percent,
   1.333 +                       avg);
   1.334 +            else
   1.335 +                printf("%s: %7d %llu %6lld\n",
   1.336 +                       p, s->count, 
   1.337 +                       s->cycles,
   1.338 +                       avg);
   1.339 +        }
   1.340 +    }
   1.341 +}
   1.342 +