以下有三個版本的memcpy，對于版本3，很多人都很熟悉，它很經(jīng)典，很多人面試都寫這個，可是我不得不說一句，對于類似的問題，最好的回答有兩個：一是調(diào)用c庫，二是使用匯編。用這一類的問題來考察應(yīng)聘者的c語言能力，真的很菜！如果真的要考察c語言能力，還不如給幾個if，switch-case，for語句呢。
版本1.linux內(nèi)核中的實現(xiàn)，其實glibc也是如此實現(xiàn)的，省略了不少內(nèi)容，真正的實現(xiàn)很巧妙，將n個字節(jié)分為了三部分(前導(dǎo)字節(jié)-對齊到頁面+頁面+后續(xù)字節(jié)-頁面對齊后的游離字節(jié))進行分塊拷貝(linux內(nèi)核是絕對不會賣弄c語言的，基本的底層函數(shù)最終為了高效大多數(shù)都用匯編)：
char *memcpy1(char *to, char *from, size_t n)
{
??? long esi, edi;
??? int ecx;
??? esi = (long)from;
??? edi = (long)to;
??? asm volatile("rep ; movsl"
??? ??? : "=&c" (ecx), "=&D" (edi), "=&S" (esi)
??? ??? : "0" (n / 4), "1" (edi), "2" (esi)
??? ??? : "memory"
??? ??? );
??? return to;
}
版本2.memcpy2為經(jīng)典的C面試者寫法：
char *memcpy2(char *dest, char *src, size_t n)
{
??? ??? int i = 0;
??? while (i < n)
??? {
??? ??? dest[i] = src[i];
??? ??? i ++;
??? }
??? return dest;

}
版本3.glibc的寫法：
...
僅僅這幾個memcpy版本，如何確定哪個更高效呢？以下是一個測試的例子，請看例子1。
例子1：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define COUNTS 6000000

