6.4. 最悪応答時間

mt-liteおよび比較対象の擬似乱数生成アルゴリズムの最悪応答時間の評価を示す。ただし、複数乱数生成を行うものは関数呼び出し側で最悪応答時間を制御できるため、評価する意味がないので対象に入れていない。

測定は、生成関数内部にループを持つもののみに対して行った。生成関数内でのインデックス値の更新を意図的に停止させるなどして常に最悪時間での応答を行うようにし、106回の関数呼び出しを行って評価した。ループを持たないものの最悪応答時間は、実行速度の測定結果から計算で求めた平均応答時間と等しいものとした。どちらの方法も最悪応答時間の評価としては厳密性を欠くので、平均計算量と最悪計算量から応答時間を見積もる際の参考値程度のものとして見るべきである。

結果は次の通り。表中のworstは最悪応答時間、aveは実行速度の測定結果から計算で求めた平均応答時間を示す。値の単位はナノ秒である。

表 6.4. x86 (Pentium M 1.6GHz) + Gcc (4.1.2, -O3)での最悪応答時間


表 6.5. PowerPC (G4 1.25GHz) + Gcc (4.1.2, -O3)での最悪応答時間


表 6.6. ARM (X-Scale PXA255 400MHz) + Gcc (3.2.3, -O3)での最悪応答時間


結果から、関数内部にループを持つmt19937ar、SFMT、mtlite-loopおよびmtlite-loop-ntは、平均応答時間に比べて最悪応答時間が著しく長いことがわかる。また、ループがある場合の最悪応答時間は状態ベクトルの長さに比例するため、周期219937-1のものよりも周期2607-1のものの方が最悪応答時間が短いことがわかる。

リアルタイム性が要求され、ループを持つ関数の最悪応答時間では要求を満たせない場合は、mtlite-nonloop、mtlite-nonloop-ntあるいはWELLやxor128などのループを持たない乱数生成アルゴリズムを選択する必要がある。

ただし、ループを持つものであっても、周期を短くすることで最悪応答時間を要求内に収めることができるかどうかは検討する価値がある。また、上記評価対象のすべてのループを持つ乱数生成アルゴリズムにおいて、応答時間が最悪値を示す可能性があるのは内部の状態ベクトルを更新するときのみである: 状態ベクトルの更新は一定間隔で定期的に行われるため、例えば2回の連続した乱数生成の両方が最悪応答時間となることはない。