Eigen C++ : 희소 행렬 조작의 성능

Question

누구나 Eigen sparse 행렬의 다음 동작을 설명 할 수 있습니까? aliasing과 lazy evaluation을 조사했지만이 문제를 개선 할 수없는 것 같습니다. 기술 사양 : g ++ 컴파일러와 최적화 플래그가없는 우분투 16.10에 최신 Eigen 안정 버전을 사용하고 있습니다.

가정한다 I는 다음과 같이 간단한 신원을 정의

SparseMatrix<double> spIdent(N,N); 
spIdent.reserve(N); 
spIdent.setIdentity(); 

다음 세위한 계산 시간을 그

spIdent-spIdent; 
spIdent*spIdent; 
spIdent - spIdent*spIdent; 

이러한 작업을 수행하고 측정한다. 내가 얻을 것은 두 작업이 빠르지 만 조합이 매우 낮다는 의미이

0 Computation time: 2.6e-05 
1 Computation time: 2e-06 
2 Computation time: 1.10706 

입니다. noalias() 메서드는 조밀도 행렬에 대해서만 정의되었으며, 플러스 예제에서는 그다지 차이가 ​​없습니다. 어떤 깨달음?

MCVE :

#include <iostream> 
#include <ctime> 
#include "../Eigen/Sparse" 

using namespace std; 
using namespace Eigen; 

int main() { 

unsigned int N=2000000; 

SparseMatrix<double> spIdent(N,N); 
spIdent.reserve(N); 
spIdent.setIdentity(); 

clock_t start=clock(); 
spIdent*spIdent; 
cout << "0 Computation time: " << float(clock() - start)/1e6 << '\n'; 

start=clock(); 
spIdent-spIdent; 
cout << "1 Computation time: " << float(clock() - start)/1e6 << '\n'; 

start=clock(); 
spIdent - (spIdent*spIdent); 
cout << "2 Computation time: " << float(clock() - start)/1e6 << '\n'; 

return 0; 

} 

Answer 1

그것은 게으른 평가, 음, 아주 게으른 그대로만큼을 최적화됩니다 너무 많이하지 않습니다. 제품을보십시오. 라고 코드는 (적어도이 컴퓨터에 포함 된 아이겐의 어떤 버전)입니다 : 제품의 표현 (즉 게으른) 반환

template<typename Derived> 
template<typename OtherDerived> 
inline const typename SparseSparseProductReturnType<Derived,OtherDerived>::Type 
SparseMatrixBase<Derived>::operator*(const SparseMatrixBase<OtherDerived> &other) const 
{ 
    return typename SparseSparseProductReturnType<Derived,OtherDerived>::Type(derived(), other.derived()); 
} 

. 이 표현식으로 아무것도 수행되지 않으므로 비용은 0입니다. 차이점도 마찬가지입니다. 이제 a-a*a 일 때 a*a은 표현식입니다. 그런 다음 operator-을 충족합니다. 이것은 오른쪽에 표현을 본다. 이 표현식은 operator-에서 사용하기 위해 임시 (즉, 비용 시간)로 평가됩니다. 임시로 평가하는 이유는 무엇입니까? 그들의 논리에 대해 this을 읽으십시오 ("두 번째 상황"검색).

operator-은 오른쪽과 같은 제품 식 CwiseBinaryOp이다.CwiseBinaryOp 수행하는 첫 번째 일은 회원에 오른쪽을 할당 할 수 있습니다 : 차례로 SparseMatrix 생성자를 호출

EIGEN_STRONG_INLINE CwiseBinaryOp(const Lhs& aLhs, const Rhs& aRhs, const BinaryOp& func = BinaryOp()) 
     : m_lhs(aLhs), m_rhs(aRhs), m_functor(func) 

(m_rhs(aRhs)) : 다시 올바른 operator=하는 것이다 (누군가를 호출

/** Constructs a sparse matrix from the sparse expression \a other */ 
template<typename OtherDerived> 
inline SparseMatrix(const SparseMatrixBase<OtherDerived>& other) 
    : m_outerSize(0), m_innerSize(0), m_outerIndex(0), m_innerNonZeros(0) 
{ 
    ... 
    *this = other.derived(); 
} 

나) 내가 틀렸다면 항상이 경우 평가를 트리거합니다.

Answer 2

음, 코드가 완전히 (I는 현재 g의 버전 ++ 및 -O3 세트로 테스트 한) 멀리 최적화됩니다 처음 두 문장에서 언급 한 사람으로. 이 경우 컴파일러는 수 없다는 것을 같아요

