Swisstable Hash に使われているビット演算の魔術 - methaneのブログGoogleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。 Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。 この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。 SSE2を使う場合 SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次の
