The latest discussion about strlen optimization raised a question of performance measurements. In this article, I will explain the method that I use for comparing optimized functions and choosing the fastest one. You are welcomed to comment about your favorite performance measurement methods.

1. Choosing the function to measure. The scope of the method

• This method is useful for measuring the tasks that are mostly computation-bounded, e.g. various calculations, cryptographic functions, fractal generation, some text-processing tasks, etc.
• Your data should be located in L1 or L2 cache entirely. If you are measuring memcpy function for several megabytes of data, you should use a different method. Ditto for most image-processing functions and other memory-intensive tasks.
• If your task involves reading or writing files, calling “heavy” API functions, you should use a different method.
• This method is ideal if you have a simple function that is called very often, doesn’t call any API functions, and operates on a small data set.

2. Using RDTSC instruction

The RDTSC instruction returns a 64-bit time stamp counter (TSC), which is increased on every clock cycle. It’s the most precise counter available on x86 architecture.

MSVC++ 2005 compiler supports a handy __rdtsc intrinsic that returns the result in 64-bit variable. However, you should flush the instruction pipeline before using RDTSC, so you usually have to use inline assembly function shown below.

3. Serializing the instruction stream

RDTSC can be executed out-of-order, so you should flush the instruction pipeline to prevent the counter from stopping measurement before the code has actually finished executing.

unsigned __int64 inline GetRDTSC() {
   __asm {
      ; Flush the pipeline
      XOR eax, eax
      CPUID
      ; Get RDTSC counter in edx:eax
      RDTSC
   }
}

4. Dealing with context switches

Many people worry about context switches that may occur during the measurement. Context switches on Windows NT take several thousand clock cycles, so they might bias your results. The best way to avoid this problem is to arrange a small test case, so that your thread will be rarely interrupted.

The scheduling quant on Windows NT is 20 msec. If your function takes 60 000 clock cycles on 1 GHz processor, there is 0.3% probability that the context switch will happen. On the other hand, if your function takes 100 times more, it will be interrupted with 30% probability.

Some people use SetPriorityClass with REALTIME_PRIORITY_CLASS, SetThreadPriority with THREAD_PRIORITY_TIME_CRITICAL, or SetProcessPriorityBoost to prevent their threads from being preempted. This can help sometimes, but it’s not a panacea. Please don’t try to measure the functions that take several seconds with this method.

5. Handling multi-core processors
Time-stamp counters on different cores or different processors are not synchonized with each other. Use SetThreadAffinityMask function to prevent your function from executing on different cores.

6. Repeating the measurements

To detect the context switches and eliminate cache warm-up effects, you should repeat the measurements at least 5 times. The last measurements should give constant results:

     strlen:       1489 ticks  <== cache warm-up
     strlen:       1041 ticks
     strlen:       1041 ticks
     strlen:       1034 ticks
     strlen:       1013 ticks
     strlen:       1019 ticks
     strlen:       1019 ticks
     strlen:       1019 ticks
     strlen:       1019 ticks
     strlen:       1019 ticks
     strlen:       1019 ticks

The result for this function will be 1019 clock cycles.

7. Subtracting overhead

Intel and Agner Fog recommend measuring the overhead of RDTSC function and subtracting it from your result. The overhead is relatively low (150-200 clock cycles) and it occurs in all tested functions, so you can neglect it when measuring long functions (e.g., 100 000 clock cycles).

If you are measuring a short function, you should subtract the overhead using the method described in Intel’s paper.

8. Preventing frequency changes

If your processor supports Intel SpeedStep (usually supported on laptop computers), you should set the power management scheme in Windows to “Always on” before starting long measurements. Otherwise, the processor will change its frequency, and the process of switching to another frequency (”power state transition”, in Intel terminology) may bias your results.

9. Reporting the result in clock cycles, not in seconds

You should not convert your results to seconds. Report them in clock cycles.

From user’s point of view, execution time in seconds makes more sense than clock cycles. But remember that:

time_in_seconds = number_of_clock_cycles / frequency

Frequency is a constant (we are comparing the functions on the same processor), so both methods will give the same result.

Clock cycles are more useful, because you can calculate the theoretical number of clock cycles using the Agner Fog’s instruction tables and compare it with the real number. If you also monitor performance events (see below), you will know not only which function is faster, but also why it is faster and how to improve it.

Also note that your processor counts in clock cycles, not in seconds. For example, your function takes 5000 clock cycles on 1.5 GHz Pentium M processor. If you will switch the processor to 600 MHz (using Intel SpeedStep), it will take 5000 clock cycles again. Moreover, on another Pentium M with different frequency, the function will take 5000 clock cycles.

The time in clock cycles in a consistent, predicable measure, which is independent of frequency changes.

10. Getting not only timings, but also performance event counters

Reporting only execution time is not enough. If you wish to know the reasons of low performance, you should use performance events monitor (RDPMC instruction), which report you the precise reasons of slow down (for example, is it slow because of cache misses? partial register stalls? instruction fetch stalls?). You can get performance events data with these programs:

• AMD CodeAnalyst (freeware, for AMD processors only);
• Intel VTune (very expensive and buggy bloatware);
• Agner Fog’s TestP.Zip package (open source, for all kinds of processors).

Common misunderstandings of the concept
(from private communication and articles by other authors)

You should repeat the test 1000 times, so it will take several seconds, and then average the time

You will get a lot of context switches. The possible implications:

• Because the real code does not call the function 1000 times on the same data, your cache usage pattern will be different from the real code. You must be careful enough to reproduce the real cache usage pattern in your tests. It’s hard.
• The processes executing in background may do crazy things, for example, your Vista indexing service will decide it’s a good time to index your folders.
• You cannot monitor performance events, because you don’t know which performance events are from your program, and which are not. So you will have to optimize blindly, using trial-and-error method without understanding the real reasons of bad performance.

Instead of such tests, I recommend running the whole program on real data. Your cache usage pattern will then be absolutely real and reliable. Also, the execution time on real data is more valuable to the end user than the time that some synthesized test takes.

So, you should have two tests: the one with the small function, which is known to be a bottleneck, and the one with the large program and the real data for estimating the overall effect of your optimization. In the first case, the time will be measured with RDTSC in clock cycles. In the second case, it will be measured in seconds (you can even use GetTickCount for this case).

Microsoft recommends using QueryPerformanceCounter instead of RDTSC

• Note that Microsoft does not recommend using RDTSC for game timing, not for performance measurements. Timing in games is a completely different topic.
• QueryPerformanceCounter can report data from various counters, and one of them is RDTSC. On single-core processors without Intel SpeedStep, QueryPerformanceCounter is implemented using RDTSC. The function just adds a lot of overhead and some additional problems. As the developer of VirtualDub says:
  

  So, realistically, using QueryPerformanceCounter actually exposes you to all of the existing problems of the time stamp counter AND some other bugs.

• When used with care and understanding, RDTSC is more precise than QueryPerformanceCounter. See the thread where a person tried both methods and finally chose RDTSC.
• Microsoft itself uses RDTSC in Visual Studio profiler.

Recommended reading

• Using the RDTSC Instruction for Performance Monitoring by Intel
• TestP.zip package by Agner Fog (also read his manual “Optimizing subroutines in assembly language”, chapter 18, “Measuring performance”)
• Getting accurate per thread timing on Windows by John Lyon-Smith

Error in Intel’s paper (on page 5):

rdtsc
sub             eax, time_low
sub             edx, time_high

should be

rdtsc
sub             eax, time_low
sbb             edx, time_high  ; Subtract with borrow from low 32 bits