找回密码
 欢迎注册
楼主: G-Spider

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

[复制链接]
 楼主| 发表于 2010-12-24 22:14:48 | 显示全部楼层
17# G-Spider
有bug 更正(精确拷贝到字节),顺便加上硬预取方式,对于小字节量拷贝用movsd过渡。
测试平台:
cpu-26661.PNG
测试32.1 MB文件存拷贝:
_fast_memcpy1 (movsd)
33 ms
_fast_memcpy9  (SSE 系列)
23 ms
_block_prefetch  (硬预取 block_size 8KB)
22 ms
代码:
  1. ;************************************************************
  2. ;-==-: fast_memcpyTest  By G-Spider @2010
  3. ;-==-: ml  /c /coff memcpyTest.asm  
  4. ;-==-: link /subsystem:console memcpyTest.obj
  5. ;************************************************************
  6. .686p
  7. .XMM

  8. .model flat,stdcall
  9. option casemap:none

  10. include windows.inc
  11. include user32.inc
  12. include kernel32.inc
  13. include msvcrt.inc

  14. includelib user32.lib
  15. includelib kernel32.lib  
  16. includelib msvcrt.lib

  17. BLOCK_SIZE     equ  8192

  18. .data
  19. dwlm            dd      1000 ;1000是毫秒为单位,1000000则是微秒为单位
  20. fmt             db      '计算用时:',0dh,0ah,0
  21. fmt1            db      '%6lld ms',0dh,0ah,0

  22. szFileName      db      'xinyu.avi',0    ;32,954KB   原文件
  23. szOutName       db      'output.avi',0   ;输出文件;

  24. ;szFileName      db     'test.png',0    ;63KB   请以微秒为单位 原文件
  25. ;szOutName       db     'output.png',0   ;输出文件

  26. szPause         db      'Pause',0

  27. .data?
  28. hHandle         dd      ?
  29. hHandle1        dd      ?
  30. lpInputBuf      dd      ?
  31. lpOutputBuf     dd      ?
  32. dwStrlen        dd      ?
  33. lpNumberOfBytes dd      ?

  34. dwOldProcessP   dd      ?
  35. dwOldThreadP    dd      ?


  36. ;-------------------------------------
  37. dqTickCounter1  dq      ?
  38. dqTickCounter2  dq      ?
  39. dqFreq          dq      ?
  40. dqTime          dq      ?

  41. .code
  42. ;*************************************
  43. _fast_memcpy1   proc lpdst,lpsrc,dwlen

  44.         ;%define param esp+8+4
  45.         ;%define src param+0
  46.         ;%define dst param+4
  47.         ;%define len param+8

  48.         mov esi, lpsrc  ; source array
  49.         mov edi, lpdst  ; destination array
  50.         mov ecx, dwlen
  51.         mov eax,ecx
  52.         and eax,3
  53.         shr ecx, 2      ; convert to DWORD count
  54.         test ecx,ecx
  55.         jz   A000
  56.         rep movsd
  57. A000:
  58.         test eax,eax
  59.         jz A001
  60.         mov ecx,eax
  61.         rep movsb
  62. A001:       
  63.         xor eax,eax
  64.         ret
  65. _fast_memcpy1   endp

  66. ;***************************************
  67. _fast_memcpy9  proc lpdst,lpsrc,dwlen
  68.         
  69.            mov esi, lpsrc        ;src pointer
  70.            mov edi, lpdst        ;dest pointer      
  71.            mov ebx, dwlen        ;ebx is our counter
  72.            mov ecx, ebx
  73.            and ecx, 07fh         ;剩余的<128字节
  74.            shr ebx, 7                ;divide by 128 (8 * 128bit registers)
  75.            
  76.            test ebx,ebx
  77.            jz  A000
  78.            
  79.        ALIGN 16               
  80.        loop_copy:      
  81.             prefetchnta 128[ESI]; SSE2 prefetch      
  82.             prefetchnta 160[ESI];      
  83.             prefetchnta 192[ESI];      
  84.             prefetchnta 224[ESI];
  85.                     
  86.             movdqa xmm0, 0[ESI]        ; move data from src to registers      
  87.             movdqa xmm1, 16[ESI];      
  88.             movdqa xmm2, 32[ESI];      
  89.             movdqa xmm3, 48[ESI];      
  90.             movdqa xmm4, 64[ESI];      
  91.             movdqa xmm5, 80[ESI];      
  92.             movdqa xmm6, 96[ESI];      
  93.             movdqa xmm7, 112[ESI];
  94.                     
  95.             movntdq 0[EDI], xmm0 ; move data from registers to dest      
  96.             movntdq 16[EDI], xmm1;      
  97.             movntdq 32[EDI], xmm2;      
  98.             movntdq 48[EDI], xmm3;      
  99.             movntdq 64[EDI], xmm4;      
  100.             movntdq 80[EDI], xmm5;      
  101.             movntdq 96[EDI], xmm6;      
  102.             movntdq 112[EDI], xmm7;        
  103.             add esi, 128;      
  104.             add edi, 128;      
  105.             dec ebx;        
  106.             jnz loop_copy; //loop please
  107.             sfence
  108.         align 16   
  109.         A000:       
  110.                 mov eax, ecx
  111.                 and eax, 3
  112.                           
  113.                 shr ecx, 2      ; co[local]1[/local]nvert to DWORD count
  114.                 test ecx,ecx
  115.                 jz short A001
  116.                 rep movsd
  117.         A001:
  118.                 test eax,eax
  119.                 jz   A002
  120.                 mov  ecx,eax
  121.                 rep  movsb
  122.                
  123.         A002:       
  124.                 xor eax,eax
  125.                 ret

  126. _fast_memcpy9   endp



  127. _block_prefetch   proc lpdst,lpsrc,dwlen

  128.         mov  edi, lpdst
  129.         mov  esi, lpsrc
  130.         mov  eax, dwlen
  131.         mov  edx, eax
  132.         and  eax, (BLOCK_SIZE-1) ;4096-1=0fffh ;8192-1=1fffh;16*1024-1=3fffh
  133.        
  134.         and  edx, 0ffffe000h     ;与 BLOCK_SIZE有关
  135.         test edx,edx
  136.         jz  A000

  137.         align 16
  138. main_loop:
  139.         xor ecx,ecx
  140.         align 16
  141. prefetch_loop:
  142.         movaps xmm0, [esi+ecx]
  143.         movaps xmm0, [esi+ecx+64]
  144.         add ecx,128
  145.         cmp ecx,BLOCK_SIZE
  146.         jne prefetch_loop
  147.        
  148.         xor ecx,ecx
  149.         align 16
  150.         cpy_loop:
  151.         movdqa xmm0,[esi+ecx]
  152.         movdqa xmm1,[esi+ecx+16]
  153.         movdqa xmm2,[esi+ecx+32]
  154.         movdqa xmm3,[esi+ecx+48]
  155.         movdqa xmm4,[esi+ecx+64]
  156.         movdqa xmm5,[esi+ecx+16+64]
  157.         movdqa xmm6,[esi+ecx+32+64]
  158.         movdqa xmm7,[esi+ecx+48+64]
  159.        
  160.         movntdq [edi+ecx],xmm0
  161.         movntdq [edi+ecx+16],xmm1
  162.         movntdq [edi+ecx+32],xmm2
  163.         movntdq [edi+ecx+48],xmm3
  164.         movntdq [edi+ecx+64],xmm4
  165.         movntdq [edi+ecx+80],xmm5
  166.         movntdq [edi+ecx+96],xmm6
  167.         movntdq [edi+ecx+112],xmm7
  168.         add ecx,128
  169.         cmp ecx,BLOCK_SIZE
  170.         jne cpy_loop
  171.        
  172.         add esi,ecx
  173.         add edi,ecx
  174.         sub edx,ecx
  175.         jnz main_loop
  176.        
  177.         sfence
  178. align 16       
  179. A000:       
  180.         mov ecx, eax
  181.         and eax, 3
  182.                   
  183.         shr ecx, 2      ; convert to DWORD count
  184.         test ecx,ecx
  185.         jz short A001
  186.         rep movsd
  187. A001:
  188.         test eax,eax
  189.         jz   A002
  190.         mov  ecx,eax
  191.         rep  movsb
  192.        
  193. A002:       
  194.         xor eax,eax
  195.         ret

  196. _block_prefetch endp

  197. ;*****************************************************
  198. start:
  199.         invoke  CreateFile,offset szFileName,GENERIC_READ,FILE_SHARE_READ,\
  200.                 NULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL
  201.         .if     eax == INVALID_HANDLE_VALUE
  202.                 invoke MessageBox,NULL,0,0,0
  203.         .endif
  204.         mov     hHandle,eax
  205.         
  206.         invoke  GetFileSize,eax,NULL
  207.         mov     dwStrlen,eax
  208.         add     eax,16
  209.         invoke  crt_malloc,eax
  210.         mov     lpInputBuf,eax
  211.         mov     edx,lpInputBuf
  212.         and     eax,0fh
  213.         jz      Good1
  214.         xor     eax,edx
  215.         add     eax,10h
  216.         mov     lpInputBuf,eax
  217.         
  218. Good1:

  219.         invoke  RtlZeroMemory,lpInputBuf,dwStrlen
  220.         invoke  ReadFile,hHandle,lpInputBuf,dwStrlen,offset lpNumberOfBytes,NULL
  221.         
  222.         mov     eax,dwStrlen
  223.         add     eax,16
  224.         invoke  crt_malloc,eax
  225.         mov     lpOutputBuf,eax
  226.         mov     edx,lpOutputBuf
  227.         and     eax,0fh
  228.         jz      Good2
  229.         xor     eax,edx
  230.         add     eax,10h
  231.         mov     lpOutputBuf,eax
  232. Good2:        
  233.         invoke  RtlZeroMemory,lpOutputBuf,dwStrlen

  234. ;----------------------------------------------------
  235.         invoke  crt_printf,offset fmt
  236.         mov     ecx,5   ;测试5次
  237. .while  ecx!=0
  238.         push  ecx
  239.         
  240.         invoke  GetCurrentProcess
  241.         invoke  GetPriorityClass,eax
  242.         mov     dwOldProcessP,eax
  243.         
  244.         invoke  GetCurrentThread
  245.         invoke  GetThreadPriority,eax
  246.         mov     dwOldThreadP,eax
  247.         
  248.         invoke  GetCurrentProcess
  249.         invoke  SetPriorityClass,eax,REALTIME_PRIORITY_CLASS
  250.         invoke  GetCurrentThread
  251.         invoke  SetThreadPriority,eax,THREAD_PRIORITY_TIME_CRITICAL
  252.         ;--------------------------------------------------
  253.         
  254.         invoke  QueryPerformanceCounter,addr dqTickCounter1
  255.         ;时间测试
  256.         ;invoke  _fast_memcpy1,lpOutputBuf,lpInputBuf,dwStrlen            
  257.         ;invoke  _fast_memcpy9,lpOutputBuf,lpInputBuf,dwStrlen
  258.         invoke  _block_prefetch,lpOutputBuf,lpInputBuf,dwStrlen
  259.         
  260.         ;测试结束
  261.         invoke  QueryPerformanceCounter,addr dqTickCounter2
  262.         invoke  QueryPerformanceFrequency,addr  dqFreq
  263.         mov     eax,dword ptr dqTickCounter1
  264.         mov     edx,dword ptr dqTickCounter1[4]      
  265.         sub     dword ptr dqTickCounter2,eax
  266.         sub     dword ptr dqTickCounter2[4],edx
  267.          
  268.         ;----------------------------------------------------   
  269.         ;优先级还原
  270.         invoke  GetCurrentThread
  271.         invoke  SetThreadPriority,eax,dwOldThreadP
  272.         
  273.         invoke  GetCurrentProcess
  274.         invoke  SetPriorityClass,eax, dwOldProcessP
  275.         
  276.             
  277.         finit
  278.         fild    dqFreq
  279.         fild    dqTickCounter2
  280.         fimul   dwlm
  281.         fdivr
  282.         fistp   dqTime  ;dqTime中的64位值就是时间间隔(以微秒为单位)
  283.         ;---------------------------------------------------
  284.             
  285.         invoke  crt_printf,offset fmt1,dqTime

  286.         pop      ecx
  287.         dec      ecx
  288. .endw
  289.         
  290.         ;输出copy文件        
  291.         invoke  CreateFile,offset szOutName,GENERIC_WRITE,FILE_SHARE_READ,\
  292.                 NULL,CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL
  293.         .if     eax == INVALID_HANDLE_VALUE
  294.                 invoke MessageBox,NULL,0,0,0
  295.         .endif
  296.         mov     hHandle1,eax
  297.         invoke  WriteFile,eax,lpOutputBuf,dwStrlen,offset lpNumberOfBytes,NULL
  298.         
  299.         invoke  CloseHandle,hHandle
  300.         invoke  CloseHandle,hHandle1
  301.         
  302.         invoke  crt_system,offset szPause
  303.         invoke ExitProcess,0

  304. end start
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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 &copy; 1996 - 2011. Last updated 2011-01-30.

