c++ - 为什么while循环的执行时间显得如此奇怪？

Question

我使用rdstc()函数从其内部和外部分别测试while循环的执行时间，这两个结果有很大差异。当我从外部进行测试时，结果约为445亿个周期。当我从内部进行测试时，结果大约是330亿个周期。

代码段如下所示:

while(true){
    beginTime = rdtsc();
    typename TypedGlobalTable<K, V, V, D>::Iterator *it2 = a->get_typed_iterator(current_shard(), false);
    getIteratorTime += rdtsc()-beginTime;
    if(it2 == NULL) break;

    uint64_t tmp = rdtsc();
    while(true) {
        beginTime = rdtsc();
        if(it2->done()) break;      
        bool cont = it2->Next();        //if we have more in the state table, we continue
        if(!cont) break;
        totalF2+=it2->value2();         //for experiment, recording the sum of v
        updates++;                      //for experiment, recording the number of updates
        otherTime += rdtsc()-beginTime;
        //cout << "processing " << it2->key() << " " << it2->value1() << " " << it2->value2() << endl;
        beginTime = rdtsc();
        run_iter(it2->key(), it2->value1(), it2->value2(), it2->value3());
        iterateTime += rdtsc()-beginTime;
    }
    flagtime += rdtsc()-tmp;
    delete it2;                         //delete the table iterator}

我测试的while循环是内部循环。

rdstc()函数如下所示:

static uint64_t rdtsc() {

  uint32_t hi, lo;

  __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));

  return (((uint64_t)hi)<<32) | ((uint64_t)lo);

}

我在虚拟机中的Ubuntu 10.04LTS下构建并运行该程序，内核版本为“Linux ubuntu 2.6.32-38-generiC#83-Ubuntu SMP Wed Jan 4 11:13:04 UTC 2012 i686 GNU / Linux”。

Answer 1

RDTSC指令不是"serializing"，请参阅此SO问题

Why isn't RDTSC a serializing instruction?

一些背景

现代X86内核具有“无序”(OoO)执行，这意味着一旦操作数准备好并且执行单元可用，指令便被分派(dispatch)到能够执行指令的execution unit中……指令不一定要执行按程序顺序。指令确实按程序顺序退出，因此您可以获取寄存器和内存的准确内容，这些内容是体系结构的有序执行在发生中断，异常或错误时指定的。

这意味着CPU可以自由分配调度指令以执行任意顺序，只要它想获得按顺序执行的错觉，它就可以获取尽可能多的并发并提高性能。
RDTSC指令旨在以尽可能快的速度执行，以尽可能少的开销实现非侵入式的执行。它具有大约22个处理器周期的延迟，但是您可以同时完成很多工作。

有一个更新的变种，称为RDTSCP，它正在序列化...处理器等待程序指令中的先前指令完成，并阻止将来的指令被派发...从性能的 Angular 来看这是昂贵的。

回到您的问题

考虑到这一点，考虑一下编译器生成什么以及处理器看到什么... while(true)只是一个无条件分支，它实际上并没有执行，但是被管道的前端，指令解码器消耗了，它正在尽可能远地获取数据，将指令塞满指令分派(dispatch)器以尝试使每个周期执行尽可能多的指令。因此，将分派(dispatch)循环中的RDTSC指令，继续执行其他指令，最后RDTSC退出，并将结果转发到取决于结果的指令(代码中的减法)。但是您还没有真正计时好内部循环。

让我们看下面的代码:

beginTime = rdtsc();
run_iter(it2->key(), it2->value1(), it2->value2(), it2->value3());
iterateTime += rdtsc()-beginTime;

假设函数run_iter()在返回后调用rdtsc()时将完成。但是实际上可能会发生的是，run_iter中内存中的某些负载在高速缓存中丢失，并且处理器将负载保持在内存中，但是它可以继续执行独立的指令，从函数返回(或者该函数已由编译器内联)并且它在返回处看到RDTSC，因此它调度...嘿，它不依赖于高速缓存中丢失的负载，并且不进行序列化，因此这是公平的游戏。 RDTSC在22个周期内退出，这比去往DRAM的高速缓存未命中(数百个周期)要快得多……而突然之间，您却低估了执行run_iter()所花费的时间。

外环测量不受此影响，因此它为您提供了真正的整体周期时间。

建议的修复

这是一个简单的帮助程序struct / class，它使您可以考虑各种累加器中的时间而不会出现“时间泄漏”。每当调用“split”成员函数时，都必须给它一个累加器变量(通过引用)，该变量将累加先前的时间间隔:

struct Timer {
    uint64_t _previous_tsc;
    Timer() : _previous_tsc(rdtsc()) {}
    void split( uint64_t & accumulator )
    {
        uint64_t tmp = rdtsc();
        accumulator += tmp - _previous_tsc;
        _previous_tsc = tmp;
    }
};

现在，您可以使用一个实例来计时内部循环的“拆分”，而另一个可以对整个外部循环进行计时:

uint64_t flagtime    = 0; // outer loop

uint64_t otherTime   = 0; // inner split
uint64_t iterateTime = 0; // inner split
uint64_t loopTime    = 0; // inner split

Timer tsc_outer;
Timer tsc_inner;

while(! it2->done()) {

    tsc_inner.split( loopTime );

    bool cont = it2->Next();        //if we have more in the state table, we continue
    if(!cont) break;
    totalF2+=it2->value2();         //for experiment, recording the sum of v
    updates++;                      //for experiment, recording the number of updates

    tsc_inner.split( otherTime );

    run_iter(it2->key(), it2->value1(), it2->value2(), it2->value3());

    tsc_inner.split( iterateTime );
}
tsc_outer.split( flagtime );

现在这是“紧密的”，您将不会错过任何周期。需要注意的是，它仍然使用RDTSC而不是RDTSCP来进行序列化，这意味着您可能仍然低估了一次拆分所花费的时间(例如iterateTime)，而过度报告了其他一些累加器(例如loopTime)。 run_iter()中没有在iterateTime中解决的高速缓存未命中将在loopTime中解决。

注意:虚拟机的管理程序可能正在捕获RDTSC

需要注意的一件事是，在虚拟机中，系统管理程序可能会设置一个控制寄存器，以在用户级程序尝试执行RDTSC时强制CPU故障……这肯定会序列化执行，并且性能非常好瓶颈。在这些情况下，系统管理程序emulates会执行RDTSC，并为应用程序提供虚拟时间戳。参见问题Weird program latency behavior on VM。

最初，我认为这不是您正在观察的问题，现在我想知道是否是这样。如果实际上虚拟机正在捕获RDTSC，则您必须添加硬件开销，以保存VM寄存器，调度内核/管理程序以及在“修复” EDX:EAX以模拟RDTSC后恢复应用程序... 50在3 GHz上，十亿个周期是很长的时间，超过16秒。这可以解释为什么您会错过这么多时间... 110亿个周期...(44-33)。