grafi.jp

ROT13と呼ばれる、アルファベットを13文字離れた文字に置き換える操作を行うプログラムを、SSE2を中心としたx86_64のSIMDによって高速化しました。結果としてテーブル引きによる実装と比べて4倍程度速くなりました。

ソースコードは https://github.com/grafi-tt/rot13-simd で公開しています。

基本的な発想は、何文字だけずらすかを比較演算の結果を元にして算出した上で元の文字に足し合わせるというものです。

大まかには、

  1. 各文字を0xDFでマスクして、小文字を大文字にする。
  2. 各文字を’A'-1、M、'Z’と比較する。比較結果は、-1あるいは0として得られる。
  3. それを元に、「足す数」 / 13 + 1を算出する（or演算を上手く用いて命令数を削っている）。「足す数」は負になり得るが、ここで算出する数は必ず0以上。
  4. その数に13をかける。8bit単位のSIMD乗算はできないが、変な繰り上がりがないので16bit単位や32bit単位で乗算しても問題は無い。このためにさっき0以上にする必要があった。
  5. 元の文字から13を引く。
  6. 4.と5.の結果を足し合わせる。

という流れで行います。

具体的な式を考えます。

dA := if c > 'A' - 1 then -1 else 0
dM := if c > 'M' then -1 else 0
dZ := if c > 'Z' then -1 else 0

とすると、ずらす文字数は (- dA + 2dM - dZ) × 13 となります。

2dM + 1 は、 dM | 1 で算出できます。これから dA + dZ を引けば、3.のステップが行えます。

実は乗算を使わなくても、

j = (dM - dA) × 13
k = (dM - dZ) × 13

としたときに、 dM - dA および dM - dZ は 0 か -1 にしかならないことから -j = (dM - dA) | 13 、 -k = (dM - dZ) | 13 として算出できるので、ここから j + k を求めることで「足す数」をいきなり求めることができます。

しかしこうすると、依存関係が伸びてスケジューリングが悪くなる関係なのか、微妙に遅くなってしまいました（SSE4.1のblendを上手く使えばひょっとしたら速くなるかも）。

両端の処理もmaskmovを用いてSIMDで行いました。maskの生成は結構大変だったけど何とかなりました（説明は省きます）。

ただ、maskmovがかなり遅くて短い文字列に対してはかなり（アンロールした実装と比べて10倍近く）遅くなります。両端はテーブル引きするようにすれば、テーブルがL1キャッシュに載っている限り速くはなりますが、なんか中途半端にテーブルを使うのは負けた気がします。maskmovを使わずに文字列の範囲外には元と同じ文字を書き込むようにすれば一気に速くなるし、ページ境界を跨ぐことは無いので多分セグメンテーションフォルトは起きないような気がするのですが、文字列を読み込んだ直後に他のスレッドからその部分の文字が書き換えられた場合にデータが壊れてしまいます。別にスレッドセーフじゃないといけないとかは思わないのですが、範囲外の文字まで安全じゃないというのは気持ち悪いです。atomicな加算を使えないかとも思いましたがやっぱりアトミックにメモリを操作するのは遅かったです。