Tweenの高速化についてまとめ。その１

最近作っている、そこそこに高速なTweenのライブラリについて、主に高速化の手法についていくつかまとめ。

まずは定番ではあるが、配列を使わずにリンクリストを使う。やはりFP10.1ではVectorよりも速い。ただし、要素の削除に伴う付け替えのコストが高い。削除による要素の付け替えの場合を考えてみると、以下の処理が必要となる。

• 削除対象の前がnullなら次の要素がヘッドになる
• 削除対象の次がnullなら前の要素がテイルになる
• 削除対象の前後両方がnullならヘッドもテイルもnullになる
• 削除対象の前後両方がnullでなければ、前後を繋ぎ合わせる

IF文は高速化の邪魔であるので、まずは不要な判定を減らしたいところである。そこで、ヘッドもテイルもダミーの要素として、事前に用意するのである。すると削除対象の前後が絶対にnullにならないので、IF文は不要になるのである。

リンクリストはwhile文などで回すことが多いと思うが、ループ毎にループを抜ける判定が必要になる。処理の実行回数にたいしてループの判定を減らすことによって高速化ができる。その手法として、ループの展開（アンロール）と呼ばれる手法がある。

例えばループを1ループあたり8回処理するようにすると、ループ回数は8で割った数になる。では処理回数が8で割り切れない場合はどうするか。普通に考えると、ループ内で都度、「まだ処理は必要か」と判定を行うことになる。それではアンロールの効果はないし、本末転倒である。

そこで、リンクリストのテイルに着目してみよう。テイルの次の要素は最後なのでnullである。しかし、テイルの次の要素がテイル自信の場合は、次、次と辿っても、nullが現れることはないのだ。つまり、nullであるかの判定が不要なので、「まだ処理は必要か」という判断がいらないのである。

次回はメモリ関連について書いてみる予定。