Messages in this thread | | | Date | Thu, 24 Sep 1998 14:24:29 -0500 (CDT) | From | Oliver Xymoron <> | Subject | Re: Interesting scheduling times - NOT |
| |
On Wed, 23 Sep 1998, Larry McVoy wrote:
> 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/
| |