이 글은 2021년 10월 28일에 제 이전 블로그에 올렸던 글입니다.
https://codenested.blogspot.com/2021/10/robinhoodunorderedmap-vs.html
참고로, 2024년 현재 robin_hood::unordered_map는 archiving 된 상황이고, 저는 Qt와 척을 좀 지고 있습니다(lol).

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의 모든 노력과 그 결과물을 존중합니다. 그리고 저 또한 그 위에 얹혀(?) 살고 있기도 하고요(웃음).