2010年9月29日星期三

如何调整窗口以适应客户区大小

假设我们用CreateWindow(..., 0, 0, w, h, ...); 创建一个窗口, 我们将获得一个w x h大小的窗口, 通常我们需要的是客户区大小为w x h,

如何做呢?

一个方法是调用API函数SetWindowPos, 通常我们需要提供3个参数:窗口句柄hwnd,窗口宽度w,窗口高度h。下面是一个示例:
SetWindowPos(hwnd, NULL, 0, 0, w, h, SWP_NOMOVE | SWP_NOZORDER);

现在的问题是我们只知道客户区的大小w x h, 如何获取窗口大小呢?

这里的关键是
wWindow = wClient + wFrame * 2
hWindow = hClient + hCaption + hMenu + hFrame * 2
其中wFrame, hCaption, hMenu, hFrame取值则需要根据窗口样式而定了。
如果窗口提供了Caption, 则hCaption=GetSystemMetrics(SM_CYCAPTION); 否则为0
如果窗口提供了菜单, 则hMenu=GetSystemMetrics(SM_CYMENU); 否则为0
如果窗口提供了Border, 则wFrame=GetSystemMetrics(SM_CXFRAME),hFrame=GetSystemMetrics(SM_CYFRAME); 否则为0

综合起来,如果窗口具有标题栏,具有菜单,具有border,我们可以这样创建一个指定客户区w x h大小的窗口:
CreateWindow(..., 0, 0, w, h, ...);
w = w + GetSystemMetrics(SM_CXFRAME) * 2;
h = h + GetSystemMetrics(SM_CYCAPTION) + GetSystemMetrics(SM_CYMENU) + GetSystemMetrics(SM_CYFRAME) * 2;
SetWindowPos(hwnd, NULL, 0, 0, w, h, SWP_NOMOVE | SWP_NOZORDER);

MFC的方法则更加简单
在Create()或者CreateEx()创建窗口以后, 用下面的代码调整窗口的大小。
CRect rect(0, 0, w, h);
CalcWindowRect(&rect);
SetWindowPos(NULL, 0, 0, rect.Width(), rect.Height(), SWP_NOMOVE | SWP_NOZORDER | SWP_NOREDRAW);

2010年9月28日星期二

malloc函数

malloc函数

百科名片

本词条主要介绍 malloc 函数

Malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定,void* 类型可以强制转换为任何其它类型的指针。

目录

函数简介
函数声明
函数的工作机制
举例说明

函数简介

  原型:extern void *malloc(unsigned int num_bytes);
  头文件:在TC2.0中可以用malloc.h或 alloc.h (注意:alloc.h 与 malloc.h 的内容是完全一致的),而在Visual C++6.0中可以用malloc.h或者stdlib.h。
  功能:分配长度为num_bytes字节的内存块
  返回值:如果分配成功则返回指向被分配内存的指针,否则返回空指针NULL。当内存不再使用时,应使用free()函数将内存块释放。
  说明:关于该函数的原型,在旧的版本中malloc返回的是char型指针,新的ANSIC标准规定,该函数返回为void型指针,因此必要时要进行类型转换。
  相关函数:callocreallocfree、_alloca

函数声明

  void *malloc(int size);
  说明:malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void* 类型。void* 表示未确定类型的指针。C,C++规定,void* 类型可以强制转换为任何其它类型的指针。
  从函数声明上可以看出。malloc 和 new 至少有两个不同: new 返回指定类型的指针,并且可以自动计算所需要大小。比如:
  int *p;
  p = new int; //返回类型为int* 类型(整数型指针),分配大小为 sizeof(int);
  或:
  int* parr;
  parr = new int [100]; //返回类型为 int* 类型(整数型指针),分配大小为 sizeof(int) * 100;
  而 malloc 则必须由我们计算要字节数,并且在返回后强行转换为实际类型的指针。
  int* p;
  p = (int *) malloc (sizeof(int));
  第一、malloc 函数返回的是 void * 类型,如果你写成:p = malloc (sizeof(int)); 则程序无法通过编译,报错:“不能将 void* 赋值给 int * 类型变量”。所以必须通过 (int *) 来将强制转换。
  第二、函数的实参为 sizeof(int) ,用于指明一个整型数据需要的大小。如果你写成:
  int* p = (int *) malloc (1);
  代码也能通过编译,但事实上只分配了1个字节大小的内存空间,当你往里头存入一个整数,就会有3个字节无家可归,而直接“住进邻居家”!造成的结果是后面的内存中原有数据内容全部被清空。
  malloc 也可以达到 new [] 的效果,申请出一段连续的内存,方法无非是指定你所需要内存大小。
  比如想分配100个int类型的空间:
  int* p = (int *) malloc ( sizeof(int) * 100 ); //分配可以放得下100个整数的内存空间。
  另外有一点不能直接看出的区别是,malloc 只管分配内存,并不能对所得的内存进行初始化,所以得到的一片新内存中,其值将是随机的。
  除了分配及最后释放的方法不一样以外,通过malloc或new得到指针,在其它操作上保持一致。
  对其做一个特例补充
  char *ptr;
  if ((ptr = (char *)malloc(0)) == NULL)
  puts("Got a null pointer");
  else
  puts("Got a valid pointer");
  此时得到的是Got a valid pointer。把0赋给malloc能得到一个合法的指针。

