【日积月累】优化小技巧

G-Spider · 发表于 2010-12-24 22:14:48

17# G-Spider 有bug 更正(精确拷贝到字节)，顺便加上硬预取方式，对于小字节量拷贝用movsd过渡。测试平台：

测试32.1 MB文件存拷贝： _fast_memcpy1 （movsd） 33 ms _fast_memcpy9 (SSE 系列) 23 ms _block_prefetch (硬预取 block_size 8KB) 22 ms 代码：

;************************************************************
;-==-: fast_memcpyTest By G-Spider @2010
;-==-: ml /c /coff memcpyTest.asm
;-==-: link /subsystem:console memcpyTest.obj
;************************************************************
.686p
.XMM
.model flat,stdcall
option casemap:none
include windows.inc
include user32.inc
include kernel32.inc
include msvcrt.inc
includelib user32.lib
includelib kernel32.lib
includelib msvcrt.lib
BLOCK_SIZE equ 8192
.data
dwlm dd 1000 ;1000是毫秒为单位,1000000则是微秒为单位
fmt db '计算用时:',0dh,0ah,0
fmt1 db '%6lld ms',0dh,0ah,0
szFileName db 'xinyu.avi',0 ;32,954KB 原文件
szOutName db 'output.avi',0 ;输出文件;
;szFileName db 'test.png',0 ;63KB 请以微秒为单位原文件
;szOutName db 'output.png',0 ;输出文件
szPause db 'Pause',0
.data?
hHandle dd ?
hHandle1 dd ?
lpInputBuf dd ?
lpOutputBuf dd ?
dwStrlen dd ?
lpNumberOfBytes dd ?
dwOldProcessP dd ?
dwOldThreadP dd ?
;-------------------------------------
dqTickCounter1 dq ?
dqTickCounter2 dq ?
dqFreq dq ?
dqTime dq ?
.code
;*************************************
_fast_memcpy1 proc lpdst,lpsrc,dwlen
;%define param esp+8+4
;%define src param+0
;%define dst param+4
;%define len param+8
mov esi, lpsrc ; source array
mov edi, lpdst ; destination array
mov ecx, dwlen
mov eax,ecx
and eax,3
shr ecx, 2 ; convert to DWORD count
test ecx,ecx
jz A000
rep movsd
A000:
test eax,eax
jz A001
mov ecx,eax
rep movsb
A001:
xor eax,eax
ret
_fast_memcpy1 endp
;***************************************
_fast_memcpy9 proc lpdst,lpsrc,dwlen
mov esi, lpsrc ;src pointer
mov edi, lpdst ;dest pointer
mov ebx, dwlen ;ebx is our counter
mov ecx, ebx
and ecx, 07fh ;剩余的<128字节
shr ebx, 7 ;divide by 128 (8 * 128bit registers)
test ebx,ebx
jz A000
ALIGN 16
loop_copy:
prefetchnta 128[ESI]; SSE2 prefetch
prefetchnta 160[ESI];
prefetchnta 192[ESI];
prefetchnta 224[ESI];
movdqa xmm0, 0[ESI] ; move data from src to registers
movdqa xmm1, 16[ESI];
movdqa xmm2, 32[ESI];
movdqa xmm3, 48[ESI];
movdqa xmm4, 64[ESI];
movdqa xmm5, 80[ESI];
movdqa xmm6, 96[ESI];
movdqa xmm7, 112[ESI];
movntdq 0[EDI], xmm0 ; move data from registers to dest
movntdq 16[EDI], xmm1;
movntdq 32[EDI], xmm2;
movntdq 48[EDI], xmm3;
movntdq 64[EDI], xmm4;
movntdq 80[EDI], xmm5;
movntdq 96[EDI], xmm6;
movntdq 112[EDI], xmm7;
add esi, 128;
add edi, 128;
dec ebx;
jnz loop_copy; //loop please
sfence
align 16
A000:
mov eax, ecx
and eax, 3
shr ecx, 2 ; co[local]1[/local]nvert to DWORD count
test ecx,ecx
jz short A001
rep movsd
A001:
test eax,eax
jz A002
mov ecx,eax
rep movsb
A002:
xor eax,eax
ret
_fast_memcpy9 endp
_block_prefetch proc lpdst,lpsrc,dwlen
mov edi, lpdst
mov esi, lpsrc
mov eax, dwlen
mov edx, eax
and eax, (BLOCK_SIZE-1) ;4096-1=0fffh ;8192-1=1fffh;16*1024-1=3fffh
and edx, 0ffffe000h ;与 BLOCK_SIZE有关
test edx,edx
jz A000
align 16
main_loop:
xor ecx,ecx
align 16
prefetch_loop:
movaps xmm0, [esi+ecx]
movaps xmm0, [esi+ecx+64]
add ecx,128
cmp ecx,BLOCK_SIZE
jne prefetch_loop
xor ecx,ecx
align 16
cpy_loop:
movdqa xmm0,[esi+ecx]
movdqa xmm1,[esi+ecx+16]
movdqa xmm2,[esi+ecx+32]
movdqa xmm3,[esi+ecx+48]
movdqa xmm4,[esi+ecx+64]
movdqa xmm5,[esi+ecx+16+64]
movdqa xmm6,[esi+ecx+32+64]
movdqa xmm7,[esi+ecx+48+64]
movntdq [edi+ecx],xmm0
movntdq [edi+ecx+16],xmm1
movntdq [edi+ecx+32],xmm2
movntdq [edi+ecx+48],xmm3
movntdq [edi+ecx+64],xmm4
movntdq [edi+ecx+80],xmm5
movntdq [edi+ecx+96],xmm6
movntdq [edi+ecx+112],xmm7
add ecx,128
cmp ecx,BLOCK_SIZE
jne cpy_loop
add esi,ecx
add edi,ecx
sub edx,ecx
jnz main_loop
sfence
align 16
A000:
mov ecx, eax
and eax, 3
shr ecx, 2 ; convert to DWORD count
test ecx,ecx
jz short A001
rep movsd
A001:
test eax,eax
jz A002
mov ecx,eax
rep movsb
A002:
xor eax,eax
ret
_block_prefetch endp
;*****************************************************
start:
invoke CreateFile,offset szFileName,GENERIC_READ,FILE_SHARE_READ,\
NULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL
.if eax == INVALID_HANDLE_VALUE
invoke MessageBox,NULL,0,0,0
.endif
mov hHandle,eax
invoke GetFileSize,eax,NULL
mov dwStrlen,eax
add eax,16
invoke crt_malloc,eax
mov lpInputBuf,eax
mov edx,lpInputBuf
and eax,0fh
jz Good1
xor eax,edx
add eax,10h
mov lpInputBuf,eax
Good1:
invoke RtlZeroMemory,lpInputBuf,dwStrlen
invoke ReadFile,hHandle,lpInputBuf,dwStrlen,offset lpNumberOfBytes,NULL
mov eax,dwStrlen
add eax,16
invoke crt_malloc,eax
mov lpOutputBuf,eax
mov edx,lpOutputBuf
and eax,0fh
jz Good2
xor eax,edx
add eax,10h
mov lpOutputBuf,eax
Good2:
invoke RtlZeroMemory,lpOutputBuf,dwStrlen
;----------------------------------------------------
invoke crt_printf,offset fmt
mov ecx,5 ;测试5次
.while ecx!=0
push ecx
invoke GetCurrentProcess
invoke GetPriorityClass,eax
mov dwOldProcessP,eax
invoke GetCurrentThread
invoke GetThreadPriority,eax
mov dwOldThreadP,eax
invoke GetCurrentProcess
invoke SetPriorityClass,eax,REALTIME_PRIORITY_CLASS
invoke GetCurrentThread
invoke SetThreadPriority,eax,THREAD_PRIORITY_TIME_CRITICAL
;--------------------------------------------------
invoke QueryPerformanceCounter,addr dqTickCounter1
;时间测试
;invoke _fast_memcpy1,lpOutputBuf,lpInputBuf,dwStrlen
;invoke _fast_memcpy9,lpOutputBuf,lpInputBuf,dwStrlen
invoke _block_prefetch,lpOutputBuf,lpInputBuf,dwStrlen
;测试结束
invoke QueryPerformanceCounter,addr dqTickCounter2
invoke QueryPerformanceFrequency,addr dqFreq
mov eax,dword ptr dqTickCounter1
mov edx,dword ptr dqTickCounter1[4]
sub dword ptr dqTickCounter2,eax
sub dword ptr dqTickCounter2[4],edx
;----------------------------------------------------
;优先级还原
invoke GetCurrentThread
invoke SetThreadPriority,eax,dwOldThreadP
invoke GetCurrentProcess
invoke SetPriorityClass,eax, dwOldProcessP
finit
fild dqFreq
fild dqTickCounter2
fimul dwlm
fdivr
fistp dqTime ;dqTime中的64位值就是时间间隔(以微秒为单位)
;---------------------------------------------------
invoke crt_printf,offset fmt1,dqTime
pop ecx
dec ecx
.endw
;输出copy文件
invoke CreateFile,offset szOutName,GENERIC_WRITE,FILE_SHARE_READ,\
NULL,CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL
.if eax == INVALID_HANDLE_VALUE
invoke MessageBox,NULL,0,0,0
.endif
mov hHandle1,eax
invoke WriteFile,eax,lpOutputBuf,dwStrlen,offset lpNumberOfBytes,NULL
invoke CloseHandle,hHandle
invoke CloseHandle,hHandle1
invoke crt_system,offset szPause
invoke ExitProcess,0
end start

