어느 것이 가장 빠릅니까? boost :: multi_array 또는 std :: vector?

Question

어느 것이 가장 빠릅니까? A boost::multi_array 또는 std::vector? 루프 내에서 매우 빠르게 그리고 매우 자주 액세스해야하는 3 차원으로 17.179.869 요소를 저장합니다 (상수는 아님). 가장 실적이 좋은 것은 무엇입니까? std::vector 또는 boost::multi_array?

(나는 두 번째 내에서 수행 할 수 있지만, 나는 나노초 차이가 많은 시간을 절약 할 수 있기 때문에 가능한 한 효율적으로하고 싶은 기대하지 않습니다.)

Answer 1

최선의 충고는 벤치 마크이다 너 혼자. 당신이 일정한 크기를 갖고있는 것 같다 있기 때문에 어떤 경우

는 다른 솔루션이 있습니다 :

• 일반 C 배열 (. 예를 들어 int data[X][Y][Z])
• 보통 한 사용자가 스스로 지수를 계산하는 차원 C 배열, 예를 들어 X*W*H + Y*W + Z는, 기본적으로 내가 추측 STL 컬렉션
• std::vector을에서 가져온 일부 synctactic 설탕과 C++ 배열 상황
• std::array에 편리하게 될 수 있습니다 시도 할 수있는 첫 번째 해결책
• boost::multi_array 이것은 N 차원 배열을 지원하기위한 것이므로 목적에 따라 잔인 할 수 있지만 벡터와 비교할 때 데이터의 지역성이 좋습니다.

Answer 2

이러한 라이브러리 벡터 클래스는 사용하기 쉽고 상대적으로 오류가 없도록 설계되었습니다. 그들은 디자인 내에서 가능한만큼 빠르지 만, 직접 할 필요는 없습니다 (손으로 코딩 한 어셈블리 제외). 당신이 말하는 크기 (2e10 요소)의 경우, 사용자 친화보다 효율성에 더 관심이 있습니다. 가장 안쪽의 루프가 요소 당 계산을 거의하지 않는다면 인덱싱 계산식이 우세한 것으로 나타납니다. 은 언 롤링과 포인터 스테핑을 제안합니다. (아마 당신은 몇 가지 풀기를 할 컴파일러 믿을 수,하지만 난 괜찮은 남자에 대해 걱정하지 않는다.)

Answer 3

확실히 알 수있는 유일한 방법은 모두를 시도하고 코드를 프로파일 링하는 것입니다. 그러나 아이디어의 낱단으로, 이것은 당신이 찾을 것이라고 생각합니다.

1. 처리중인 많은 요소 (2e10 이상)의 경우 요소에 대한 액세스가 CPU 캐시에 해당 요소를로드하기위한 캐시 압력만큼 중요하지는 않습니다. 프리 페처 (prefetcher)는 거기에 앉아서 그 요소들을로드하려고 시도 할 것이고, 이것은 시간의 상당 부분을 차지할 것입니다.
2. 2 (또는 3D) 비 연속적 C 배열에 액세스하면 CPU가 메모리의 다른 부분에서 물건을 가져와야합니다. boost :: multi_array는 연속적인 블록으로 저장하면서 장면을 다소 해결합니다. 하지만 그렇게하려면 오버 헤드가 있습니다. @Jack이 말했듯이 인덱스가있는 일반 1D 배열이 가장 좋으며 인덱싱을 최소화하기 위해 작업을 수행 할 수도 있습니다 (예 : 메모)
3. 루프 내에서 수행하는 작업이 타이밍에 상당한 영향을 미칩니다. 분기 예측기가 가장 큰 기여자가 될 것입니다. 간단한 수학 연산 인 경우 if/else 문을 사용하면 최상의 성능을 얻을 수 없으며 컴파일러는이를 SSE 명령어로 최적화 할 가능성이 높습니다.당신이 복합 형 (int/float/char 대신에)을 가지고 있다면 접근을 최적화하기 위해 그들을 배치해야 할 것입니다.
4. 나는 거의 제안 할 것이고, 양쪽 다 시도해보고, 당신의 루프가 쓰여지는 새로운 SO 질문으로 돌아와 그 부분을 최적화하는 방법을 묻는다. 거의 항상 컴파일러는 의도를 확실히 알 수있는 힌트를 얻을 수 있습니다.
하루의 끝에서

, 그것을 시도하고 당신이 걱정하는 경우