【プログラム高速化】分岐除去テクニック

　こんにちは。ディマージシェアの技術担当です。皆さんは重い処理をするプログラムを書くとき、命令レベルのコストを意識していますか？例えば、
・ファイルI/O
・除算
・分岐
・乗算
・その他
上記の処理は概ね上に書いたものほどコストがかかります。瞬時に終わる処理であれば意識する必要はありませんが、1%でも速くしたいというケースは珍しくありません。また、小さい工夫でも積みあがって最終的に大きなパフォーマンス差になることもあります。

　今回は、ボウリングのスコア計算をするプログラムを作り、思いつく限りの高速化を試します。

ボウリングスコア計算プログラム

　ファイルで入力します。1行に1ゲーム分の「投球によって倒れたピン数」が並んでいます。
全て正常系で、半端に終了した行や、ファウルなどは含まれません。
入力ファイルは10万行あります。

4,6,10,10,10,5,5,2,3,10,5,5,10,2,8,10,
10,10,4,6,10,10,6,4,10,0,10,10,5,5,1,
10,4,6,6,4,10,10,10,10,10,10,0,10,10,
10,10,10,10,10,10,0,10,10,6,4,10,8,2,
10,10,10,10,10,10,10,10,2,6,10,10,10,
10,10,10,3,7,10,10,10,3,7,10,10,10,10,
10,2,8,10,10,10,10,9,1,8,2,10,2,8,10,
10,3,7,8,2,10,8,2,10,10,7,3,6,4,10,10,10,
10,10,10,9,1,9,1,10,9,1,10,10,10,10,2,
0,10,2,8,9,1,10,10,10,10,10,6,4,10,10,10,
(省略)

計算した結果はファイルに出力します。計算したスコアを1ゲーム1行で出力します。入力ファイルと同じ行数になります。

192
201
236
240
258
246
227
211
240
237
(省略)

PHPによる実装

<?php 
if ($argc < 3){
 echo "usage: php script input_path output_path\n";
 return 0;
}
$in_fp = fopen($argv[1], "r");
if (!$in_fp){
 printf("failed to open %s\n", $argv[1]);
 return 0;
}
$out_fp = fopen($argv[2], "w");
if (!$out_fp){
 printf("failed to open %s\n", $argv[2]);
 return 0;
}
while (($buf = fgets($in_fp, 127)) !== false) {
 $pinlog = array_filter(explode(',', trim($buf)), 'strlen');
 $score = calc_score($pinlog);
 fprintf($out_fp, "%d\n", $score);
}
fclose($in_fp);
fclose($out_fp);
function calc_score($log){
 $frame_score = 0; // フレームのスコア
 $score = 0; // スコア
 $frame = 1; // 現在フレーム
 $nth_throw = 0; // 現在フレームの何投目か 0:1, 1:2
 $remain_pin = 10; // 投球ごとの残ピン数
 foreach ($log as $i => $n_pin){
   $bonus_score = [($log[$i + 1] ?? 0) + ($log[$i + 2] ?? 0), $log[$i + 1] ?? 0];
   $frame_score += $n_pin; // 基礎点
   $remain_pin -= $n_pin; // 残ったピン
   if (!$remain_pin){ //残ピン0 ストライク or スペア
     $frame_score += $bonus_score[$nth_throw]; // 未来分のデータがある前提で、未来分の点数を加算は正しい
   }
   if (!$remain_pin || $nth_throw){ //残ピン0 or 2投目はフレームの終わり
     $score += $frame_score; //合計点に加算
   }
   if ($frame == 10 && !$remain_pin){
     break; // 10フレーム目でストライク or スペアは上のソースで点数加算済なのでループ停止
   }
   if (!$remain_pin || $nth_throw){ // ストライク or 2投目は次のフレームへ
     $frame++; // 次フレームへ
     $remain_pin = 10; // 残ピン復活
     $frame_score = 0; // フレームのスコアを0にリセット
     $nth_throw = -1; // フレーム1投目にリセット
   }
   $nth_throw++;
 }
 return $score;
}

実行結果

time php bowling_score.php pin_logs.txt out.txt 
0m0.518s

これをベースにチューニングします。

C言語による実装

