중첩 된 표현식의 표현식 템플릿 성능

Question

행렬 곱셈에서 표현식 템플릿 성능을 조사하고 있습니다. 저는 행렬 곱셈에서 루프를 풀고 있습니다. 네이티브 복식의 성능은 표현의 깊이가 너무 커지고 표현 템플릿 성능이 내리막 때까지 표현 템플릿의 성능과 같습니다. 여기서 코드이다 :

#include <iostream> 
#include <vector> 
#include <chrono> 

template<typename T> 
struct Real 
{ 
    typedef T RealType; 

    Real() noexcept : m_real(0) {} 
    inline explicit Real(RealType real) noexcept 
     : m_real(real) 
    { 
    } 

    inline RealType value() const noexcept 
    { 
     return m_real; 
    }           

    template<typename Expr> 
    void operator+=(const Expr& expr) 
    { 
     m_real += expr.value(); 
    } 

    RealType m_real; 
}; 

#define DEFINE_BINARY_OPERATOR(NAME, OP)  \ 
    template<typename Expr1, typename Expr2>       \ 
    struct NAME               \ 
    {                 \ 
     typedef typename Expr1::RealType RealType;      \ 
                     \ 
     NAME() noexcept {}            \ 
     NAME(const Expr1& e1, const Expr2& e2) noexcept     \ 
      : m_e1(e1), m_e2(e2) {}          \ 
                     \ 
     inline RealType value() const noexcept       \ 
     {                \ 
      return m_e1.value() OP m_e2.value();      \ 
     }                \ 
                     \ 
     Expr1 m_e1;              \ 
     Expr2 m_e2;              \ 
    };                 \ 
    template<typename Expr1, typename Expr2>       \ 
    inline decltype(auto) operator OP (const Expr1& e1, const Expr2& e2) noexcept\ 
    {                 \ 
     return NAME<Expr1, Expr2>(e1, e2);        \ 
    }                 \ 

DEFINE_BINARY_OPERATOR(Multiply, *) 
DEFINE_BINARY_OPERATOR(Add, +) 
DEFINE_BINARY_OPERATOR(Subtract, -) 
DEFINE_BINARY_OPERATOR(Divide, /) 

template<typename T> 
struct Matrix 
{ 
    explicit Matrix(size_t size) 
     : m_matrix(size, std::vector<T>(size)) 
    { 
    } 
    explicit Matrix(size_t size, const T& intialVal) 
     : m_matrix(size, std::vector<T>(size, intialVal)) 
    { 
    } 
    std::vector<T>& operator[](size_t row) { return m_matrix[row]; } 
    const std::vector<T>& operator[](size_t row) const { return m_matrix[row]; } 
    size_t size() const { return m_matrix.size(); } 

    std::vector<std::vector<T> > m_matrix; 
}; 

#define MATRIX_MULT_KERNEL(N) m1[i][k+N] * m2[j][k+N] 
#define MATRIX_MULT_ADD_KERNELS_4(N) \ 
    MATRIX_MULT_KERNEL(N) + MATRIX_MULT_KERNEL(N+1) + MATRIX_MULT_KERNEL(N+2) + MATRIX_MULT_KERNEL(N+3) 

template<typename T> 
Matrix<T> operator*(const Matrix<T>& m1, const Matrix<T>& m2) 
{ 
    if (m1.size() != m2.size()) 
     throw std::runtime_error("wrong sizes"); 

    Matrix<T> m3(m1.size()); 
    for (size_t i = 0; i < m1.size(); ++i) 
     for (size_t j = 0; j < m1.size(); ++j) 
      for (size_t k = 0; k < m1.size(); k+=16) 
      { 
       auto v0 = MATRIX_MULT_ADD_KERNELS_4(0); 
       auto v1 = MATRIX_MULT_ADD_KERNELS_4(4); 
       auto v2 = MATRIX_MULT_ADD_KERNELS_4(8); 
       auto v3 = MATRIX_MULT_ADD_KERNELS_4(12); 
       // auto v4 = MATRIX_MULT_ADD_KERNELS_4(16); 
       // auto v5 = MATRIX_MULT_ADD_KERNELS_4(20); 
       // auto v6 = MATRIX_MULT_ADD_KERNELS_4(24); 
       // auto v7 = MATRIX_MULT_ADD_KERNELS_4(28); 
       auto expr = (v0 + v1 + v2 + v3);// + v4 + v5 + v6 + v7); 
       m3[i][j] += expr; 

      } 
    return m3; 
} 