函数的工作机制

  malloc函数的实质体现在,它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时,它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后,将该内存块一分为二(一块的大小与用户请求的大小相等,另一块的大小就是剩下的字节)。接下来,将分配给用户的那块内存传给用户,并将剩下的那块(如果有的话)返回到连接表上。调用free函数时,它将用户释放的内存块连接到空闲链上。到最后,空闲链会被切成很多的小内存片段,如果这时用户申请一个大的内存片段,那么空闲链上可能没有可以满足用户要求的片段了。于是,malloc函数请求延时,并开始在空闲链上翻箱倒柜地检查各内存片段,对它们进行整理,将相邻的小空闲块合并成较大的内存块。

举例说明

  举例1:(在Visual C++ 6.0中运行通过)
  #include
  #include
  int main()
  {
  int i,j;
  int *array=NULL;
  scanf("%d",&i);
  array=(int*)malloc(i*sizeof(int));
  for(j=0;j
  scanf("%d",&array[j]);
  for(j=0;j
  printf("%d\n",array[j]);
  free(array);
  array=NULL;
  return 0;
  }
  举例2:(在TC2.0中运行通过) 
  /*malloc.c*/
  #include
  #include
  main()
  {
  char *p;
  clrscr(); /*clear screen*/
  p=malloc(100);
  if(p)
  printf("Memory Allocated at: %x",p);
  else
  printf("Not Enough Memory!\n");
  free(p);
  getchar();
  return 0;
  }

CPU 读取内存数据过程,地址总线,数据总线,控制总线

CPU在运作时,读取内存数据,首先要指定存储单元的地址。就是要确实读取哪段数据,就想大街上找人,首先要确定他在哪栋房子里。

(注意:另外,CPU读写数据时还有指明,它要对哪个器件进行操作,何种操作,是从中读取数据,还是向里写入数据。)

CPU要进行数据的读写,必须和外部器件(标准的说法是芯片)进行信息下3类交互

存储单元的地址(地址信息)

器件的选择,读or写 (控制信息)

读写的数据 (数据信息)



CPU 是以电信号的方式,以导线传输到存储器的芯片中

CPU连接芯片的导线,成为总线

根据传输的信息不同,总线分为三类,地址总线,控制总线,数据总线。如图

CPU 读取内存数据过程,地址总线,数据总线,控制总线 - 【墨Ю】 - 墨




读取流程:

1,CPU通过地址线将地址信息3发出

2,CPU通过控制线发出内存读命令,选中存储器芯片,并通知它,将要从中读取数据。

3,存储器将3号单元中的数据 8 通过数据线送入 CPU



写入流程:(将26写入单元3)

1,CPU通过地址线将地址信息3发出。

2,CPU通过地址线发出内存写命令,选中存储器芯片,并通知它,要其写入数据

3,CPU通过数据线将数据26送入内存3单元中



地址总线

其中CUP通过地址总线要寻址,指定存储单元。

可见地址总线上能传送多少个不同的信息,CPU就可以对多少个存储单元进行寻址。

有10根地址总线,就能传送10位二进制数据,也就是2的10次方 。最小位0,最大为1023。

也就是 2(n) = 最大传输 n = 多少地址总线

CPU地址总线的宽带决定了CPU的寻址能力



数据总线

CPU与内存或其他器件直接爱你数据传达是通过数据总线来进行的。

数据总线的宽度决定了CPU和外界的数据传输速度。

8根数据总线一次可以传送8位二进制数据。

16根数据总线一次可以穿2个字节。



控制总线

CPU对外部部件的控制时通过控制总线来进行的。 控制总线是个总称,控制总线是有不同的控制线来集合的。

有多少根控制总线,就意味着 CPU 提供了对外部器件的多少种控制。

so 数据总线的宽带决定了CPU对外部部件的控制能力。



内存读或写时,是有几根控制线综合发出的,其中一根称为“读信号输出”的控制线负责由CPU向外传送读信号。

有一根称为“读信号输出”的控制线负责传送写信号。

内存分配详解、指针与数组[C++][内存管理]

程序员们经常编写内存管理程序,往往提心吊胆。如果不想触雷,唯一的解决办法就是发现所有潜伏的地雷并且排除它们,躲是躲不了的。本文的内容比一般教科书的要深入得多,读者需细心阅读,做到真正地通晓内存管理。

内存分配方式

(1)从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static变量。
(2)在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。
(3) 从堆上分配,亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存,程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定,使用非常灵活,但问题也最多。

常见的内存错误及其对策

发生内存错误是件非常麻烦的事情。编译器不能自动发现这些错误,通常是在程序运行时才能捕捉到。而这些错误大多没有明显的症状,时隐时现,增加了改错的难度。有时用户怒气冲冲地把你找来,程序却没有发生任何问题,你一走,错误又发作了。 常见的内存错误及其对策如下:

* 内存分配未成功,却使用了它

编程新手常犯这种错误,因为他们没有意识到内存分配会不成功。常用解决办法是,在使用内存之前检查指针是否为NULL。如果指针p是函数的参数,那么在函数的入口处用assert(p!=NULL)进行检查。如果是用malloc或new来申请内存,应该用if(p==NULL) 或if(p!=NULL)进行防错处理。

* 内存分配虽然成功,但是尚未初始化就引用它

犯这种错误主要有两个起因:一是没有初始化的观念;二是误以为内存的缺省初值全为零,导致引用初值错误(例如数组)。内存的缺省初值究竟是什么并没有统一的标准,尽管有些时候为零值,我们宁可信其无不可信其有。所以无论用何种方式创建数组,都别忘了赋初值,即便是赋零值也不可省略,不要嫌麻烦。

* 内存分配成功并且已经初始化,但操作越过了内存的边界

例如在使用数组时经常发生下标“多1”或者“少1”的操作。特别是在for循环语句中,循环次数很容易搞错,导致数组操作越界。

* 忘记了释放内存,造成内存泄露

含有这种错误的函数每被调用一次就丢失一块内存。刚开始时系统的内存充足,你看不到错误。终有一次程序突然死掉,系统出现提示:内存耗尽。

动态内存的申请与释放必须配对,程序中malloc与free的使用次数一定要相同,否则肯定有错误(new/delete同理)。

* 释放了内存却继续使用它

有三种情况:

(1)程序中的对象调用关系过于复杂,实在难以搞清楚某个对象究竟是否已经释放了内存,此时应该重新设计数据结构,从根本上解决对象管理的混乱局面。

(2)函数的return语句写错了,注意不要返回指向“栈内存”的“指针”或者“引用”,因为该内存在函数体结束时被自动销毁。

(3)使用free或delete释放了内存后,没有将指针设置为NULL。导致产生“野指针”。

【规则1】用malloc或new申请内存之后,应该立即检查指针值是否为NULL。防止使用指针值为NULL的内存。

【规则2】不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右值使用。

【规则3】避免数组或指针的下标越界,特别要当心发生“多1”或者“少1”操作。

【规则4】动态内存的申请与释放必须配对,防止内存泄漏。

【规则5】用free或delete释放了内存之后,立即将指针设置为NULL,防止产生“野指针”。

指针与数组的对比

C++/C程序中,指针和数组在不少地方可以相互替换着用,让人产生一种错觉,以为两者是等价的。

数组要么在静态存储区被创建(如全局数组),要么在栈上被创建。数组名对应着(而不是指向)一块内存,其地址与容量在生命期内保持不变,只有数组的内容可以改变。

指针可以随时指向任意类型的内存块,它的特征是“可变”,所以我们常用指针来操作动态内存。指针远比数组灵活,但也更危险。

下面以字符串为例比较指针与数组的特性

1 修改内容

下例中,字符数组a的容量是6个字符,其内容为hello。a的内容可以改变,如a[0]= 'x'。指针p指向常量字符串"world"(位于静态存储区,内容为world),常量字符串的内容是不可以被修改的。从语法上看,编译器并不觉得语句 p[0]= 'x'有什么不妥,但是该语句企图修改常量字符串的内容而导致运行错误。

#include<iostream.h>

void main()

{

char a[] = "hello";

a[0] = 'x';
cout
<< a << endl;
char *p = "world"; // 注意p指向常量字符串
p[0] = 'x'; // 编译器不能发现该错误
cout << p << endl;
}

2 内容复制与比较

不能对数组名进行直接复制与比较。下例中,若想把数组a的内容复制给数组b,不能用语句 b = a ,否则将产生编译错误。应该用标准库函数strcpy进行复制。同理,比较b和a的内容是否相同,不能用if(b==a) 来判断,应该用标准库函数strcmp进行比较。

语句p = a 并不能把a的内容复制指针p,而是把a的地址赋给了p。要想复制a的内容,可以先用库函数malloc为p申请一块容量为strlen(a)+1个字符的内存,再用strcpy进行字符串复制。同理,语句if(p==a) 比较的不是内容而是地址,应该用库函数strcmp来比较。

// 数组…

char a[] = "hello";

char b[10];

strcpy(b, a); // 不能用 b = a;

if(strcmp(b, a) == 0) // 不能用 if (b == a)

// 指针…

int len = strlen(a);

char *p = (char *)malloc(sizeof(char)*(len+1));

strcpy(p,a); // 不要用 p = a;

if(strcmp(p, a) == 0) // 不要用 if (p == a)

3 计算内存容量

用运算符sizeof可以计算出数组的容量(字节数)。下例(a)中,sizeof(a)的值是12(注意别忘了' ')。指针p指向a,但是 sizeof(p)的值却是4。这是因为sizeof(p)得到的是一个指针变量的字节数,相当于sizeof(char*),而不是p所指的内存容量。 C++/C语言没有办法知道指针所指的内存容量,除非在申请内存时记住它。注意当数组作为函数的参数进行传递时,该数组自动退化为同类型的指针。下例(b)中,不论数组a的容量是多少,sizeof(a)始终等于sizeof(char *)。

示例(a)


char a[] = "hello world";
char *p = a;
cout<< sizeof(a) << endl; // 12字节
cout<< sizeof(p) << endl; // 4字节


示例(b)

void Func(char a[100])
{
cout<< sizeof(a) << endl; // 4字节而不是100字节
}

函数数组指针

笔者在开发某软件过程中遇到这样一个问题,前级模块传给我二进制数据,输入参数为 char* buffer和 int length,buffer是数据的首地址,length表示这批数据的长度。数据的特点是:长度不定,类型不定,由第一个字节(buffer[0])标识该数据的类型,共有256(28 )种可能性。我的任务是必须对每一种可能出现的数据类型都要作处理,并且我的模块包含若干个函数,在每个函数里面都要作类似的处理。若按通常做法,会写出如下代码:

void MyFuntion( char* buffer, int length )
{
    __int8 nStreamType = buffer[0];

    switch( nStreamType )
    {
       case 0:
           function1();
           break;
       case 1:
       ......
       case 255:
           function255();
           break;
     }
}

如果按照这种方法写下去,那么在我的每一个函数里面,都必须作如此多的判断,写出的代码肯定很长,并且每一次处理,都要作许多次判断之后才找到正确的处理函数,代码的执行效率也不高。针对上述问题,我想到了用函数指针数组的方法解决这个问题。

  函数指针的概念,在潭浩强先生的C语言程序设计这本经典的教程中提及过,在大多数情况下我们使用不到,也忽略了它的存在。函数名实际上也是一种指针,指向函数的入口地址,但它又不同于普通的如int*、double*指针,看下面的例子来理解函数指针的概念:
int funtion( int x, int y );
void main ( void )
{
   int (*fun) ( int x, int y );
   int a = 10, b = 20;
   function( a, b );
   fun = function;
   (*fun)( a, b );
    ……
}
  语句1定义了一个函数function,其输入为两个整型数,返回也为一个整型数(输入参数和返回值可为其它任何数据类型);语句3定义了一个函数指针,与int*或double*定义指针不同的是,函数指针的定义必须同时指出输入参数,表明这是一个函数指针,并且*fun也必须用一对括号括起来;语句6将函数指针赋值为funtion,前提条件是*fun和function的输入参数和返回值必须保持一致。语句5直接调用函数function(),语句7是调用函数指针,二者等效。

  当然从上述例子看不出函数指针的优点,目的主要是想引出函数指针数组的概念。我们从上面例子可以得知,既然函数名可以通过函数指针加以保存,那们也一定能定义一个数组保存若干个函数名,这就是函数指针数组。正确使用函数指针数组的前提条件是,这若干个需要通过函数指针数组保存的函数必须有相同的输入、输出值。

这样,我工作中所面临的问题可以解决如下:

首先定义256个处理函数(及其实现)。

void funtion0( void );
……..
void funtion255(void );

其次定义函数指针数组,并给数组赋值。
void (*fun[256])(void);

fun[0] = function0;
…….
fun[255] = function();
最后,MyFunction()函数可以修改如下:

void MyFuntion( char* buffer, int length )
{
    __int8 nStreamType = buffer[0];
    (*fun[nStreamType])();
}

  只要2行代码,就完成了256条case语句要做的事,减少了编写代码时工作量,将nStreamType作为数组下标,直接调用函数指针,从代码执行效率上来说,也比case语句高。假如多个函数中均要作如此处理,函数指针数组更能体现出它的优势。

2010年9月21日星期二

高精度计时

声明:本文章是我整合网上的资料而成的,其中的大部分文字不是我所为的,我所起的作用只是归纳整理并添加我的一些看法。非常感谢引用到的文字的作者的辛勤劳动,所参考的文献在文章最后我已一一列出。

对关注性能的程序开发人员而言,一个好的计时部件既是益友,也是良师。计时器既可以作为程序组件帮助程序员精确的控制程序进程,又是一件有力的调试武器,在有经验的程序员手里可以尽快的确定程序的性能瓶颈,或者对不同的算法作出有说服力的性能比较。

在Windows平台下,常用的计时器有两种,一种是timeGetTime多媒体计时器,它可以提供毫秒级的计时。但这个精度对很多应用场合而言还是太 粗糙了。另一种是QueryPerformanceCount计数器,随系统的不同可以提供微秒级的计数。对于实时图形处理、多媒体数据流处理、或者实时 系统构造的程序员,善用QueryPerformanceCount/QueryPerformanceFrequency是一项基本功。

本文要介绍的,是另一种直接利用Pentium CPU内部时间戳进行计时的高精度计时手段。以下讨论主要得益于《Windows图形编程》一书,第 15页-17页,有兴趣的读者可以直接参考该书。关于RDTSC指令的详细讨论,可以参考Intel产品手册。本文仅仅作抛砖之用。
在 Intel Pentium以上级别的CPU中,有一个称为“时间戳(Time Stamp)”的部件,它以64位无符号整型数的格式,记录了自CPU上电以来所经过的时钟周期数。由于目前的CPU主频都非常高,因此这个部件可以达到 纳秒级的计时精度。这个精确性是上述两种方法所无法比拟的。

在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
}

以后在需要计数器的场合,可以像使用普通的Win32 API一样,调用两次GetCycleCount函数,比较两个返回值的差,像这样:

unsigned long t;
t = (unsigned long)GetCycleCount();
//Do Something time-intensive ...
t -= (unsigned long)GetCycleCount();

《Windows图形编程》第15页编写了一个类,把这个计数器封装起来。有兴趣的读者可以去参考那个类的代码。作者为了更精确的定时,做了一点小小的改 进,把执行RDTSC指令的时间,通过连续两次调用GetCycleCount函数计算出来并保存了起来,以后每次计时结束后,都从实际得到的计数中减掉 这一小段时间,以得到更准确的计时数字。但我个人觉得这一点点改进意义不大。在我的机器上实测,这条指令大概花掉了几十到100多个周期,在 Celeron 800MHz的机器上,这不过是十分之一微秒的时间。对大多数应用来说,这点时间完全可以忽略不计;而对那些确实要精确到纳秒数量级的应用来说,这个补偿 也过于粗糙了。

我从《Windows图形编程》上把这个类的源码拷贝了下来供大家看看,下面是使用RDTSC指令的CPU时钟循环秒表类:

C/C++ code

// Timer.h
#pragma once

inline unsigned __int64 GetCycleCount(
void)
{
_asm _emit
0x0F
_asm _emit
0x31
}

class KTimer
{
unsigned __int64 m_startcycle;

public:

unsigned __int64 m_overhead;

KTimer(
void)
{
m_overhead
= 0;

Start();
m_overhead
= Stop();
}

void Start(void)
{
m_startcycle
= GetCycleCount();
}

unsigned __int64 Stop(
void)
{
return GetCycleCount()-m_startcycle-m_overhead;
}
};



这个方法的优点是:

1.高精度。可以直接达到纳秒级的计时精度(在1GHz的CPU上每个时钟周期就是一纳秒),这是其他计时方法所难以企及的。

2. 成本低。timeGetTime 函数需要链接多媒体库winmm.lib,QueryPerformance* 函数根据MSDN的说明,需要硬件的支持(虽然我还没有见过不支持的机器)和KERNEL库的支持,所以二者都只能在Windows平台下使用(关于 DOS平台下的高精度计时问题,可以参考《图形程序开发人员指南》,里面有关于控制定时器8253的详细说明)。但RDTSC指令是一条CPU指令,凡是 i386平台下Pentium以上的机器均支持,甚至没有平台的限制(我相信i386版本UNIX和Linux下这个方法同样适用,但没有条件试验),而 且函数调用的开销是最小的。
(这里我想说的是:照这样看,跨平台也只能说是操作系统平台,不能跨硬件平台,就是说只能用在Intel Pentium以上的机器)


3. 具有和CPU主频直接对应的速率关系。一个计数相当于1/(CPU主频Hz数)秒,这样只要知道了CPU的主频,可以直接计算出时间。这和 QueryPerformanceCount不同,后者需要通过QueryPerformanceFrequency获取当前计数器每秒的计数次数才能换 算成时间。

这个方法的缺点是:

1.现有的C/C++编译器多数不直接支持使用RDTSC指令,需要用直接嵌入机器码的方式编程,比较麻烦。

2.数据抖动比较厉害。其实对任何计量手段而言,精度和稳定性永远是一对矛盾。如果用低精度的timeGetTime来计时,基本上每次计时的结果都是相同的;而RDTSC指令每次结果都不一样,经常有几百甚至上千的差距。这是这种方法高精度本身固有的矛盾。

(这里数据抖动确实是一个大问题,我遇到过这样一种情况,比如测试a和b两种算法,由于数据抖动,有时a比b耗时少,有时b比a耗时少。我想过两种测试办法:
(1)增多测试次数,比如对a和b两种算法各测试10次,看a比b耗时少的次数和b比a耗时少的次数哪个多,以此判定哪个算法效率高。
(2)增大测试数据量,我想一增大测试数据量,算法效率的差异就会显现出来)

关于这个方法计时的最大长度,我们可以简单的用下列公式计算:

自CPU上电以来的秒数 = RDTSC读出的周期数 / CPU主频速率(Hz)

64位无符号整数所能表达的最大数字是1.8×10^19,在我的Celeron 800上可以计时大约700年(书中说可以在200MHz的Pentium上计时117年,这个数字不知道是怎么得出来的,与我的计算有出入)。无论如 何,我们大可不必关心溢出的问题。

下面是几个小例子,简要比较了三种计时方法的用法与精度

C/C++ code

#include
<stdio.h>
#include
"KTimer.h"
main()
{
unsigned t;
KTimer timer;
timer.Start();
Sleep(
1000);
t
= timer.Stop();
printf(
"Lasting Time: %d\n",t);
}

//Timer2.cpp 使用了timeGetTime函数
//需包含,但由于Windows头文件错综复杂的关系
//简单包含比较偷懒:)
//编译行:CL timer2.cpp /link winmm.lib
#include <windows.h>
#include
<stdio.h>

main()
{
DWORD t1, t2;
t1
= timeGetTime();
Sleep(
1000);
t2
= timeGetTime();
printf(
"Begin Time: %u\n", t1);
printf(
"End Time: %u\n", t2);
printf(
"Lasting Time: %u\n",(t2-t1));
}

//Timer3.cpp 使用了QueryPerformanceCounter函数
//编译行:CL timer3.cpp /link KERNEl32.lib
#include <windows.h>
#include
<stdio.h>

main()
{
LARGE_INTEGER t1, t2, tc;
QueryPerformanceFrequency(
&tc);
printf(
"Frequency: %u\n", tc.QuadPart);
QueryPerformanceCounter(
&t1);
Sleep(
1000);
QueryPerformanceCounter(
&t2);
printf(
"Begin Time: %u\n", t1.QuadPart);
printf(
"End Time: %u\n", t2.QuadPart);
printf(
"Lasting Time: %u\n",( t2.QuadPart- t1.QuadPart));
// 这里要计算时间(单位为秒),应加上这一句
double dTotalTime = (double)(t2.QuadPart-t1.QuadPart) / (double)tc.QuadPart; //
printf("耗时: %f\n", dTotalTime);
}



////////////////////////////////////////////////
//以上三个示例程序都是测试1秒钟休眠所耗费的时间
file://测/试环境:Celeron 800MHz / 256M SDRAM
// Windows 2000 Professional SP2
// Microsoft Visual C++ 6.0 SP5
////////////////////////////////////////////////

以下是Timer1的运行结果,使用的是高精度的RDTSC指令
Lasting Time: 804586872

以下是Timer2的运行结果,使用的是最粗糙的timeGetTime API
Begin Time: 20254254
End Time: 20255255
Lasting Time: 1001

以下是Timer3的运行结果,使用的是QueryPerformanceCount API
Frequency: 3579545
Begin Time: 3804729124
End Time: 3808298836
Lasting Time: 3569712

古人说,触类旁通。从一本介绍图形编程的书上得到一个如此有用的实时处理知识,我感到非常高兴。有美不敢自专,希望大家和我一样喜欢这个轻便有效的计时器。

网上有一种说法说
double dTotalTime=(double)(t2.QuadPart-t1.QuadPart)/(double)tc.QuadPart
可能有问题,比如说现在很多主板都有CPU频率自动调整功能,主要是节能,尤其在笔记本上,这样除下来不能保证精确性。我不确定这种说法是否准确,供大家研究

上文主要摘自《使用CPU时间戳进行高精度计时》,其实除了上面提到的三种方法,还有一种常用当然没有上面准确的办法,就是使用GetTickCount函数,这种方法能够获取毫秒级的时间,具体用法如下:

C/C++ code

DWORD startTime
= GetTickCount();

// do something

DWORD totalTime
= GetTickCount() - startTime;




参考文献:
《使用CPU时间戳进行高精度计时》 作者:zhangyan_qd
《Windows图形编程》,(美)Feng Yuan 著
《VC中取得毫秒级的时间》,http://www.cppblog.com/humanchao/archive/2008/04/22/43322.html

2010年9月20日星期一

SSE指令

SSE技术简介


Intel
公司的单指令多数据流式扩展(SSEStreaming SIMD Extensions)技术能够有效增强CPU浮点运算的能力。Visual Studio .NET 2003提供了对SSE指令集的编程支持,从而允许用户在C++代码中不用编写汇编代码就可直接使用SSE指令的功能。MSDN中有关SSE技术的主题 [1]有可能会使不熟悉使用SSE汇编指令编程的初学者感到困惑,但是在阅读MSDN有关文档的同时,参考一下Intel软件说明书(Intel Software manuals[2]会使你更清楚地理解使用SSE指令编程的要点。

SIMDsingle-instruction, multiple-data)是一种使用单道指令处理多道数据流的CPU执行模式,即在一个CPU指令执行周期内用一道指令完成处理多个数据的操作。考虑一下下面这个任务:计算一个很长的浮点型数组中每一个元素的平方根。实现这个任务的算法可以这样写:

for each f in array //对数组中的每一个元素
f = sqrt(f) //
计算它的平方根

为了了解实现的细节,我们把上面的代码这样写:

for each f in array
{
f从内存加载到浮点寄存器
计算平方根
再把计算结果从寄存器中取出放入内存
}

具有Intel SSE指令集支持的处理器有8128位的寄存器,每一个寄存器可以存放4个(32位)单精度的浮点数。SSE同时提供了一个指令集,其中的指令可以允许 把浮点数加载到这些128位的寄存器之中,这些数就可以在这些寄存器中进行算术逻辑运算,然后把结果放回内存。采用SSE技术后,算法可以写成下面的样 子:

for each 4 members in array //对数组中的每4个元素
{
把数组中的这4个数加载到一个128位的SSE寄存器中
在一个CPU指令执行周期中完成计算这4个数的平方根的操作
把所得的4个结果取出写入内存
}

C++
编程人员在使用SSE指令函数编程时不必关心这些128位的寄存器,你可以使用128位的数据类型“__m128”和一系列C++函数来实现这些算 术和逻辑操作,而决定程序使用哪个SSE寄存器以及代码优化是C++编译器的任务。当需要对很长的浮点数数组中的元素进行处理的时候,SSE技术确实是一 种很高效的方法。


SSE程序设计详细介绍

包含的头文件:

所有的SSE指令函数和__m128数据类型都在xmmintrin.h文件中定义:
#include
因为程序中用到的SSE处理器指令是由编译器决定,所以它并没有相关的.lib库文件。

数据分组(Data Alignment

SSE指令处理的每一个浮点数数组必须把其中需要处理的数每16个字节(128位二进制)分为一组。一个静态数组(static array)可由__declspec(align(16))关键字声明:

__declspec(align(16)) float m_fArray[ARRAY_SIZE];

动态数组(dynamic array)可由_aligned_malloc函数为其分配空间:
m_fArray = (float*) _aligned_malloc(ARRAY_SIZE * sizeof(float), 16);

_aligned_malloc函数分配空间的动态数组可以由_aligned_free函数释放其占用的空间:
_aligned_free(m_fArray);

__m128 数据类型

该数据类型的变量可用做SSE指令的操作数,它们不能被用户指令直接存取。_m128类型的变量被自动分配为16个字节的字长。

CPUSSE指令集的支持

如果你的CPU能够具有了SSE指令集,你就可以使用Visual Studio .NET 2003提供的对SSE指令集支持的C++函数库了,你可以查看MSDN中的一个Visual C++ CPUID的例子[4],它可以帮你检测你的CPU是否支持SSEMMX指令集或其它的CPU功能。


编程实例
以下讲解了SSE技术在Visual Studio .NET 2003下的应用实例,你可以在http://www.codeproject.com/cpp/sseintro/SSE_src.zip下载示例程序压缩包。该压缩包中含有两个项目,这两个项目是基于微软基本类库(MFC)建立的Visual C++.NET项目,你也可以按照下面的讲解建立这两个项目。

SSETest 示例项目

SSETest项目是一个基于对话框的应用程序,它用到了三个浮点数组参与运算:

fResult[i] = sqrt( fSource1[i]*fSource1[i] + fSource2[i]*fSource2[i] ) + 0.5

其中i = 0, 1, 2 ... ARRAY_SIZE-1

其中ARRAY_SIZE被定义为30000。数据源数组(Source数组)通过使用sincos函数给它赋 值,我们用Kris Jearakul开发的瀑布状图表控件(Waterfall chart control[3] 来显示参与计算的源数组和结果数组。计算所需的时间(以毫秒ms为单位)在对话框中显示出来。我们使用三种不同的途径来完成计算:

C++代码;
使用SSE指令函数的C++代码;
包含SSE汇编指令的代码。


C++代码:

void CSSETestDlg::ComputeArrayCPlusPlus(
float* pArray1, // [
输入] 源数组1
float* pArray2, // [
输入] 源数组2
float* pResult, // [
输出] 用来存放结果的数组
int nSize) // [
输入] 数组的大小
{

int i;

float* pSource1 = pArray1;
float* pSource2 = pArray2;
float* pDest = pResult;

for ( i = 0; i < nSize; i++ )
{
*pDest = (float)sqrt((*pSource1) * (*pSource1) + (*pSource2)
* (*pSource2)) + 0.5f;

pSource1++;
pSource2++;
pDest++;
}
}