　大抵のスクリプト言語のプログラムはC言語で書けば速くなります。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int calc_score(int *log, int n){
 int i;
 int frame_score = 0; // フレームのスコア
 int score = 0; // スコア
 int frame = 1; // 現在フレーム
 int nth_throw = 1; // 現在フレームの何投目か
 int remain_pin = 10; // 投球ごとの残ピン数
 for (i = 0 ; i < n ; i++){
   int strike = 0;
   int spare = 0;
   int n_pin = log[i]; //倒れたピン数
   frame_score += n_pin; // 基礎点
   remain_pin -= n_pin; // 残ったピン
   if (nth_throw == 1 && remain_pin == 0){ //フレーム1投球目で残ピン0 ストライク
     strike = 1;
     frame_score += (log[i + 1] + log[i + 2]); // 未来2投分のデータがある前提で、未来分の点数を加算は正しい
   }
   if (nth_throw == 2 && remain_pin == 0){ //フレーム2投球目で残ピン0 スペア
     spare = 1;
     frame_score += log[i + 1]; // 未来1投分のデータがある前提で、未来分の点数を加算は正しい
   }
   if (strike || nth_throw == 2){ //ストライク or 2投目はフレームの終わり
     score += frame_score; //合計点に加算
   }
   if (frame == 10 && (strike || spare)){
     break; // 10フレーム目でストライク or スペアは上のソースで点数加算済なのでループ停止
   }
   if (strike || nth_throw == 2){ // ストライク or 2投目は次のフレームへ
     frame++; // 次フレームへ
     remain_pin = 10; // 残ピン復活
     nth_throw = 1; // フレーム1投目にリセット
     frame_score = 0; // フレームのスコアを0にリセット
     continue;
   }
   nth_throw++; // フレーム変わらず2投目へ
 }
 return score;
}

// C言語にはsplit関数のような便利なものは無い
// strを文字列cで分割して数値変換してdstに格納、戻り値は分割された要素数
// 入力strを破壊する副作用有り
int explodeint(char* c, char* str, int* dst){
 char *tp;
 int ct = 0;
 int len;
 if (len = strlen(str)){
   if (str[len - 1] == '\n'){
     str[len - 1] = '\0';
   }
 }
 tp = strtok(str, c);
 if (tp[0] != '\0'){
   dst[ct++] = atoi(tp);
 }
 while(tp = strtok(NULL, c)){
   if (tp[0] != '\0'){
     dst[ct++] = atoi(tp);
   }
 }
 return ct;
}

int main(int argc, char *argv[]){
 char *buf;
 char pinlog[64];
 FILE *in_fp, *out_fp;
 int in_fsize;
 int r;
 char *tp, *save;
 int len;
 int score;
 int out_byte = 0;
 if (argc < 3){
   printf("usage: ./bin input_path output_path\n");
   return 0;
 }
 in_fsize = get_file_size(argv[1]);
 if (in_fsize < 0){
   printf("failed to open %s\n", argv[1]);
   return 0;
 }
 in_fp = fopen(argv[1], "r");
 out_fp = fopen(argv[2], "w");
 if (!out_fp){
   printf("failed to open %s\n", argv[2]);
   return 0;
 }
 buf = malloc(in_fsize + 1);
 r = fread(buf, in_fsize, 1, in_fp);
 tp = strtok_r(buf, "\n", &save);
 len = strlen(tp);
 if (tp[len - 1] == ','){
   tp[len - 1] = '\0';
 }
 explodeint(",", tp, pinlog);
 score = c(pinlog);
 out_byte += sprintf(buf + out_byte, "%d\n", score);
 while(tp = strtok_r(NULL, "\n", &save)){
   len = strlen(tp);
   if (tp[len - 1] == ','){
     tp[len - 1] = '\0';
   }
   int pinlogct = explodeint(",", tp, pinlog);
   score = calc_score(pinlog, pinlogct);
   out_byte += sprintf(buf + out_byte, "%d\n", score);
 }
 fprintf(out_fp, "%s", buf);
 fclose(in_fp);
 fclose(out_fp);
 free(buf);
}

実行結果

time ./a.out pin_logs.txt out.txt 
0m0.051s

C言語で書き直しただけで10倍の性能になりました。

分岐除去

　普段スクリプト言語を利用していると気付きすらしない事項ですが、分岐命令はその他の汎用演算に比べるとコストがかかります。ソースコードの可読性を著しく損ないますが、速くするためです。仕方ありませんね。

