10
\$\begingroup\$

The Win32 API has a so-called 'high performance counter' (QueryPerformanceCounter() and friends) but often it is neither precise enough nor reliable enough, due to high jitter.

The low resolution is no surprise since the value is often derived by shifting off the 10 low bits of the CPU's time stamp counter (TSC), after adding a value that reflects the cumulative sleep/hibernation time of the system. A good overview of the official story is given in the MSDN article "Acquiring high-resolution time stamps."

On many (most?) reasonably non-ancient systems the time stamp counter is global - shared by all logical CPUs in the processor package - which is how Windows can use it for timing purposes in the first place. This makes the RDTSC instruction even more attractive than it always has been, since it can now also be used for global timing measurements of longer duration - across time slices and across logical CPUs. For many purposes it's just as good as QueryPerformanceCounter() but a thousand times as precise.

However, modern CPUs with their deep pipelines and out-of-order execution add another difficulty. By the time the TSC value is read out, some of the instructions preceding RDTSC may not have finished executing and/or some instructions that follow RDTSC may already have been executed. These vagaries introduce a lot of jitter when the TSC is used for timing code fragments.

The CPUID instruction comes to the rescue here since it has a serialising effect on the execution of the instruction stream; it basically acts like a full barrier. When CPUID returns, all preceding instructions will have finished execution and none of the instructions following it will have begun execution. Its drawback is that it takes hundreds of cycles to execute and that its execution time is highly variable. That's no problem if CPUID is placed before the initial TSC measuremnt - before the code fragment to be timed - but it's a big problem for the second measurement, after the execution of the code fragment to be timed.

This is where RDTSCP comes in. This instruction is available on most reasonably modern CPUs, and it forces the retirement of all instructions that precede it in the instruction stream (i.e. the instructions of the code fragment to be timed). A CPUID instruction can then be placed after the RDTSCP - where its own timing cannot add to the measured time - in order to keep subsequent instructions from jumping the queue.

A good overview of various issues is in Performance measurements with RDTSC, including cache considerations and so on. The full story about precise measurements with RDTSC is in Intel's article How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures.

Hence the timing of a code fragment can be done like this:

t0 := RdTSC0;        // CPUID before RDTSC
code_to_be_timed;
t1 := RdTSC1;        // CPUID after RDTSCP

cycles := t1 - t0;

Note: this applies only to measuring the cycles for code that can be bracketed as shown above, since RdTSC0 adds lots of cycles before the initial measurement and RdTSC1 adds lots of cycles after the second measurement.

For flank-to-flank measurements of external events it is best to use plain RDTSCP without CPUID at the back. The reason is that the reading of the TSC must still be kept from occurring before the instruction that detects the external event (like the change of a shared memory location), which requires RDTSCP instead of plain RDTSC, but there is no place where a CPUID instruction can be stowed without its timing getting in the way.

Hence, precise timing calls for three different functions that read the TSC: a pair RdTSC0 and RdTSC1 for bracketing code fragments, and RdTSCP for flank-to-flank measurements. Of course, there 's a ton of auxiliary functions that are necessary - like for setting thread affinity and priority, or even a humble Sleep(0) in the right places - but those won't be shown here.

At long last, here's the code for the three TSC functions:

type
   TTicks64 = type Int64;  // signed, so that deltas can be represented cleanly

///////////////////////////////////////////////////////////////////////////////////////////////////
// CPUID implements a full barrier; it doesn't influence the timing as it is called before RDTSC.
// Full story: ia-32-ia-64-benchmark-code-execution-paper.pdf

function RdTSC0: TTicks64;  // the 'before' tick
asm
{$ifdef CPUX64}
         xor   rax, rax
         push  rbx          // Delphi requires EBX/RBX to be preserved
         cpuid              // full fence
         pop   rbx
         rdtsc
         shl   rdx, 32
         or    rax, rdx
{$else}
         xor   eax, eax
         push  ebx
         cpuid
         pop   ebx
         rdtsc
{$endif}
end;

//--------------------------------------------------------------------------------------------------
// RDTSCP implements a sort of read fence: it waits until all preceding instructions in the stream
// have been executed but it doesn't keep later instruction from jumping the queue. That's why the
// RDTSCP is bracketed by CPUID from behind.

function RdTSC1: TTicks64;  // the 'after' tick
asm
{$ifdef CPUX64}
   {$ifdef ZX_dont_use_RDTSCP}
         rdtsc
   {$else}
         rdtscp
   {$endif}
         shl   rdx, 32
         or    rdx, rax
         xor   rax, rax
         push  rbx
         push  rdx
         cpuid
         pop   rax
         pop   rbx
{$else}
   {$ifdef ZX_dont_use_RDTSCP}
         rdtsc
   {$else}
         db    $0F, $01, $F9  // rdtscp; X2 understands the mnemonic for x64 but not for x86
   {$endif}
         push  eax
         xor   eax, eax
         push  edx
         push  ebx
         cpuid
         pop   ebx
         pop   edx
         pop   eax
{$endif}
end;

//-------------------------------------------------------------------------------------------------
// for flank-to-flank measurements

function RdTSCP: TTicks64;
asm
{$ifdef CPUX64}
   {$ifdef ZX_dont_use_RDTSCP}
         rdtsc
   {$else}
         rdtscp
   {$endif}
         shl   rdx, 32
         or    rax, rdx
{$else}
   {$ifdef ZX_dont_use_RDTSCP}
         rdtsc
   {$else}
         db    $0F, $01, $F9  // rdtscp; X2 understands the mnemonic for x64 but not for x86
   {$endif}
{$endif}
end;

