문제

C ++에서 복식의 2D 배열 (조밀 한 매트릭스)을 나타내는 방법이 필요하며 절대 최소 액세스 오버 헤드.

다양한 Linux/Unix Machines 및 GCC 버전에서 약간의 타이밍을 수행했습니다. 벡터의 STL 벡터는 다음과 같이 선언했습니다.

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

그리고 접근 matrix[i][j] 다음과 같이 선언 된 배열보다 액세스가 5%에서 100% 더 느립니다.

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

인라인 인덱스 기능을 통해 액세스합니다 matrix[index(i,j)], 어디 index(i,j) i+n*j로 평가합니다. STL없이 2D 배열을 배열하는 다른 방법 - 각 행의 시작 부분에 N 포인터의 배열 또는 스택의 모든 것을 일정한 크기로 정의하는 방법 matrix[n][n] - 인덱스 함수 메소드와 거의 동일한 속도로 실행하십시오.

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

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

도움이 되었습니까?

해결책

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

-fipa-matrix-reorg

매트릭스 평평하고 전송을 수행하십시오. 매트릭스 평탄화는 m 차원 행렬을 동등한 n- 차원 행렬로 대체하려고 시도합니다. 여기서 n <m. 이는 행렬의 요소에 액세스하는 데 필요한 간접 수준을 줄입니다. 두 번째 최적화는 캐시 위치를 향상시키기 위해 행렬의 차수 순서를 변경하기 위해 ATTEMPS를 전달하는 행렬 전환입니다. 두 최적화 모두 fwhole 프로그램 플래그가 필요합니다. 프로파일 링 정보가 불가능한 경우에만 전환이 가능합니다.

이 옵션은 -o2 또는 -o3에 의해 활성화되지 않습니다. 당신은 그것을 직접 통과해야합니다.

다른 팁

내 추측은 매트릭스의 경우 1D STL 어레이를 사용하고 () 연산자를 2D 행렬로 사용하는 것입니다.

그러나 STL은 또한 부적합 할 수없는 숫자 배열 인 Valarray에 대한 유형을 특별히 정의합니다. 또한 현장 운영에 대한 다양한 최적화가 있습니다.

Valarray는 인수로 수치 유형을 받아들입니다. 

valarray<double> a;

그런 다음 슬라이스, 간접 배열을 사용할 수 있습니다. 물론 Valarray를 상속하고 2D 어레이에 대한 Operator () (int i, int j)를 정의 할 수 있습니다 ...

아마도 이것은 회의 지역 문제 일 것입니다. vector 용도 new 내부 배열을 할당하려면 각 블록의 헤더로 인해 각 행이 메모리가 약간 떨어집니다. 메모리가 이미 할당 될 때 이미 조각화 된 경우 장거리 떨어져있을 수 있습니다. 배열의 다른 행은 적어도 캐시 라인 오류가 발생할 가능성이 높으며 페이지 오류가 발생할 수 있습니다. 당신이 정말로 운이 좋지 않은 경우, 두 개의 인접한 행이 TLB 슬롯을 공유하는 메모리 라인에있을 수 있고 하나에 액세스하면 다른 하나를 퇴거시킬 수 있습니다.

반대로 다른 솔루션은 모든 데이터가 인접 해 있음을 보장합니다. 구조를 정렬하면 가능한 한 적은 수의 캐시 라인을 가로 지르는 경우 성능에 도움이 될 수 있습니다.

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

어레이를 올바른 방향으로 걸어 가십시오 (예 : 아래로가 아닌 연속 메모리 주소). 이렇게하면 캐시 결함이 줄어 듭니다.

내 권장 사항은 빠른 매트릭스/벡터 클래스를 제공하는 roost.ublas를 사용하는 것입니다.

공정하다는 것은 매트릭스에 사용하는 알고리즘에 따라 다릅니다.

이중 이름 [n*m] 형식은 곱셈과 추가 외에도 거의 오버 헤드가없고 캐시에서 일관된 데이터가 포장되어 있기 때문에 행으로 데이터에 액세스 할 때 매우 빠릅니다.

알고리즘 액세스 열 순서 데이터에 따라 다른 레이아웃은 캐시 일관성이 훨씬 우수 할 수 있습니다. 매트릭스의 사분면에서 알고리즘에 액세스하는 경우 다른 레이아웃도 더 나을 수 있습니다.

사용중인 사용법 및 알고리즘 유형에 대한 연구를 수행하십시오. 캐시 미스가 각 주소에 액세스하기 위해 1 ~ 2 개의 추가 수학 작업이 필요한 것보다 성능을 손상시킬 수 있으므로 매트릭스가 매우 크면 특히 중요합니다.

벡터 <bouble> (n*m)을 쉽게 할 수 있습니다.

Eigen C ++ 템플릿 라이브러리를보고 싶을 수도 있습니다. http://eigen.tuxfamily.org/ . 벡터/매트릭스 계산을 최적화하기 위해 Altivec 또는 SSE2 코드를 생성합니다.

부스트에는 UBLAS 구현이 있습니다. 볼만한 가치가 있습니다.

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

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

Blitz ++는 배열 조작을 최적화하도록 설계되었습니다.

나는 내 자신의 2 차원 배열 클래스를 선언하여 원시 이미지를 위해이 시간을 다시 수행했습니다.

일반 2D 배열에서는 다음과 같은 요소에 액세스 할 수 있습니다.

배열 [2] [3]. 이제 그 효과를 얻으려면 오버로드 된 [] 배열 액세서가있는 클래스 배열이 있습니다. 그러나 이것은 본질적으로 다른 배열을 반환하여 두 번째 차원을 제공합니다.

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

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

배열 [2] [3] 대신에 변경 하여이 스타일 배열 (2,3)을 수행했습니다.

그 () 기능은 매우 작았으며 나는 그것이 감소했는지 확인했습니다.

일반적인 개념은이 링크를 참조하십시오.http://www.learncpp.com/cpp-tutorial/99-overloading-the-parenthesis-operator/

필요한 경우 유형을 템플릿 할 수 있습니다.
내가 가진 차이점은 내 배열이 역동적이라는 것입니다. 나는 내가 선언 할 숯 메모리 블록이 있었다. 그리고 열 캐시를 사용했기 때문에 다음 행이 시작된 바이트 시퀀스에서 어디에서 시작되었는지 알았습니다. 이미지 처리에 사용하고 있었기 때문에 인접 값에 액세스하기 위해 액세스가 최적화되었습니다.

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

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top