> Oliver Xymoron <oxymoron@waste.org>:
> : On Tue, 22 Sep 1998, Larry McVoy wrote:
> : > How many times before it sinks in: 77% variance is not cache induced. If
> : > that were true, then nothing would be deterministic. You wouldn't be able
> : > to say "time make" and expect to get anything like the same number two times
> : > in a row, yet people do that all the time.
> :
> : This is not really true, especially for something like make. If you
> : combine n events of average length t and std dev u, you get an event of
> : average length n*t, but a smaller std dev - if you multiply a bunch of
> : bell curves together, you get a tighter curve. The possible range becomes
> : larger, sure.
[run times deleted]
> The claim was that cache interference would explain variations in run
> times of 70-100%.
I agree that this is not likely the proper explanation.
> My counter claim was that if that were true, things
> like make would not be deterministic.
But this is also not likely true. As long as the number of cache accesses
(hits or misses) is relatively high, ie high enough that the cache gets
turned over fairly frequently, the variances of individual cache access
timings tend to cancel each other out.
> I'm not about to hold up this test as scientificly perfect, but it is the
> sort of thing that, given an argument that cache interference causes large
> variations in run time, ought to should some large variations. Instead,
> we're seeing variations of < 6%.
Yes, this is expected. Here's a simple model: Define a process as
something that takes from 0-100 ms. And a make as something that runs 1000
processes (no overhead). Now here's a simulation:
10 runs of one process each
29.8589012119919
27.6316420640796
10.0863066967577
95.3269239515066
80.8217294048518
47.6818275637925
80.5122145451605
10.0866224616766
31.5303748939186
74.7918138280511
avg: 48.83 stddev: 31.58 (64.67)
10 runs of 1000 processes each
50961.29796803
50038.1745733321
50851.941928314
49304.2158972006
48633.5776282474
50144.0852684435
49277.4656228721
49693.5240976512
49526.6901504248
48859.6836516168
avg: 49729.07 stddev: 776.72 (1.56)
Each process above varies radically above and the stddev/avg (close to
what you're calling variance) is huge (64.67%). But put a bunch of these
together as a make and you get only 1.56% - most of the "variance" cancels
out.
Perl script for the above:
#!/usr/bin/perl
sub process
{
# Takes from 0-100 ms
return rand(100);
}
sub make
{
my($total,$i);
for (1..1000)
{
$total+=process();
}
return $total
}
print "10 runs of one process each\n";
for (1..10)
{
$r=process();
push(@results,$r);
print "$r\n";
}
$a=avg(@results);
$u=stddev(@results);
$p=$u/$a*100;
printf "avg: %.2f stddev: %.2f (%.2f)\n",$a,$u,$p;
undef @results;
print "10 runs of 1000 processes each\n";
for (1..10)
{
$r=make();
push(@results,$r);
print "$r\n";
}
$a=avg(@results);
$u=stddev(@results);
$p=$u/$a*100;
printf "avg: %.2f stddev: %.2f (%.2f)\n",$a,$u,$p;
sub avg
{
my($tot);
grep($tot+=$_,@_);
return $tot/scalar(@_);
}
sub variance # Numerical Recipes in Perl, anyone?
{
my($xbar,$tot);
$xbar=avg(@_);
foreach $x (@_)
{
$tot+=($x-$xbar)**2;
}
return $tot/(scalar(@_)-1);
}
sub stddev { return sqrt(variance(@_)); }
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/