下面我们用具有SSE特性的C++代码重写上面这个函数。为了查询使用SSE指令C++函数的方法,我参考了Intel 件说明书(Intel Software manuals)中有关SSE汇编指令的说明,首先我是在第一卷的第九章找到的相关SSE指令,然后在第二卷找到了这些SSE指令的详细说明,这些说明有 一部分涉及了与其特性相关的C++函数。然后我通过这些SSE指令对应的C++函数查找了MSDN中与其相关的说明。搜索的结果见下表:

实现的功能

对应SSE汇编指令

Visual C++.NET中的SSE函数

432位浮点数放一个128位的存储单元。

movss 和 shufps

_mm_set_ps1

432位浮点数同时进行相乘操作。432位浮点数来自两个128位的存储单元,再把果(乘赋给一个128位的存储单元。

mulps

_mm_mul_ps

432位浮点数同时进行相加操作。432位浮点数来自两个128位的存储单元,再把果(相加之和)赋给一个128位的存储单元。

addps

_mm_add_ps

一个128位存储单元中的432位浮点数同时进行求平方根操作。

sqrtps

_mm_sqrt_ps

使用Visual C++.NET SSE指令函数的代码:

void CSSETestDlg::ComputeArrayCPlusPlusSSE(
float* pArray1, // [
输入] 源数组1
float* pArray2, // [
输入] 源数组2
float* pResult, // [
输出] 用来存放结果的数组
int nSize) // [
输入] 数组的大小
{
int nLoop = nSize/ 4;

__m128 m1, m2, m3, m4;

__m128* pSrc1 = (__m128*) pArray1;
__m128* pSrc2 = (__m128*) pArray2;
__m128* pDest = (__m128*) pResult;


__m128 m0_5 = _mm_set_ps1(0.5f); // m0_5[0, 1, 2, 3] = 0.5

for ( int i = 0; i < nLoop; i++ )
{
m1 = _mm_mul_ps(*pSrc1, *pSrc1); // m1 = *pSrc1 * *pSrc1
m2 = _mm_mul_ps(*pSrc2, *pSrc2); // m2 = *pSrc2 * *pSrc2
m3 = _mm_add_ps(m1, m2); // m3 = m1 + m2
m4 = _mm_sqrt_ps(m3); // m4 = sqrt(m3)
*pDest = _mm_add_ps(m4, m0_5); // *pDest = m4 + 0.5

pSrc1++;
pSrc2++;
pDest++;
}
}

