lkml.org 
[lkml]   [2019]   [Oct]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Question about sched_prio_to_weight values
On Mon, 7 Oct 2019 10:13:23 +0100 Valentin Schneider wrote:

[...]
> Following the blame rabbit hole I found this:
>
> 254753dc321e ("sched: make the multiplication table more accurate")
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=254753dc321ea2b753ca9bc58ac329557a20efac
>
> which sounds like it would explain some small deltas if compared to a
> formula that is set in stone.
>
> Hope that helps.

It helps a lot, thank you so much for your kind reply!

I am now able to reproduce the numbers (almost), with the following
calc(1) script:

$ cat prio_to_weight.cal
#!/usr/bin/calc -f

oldtilde = config("tilde", "off")


printf('nice mult * inv_mult error\n')
printf('------------------------------------------\n')
for (nice = -20; nice < 20; ++nice) {
w = 1024/(1.25)^(nice);
weight = round(w);
invmul = round(2^32 / weight);
error = weight*invmul / 2^32 - 1;
printf('%3d:%11d *%11d%15.10f\n', nice, weight, invmul, error);
}

printf('\nnice mult * inv_mult error\n')
printf('------------------------------------------\n')
for (nice = -20; nice < 20; ++nice) {
w = 1024/(1.25)^(nice);
for (delta = 0; delta < 1000; ++delta) {
weight = round(w) - delta;
invmul = round(2^32 / weight);
error = weight*invmul / 2^32 - 1;
if (abs(error) < 1e-8) { break; }
weight = round(w) + delta;
invmul = round(2^32 / weight);
error = weight*invmul / 2^32 - 1;
if (abs(error) < 1e-8) { break; }
}
printf('%3d:%11d *%11d%15.10f\n', nice, weight, invmul, error);
}


After running the script:

$ ./prio_to_weight.cal | tail -n 42 | tee prio_to_weight.out
nice mult * inv_mult error
------------------------------------------
-20: 88761 * 48388 -0.0000000065
-19: 71755 * 59856 -0.0000000037
-18: 56483 * 76040 0.0000000056
-17: 46273 * 92818 0.0000000042
-16: 36291 * 118348 -0.0000000065
-15: 29154 * 147320 -0.0000000037
-14: 23254 * 184698 -0.0000000009
-13: 18705 * 229616 -0.0000000037
-12: 14949 * 287308 -0.0000000009
-11: 11916 * 360437 -0.0000000009
-10: 9548 * 449829 -0.0000000009
-9: 7620 * 563644 -0.0000000037
-8: 6100 * 704093 0.0000000009
-7: 4904 * 875809 0.0000000093
-6: 3906 * 1099582 -0.0000000009
-5: 3121 * 1376151 -0.0000000058
-4: 2501 * 1717300 0.0000000009
-3: 1991 * 2157191 -0.0000000035
-2: 1586 * 2708050 0.0000000009
-1: 1277 * 3363326 0.0000000014
0: 1024 * 4194304 0
1: 820 * 5237765 0.0000000009
2: 655 * 6557202 0.0000000033
3: 526 * 8165337 -0.0000000079
4: 423 * 10153587 0.0000000012
5: 335 * 12820798 0.0000000079
6: 272 * 15790321 0.0000000037
7: 215 * 19976592 -0.0000000037
8: 172 * 24970740 -0.0000000037
9: 137 * 31350126 -0.0000000079
10: 110 * 39045157 -0.0000000061
11: 88 * 48806447 0.0000000093
12: 70 * 61356676 0.0000000056
13: 56 * 76695845 0.0000000056
14: 45 * 95443718 0.0000000033
15: 36 * 119304647 -0.0000000009
16: 29 * 148102321 0.0000000030
17: 23 * 186737709 0.0000000026
18: 18 * 238609294 -0.0000000009
19: 15 * 286331153 -0.0000000002

I get an output which is almost identical to the one copied from
the commit message (target.out):

$ diff target.out prio_to_weight.out
34c34
< 11: 87 * 49367440 -0.0000000037
---
> 11: 88 * 48806447 0.0000000093
36,37c36,37
< 13: 56 * 76695844 -0.0000000075
< 14: 45 * 95443717 -0.0000000072
---
> 13: 56 * 76695845 0.0000000056
> 14: 45 * 95443718 0.0000000033
39,40c39,40
< 16: 29 * 148102320 -0.0000000037
< 17: 23 * 186737708 -0.0000000028
---
> 16: 29 * 148102321 0.0000000030
> 17: 23 * 186737709 0.0000000026

The differences are probably due to the different precision
of the computations: I don't know the precision of those originally
carried out by Ingo Molnar (single precision? double?), but calc(1)
is an arbitrary precision calculator and, by default, performs
calculations with epsilon = 1e-20 !

Please note that, except for the first one, all the differing
values obtained with the calc(1) script have slightly better
errors than the ones found in kernel/sched/core.c ...


Thanks again for the clarification!
Bye.

--
http://www.inventati.org/frx/
There's not a second to spare! To the laboratory!
..................................................... Francesco Poli .
GnuPG key fpr == CA01 1147 9CD2 EFDF FB82 3925 3E1C 27E1 1F69 BFFE
[unhandled content-type:application/pgp-signature]
\
 
 \ /
  Last update: 2019-10-07 22:51    [W:0.074 / U:0.088 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site