复制代码

G-Spider · 发表于 2011-4-7 15:30:48

再接着聊一下吧，主要是Agner Fog 的日志更新了，小有激动。 Optimizing subroutines in assembly language An optimization guide for x86 platforms By Agner Fog. Copenhagen University College of Engineering. Copyright © 1996 - 2011. Last updated 2011-01-30. 当时一直说什么Cache怎么怎么的，也没有具体的测试一下，这次深入一点(对以上文档关于 Optimizing memory access部分的个人理解)，也肯请高手指点。

G-Spider · 发表于 2011-4-7 16:10:56

CPU读一级缓存数据大约3个时钟周期，读二级缓存数据大约10个时钟周期，读主存大约100个时钟周期，如果访存缺页，花的时间更多了。当然不同的系统会有所差别，但也可以看出不同级别的数据读取的确存在性能差异。可见缓存的数据和代码大小对性能的影响是比较大的，如果缓存中数据或代码缺失，可能要花费上百个时钟周期。所以说优化缓冲很重要。缓存是怎样工作的呢？缓存作为临时存储器，比主存更靠近微处理器。被用或将要被用的指令或数据通常会载入缓存，以便更快地获取。通常的CPU有1，2或3级的缓存(cache)。1-cache最靠近微处理器，对其访问所花时间最少。以P4处理器的1-cache缓存为例。它包含8KB的数据缓存，每个缓存行有64字节，所以共128个缓存行。采用4路组相联结构。这意味着数据按地址进行分块存储到Cache中，而不能任意分配缓存。载入到1-cahce中的数据是64字节对齐的，2^6=64 所以地址的低6位(位0~位5) 对数据的载入不重要。4路组相联结构把数据分成块，每一块有4个缓存行，所以128/4=32=2^5 共32个块。载入到某一块怎么决定呢，这就可以由地址接下来的5位决定(位6~位10)，这样（按经验）如果位6~位10是相同的，则可以被载入到缓存的同一个块中（每次以缓存行为单位进行载入数据，可见这里每块最多能载入4个缓存行），如果来了第5个数据行，而位6~位10跟前4个相同，这样就必须替换出之前的4行之一，用最近最少被使用(the least recently used)策略替换。并且我们可以发现，这里每块4个缓存行中的数据地址至少有2^11=2048字节的间隙。

