From: Stanislaw Gruszka <sgruszka@redhat.com>
To: Peter Zijlstra <peterz@infradead.org>
Cc: "Linus Torvalds" <torvalds@linux-foundation.org>,
"Linux Kernel Mailing List" <linux-kernel@vger.kernel.org>,
"Ingo Molnar" <mingo@kernel.org>,
"H. Peter Anvin" <hpa@zytor.com>,
"Frédéric Weisbecker" <fweisbec@gmail.com>,
"Steven Rostedt" <rostedt@goodmis.org>,
"Andrew Morton" <akpm@linux-foundation.org>,
"Thomas Gleixner" <tglx@linutronix.de>,
linux-tip-commits@vger.kernel.org
Subject: Re: [tip:sched/core] sched: Lower chances of cputime scaling overflow
Date: Sat, 13 Apr 2013 16:49:35 +0200 [thread overview]
Message-ID: <20130413144934.GA11556@redhat.com> (raw)
In-Reply-To: <1365753356.17140.18.camel@laptop>
[-- Attachment #1: Type: text/plain, Size: 1202 bytes --]
On Fri, Apr 12, 2013 at 09:55:56AM +0200, Peter Zijlstra wrote:
> > The above is totally untested, but each step is pretty damn simple and
> > fairly cheap. Sure, it's a loop, but it's bounded to 32 (cheap)
> > iterations, and the normal case is that it's not done at all, or done
> > only a few times.
>
> Right it gets gradually heavier the bigger the numbers get; which is
> more and more unlikely.
>
> > And the advantage is that the end result is always that simple
> > 32x32/32 case that we started out with as the common case.
> >
> > I dunno. Maybe I'm overlooking something, and the above is horrible,
> > but the above seems reasonably efficient if not optimal, and
> > *understandable*.
>
> I suppose that entirely matters on what one is used to ;-) I had to
> stare rather hard at it for a little while.
>
> But yes, you take it one step further and are willing to ditch rtime
> bits too and I suppose that's fine.
>
> Should work,.. Stanislaw could you stick this into your userspace
> thingy and verify the numbers are sane enough?
It works fine - gives relative error less than 0.1% for very big
numbers.
For the record I'm attaching test program and script.
Thanks
Stanislaw
[-- Attachment #2: scale_stime5.c --]
[-- Type: text/plain, Size: 1587 bytes --]
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <strings.h>
#include <stdint.h>
typedef uint64_t u64;
typedef uint32_t u32;
static u64 div_u64_u32(u64 a, u32 b)
{
return a / b;
}
static u64 scale_stime(u64 stime, u64 rtime, u64 total)
{
/* We know one of the values has a bit set in the high 32 bits */
for (;;) {
/* Make sure "rtime" is the bigger of stime/rtime */
if (stime > rtime) {
u64 tmp = rtime; rtime = stime; stime = tmp;
}
/* Do we need to balance stime/rtime bits? */
if (rtime >> 32) {
if (stime >> 31)
goto drop_precision;
/* We can grow rtime and shrink stime and try to make them both fit */
stime <<= 1;
rtime >>= 1;
continue;
}
/* stime/rtime fits in 32 bits, how about total? */
if (!(total >> 32))
break;
drop_precision:
/* We drop from rtime, it has more bits than stime */
rtime >>= 1;
total >>= 1;
}
if (!total)
return stime;
/* Make sure gcc understands that this is a 32x32->64 multiply,
* followed by a 64/32->64 divide */
return div_u64_u32((u64) (u32) stime * (u64) (u32) rtime, (u32)total);
}
int main(int argc, char *argv[])
{
u64 rtime, total, stime, scaled;
if (argc != 4)
return;
rtime = strtoll(argv[1], NULL, 10);
total = strtoll(argv[2], NULL, 10);
stime = strtoll(argv[3], NULL, 10);
assert (total >= stime);
scaled = scale_stime(stime, rtime, total);
printf("%llu\n", scaled);
return 0;
}
[-- Attachment #3: scale_stime_test5.py --]
[-- Type: text/plain, Size: 999 bytes --]
#!/usr/bin/python
import subprocess
import random
import math
def kernel_scale (rtime, total, stime):
p = subprocess.Popen("./scale_stime5 " + str(rtime) + " " + str(total) + " " + str(stime) , shell=True, stdout=subprocess.PIPE)
return int(p.stdout.read())
def python_scale (rtime, total, stime):
return (stime * rtime) / total
max_rtime = 10*4096*364*24*60*60*1000; # 10 years for 4096 threads
fail=False
K=10000
for i in range(0, K):
rtime = random.randrange(max_rtime)
total = int(random.uniform(0.1, 1.9) * rtime)
for n in range(1, 100):
stime = (n * total / 100)
r1 = kernel_scale(rtime, total, stime)
r2 = python_scale(rtime, total, stime)
if (float(abs(r1 - r2)) / float(r2)) > 0.001:
print "FAIL!"
print "rtime: " + str(rtime)
print "total: " + str(total)
print "stime: " + str(stime)
print "kernel: " + str(r1)
print "python: " + str(r2)
fail=True
break
if fail:
break;
if (i % 100) == 99:
print str(i/100) + "/" + str(K/100) + " OK"
next prev parent reply other threads:[~2013-04-13 14:49 UTC|newest]
Thread overview: 21+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <tip-d9a3c9823a2e6a543eb7807fb3d15d8233817ec5@git.kernel.org>
2013-03-26 14:01 ` [tip:sched/core] sched: Lower chances of cputime scaling overflow Stanislaw Gruszka
2013-03-26 14:19 ` Frederic Weisbecker
2013-03-26 16:54 ` Stanislaw Gruszka
2013-04-10 12:51 ` Ingo Molnar
2013-04-10 15:28 ` Frederic Weisbecker
2013-04-10 17:32 ` Ingo Molnar
2013-04-11 8:04 ` Stanislaw Gruszka
2013-04-11 13:45 ` Peter Zijlstra
2013-04-11 14:50 ` Stanislaw Gruszka
2013-04-11 17:31 ` Peter Zijlstra
2013-04-11 15:38 ` Linus Torvalds
2013-04-11 18:07 ` Peter Zijlstra
2013-04-11 18:22 ` Frederic Weisbecker
2013-04-11 18:26 ` Frederic Weisbecker
2013-04-11 18:22 ` Linus Torvalds
2013-04-12 7:55 ` Peter Zijlstra
2013-04-13 14:49 ` Stanislaw Gruszka [this message]
2013-04-13 18:44 ` Linus Torvalds
2013-04-16 10:40 ` Stanislaw Gruszka
2013-04-30 14:03 ` Stanislaw Gruszka
2013-04-13 14:55 ` Stanislaw Gruszka
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20130413144934.GA11556@redhat.com \
--to=sgruszka@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=fweisbec@gmail.com \
--cc=hpa@zytor.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-tip-commits@vger.kernel.org \
--cc=mingo@kernel.org \
--cc=peterz@infradead.org \
--cc=rostedt@goodmis.org \
--cc=tglx@linutronix.de \
--cc=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).