最近の JavaScript エンジンの最適化がすごい
JavaScript で幅優先探索をしたかったので、キューを作らなければならない。JavaScript では配列を使い、push() で追加し shift() で取り出すことでキューを実装できる。しかし、shift() のせいで要素数が増えると遅くなる。そこで、JavaScript queues なんて工夫されたライブラリがあるので、これを使って速く…
といきたいところだったが、使うのをやめた。原因は、そのページのベンチマークテスト。なんと、そのライブラリを使うと普通の配列の操作より遅くなった。
ベンチマークテスト
1要素あたりの結果（だったはず）。環境は Core2 Quad Q9550、メモリ4 GB、Ubuntu 12.04 x64。
Firefox
まず Firefox から。
| Queue length | Queue.js | Array |
|---|---|---|
| 1 | 3136700 | 3593400 |
| 2 | 1965500 | 3548400 |
| 4 | 3015200 | 3357700 |
| 8 | 4823000 | 3622500 |
| 16 | 3885900 | 3503960 |
| 32 | 6278797 | 3476424 |
| 64 | 4560900 | 2754900 |
| 128 | 7162700 | 3558600 |
| 256 | 4691100 | 3396065 |
| 512 | 7783000 | 3469118 |
| 1024 | 5558300 | 3604800 |
| 2048 | 5940300 | 3644500 |
| 4096 | 6454500 | 3513817 |
| 8192 | 7294100 | 3516733 |
| 16384 | 8495200 | 3413372 |
| 32768 | 9559500 | 3622700 |
| 65536 | 8480600 | 3466567 |
| 131072 | 9250000 | 3624100 |
| 262144 | 7199500 | 3479700 |
| 524288 | 8069700 | 3338400 |
| 1048576 | 8869500 | 3389900 |
Chrome
次に Chrome。
| Queue length | Queue.js | Array |
|---|---|---|
| 1 | 3673000 | 104076 |
| 2 | 5872300 | 90330 |
| 4 | 7979700 | 85437 |
| 8 | 8904700 | 90034 |
| 16 | 9594100 | 86421 |
| 32 | 10037100 | 104248 |
| 64 | 9634600 | 73794 |
| 128 | 8979900 | 97083 |
| 256 | 8831000 | 99533 |
| 512 | 8875900 | 94849 |
| 1024 | 8800800 | 77334 |
| 2048 | 6755900 | 115851 |
| 4096 | 6816500 | 86172 |
| 8192 | 7027300 | 74266 |
| 16384 | 6897800 | 106680 |
| 32768 | 7071000 | 72366 |
| 65536 | 3393195 | 32613 |
| 131072 | 2858500 | 192 |
| 262144 | 2872400 | 98 |
| 524288 | 3048256 | 76 |
| 1048576 | 3542568 | 38 |
Array 圧勝。文字通り桁が違う。最後の方がおかしい。V8 さんマジパネェっす！…なのか？
ところで
iPad 2 の Safari ではライブラリは意図どおりに配列より高速に動いた。したがって、環境により配列の普通の操作の速度が大幅に異なること、特に最近のデスクトップ用のブラウザではびっくりするくらい最適化されていることが分かった。