long long getcyclenow()
{
??? unsigned int h, l;
??? long long bs, cc;
??? asm("rdtsc /n/t");
??? asm("movl %%eax, %0/n/t":"=g"(l));
??? asm("movl %%edx, %0/n/t":"=g"(h));
??? bs = h;
??? cc = (bs << 32)|l;
??? return cc;
}
int main(int argc, char **argv)
{
??? time_t st0, st1, st2, st3;
??? long long l0, l1, l2, l3;
??? int i = 0;
??? char *src = (char *)calloc(1, 109);
??? strcpy(src, "iiiiabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz");
??? char *dest0 = (char *)calloc(1, 109);
??? char *dest1 = (char *)calloc(1, 109);
??? char *dest2 = (char *)calloc(1, 109);

??? l0 = getcyclenow();???
??? dest0 = memcpy(dest0, src, 108);
??? l1 = getcyclenow();???
??? dest2 = memcpy2(dest2, src, 108);
??? l2 = getcyclenow();???
??? dest1 = memcpy1(dest1, src, 108);
??? l3 = getcyclenow();???
??? printf("%X/t%X/t%X/n", l1-l0, l2-l1, l3-l2);
???
??? memset(dest0, 0, 109);
??? memset(dest1, 0, 109);
??? memset(dest2, 0, 109);

??? st0 = time(NULL);
??? for (i = 0; i < COUNTS; i++)
??? ??? dest0 = memcpy(dest0, src, 108);
??? st1 = time(NULL);
??? for (i = 0; i < COUNTS; i++)
??? ??? dest2 = memcpy2(dest2, src, 108);
??? st2 = time(NULL);
??? for (i = 0; i < COUNTS; i++)
??? ??? dest1 = memcpy1(dest1, src, 108);
??? st3 = time(NULL);
??? printf("t0:%f, t1:%f, %f/n", difftime(st1, st0), difftime(st2, st1), difftime(st3, st2));

/*
??? memset(dest0, 0, 109);
??? memset(dest1, 0, 109);
??? memset(dest2, 0, 109);
???
??? l0 = getcyclenow();???
??? dest0 = memcpy(dest0, src, 108);
??? l1 = getcyclenow();???
??? dest2 = memcpy2(dest2, src, 108);
??? l2 = getcyclenow();???
??? dest1 = memcpy1(dest1, src, 108);
??? l3 = getcyclenow();???
??? printf("%X/t%X/t%X/n", l1-l0, l2-l1, l3-l2);
*/
??? return 0;
}
執(zhí)行這個程序，看第一個printf輸出，發(fā)現(xiàn)memcpy是最慢的，而匯編寫的memcpy1是最快的，而經(jīng)典的面試寫法memcpy2位居中間，可是看c庫的memcpy源碼或者其反匯編代碼，它也是使用了rep ; movsX指令，那為什么它慢呢？考慮到了數(shù)據(jù)緩存問題，將memcpy和memcpy1以及memcpy2的調(diào)用互換了位置，仍然是c庫的memcpy最慢，這就給了很多涉業(yè)不久的畢業(yè)生十足的理由繼續(xù)往筆試卷上寫memcpy2之類的。附帶一句，后面的for循環(huán)的COUNTS次測速為了得到一個統(tǒng)計值，這次發(fā)現(xiàn)memcpy2最慢，memcpy比memcpy1慢一點點，但是都比memcpy2快很多，這名顯與通過rdtsc測試出來的結(jié)果不對應(yīng)，于是肯定哪里出了問題。
???? 實際上這是cpu指令預(yù)取和指令cache以及缺頁引起的，而和c庫以及c庫實現(xiàn)的memcpy沒有關(guān)系，要知道c庫大家都在用，不會有如此明顯的性能問題的，再者說，隨便懂點cpu知識和匯編的人都知道m(xù)emcpy2是最不可取的，因為它里面有大量的條件判斷和條件跳轉(zhuǎn)，這對于cpu的流水線是很不利的，并且通過c語言語義上語句實現(xiàn)拷貝增加了指令數(shù)，從而也就是增加了執(zhí)行時間，x86處理器猛就猛在其是從cisc演變過來的，包含了大量的指令，于是movsX加repeat前綴肯定是不二的選擇啦。當(dāng)?shù)谝淮握{(diào)用memcpy的時候，cpu不得不從其所在的“地址”處將指令取到cpu，然后就cache到那里了，除非越來越多的別的指令將它沖掉(flush)，它就一直在那里。
???? 另外tlb也是一個重要的因素，tlb緩存了虛擬地址和物理地址的映射，在cpu用虛擬地址訪存時，需要通過mmu得到物理地址，tlb可以緩存這個映射從而以后不再需要查詢頁表，直接從tlb中得到物理地址。對于指令的尋址，cpu也是按照虛擬地址來的，第一次訪問時要完全查找頁表，并且還可能缺頁，接下來從最慢的磁盤將數(shù)據(jù)讀到次慢的內(nèi)存，然后將物理地址-虛擬地址的映射讀入tlb，指令進入icache，因此接下來的調(diào)用就會很快了。有個問題需要解釋，c庫的函數(shù)不是一直cache在內(nèi)存中的嗎？是的，但是第一它沒有cache在處理器中，第二它雖然緩存在了內(nèi)存，但是對于當(dāng)前task卻不一定建立了頁表項，而處理器dcache/icache(數(shù)據(jù)緩存/指令緩存)是通過物理地址尋址的(而tlb是虛擬地址尋址的)，因此會導(dǎo)致兩個不命中：cpu cache(icache/dcache/tlb)不命中和頁表項不命中，然后發(fā)生缺頁，內(nèi)核準(zhǔn)備讀磁盤之前首先要看一下它是否在內(nèi)存中，如果在的話直接建立頁表項映射就可以了，對于c庫的函數(shù)，一般是在內(nèi)存的(前提是內(nèi)存足夠大)，因此第一次調(diào)用c庫函數(shù)只會有缺頁-建立頁表項的開銷，而大多數(shù)情況下不會有讀磁盤的開銷。
???? 下面通過例子2分析問題到底出在哪里！
例子2：
#include <stdlib.h>
#include <stdio.h>
#define ALIGN? 0X800
int test()
{
??? return 1;
}
void __attribute__ ((aligned (ALIGN))) stub()
{
??? return;
}
long long getcycle()
{
??? unsigned int h, l;
??? long long bs, cc;
??? asm("rdtsc /n/t");
??? asm("movl %%eax, %0/n/t":"=g"(l));
??? asm("movl %%edx, %0/n/t":"=g"(h));
??? bs = h;
??? cc = (bs << 32)|l;
??? return cc;
}

int main(int argc, char **argv)
{
??? long long t1, t2, t3, t4;
??? printf("%p/t%p/t%p/n", test, stub, main);
??? t1 = getcycle();
??? test();
??? t2 = getcycle();
??? test();
??? t3 = getcycle();
??? test();
??? t4 = getcycle();
??? printf("%X/t%X/t%X/n", t2-t1, t3-t2, t4-t3);
??? printf("%p/t%p/t%p/n", getcycle, test, main);
??? return 0;
}
stub函數(shù)設(shè)置了aligned這個attribute，為了在test函數(shù)和main之間制造一點“距離”(用nop指令填充)，這樣的話，第一，cpu的指令預(yù)取(instruction prefetch)就取不到了，畢竟cpu的指令緩存是有限的；第二，執(zhí)行main之前main函數(shù)一定要映射進頁表項，由于mmu按頁大小(4096字節(jié))映射，拉開一定距離就不會讓test也映射進入，在下一個例子中我們會調(diào)整這個距離來表明缺頁對執(zhí)行性能的影響。控制ALIGN的值，使得test函數(shù)和main的距離變化，當(dāng)ALIGN很小的時候，test和main離的很近(小于一個頁面且在同一頁面)，cpu可能會根據(jù)局部性原理加載main的時候?qū)est的指令取入cache，并且由于test和main在一個頁面，test也會進入內(nèi)存且建立頁表映射，從而tlb中也會有test的物理地址，然而如果ALIGN很大，比如是0x10000，這樣test和main很遠，cpu既取不到test的指令，又不會建立頁表映射，在第一次執(zhí)行test的時候，會缺頁，會花費很多時間，以下討論不再考慮cpu預(yù)取，僅考慮缺頁和cpu的icache，也不再考慮tlb，因為在訪問一組連續(xù)地址(頁面)的第一個字節(jié)時，地址映射信息就會進入tlb，以下一個頁面內(nèi)的連續(xù)訪問幾乎都會命中，1個字節(jié)帶來的優(yōu)勢對比一個頁面字節(jié)來講，效果不容易表現(xiàn)出來(測試不容易)。因此在ALIGN為0x10000的時候，執(zhí)行結(jié)果如下：
b36???? 3f????? 38
0x450017??????? 0x420006??????? 0x450045
第一次和第二次調(diào)用test足有40多倍的延遲。由于指令已經(jīng)cache了，第二次和第三次執(zhí)行就很快了。為了證明是缺頁的的影響很大，把getcycle的定義放到test之前：
long long getcycle()
{
??? ...
}
int test()
{
??? return 1;
}
void __attribute__ ((aligned (ALIGN))) stub()
{
??? return;
}
在執(zhí)行test之前要先執(zhí)行一個t1 = getcycle();，該調(diào)用會觸發(fā)getcycle缺頁，由于getcycle和test在同一頁面，也就是說會建立test的頁表映射，執(zhí)行結(jié)果如下：
3f????? 38????? 3f
0x420000??????? 0x420034??????? 0x450017
雖然main和test離的仍然很遠，然而getcycle和test很近，在調(diào)用getcycle的時候會建立頁表項，因此速度加快很多，以后就從指令緩存icache中取指令，為了再次證實這個事情且不影響getcycle的執(zhí)行，將getcycle放回原位，然后在test之前放一個stub0，然后在第一個調(diào)用getcycle之前調(diào)用stub0，然后看結(jié)果，三次執(zhí)行test的時間仍然很接近。看一下linux的do_page_fault的代碼，的確很多，這些都要算在t2-t1中，怪不得缺頁情形下多了那么多的時間。
???? 因此前一個例子中c庫的memcpy慢的原因就找到了，將例子1中main函數(shù)最后的注釋放開，再次編譯執(zhí)行(-O0參數(shù)，不優(yōu)化，前面的例子2也要這樣編譯)，發(fā)現(xiàn)memcpy1仍然是最快的，而c庫的memcpy位居第二，和memcpy1相差不多，而面試版本的memcpy2最慢。接下來看例子3，展示缺頁的影響。
例子3：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define ALIGN_test? 0X800
#define ALIGN_main? 0X800

