2016www.adventar.orgの11日目の記事です。ビット単位のunpackC++の固定長ビット配列を扱うクラスstd::bitsetを例として解説します。result;}要は2つのビット列から交互に1ビットずつ取ってきたデータを生成します。今回は簡単のため128ビット固定とします。Extensions)を利用します。SSE4.2がありますがここではまとめてSSEと呼ぶことにします)SSEを用いると128ビット単位で算術演算、ビット演算、シャッフルなど様々な操作を行うことができます。Swapを使ってunpackするのがぱっと思いつく実装でしょうか。intrinsicsを使って実装してみます。1);}pdepビット演算に詳しい人ならBMIという拡張命令セットにpdepという命令があってこれが使えるということを思いつくかもしれません。UINT64_C(0xAAAAAAAAAAAAAAAA)));}pclmulqdqさて、また別の拡張命令セットCLMULにはpclmulqdqという命令があります。上の乗算を高速に行うために使われます。pclmulqdqの動作をstd::bitsetを用いた疑似コードで書くとこんな感じでしょうか。result;}最初のindexにより分岐している部分で128ビットのうちどの64ビットを使って演算するかを選択し、64ビットx64ビットの繰り上がりなしの掛け算を行います。乗算だと思うことができます。多項式の自乗を考えてみます。a[i];}と同じことになります。これを用いるとかなり簡潔にunpackを実装できます。1));}ベンチマーク以上3種類のアルゴリズムの実行コストを実際に計測してみました。unpack.cppHi/Loそれぞれ230回(≒10億回)unpackを計算しその時間を計測します。1回の処理が軽いので、関数呼び出しやデータ生成が遅いと差が出る比較ができないので、(もともと最適化したら関数呼び出しは消えますが)関数にインライン化指定をして、データ生成はxorshiftを用いています。ベンチマーク結果は以下のとおりです。2.265sHi/Loともにpclmulqdqを用いた場合が一番高速という結果になりました。ちなみにpdepバージョンがHiとLoで実行時間に開きがあるのはmovq命令とpextrq命令の違いによると思われます。pclmulqdq命令は使いどころが難しいですがスポッとハマると気持ちいいですね。明日の12日目はocxtalさんによる「たぶんbitDPの話」です。22日目】この記事はKMCアドベントカレンダー22日目の記事です。「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみたLeapMind株式会社に入社しました月別アーカイブはてなブログをはじめよう!PrimeNumberさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。