使用SSE汇编指令实现的C++函数代码:

void CSSETestDlg::ComputeArrayAssemblySSE(
float* pArray1, // [
输入] 源数组1
float* pArray2, // [
输入] 源数组2
float* pResult, // [
输出] 用来存放结果的数组
int nSize) // [
输入] 数组的大小
{
int nLoop = nSize/4;
float f = 0.5f;

_asm
{
movss xmm2, f // xmm2[0] = 0.5
shufps xmm2, xmm2, 0 // xmm2[1, 2, 3] = xmm2[0]

mov esi, pArray1 // 输入的源数组1的地址送往esi
mov edx, pArray2 //
输入的源数组2的地址送往edx

mov edi, pResult // 输出结果数组的地址保存在edi
mov ecx, nLoop //
循环次数送往ecx

start_loop:
movaps xmm0, [esi] // xmm0 = [esi]
mulps xmm0, xmm0 // xmm0 = xmm0 * xmm0

movaps xmm1, [edx] // xmm1 = [edx]
mulps xmm1, xmm1 // xmm1 = xmm1 * xmm1

addps xmm0, xmm1 // xmm0 = xmm0 + xmm1
sqrtps xmm0, xmm0 // xmm0 = sqrt(xmm0)

addps xmm0, xmm2 // xmm0 = xmm1 + xmm2

movaps [edi], xmm0 // [edi] = xmm0

add esi, 16 // esi += 16
add edx, 16 // edx += 16
add edi, 16 // edi += 16

dec ecx // ecx--
jnz start_loop //
如果不为0则转向start_loop
}
}