The ZX_dont_use_RDTSCP $define is there to allow compilation without RDTSCP. It makes the measurements less precise but it offers a quick and dirty way of compiling test programs for older CPUs, where the code with RDTSCP would bomb.

Whether a given machine has a suitable TSC can be ascertained in two different ways.

A quick and dirty manual way is tracing into QueryPerformanceCounter(); if that thing uses RDTSC then it's presumably okay to do so.

Another way is to run a bit of test code on every logical CPU in parallel; each thread must be confined to its own logical CPU by setting thread affinity, and thread priority must be raised to the max to increase the likelihood of getting a clean test run without preemption. Glossing over a lot of details, the important bits of the test code look like this:

constructor CTestThread.Create (mask_bit: DWORD_PTR);
begin
   inherited Create(true);
   FreeOnTerminate := false;  // so that the calling code can read results
   if SetThreadAffinityMask(Handle, mask_bit) = 0 then
      zw_ThrowLastWin32Error('SetThreadAffinityMask');
   if not SetThreadPriority(Handle, THREAD_PRIORITY_TIME_CRITICAL) then
      zw_ThrowLastWin32Error('SetThreadPriority');
end;

//-------------------------------------------------------------------------------------------------

procedure CTestThread.Execute;
begin
   t0.measure;
   g_start_event.WaitFor;
   t1.measure;
   if InterlockedDecrement(g_sleeping) = 0 then
      m_woken_last := true
   else
      while g_sleeping <> 0 do
         ;
   t2.measure;
end;

g_sleeping is initialised to the number of threads (logical CPUs) by the thread that initialises the whole shebang, before it rings in the fun by setting the global g_start_event. This event is intended to offer rough synchronisation between threads, before they start precise synchronisation by spinning on the g_sleeping. This reduces the time during which the system is unresponsive.

Each thread gets a different bit from the 1-bits found in the affinity mask of the process. t0 etc. are timers that are member variables of the test threads.

Sample output on my notebook:

mask         t0               t1        t1-min(t1)         t2        t2-min(t2)
-------------------------------------------------------------------------------
0001: 000000003905436A 00000000390CE1E7          0  000000003910B14D         69
0002: 000000003907DA4B 00000000390CEBC7       2528  000000003910B14B         67
0004: 0000000039095559 00000000390DA98E      51111  000000003910B12E         38
0008: 00000000390CAC0E 00000000390DA960      51065  000000003910B143         59
0010: 00000000390E1E4D 00000000390E292A      83779  000000003910B12D         37
0020: 00000000390F0F2F 00000000390F1826     144959  000000003910B149         65
0040: 0000000039101DF6 0000000039102965     214910  000000003910B139         49
0080: 000000003910A73C 000000003910AF25     249150  000000003910B108 *        0

Obviously, the thread that is the last to decrement g_sleeping (i.e. m_woken_last == true, marked with a star) will be the only one that can make it to the t2 measurement without delay. The other threads have to wait for the memory change go propagate through their cache hierarchies.

Still, it can be seen that spinning on a global variable manages to synchronise all threads to within about 50 cycles of each other (column t2-min(t2)). Contrast this to synchronising via a Win32 event where eons can pass between the different threads being released.

I'd be most grateful for reviews of the three TSC functions (superfluous instructions, missing instructions, non-optimal instruction order) and insights regarding the methodology - especially potential weak points.

Please bear in mind that the code is intended to be run on the developer's machine and selected test systems, which means that things like automatic selection of appropriate code paths for different CPU architectures and so on are basically irrelevant. Also, the code is not intended to replace functions like QueryPerformanceCounter(), which still serves the bulk of my timing needs. It is intended for cases where the TSC is most appropriate.

\$\endgroup\$
1
\$\begingroup\$

Thank you for the tutorial on timing jitter, and for the valuable references. Do I have any critiques? No, it is clear to me that you are more knowledgeable and experienced than I am in this particular domain. I will share a few ideas generated by your discussion.

Between t0 & t1 there may have been diverse CPU and cache activities happening: retiring instructions or flushing dirty cache lines to RAM. Between t1 & t2 all cores were fairly boring, issuing lots of reads for a single location. They're in a known state. I wonder if tacking on yet another, t3, phase could achieve even less dispersion than your observed ~70 cycles? So spin on g_sleeping, then spin on g_sleeping2.

Could dispersion be reduced by spinning at lower duty cycle, say by putting XORs or NOPs in that tight loop? My goal would be to reduce contention for off-core communication channels.

Are there interrupts or other ACPI events that cores could synchronize on? Or do we maybe want to make one designated core produce N annoying barrier events that will, with high probability, lock out other cores until N is exhausted, and then they all get to jump on the bus? Is there any virtue to using expensive instructions like CAS, in the hopes of high latency but low jitter?

Rather than waiting for a memory location to decrement to zero, would dispersion be less if TSC was the global signal viewed by all cores? So all cores wait for the k low-order bits to (roughly) be zero, that is, for low-order bits to be less than a small constant m.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the heads-up and the ideas for new avenues of research, especially the one with using the TSC itself for synchronisation. Kudos! \$\endgroup\$ – DarthGizka Sep 10 '17 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.