C++ 2-D 배열 최적화

Question

절대 최소 액세스 오버 헤드로 C++에서 2 차원 배열 (조밀 한 행렬)을 나타내는 방법이 필요합니다.

나는 다양한 리눅스/유닉스 기계와 gcc 버전에서 타이밍을 해왔다. 벡터의 STL 벡터로서 선언

vector<vector<double> > matrix(n,vector<double>(n)); 

및 배열로 선언보다 접근 5 %와 100 % 느린 사이 matrix[i][j] 통해 액세스 :

double *matrix = new double[n*n]; 

가 인라인 지수 함수 matrix[index(i,j)] 통해 액세스 여기서, index(i,j)은 i + n * j로 평가된다. STL을 사용하지 않고 2 차원 배열을 배열하는 다른 방법 - 각 행의 시작에 대한 n 개의 포인터 배열 또는 상수 크기로 스택에 모든 것을 정의 matrix[n][n] - 인덱스 함수와 거의 동일한 속도로 실행됩니다 .

최근 GCC 버전 (> 4.0)은 STL 벡터 벡터를 최적화가 켜져있을 때 STL 코드와 거의 동일한 효율로 컴파일 할 수있는 것처럼 보입니다. 그러나 이는 다소 기계에 따라 다릅니다.

가능하면 STL을 사용하고 싶지만 가장 빠른 솔루션을 선택해야합니다. 누구든지 GCC로 STL을 최적화 한 경험이 있습니까?

Answer 1

GCC를 사용하는 경우 컴파일러는 매트릭스 액세스를 분석하고 특정 경우 메모리의 순서를 변경할 수 있습니다.

-fipa-matrix-reorg 

매트릭스 납작하고 이조를 수행 마법의 컴파일러 플래그는 다음과 같이 정의된다. 행렬 병합은 을 사용하여 m 차원 행렬을 해당 동등한 n 차원 행렬 으로 대체합니다. 여기서 n은 < m입니다. 이렇게하면 행렬의 요소에 액세스하는 데 필요한 간접 지정의 수준이 줄어 듭니다. 두 번째 최적화는 행렬의 크기를 의 순서를 변경하려고 시도하는 인 행렬 중계로, 은 캐시 지역을 개선합니다. 최적화에는 fwhole-program 플래그가 필요합니다. 조 변경은 프로파일 링 정보가 사용 가능한 경우에만 사용할 수 있습니다.

-O2 또는 -O3에서는이 옵션을 사용할 수 없습니다. 당신은 그것을 스스로 전달해야합니다.

Answer 2

매트릭스가 1D STL 배열을 사용하고() 연산자를 재정 의하여 2D 매트릭스로 사용하는 것이 가장 빠를 것이라고 생각합니다.

그러나 STL에서는 크기가 조정되지 않는 숫자 배열에 대한 형식 인 valarray도 정의합니다. 또한 전체 작동에 대한 다양한 최적화 기능을 제공합니다. (INT ... 당신은 조각, 간접적 인 배열을 사용할 수 있습니다, 그리고

valarray<double> a; 

물론, 당신은 적 valarray을 상속 수) (자신의 연산자를 정의

는 인수로 숫자 형을 받아 적 valarray i, int j) ...

Answer 3

빠른 매트릭스/벡터 클래스를 제공하는 Boost.UBLAS를 사용하는 것이 좋습니다.

Answer 4

이것은 참조 지역 문제 일 가능성이 큽니다. vector은 new을 사용하여 내부 배열을 할당하므로 각 행은 각 블록의 헤더로 인해 메모리에서 적어도 약간 떨어져 있습니다. 메모리를 할당 할 때 이미 조각난 경우에는 멀리 떨어져있을 수 있습니다. 배열의 다른 행은 적어도 캐시 라인 오류를 일으키고 페이지 오류가 발생할 수 있습니다. 만약 당신이 정말로 불행하다면, 인접한 두 개의 행은 TLB 슬롯을 공유하는 메모리 라인에있을 수 있으며, 하나의 TLB 슬롯을 액세스하면 다른 TLB를 제거 할 수 있습니다.

