Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« 「なぜふぉろ」の shortcut 対応 | トップページ | verilog-mode for xyzzy »

2011-02-02

JavaScript の配列アクセス速度


先週末、「続・ハイパフォーマンス Web サイト」を読みました。


前作に比べてさらにマニアックな内容になっていて、
ブラウザの処理をブロックせずに外部 JavaScript ファイルを
読み込むにはどうすればよいか、とかが詳しく書いてあります。
あと、Comet (ロングポーリング)の仕組みや利点欠点が
ちゃんと書いてあるのはけっこう貴重かもしれません。
とりあえず、動的な Web サイトを構築している人なら
一読の価値はあると思います。



で、読んでいて気になった記述がひとつ。

JavaScript のコードの実行効率に関する話の中で、

JavaScript の Array の要素へのアクセス速度は一定ではなく、 配列の後ろのほうの要素へのアクセスは前のほうの要素に比べて遅い。
という意味の記述がありました。 つまり、a[65535] へのアクセスは a[7] へのアクセスより遅い、というのです。 これはいわゆる「配列」というデータ構造に関して Seaoak が持っていた直感に反しています。 びっくり! さっそく自宅の PC で実験してみました。 8M 個の乱数を格納した数値配列オブジェクトを作成して、 ランダムに選択した要素の読み取りを 128M 回繰り返し、 かかった時間を計測してみました。 単純に実行すると「スクリプトの実行に異常に時間がかかっています」という 警告が出て、それでも続行するとブラウザが半分固まってしまうので、 今回は Web Worker に処理させてみました。 以下、Web Worker のコード:
(function() { try { var list = new Array; for (var i=0; i<8*1024*1024; i++) { list[i] = Math.random(); } onmessage = function(event) { try { var count = 128*1024*1024; var start_time = (new Date).getTime(); var acc = Math.random(); var index = Math.floor(Math.random()*list.length); while (count-- > 0) { acc = acc ^ list[0] ^ list[index]; } postMessage({'index': index, 'time': (new Date).getTime() - start_time}); } catch(e) { postMessage('FATAL2: ' + e); } }; } catch(e) { postMessage('FATAL2: ' + e); } })();
このコードを Google Chrome と Firefox と Opera で 1024 回ずつ 実行した結果、以下のグラフのようになりました。 グラフ(Google Chrome での計測結果) グラフ(Firefox での計測結果) グラフ(Opera での計測結果) 実行時間の絶対値はブラウザによってかなり異なっていますが、 傾向はどれも同じで、添字の大小によるアクセス速度の差は無し。 残念ながら IE8 は Web Worker が実装されていないので未測定です。 こんな単純な処理なのに、ブラウザによって実行時間が 15 倍も違うのは かなり意外でした。というか、Chrome が速すぎ? ちなみに、各ブラウザのバージョンと測定環境は以下のとおり:
Google Chrome 9.0.597.83 beta Firefox 3.6.13 Opera 11.01 Windows 7 Professional 32bit AMD Phenom II X4 970 BlackEdition (3.5GHz / Quad Core / TDP95W) ASUS M4A89TD PRO/USB3 (AMD 890FX + SB850) DDR3 PC3-12800 4GB ×2枚 (CL=9-9-9-24)
まぁ、Wikipedia の「配列」の項を見ても「配列内のデータへのアクセスは O(1) 時間でできる」と 書いてあるので、たぶん、本の記述が間違っているのだと思います。 とりあえず、モダンブラウザは直感に合った挙動をしているみたいで、ひと安心。

« 「なぜふぉろ」の shortcut 対応 | トップページ | verilog-mode for xyzzy »