特別鳴謝：

參考文章：
http://blog.csdn.net/zoucharming/article/details/49766155
http://www.cppblog.com/djxzh/archive/2011/10/27/159192.aspx
https://zhuanlan.zhihu.com/p/20037058
https://msdn.microsoft.com/it-it/library/szdcdfc2(v=vs.100).aspx
http://www.cnblogs.com/zyl910/archive/2012/10/22/simdsumfloat.html
http://www.cnblogs.com/tibetanmastiff/p/4394608.html

開發(fā)環(huán)境：

CPU: Inter(R) Core(TM) i3-2330M
操作系統(tǒng)： ubuntu 14.04 x86_64 GNU/Linux
編譯器： gcc 4.8.4
glibc版本： libc-2.19

sse介紹：

SSE的全稱是 Sreaming SIMD Extensions妖谴， 它是一組Intel CPU指令餐弱，用于像信號處理霹菊、科學計算或者3D圖形計算一樣的應用悦陋。其優(yōu)勢包括：更高分辨率的圖像瀏覽和處理贱田、高質量音頻忌栅、MPEG2視頻沸手、同時MPEG2加解密锄贼；語音識別占用更少CPU資源票灰；更高精度和更快響應速度。使用SSE指令集，主要是通過8個128-bit的寄存器：xmm0到xmm7 來完成的屑迂。在Linux下可以使用cat /proc/cpuinfo來查看CPU支持哪些指令集浸策。 SSE的指令集是X86架構CPU特有的，對于ARM架構惹盼、MIPS架構等CPU是不支持的庸汗，所以使用了SSE指令集的程序，是不具備可移植標準的逻锐。

ARM架構和X86架構有什么區(qū)別：

最大的區(qū)別就是ARM架構使用的RSIC(精簡指令集)夫晌，X86使用的是CSIC(復雜指令集)，ARM架構的CPU一般是用于低功耗領域昧诱，在這個領域就是NO.1，如手機所袁、平板盏档、工控領域，嵌入式行業(yè)燥爷。X86架構的CPU蜈亩，功耗比較高，但是計算性能強勁前翎。一般用于個人PC稚配、服務器、需要復雜的計算領域港华，如向量計算道川，矩陣運算。市面上幾乎所有的手機使用的CPU立宜，都是ARM架構冒萄。咦....，等等橙数。IPhone不是使用的是蘋果的A系列的CPU嗎尊流？尼瑪，你在逗我嗎灯帮？我那么高大上的手機崖技，怎么能跟Android那種垃圾手機，使用的是一樣架構的CPU呢钟哥？恩~迎献，別慌，確實是這樣子的瞪醋。雖然蘋果忿晕、高通、MTK银受、三星都有自己的CPU践盼，但是都是使用的是ARM架構的鸦采。簡單的說，就是這些廠商通過使用ARM指令集體系結構,來設計自己的CPU咕幻、外圍的IC(如：音頻渔伯、WIFI、藍牙)和對指令集進行優(yōu)化肄程，最后形成自己的CPU锣吼。ARM架構一般有ARMv8架構、ARMv7-A架構蓝厌、ARMv6架構玄叠、Cortex-A系列架構、Cortex-M系列架構拓提，不同架構的CPU有不同的用途读恃。所以不管是高大上的蘋果手機還是爛大街的Android手機，都是使用的是ARM架構的CPU代态。
ARM已經被軟銀收購了寺惫，所以抵制日貨，這比較麻煩蹦疑。

使用SSE指令集進行程序優(yōu)化

Talk is cheap西雀， Show me the code

普通版

int normal_add(int *a, size_t n) {
    assert(a);
    int sum = 0;

    for(size_t i = 0; i < n; ++i) {
        sum += a[i];
    }
    return sum;
}

這個函數有點簡單，簡單到以至于無需要過多華麗的語言來修飾歉摧。它就是一個求和的函數艇肴。下面我們來看一下測試程序：

class Timer {
    public:
        Timer(const std::string& n) : name(n), start(std::clock()) {}

        ~Timer() {
            double elapsed = (double(std::clock() - start)) / double(CLOCKS_PER_SEC);

            std::cout << name << ": " << int(elapsed * 1000) << "ms" << std::endl;
        }

    private:
        std::string name;
        std::clock_t start;
};

#define Timer(n) Timer timer(n)

int main(int argc, char *argv[]) {
    if(argc != 2) {
        std::cout << "error argument" << std::endl;
        return -1;
    }

    size_t n = atoi(argv[1]);

    int *a = NULL;
    posix_memalign((void**)&a, 16, sizeof(int)*n);

    for(size_t i = 0; i < n; ++i) {
        a[i] = 5;
    }

    {
        Timer("normal_add");
        std::cout << "return: " << normal_add(a, n) << ",  "; 
    }
    free(a);

    return 0;

這個測試程序定義一個Timer類，用于計算normal_add函數的時間判莉，單位為毫秒豆挽。通過命令行傳入的參數，申請內存券盅。posix_memalign函數表示在堆中申請16字節(jié)對齊的內存帮哈。至于為什么要16字節(jié)對齊，我們下面會用到锰镀。然后把數組中的每個值設置為5娘侍。調用normal_add函數進行計算。下面我們進行測試：

編譯：g++ normal_add.cc
運行：./a.out 10000000
結果：return: 50000000,  normal_add: 41ms

可以看到泳炉，5加上10000000的結果為50000000憾筏，normal_add函數耗時為41ms。是的花鹅，沒問題氧腰，非常完美，你應該為自己的設計感覺到驕傲。下面我們對這個程序進行優(yōu)化古拴。

循環(huán)版

在程序優(yōu)化中有一種經常使用的方法：循環(huán)展開箩帚。循環(huán)展開可以降低循環(huán)開銷，提高指令級并行性能,此處使用四路展開

下面我們把上面的程序在循環(huán)內分4路進行展開黄痪，代碼如下：

int normal_add_loop4(int *a, size_t n) {
    assert(a);

    int sum = 0;
    size_t block = n / 4;    // 等價于n >> 2
    size_t reserve = n % 4;  // 等價于 n & 0x3
    int *p = a;

    for(size_t i = 0; i < block; ++i) {
        sum += *p;        
        sum += *(p+1);        
        sum += *(p+2);        
        sum += *(p+3);        
        p += 4;
    }

    // 剩余的不足4字節(jié)
    for(size_t i = 0; i < reserve; ++i) {
        sum += p[i];
    }
    return sum;
}

修改上面的測試程序為：

{
    Timer("normal_add_loop4");
    std::cout << "return: " << normal_add(a, n) << ",  "; 
}  

進行測試：

編譯：g++ normal_add_loop4.cc
運行：./a.out 10000000
結果: return: 50000000,  normal_add_loop4: 33ms

結果為50000000紧帕，normal_add_loop4函數耗時為33ms。比上面的normal_add快了8ms桅打。下面我們使用SSE指令集對程序進行優(yōu)化是嗜。

SSE版

使用SSE指令，首先要了解這一類用于進行初始化加載數據以及將暫存器的數據保存到內存相關的指令挺尾，大多數SSE指令是使用的xmm0到xmm8的暫存器鹅搪，那么使用之前，就需要將數據從內存加載到這些暫存器遭铺。

1. load(set)系列涩嚣，用于加載數據，從內存到暫存器掂僵。
   __m128i _mm_load_si128(__m128i *p);
   __m128i _mm_loadu_si128(__m128i *p);
2. store系列，用于將計算結果等SSE暫存器的數據保存到內存中顷歌。
   void _mm_store_si128 (__m128i *p, __m128i a);
   void _mm_storeu_si128 (__m128i *p, __m128i a);

_mm_load_si128函數表示從內存中加載一個128bits值到暫存器锰蓬，也就是16字節(jié)，注意：p必須是一個16字節(jié)對齊的一個變量的地址眯漩。返回可以存放在代表寄存器的變量中的值芹扭。
_mm_loadu_si128函數和_mm_load_si128一樣的，但是不要求地址p是16字節(jié)對齊赦抖。

store系列的_mm_store_si128和_mm_storeu_si128函數舱卡，與上面的load系列的函數是對應的。 表示將__m128i 變量a的值存儲到p所指定的地址中去队萤。

字節(jié)對齊是什么東西轮锥？

首先字節(jié)對齊不是東西，字節(jié)對齊是一個古老而又神秘的傳說要尔，它起源于遙遠的上古時代舍杜，遙遠有多遠，額~赵辕，總之就是很久以前既绩，在那個你或者我都還沒出生的年代。如果你不知道什么是字節(jié)對齊还惠，你就不能提高CPU高速緩存的命中率饲握，也就不能對程序優(yōu)化，更談不上用什么指令集。字節(jié)對齊救欧，比你想象中還要常見衰粹，比如說：

    struct St {
        char c;
        int a;
    };
    struct St s;

sizeof(s)的值等于多少呢？ 在自己的計算機上看一下吧颜矿，如果它和你想象中的不一樣寄猩，那么。骑疆。田篇。額~，也沒什么箍铭。下面我們用sse指令集對上面的程序進行優(yōu)化泊柬，代碼如下：

int sse_add(int *a, size_t n) { 
    assert(a);

    int sum = 0;
    __m128i sse_sum = _mm_setzero_si128();
    __m128i sse_load;
    __m128i *p = (__m128i*)a;

    size_t block = n / 4;     // SSE寄存器能一次處理4個32位的整數
    size_t reserve = n % 4;  // 剩余的不足16字節(jié)
    
    for(size_t i = 0; i < block; ++i) {
        sse_load = _mm_load_si128(p);
        sse_sum  = _mm_add_epi32(sse_sum, sse_load); // 帶符號32位緊縮加法
        ++p;
    }

    // 剩余的不足16字節(jié)
    int *q = (int *)p;
    for(size_t i = 0; i < reserve; ++i) {
        sum += q[i];
    }

    // 將累加值合并
    sse_sum = _mm_hadd_epi32(sse_sum, sse_sum);  // 帶符號32位水平加法
    sse_sum = _mm_hadd_epi32(sse_sum, sse_sum);

    sum += _mm_cvtsi128_si32(sse_sum);  // 返回低32位
    return sum;
}

注意: 上面的代碼只針對是int為4個字節(jié)，如果你的機器上int為8個字節(jié)诈火，則不可用兽赁。用sizeof(int)看一下你機器中的輸出的值吧。我們使用是_mm_load_si128函數, 所以傳入的地址a必須是16字節(jié)對齊的冷守，所以上面的測試程序用了posix_memalign申請了16字節(jié)對齊的內存(還記得嗎刀崖？)。

修改上面的測試程序為：

{
    Timer("sse_add");
    std::cout << "return: " << sse_add(a, n) << ",  "; 
}

進行測試拍摇，編譯時記得加頭文件nmmintrin.h亮钦，編譯選項-msse4：

編譯: g++ -msse4 sse_add.cc
運行: ./a.out 10000000
結果: return: 50000000,  sse_add: 17ms

沒問題，結果正確充活，sse_add用了17ms蜂莉，比上面的normal_add_loop4函數快了16ms。下面我們使用循環(huán)4路展開對上面的sse_add進行優(yōu)化混卵，代碼為：

int sse_add_loop4(int *a, int n) { 
    assert(a);

    int sum = 0;
    size_t block = n / 16;    // SSE寄存器能一次處理4個32位的整數
    size_t reserve = n % 16; // 剩余的字節(jié)

    __m128i sse_sum0 = _mm_setzero_si128();
    __m128i sse_sum1 = _mm_setzero_si128();
    __m128i sse_sum2 = _mm_setzero_si128();
    __m128i sse_sum3 = _mm_setzero_si128();
    __m128i sse_load0;
    __m128i sse_load1;
    __m128i sse_load2;
    __m128i sse_load3;
    __m128i *p = (__m128i*)a;

    for(size_t i = 0; i < block; ++i) {
        sse_load0 = _mm_load_si128(p);
        sse_load1 = _mm_load_si128(p+1);
        sse_load2 = _mm_load_si128(p+2);
        sse_load3 = _mm_load_si128(p+3);

        sse_sum0 = _mm_add_epi32(sse_sum0, sse_load0);
        sse_sum1 = _mm_add_epi32(sse_sum1, sse_load1);
        sse_sum2 = _mm_add_epi32(sse_sum2, sse_load2);
        sse_sum3 = _mm_add_epi32(sse_sum3, sse_load3);

        p += 4;
    }

    // 剩余的不足16字節(jié)
    int *q = (int *)p;
    for(size_t i = 0; i < reserve; ++i) {
        sum += q[i];
    }

    // 將累加值兩兩合并
    sse_sum0 = _mm_add_epi32(sse_sum0, sse_sum1);
    sse_sum2 = _mm_hadd_epi32(sse_sum2, sse_sum3);
    sse_sum0 = _mm_add_epi32(sse_sum0, sse_sum2);

    sse_sum0 = _mm_hadd_epi32(sse_sum0, sse_sum0);
    sse_sum0 = _mm_hadd_epi32(sse_sum0, sse_sum0);

    sum += _mm_cvtsi128_si32(sse_sum0); // 取低32位

    return sum;
}

修改上面的測試程序為：

{
    Timer("sse_add_loop4");
    std::cout << "return: " << sse_add(a, n) << ",  "; 
}

進行測試映穗，編譯時記得加頭文件nmmintrin.h，編譯選項-msse4：

編譯: g++ -msse4 sse_add_loop4.cc
運行: ./a.out 10000000
結果: return: 50000000,  sse_add_loop4: 10ms

結果正確幕随，用于10ms蚁滋，比上面的sse_add快了7ms。

由此可以看出合陵，sse指令集確實可以提高程序的性能枢赔。但是上面的函數有點無聊，有點不切實際拥知，5*10000000不就是等于50000000踏拜，搞那么復雜干嘛。是的低剔，的確挺無聊的速梗，無聊的函數肮塞、無聊的人，無聊的人寫的無聊的代碼姻锁，~恩枕赵。。位隶。別浪拷窜，春風十里不如你。下面我們接著往下看：

字符串模式匹配

字符串的模式匹配涧黄，也就是在主串s中篮昧，找到一個相等的目標串t。
如: s = "cddcdc", t = "cdc", 則可以匹配笋妥。 t = "cdcc" 時懊昨，則不能匹配。

于是乎春宣，我們可以采取暴力搜索進行匹配酵颁，代碼如下：

int normal_strstr(const char *src, const char *dest) {
    assert(src && dest);

    int src_len = strlen(src);
    int dest_len = strlen(dest);

    int i;
    int j;
    int k;

    for(i = 0; i < src_len; ++i) {
        k = i;
        for(j = 0; j < dest_len; ++j) {
            if(src[k] == dest[j]) {
                ++k;
            } else break;
        }
        if(j == dest_len) {
            return k - dest_len;
        }
    }
    return -1;
}

暴力搜索是最費時間的，時間復雜度為O(n*n), 我們寫個測試程序進行測試月帝，代碼如下：

int main(int argc, char *argv[]) {
#define BUF_SIZE (10 * 1024 * 1024)

    char *buf = (char *)malloc(sizeof(char) * BUF_SIZE);
    if(!buf) {
        std::cout << "failed malloc" << std::endl;
        return -1;
    }

    memset(buf, 'm', BUF_SIZE);

    const char *dest = "message=";

    memcpy(buf + BUF_SIZE - 1 - strlen(dest), dest, strlen(dest));

    buf[BUF_SIZE - 1] = '\0';

    const char *src = buf;

    int pos;
    for(int i = 0; i < 500; ++i) {
        pos = normal_strstr(src, dest);
    }
    std::cout << "pos: " << pos << std::endl;

    free(buf);
}  

這個測試函數的躏惋，主要是申請一塊10M的buf，把要匹配的字符message=放入buf的最后嚷辅，然后調用normal_strstr 500次其掂。下面我們用gprof進行測試。下面進行測試：

編譯： g++ normal_strstr.cc -pg -lc
運行: ./a.out
查看gprof的測試結果：   gprof ./a.out gmon.out -p
輸出：  
      %   cumulative   self              self     total           
      time   seconds   seconds    calls  ms/call  ms/call  name    
    100.74     56.93    56.93      500   113.86   113.86  normal_strstr(char const*, char const*)  

可以看到normal_strstr執(zhí)行了500次潦蝇，每次耗費的時間為113.86ms，總的時間為56.93s深寥。

在計算機科學領域攘乒， 有一門課程，叫做數據結構和算法惋鹅，里面有講到對字符串模式匹配進行優(yōu)化的算法则酝，叫做KMP算法。

KMP算法

至于kmp算法的原理闰集，我也忘了差不多沽讹。這東西，看了也不一定懂武鲁、懂了也不一定會爽雄、會了也不一定會用、用了你才知道你不懂沐鼠。下面是KMP算法的代碼：

static void get_next(const char* dest, int next[]) {
    /* 計算回溯值 */

    int j = 0;
    int k = -1;
    next[0] = -1;
    int dest_len = strlen(dest);

    while(j < dest_len) {
        if(k == -1 || dest[j] == dest[k]) {
            ++j;
            ++k;
            if(dest[j] != dest[k]) {
                next[j] = k;
            } else {
                next[j] = next[k];
            }
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}  

int kmp(const char *src, const char* dest) {  
    assert(src && dest);

    int i = 0;
    int j = 0;
    const int src_len = strlen(src);
    const int dest_len = strlen(dest);
    int next[dest_len];

    get_next(dest, next);

    i = 0;
    while(i < src_len && j < dest_len) {
        if(j == -1 || src[i] == dest[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    return j >= dest_len ? i - dest_len : -1;
}

我們把上面的測試程序改為：

for(int i = 0; i < 500; ++i) {
    pos = kmp(src, dest);
}  

進行測試：

編譯： g++ kmp_strstr.cc -pg -lc  
運行: ./a.out
查看gprof的測試結果：   gprof ./a.out gmon.out -p   
輸出：
%   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
100.52     62.07    62.07      500   124.14   124.14  kmp(char const*, char const*)

可以看到kmp算法執(zhí)行了500次挚瘟，每次耗費的時間為124.14ms叹谁，總的時間為62.07s，擦乘盖。焰檩。。比我們那個normal_strstr函數還耗時間订框，不是說kmp算法是優(yōu)化字符串匹配的嗎析苫？童話里都是騙人的。是的穿扳，別慌衩侥。KMP算法的確可以優(yōu)化字符串匹配，但是我們上面的函數只是實現了算法纵揍，并沒有做優(yōu)化顿乒，比如每次計算都要調用get_next計算回溯值，函數調用是需要時間的泽谨，還有就是子串的相似度比較低璧榄，函數也沒進行優(yōu)化，這都會影響性能吧雹，可見能寫出一個好的算法多么艱辛骨杂，更別說從頭到尾設計一個算法。在這里致敬大師雄卷。下面我們使用SSE指令集對字符串匹配進行優(yōu)化.

使用SSE優(yōu)化字符串匹配

在 Intel 的 SSE4.2 指令集中搓蚪，有一個 pcmpistrm 指令，它可以一次對一組16個字符與另一組字符作比較丁鹉，也就是說一個指令可以作最多16×16=256次比較妒潭。

要使用SSE對字符串匹配進行優(yōu)化，需要用到下面幾個函數：
參考：https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm_cmpistri&expand=914

int _mm_cmpistri (__m128i a, __m128i b, const int imm8)
Compare packed strings with implicit lengths in a and b using the control in imm8, and store the generated index in dst.

int _mm_cmpistrz (__m128i a, __m128i b, const int imm8)
Compare packed strings with implicit lengths in a and b using the control in imm8, and returns 1 if any character in b was null, and 0 otherwise.

int _mm_cmpistrs (__m128i a, __m128i b, const int imm8)
Compare packed strings with implicit lengths in a and b using the control in imm8, and returns 1 if any character in a was null, and 0 otherwise.

使用SSE優(yōu)化字符串匹配代碼如下：

     /* unit test:
      * src = "00000000001234561234123456789abcdefghi", dest = "1234567"; ret = 20
      * src = "00000000001234561234123456789abcdefghi", dest = "123456789abcdefg";  ret = 20
      * src = "00000000001234561234123456789abcdefghi", dest = "1234"; ret = 10
      * src = "00000000001234561234123456789abcdefghi", dest = "00000000"; ret = 0
      * src = "00000000001234561234123456789abcdefghi", dest = "0000000000123456"; ret = 0
      * src = "00000000001234561234123456789abcdefghi", dest = "000000000012345612"; ret = 0
      * src = "00000000001234561234123456789abcdefghi", dest = "1000000000012345612"; ret = -1
      * src = "00000000001234561234123456789abcdefghi", dest = "fghi"; ret = 34
      * src = "00000000001234561234123456789abcdefghi", dest = "fghia"; ret = -1
      * src = "00000000001234561234123456789abcdefghi", dest = "3456789abcdefghi"; ret = 22
      * src = "00000000001234561234123456789abcdefghi", dest = "23456789abcdefghi"; ret = 21
      * src = "00000000001234561234123456789abcdefghi", dest = "3456789abcdefghiq"; ret = -1
      * src = "aaaabbbbaaaabbbbaaaabbbbacc", dest = "aaaabbbbaaaabbbbacc"; ret = 8
      * src = "aaaabbbbaaaabbbbaaaabbbbacc", dest = "aaaabbbbaaaabbbbccc"; ret = -1
      * src = "012345678", dest = "234"; ret = 2
      * src = "012345678", dest = "2346"; ret = -1  
      * /  
       
    int sse_strstr(const char *src, const char *dest) {   
        assert(src && dest);

        if(strlen(src) < strlen(dest)) {
            return -1;
        }

        const char *s = src;
        const char *d = dest;
        int cmp;
        int cmp_z;
        int cmp_c;
        int cmp_s;

        const char *s_16;
        const char *d_16;

        __m128i frag1;
        __m128i frag2;
        frag1 = _mm_loadu_si128((__m128i *)s);
        frag2 = _mm_loadu_si128((__m128i *)d);
        cmp_s = _mm_cmpistrs(frag2, frag1, 0xc);


        if(cmp_s) {
            /* strlen(dest) < 16 */
            do {
                frag1 = _mm_loadu_si128((__m128i *)s); 
                cmp   = _mm_cmpistri(frag2, frag1, 0x0c);
                cmp_c = _mm_cmpistrc(frag2, frag1, 0x0c);
                cmp_z = _mm_cmpistrz(frag2, frag1, 0xc);
    
                if((!cmp) & cmp_c) break;
                s += cmp;
            } while(!cmp_z);

            if(!cmp_c) {
                return -1;
            }
            return s - src;
        } else {
            /* strlen(dest) >= 16 */
            do {
                frag1 = _mm_loadu_si128((__m128i *)s);
                frag2 = _mm_loadu_si128((__m128i *)d);
                cmp   = _mm_cmpistri(frag2, frag1, 0xc);
                cmp_z = _mm_cmpistrz(frag2, frag1, 0xc);
                cmp_s = _mm_cmpistrs(frag2, frag1, 0xc);       

                if(cmp) {
                    /* suffix or not match(cmp=16)*/
                    s += cmp;  
                } else {
                    /* match */
                    do {
                        s_16  = s + 16;
                        d_16  = d + 16;
                        frag1 = _mm_loadu_si128((__m128i *)s_16);
                        frag2 = _mm_loadu_si128((__m128i *)d_16);
                        cmp   = _mm_cmpistri(frag2, frag1, 0xc);
                        cmp_z = _mm_cmpistrz(frag2, frag1, 0xc);
                        cmp_s = _mm_cmpistrs(frag2, frag1, 0xc);
                
                        if(cmp) break;
                
                    } while(!cmp_s && !cmp_z);
                    if(!cmp) {
                        return s - src;
                    } else {
                        s += 1;
                        cmp_z = 0;
                    }
                }            
            } while(!cmp_z);
            return -1;
        } 
    }     

上面的代碼大意是：通過_mm_cmpistrs函數判斷揣钦，目標串的長度是否大于16字節(jié)雳灾，如果是小于16字節(jié)，那么目標串可以一次性加載sse的暫存器中冯凹，當大于16字節(jié)時谎亩，目標串不能一次性加載到sse的暫存器。通過_mm_cmpistri函數判斷宇姚，目標串在主串中匹配的位置匈庭，如果返回0，則表示目標串和主串的16字節(jié)完全匹配浑劳，繼續(xù)匹配阱持，剩余的字節(jié)。如果返回非0則表示魔熏，目標串在子串沒有完全匹配紊选。返回16為啼止，目標串和主串完全不匹配。其他值為兵罢，主串的后綴與目標串匹配的個數献烦，如cmp=5，表示主串的后面5個字符與目標串的前面5個字符相匹配卖词。

修改測試程序為：

for(int i = 0; i < 500; ++i) {
    pos = sse_strstr(src, dest);
}           

進行測試：

編譯： g++ -msse4 sse_strstr.cc -pg -lc  
運行: ./a.out
查看gprof的測試結果：   gprof ./a.out gmon.out -p   
輸出：  
  %   cumulative   self              self     total           
   time   seconds   seconds    calls  ms/call  ms/call  name    
 100.44      7.67     7.67      500    15.35    15.35  sse_strstr(char const*, char const*)  

可以看到sse_strstr執(zhí)行了500次巩那，每次耗費的時間為15.35ms，總的時間為7.67s,遠遠比我們上面寫的kmp算法(62.07s), normal_strstr（56.93s)快得多此蜈，幾乎可以說是完勝了即横。這個函數還不是最優(yōu)的，還可以進行優(yōu)化裆赵，上面我們說了东囚，SSE的寄存器是128位，16字節(jié)對齊战授，上面的程序并沒有考慮16字節(jié)页藻，算法也不是使用的是KMP算法。如果每次加載的數據是16對齊植兰，而且使用KMP算法的話份帐，程序的性能是最快的。下面我們測試一下楣导，標準庫的字符串匹配废境。

strstr函數

strstr函數是glibc自帶的字符串匹配的函數，下面我們對它進行性能測試筒繁。如果把上面的測試程序改成這樣：

for(int i = 0; i < 500; ++i) {
    p = strstr(src, dest);
}  

在10M的內存中噩凹，調用500次的strstr函數，如果你去查看gprof文件或反編譯去看匯編代碼的話毡咏，實際上栓始，上面的調用只會調用一次的strstr函數，也就是說編譯器會幫你優(yōu)化血当。雖然你調用了500次，但是編譯器很聰明禀忆，只會幫你調用一次strstr函數臊旭。額~~~，那怎么整箩退？ 居然只能調用1次离熏，那就讓它調用1次吧。我們把上面的BUF改大一點就是了戴涝，改為100M進行測試滋戳。代碼如下：

int main(int argc, char *argv[]) {

#define BUF_SIZE (100 * 1024 * 1024)

    char *buf = (char *)malloc(sizeof(char) * BUF_SIZE);
    if(!buf) {
        std::cout << "failed malloc" << std::endl;
        return -1;
    }

    memset(buf, 'm', BUF_SIZE);

    const char *dest = "message=";

    memcpy(buf + BUF_SIZE - 1 - strlen(dest), dest, strlen(dest));

    buf[BUF_SIZE - 1] = '\0';
    const char *src = buf;

    const char* p = strstr(src, dest);
    std::cout << "pos: " << p - src << std::endl;

    free(buf);
    return 0;
}

進行測試：

編譯： g++ test_strstr.cc
運行:  time ./a.out 
結果： 
    real    0m0.092s
    user    0m0.028s
    sys     0m0.036s 

上面我們用了time測試運行完成的時間钻蔑，可以看到，整個程序總共花費了92ms, 用戶空間使用了28ms, 內核空間使用36ms奸鸯。

我們把上面的strstr函數咪笑，替換為我們上面寫的sse_strstr函數，進行測試：

編譯： g++ -msse4 test_sse_strstr.cc
運行： time ./a.out
結果：  
    real    0m0.231s
    user    0m0.176s
    sys     0m0.032s    

可以看到娄涩，我們使用sse_strstr函數窗怒，整個程序總共花費了231ms, 用戶空間使用了176ms, 內核空間使用32ms。被glic庫的strstr秒殺蓄拣。

我們再測試一下扬虚，C++中的std::search函數，進行測試：

編譯： g++ test_std_search.cc
運行： time ./a.out
結果：  
    real    0m0.414s
    user    0m0.368s
    sys     0m0.028s        

可以看到球恤，我們使用std::search函數辜昵，整個程序總共花費了414ms, 用戶空間使用了368ms, 內核空間使用28ms, 比我們的sse_strstr函數還慢，被glic庫的strstr再次秒殺咽斧。

我們在來看一下string類中的find的函數堪置，注意上面我們申請內存是字符串，要轉換為string類收厨，需要使用string(src, BUF_SIZE)操作晋柱，但是這個操作也是需要耗費時間的。所以我們使用最上面的Timer類來粗劣的統(tǒng)計一下诵叁，string類在100M的內存進行查找需要耗費的時間雁竞。

{
    TIMER("string find")
    s_src.find(s_dest);
}

進行測試：

編譯： g++ test_string_find.cc
運行： ./a.out
結果為： string find: 889ms  

可以看到在100M進行查找目標串， string類find的函數大概需要 889ms拧额，跟上面的幾個函數沒有任何的可比性碑诉。

strstr函數為什么那么快?

strstr函數是glibc庫的函數，glibc在X86的環(huán)境下已經默認是已經支持SSE優(yōu)化的侥锦，不同版本的發(fā)型商进栽，可能會有所不同，使用的glibc版本庫不一樣恭垦，也可能不同快毛，我這臺機器使用的是libc-2.19，如果你去看glic-2.19源碼的strstr函數番挺，可以看到它是有支持SSE4.2優(yōu)化的唠帝，而且使用的就是我們上面所說的16字節(jié)對齊的KMP算法，進行優(yōu)化的玄柏。所以它會那么快襟衰，故，能寫標準庫的都不是一般人粪摘，在這里再次致敬大師瀑晒，因為你們的努力惰说，讓這個世界變得更加美好赚瘦。如果你的機器的glibc庫是已經支持SSE優(yōu)化的千所，那么字符串匹配是最快的报咳，遠遠比C++的string類，和std::search函數快间坐，當然還有其他函數也是支持SSE的灾挨，如strchr。

總結：

使用sse進行程序優(yōu)化竹宋，能帶來性能的提升劳澄，但是也會使代碼的可移植性、維護性變差蜈七。因本人技術水平有限秒拔，上面的分析（僅代表個人意見）可能有存在錯誤的地方，歡迎指正飒硅。