int calc_score(int *log, int n){
 int i;
 int frame_score = 0; // フレームのスコア
 int score = 0; // スコア
 int frame = 1; // 現在フレーム
 int nth_throw = 1; // 現在フレームの何投目か
 int remain_pin = 10; // 投球ごとの残ピン数
 for (i = 0 ; i < n ; i++){
   int strike = 0;
   int spare = 0;
   int n_pin = log[i]; //倒れたピン数
   frame_score += n_pin; // 基礎点
   remain_pin -= n_pin; // 残ったピン
   if (nth_throw == 1 && remain_pin == 0){ //フレーム1投球目で残ピン0 ストライク
     strike = 1;
     frame_score += (log[i + 1] + log[i + 2]); // 未来2投分のデータがある前提で、未来分の点数を加算は正しい
   }
   if (nth_throw == 2 && remain_pin == 0){ //フレーム2投球目で残ピン0 スペア
     spare = 1;
     frame_score += log[i + 1]; // 未来1投分のデータがある前提で、未来分の点数を加算は正しい
   }
   if (strike || nth_throw == 2){ //ストライク or 2投目はフレームの終わり
     score += frame_score; //合計点に加算
   }
   if (frame == 10 && (strike || spare)){
     break; // 10フレーム目でストライク or スペアは上のソースで点数加算済なのでループ停止
   }
   if (strike || nth_throw == 2){ // ストライク or 2投目は次のフレームへ
     frame++; // 次フレームへ
     remain_pin = 10; // 残ピン復活
     nth_throw = 1; // フレーム1投目にリセット
     frame_score = 0; // フレームのスコアを0にリセット
     continue;
   }
   nth_throw++; // フレーム変わらず2投目へ
 }
 return score;
}

を書き換えると

static inline int calc_score(register char*l){
 register int f=0,s=0,t=0,c=10,r=10,b,m,n,o; //もろもろ初期化
 while(c){
   o=b=m=(*(int*)l++)&0x00FFFFFF;
   o&=255;
   b>>=8;
   b+=(b<<8);
   r-=o; // 残りピン数
   f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
   m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
   n=~m;
   s+=f&m; // スコア合計加算
   c+=m; // フレームカウント
   f&=n; // フレームスコア維持 or リセット
   t&=n; // フレーム内n投球目維持 or リセット
   r=m&10|n&r; // 残ピン数維持 or リセット
 }
 return s;
}

こんなソースにすることができます。可読性は犠牲になりました。

基本的なテクニックは、条件のtrue or falseに応じて

00000000000000000000000000000000
11111111111111111111111111111111

のようなレジスタ長のビットマスクを生成し、ビット演算で欲しい結果を得るというものです。
符号付きシフト演算を用いて符号ビットを右に伝搬させて作成するのが一般的です。

さて、上のコードで分岐は粗方除去されましたが、まだループの制御

while(c)

が生きています。ここも除去します。
このループは高々22回しか実行されません。また、少なくとも10回は実行されるのです。22回同じコードをコピペしてしまい、前半10回はループ停止の分岐を消します。このテクニックはループのアンローリングと呼ばれます。

static inline int c_expansion(char*l){
 register int f=0,s=0,t=0,c=10,r=10,b,m,n,o; //もろもろ初期化
 register unsigned long long int z;
 //////////////////////////////////////
 z=*(unsigned long long int*)l;
 l+=6;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z=*(unsigned long long int*)l;
 l+=6;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 //////////////////////////////////////
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 /////////////////////////////////////////////////////
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z=*(unsigned long long int*)l;
 l+=6;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z=*(unsigned long long int*)l;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 if (!c){
   return s;
 }
 z>>=8;
 o=b=m=z&0x0000000000FFFFFFull;
 o&=255;
 b>>=8;
 b+=(b<<8);
 r-=o; // 残りピン数
 f+=o+(((b>>(8-(t<<3)))&255)&(m=(r-1)>>31)); // 点数加算、必要があればストライク、スペアボーナス点も加算
 m|=(~((t++-1)>>31)); // 後続処理のためのビットマスク
 n=~m;
 s+=f&m; // スコア合計加算
 c+=m; // フレームカウント
 f&=n; // フレームスコア維持 or リセット
 t&=n; // フレーム内n投球目維持 or リセット
 r=m&10|n&r; // 残ピン数維持 or リセット
 /////////////////////////////////////////////////////
 return s;
}

オリジナルからは想像もできないソースが出てきました。

実行性能を計測します。このプログラムのほとんどはファイルのIOにかかる時間のため、スコア計算を10000回ループした結果を比較します。

C言語でシンプルに実装した場合

time ./a.out pin_logs.txt out.txt 
0m13.983s

分岐除去、ループアンローリングの場合

time ./a.out pin_logs.txt out.txt 
0m1.801s

分岐が除去されたプログラムは元のプログラムの5倍以上の性能になりました。

まとめ

　速度を重視したコーディングでは、C言語の世界でナノ秒オーダーでチューニングすることができます。今回は分岐命令を算術演算に置き換えるテクニックを紹介しました。このテクニックは、高速化だけでなく、実行時間を均一にする効果もあります。分岐のパターンによって速い遅いがなくなるのです。実行時間の最悪値を押さえる効果があり、リアルタイム性が重視されるプログラムでは重要なテクニックです。