C++テンプレートではパフォーマンスが改善されない

Question

C++テンプレートを学習するために、ループアンローリング（LU）を使用したバブルソートの3つのバージョンを実装しました。すなわち、ループアンローリング、Cマクロによる手動ループアンローリング、およびテンプレートによるループアンローリングを伴わない。コード：

// No LU 
void bubbleSort(int* data, int n) 
{ 
    for(int i=n-1; i>0; --i) { 
     for(int j=0; j<i; ++j) 
      if (data[j]>data[j+1]) std::swap(data[j], data[j+1]); 
    } 
} 
// LU with macro 
void bubbleSort4(int* data) 
{ 
#define COMP_SWAP(i, j) if(data[i]>data[j]) std::swap(data[i], data[j]) 
    COMP_SWAP(0, 1); COMP_SWAP(1, 2); COMP_SWAP(2, 3); 
    COMP_SWAP(0, 1); COMP_SWAP(1, 2); 
    COMP_SWAP(0, 1); 
} 
// LU with template 
template<int i, int j> 
inline void IntSwap(int* data) { 
    if(data[i]>data[j]) std::swap(data[i], data[j]); 
} 
template<int i, int j> 
inline void IntBubbleSortLoop(int* data) { 
    IntSwap<j, j+1>(data); 
    IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>(data); 
} 
template<> 
inline void IntBubbleSortLoop<0, 0>(int*) { } 
template<int n> 
inline void IntBubbleSort(int* data) { 
    IntBubbleSortLoop<n-1, 0>(data); 
    IntBubbleSort<n-1>(data); 
} 
template<> 
inline void IntBubbleSort<1>(int* data) { } 

テストコード：

#include <iostream> 
#include <utility> //std::swap 
#include <string.h> // memcpy 
#include <sys/time.h> 

class Timer{ 
    struct timeval start_t; 
    struct timeval end_t; 
    public: 
    void start() { gettimeofday(&start_t, NULL); } 
    void end() { gettimeofday(&end_t, NULL); } 
    void print() { 
     std::cout << "Timer: " << 1000.0*(end_t.tv_sec-start_t.tv_sec)+(end_t.tv_usec-start_t.tv_usec)/1000.0 << " ms\n"; 
    } 
}; 

int main() { 
    Timer t1, t2, t3; const int num=100000000; 
    int data[4]; int inidata[4]={3,4,2,1}; 

    t1.start(); 
    for(int i=0; i<num; ++i) { 
     memcpy(data, inidata, 4); 
     bubbleSort(data, 4); 
    } 
    t1.end(); 
    t1.print(); 

    t2.start(); 
    for(int i=0; i<num; ++i) { 
     memcpy(data, inidata, 4); 
     bubbleSort4(data); 
    } 
    t2.end(); 
    t2.print(); 

    t3.start(); 
    for(int i=0; i<num; ++i) { 
     memcpy(data, inidata, 4); 
     IntBubbleSort<4>(data);  
    } 
    t3.end(); 
    t3.print(); 

    return 0; 
} 

私のプラットフォームはOSXで、コンパイラが打ち鳴らすさ：

g++ -std=c++11 -o loop_unrolling loop_unrolling.cpp 

私はテンプレートのバージョンは、マクロverisonと同等の性能を持っている期待して、通常よりもはるかに高速です。しかし、テンプレートのバージョンは最も遅いです。誰も知っている理由は？ -O1と

Timer: 1847.78 ms 
Timer: 685.736 ms 
Timer: 5075.86 ms 

=================================

：

-O2と

Timer: 861.071 ms 
Timer: 495.001 ms 
Timer: 2793.02 ms 

：

Timer: 247.691 ms 
Timer: 258.666 ms 
Timer: 254.466 ms 

-O3と：

Timer: 242.535 ms 
Timer: 233.354 ms 
Timer: 251.297 ms 

私に混乱を招くのは、テンプレートバージョンで-Oxを有効にするかどうかにかかわらずループアンローリングコードが生成されるはずです。しかし、それは当てはまりません。もっと混乱させるのは、LP以外のバージョンよりも遅く、-Oxを有効にしないことです。

Answer 1

Jarod42が指摘したように、関数呼び出しが問題です。関数テンプレートから関数を生成するコンパイラプロセスは、インライン展開を行うコンパイラプロセスとは別です。その結果、インライン展開は保証されず、テンプレートバージョンの関数呼び出しのパフォーマンスペナルティを支払うことになります。 inlineキーワードはコンパイラへのヒントであり、尊重する必要はありません。

将来的に同様の問題が発生し、勇気がある場合は、コードで生成されたアセンブリコードを見て違いを確認できます。上記のコードを撮影し、

// b4.cc 
#include <algorithm> 

// LU with macro 
void bubbleSort4(int* data) 
{ 
#define COMP_SWAP(i, j) if(data[i]>data[j]) std::swap(data[i], data[j]) 
    COMP_SWAP(0, 1); COMP_SWAP(1, 2); COMP_SWAP(2, 3); 
    COMP_SWAP(0, 1); COMP_SWAP(1, 2); 
    COMP_SWAP(0, 1); 
} 

とb4t.cc

// b4t.cc 
#include <algorithm> 

// LU with template 
template<int i, int j> 
inline void IntSwap(int* data) { 
    if(data[i]>data[j]) std::swap(data[i], data[j]); 
} 
template<int i, int j> 
inline void IntBubbleSortLoop(int* data) { 
    IntSwap<j, j+1>(data); 
    IntBubbleSortLoop<j<i-1?i:0, j<i-1?(j+1):0>(data); 
} 
template<> 
inline void IntBubbleSortLoop<0, 0>(int*) { } 
template<int n> 
inline void IntBubbleSort(int* data) { 
    IntBubbleSortLoop<n-1, 0>(data); 
    IntBubbleSort<n-1>(data); 
} 
template<> 
inline void IntBubbleSort<1>(int* data) { } 

// LU with macro 
void bubbleSort4(int* data) 
{ 
    IntBubbleSort<4>(data); 
} 

b4.cc 2つのコンパイル単位にそれを分割する。これは、あなたがg++ -S b4*.cc、その後することができますし、b4.sとb4t.s.を比較しますb4t.sには多くの機能があります。 g++ -O2 -S b4*.ccのようなインライン展開をオンにすると、アセンブリは事実上同一です。