What are the reasons for great performance differences running the same program?

Question

I wrote a Python program that has to perform some expensive spatial searches while holding lots of data in memory. I tried to improve the performance, that is tried different approaches (see my question here for example).

First, and maybe not so surprisingly, I found great performance differences when running the same code on two different machines (up to 6 x faster on one machine).

Then however and very much to my own surprise, running the exactly same code on the same machine on two different days showed great performance differences.

To give you a rough idea what I mean by great.

Machine 1, day 1: 11 minutes

Machine 1, day 2: 2 minutes

There was no reboot in the meantime by the way.

What could be possible reasons for this difference? How can I can I make sure my system is ready for high performance when I start running my program?

Answer 1

This has a lot to do with the OS, the other processes running, and the amount of memory being used. The OS will let each process have a certain number of CPU cycles before it switches to the next process. If there are lots of other processes, it will be longer between each time your program gets access to the CPU. Also, since your program holds lots of data in memory, when the CPU switches to a different process, this data may have to be moved out of memory. This will require it to be temporarily written to disk which is a slow process (relative to other operations in a computer).

Basically there are many factors that can cause the difference in time. However, in most systems, you can set your program to run with greater importance than other processes. This will differ based on the OS you run. That could help to speed up the running time because your program will be given a higher priority to run over other processes.

Answer 2

First, and maybe not so surprisingly, I found great performance differences when running the same code on two different machines (up to 6 x faster on one machine).

Then however and very much to my own surprise, running the exactly same code on the same machine on two different days showed great performance differences.

Performance measurement is a surprisingly hard topic and huge differences such as what you observed are very common. There is a lot of known measurement bias such as:

1. OS noise, as suggested by DFord's answer
2. OS policies (such as scheduler, memory mapper and IO-cache)
3. Environment variables, even unused ones
4. Memory alignment
5. Memory localisation

Each of these parameters may greatly influence the performance of your program. If you want to prepare your program “for high performance” then:

1. Devise strategies to sanitize environment so that you gain some control over parameters 1-5 above.

2. Devise tests to determine which combination of parameters do well.

The key point here is that experiments need to be reproducible. If you are not able to reproduce an experiment, then it includes a source of randomness that you need to get a grasp on. And first of all, if you are not able to reproduce an experiment, then the results of the experiments are random and you probably do not want to take decisions based on random values, do you?

---

While this is not really the question you asked, I guess you are interested in performance measurement. Here are a few references I suggest to you:

http://compilers.iecc.com/comparch/article/96-02-165

Boehm commenting about execution speed for the same binary varying by a factor of 2 depending on cache placement

http://www.inf.usi.ch/faculty/hauswirth/publications/asplos09.pdf

Producing Wrong Data Without Doing Anything Obviously Wrong! It is very easy to read, contains surprising results, and give a very good feeling of the difficulty of performance measurement and a few methods to produce (more) reliable results.

http://plasma.cs.umass.edu/emery/stabilizer

“Stabilizer is a compiler and runtime system that enables statistically rigorous performance evaluation.” There is a scientific publication claiming to prove that -O3 and -O2 in gcc are not distinguishable, you will find plenty of interesting references in there.

As a final word, you just discovered with your measurements that wall clock does not provide a useful information when it comes to measure performance of programs, so that you will never get a useful answer to a question such as “how long runs my program?” and you have to consider more precise statements.

Answer 3

Radical, unexplained, apparently random changes in execution time are a consequence of the chaotic nature of such complex systems. and by complex systems, i go so far as to include, BUGS, as part of the complexity. You may be hitting a major bug somewhere in your programs, a bug that only manifests itself in certain situations and slows your program seemingly randomly ( until you figure it out )

see this bug in SQL server for an example of tracking this down.

http://support.microsoft.com/kb/2570501

so, the point is, you add more processors, your programs gets slower. until you isolate and correct this bug, a bug in SQL server itself.

Answer 4

Using two different machines to compare a program is out of question. There are so many factors that affect the results (different hardware, different software, caches, other processes running, etc.) that what you get has no value.

When using the same machine, you can do some things to make the results more reliable. A few examples: (1) Always reboot before starting a new benchmark. It's the only way of ensuring that all caches are cold. (2) Run the same benchmark multiple times (eg. at least five) and average the results instead of relying on a single execution. (3) Consider switching into single user mode or stopping all the rest running programs/services (unless they're absolutely necessary), since they might affect the execution time of your program.

If you want to know more about how hard proper benchmarking is I recommend A Nine Year Study of File System and Storage Benchmarking