대조적으로 다른 솔루션은 모든 데이터가 인접 해 있음을 보장합니다. 가능한 한 적은 수의 캐시 라인을 통과하도록 구조를 정렬하면 성능에 도움이됩니다.

vector은 크기 조정 가능 어레이로 설계되었습니다. 배열의 크기를 조정할 필요가 없으면 일반 C++ 배열을 사용하십시오. STL 작업은 일반적으로 C++ 배열에서 작동 할 수 있습니다.

배열을 올바른 방향, 즉 가로 방향이 아닌 가로 방향 (연속 메모리 주소)으로 이동하십시오. 이렇게하면 캐시 오류가 줄어 듭니다.

Answer 5

공정하게하려면 매트릭스에서 사용하는 알고리즘에 따라 다릅니다.

곱하기 및 덧셈 이외에 오버 헤드가 거의없고 캐시에 일관성있게 압축 된 데이터가 포함되어 있기 때문에 두 행으로 데이터에 액세스 할 때 두 배로 [n * m] 형식이 매우 빠릅니다.

알고리즘이 열에 데이터를 정렬하면 다른 레이아웃의 캐시 일관성이 훨씬 향상 될 수 있습니다. 귀하의 알고리즘이 매트릭스의 사분면에있는 데이터를 다른 레이아웃으로 액세스하는 것이 더 좋을 수도 있습니다.

사용중인 알고리즘 및 유형에 대한 조사를 수행하십시오. 이는 행렬이 매우 큰 경우에 특히 중요합니다. 캐쉬 미스가 각 주소에 액세스하기 위해 1 또는 2 개의 여분의 수학 연산을 필요로하는 것보다 성능을 해칠 수 있기 때문입니다.

Answer 6

벡터를 쉽게 수행 할 수 있습니다. < double> (n * m);

Answer 7

부스트에는 uBLAS 구현이 있습니다. 보세요.

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm

Answer 8

당신은 http://eigen.tuxfamily.org/에서 아이겐 C++ 템플릿 라이브러리를보고 할 수 있습니다. 벡터/행렬 계산을 최적화하기 위해 AltiVec 또는 sse2 코드를 생성합니다.

Answer 9

또 다른 관련 라이브러리 ++ 블리츠입니다 : http://www.oonumerics.org/blitz/docs/blitz.html

전격 ++가 배열 조작을 최적화 할 수 있도록 설계되었습니다.

Answer 10

나는 2 차원 배열 클래스를 선언함으로써 원시 이미지를 얻었습니다. 통상의 2 차원 어레이에서

가 원하는 요소 액세스 :

배열 [2] [3]. 이제 그 효과를 얻으려면 오버로드 된 [] 배열 접근자를 사용하는 클래스 배열을 사용해야합니다. 그러나 이것은 본질적으로 다른 배열을 반환 할 것이므로 두 번째 차원을 제공합니다.

이 접근법의 문제점은 이중 함수 호출 오버 헤드가 있다는 것입니다.

내가 한 방법은() 스타일 오버로드를 사용하는 것이 었습니다.

대신 배열 [2] [3] 대신이 스타일 배열 (2,3)을 변경해야합니다.

That() 함수는 매우 작았고 인라인되었는지 확인했습니다. 필요하면 http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

당신은 유형을 템플릿 수

은의 일반적인 개념이 링크를 참조하십시오.
차이점은 배열이 동적이라는 것입니다. 나는 선언하겠다고 선언했다. 그리고 저는 컬럼 캐시를 사용했기 때문에 다음 행이 바이트 시퀀스에서 어디에 있는지 알았습니다. 인접한 값에 액세스하기 위해 액세스가 최적화되었습니다. 이미지 처리를 위해이 값을 사용했기 때문입니다.

코드 없이는 설명하기가 어렵지만 기본적으로 결과는 C만큼 빠르며 이해하고 사용하기가 훨씬 쉽습니다.