Posted on 2010-07-13 23:03
李熙建 阅读(1011)
评论(0) 编辑 收藏 引用 所属分类:
算法
申明：Blog上的文章只是个人学习的一些记录和总结，这些记录部分来自于网络，加上自己的一些理解，有些已经找不到最原始的出处了，在此对大牛们的贡献表示感谢，如有侵权的地方，请通知我，我会尽快删除。
对关注性能的程序开发人员而言，一个好的计时部件既是益友，也是良师。计时器既可以作为程序组件帮助程序员精确的控制程序进程，又是一件有力的调试武器，在有经验的程序员手里可以尽快的确定程序的性能瓶颈，或者对不同的算法作出有说服力的性能比较。GPU程序性能瓶颈测试，比较常用的工具是NVIDIA PerfHUD ，它能准确测量出渲染管线的每个阶段消耗的时间，从时间轴上可以很明显的看出在渲染一帧是，渲染瓶颈在哪个阶段，从而根据具体情况进行优化。CPU程序性能分析工具，Intel公司的 VTune在业界比较常用，一直想用，还没试过。
然而下面将要介绍的，从网上搜集到的一些关于程序代码段时间统计函数，用于单个算法的性能分析，比上面提及的工具，更加方便，轻量，易用，根据你对时间统计的精度要求，选择不同的时间统计函数。
1.C语言时间库<time.h>的clock()函数
unsigned long sTime,eTime;
double dTime;
sTime = click();
/**////TODOeTime = click();
dTime = (double)(eTime-sTime)/CLOCKS_PER_SEC;
2. RDTSC :(Read Time Stamp Counter)
[1]在Intel Pentium以上级别的CPU中，有一个称为“时间戳（Time Stamp）”的部件，它以64位无符号整型数的格式，记录了自CPU上电以来所经过的时钟周期数。由于目前的CPU主频都非常高(1GHz = 10
9)，因此这个部件可以达到纳秒级(
一秒的10亿分之一，即等于10的负9次方秒)的计时精度。这个精确性是上述方法所无法比拟的。在Pentium以上的CPU中，提供了一条机器指令RDTSC（Read Time Stamp Counter）来读取这个时间戳的数字，并将其保存在EDX:EAX寄存器对中。由于EDX:EAX寄存器对恰好是Win32平台下C++语言保存函数返回值的寄存器，所以我们可以把这条指令，嵌入汇编代码的方式，看成是一个普通的函数调用。像这样：
inline unsigned __int64 GetCycleCount()
{
__asm RDTSC
}
但是不行，因为RDTSC不被C++的内嵌汇编器直接支持，所以我们要用_emit伪指令直接嵌入该指令的机器码形式0X0F、0X31，如下：
inline unsigned __int64 GetCycleCount()
{
__asm _emit 0x0F
__asm _emit 0x31
}
以后在需要计数器的场合，可以调用两次GetCycleCount函数，比较两个返回值的差，像这样：
#include <iostream>
#include <Windows.h>
using namespace std;
inline unsigned __int64 GetCycleCount()
{
__asm _emit 0x0F
__asm _emit 0x31
}
int main()
{
unsigned long t;
t = (unsigned long)GetCycleCount();
Sleep(1000);
t = (unsigned long)GetCycleCount() - t;
cout<<"时间："<<t<<endl;
system("pause");
return 0;
}
我的CPU是2.0GHz
所以输出结果：
时间：1995027270
程序所花时间秒数 = RDTSC读出的周期数T1-RDTSC读出周期数T2 / CPU主频速率（Hz）
缺点：
1.数据抖动比较厉害，每次测得结果都不一样，波动幅度上百甚至上千
2.在多核下不准确或不可用，有以下几个方面的原因
[2]：
a.两个CPU核的内部计数器不同步。如果程序两次读取这个计数器的时候恰好被轮换到不同的核上，那么用来计时就会有比较大的误差。
b.CPU 的时钟频率可能变化，例如笔记本电脑的节能功能；
c.乱序执行导致 RDTSC 测得的周期数不准，这个问题从 Pentium Pro 时代就存在。
解决方法
[3]：可以采用设定线程亲核性的方法。函数SetThreadAffinityMask可以指定某线程只在某些核上运行（由第二个参数设定，每个位代表一个核）。例如，在需要调用RDTSC的那个线程里执行SetThreadAffinityMask(GetCurrentThread(), 0x00000001);就能保证该线程只在第一个核上运行，不会因为两个核的RDTSC计数器不同步而造成计时误差。我在windows7和VS2005下测试，测出的数据和我CPU主频不符，我一度怀疑刚买的笔记本是不是被刷屏了，后来还找了其他的一些测CPU的工具，比如CPU-Z，这个问题还没解决。
3.使用QueryPerformanceCounter查询函数方法
这个方法在多核下照常有效，QueryPerformanceFrequency()参数只和主板上的高精度定时器的晶振频率相关
在面的例子是两种求平方根的算法的性能比较，一种采用库函数的sqrt(),另一种方法是《编程珠玑》上介绍的牛顿迭代法求平方根，原理类似于二分查找，但是牛顿迭代法收敛速度相比快很多。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
//a待输入的开平方根数
//x 选取的x0点
//y 每次迭代的中间值
double a, x,y;
unsigned long start,endt;
cin>>a;
LARGE_INTEGER t1,t2,tc;
QueryPerformanceFrequency(&tc);
printf("Frequency:%u\n",tc.QuadPart);
QueryPerformanceCounter(&t1);
if (a<0)
cout<<"负数没有平方根！"<<endl;
else
{
x = 1;
y = (x+a/x)/2;
while (x!=y)
{
x = y;
y = (x+a/x)/2;
}
}
QueryPerformanceCounter(&t2);
//牛顿迭代法求平方根所需时间;
printf("Lasting Time:%u\n",(t2.QuadPart-t1.QuadPart));
//duration = (double)(finish - start)/CLOCKS_PER_SEC ;
cout <<a<<"的平方根为："<<x<<endl;
QueryPerformanceCounter(&t1);
sqrt(a);
QueryPerformanceCounter(&t2);
//math.h库函数sqrt求平方根所需时间;
printf("Lasting Time:%u\n",(t2.QuadPart-t1.QuadPart));
cout<<a<<"的平方根为："<<sqrt(a)<<endl;
system("pause");
return 0;
两种求平方根所需时间对比如下：
在图形学中求平方根使用频率非常高，尤其是在碰触检测中，尽量提高求平方根的效率是非常有必要的。
总结：效率就是生命，在平时的项目开发中尽量做到简单，简单代表高效。这是检测高效的第一步。
引用：
[1]:http://zhidao.baidu.com/question/41853032.html
[2]:http://blog.csdn.net/Solstice/archive/2010/01/16/5196544.aspx
[3]:http://blog.21ic.com/user1/5184/archives/2009/65439.html