diff mbox

[1/4] sched/fair: Optimize sum computation with a lookup table

Message ID 570BD7DF.6070400@arm.com
State New
Headers show

Commit Message

Dietmar Eggemann April 11, 2016, 4:59 p.m. UTC 
On 10/04/16 23:36, Yuyang Du wrote:
> __compute_runnable_contrib() uses a loop to compute sum, whereas a

> table loopup can do it faster in a constant time.

> 

> The following python script can be used to generate the constants:

> 

> print " #:     yN_inv   yN_sum"

> print "-----------------------"

> y = (0.5)**(1/32.0)

> x = 2**32

> xx = 1024

> for i in range(0, 32):

> 	if i == 0:

> 		x = x-1

> 		xx = xx*y

> 	else:

> 		x = x*y

> 		xx = int(xx*y + 1024*y)

> 	print "%2d: %#x %8d" % (i, int(x), int(xx))

> 

> print " #:  sum_N32"

> print "------------"

> xxx = xx

> for i in range(0, 11):

> 	if i == 0:

> 		xxx = xx

> 	else:

> 		xxx = xxx/2 + xx

> 	print "%2d: %8d" % (i, xxx)

>


IMHO, it would be nice to add this to the existing tool from the patch
header of commit 5b51f2f80b3b
("sched: Make __update_entity_runnable_avg() fast") simply because people
already use this one to tweak their pelt tables. Maybe something like

[...]

Comments

Juri Lelli April 12, 2016, 12:02 p.m. UTC | #1 
On 11/04/16 16:21, Joe Perches wrote:
> On Mon, 2016-04-11 at 17:59 +0100, Dietmar Eggemann wrote:

> []

> > IMHO, it would be nice to add this to the existing tool from the patch

> > header of commit 5b51f2f80b3b

> > ("sched: Make __update_entity_runnable_avg() fast") simply because people

> > already use this one to tweak their pelt tables.

> 

> Maybe create a file and put it in tools somewhere.

> Maybe tools/sched ?

> 


+1. And I'd stick with the C program.

Best,

- Juri
diff mbox

Patch

diff --git a/pelt.c b/pelt.c
index 63e32d1d18b0..b36194e8bb9c 100644
--- a/pelt.c
+++ b/pelt.c
@@ -6,6 +6,8 @@ 

 const long WMULT_CONST = ((1UL << N) - 1);
 double y;
+int ld_avg_max_n;
+double sum_fl_n;

 long runnable_avg_yN_inv[N];
 void calc_mult_inv() {
@@ -42,6 +44,7 @@  void calc_yn_sum(int n)
                printf("%2d: %8.0f  %8.0f %8.0f\n", i, sum, sum_fl,
                        sum_fl - sum);
        }
+       sum_fl_n = sum_fl;
        printf("\n");
 }

@@ -55,14 +58,29 @@  void calc_conv(long n) {
                n = mult_inv(n, 1) + 1024;
                i++;
        } while (n != old_n);
+       ld_avg_max_n = i - 1;
        printf("%d> %ld\n", i - 1, n);
        printf("\n");
 }

+void calc_acc_sum() {
+       int i = 1;
+       double sum = sum_fl_n;
+       int periods = ld_avg_max_n/N + 1;
+
+       printf("sum acc\n");
+
+       do {
+               printf("%2d: %8.0f\n", i, sum);
+               sum = floor(sum/2 + sum_fl_n);
+       } while (++i <= periods);
+}
+
 void main() {
        y = pow(0.5, 1/(double)N);
        calc_mult_inv();
        calc_conv(1024);
        calc_yn_sum(N);
+       calc_acc_sum();
 }