概要 marisa-trie の初期版を公開してから約 2 年になるわけですが，いまだに改良の余地があります．最近は，互換性のことを考慮して，データ構造に手を加えない範囲で改良をしてきました（※）．個別の改良は効果の薄いものばかりですが，古い実装と最新の実…

BitVector の select に SSE2 を使ってみる - やた＠はてな日記 の続きです．変更箇所が極わずかなので，説明は省略します．SSE2 を使わなくても分岐をなくすことができました．めでたしめでたし． SSE2 命令を使うバージョン std::size_t find_ith_1_bit(st…

最近は同じような内容ばかりでアレなのですが，BitVector の select に SSE2 を使ってみる - やた＠はてな日記 の続きです． 概要 前回の記事で「PMOVMSKB を使うより BSR を使った方が速いかも…」と書いたので，それを検証してみました．残念ながら，結論は…

marisa-trie に SSE2, SSSE3 を使ってみた - やた＠はてな日記，marisa-trie に SSE2, SSSE3 を使ってみた（続き） - やた＠はてな日記 の続きです． はじめに BitVector の select に SSE2 を導入することで高速化したわけですが，本記事では select のどこ…

概要 前回の記事を書いた後，有効にする命令セットをいろいろと試してみたところ，gcc と clang では傾向が異なることが分かりました．gcc では SSE4.1 を有効にすると速くなりましたが，clang では SSE4.1 を有効にしてもほとんど変化しませんでした． また…