Performance Comparison in multithread environment: robin_hood::unordered_map vs. tbb::concurrent_hash_map

 

robin_hood::unordered_map

robin_hood::unordered_map is said to be among the fastest in replacements for std::unordered_map. Personally I found that both in VS2019 and Ubuntu 20.04 the map reduces about half of the time spent against std::unordered_map. However, considering its birth and origin, in multithreaded environment we need to serialize the access to the hashmap using something like mutex. Or, the angry Lord of Segmentation Fault will fire at you(......).

tbb::concurrent_hash_map

Well, if you're in multithreading environment, you can't avoid this: Intel's proud production, tbb::concurrent_hash_map from oneTBB (Threading Building Block). In multithreaded environment container classes from TBB is quite decent. Certainly, I'm sure Intel devoted the best efforts to TBB, as its performance is about similar to std::unordered_map, if I compare time spent for the operation.

Fastest in Single Thread vs. Optimized for Multithread

One shows the best speed in single thread environment, and the other is optimized for multithreading. Then one thing: what if we apply something like std::shared_mutex to robin_hood::unordered_map? Wouldn't it be faster if there are more read than write?

OK OK. I know it's nerdy, but you know, ....... a lot of programmers are nerds. Right? So I applied that to my current development. The program's read-write ratio is about 3:1, and I applied std::shared_mutex.

The winner? TIE(oops). The time spent for both libraries was about the same or similar.

What's Your Choice?

Anyway it depends(tm), I concluded tbb:concurrent_hash_map is better. I think tbb::concurrent_has_map will show better performance if there are more requests, and you can avoid any mistakes on implementation with with its own syntax for forced data lock.

For some time being, I'd reside on tbb::concurrent_hash_map.

One More Thing: QReadWriteLock vs. std::shared_mutex (C++17)

Oh yeah. Another nerdy test. For this I just had to swap lock/mutex only so I did it too. And unexpectedly, std::shared_mutex won this time. Though the Qt Company and the community did a lot of efforts to optimize QReadWriteLock(e.g. https://codereview.qt-project.org/c/qt/qtbase/+/140322/ and https://woboq.com/blog/qreadwritelock-gets-faster-in-qt57.html), after some years there seems to be better(and standard) alternative.

 

Yet anyway, thanks for your hard work, Qt team!

멀티스레드 환경에서의 성능 비교: robin_hood::unordered_map vs. tbb::concurrent_hash_map

robin_hood::unordered_map

robin_hood::unordered_map은 std::unordered_map을 대체하는 hashmap 중 가장 속력이 빠른 라이브러리로 알려져 있습니다. 제 개인적인 테스트로는 VS2019 및 Ubuntu 20.04 환경 모두에서 std::unordered_map에 대비하여 수행시간이 약 절반 수준으로 줄어들더군요. 하지만 이것도 태생이 태생이라, 멀티스레드에서 사용하기 위해서는 mutex 등을 사용해서 접근을 제어해야 합니다. 안 그랬다간 바로 segmentation fault의 불호령이 떨어집니다(.....).

tbb::concurrent_hash_map

한편, 멀티스레드 환경에 편리하게 사용하기 위한 hashmap이면 역시 인텔의 자랑인 oneTBB (Threading Building Block)의 tbb:concurrent_hash_map을 빼놓을 수가 없습니다. 멀티스레딩 환경에서 접근제어를 신경쓰지 않고 사용하기에는 역시 TBB의 컨테이너 클래스들이 가장 무난하다 하지 않을 수 없겠습니다. 확실히 인텔이 TBB에 신경을 각별히 쓴게 보이는 것이, std::unordered_map과 성능이 거의 비슷합니다. 각 기능별 소요시간이 std::unordered_map과 거의 똑같더군요.

싱글스레드 최속 vs. 멀티스레드 최적

한쪽은 싱글스레드 환경 한정으로 속도면에서는 최강자이고, 다른 한 쪽은 멀티스레딩 환경에서 최적화된 성능을 보여줍니다. 그럼 문득 드는 생각 하나...... robin_hood::unordered_map에다가 std::shared_mutex같은걸 씌우면, 어쩌면 읽기가 쓰기보다 더 많은 환경에서는 oneTBB보다 더 빠를 수도 있지 않을까?

아니 뭐..... 뻘짓인건 알지만, 그래도 길고 짧은건 역시 대봐야 아는 거잖아요? 해서 제가 현재 개발중인 프로그램에 한번 적용해 봤습니다. 해당 프로그램은 읽기와 쓰기 비율이 약 3:1 정도로 추산되고, 접근제어에는 std::shared_mutex를 사용했습니다.

그리고 테스트 결과는...... 승자가 없습니다. robin_hood::unordered_map과 tbb:concurrent_hash_map 모두 소요시간이 비슷하더군요.

당신의 선택은?

프로그램의 구조에 따라 다르겠지만, 전 tbb::concurrent_hash_map이 더 낫겠다는 판단을 내렸습니다. 리소스에 대한 접근 요청이 많아질수록 tbb::concurrent_hash_map이 더 우세할 것 같기도 하고, 고유 문법을 통해 리소스 접근시 data lock을 강제하기 때문에 구현상의 실수가 더 줄어들겠다는 것이 저의 판단입니다.

최소한 당분간 멀티스레드 환경에서는 tbb:concurrent_hash_map을 쓰게 될 것 같네요.

부록: QReadWriteLock vs. std::shared_mutex (C++17)

길고 짧은건 역시 대봐야 합니다. 이왕 하는김에, 저 두 가지 사이에서도 뭔가 속도 차이가 있을까 싶은 생각이 들어서 저 두 가지도 실험해봤습니다. 그리고 여기선 std::shared_mutex가 승리했습니다.

Qt Company와 커뮤니티가 QReadWriteLock을 최적화하기 위해 갖은 노력을 다 하긴 했습니다만(예: https://codereview.qt-project.org/c/qt/qtbase/+/140322/ and https://woboq.com/blog/qreadwritelock-gets-faster-in-qt57.html), 몇년 뒤에 더 좋은-그리고 표준화된- 대안이 나온 것 같네요.

 

뭐 어찌됐건, 전 Qt의 모든 노력과 그 결과물을 존중합니다. 그리고 저 또한 그 위에 얹혀(?) 살고 있기도 하고요(웃음).