?? csdn_文檔中心_內存拷貝的優化方法.htm
字號:
<TD align=middle width=500></TD></TR></TBODY></TABLE><!--文章說明信息結束//-->
<TABLE border=0 width=600>
<TBODY>
<TR>
<TD align=left><BR>
<P><A
href="http://www.blogcn.com/blog/cool/main.asp?uid=flier_lu&id=1577430">http://www.blogcn.com/blog/cool/main.asp?uid=flier_lu&id=1577430</A><BR><A
href="http://www.blogcn.com/blog/cool/main.asp?uid=flier_lu&id=1577440">http://www.blogcn.com/blog/cool/main.asp?uid=flier_lu&id=1577440</A></P>
<P>在復雜的底層網絡程序中，內存拷貝、字符串比較和搜索操作很容易成為性能瓶頸所在。編譯器自帶的此類函數雖然做了一些通用性的優化工作，但因為在使用指令集方面受到兼容性的約束，遠遠沒有達到最大限度利用硬件能力的地步。而通過針對特定硬件平臺的優化，可以大大提高此類操作的性能。下面我將以P4平臺下內存拷貝操作為例，根據AMD提供的一份優化文檔中的例子，簡要介紹一下如何通過特定指令集，優化內存帶寬的使用。雖然因為硬件限制沒有達到AMD文檔中所說memcpy函數300%的性能提升，但在我機器上實測也有%175-%200的明顯性能提升（此數據可能根據機器情況不同）。<BR><BR><A
href="http://cdrom.amd.com/devconn/events/gdc_2002_amd.pdf"
target=_blank><FONT color=#0000ff>Optimizing Memory
Bandwidth</FONT></A> from <A href="http://www.amd.com/"
target=_blank>AMD</A><BR><BR>按照眾所周知的“摩爾”定律，CPU的運算速度每18個月翻一翻，但與此同時內存和外存（硬盤）的速度并無法達到同步增長。這就造成高速CPU與相對低速的內存和外設之間的不同步發展，成為很多程序的瓶頸所在。而如何最大限度提升對現有硬件的利用程度，是算法以下層面優化的主要途徑。對內存拷貝操作來說，了解和合理使用Cache是最關鍵的一點。為追求性能，我們將以犧牲兼容性為代價，因此以下討論和代碼都以P4及以上級別CPU為主，AMD芯片雖然實現上有所區別，但在指令集和整體結構上相同。<BR><BR>首先我們來看一個最簡單的memcpy的匯編實現：<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>;<BR>; Flier Lu
(flier@nsfocus.com)<BR>;<BR>; nasmw.exe -f win32
fastmemcpy.asm -o fastmemcpy.obj<BR>;<BR>; extern "C"
{<BR>; extern void fast_memcpy1(void *dst, const void
*src, size_t size);<BR>; }<BR>;<BR>cpu p4<BR><BR>segment
.text use32<BR><BR>global _fast_memcpy1<BR><BR>%define
param esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy1:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len]<BR><BR>rep
movsb<BR><BR>pop edi<BR>pop
esi<BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>這里我為了代碼可移植性，使用的是<A href="http://nasm.sourceforge.net/"
target=_blank><FONT color=#0000ff>NASM</FONT></A>格式的匯編代碼。<A
href="http://nasm.sourceforge.net/" target=_blank><FONT
color=#0000ff>NASM</FONT></A>是一個非常出色的開源匯編編譯器，支持各種平臺和中間格式，被開源項目廣泛使用，這樣可以避免同時使用
VC 的嵌入式匯編和 GCC 中麻煩的 unix 風格 AT&T 格式匯編 :P<BR><BR>代碼初始的cpu
p4定義使用p4指令集，因為后面的很多優化工作使用了P4指令集和相關特性；接著的segment .text
use32定義此代碼在32位代碼段；然后global定義標簽_fast_memcpy1為全局符號，使得C++代碼中可以LINK其.obj后訪問此代碼；最后%define定義多個宏，用于訪問函數參數。<BR><BR>在C++中只需要定義fast_memcpy1函數格式并鏈接nasm編譯生成的.obj文件即可。NASM編譯時
-f 參數指定生成中間文件格式為 MS 的 32 位 COFF 格式，-o
參數指定輸出文件名。<BR><BR>上面這段代碼非常簡單，適合小內存塊的快速拷貝。實際上VC編譯器在處理小內存拷貝時，會自動根據情況使用
rep movsb 直接替換 memcpy 函數，通過忽略函數調用和堆棧操作，優化代碼長度和性能。<BR><BR>不過在 32 位的
x86 架構下，完全沒有必要逐字節進行操作，使用 movsd 替換 movsb 是必然的選擇。<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy2<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy2:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len]<BR>shr ecx, 2 ;
convert to DWORD count<BR><BR>rep movsd<BR><BR>pop
edi<BR>pop
esi<BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>為了展示方便，這里假設源和目標內存塊本身長度都是64字節的整數倍，并且已經4K頁對齊。前者保證單條指令不會出現跨CACHE行訪問的情況；后者保證測試速度時不會因為跨頁操作影響測試結果。等會分析CACHE時再詳細解釋為什么要做這種假設。<BR><BR>不過因為現代CPU大多使用了很長的指令流水線，多條指令并行工作往往比一條指令效率更高，因此
AMD 文檔中給出了這樣的優化：<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy3<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy3:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len]<BR>shr ecx, 2 ;
convert to DWORD count<BR><BR>.copyloop:<BR>mov eax, dword
[esi]<BR>mov dword [edi], eax<BR><BR>add esi, 4<BR>add
edi, 4<BR><BR>dec ecx<BR>jnz .copyloop<BR><BR>pop
edi<BR>pop
esi<BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>標簽.copyloop中那段循環實際上完成跟rep
movsd指令完全相同的工作，但是因為是多條指令，理論上CPU指令流水線可以并行處理之。故而在AMD的文檔中指出能有1.5%的性能提高，不過就我實測效果不太明顯。相對而言，當年從486向pentium架構遷移時，這兩種方式的區別非常明顯。記得Delphi
3還是4中就只是通過做這一種優化，其字符串處理性能就有較大提升。而目前主流CPU廠商，實際上都是通過微代碼技術，內核中使用RISC微指令模擬CISC指令集，因此現在效果并不明顯。<BR><BR>然后，可以通過循環展開的優化策略，增加每次處理數據量并減少循環次數，達到性能提升目的。<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy4<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy4:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len]<BR>shr ecx, 4 ;
convert to 16-byte size count<BR><BR>.copyloop:<BR>mov
eax, dword [esi]<BR>mov dword [edi], eax<BR><BR>mov ebx,
dword [esi+4]<BR>mov dword [edi+4], ebx<BR><BR>mov eax,
dword [esi+8]<BR>mov dword [edi+8], eax<BR><BR>mov ebx,
dword [esi+12]<BR>mov dword [edi+12], ebx<BR><BR>add esi,
16<BR>add edi, 16<BR><BR>dec ecx<BR>jnz
.copyloop<BR><BR>pop edi<BR>pop
esi<BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>但這種操作就 AMD 文檔上評測反而有 %1.5
性能降低，呵呵。其自己的說法是需要將讀取內存和寫入內存的操作分組，以使CPU可以一次性搞定。改稱以下分組操作就可以比_fast_memcpy3提高3%
-_-b<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy5<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy5:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len]<BR>shr ecx, 4 ;
convert to 16-byte size count<BR><BR>.copyloop:<BR>mov
eax, dword [esi]<BR>mov ebx, dword [esi+4]<BR>mov dword
[edi], eax<BR>mov dword [edi+4], ebx<BR><BR>mov eax, dword
[esi+8]<BR>mov ebx, dword [esi+12]<BR>mov dword [edi+8],
eax<BR>mov dword [edi+12], ebx<BR><BR>add esi, 16<BR>add
edi, 16<BR><BR>dec ecx<BR>jnz .copyloop<BR><BR>pop
edi<BR>pop
esi<BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>可惜我在P4上實在測不出什么區別，呵呵，大概P4和AMD實現流水線的思路有細微的出入吧
:D<BR><BR>既然進行循環展開，為什么不干脆多展開一些呢？雖然x86下面通用寄存器只有那么幾個，但是現在有MMX啊，呵呵，大把的寄存器啊
:D
改稱使用MMX寄存器后，一次載入/寫入操作可以處理64字節的數據，呵呵，比_fast_memcpy5可以再有7%的性能提升。<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy6<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy6:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len] ; number of QWORDS
(8 bytes) assumes len / CACHEBLOCK is an integer<BR>shr
ecx, 3<BR><BR>lea esi, [esi+ecx*8] ; end of source<BR>lea
edi, [edi+ecx*8] ; end of destination<BR>neg ecx ; use a
negative offset as a combo
pointer-and-loop-counter<BR><BR>.copyloop:<BR>movq mm0,
qword [esi+ecx*8]<BR>movq mm1, qword [esi+ecx*8+8]<BR>movq
mm2, qword [esi+ecx*8+16]<BR>movq mm3, qword
[esi+ecx*8+24]<BR>movq mm4, qword [esi+ecx*8+32]<BR>movq
mm5, qword [esi+ecx*8+40]<BR>movq mm6, qword
[esi+ecx*8+48]<BR>movq mm7, qword
[esi+ecx*8+56]<BR><BR>movq qword [edi+ecx*8], mm0<BR>movq
qword [edi+ecx*8+8], mm1<BR>movq qword [edi+ecx*8+16],
mm2<BR>movq qword [edi+ecx*8+24], mm3<BR>movq qword
[edi+ecx*8+32], mm4<BR>movq qword [edi+ecx*8+40],
mm5<BR>movq qword [edi+ecx*8+48], mm6<BR>movq qword
[edi+ecx*8+56], mm7<BR><BR>add ecx, 8<BR>jnz
.copyloop<BR><BR>emms<BR><BR>pop edi<BR>pop
esi<BR><BR>ret<BR></BLOCKQUOTE></TD></TR></TBODY></TABLE></BLOCKQUOTE>
<P><BR><BR>優化到這個份上，常規的優化手段基本上已經用盡，需要動用非常手段了，呵呵。<BR>讓我們回過頭來看看P4架構下的Cache結構。<BR><BR><A
href="http://developer.intel.com/design/pentium4/manuals/253668.htm"
target=_blank>The IA-32 Intel Architecture Software Developer's
Manual, Volume 3: System Programming
Guide</A><BR><BR>Intel的系統變成手冊中第十章介紹了IA32架構下的內存緩存控制。因為CPU速度和內存速度的巨大差距，CPU廠商通過在CPU中內置和外置多級緩存提高頻繁使用數據的訪問速度。一般來說，在CPU和內存之間存在L1,
L2和L3三級緩存(還有幾種TLB緩存在此不涉及)，每級緩存的速度有一個數量級左右的差別，容量也有較大差別(實際上跟$有關，呵呵)，而L1緩存更是細分為指令緩存和數據緩存，用于不同的目的。就P4和Xeon的處理器來說，L1指令緩存由Trace
Cache取代，內置在NetBust微架構中；L1數據緩存和L2緩存則封裝在CPU中，根據CPU檔次不同，分別在8-16K和256-512K之間；而L3緩存只在Xeon處理器中實現，也是封裝在CPU中，512K-1M左右。<BR>可以通過查看CPU信息的軟件如<A
href="http://www.pcanalyser.com/eng/" target=_blank><FONT
color=#0000ff>CPUInfo</FONT></A>查看當前機器的緩存信息，如我的系統為：<BR>P4 1.7G, 8K
L1 Code Cache, 12K L1 Data Cache, 256K L2
Cache。<BR><BR>而緩存在實現上是若干行(slot or
line)組成的，每行對應內存中的一個地址上的連續數據，由高速緩存管理器控制讀寫中的數據載入和命中。其原理這里不多羅嗦，有興趣的朋友可以自行查看Intel手冊。需要知道的就是每個slot的長度在P4以前是32字節，P4開始改成64字節。而對緩存行的操作都是完整進行的，哪怕只讀一個字節也需要將整個緩存行(64字節)全部載入，后面的優化很大程度上基于這些原理。<BR><BR>就緩存的工作模式來說，P4支持的有六種之多，這里就不一一介紹了。對我們優化有影響的，實際上就是寫內存時緩存的表現。最常見的WT(Write-through)寫通模式在寫數據到內存的同時更新數據到緩存中；而WB(Write-back)寫回模式，則直接寫到緩存中，暫不進行較慢的內存讀寫。這兩種模式在操作頻繁操作(每秒百萬次這個級別)的內存變量處理上有較大性能差別。例如通過編寫驅動模塊操作MTRR強行打開WB模式，在Linux的網卡驅動中曾收到不錯的效果，但對內存復制的優化幫助不大，因為我們需要的是完全跳過對緩存的操作，無論是緩存定位、載入還是寫入。<BR><BR>好在P4提供了MOVNTQ指令，使用WC(Write-combining)模式，跳過緩存直接寫內存。因為我們的寫內存操作是純粹的寫，寫入的數據一定時間內根本不會被使用，無論使用WT還是WB模式，都會有冗余的緩存操作。優化代碼如下：<BR></P>
<BLOCKQUOTE>
<TABLE border=0 cellPadding=6 cellSpacing=0 class=ubb_quote
width="100%">
<TBODY>
<TR>
<TD><B>以下為引用：</B>
<BLOCKQUOTE><BR>global _fast_memcpy7<BR><BR>%define param
esp+8+4<BR>%define src param+0<BR>%define dst
param+4<BR>%define len
param+8<BR><BR>_fast_memcpy7:<BR>push esi<BR>push
edi<BR><BR>mov esi, [src] ; source array<BR>mov edi, [dst]
; destination array<BR>mov ecx, [len] ; number of QWORDS
(8 bytes) assumes len / CACHEBLOCK is an integer<BR>shr
ecx, 3<BR><BR>lea esi, [esi+ecx*8] ; end of source<BR>lea
edi, [edi+ecx*8] ; end of destination<BR>neg ecx ; use a
negative offset as a combo
pointer-and-loop-counter<BR><BR>.copyloop:<BR>movq mm0,
qword [esi+ecx*8]<BR>movq mm1, qword [esi+ecx*8+8]<BR>movq
mm2, qword [esi+ecx*8+16]<BR>movq mm3, qword
[esi+ecx*8+24]<BR>movq mm4, qword [esi+ecx*8+32]<BR>movq
mm5, qword [esi+ecx*8+40]<BR>movq mm6, qword
[esi+ecx*8+48]<BR>movq mm7, qword
[esi+ecx*8+56]<BR><BR>movntq qword [edi+ecx*8],
mm0<BR>movntq qword [edi+ecx*8+8], mm1<BR>movntq qword
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -