4(編譯展開)

今天繼續介紹第4種常見技巧,編譯展開,代碼見本文最後,重要的部分有註釋說明。

我們知道對於循環,編譯器會自動進行展開,但是如何展開,這完全不可控,如果我們自行碼代碼,代碼會顯得臃腫難看,大段重複代碼,因此本為介紹了一種常見的方法進行這種代碼展開,可以寫到任意層次,我這裡只寫到了DO16,見代碼加粗的部分。

實驗表明在手動展開後,加上O3的編譯優化,依然能夠比不手動展開要快,大家可以實驗以下的代碼。

可能會有讀者問,這能節省多少時間,會有多少好處,那麼請讀者朋友們做實驗來驗證吧,一切真知來自實踐。如果經常閱讀高質量開源代碼會常常看到這個技巧,希望讀者在深入理解後在工作中多多采用。

有興趣的朋友還可以用不同層次(4,16,32,64)的展開,看看展開多少是最優的,並解釋原因,那恭喜您,您的境界又上了一個新的臺階了。

注:

1)裡面會使用到一些此前介紹過的代碼,因此新讀者建議閱讀此前系列的內容,鏈接在本文最後。

2)本文的續篇參見:http://blog.csdn.net/pennyliang/archive/2010/10/30/5975678.aspx

在用-O3編譯後,用objdump -d test_m1_o3觀察代碼的情況[兩段rdtsc之間的代碼,為主要計算過程的代碼]

400730:       83 fd 02                cmp    $0x2,%ebp

  400733:       89 c6                   mov    %eax,%esi
  400735:       4c 8d 63 fc             lea    0xfffffffffffffffc(%rbx),%r12 //0xfffffffffffffffc為16進制的 -4,未來會有專門博客介紹這段代碼的具體含義,不在本文展開。
  400739:       7e 21                   jle    40075c <main+0xac>
  40073b:       8d 45 fd                lea    0xfffffffffffffffd(%rbp),%eax
  40073e:       4c 8d 63 fc             lea    0xfffffffffffffffc(%rbx),%r12
  400742:       31 d2                   xor    %edx,%edx
  400744:       48 8d 48 01             lea    0x1(%rax),%rcx
  400748:       8b 44 93 04             mov    0x4(%rbx,%rdx,4),%eax
  40074c:       03 04 93                add    (%rbx,%rdx,4),%eax          //循環並沒有被展開      
  40074f:       89 44 93 08             mov    %eax,0x8(%rbx,%rdx,4)
  400753:       48 83 c2 01             add    $0x1,%rdx                        //相當於i++
  400757:       48 39 ca                cmp    %rcx,%rdx
  40075a:       75 ec                   jne    400748 <main+0x98>
     用objdump -d test_m3_o3觀察代碼的情況[兩段rdtsc之間的代碼,為主要計算過程的代碼]
 400726:       89 c7                   mov    %eax,%edi
  400728:       8d 45 0f                lea    0xf(%rbp),%eax
  40072b:       85 ed                   test   %ebp,%ebp
  40072d:       89 ea                   mov    %ebp,%edx
  40072f:       4d 8d 6c 24 fc          lea    0xfffffffffffffffc(%r12),%r13
  400734:       be 02 00 00 00          mov    $0x2,%esi
  400739:       0f 48 d0                cmovs  %eax,%edx
  40073c:       c1 fa 04                sar    $0x4,%edx
  40073f:       83 fa 02                cmp    $0x2,%edx
  400742:       7e 79                   jle    4007bd <main+0x10d>
  400744:       4d 8d 6c 24 fc          lea    0xfffffffffffffffc(%r12),%r13
  400749:       be 02 00 00 00          mov    $0x2,%esi
  40074e:       66 90                   xchg   %ax,%ax
  400750:       8b 43 04                mov    0x4(%rbx),%eax    //eax是累加器,可以看到明顯的代碼展開
  400753:       03 03                   add    (%rbx),%eax
  400755:       83 c6 10                add    $0x10,%esi
  400758:       89 43 08                mov    %eax,0x8(%rbx)
  40075b:       03 43 04                add    0x4(%rbx),%eax
  40075e:       89 43 0c                mov    %eax,0xc(%rbx)
  400761:       03 43 08                add    0x8(%rbx),%eax
  400764:       89 43 10                mov    %eax,0x10(%rbx)
  400767:       03 43 0c                add    0xc(%rbx),%eax
  40076a:       89 43 14                mov    %eax,0x14(%rbx)
  40076d:       03 43 10                add    0x10(%rbx),%eax
  400770:       89 43 18                mov    %eax,0x18(%rbx)
  400773:       03 43 14                add    0x14(%rbx),%eax
  400776:       89 43 1c                mov    %eax,0x1c(%rbx)
  400779:       03 43 18                add    0x18(%rbx),%eax
  40077c:       89 43 20                mov    %eax,0x20(%rbx)
  40077f:       03 43 1c                add    0x1c(%rbx),%eax
  400782:       89 43 24                mov    %eax,0x24(%rbx)
  400785:       03 43 20                add    0x20(%rbx),%eax
  400788:       89 43 28                mov    %eax,0x28(%rbx)
  40078b:       03 43 24                add    0x24(%rbx),%eax
  40078e:       89 43 2c                mov    %eax,0x2c(%rbx)
  400791:       03 43 28                add    0x28(%rbx),%eax
  400794:       89 43 30                mov    %eax,0x30(%rbx)
  400797:       03 43 2c                add    0x2c(%rbx),%eax
  40079a:       89 43 34                mov    %eax,0x34(%rbx)
  40079d:       03 43 30                add    0x30(%rbx),%eax
  4007a0:       89 43 38                mov    %eax,0x38(%rbx)
  4007a3:       03 43 34                add    0x34(%rbx),%eax
  4007a6:       89 43 3c                mov    %eax,0x3c(%rbx)
  4007a9:       03 43 38                add    0x38(%rbx),%eax
  4007ac:       89 43 40                mov    %eax,0x40(%rbx)
  4007af:       03 43 3c                add    0x3c(%rbx),%eax
  4007b2:       89 43 44                mov    %eax,0x44(%rbx)
  4penny:       48 83 c3 40             add    $0x40,%rbx
  4007b9:       39 f2                   cmp    %esi,%edx
  4007bb:       7f 93                   jg     400750 <main+0xa0>
  4007bd:       39 f5                   cmp    %esi,%ebp
  4007bf:       7e 27                   jle    4007e8 <main+0x138>
  4007c1:       48 63 c6                movslq %esi,%rax
  4007c4:       48 c1 e0 02             shl    $0x2,%rax
  4liang:       49 8d 4c 05 00          lea    0x0(%r13,%rax,1),%rcx
  4007cd:       49 8d 54 04 f8          lea    0xfffffffffffffff8(%r12,%rax,1),%rdx
  4007d2:       8b 01                   mov    (%rcx),%eax
  4007d4:       03 02                   add    (%rdx),%eax
  4007d6:       83 c6 01                add    $0x1,%esi
  4007d9:       48 83 c1 04             add    $0x4,%rcx
  4007dd:       89 42 08                mov    %eax,0x8(%rdx)
  4007e0:       48 83 c2 04             add    $0x4,%rdx
  4007e4:       39 f5                   cmp    %esi,%ebp
  4007e6:       7f ea                   jg     4007d2 <main+0x122>

明顯看出展開後的代碼,另外從編譯出的可執行程序的大小也可看出這種差異,越是內聯展開的代碼可執行程序越大。

------------------------------------------編譯方法---------------------------------

在debug模式下的編譯


g++ -g  test.cpp -o test_m1 -D M_1

g++ -g  test.cpp -o test_m2 -D M_2

g++ -g  test.cpp -o test_m3 -D M_3

在-O3條件下的優化編譯:

g++ -O3  test.cpp -o test_m1_o3 -D M_1

g++ -O3  test.cpp -o test_m2_o3 -D M_2

g++ -O3  test.cpp -o test_m3_o3 -D M_3

-----------------------------------------運行方法-------------------------------------

./test_m1 1000000 //求1000000的斐波拉契數

./test_m2 1000000

./test_m3 1000000

-------------------------------------------代碼-------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DO(x)  x
#define DO4(x)  x  x  x  x
#define DO8(x)  DO4(x) DO4(x)
#define DO16(x) DO8(x) DO8(x)
const int MAX = 512*1024*1024;
const float CPU_MHZ = 3000.164; //use cat /proc/cpuinfo get the value
const float CPU_tick_count_per_msecond = CPU_MHZ*1000;
#if defined(__i386__)

static __inline__ unsigned long long rdtsc(void)
{
  unsigned long long int x;
     __asm__ volatile ("rdtsc" : "=A" (x));
     return x;
}
#elif defined(__x86_64__)
static __inline__ unsigned long long rdtsc(void)
{
  unsigned hi, lo;
  __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
  return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

#endif

int main(int argc,char **argv)
{
        if(argc!=2)
        {
                printf("command penny line: test N,N no more than%d/n",MAX);
                return 0;
        }

        int* F = (int*)malloc(MAX*sizeof(int));
        memset(F,0,MAX*sizeof(int)); //just warm up cache, to make calculate more accurate!!!   
        F[0]=1;
        F[1]=1;
        int Fx=atoi(argv[1]);
        int start = 0;
        int end = 0;
        start = rdtsc();
        #ifdef M_1
        for(int i=2;i<Fx;++i)        //通過循環的方法,遞進地計算
        {
                F[i]=F[i-1]+F[i-2];
        }
        #endif


        #ifdef M_2
        int r= Fx%4;
        int idx = Fx/4;
        int i =2;

        int j=0;
        for(;j<idx;++j)
        {
                DO4(F[i]=F[i-1]+F[i-2];i++;);  //通過循環展開的方法,展成4段代碼,循環規模降低到原來的1/4
        }
        for(;i<Fx;i++)
        {
                F[i]=F[i-1]+F[i-2];
        }
        #endif

        #ifdef M_3
        int r= Fx%16;   
        int idx = Fx/16;
        int i=2;

        int j=0;
        for(;j<idx;++j)
        {
                DO16(F[i]=F[i-1]+F[i-2];i++;); //展開成16段代碼
        }
        for(;i<Fx;i++)
        {
                F[i]=F[i-1]+F[i-2];
        }
        #endif
        end = rdtsc();
        printf("run tick count:%d/n",(end -start));
        printf("ret:%d/n",F[Fx-1]);
        free(F);
        return 0;
}

(續)

編譯展開的這篇博客被CSDN推了首頁http://blog.csdn.net/pennyliang/archive/2010/10/28/5971059.aspx,有些讀者反映有些太難,考慮到有些地方沒有講得太清楚,本文一併進行深入討論。

首先關鍵的代碼是:

#define DO(x)  x
#define DO4(x)  x  x  x  x
#define DO8(x)  DO4(x) DO4(x)
#define DO16(x) DO8(x) DO8(x)

讀者可以按葫蘆畫瓢,繼續展開,這並不難理解。

我們選取了計算斐波那契數作為例子,將代碼展開為16的倍數,但是因為Fx是用戶輸入的,可能是16的倍數也可能不是,因此需要做一些轉換,將Fx變為Fx=16idx+r,這樣可以確保可以做idx次展開,最後尾部再用一個循環計算完,如下:

int r= Fx%16;   
int idx = Fx/16;
int i=2;
for(;i<idx;)
{
    DO16(F[i]=F[i-1]+F[i-2];i++;); //展開成16段代碼
}
for(;i<Fx;i++)
{
    F[i]=F[i-1]+F[i-2];
}
如果我們不用編譯來做循環展開,我們的代碼可能就得是

for(;i<idx;)
{
    F[i]=F[i-1]+F[i-2];i++;

    F[i]=F[i-1]+F[i-2];i++;

    F[i]=F[i-1]+F[i-2];i++;

    ....寫16遍相同的代碼,多難看啊。
}
for(;i<Fx;i++)
{
    F[i]=F[i-1]+F[i-2];
}

第二,我們要特別注意memset的使用,memset在計時之前進行,是因為這樣的計算更為準確,malloc分配大內存是採用mmap的方式,即只分配虛地址,而沒有實際的調頁,而我們做一個memset是為了調頁,大家可以做這樣的實驗,做兩次相同的malloc,用rdtsc的方式進行計時,你會發現第一次malloc會慢一些,而第二次會快,因為第一次有調頁,而第二次幾乎無調頁(內存要足夠大,否則可能會swap,也可能有少量調頁)。

用memset相信也不難理解,因為這個時間混在裡面可能會看不出誤差,假定某市一季度GDP為10,二季度為15,看上去提高了50%,但是因為在計算過程中,有5份的GDP(可以想象成memset的代價)是多算在裡面的,如果扣除這5份,則實際上是從5提升了100%。因此我們在設計實驗時,需要把一些幹擾項扣除,來比較,實驗的數據才具有價值。

第三,我的實驗結果是展開為4次是比較快的,我認為有這樣一些主要原因,但還需要設計進一步的實驗來證明:

(1)編譯展開的層次過大,代碼會變大,而代碼存儲在文件中,進入執行需要有一個讀磁盤的過程,另外代碼大,代碼局部性就不強,L1 cache的一部分是存放代碼段的,如果代碼越小越緊湊,那麼執行起來就會越開,展開出1024層,代碼的局部性肯定很差。

(2)編譯展開的層次過小,代碼雖然緊湊,但是流水線不通暢,跳轉太多,因此也容易導致性能變低。

因此總會有一種展開的層次可以trade off的流水線和代碼段的緊湊性,我的實驗結果是展開到4層是最快的,這是受機器環境影響的,不知道其他同學的實驗結果是怎樣的。

最後提到的細節是DO16(F[i]=F[i-1]+F[i-2];i++;); 的最後一個分號是不必要的,但是添加在這裡是為了讓代碼更自然,相信大部分細心的讀者都能看到這一點。