SwissTable
Googleが開発したハッシュテーブルの実装
hashbrownはRustでの実装
absl::Hash
absl::flat_hash_map
absl::flat_hash_set
以下をSwissTableと呼んでいる。
absl::flat_hash_map
absl::flat_hash_set
absl::node_hash_map
absl::node_hash_set
参考
from:
mattn_jp Go の map の実装が hashmap から SwissTable になる可能性が出てきた。今の実装から仕様を変える事なしに SwissTable に置き換える事が可能で、それでありながら read/write 共に 20～50% 改善、iterate が 10% 改善。https://t.co/e0nF4z4pCZ
runtime: use SwissTable · Issue #54766 · golang/go
abseil / Swiss Tables Design Notes
SwissTableの設計について？
テーブル内の項目検索の際にSSE命令を使ってい並列化している
雪崩効果
abseil / Swiss Tables and absl::Hash
abseil / Abseil Containers
STLコンテナの代替で、Avseilコンテナは効率的なハッシュテーブルを作れる。
Swisstable Hash に使われているビット演算の魔術 - methaneのブログ
SIMD
SSE2
CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
https://www.youtube.com/watch?v=ncHmEUmJZf4
#CS(情報科学) #C/C++