Abstract:
A method for measuring performance with RDTSC instruction.

Created 2 years ago by Peter Kankowski
Last changed 2 years ago
Contributors: Ace and Marcus Aurelius
Filed under Low-level code optimization

Reddit Digg Delicious Buzz Facebook Twitter

Performance measurements with RDTSC

This article explain a method for comparing optimized functions and choosing the fastest one.

The scope of the method

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.

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
   }
}

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.

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.

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  <== constant performance is reached
     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.

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.

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.

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 the same 5000 clock cycles. Moreover, on another Pentium M with different frequency, the function will take 5000 clock cycles again.

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

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:

Common misunderstandings of the concept

Responses collected 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:

Instead of such tests, you should run 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.

Recommended reading

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

16 comments

Ten recent comments are shown below. Show all comments

Simon (enhzflep), 2 years ago
Great site Peter, I found this after following a link from your CodeProject article on determining the correct form of a plural to use.
It's so refreshing to see somebody that still cares about small code size, efficient execution. Just learned about the concept of cache-warmup from here today. Many thanks, and keep up the good work.
Peter Kankowski, 2 years ago
Thank you for kind words, Simon!
henrin, 7 months ago
Here is how I use rdtsc with VC6:

--1-- In some perf.h file:
#define GCLK(m) {__int64 _t=rdtsc(); m; _t=rdtsc()-_t; printf("\n:CLK: %-50.50s :%14I64d",#m,_t);}
static __int64 rdtsc(void) { __asm rdtsc }		/* read CPU clock counter */
--2-- In the source file where I need to trace the execution time:
#include "perf.h"
..
GLCK(some code)
..
Remarks:
- ease of use: bracket the tested code and put GCLK before the 1st bracket.
- this piece of code is the m parameter of the macro GCLK
- if cannot exceed about 512 characters
- is used as compiled code and as a text string (only the 1st 50 characters are printed)
- the 64-bit integer declaration and format may vary with other compilers
Stein0r, 7 days ago
Which instructions / functions do you recommend for the performance measurement of bigger program parts involving I/O and "heavy" API functions?

If I e.g. want to know how long it averagely takes my program to process a certain file...
Can't I simply take a rdtsc measurement before and after and do this very often to eliminate caching effects, etc. ?
Stein0r, 7 days ago
sry, my previous post might be misunderstood so i have to rectify it: i don't want to "eliminate" caching effects, just average them as they are a "natural part" of my process :-).

i can't find a reason why rdtsc might be unsuitable to measure the time my program needs to perform certain operations involving I/O and lots of memory :-).

am i right to suppose that the "scope of the method" is only targeted at people who directly want to compare the performance of two implementations of the same function ... ?

great site btw!
Peter Kankowski, 7 days ago

Thank you for kind words :) RDTSC can be useful for longer intervals if you take some measures:

  • prevent switches to another core (call SetThreadAffinityMask),
  • eliminate changes in processor frequency (use processors with a constant rate TSC),
  • convert the result to milliseconds (because it's meaningless to measure, say, HDD access time in processor clock cycles).

I would use QueryPerformanceCounter for I/O and heavy API functions. The resolution is less than 1 microsecond; the result can be easily converted to microseconds (10−6 sec) or milliseconds (10−3 sec) using QueryPerformanceFrequency. There is no problem with changing processor frequency.

Stein0r, 6 days ago
thanks for your quick response...

...but i still have some questions :-) .

my measurements are taken in different threads (main thread, I/O thread, ...)
why do i have to make sure my code is executed on one core only?
the measurements are taken inside of threads running on one of the cores---measuring durations.
so even if the time stamp counters on different cores are not synchronized that shouldn't matter imho
because each of them is calculating a relative value ... (?)

isn't it possible to eliminate changes to processor frequency by adjusting the power settings of the operating system, as you said?

the conversion to milliseconds is done in the last step by measuring how many cycles it takes to wait one second (several times).
even if there is a slight measurement error in this, this error is still relative as all measured values are affected in the same way :-) ...

i still think that rdtsc is the best choice for those kinds of measurements under controlled measuring conditions. as you said: it is very fast and precise and has no overhead or bugs associated with it. it's just a pretty light weight, readily available cpu instruction, not an os api call.

best regards
Stein0r, 6 days ago
you really should implement a possibility to edit comments...
i wanted to add: are my assumptions correct? :-)
Peter Kankowski, 6 days ago

Your thread may be scheduled to different cores. Normally, OS selects the first available core, so you may end up starting the counter on one core, and finishing on another core (if there is a context switch during measurement). SetThreadAffinityMask prevents this.

On Pentium M, you can turn off SpeedStep using power settings. Newer processors have Turbo Boost, but they also feature a constant-rate counter, which is independent of frequency changes.

Generally, you are right: RDTSC is a good choice if you are careful to avoid the problem with multiple cores.

I will add the ability to edit comments later. Thanks :)

ace, 4 days ago
IMHO, using RDTSC "for the performance measurement of bigger program parts involving I/O and "heavy" API functions" with multiple threads is almost like using a single 15-inch ruler to measure the distance between Moscow and Paris. It's technically possible but it doesn't have much sense.
Your name:
Comment: