lkml.org 
[lkml]   [2012]   [Jul]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH 14/16] sched: make __update_entity_runnable_avg() fast
    From
    Date
    On Wed, 2012-07-11 at 17:15 -0700, Paul Turner wrote:
    > convergence
    > 345> 47765

    Ah, 345 is much saner indeed!

    > And for posterity, a simple generator so that I don't lose it again:
    > #include <math.h>
    > #include <stdio.h>
    >
    > #define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))
    > #define N 32
    > #define WMULT_SHIFT 32
    >
    > const long WMULT_CONST = ((1UL << N) - 1);
    > const double y = .97857206208770013451;

    I used pow(0.5, 1.0/N), no point in loosing precision and mis-typing a
    digit or somesuch nonsense ;-)

    >
    > long approx_decay(int c) {
    > return (c * 4008) >> 12;
    > }
    >
    > long mult_inv_array[N];
    > void calc_mult_inv() {
    > int i;
    > double yn = 0;
    >
    > printf("inverses\n");
    > for (i = 0; i < N; i++) {
    > yn = (double)WMULT_CONST * pow(y, i);
    > mult_inv_array[i] = yn;
    > printf("%d: %8lx\n", i, mult_inv_array[i]);
    > }
    >
    > printf("\n");
    > }
    >
    > long mult_inv(long c, int n) {
    > return SRR(c * runnable_avg_yN_inv[n], WMULT_SHIFT);

    This works much better when you do:

    s/runnable_avg_yN_inv/mult_inv_array/

    > }
    >
    > void calc_yn_sum(int n)
    > {
    > int i;
    > double sum = 0, sum_fl = 0, diff = 0;
    > long approx = 0, approx_fm = 0, approx_fm2 = 0;
    >
    > printf("sum y^n\n");
    > printf(" %8s %8s %8s %8s %8s\n", "exact", "floor", "shift",
    > "fastmul1", "fastmul2");
    > for (i = 1; i < n; i++) {
    > sum = (y * sum + y * 1024);
    > sum_fl = floor(y * sum_fl+ y * 1024);
    > approx = approx_decay(approx) + approx_decay(1024);
    > approx_fm = mult_inv(approx_fm, 1) + mult_inv(1024, 1);
    > approx_fm2 += mult_inv(1024, i);
    >
    > /*diff = sum;*/
    > printf("%2d: %8.0f %8.0f %8ld %8ld %8ld\n", i, sum,
    > sum_fl - diff,
    > approx - (long)diff,
    > approx_fm - (long)diff,
    > approx_fm2 - (long)diff);
    >
    > }
    > printf("\n");
    > }
    >
    > void calc_conv(long n) {
    > long old_n;
    > int i = -1;
    >
    > printf("convergence\n");
    > do {
    > old_n = n;
    > n = mult_inv(n, 1) + 1024;
    > i++;
    > } while (n != old_n);
    > printf("%d> %ld\n", i - 1, n);
    > printf("\n");
    > }
    >
    > void main() {
    > calc_mult_inv();
    > calc_conv(1024);
    > calc_yn_sum(N);
    > }
    >
    >


    \
     
     \ /
      Last update: 2012-07-12 17:21    [W:0.028 / U:30.732 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site