lib/stopwatch.c
/* Calculate the percentile using the P-square algorithm. For more
 * information, see https://www1.cse.wustl.edu/~jain/papers/ftp/psqr.pdf
 */
Calculate the percentile using the P-square algorithm.
Calculate the percentile using the P - square algorithm .
static void
calc_percentile(unsigned long long n_samples, struct percentile *pctl,
                unsigned long long new_sample)
{
    if (n_samples < P_SQUARE_MIN) {
        pctl->samples[n_samples - 1] = new_sample;
    }
    if (n_samples <= MARKERS) {
        pctl->q[n_samples - 1] = new_sample;
        qsort(pctl->q, n_samples, sizeof *pctl->q, comp_samples);
        if (n_samples == MARKERS) {
            pctl->n[0] = 0;
            pctl->n[1] = 1;
            pctl->n[2] = 2;
            pctl->n[3] = 3;
            pctl->n[4] = 4;
            pctl->n_prime[0] = 0;
            pctl->n_prime[1] = 2 * P;
            pctl->n_prime[2] = 4 * P;
            pctl->n_prime[3] = 2 + 2 * P;
            pctl->n_prime[4] = 4;
            pctl->dn[0] = 0;
            pctl->dn[1] = P / 2;
            pctl->dn[2] = P;
            pctl->dn[3] = (1 + P) / 2;
            pctl->dn[4] = 1;
        }
        pctl->percentile = pctl->q[(int) P * n_samples];
        return;
    }
    int k;
    if (new_sample < pctl->q[0]) {
        k = 0;
        pctl->q[0] = new_sample;
    } else if (new_sample < pctl->q[1]) {
        k = 0;
    } else if (new_sample < pctl->q[2]) {
        k = 1;
    } else if (new_sample < pctl->q[3]) {
        k = 2;
    } else if (new_sample <= pctl->q[4]) {
        k = 3;
    } else {
        k = 3;
        pctl->q[4] = new_sample;
    }
    for (int i = k + 1; i < MARKERS; i++) {
        pctl->n[i]++;
    }
    for (int i = 0; i < MARKERS; i++) {
        pctl->n_prime[i] += pctl->dn[i];
    }
    for (int i = 1; i < MARKERS - 1; i++) {
        double d = pctl->n_prime[i] - pctl->n[i];
        if ((d >= 1 && pctl->n[i + 1] - pctl->n[i] > 1) ||
            (d <= -1 && pctl->n[i - 1] - pctl->n[i] < -1)) {
            d = d >= 0 ? 1 : -1;
            double a = d / (pctl->n[i + 1] - pctl->n[i - 1]);
            double b = (pctl->n[i] - pctl->n[i - 1] + d) *
                (pctl->q[i + 1] - pctl->q[i]) / (pctl->n[i + 1] - pctl->n[i]);
            double c = (pctl->n[i + 1] - pctl->n[i] - d) *
                (pctl->q[i] - pctl->q[i - 1]) / (pctl->n[i] - pctl->n[i - 1]);
            double candidate = pctl->q[i] + a * (b + c);
            if (pctl->q[i - 1] < candidate && candidate < pctl->q[i + 1]) {
                pctl->q[i] = candidate;
            } else {
                pctl->q[i] = pctl->q[i] +
                    (d * (pctl->q[i + (int)d] - pctl->q[i]) /
                    (pctl->n[i +(int)d] - pctl->n[i]));
            }
            pctl->n[i] += d;
        }
    }
    if (n_samples < P_SQUARE_MIN) {
        qsort(pctl->samples, n_samples, sizeof *pctl->samples, comp_samples);
        pctl->percentile = pctl->samples[(int) (P * n_samples)];
    } else {
        pctl->percentile = pctl->q[2];
    }
}
static void calc_percentile ( unsigned long long n_samples , struct percentile * pctl , unsigned long long new_sample ) { if ( n_samples < P_SQUARE_MIN ) { pctl -> samples [ n_samples - 1 ] = new_sample ; } if ( n_samples <= MARKERS ) { pctl -> q [ n_samples - 1 ] = new_sample ; qsort ( pctl -> q , n_samples , sizeof * pctl -> q , comp_samples ) ; if ( n_samples == MARKERS ) { pctl -> n [ 0 ] = 0 ; pctl -> n [ 1 ] = 1 ; pctl -> n [ 2 ] = 2 ; pctl -> n [ 3 ] = 3 ; pctl -> n [ 4 ] = 4 ; pctl -> n_prime [ 0 ] = 0 ; pctl -> n_prime [ 1 ] = 2 * P ; pctl -> n_prime [ 2 ] = 4 * P ; pctl -> n_prime [ 3 ] = 2 + 2 * P ; pctl -> n_prime [ 4 ] = 4 ; pctl -> dn [ 0 ] = 0 ; pctl -> dn [ 1 ] = P / 2 ; pctl -> dn [ 2 ] = P ; pctl -> dn [ 3 ] = ( 1 + P ) / 2 ; pctl -> dn [ 4 ] = 1 ; } pctl -> percentile = pctl -> q [ ( int ) P * n_samples ] ; return ; } int k ; if ( new_sample < pctl -> q [ 0 ] ) { k = 0 ; pctl -> q [ 0 ] = new_sample ; } else if ( new_sample < pctl -> q [ 1 ] ) { k = 0 ; } else if ( new_sample < pctl -> q [ 2 ] ) { k = 1 ; } else if ( new_sample < pctl -> q [ 3 ] ) { k = 2 ; } else if ( new_sample <= pctl -> q [ 4 ] ) { k = 3 ; } else { k = 3 ; pctl -> q [ 4 ] = new_sample ; } for ( int i = k + 1 ; i < MARKERS ; i ++ ) { pctl -> n [ i ] ++ ; } for ( int i = 0 ; i < MARKERS ; i ++ ) { pctl -> n_prime [ i ] += pctl -> dn [ i ] ; } for ( int i = 1 ; i < MARKERS - 1 ; i ++ ) { double d = pctl -> n_prime [ i ] - pctl -> n [ i ] ; if ( ( d >= 1 && pctl -> n [ i + 1 ] - pctl -> n [ i ] > 1 ) || ( d <= -1 && pctl -> n [ i - 1 ] - pctl -> n [ i ] < -1 ) ) { d = d >= 0 ? 1 : -1 ; double a = d / ( pctl -> n [ i + 1 ] - pctl -> n [ i - 1 ] ) ; double b = ( pctl -> n [ i ] - pctl -> n [ i - 1 ] + d ) * ( pctl -> q [ i + 1 ] - pctl -> q [ i ] ) / ( pctl -> n [ i + 1 ] - pctl -> n [ i ] ) ; double c = ( pctl -> n [ i + 1 ] - pctl -> n [ i ] - d ) * ( pctl -> q [ i ] - pctl -> q [ i - 1 ] ) / ( pctl -> n [ i ] - pctl -> n [ i - 1 ] ) ; double candidate = pctl -> q [ i ] + a * ( b + c ) ; if ( pctl -> q [ i - 1 ] < candidate && candidate < pctl -> q [ i + 1 ] ) { pctl -> q [ i ] = candidate ; } else { pctl -> q [ i ] = pctl -> q [ i ] + ( d * ( pctl -> q [ i + ( int ) d ] - pctl -> q [ i ] ) / ( pctl -> n [ i + ( int ) d ] - pctl -> n [ i ] ) ) ; } pctl -> n [ i ] += d ; } } if ( n_samples < P_SQUARE_MIN ) { qsort ( pctl -> samples , n_samples , sizeof * pctl -> samples , comp_samples ) ; pctl -> percentile = pctl -> samples [ ( int ) ( P * n_samples ) ] ; } else { pctl -> percentile = pctl -> q [ 2 ] ; } }
Calculate the percentile using the P-square algorithm.
Calculate the percentile using the P - square algorithm .
/* For the first MARKERS samples, we calculate the percentile
     * in the traditional way in the pct->q array.
     */ /* From here on, update the markers using quadratic spline calculations */ /* Without enough samples, P-square is not very accurate. Until we reach
     * P_SQUARE_MIN, use a traditional calculation for the percentile.
     */