続・続・計算量を減らす:Newの回数を減らしたらもっと速く… なるどころか遅くなった!?
前回までのお話
taichiw.hatenablog.com
たった一行、乱数の初期化をループの中からクラス生成時に移しただけで5倍も速くなったというお話でした。
じゃあ、クラス変数にしたらNewが減るじゃん!ということでstaticをつけてみました。
private static Random rnd = new SecureRandom();
結果。
37秒, 39秒, 45秒, 49秒, 49秒, …
って… 元々30秒だったのが遅くなってるじゃないですカー!
CPUがサボってやがる
CPUの使われ方を比較してみると
インスタンス変数(=Classが作られるタイミングでNewする場合)
クラス変数(= Classがロードされるタイミングで一回だけNewする場合)
クラス変数のほうがギザギザしていて、天井に張り付いて『ない』気が。
(上のスクリーンショットだとあまりそうは見えませんが… 動いているものを見るとそんな気がしました)
おそらくこのサボりが遅さの原因…
ということは、マルチスレッド間でアクセスの待ちが発生している?
と思い調べてみると、案の定でした。
SecureRandomクラスでは、
public int nextInt(int bound) {
から呼ばれている
@Override final protected int next(int numBits) {
から呼ばれている
@Override public void nextBytes(byte[] bytes) {
から呼ばれている
public synchronized void engineNextBytes(byte[] var1) {
こいつがsynchronized。
ということで、マルチスレッド間で1インスタンスを共有した結果、メソッドにロックがかかって待ちが発生し、遅くなってしまっていたのでした。
SecureRandomをやめたら…
これまで、なんとなくSecureRandomクラスを使っていたのですが*1、改めて見るといかにも「Secureを得るために速度を犠牲にしている」っぽい名前です。
そこで改めて確認したところ、SecureRandomクラスの他に、単なるRandomクラスが存在しました*2。
Randomクラスで用いられている乱数生成アルゴリズムは予測可能であるために、暗号などには使えないそうなのですが、別に暗号を作っているわけではないのでこれで十分。
ということで、ただのRandomクラスに差し替えてみます。
22秒、21秒、20秒、22秒、…
おおおお… 速くなった!!
しかも、クラス変数でも、インスタンス変数でも、はたまたループ内で都度生成されるメソッドローカルな変数でも、ほぼ実行時間が変わらないという。
要は、SecureRandomの生成が遅かったのか…。
おまけ そもそも乱数を使わなかったら
Randomクラスにした結果、どうやら生成のコストは下がったのですが、それでもなお毎回の乱数の取得が重そうだなぁ… ということで、
試しに乱数を使うのをやめてみました*3
13秒、11秒、11秒、12秒、…
ということで、10秒前後縮まりました。
乱数って用法・容量を守って正しく使わないとコワイですね。