G-Spider · 发表于 2011-4-7 16:30:48

对于上面的内容，这里给个简单的例子。如下代码片段，假设内存地址edi能被64整除（仍然是上面的P4类型）。 ; Example 11.1. Level-1 cache contention again: mov eax, [edi] ;0000 0000 0000 0000 mov ebx, [edi + 0804h] ;0000 1000 0000 0100 mov ecx, [edi + 1000h] ;0001 0000 0000 0000 mov edx, [edi + 5008h] ;0101 0000 0000 1000 mov esi, [edi + 583ch] ;0101 1000 0011 1100 sub ebp, 1 jnz again 可以看出上面给的5地址中的数据会被载入到同一个块中，因为它们的位6~位10是相同的，但这段代码的执行性能很差，因为当我们读mov esi, [edi + 583ch]时，4个缓存行已经占满了，没有多余的空间来存放数据[edi + 583ch]，这势必要换出之前的4个缓存行之一。由最近最少使用原则，[edi]所在的缓存行会被换出，用[edi+5800h]到[edi+583fh]的地址段数据填充(每次载入一个缓存行即64字节，且64字节对齐)。接下来，循环到mov eax, [edi]时，因为[edi]所在的数据已被换出，这样又将[edi + 0804h] 所在的缓存行换出，填上[edi]中的数据，依次，这样每次都会换进换出。如何修改以提高性能呢，可以看出如果将上面的语句mov esi, [edi + 583ch]改成 MOV ESI,[EDI + 5840H] ;0101 1000 0100 0000 这样此地址的位6~位10与上面的四个地址均不同，这样它们不会争用同一个缓存块。循行执行就不会换进换出了。

