c++ - 时间和基准

Question

如果我想比较两种算法的速度，最好的方法是什么？ 我熟悉数学方法，而且我知道我还没有完全掌握它 =/ 我有兴趣了解如何在 Windows 上以高精度对两种算法进行计时。 最好使用的 API 是什么，stdio.h 中的 time() 可靠还是我需要更好的东西？

举个例子也不错! 谢谢!

Answer 1

不幸的是，这不是一件容易的事。

如前所述，QueryPerformanceCounter 是一个可行的选择。
其他可能性是:
- GetTickCount(不可取，因为它的精度低于 30 毫秒)
- timeGetTime:默认情况下它的精度为 15 毫秒。这对应于任务调度程序分配的默认时间(在我的电脑上为 15 毫秒)。您可以强制 timeGetTime 更准确，方法是更改​​系统范围内的设置，该设置规定调度程序分配的时间:调用 timeBeginPeriod 可以做到这一点。但是，这只能用作临时系统破解!请不要在您的发布代码中使用它!
- 查询处理器的时间戳计数器:这需要汇编程序编程，我不推荐这样做。

就 QueryPerformanceCounter 而言，您可以在这里找到一个易于使用的包装器:http://www.codeproject.com/KB/datetime/perftimer.aspx

你可以这样使用它:

CPerfTimer t;
t.Start();     
CallExpensiveTask();
std::cout << "Time (ms) " << t.Elapsedms();

但是有一些建议:

• 如前所述，多次运行您的函数以获得可靠的测量
• 注意任务调度程序: 在普通计算机上，每个进程在切换到另一个进程之前有 15 毫秒的时间。如果任务调度程序在调用您测量的函数期间切换任务，您可能会测量到更长的时间(大约高 15 毫秒)
• 请注意，sleep(1) 会暂停 15 毫秒(因为调度程序将切换到不同的进程)
• 请记住，QueryPerformanceCounter 可以(很少)给出不准确的结果: 在多核处理器上，您有时可能会看到负延时 (!)。在这种情况下，您应该重新测量(参见 http://www.virtualdub.org/blog/pivot/entry.php?id=106 )
• 抵消调度器影响的临时解决方案: - 提高你的进程优先级(你可以通过任务管理器来完成) - 破解调度程序:微软提供的 timeBeginPeriod (http://msdn.microsoft.com/en-us/library/dd757624(v=VS.85).aspx) 可以更改分配给每个任务的时间15ms 到更低的值(记住不要包括这是你的发布代码，因为这是一个系统范围的设置，可以降低全局性能......)

关于处理器时间戳计数器的更多说明

• 我自己没有测试它的准确性，但是 http://en.wikipedia.org/wiki/Time_Stamp_Counter 是一个很好的信息来源，可以了解它及其局限性(尤其是在多核处理器上，以及具有可变时钟频率)
• AFAIK，建议在您为其设置处理器关联的单个线程上使用这种计时器
• 一个实现示例(可在 http://developer.nvidia.com/object/timer_function_performance.html 找到)可以是:

#pragma warning (disable : 4035)    // disable no return value warning

__forceinline  DWORD GetPentiumCounter()
{
__asm
{
    xor   eax,eax             // VC won't realize that eax is modified w/out this
                              //   instruction to modify the val.
                              //   Problem shows up in release mode builds
    _emit 0x0F                // Pentium high-freq counter to edx;eax
    _emit 0x31                // only care about low 32 bits in eax

    xor   edx,edx             // so VC gets that edx is modified
}
}

#pragma warning (pop)