两段代码执行时间差异奇怪

7

我想了解一下程序在将变量的值复制到另一个变量之前进行比较会有多大性能提升(这个将在例子中更好地解释),但我发现了一些奇怪的问题。我有以下两段代码:

string a = "";
for (int i = 0; i < 1000000; i++) a += 'a';

for (int i = 0; i < 1000000; i++) {
    if ('b' == a.at(i));//compare the two chars directly
}

并且

string a = "";
for (int i = 0; i < 100000000; i++) a += 'a';

for (int i = 0; i < 100000000; i++) {
    char c = a.at(i);//declare a new variable
    if ('b' == c);//compare the char with the newly created variable,
                  //instead of comparing it to the other char directly
}

我原以为第二段会比第一段执行时间长,因为多声明了一个变量。但实际测试后发现,第二段所需的时间比第一段还要更短。我进行了几次测试,结果表明第二段总是需要少约0.13秒的时间才能完成执行。以下是完整代码:

#include <string>
#include <iostream>
#include <ctime>

using namespace std;

int main() {
    clock_t timer;

    string a = "";
    string b;

    for (int i = 0; i < 100000000; i++)
        a += "a";

    timer = clock();

    for (int i = 0; i < 100000000; i++) {
        if ('b'==a.at(i)) b += "a";
    }

    cout << (clock()-timer)/(float)CLOCKS_PER_SEC << "sec" << endl;

    timer = clock();

    for (int i = 0; i < 100000000; i++) {
        char c = a.at(i);
        if ('b'==c) b += "a";
    }

    cout << (clock()-timer)/(float)CLOCKS_PER_SEC << "sec" << endl;

    return 0;
}

为什么会发生这种情况?
编辑:我遵循NathanOliver的建议,为每个循环添加了单独的字符串,所以现在代码看起来像这样:
#include <string>
#include <iostream>
#include <ctime>

using namespace std;

int main() {
    clock_t timer;

    string compare_string_1 = "";
    string compare_string_2 = "";
    string segment_1 = "";
    string segment_2 = "";

    for (int i = 0; i < 100000000; i++)
        compare_string_1 += "a";

    for (int i = 0; i < 100000000; i++)
        compare_string_2 += "a";

    timer = clock();

    for (int i = 0; i < 100000000; i++) {
        if ('b'==compare_string_1.at(i)) segment_1 += "a";
    }

    cout << (clock()-timer)/(float)CLOCKS_PER_SEC << "sec" << endl;

    timer = clock();

    for (int i = 0; i < 100000000; i++) {
        char c = compare_string_2.at(i);
        if ('b'==c) segment_2 += "a";
    }

    cout << (clock()-timer)/(float)CLOCKS_PER_SEC << "sec" << endl;

    return 0;
}

4
为了消除底层硬件结构所使用的缓存启发式算法可能造成的影响,请颠倒执行这两种方法的顺序。接着,运行测试并检查结果是否与之前相同。顺便说一句,一个好的编译器会为两种情况生成完全相同的操作码,因此我建议你首先检查反汇编代码。如果它们确实是相同的,那么这就是执行顺序所导致的缓存问题。 - barak manos
1
创建一个char变量实际上不需要任何时间。对于这两个循环,生成的代码很可能是相同的(将a.at(i)放入寄存器中,将寄存器与'b'进行比较)。(虽然这不是您实际的代码 - b从未声明。复制和粘贴似乎已经失传了。) - molbdnilo
1
我建议您查看生成的汇编代码以找出差异。顺便问一下,您是在发布模式下进行测量的吗? - HiFile.app - best file manager
1
正如Barak Manos建议的那样,我也尝试交换执行这两个段的顺序。新的第一个段(旧的第二个段,带有额外的变量)执行所需时间减少了1.33秒。 - zomnombom
我已经使用启用优化的GCC6.1编译了这两个片段,并获得了相同的代码:https://godbolt.org/g/wwq4Nf - Revolver_Ocelot
显示剩余10条评论
1个回答

2
使用Visual C++ 2010,我得到了与上面评论中相同的时间结果-平均第二个循环需要大约80%的第一个循环运行时间。有一两次,第一个循环会稍微快一些,但这可能是由于操作系统中的某些线程问题。检查反汇编产生了以下结果:
第一个循环:
01231120  cmp         dword ptr [ebp-38h],esi  
01231123  jbe         main+1CBh (123120Bh)  
01231129  cmp         dword ptr [ebp-34h],10h  
0123112D  mov         eax,dword ptr [ebp-48h]  
01231130  jae         main+0F5h (1231135h)  
01231132  lea         eax,[ebp-48h]  
01231135  cmp         byte ptr [eax+esi],62h  
01231139  jne         main+108h (1231148h)  
0123113B  mov         ebx,1  
01231140  lea         eax,[ebp-80h]  
01231143  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::append (1231250h)  
01231148  inc         esi  
01231149  cmp         esi,5F5E100h  
0123114F  jl          main+0E0h (1231120h)

第二个循环:

01231155  cmp         dword ptr [ebp-1Ch],esi  
01231158  jbe         main+1CBh (123120Bh)  
0123115E  cmp         dword ptr [ebp-18h],10h  
01231162  mov         eax,dword ptr [ebp-2Ch]  
01231165  jae         main+12Ah (123116Ah)  
01231167  lea         eax,[ebp-2Ch]  
0123116A  cmp         byte ptr [eax+esi],62h  
0123116E  jne         main+13Dh (123117Dh)  
01231170  mov         ebx,1  
01231175  lea         eax,[ebp-64h]  
01231178  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::append (1231250h)  
0123117D  inc         esi  
0123117E  cmp         esi,5F5E100h  
01231184  jl          main+115h (1231155h) 

由于生成的汇编代码看起来基本相同,我考虑了操作系统或CPU中的限流机制,猜猜会发生什么? 在两个循环之间添加 Sleep(5000); 导致第二个循环几乎总是比第一个慢。运行20次后,第二个循环平均需要第一个循环的运行时间的150%左右。
编辑: 将自旋计数增加五倍会得到相同的结果。我认为大约可以可靠地测量0.5秒左右的运行时间。:-)
在原始代码中,我认为操作系统可能需要几个时间片来检测 CPU 负载,然后开始在调度期间给线程更高的优先级,而 CPU 可能会在一段时间后进行提升,留下第一个循环的部分未被提升。当第二个循环开始执行时,操作系统/CPU 可能已经为重负荷工作做好了准备,并且执行速度会稍微快一些。MMU 或操作系统内部内存页面处理也可能发生相同的情况。 在循环之间添加 Sleep 时,相反的情况可能会发生,导致操作系统将线程放置一段时间,直到最终检测到新的工作负载,使第二个循环执行稍微慢一些。
你的结果是什么?有人手头有像英特尔的放大器一样的适当分析工具,可以测量循环中的 CPI 率和 CPU 速度步进吗?

1
在我看来,这是一个很好的建议。代码执行时间很短却很难计时并不罕见。CPU 时间分配高度影响计时,然而,正是由于 Sleep 可能导致第二种情况需要更长时间,因此我的建议是将循环次数增加100倍左右。 - philkark

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接