最后,在我的计算机上运行计算测试的结果:

C++代码计算所用的时间是26 毫秒
使用SSEC++ 函数计算所用的时间是 9 毫秒
包含SSE汇编指令的C++代码计算所用的时间是 9 毫秒

以上的时间结果是在Release优化编译后执行程序得出的。

SSESample 示例项目


SSESample
项目是一个基于对话框的应用程序,其中它用下面的浮点数数组进行计算:

fResult[i] = sqrt(fSource[i]*2.8)

其中i = 0, 1, 2 ... ARRAY_SIZE-1

这个程序同时计算了数组中的最大值和最小值。ARRAY_SIZE被定义为100000,数组中的计算结果在列表框中显示出来。其中在我的机子上用下面三种方法计算所需的时间是:
C++代码计算 6 毫秒
使用SSEC++ 函数计算 3 毫秒
使用SSE汇编指令计算 2 毫秒

大家看到,使用SSE汇编指令计算的结果会好一些,因为使用了效率增强了的SSX寄存器组。但是在通常情况下,使用SSEC++ 函数计算会比汇编代码计算的效率更高一些,因为C++编译器的优化后的代码有很高的运算效率,若要使汇编代码比优化后的代码运算效率更高,这通常是很难做 到的。

C++代码:

// 输入: m_fInitialArray
//
输出: m_fResultArray, m_fMin, m_fMax
void CSSESampleDlg::OnBnClickedButtonCplusplus()
{
m_fMin = FLT_MAX;
m_fMax = FLT_MIN;

int i;

for ( i = 0; i < ARRAY_SIZE; i++ )
{
m_fResultArray[i] = sqrt(m_fInitialArray[i] * 2.8f);

if ( m_fResultArray[i] < m_fMin )
m_fMin = m_fResultArray[i];

if ( m_fResultArray[i] > m_fMax )
m_fMax = m_fResultArray[i];
}
}

