boost :: flat_map 및 map 및 unordered_map과 비교 한 성능

boost :: flat_map 및 map 및 unordered_map과 비교 한 성능

---

메모리 지역성이 캐시 적중으로 인해 성능을 크게 향상 시킨다는 것은 프로그래밍에서 상식입니다. 최근 boost::flat_map에지도의 벡터 기반 구현이 무엇인지 알아 냈습니다 . 당신의 전형적인만큼 인기가하지 않는 것 map/ unordered_map내가 어떤 성능 비교를 찾을 수 없어 있도록. 어떻게 비교하고 최상의 사용 사례는 무엇입니까?

감사!

---

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

벤치마킹

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

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 = Aska::Min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = Aska::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

삽입

편집하다:

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

I have checked the implementation, there is no such thing as a deferred sort implemented in the flat maps here. Each insertion sorts on the fly, therefore this benchmark exhibits the asymptotic tendencies:

map : O(N * log(N))
hashmaps : O(N)
vector and flatmaps : O(N * N)

Warning: hereafter the 2 tests for std::map and both flat_maps are buggy and actually test ordered insertion (vs random insertion for other containers. yes it's confusing sorry):

We can see that ordered insertion, results in back pushing, and is extremely fast. However, from non-charted results of my benchmark, I can also say that this is not near the absolute optimality for a back-insertion. At 10k elements, perfect back-insertion optimality is obtained on a pre-reserved vector. Which gives us 3Million cycles; we observe 4.8M here for the ordered insertion into the flat_map (therefore 160% of the optimal).

Analysis: remember this is 'random insert' for the vector, so the massive 1 billion cycles comes from having to shift half (in average) the data upward (one element by one element) at each insertion.

Random search of 3 elements (clocks renormalized to 1)

in size = 100

in size = 10000

Iteration

over size 100 (only MediumPod type)

over size 10000 (only MediumPod type)

Final grain of salt

In the end I wanted to come back on "Benchmarking §3 Pt1" (the system allocator). In a recent experiment I am doing around the performance of an open address hash map I developed, I measured a performance gap of more than 3000% between Windows 7 and Windows 8 on some std::unordered_map use cases (discussed here).
Which makes me want to warn the reader about the above results (they were made on Win7): your mileage may vary.

best regards

---

From the docs it seems this is analogous to Loki::AssocVector which I'm a fairly heavy user of. Since it's based on a vector it has the characteristics of a vector, that is to say:

• Iterators gets invalidated whenever size grows beyond capacity.
• When it grows beyond capacity it needs to reallocated and move objects over, ie insertion isn't guaranteed constant time except for the special case of inserting at end when capacity > size
• Lookup is faster than std::map due to cache locality, a binary search which has the same performance characteristics as std::map otherwise
• Uses less memory because it isn't a linked binary tree
• It never shrinks unless you forcibly tell it to ( since that triggers reallocation )

The best use is when you know the number of elements in advance ( so you can reserve upfront ), or when insertion / removal is rare but lookup is frequent. Iterator invalidation makes it a bit cumbersome in some use cases so they're not interchangeable in terms of program correctness.

참고 URL : https://stackoverflow.com/questions/21166675/boostflat-map-and-its-performance-compared-to-map-and-unordered-map