7

I'm writing a program similar to Python's timeit module. The idea is to time a function by executing it anywhere from 10 to 100,000 times depending on how long it takes and then report results.

I've read that the most important number is the minimum execution time because this is the number that best reflects how fast the machine can run the code in question in the absence of other programs competing for processor time and memory. This argument makes sense to me.

Would you be happy with this?

Would you want to know the average time or the standard deviation? Is there some other measure that you consider more important?

aaronasterling
  • 375
  • 1
  • 9
  • When you say profiling a function for time use, it looks like you mean timing how long the function takes, and getting the distribution of that. If you're interested in the bigger problem of how to make code faster, there's more to say on it. – Mike Dunlavey Jan 05 '11 at 18:22

2 Answers2

3

The first question, is does your function do the same difficulty of computation every time? Or are some inputs intrinsically harder than others? Then what matters depends upon the environment it is to be used in. If it is a realtime application, there may be a hard upper bound on acceptable execution time. For most purposes average execution time would be relevant. Note that even for an unloaded machine -say you are only running a single thread, even processes that have the same formal compuational complexity (and even execute exactly the same instructions), might have greatly differing execution times, depending upon the pre-existing state of the cache memory, state of the TLB, etc. Performance of modern machines is not simple at all. Even the execution time of a chunk of code is no longer a good metric. For every chunk of code that is executed, the state of cache, the TLB, etc are altered, so the execution speed of whatever process follows, depends in a non trivial way upon what went on before.

Omega Centauri
  • 1,038
  • 5
  • 8
2

You definitely need more than a single value returned.

I would see Mean, Min, Max and Standard Deviation as a minimum to use the information in a statistically meaningful manner.

There are a lot of issues that can affect performance that have variances even on a 'clean machine', even more so now that we are moving into a world with increasingly parallel processing and all the complexities with scheduling, etc that it brings.

Dan McGrath
  • 11,163
  • 6
  • 55
  • 81
  • "statistically meaningful manner"? Aren't rough numbers fine? I would be surprised if the percentage of programmers in the world who know or need to know any statistics is as high as 1%. How many of them are doing hypothesis testing on program speed? I've never met any. They do like to talk about it, though, as if it does matter. – Mike Dunlavey Dec 31 '10 at 02:01
  • In some cases, rough numbers are fine. As soon as you start working on complex real-time systems, assuming "rough numbers are fine" is at best, naive. For example, I've done work here on a real-time transaction system for which "rough numbers" where used to evaluate its effectiveness. Unfortunately, they just looked at the 'mean' of calling the method millions of times which had it at sub 20ms response per call. The catch? It generally ran at < 1ms but It would occasionally spike to up to 60 seconds which was quite disastrous. – Dan McGrath Dec 31 '10 at 03:10
  • Also, if you want to build effective user interfaces, consistently fast response times matter. Std Dev can be quite informative to how it is really behaving – Dan McGrath Dec 31 '10 at 03:15
  • OK Dan, point taken. – Mike Dunlavey Dec 31 '10 at 16:28