使用Visual C++.NET SSE指令函数的代码:


// 输入: m_fInitialArray
//
输出: m_fResultArray, m_fMin, m_fMax
void CSSESampleDlg::OnBnClickedButtonSseC()
{
__m128 coeff = _mm_set_ps1(2.8f); // coeff[0, 1, 2, 3] = 2.8
__m128 tmp;

__m128 min128 = _mm_set_ps1(FLT_MAX); // min128[0, 1, 2, 3] = FLT_MAX
__m128 max128 = _mm_set_ps1(FLT_MIN); // max128[0, 1, 2, 3] = FLT_MIN

__m128* pSource = (__m128*) m_fInitialArray;
__m128* pDest = (__m128*) m_fResultArray;

for ( int i = 0; i < ARRAY_SIZE/4; i++ )
{
tmp = _mm_mul_ps(*pSource, coeff); // tmp = *pSource * coeff
*pDest = _mm_sqrt_ps(tmp); // *pDest = sqrt(tmp)

min128 = _mm_min_ps(*pDest, min128);
max128 = _mm_max_ps(*pDest, max128);

pSource++;
pDest++;
}

// 计算max128的最大值和min128的最小值
union u
{
__m128 m;
float f[4];
} x;

x.m = min128;
m_fMin = min(x.f[0], min(x.f[1], min(x.f[2], x.f[3])));

x.m = max128;
m_fMax = max(x.f[0], max(x.f[1], max(x.f[2], x.f[3])));
}