liangbch · 发表于 2011-11-18 10:38:42

google/baidu 互联网发现，在中国，关注汇编优化的人不多，不过偶尔也能发现一些，推荐喜欢优化技术的朋友看看云风的书《游戏之旅--我的编程感悟》，电子版可从http://ishare.iask.sina.com.cn/f/5552521.html 下载

G-Spider · 发表于 2011-11-18 11:13:09

云风早期翻译过部分Agner Fog 的优化文档。谢谢LS兄台的分享，这书里面关于循环展开我还是很赞同的。

G-Spider · 发表于 2011-11-18 14:13:26

Nehalem结构常用指令的端口分布。

以上表看出，Nehalem结构每核包含三个执行端口: Port 0 Port 1 Port 5 三个数据传送端口: Port 2 loads Port 3 Store address Port 4 Store data 对于执行端口，某类指令可并发执行，比如Integer ALU等，在Port 0,1,5均可执行，像mov r,r 一个周期可完成3条。而像LEA只能在Port 1上执行。合理的选取指令可提高并发性。从Agner Fog 的instruction_tables.pdf上更细致的了解这种特性。

new_mathee · 发表于 2012-4-21 13:24:20

学习了，这样技巧将来可能用到。

liangbch · 发表于 2013-3-22 14:20:28

回17楼：对memcpy来说，地址对齐对性能的影响远比我们想象的要大。这里的地址对齐是指目标地址和源地址的差除以64的余数。之所以求64的余数，是因为一般的CPU其L2 cahce中block的大小为64字节。为了简化起见，假设src和dst都是4字节对齐的，则(dst-src)%64的值总共有16种情况，他们为 0,4,8,12,16,20,24,28,32,36,40,44,48,52,56,60. 测试一下你的这几个函数，看看不同的内存对齐对性能的的影响。为了简单起见，我们定义如下测试条件。 1. src,dst 为内存地址，都为4字节对齐。 2 复制的字节数为4的整数倍，就是说需要复制 len个DWORD从src到dst 3. len*sizeof(DWORD)*2<= L2 cache size.

账号		自动登录	找回密码
密码			欢迎注册

[原创] 【日积月累】优化小技巧

评分

评分