linux-kernel - Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 11 Apr 2016 17:59:11 +0100
From:	Dietmar Eggemann <dietmar.eggemann@....com>
To:	Yuyang Du <yuyang.du@...el.com>, peterz@...radead.org,
	mingo@...nel.org, linux-kernel@...r.kernel.org
Cc:	bsegall@...gle.com, pjt@...gle.com, morten.rasmussen@....com,
	vincent.guittot@...aro.org, juri.lelli@....com
Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup
 table

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

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();
 }

[...]