최근에 회사에서 다양한 데이터 구조에 대한 벤치 마크를 실행했기 때문에 한 마디도해야한다고 생각합니다. 무언가를 올바르게 벤치마킹하는 것은 매우 복잡합니다.

벤치마킹

웹에서 우리는 잘 설계된 벤치 마크를 거의 찾을 수 없습니다. 오늘까지 저는 저널리스트 방식으로 수행 된 벤치 마크 만 찾았습니다 (매우 신속하고 카펫 아래에서 수십 개의 변수를 휩쓸고 있음).

1) 캐시 워밍에 대해 고려해야합니다.

벤치 마크를 실행하는 대부분의 사람들은 타이머 불일치를 두려워하므로 물건을 수천 번 실행하고 전체 시간을 소비합니다. 모든 작업에 대해 동일한 수천 번을 수행하도록주의 한 다음 비교 가능한 것으로 간주합니다.

사실은 캐시가 따뜻하지 않고 작업이 한 번만 호출 될 가능성이 있기 때문에 현실 세계에서는 거의 의미가 없습니다. 따라서 RDTSC를 사용하여 벤치마킹하고 한 번만 호출하는 시간을 측정해야합니다. 인텔은 RDTSC를 사용 하는 방법을 설명 하는 문서 를 만들었습니다 (cpuid 명령을 사용하여 파이프 라인을 플러시하고 프로그램 시작시이를 안정화하기 위해 적어도 3 번 호출).

2) RDTSC 정확도 측정

또한 다음을 수행하는 것이 좋습니다.

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

이것은 불일치 측정기이며 때때로 -10 ** 18 (64 비트 첫 음수 값)을 얻는 것을 피하기 위해 모든 측정 값의 최소값을 취합니다.

인라인 어셈블리가 아닌 내장 함수를 사용합니다. 첫 번째 인라인 어셈블리는 오늘날 컴파일러에서 거의 지원되지 않지만 무엇보다도 컴파일러는 내부를 정적으로 분석 할 수 없기 때문에 인라인 어셈블리 주변에 완전한 순서 장벽을 생성합니다. 따라서 이것은 특히 물건을 호출 할 때 실제 세계를 벤치마킹하는 문제입니다. 한번. 따라서 intrinsic이 여기에 적합합니다. 컴파일러가 명령을 자유롭게 재정렬하는 것을 방해하지 않기 때문입니다.

3) 매개 변수

마지막 문제는 사람들이 일반적으로 너무 적은 시나리오 변형을 테스트한다는 것입니다. 컨테이너 성능은 다음에 의해 영향을받습니다.

1. 할당 자
2. 포함 된 유형의 크기
3. 포함 된 유형의 복사 작업, 할당 작업, 이동 작업, 구성 작업의 구현 비용.
4. 컨테이너의 요소 수 (문제의 크기)
5. 유형에는 사소한 3- 작업이 있습니다.
6. 유형은 POD입니다

포인트 1은 컨테이너가 수시로 할당되기 때문에 중요하며, CRT “new”또는 풀 할당이나 freelist 또는 기타와 같은 일부 사용자 정의 작업을 사용하여 할당하는 경우 매우 중요합니다.

( pt 1에 관심이있는 사람들 은 시스템 할당 자 성능 영향에 대한 gamedev의 미스터리 스레드에 참여하세요. )

포인트 2는 일부 컨테이너 (예 : A)가 물건을 복사하는 데 시간을 낭비하고 유형이 클수록 오버 헤드가 커지기 때문입니다. 문제는 다른 컨테이너 B와 비교할 때 A가 작은 유형의 경우 B를 이기고 큰 유형의 경우 잃을 수 있다는 것입니다.

포인트 3은 비용에 일부 가중치를 곱한다는 점을 제외하면 포인트 2와 동일합니다.

포인트 4는 캐시 문제와 혼합 된 빅 O의 문제입니다. 일부 복잡하지 않은 컨테이너는 적은 수의 유형에 대해 복잡도가 낮은 컨테이너를 크게 능가 할 수 있습니다 (예 map: vector캐시 지역 성은 좋지만 map메모리 조각화). 그런 다음 일부 교차 지점에서 포함 된 전체 크기가 주 메모리로 “누수”되기 시작하고 캐시 미스를 유발하고 점근 적 복잡성이 느껴지기 시작하기 때문에 손실됩니다.

요점 5는 컴파일러가 컴파일 타임에 비어 있거나 사소한 것을 제거 할 수 있다는 것입니다. 컨테이너가 템플릿 화되어 있기 때문에 일부 작업을 크게 최적화 할 수 있으므로 각 유형은 자체 성능 프로필을 갖습니다.

포인트 5와 동일한 포인트 6, POD는 복사 구성이 단지 memcpy라는 사실에서 이점을 얻을 수 있으며 일부 컨테이너는 부분 템플릿 전문화 또는 SFINAE를 사용하여 T의 특성에 따라 알고리즘을 선택하여 이러한 경우에 대한 특정 구현을 가질 수 있습니다.

