はじめに

この記事を読んで嬉しくなるのは一部の人だけだと思います．

問題

8 桁の整数を表す文字列が与えられます．それに対応する整数を返す関数を作ってください．

以下において，int は 32-bit であるとか long は 64-bit であるとか，そういったことを仮定します．仮定してまずい場合は適宜よしなに．

愚直な解法

parse.cpp

int parseIntNaive(const std::string& in) {
  int out = 0;
  for (size_t i = 0; i < 8; ++i)
    out = out*10 + in[i] - '0';
  return out;
}

それはそう．なんだけど，char 1 つが表現できる範囲の演算を細々やっていて，もっと効率よくできるんじゃないかなぁ，という気持ちになってきます．

// 実際には，コンパイラしゃんに投げると LEA 命令を駆使したりループアンロールしたりしてめちゃ高速になるんだよね．

ワード単位での並列化

たとえば，char 8 つは long 1 つで表せるので，表したくなってきます．
以下では ASCII でエンコードされることとリトルエンディアンを仮定しますが，適宜よしなに．

"31415926" --> 0x3632393531343133

（'0' から '9' は 0x30 から 0x39 に対応しています．）

この形式にできたとすると，parseIntNaive() ではループごとに '0' を引いていたところを 0x3030303030303030 をまとめて引く操作に置き換えられます．

0x0602090501040103

えー，うーん，これうまく説明できないんですが，がんばります．

まず，（変換後の）右側の桁が（入力文字列の）上位桁に対応しているので，右を 10 倍し，それと左のものを足し合わせます（まずは 2 桁ごとに区切って考えます）．

   0x0602090501040103 * 10
+) 0x0602090501040103 >> 8
--------------------------
   0x3c1a5c3b0f290e1f

もう左側の桁は不要になったので，マスクをかけて消します．

   0x3c1a5c3b0f290e1f
&) 0x00ff00ff00ff00ff
---------------------
   0x001a003b0029001f

ここで，31 == 0x1f，41 == 0x29，59 == 0x3b，26 == 0x1a です（もう流れがわかってきましたか）．

同じことを繰り返します．今度は 100 倍ですね．

   0x001a003b0029001f * 100
+) 0x001a003b0029001f >> 16
---------------------------
   0x0a281726103f0c45

マスクをかけます．

   0x0a281726103f0c45
&) 0x0000ffff0000ffff
---------------------
   0x0000172600000c45

ここで，0x0c45 == 3141，0x1726 == 5926 です．
ラスト一回．最後は 10000 倍です．

   0x0000172600000c45 * 10000
+) 0x0000172600000c45 >> 32
-----------------------------
   0x03883c6001df5e76

マスクも忘れずに．

   0x03883c6001df5e76
&) 0x00000000ffffffff
---------------------
   0x0000000001df5e76

さて，0x01df5e76 == 31415926 でありますので，求めたい数値が得られていることがわかります．

// 各操作で足し算を行う際，特に最初の操作では，隣の桁とは 256 倍の差があるので，10 倍しても隣の桁まではみ出さないことが一つの重要なポイントです．

コードにすると，次のようになります．

parse.cpp

int parseIntParallel(const std::string& in) {
  long out = *(long*)in.c_str();
  out -= 0x3030303030303030;
  out = (out * 10 + (out >> 8)) & 0x00FF00FF00FF00FF;
  out = (out * 100 + (out >> 16)) & 0x0000FFFF0000FFFF;
  out = (out * 10000 + (out >> 32)) & 0x00000000FFFFFFFF;
  return out;
}

なお，今回の方法では，8 桁に決め打ちしていましたが，実際の入力はそうとは限らないので，適宜よしなにする必要があります．

実験

いつものをやって速度比較をしました．

愚直な方法と並列の方法です．並列の方が 1 ms 勝っています．しょっぱいですね．

愚直な方法でも，スペースや改行区切りのパースなら終端の判定は >= '0' で済む，みたいな工夫をやっています．

並列の手法では，たかだか 8 桁以下という仮定を置いています（10 桁になりうる場合のやつは未実装）．適宜ビットシフトをする必要があるので注意です．

今後の課題

たくさんの桁がくるとき，まだ数字が残っているのか？区切り文字に到達したか？などを判定するのに時間がかかりそうなので大変そう．なんとかしたいです．
あと負数についてもちゃんとやらなきゃで大変です．

あと，こんな感じでワードで並列にしたり，ビット演算で賢くやるのを自分の中で bit magic と呼んでいたのですが，どこで見た用語だったか（あるいは自分で考えた？それとも別の意味の用語を勘違いした？）わからなくなりました．知っている方がいればよしなに．