同じ命令なのに、なぜ遅くなる？

プログラムの中身を1文字も変えていない部分が、遅くなることがあります。原因は、関数がメモリの「どこに置かれたか」でした。その仕組みと直し方を、動く図で説明します。

はじめに：このページの前提

1どんなプログラム？

どうぶつしょうぎ（3×4マスの小さな将棋）で、最初の局面から指し進めて現れうる2億4680万の局面すべてについて、勝ち負けと決着までの手数を決めるプログラムです。2021年に書いたものを少しずつ速くしていて、最初は8時間55分かかっていたのが、いまは約2分15秒です。速くする1回ごとに番号を付けて記録しています（記録 #32、#33 など）。

2時間はどこで使っている？

工程は大きく2つです。全探索：最初の局面から指せる手を全部たどって、局面を集める。後退解析：決着がついた局面から逆向きにたどって、勝ち負けを広げる。どちらも「ある局面から指せる手を全部作る」処理を何億回も繰り返していて、そこが時間の大半です。

3関数・命令・番地

プログラムは関数という部品の集まりです。コンパイルすると、関数は CPU が実行する命令（機械語）の列になり、メモリの上に並びます。メモリの位置は番地（バイト単位の住所のような番号）で表します。

4速くなったかの確かめ方

変える前の版と変えた後の版を、交互に6回ずつ走らせて、差の平均と「本当の差はたぶんこの範囲」という区間を出します。区間が 0 をまたがなければ、偶然ではない差と判断します。この比べ方を、このプロジェクトでは門番と呼んでいます。

前の関数を伸ばす+0 バイト

手を作る関数 nextBoardInvNormal置き場所の番地 0x1046ループ1周で読むかたまり 1 個

後退解析の関数 buildSuccRange置き場所の番地 0x10feループ1周で読むかたまり 1 個

触っていない部分が、0.63秒遅くなった

+0.63 秒（区間 +0.35〜+0.90 秒）

記録 #32 では、全探索の中の関数を1つだけ書き換えました。後退解析のほうは1文字も変えていません。それなのに門番で比べると、後退解析の「手を作って番号に直す工程」が平均 0.63 秒遅くなりました。区間が 0 をまたがないので、偶然とは言いにくい差です。

調べると、後退解析で CPU が実行する命令は、前とまったく同じでした。違っていたのは、関数がメモリのどこに置かれたかだけです。

図は仕組みを見せるための模型です。関数の大きさや番地は実物の値ではありません。実際の CPU では、64バイトのかたまりのほかに、解読済みの命令を置いておく場所や、分岐の向きを予想するための表も、番地の影響を受けます。0.63 秒などの数字は記録 #32 の門番の実測です。詳しい記録は dobutsu-shogi-rta のリポジトリにあります。