평면지도 정보

분명히 플랫 맵은 Loki AssocVector와 같은 정렬 된 벡터 래퍼이지만 C ++ 11과 함께 제공되는 일부 보완 현대화를 통해 이동 시맨틱을 활용하여 단일 요소의 삽입 및 삭제를 가속화합니다.

이것은 여전히 ​​주문 된 컨테이너입니다. 대부분의 사람들은 일반적으로 주문 부분이 필요하지 않으므로unordered.. .

아마도 당신이 필요하다고 생각 했습니까 flat_unorderedmap? 그것은 다음과 같을 것입니다google::sparse_map 그-오픈 주소 해시 맵과 같은 또는 뭔가.

열린 주소 해시 맵의 문제는 rehash 모든 것을 새로운 확장 평지에 복사해야하는 반면, 표준 무순 맵은 해시 인덱스를 다시 생성해야하는 반면 할당 된 데이터는 그대로 유지된다는 것입니다. 물론 단점은 메모리가 지옥처럼 조각화되어 있다는 것입니다.

열린 주소 해시 맵에서 재해시의 기준은 용량이 버킷 벡터의 크기에 부하 계수를 곱한 값을 초과하는 경우입니다.

일반적인 부하율은 다음과 같습니다 0.8. 따라서 채우기 전에 해시 맵의 크기를 미리 조정할 수 있다면 항상 크기를 미리 조정해야합니다. intended_filling * (1/0.8) + epsilon이렇게하면 채우기 중에 모든 것을 허위로 다시 해시하고 다시 복사 할 필요가 전혀 없습니다.

닫힌 주소 맵 ( std::unordered..) 의 장점 은 이러한 매개 변수에 대해 신경 쓸 필요가 없다는 것입니다.

그러나 boost::flat_map는 정렬 된 벡터입니다. 따라서 항상 log (N) 점근 복잡도를 가지게되며 이는 개방 주소 해시 맵 (상각 된 일정 시간)보다 좋지 않습니다. 이것도 고려해야합니다.

벤치 마크 결과

이것은 ( int키 및 __int64/ somestruct를 값으로) 다른 맵과 관련된 테스트 std::vector입니다.

테스트 유형 정보 :

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

삽입

편집하다:

내 이전 결과에는 버그가 포함되어있었습니다. 그들은 실제로 주문 된 삽입을 테스트했는데, 이는 평면지도에서 매우 빠른 동작을 나타 냈습니다.
이 결과는 흥미 롭기 때문에 나중에이 페이지에 남겨 두었습니다.

이것은 올바른 테스트입니다.

구현을 확인했지만 여기에 플랫 맵에 구현 된 지연된 정렬과 같은 것은 없습니다. 각 삽입은 즉시 정렬되므로이 벤치 마크는 점근 적 경향을 보여줍니다.

맵 : O (N * log (N))
해시 맵 : O (N)
벡터 및 플랫 맵 : O (N * N)

경고 : 이하의 두 테스트 std::map모두 flat_map의가되는 버그가 실제로 테스트하는 것은 삽입 명령 (다른 컨테이너에 대한 임의 삽입 대 네, 죄송 혼란.)

순서대로 삽입하면 뒤로 밀고 매우 빠르다는 것을 알 수 있습니다. 그러나 내 벤치 마크의 차트에 나와 있지 않은 결과를 보면 이것이 역 삽입에 대한 절대적 최적성에 가깝지 않다고 말할 수도 있습니다. 10k 요소에서 사전 예약 된 벡터에서 완벽한 역 삽입 최적 성이 얻어집니다. 이것은 우리에게 3 백만 사이클을줍니다. 여기에서 주문 된 삽입에 대해 4.8M을 관찰합니다 flat_map(따라서 최적의 160 %).

분석 : 이것이 벡터에 대한 ‘무작위 삽입’이라는 것을 기억하십시오. 따라서 각 삽입에서 데이터의 절반 (평균)을 위로 (1 요소 1 요소) 이동해야하는 엄청난 10 억 사이클이 발생합니다.

3 개 요소 무작위 검색 (클럭이 1로 재 정규화 됨)

크기 = 100

크기 = 10000

되풀이

100 개 이상 (MediumPod 유형 만 해당)

10000 이상 (MediumPod 유형 만 해당)

최종 소금

결국 나는 “Benchmarking §3 Pt1″(시스템 할당 자)로 돌아가고 싶었습니다. 최근에 개발 한 오픈 주소 해시 맵 의 성능에 대해 수행하고있는 실험 에서 일부 std::unordered_map사용 사례 에서 Windows 7과 Windows 8 간의 성능 차이를 3000 % 이상 측정했습니다 ( 여기에서 설명 ).
위의 결과 (Win7에서 생성됨)에 대해 독자에게 경고하고 싶습니다. 마일리지가 다를 수 있습니다.

친애하는

---

답변