400ede: e8 9d fd ff ff   callq 400c80 <clock@plt> # timing begins 
    400ee3: 48 89 c5    mov %rax,%rbp 
    400ee6: 8b 44 24 58    mov 0x58(%rsp),%eax 
    400eea: 39 44 24 54    cmp %eax,0x54(%rsp) 
    400eee: c6 44 24 20 00   movb $0x0,0x20(%rsp) 
    400ef3: 48 89 5c 24 28   mov %rbx,0x28(%rsp) 
    400ef8: 48 89 5c 24 30   mov %rbx,0x30(%rsp) 
    400efd: 48 c7 44 24 38 00 00 movq $0x0,0x38(%rsp) 
    400f04: 00 00 
    400f06: c6 44 24 40 01   movb $0x1,0x40(%rsp) 
    400f0b: 0f 85 99 00 00 00  jne 400faa <main+0x22a> 
    400f11: 48 8d 4c 24 1f   lea 0x1f(%rsp),%rcx 
    400f16: 48 8d 54 24 20   lea 0x20(%rsp),%rdx 
    400f1b: 48 8d bc 24 90 00 00 lea 0x90(%rsp),%rdi 
    400f22: 00 
    400f23: 48 89 de    mov %rbx,%rsi 
    400f26: e8 25 1a 00 00   callq 402950 <_ZN5Eigen13CwiseBinaryOpINS_8internal20scalar_difference_opIdEEKNS_12SparseMatrixIdLi0EiEEKNS_19SparseSparseProductIRS6_S8_EEEC1ES8_RSA_RKS3_> 
    400f2b: 48 8d bc 24 a0 00 00 lea 0xa0(%rsp),%rdi 
    400f32: 00 
    400f33: e8 18 02 00 00   callq 401150 <_ZN5Eigen12SparseMatrixIdLi0EiED1Ev> 
    400f38: e8 43 fd ff ff   callq 400c80 <clock@plt> # timing ends 

:

400e78: e8 03 fe ff ff   callq 400c80 <clock@plt> # timing begins 
    400e7d: 48 89 c5    mov %rax,%rbp 
    400e80: e8 fb fd ff ff   callq 400c80 <clock@plt> # timing ends 

FOP 호출되는 아이겐 라이브러리 코드를 발생하는 일이 실제로이 세 번째 부분 : 해체는 두 번째 문이 표시 처음 2 가지 경우와는 달리 계산 결과가 사용되지 않는다는 것을 알아 내야합니다.

당신이 documentation을 살펴 경우에, 당신은 희소 행렬에 + 같은 간단한 작업이 매트릭스하지만 결과를 나타내는 CwiseUnaryOp을 돌려 볼 수 있습니다. 이 클래스를 어딘가에서 사용하지 않으면 결과 행렬이 생성되지 않는다는 것을 알 수 있습니다.

Answer 3

@ hfhc2가 언급 한 것처럼 코드의 처음 두 문장은 결과가 나머지에는 필요하지 않으므로 컴파일러에서 완전히 최적화됩니다. 세 번째 명령문에서는 보조 중간 변수가 생성되어 임시 결과 인 spIdent*spIdent을 저장할 가능성이 가장 높습니다. 명시 복사 할당을 포함하는 다음 예를 고려, 명확를 참조하십시오 :이다 (컴파일러 최적화없이)

#include <iostream> 
#include <ctime> 
#include <Eigen/Sparse> 

using namespace std; 
using namespace Eigen; 

int main() { 

    const unsigned int N = 2000000; 

    SparseMatrix<double> spIdent(N,N); 
    SparseMatrix<double> a(N,N), b(N,N), c(N,N); 

    spIdent.reserve(N); 
    spIdent.setIdentity(); 

    clock_t start = clock(); 
    a = spIdent*spIdent; 
    cout << "0 Computation time: " << float(clock() - start)/1e6 << endl; 

    start = clock(); 
    b = spIdent-spIdent; 
    cout << "1 Computation time: " << float(clock() - start)/1e6 << endl; 

    start = clock(); 
    c = a - b; 
    cout << "2 Computation time: " << float(clock() - start)/1e6 << endl; 

    return 0; 

} 

측정 된 시간을 [오픈 수세 12.2 (x86_64의), g ++ 4.7.1, 인텔 2core 2GHz의 CPU에 대한 ] :

0 Computation time: 1.58737 
1 Computation time: 0.417798 
2 Computation time: 0.428174 

매우 합리적인 것처럼 보입니다.