使用SSE汇编指令的C++函数代码:


// 输入: m_fInitialArray
//
输出: m_fResultArray, m_fMin, m_fMax
void CSSESampleDlg::OnBnClickedButtonSseAssembly()
{

float* pIn = m_fInitialArray;
float* pOut = m_fResultArray;

float f = 2.8f;
float flt_min = FLT_MIN;
float flt_max = FLT_MAX;

__m128 min128;
__m128 max128;

// 使用以下的附加寄存器:xmm2xmm3xmm4:
// xmm2 –
相乘系数
// xmm3 –
最小值
// xmm4 –
最大值

_asm
{
movss xmm2, f // xmm2[0] = 2.8
shufps xmm2, xmm2, 0 // xmm2[1, 2, 3] = xmm2[0]

movss xmm3, flt_max // xmm3 = FLT_MAX
shufps xmm3, xmm3, 0 // xmm3[1, 2, 3] = xmm3[0]

movss xmm4, flt_min // xmm4 = FLT_MIN
shufps xmm4, xmm4, 0 // xmm3[1, 2, 3] = xmm3[0]

mov esi, pIn // 输入数组的地址送往esi
mov edi, pOut //
输出数组的地址送往edi
mov ecx, ARRAY_SIZE/4 //
循环计数器初始化

start_loop:
movaps xmm1, [esi] // xmm1 = [esi]
mulps xmm1, xmm2 // xmm1 = xmm1 * xmm2
sqrtps xmm1, xmm1 // xmm1 = sqrt(xmm1)
movaps [edi], xmm1 // [edi] = xmm1

minps xmm3, xmm1
maxps xmm4, xmm1

add esi, 16
add edi, 16

dec ecx
jnz start_loop


movaps min128, xmm3
movaps max128, xmm4
}

union u
{
__m128 m;
float f[4];
} x;

x.m = min128;
m_fMin = min(x.f[0], min(x.f[1], min(x.f[2], x.f[3])));

x.m = max128;
m_fMax = max(x.f[0], max(x.f[1], max(x.f[2], x.f[3])));

}


参考文档:

[1]MSDN, SSE技术主题:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclang/html/vcrefstreamingsimdextensions.asp

[2]Intel软件说明书(Intel Software manuals):
http://developer.intel.com/design/archives/processors/mmx/index.htm

[3] Kris Jearakul的瀑布状图表控件:http://www.codeguru.com/controls/Waterfall.shtml

[4] Microsoft Visual C++ CPUID示例:
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcsample/html/vcsamcpuiddeterminecpucapabilities.asp

[5] Matt PietrekMicrosoft Systems Journal 19982月刊上的评论文章:
http://www.microsoft.com/msj/0298/hood0298.aspx