sched: Make __update_entity_runnable_avg() fast
authorPaul Turner <pjt@google.com>
Thu, 4 Oct 2012 11:18:32 +0000 (13:18 +0200)
committerIngo Molnar <mingo@kernel.org>
Wed, 24 Oct 2012 08:27:30 +0000 (10:27 +0200)
commit5b51f2f80b3b906ce59bd4dce6eca3c7f34cb1b9
tree72e7c6003b377646d4ba4defa2ddf43756e81474
parentf269ae0469fc882332bdfb5db15d3c1315fe2a10
sched: Make __update_entity_runnable_avg() fast

__update_entity_runnable_avg forms the core of maintaining an entity's runnable
load average.  In this function we charge the accumulated run-time since last
update and handle appropriate decay.  In some cases, e.g. a waking task, this
time interval may be much larger than our period unit.

Fortunately we can exploit some properties of our series to perform decay for a
blocked update in constant time and account the contribution for a running
update in essentially-constant* time.

[*]: For any running entity they should be performing updates at the tick which
gives us a soft limit of 1 jiffy between updates, and we can compute up to a
32 jiffy update in a single pass.

C program to generate the magic constants in the arrays:

  #include <math.h>
  #include <stdio.h>

  #define N 32
  #define WMULT_SHIFT 32

  const long WMULT_CONST = ((1UL << N) - 1);
  double y;

  long runnable_avg_yN_inv[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);
   runnable_avg_yN_inv[i] = yn;
   printf("%2d: 0x%8lx\n", i, runnable_avg_yN_inv[i]);
   }
   printf("\n");
  }

  long mult_inv(long c, int n) {
   return (c * runnable_avg_yN_inv[n]) >>  WMULT_SHIFT;
  }

  void calc_yn_sum(int n)
  {
   int i;
   double sum = 0, sum_fl = 0, diff = 0;

   /*
    * We take the floored sum to ensure the sum of partial sums is never
    * larger than the actual sum.
    */
   printf("sum y^n\n");
   printf("   %8s  %8s %8s\n", "exact", "floor", "error");
   for (i = 1; i <= n; i++) {
   sum = (y * sum + y * 1024);
   sum_fl = floor(y * sum_fl+ y * 1024);
   printf("%2d: %8.0f  %8.0f %8.0f\n", i, sum, sum_fl,
   sum_fl - sum);
   }
   printf("\n");
  }

  void calc_conv(long n) {
   long old_n;
   int i = -1;

   printf("convergence (LOAD_AVG_MAX, LOAD_AVG_MAX_N)\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() {
   y = pow(0.5, 1/(double)N);
   calc_mult_inv();
   calc_conv(1024);
   calc_yn_sum(N);
  }

[ Compile with -lm ]
Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/20120823141507.277808946@google.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
kernel/sched/fair.c