long long getcycle()
{
??????? unsigned int h, l;
??????? long long bs, cc;
??????? asm("rdtsc /n/t");
??????? asm("movl %%eax, %0/n/t":"=g"(l));
??????? asm("movl %%edx, %0/n/t":"=g"(h));
??????? bs = h;
??????? cc = (bs << 32)|l;
??????? return cc;
}
void? __attribute__ ((aligned (0x10000))) stub0()? //為了讓test和main分布在兩個頁面中
{
??????? return;
}
int __attribute__ ((aligned (ALIGN_test)))? test(char *buf)
{??? //增加一些代碼，讓它像真正的函數(shù)。要使用-O0編譯
??????? int i = 2, j=3;

??????? if (buf[0] < i)
??????????????? j += 3;
??????? for (j; j < 10; i += j+buf[i])
??????????????? j = buf[j];
??????? if (buf[0] < i)
??????????????? j += 3;
??????? for (j; j < 10; i += j+buf[i])
??????????????? j = buf[j];
??????? if (buf[0] < i)
??????????????? j += 3;
??????? for (j; j < 10; i += j+buf[i])
??????????????? j = buf[j];

??????? return i*j;
};
int __attribute__ ((aligned (ALIGN_main))) main(int argc, char **argv)
{
??????? long long t1, t2, t3, t4;
??????? char b[25] = {0};

??????? t1 = getcycle();
??????? memcpy(b, "ddddd", 5);
??????? t2 = getcycle();
??????? memcpy(b, "ddddd", 5);
??????? t3 = getcycle();
??????? memcpy(b, "ddddd", 5);
??????? t4 = getcycle();
??????? printf("%llx/t%llx/t%llx/n", t2-t1, t3-t2, t4-t3);

??????? t1 = getcycle();
??????? test("ddddd/n");
??????? t2 = getcycle();
??????? test("ddddd/n");
??????? t3 = getcycle();
??????? test("ddddd/n");
??????? t4 = getcycle();
??????? printf("%llx/t%llx/t%llx/n", t2-t1, t3-t2, t4-t3);
??????? printf("%p/t%p/t%p/n", getcycle, printf2, main);
}
ALIGN_main和ALIGN_test均為0x800的情況下，上述的代碼將把test和main分布在兩個頁面中，間隔0x800，執(zhí)行main時并不會為test建立映射，因此第一次執(zhí)行test函數(shù)時將會慢很多，如果將ALIGN_main和ALIGN_test分別調(diào)整為0x800和0x1000，那么test和main就會分布在同一個頁面，第一次執(zhí)行test明顯會快很多，這就是缺頁帶來的影響，可見頁面調(diào)入實在太耗時了。在結(jié)束rdtsc指令的第一個影響因素之前再看一個例子，理解一下共享庫的作用。
例子4：
share.h:
int test1();
share.c
int test1()
{
??????? return 3;
}
test1.c:
#include <stdlib.h>
#include <stdio.h>
#include "share.h"
long long getcycle()
{
??????? unsigned int h, l;
??????? long long bs, cc;
??????? long long interval, start, end;
??????? asm("rdtsc /n/t");
??????? asm("movl %%eax, %0/n/t":"=g"(l));
??????? asm("movl %%edx, %0/n/t":"=g"(h));
??????? bs = h;
??????? cc = (bs << 32)|l;
??????? return cc;
}
int main(int argc, char **argv)
{
??????? time_t st0, st1, st2, st3;
??????? long long l0, l1, l2, l3;

??????? l0 = getcycle();
??????? test1();
??????? l1 = getcycle();
??????? test1();
??????? l2 = getcycle();
??????? test1();
??????? l3 = getcycle();
??????? printf("%llx/t%llx/t%llx/n", l1-l0, l2-l1, l3-l2);

}
test2.c:
#include <stdlib.h>
#include <stdio.h>
#include "shar.h"
int main(int argc, char **argv)
{
??????? while(1) {
??????????????? test1();
??????? }
}
編譯：
gcc -fPIC -shared share.c -o libshare.so -O0
gcc test1.c -o test1 -L. -lshare
gcc test2.c -o test2 -L. -lshare
1.連續(xù)執(zhí)行test1：
28b???? 46????? 3f
2.執(zhí)行sysctl -w vm.drop_caches=3后執(zhí)行一次test1：
391???? 54????? 46
3.在另一tty上執(zhí)行test2，然后執(zhí)行test1：
29a???? 46????? 38
4.在另一tty上執(zhí)行test2，執(zhí)行sysctl -w vm.drop_caches=3后執(zhí)行test1：
2c8???? 46????? 38
測試1說明第一次執(zhí)行test1函數(shù)時缺頁，建立頁表映射消耗大量時間，連續(xù)執(zhí)行后即使test1退出linux也可能將so緩存在了內(nèi)存，不再需要讀磁盤，因此得到了一個大致0x28b的數(shù)值，測試2由于刷新了文件緩存，缺頁時需要讀磁盤，時間消耗明顯增加，測試3和測試1不相上下，測試4并沒有重現(xiàn)測試2的噩夢，因此test2在循環(huán)執(zhí)行中，即使刷新了磁盤緩存，test2也會將libshare.so讀入磁盤，由于libshare.so是共享的，因此test1在第一次執(zhí)行test1函數(shù)時只需要建立頁面映射即可，不必再讀磁盤了，這就是共享庫的好處。
???? 知道了cache和缺頁帶來的影響，rdtsc就可以無憂得使用了嗎？不是這樣的！如果getcycle包圍的待測試代碼本身執(zhí)行時間過長或者導(dǎo)致了進程調(diào)度，那么兩個getcycle調(diào)用的差值并不是真正的執(zhí)行時間，比如：
t1 = getcycle();
test() //很長，可能會sleep
t2 = getcycle();
如此一來t2-t1可能會把其它進程執(zhí)行的時間都算上，因為rdtsc獲得的是cpu全局的嘀嗒信息，而我們需要測試的執(zhí)行時間是基于本進程的統(tǒng)計時間。因此實際上我們是不能信任rdtsc測試出來的結(jié)果的。哪一次在test()執(zhí)行過程中發(fā)生調(diào)度幾乎是用戶態(tài)決定不了的(除非設(shè)置實時進程優(yōu)先級并且沒有IO)。
總結(jié)：
1.編寫代碼時，主要的調(diào)用函數(shù)要盡量緊湊的放在一個頁面中，注意向物理頁面起始地址對齊，不要離的太遠，這樣可以提高執(zhí)行效率。
2.使用共享庫，雖然可能因此增加幾條指令(比如got機制的代價)，然而卻省去了很多缺頁時讀磁盤的開銷。
3.測量長函數(shù)執(zhí)行一次的時間，不要相信rdtsc，因此中間如果發(fā)生調(diào)度，別的進程時間也會計算進去，rdtsc是全局的。
4.挖掘機器的特性，在指令級別尋找辦法，不要太迷戀c語言。

轉(zhuǎn)載于:https://blog.51cto.com/dog250/1271087

總結(jié)

以上是生活随笔為你收集整理的从几个版本的memcpy的测速过程学习一点底层的东西的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。