代码优化-之-优化浮点数取整
关于环境的英语作文-火警119
代码优化－之－优化浮点数取整
HouSisong@ 2007.05.19
tag: 浮点数转换为整数,fpu,sse,s
se2,读缓冲区优化,代码优化,ftol,取
整,f2l,ftoi,f2i,floattoin
t
摘要:
本文首先给出一个浮点数取整的需求，并使用默认的取整方式，然后通过尝试各种
方法来优化它的速度；
最终的浮点数取整实现速度甚至达到了初始代码的5倍(是vc6代码的18倍)！
(注意: 文章中的测试结果在不同的CPU和系统环境下可能有不同的结果,数据仅作参考)
(2007.06.08更新： 补充SSE3新增的FPU取整指令fisttp的说明)
(2007.06.04更新： 一些修正、补充double取整、补充FPU的RC场说明)
正文:
为了便于讨论，这里代码使用C++，涉及到汇编优化的时
候假定为x86平台;使用的编译
器为vc2005;
测试使用的CPU为AMD64x2 4200+,测试时使用的单线程执行;
为了代码的可读性,没有加入异常处理代码;
A:
需要优化的原始代码(使用了大量的浮点数到整数的转换)
#include
#include
#include
volatile long testResult;
使用一个全局域的volatile变量以避免编译器把
需要测试的代码优化掉
const
long testDataCount=10000000;
const long
testCount=20;
float
fSrc[testDataCount];
#define asm __asm
void ftol_test_0()
{
long
tmp=0;
for (long i = 0; i < testDataCount;
++i)
tmp +=(long)fSrc[i]; 需要优化的浮点数取整
testResult=tmp;
}
int main()
{
inti
for (long
i=0;i
1))
*rand()*(1.0RAND_MAX));
test
double start0=(double)clock();
for
(long c=0;c
start0=((double)clock()-sta
rt0)*(1.0CLOCKS_PER_SEC);
out
printf (
0);
return 0;
}
速度测试:
==================
=============================================
=
==============
ftol_test_0
1.047 秒 (VC6编译 3.64
秒):
(使用vc2005的SSE编译选项 “arch:SSE” 0.437 秒)
一般编译器生成的浮点数转换为整数的指令序列都比预想的速度慢很多,它的性能代价
很容易被人忽略；
在VC6编译器下上面的代码需要运行3.64秒，代码先修改FPU的取整模式(RC场)，完
成取整后在恢复RC场；
VC2006生成的代码在CPU支持SSE的时候会调用使用cvtts
d2si指令实现的版本，从
而加快了取整的速度,
达到了1.047秒，快了很多！
让我们来尝试继续优化这个含有大量取整操作的函数ftol_test_0；
B:
最容易想到的就是用浮点协处理器(FPU)(也可以称作x87)来优化取整
将设置FPU取整方式和恢复FPU的取整方式的代码放到循环体外面从而加快了速度
void ftol_test_fpu()
{
unsigned
short RC_Old;
unsigned short RC_Edit;
long isrc;
asm
{
设置FPU的取整方式 为了直接使用fistp浮点指令
FNSTCW
RC_Old 保存协处理器控制字,用来恢复
FNSTCW RC_Edit 保存协处理器控制字,用来修改
FWAIT
OR RC_Edit, 0x0F00 改为
RC=11 使FPU向零取整
FLDCW RC_Edit
载入协处理器控制字,RC场已经修改
mov
ecx,testDataCount
xor eax,eax
test ecx,ecx
jle EndLoop
lea edx,[fSrc+ecx*4]
neg ecx
StartLoop:
fld dword ptr [edx+ecx*4]
fistp isrc
add eax,isrc
inc ecx
jnz
StartLoop
EndLoop:
mov testResult,eax;
恢复FPU的取整方式
FWAIT
FLDCW
RC_Old
}
}
RC场占用第11、10bit位 用于控制舍入方向
RC=00 向最近(或偶数)舍入
RC=01 向下(负无穷大)舍入
RC=10
向上(正无穷大)舍入 RC=11 向零舍入
提示:一般的编程语言环境中,RC场都会设置为一个默认值(一般为RC=00),
语言就可能利用这一点做快速的取整(比如Delphi中的round函数)，但某些引
入的
第三方库或代码可能会修改该默认值，从而造成以前运行正确的程序出现异常情
况
速度测试:
==================
=============================================
=
==============
ftol_test_fpu
0.407 秒
SSE3增加了一条FPU取整指令fisttp
,和fistp指令功能几乎相同(我的电脑上经过测
试速度也相同)，但默认向0取整，和RC场设置
无关，所以使用fisttp的代码就可以不
管RC场了，有利于简化代码和优化性能；
C:利用浮点数的编码格式来“手工”处理浮点数到整数的转换(利用了IEEE浮点编码格式)
inline long _ftol_ieee(float f)
{
long a = *(long*)(&f);
unsigned long mantissa = (a&((1<<23)-1))|(1<<23);
不支
持非规格化浮点数
long exponent =
((a&0x7fffffff)>>23);
long r =
(mantissa<<8) >> (31+127-exponent);
long sign = (a>>31);
return ((r
^ (sign)) - sign ) &~ ((exponent-127)>>31);
}
void ftol_test_ieee()
{
long tmp=0;
for (long i = 0; i <
testDataCount; ++i)
tmp
+=_ftol_ieee(fSrc[i]);
testResult=tmp;
}
速度测试:
============
==================================================
=
===============
ftol_test_ieee
0.828 秒
手工实现居然超过了VC2005的SSE实现(主要是VC2005的实现函数调用开销太大)； <
/p>
如果能够允许存在误差的话，还有一个快速的取整算法(注意，该函数的结果和标准不完全
相同)： ftol_test_ieee_M 0.438
秒
inline long ftol_ieee_M(float x)
{
static const float magic_f = (3<<21);
static const long magic_i = 0x4ac00000;
float ftmp=x+magic_f;
return
(*((long*)&ftmp)-magic_i) >> 1;
}
D:对于Double到整数的转换有一个超强的算法 (利用了IEEE浮点编码格式)
inline long _ftol_ieee_MagicNumber(double x)
{
static const double magic =
6755399441055744.0; (1<<5
1) | (1<<52)
double tmp = x;
tmp += (x > 0) ?
-0.499999999999 : +0.499999999999;
如果
需要4舍5入取整就去掉这一行
tmp += magic;
return *(long*)&tmp;
}
void ftol_test_ieee_MagicNumber()
{
long tmp=0;
for (long i = 0; i <
testDataCount; ++i)
tmp
+=_ftol_ieee_MagicNumber(fSrc[i]);
testResult=tmp;
}
(警告:该算法要求FPU的计算精度为高精度模式，
某些程序可能为了速度而将FPU改成了
低精度模式，
比如在D3D中会默认调整该设置)
速度测试:
===========
==================================================
==
===============
ftol_test_ieee_MagicNumber 1.813 秒
如果需要4舍5入取整，速度就能快出很多，降低到0.407秒
(
ftol_test_ieee,ftol_test_ieee_MagicNumber的实现主要参考了:
云风的
《_ftol 的优化》：
http:200512_ftol_
和 http:?show=64008
这里有改动)
E:借鉴vc2005的SSE实现使用cvttss2si指令
void
ftol_test_sse()
{
asm
{
mov ecx,testDataCount
xor
eax,eax
test ecx,ecx
jle EndLoop
lea
edx,[fSrc+ecx*4]
neg ecx
StartLoop:
cvttss2si ebx,dword
ptr [edx+ecx*4]
add eax,ebx
inc ecx
jnz StartLoop
EndLoop:
mov testResult,eax;
}
}
速度测试:
==================
=============================================
=
==============
ftol_test_sse
0.422 秒
F:
cvttss2si是一个单指令单数据流的指令，我们可以使用它的单指令多数据流的版本：
cvttps2dq指令；它能同时将4个float取整！
long
ftol_sse_expand16(float* psrc,long count16)
{
long result;
asm
{
mov ecx,count16
test ecx,ecx
jle EndLoop
pxor xmm0,xmm0
pxor xmm1,xmm1
mov ecx,count16
mov
edx,psrc
lea edx,[edx+ecx*4]
neg ecx
StartLoop:
一次循环处理16个float
cvttps2dq
xmm2,xmmword ptr [edx+ecx*4]
cvttps2dq xmm3,xmmword ptr [edx+ecx*4+16]
cvttps2dq xmm4,xmmword ptr [edx+ecx*4+16*2]
cvttps2dq xmm5,xmmword ptr [edx+ecx*4+16*3]
paddd xmm2,xmm3
paddd
xmm4,xmm5
add ecx,16
paddd xmm0,xmm2
paddd
xmm1,xmm4
jnz StartLoop
EndLoop:
paddd
xmm0,xmm1
movaps xmm1,xmm0
movhlps xmm1,xmm0
paddd xmm0,xmm1
movaps
xmm2,xmm0
shufps xmm2,xmm0,1
paddd xmm0,xmm2
movd eax,xmm0
mov
result,eax
}
return result;
}
void ftol_test_sse_expand16()
{
long tmp=0;
for (long i = 0; i <
testDataCount; i+=2000)
{
tmp+=ftol_sse_expand16(&fSrc[i],2000);2000=16*125
}
todo:
因为testDataCount是2000的倍数，所以这里不用处理边界了
testResult=tmp;
}
速度测试:
==============================================
=================
===============
ftol_test_sse_expand16 0.281 秒
G:
由于函数需要读取大量的数据来处理，所以可以考虑优化读缓冲区(也可以考虑使用显
式预读指令)
long ftol_sse_expand16_prefetch(float*
psrc,long count16)
{
long result;
asm
{
mov ecx,count16
test ecx,ecx
jle EndLoop
预读
mov edx,psrc
lea edx,[edx+ecx*4]
neg ecx
ReadStartLoop:
mov
eax,dword ptr [edx+ecx*4]
add
ecx,16
jnz ReadStartLoop
pxor xmm0,xmm0
pxor xmm1,xmm1
mov ecx,count16
neg ecx
StartLoop:
cvttps2dq xmm2,xmmword ptr [edx+ecx*4]
cvttps2dq xmm3,xmmword ptr [edx+ecx*4+16]
cvttps2dq xmm4,xmmword ptr [edx+ecx*4+16*2]
cvttps2dq xmm5,xmmword ptr [edx+ecx*4+16*3]
paddd xmm2,xmm3
paddd
xmm4,xmm5
add ecx,16
paddd xmm0,xmm2
paddd
xmm1,xmm4
jnz StartLoop
EndLoop:
paddd
xmm0,xmm1
movaps xmm1,xmm0
movhlps xmm1,xmm0
paddd xmm0,xmm1
movaps
xmm2,xmm0
shufps xmm2,xmm0,1
paddd xmm0,xmm2
movd eax,xmm0
mov
result,eax
}
return result;
}
void ftol_test_sse_expand16_prefetch()
{
long tmp=0;
for (long i =
0; i < testDataCount; i+=2000)
{
tmp+=ftol_sse_expand16_prefetch(&fSrc[i],2000);
}
testResult=tmp;
}
速度测试:
===========================
====================================
==========
=====
ftol_test_sse_expand16_prefetch
0.219 秒
H:补充Double的取整，完整测试源代码
#include
#include
#include
volatile long
testResult;
使用一个全局域的volatile变量以避免编译器把
需要测试的代码优化掉
const
long testDataCount=10000000;
const long
testCount=20;
double
fSrc[testDataCount];
#define asm __asm
void dftol_test_0()
{
long tmp=0;
for (long i = 0; i < testDataCount; ++i)
{
tmp +=(long)fSrc[i];
需要优化的浮点取整
}
testResult=tmp;
}
void dftol_test_fpu()
{
unsigned short RC_Old;
unsigned
short RC_Edit;
long isrc;
asm
设置FPU的取整方式 为了直接使用fistp浮点指令
{
FNSTCW RC_Old 保存协处理器控制字,用来恢复
FNSTCW RC_Edit 保存协处理器控制字,用来修改
FWAIT
OR RC_Edit, 0x0F00 改为
RC=11 使FPU向零取
整
FLDCW
RC_Edit 载入协处理器控制字,RC场已经修改
}
asm
{
mov
ecx,testDataCount
xor eax,eax
test ecx,ecx
jle EndLoop
lea edx,[fSrc+ecx*8]
neg ecx
StartLoop:
fld qword ptr [edx+ecx*8]
fistp isrc
add eax,isrc
inc ecx
jnz
StartLoop
EndLoop:
mov testResult,eax;
}
asm 恢复FPU的取整方式
{
FWAIT
FLDCW RC_Old
}
}
inline
long dftol_ieee_MagicNumber(double x)
{
static const double magic =
6755399441055744.0; (1<<5
1) | (1<<52)
double tmp = x;
tmp += (x > 0) ?
-0.499999999999 : +0.499999999999;
如果需要4
舍5入取整就去掉这一行
tmp += magic;
return *(long*)&tmp;
}
void
dftol_test_ieee_MagicNumber()
{
long
tmp=0;
for (long i = 0; i < testDataCount;
++i)
tmp
+=dftol_ieee_MagicNumber(fSrc[i]);
testResult=tmp;
}
void
dftol_test_sse2()
{
asm
{
mov ecx,testDataCount
xor eax,eax
test ecx,ecx
jle EndLoop
lea
edx,[fSrc+ecx*8]
neg ecx
StartLoop:
cvttsd2si ebx,qword
ptr [edx+ecx*8]
add eax,ebx
inc ecx
jnz
StartLoop
EndLoop:
mov testResult,eax;
}
}
long dftol_sse2_expand8(double* psrc,long
count8)
{
long result;
asm
{
mov ecx,count8
test ecx,ecx
jle EndLoop
pxor xmm0,xmm0
pxor
xmm1,xmm1
mov edx,psrc
lea edx,[edx+ecx*8]
neg
ecx
StartLoop:一次循环处理8个double
cvttpd2dq xmm2,xmmword ptr [edx+ecx*8]
cvttpd2dq xmm3,xmmword ptr [edx+ecx*8+16]
cvttpd2dq xmm4,xmmword ptr [edx+ecx*8+16*2]
cvttpd2dq xmm5,xmmword ptr [edx+ecx*8+16*3]
paddd xmm2,xmm3
paddd
xmm4,xmm5
add ecx,8
paddd xmm0,xmm2
paddd
xmm1,xmm4
jnz StartLoop
EndLoop:
paddd
xmm0,xmm1
movaps xmm1,xmm0
shufps xmm1,xmm0,1
paddd xmm0,xmm1
movd eax,xmm0
mov
result,eax
}
return result;
}
void dftol_test_sse2_expand8()
{
long tmp=0;
for (long i = 0; i <
testDataCount; i+=2000)
{
tmp+=dftol_sse2_expand8(&fSrc[i],2000);2000=8*256
}
todo:
因为testDataCount是2000的倍数，所以这里不用处理边界了
testResult=tmp;
}
long
dftol_sse2_expand8_prefetch(double* psrc,long
count8)
{
long result;
asm
{
mov ecx,count8
test ecx,ecx
jle EndLoop
预读
mov edx,psrc
lea edx,[edx+ecx*8]
neg ecx
ReadStartLoop:
mov
eax,dword ptr [edx+ecx*8]
add
ecx,8
jnz ReadStartLoop
pxor xmm0,xmm0
pxor
xmm1,xmm1
mov ecx,count8
neg ecx
StartLoop:
cvttpd2dq xmm2,xmmword ptr [edx+ecx*8]
cvttpd2dq xmm3,xmmword ptr [edx+ecx*8+16]
cvttpd2dq xmm4,xmmword ptr [edx+ecx*8+16*2]
cvttpd2dq xmm5,xmmword ptr [edx+ecx*8+16*3]
paddd xmm2,xmm3
paddd
xmm4,xmm5
add ecx,8
paddd xmm0,xmm2
paddd
xmm1,xmm4
jnz
StartLoop
EndLoop:
paddd xmm0,xmm1
movaps
xmm2,xmm0
shufps xmm2,xmm0,1
paddd xmm0,xmm2
movd eax,xmm0
mov
result,eax
}
return result;
}
void dftol_test_sse2_expand8_prefetch()
{
long tmp=0;
for (long i = 0; i <
testDataCount; i+=2000)
{
tmp+=dftol_sse2_expand8_prefetch(&fSrc[i],2000);
}
testResult=tmp;
}
int main()
{
inti
for
(long i=0;i
test
double start0=(double)clock();
for (long c=0;c
dftol_test_0();
dftol_test_fpu();
dftol_test_ieee_MagicNumber();
dftol_test_sse2();
dftol_test_sse2_expand8();
dftol_test_sse2_expand8_prefetch();
start
0=((double)clock()-start0)*(1.0CLOCKS_PER_SEC);
out
printf (
0);
return 0;
}
H:把测试结果放在一起
速度测试:
编译器vc2005 CPU为AMD64x2 4200+ 单线程
=======
==================================================
======
===============
ftol_test_0
1.047 秒 (“arch:SSE”0.437秒、
VC6编译3.64秒)
ftol_test_fpu 0.407 秒
ftol_test_ieee 0.828 秒
ftol_test_ieee_MagicNumber 1.813 秒
(4舍5入取整0.407 秒)
ftol_test_sse
0.422 秒
ftol_test_sse_expand16
0.281 秒
ftol_test_sse_expand16_prefetch
0.219 秒
======================================
=========================
===============秒
补充double的取整
dftol_test_0
1.141 秒 (“arch:SSE2”0.734
秒、VC6编译3.675秒)
dftol_test_fpu 0.719 秒
dftol_test_ieee_MagicNumber
1.688 秒 (4舍5入取整0.703 秒)
dftol_test_sse2
0.734 秒
dftol_test_sse2_expand8
0.609 秒
dftol_test_sse2_expand8_prefetch
0.516 秒
提示:为了避免浮点数到整数的转换可以考虑用定点数来表示小数，从而在需要取整的时候
可
以用一个快速的移位指令来实现
苹果牛奶减肥法-音乐巨人贝多芬