What Makes Humans Efficient Makes Computers Efficient

Erik Berg
Computer Science
Uppsala University
October 2003

Computer programs are often slow. But in many cases this is not necessary. Many programs, from games to search engines like Google, can be made to run much faster if the designers just knew how to redesign them. The problem is that it is often difficult to figure out what to do to make them faster. Therefore I develop tools and methods to analyze programs to tell whether they can run faster or not and how they can be improved.

Think of an office worker sitting by his desk. He is very fast, but not very bright, so he follows his instructions step by step. Once in a while he needs information from a binder in archive in the next building. He
calls the secretary and ask her to bring it. The office worker rolls his thumbs while the secretary fetches the binder. Obviously, he will spend most of the days rolling his thumbs if he often need extra information from the archive. Now, let's put a small book shelf on
the office worker's desk where he can store some often-used binders.
This should speed up his work a lot.

This is actually how a computer works. In a computer you have a processor, that's the office worker, and a memory, that's the archive. Getting information from the memory is slow compared to the processor. Therefore all modern computers have a small but fast scratch pad memory, called cache, that stores the most recently used information. The longer the computer can work on the small piece of information that fits in the cache, the faster it will go.

For example, take a computer program for producing animated movies. The movie is made of a lot of pictures. While the memory can store the complete movie, the cache is often to small to store even a single picture. Thus, if the computer is programmed to work on small pieces of the picture at a time instead of jumping around and work on one point here and one point there, the computer will work much faster. The designers of this computer program need a way to determine if they have anything to gain from changing their program or not and how small pieces it has to work on at a time.

In my research, I study how computer programs behave and how often they have to move new data from the main memory into the small fast cache memory. I develop an analysis method that observes how often certain memory objects are requested from the memory and measure the time it takes before the processor needs them again. If the processor reuses information within a short time, it is likely to still be in the cache, but if it takes a long time untill it is reused the program will run slow because the processor has to go all the way to the memory to fetch the information again.

A profiling tool I develop uses this analysis method. The profiling tool is run on the computer together with the program that the designers want to improve and gives feedback on how well the program manages to take advantage of the cache memory.