decltype(auto) now() 
{ 
    return std::chrono::high_resolution_clock::now(); 
} 

decltype(auto) milliseconds(const decltype(now())& start, const decltype(now())& end) 
{ 
    return std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); 
} 

int main() 
{ 
    constexpr static const int SIZE = 1024; 
    { 
     Matrix<double> m1(SIZE, 1.0); 
     Matrix<double> m2(SIZE, 1.0); 
     auto begin = now(); 
     Matrix<double> m3 = m1 * m2; 
     auto end = now(); 
     std::cout << milliseconds(begin, end) << "ms" << std::endl; 
    } 
    { 
     Matrix<Real<double> > m1(SIZE, Real<double>(1.0)); 
     Matrix<Real<double> > m2(SIZE, Real<double>(1.0)); 
     auto begin = now(); 
     Matrix<Real<double> > m3 = m1 * m2; 
     auto end = now(); 
     std::cout << milliseconds(begin, end) << "ms" << std::endl; 
    } 
} 

I (32)에 의해 매트릭스 승산 루프 코드 및 증분 K를 주석 처리하면 발현 템플릿을 세 번 이상 걸린다. 왜 이런 일이 일어날 지 아는 사람이 있습니까?

Intel Xeon E3-1225 V2의 Cygwin에서 GCC 5.4로 컴파일 중입니다.

Answer 1

세 가지 이유가 있습니다.

먼저 템플릿과 매크로를 혼합합니다. DEFINE_BINARY_OPERATOR 매크로를 만드는 것이 더 쉬울 수도 있지만 최적화를 잃을 수도 있습니다. 컴파일러가 템플릿 템플릿을 통해 클래스를 생성하도록 컴파일러를 유도하는 방법이 있습니다. 컴파일러가 매크로를 통해 수행 할 수없는 마술을 할 수도 있습니다.

두 번째로, 2 차원 벡터를 사용하고 있습니다. C++ FAQ은 Matrix 클래스를 배열 배열처럼 보이게 만들면 성능 문제가 발생할 수 있다고 설명합니다. 이 경우 3 차원 행렬을 작성하려고합니다. 특정 케이스에 대해 [][] 연산자 대신 일반 케이스의 경우 () 연산자를 사용하여 빌드 한 경우 저렴하고 더 쉬울 수 있습니다. 같은 섹션에서는 좀 더 일반화되고 효율적인 방식으로 Matrix 클래스를 구현하는 방법을 설명합니다.

1 차원 배열을 사용하여 다차원 배열을 "가짜"로 만드는 수학적 방법이 있습니다. This question에서는 방법을 설명하고 단일 수준의 간접 참조로 인해 약간의 오버 헤드가 줄어 듭니다.

셋째, 아마도 vector 클래스의 오버 헤드가 많을 것입니다. 이것은 단지 vector 대신에 배열을 사용하는 것이 더 나은 경우로, 벡터 사용의 편의성이 훨씬 뛰어나다는 점에서 그다지 효과적이지 않습니다.

마지막으로,이 루프는 불행히도 다항식 복잡성을 가지고 있습니다. 즉 위에서 말한 성능 문제가 큐브화될 것임을 의미합니다. 작은 배열의 경우 큰 문제는 아니지만 큰 배열의 경우 비용이 많이 듭니다. 아마도이 문제를 줄이기 위해 몇 가지 최적화 플래그를 켜거나 끌 필요가있을 것입니다.