当时一直说什么Cache怎么怎么的,也没有具体的测试一下,这次深入一点(对以上文档关于 Optimizing memory access部分的个人理解),也肯请高手指点。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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字节的间隙。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 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与上面的四个地址均不同,这样它们不会争用同一个缓存块。
    循行执行就不会换进换出了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-11-18 10:38:42 | 显示全部楼层
google/baidu 互联网发现,在中国,关注汇编优化的人不多,不过偶尔也能发现一些,推荐喜欢优化技术的朋友看看云风的书《游戏之旅--我的编程感悟》,电子版可从http://ishare.iask.sina.com.cn/f/5552521.html 下载

评分

参与人数 2威望 +2 贡献 +5 鲜花 +3 收起 理由
gxqcn + 3 + 3 感谢分享,此书不错!
G-Spider + 2 + 2 谢谢分享,他也算老前辈了。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-11-18 11:13:09 | 显示全部楼层
云风早期翻译过部分Agner Fog 的优化文档。谢谢LS兄台的分享,这书里面关于循环展开我还是很赞同的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2011-11-18 14:13:26 | 显示全部楼层
Nehalem结构常用指令的端口分布。
11.jpg
以上表看出,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上更细致的了解这种特性。
12.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2012-4-21 13:24:20 | 显示全部楼层
学习了,这样技巧将来可能用到。

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首贴奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 13:23 , Processed in 0.046856 second(s), 18 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表