Re: Stablilizing execution time?
Hubert A. Bahr (hab@ece.engr.ucf.edu)
Sun, 21 Jul 1996 18:02:05 +0000
Mike Black wrote:
>
> At 07:48 AM 7/19/96 +0300, Linus Torvalds wrote:
> >
> >On Thu, 18 Jul 1996, Hubert A. Bahr wrote:
> >>
> >> What can be done beyond running in single user mode to
> >> bring execution time to a more repeatable state.
> >
> >You are unlikely to get much system time variation, as the kernel seldom
> >does anything which is very susceptible to cache effects. Most of the
> >time difference is likely to be in user mode or in IO effects (and I
> >assume you have minimized those effects? I assume it's CPU-bound?)
> >
This was in reference to the system portion of the timeing which was not
significant. The user time was the problem and does seem very much cache
dependent. Virtual memory allocation of pages can really confuse this
issue.
>
> Unfortunately Hubert doesn't who his times...sigh...
>
> I expect that his major problem is between the first and second execution.
> The first execution should always be slower that the second as it will
> rearrange the cache for it's own use. This can be quite noticeable if
> Hubert is running X with 16meg as it will have to start swapping in order to
> accomodate 4Meg of data. 2nd and subsequent executions should show fairly
> consistent behaviour as long as NOTHING else is done between them to change
> the cache arrangement.
I don't give my times as order and and other factors didn't seem to
correlate with the results. By saying I was running in single user mode I
implied I had stripped the runtime load to the absolute minimum. Linus and
I discussed this in slightly more detail where Linus made a couple of suggestions
the first was to execute A large Memory dirtying program just in front of the
timed execution each time. I did that with no positive results if anything I saw
a bigger variation yet. The second was to physically partition memory by telling
linux on bootup about only part of the memory thereby reserving the rest of
your memory as your own private data area. I did not try it as I didn't feel
that I had enough memory or confidence that it would pay off. As I wasn't
interested in another research project right now I went back to the accepted
practice of collecting data on 100 trials applied statistics and made the
comparisons.
Mike you are welcome to try the code. Timing, distributions, Statistics
etc. are all part of a published document. You are only about an Hour
away from campus but I don't believe you will have any better results.
It is in the Library in UCF as an appendix to my MsCpe Thesis Fall '94.
>
> This does bring up an interesting point though...is there (or should there
> be) a cache flush program? Would be real handy in situations like this.
> Something which invalidates all cache pages would allow for consistent bench
> marking.
>
Linus mentioned that long term he had plans for "page coloring" that
should improve this situation but nothing nearterm.
Someone else mentioned the option of executing imeadiately upon a very
minimal system bootup. This was considered but not tried as being impractical
since multiple attempts would need to be made to validate the approach and it
would be very user intensive. The statistical approach can be put in a shell
script and allowed to execute unattended. The data reduction could also be
automated.
My main point is that runtime comparisons that show variations of less
than 10% or even greater when testing algorithms with tic counts are not valid
unless enough samples are taken to make the results statistically valid.
>-
> /----------------------------------------------------------\
> | Mike Black mblack@csihq.com 407-676-5118, x203 |
> | Computer Science Innovations, Inc. 407-676-2355 FAX |
> | Melbourne FL 32904-2314 http://www.csihq.com |
> \----------------------------------------------------------/
Hubert Bahr
407-679-0815