[] より . を使おう

Posted 2013.05.30 in 吉里吉里

吉里吉里(TJS2)ではオブジェクトのメンバ(または辞書の要素)へのアクセス方法には
直接メンバ選択演算子 . による直接参照と
間接メンバ選択演算子 [] による間接参照があるが
今回は

[] より . の方が速い!

というお話。

実験

次のようなテストスクリプトを書いて
それぞれの書き込み時と読み込み時の速度を計測してみた。


function test_pureLoop(testNum)
{
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) ;
  var end = System.getTickCount();
  return end-begin;
}

function test_set1(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["X"] = 999;
  var end = System.getTickCount();
  return end-begin;
}

function test_set2(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["XXXXXXXXXX"]  = 999;
  var end = System.getTickCount();
  return end-begin;
}

function test_set3(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["XXXXXXXXXXXXXXXXXXXX"]  = 999;
  var end = System.getTickCount();
  return end-begin;
}

function test_set4(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.X = 999;
  var end = System.getTickCount();
  return end-begin;
}

function test_set5(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.XXXXXXXXXX  = 999;
  var end = System.getTickCount();
  return end-begin;
}
  
function test_set6(testNum)
{
  var dic = %[];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.XXXXXXXXXXXXXXXXXXXX = 999;
  var end = System.getTickCount();
  return end-begin;
}

function test_get1(testNum)
{
  var dic = %[ "X" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["X"];
  var end = System.getTickCount();
  return end-begin;
}

function test_get2(testNum)
{
  var dic = %[ "XXXXXXXXXX" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["XXXXXXXXXX"];
  var end = System.getTickCount();
  return end-begin;
}

function test_get3(testNum)
{
  var dic = %[ "XXXXXXXXXXXXXXXXXXXX" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic["XXXXXXXXXXXXXXXXXXXX"];
  var end = System.getTickCount();
  return end-begin;
}

function test_get4(testNum)
{
  var dic = %[ "X" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.X;
  var end = System.getTickCount();
  return end-begin;
}

function test_get5(testNum)
{
  var dic = %[ "XXXXXXXXXX" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.XXXXXXXXXX;
  var end = System.getTickCount();
  return end-begin;
}

function test_get6(testNum)
{
  var dic = %[ "XXXXXXXXXXXXXXXXXXXX" => 999 ];
  var begin = System.getTickCount();
  for(var i=0; i < testNum; i++) dic.XXXXXXXXXXXXXXXXXXXX;
  var end = System.getTickCount();
  return end-begin;
}

// 割り込みなどによる計測誤差をなくすために複数回計測して最小の値を採用する
function repeatTest(func)
{
  var TEST_NUM = 1000000;
  var PEPEAT_NUM = 100;
  var minTime;
  for(var i=0; i < PEPEAT_NUM; i++)
  {
    var time = func(TEST_NUM);
    if(minTime === void)
      minTime = time;
    else
      minTime = Math.min(minTime, time);
  }
  return minTime;
}

function test()
{
  var base = repeatTest(test_pureLoop);
  Debug.message("pure loop                         : %d ms"
    .sprintf(base));

  Debug.message(">set");
  Debug.message("dic[\"X\"] = 999                    : %d ms"
    .sprintf(repeatTest(test_set1)-base));
  Debug.message("dic[\"XXXXXXXXXX\"] = 999           : %d ms"
    .sprintf(repeatTest(test_set2)-base));
  Debug.message("dic[\"XXXXXXXXXXXXXXXXXXXX\"] = 999 : %d ms"
    .sprintf(repeatTest(test_set3)-base));
  Debug.message("dic.X = 999                       : %d ms"
    .sprintf(repeatTest(test_set4)-base));
  Debug.message("dic.XXXXXXXXXX = 999              : %d ms"
    .sprintf(repeatTest(test_set5)-base));
  Debug.message("dic.XXXXXXXXXXXXXXXXXXXX = 999    : %d ms"
    .sprintf(repeatTest(test_set6)-base));

  Debug.message(">get");
  Debug.message("dic[\"X\"]                          : %d ms"
    .sprintf(repeatTest(test_get1)-base));
  Debug.message("dic[\"XXXXXXXXXX\"]                 : %d ms"
    .sprintf(repeatTest(test_get2)-base));
  Debug.message("dic[\"XXXXXXXXXXXXXXXXXXXX\"]       : %d ms"
    .sprintf(repeatTest(test_get3)-base));
  Debug.message("dic.X                             : %d ms"
    .sprintf(repeatTest(test_get4)-base));
  Debug.message("dic.XXXXXXXXXX                    : %d ms"
    .sprintf(repeatTest(test_get5)-base));
  Debug.message("dic.XXXXXXXXXXXXXXXXXXXX          : %d ms"
    .sprintf(repeatTest(test_get6)-base));
}

var win = new Window();
win.visible = true;
Debug.console.visible = true;
test();

実行結果。


pure loop                         : 17 ms
>set
dic["X"] = 999                    : 68 ms
dic["XXXXXXXXXX"] = 999           : 67 ms
dic["XXXXXXXXXXXXXXXXXXXX"] = 999 : 67 ms
dic.X = 999                       : 41 ms
dic.XXXXXXXXXX = 999              : 41 ms
dic.XXXXXXXXXXXXXXXXXXXX = 999    : 41 ms
>get
dic["X"]                          : 53 ms
dic["XXXXXXXXXX"]                 : 72 ms
dic["XXXXXXXXXXXXXXXXXXXX"]       : 96 ms
dic.X                             : 34 ms
dic.XXXXXXXXXX                    : 34 ms
dic.XXXXXXXXXXXXXXXXXXXX          : 34 ms

ちなみに比較しやすいように各値からは pure loop 分を差し引いている。
パッと見で明らかに

間接参照による取得が遅い!

キー文字列の長さに比例して遅くなっているように思える。
10文字で直接参照に対して倍近い速度差。
これは場合によってはちょっと無視できない差だ。

何が起きているのか

この現象を理解するにはまず、文字列が保持する『ヒント』情報について知る必要がある。

文字列が辞書に対するキー文字列として使われる時、キー文字列からハッシュ値が計算される。
ハッシュ値は文字列の内容全体から計算されるので、文字列が長ければ長いほど計算に時間がかかる。
計算で得られたハッシュ値はハッシュテーブル内の位置を示す値として使われる一方で、
文字列に『ヒント』情報として保持される。

保持された『ヒント』は次回辞書要素参照時にハッシュ値のかわりに使用され
ハッシュ値の計算を省いた簡易的な検索が行われる。
こうなるとキー文字列の長さは関係なくなる。
キー文字列の長さに関わらず速度がほぼ一定の計測結果が得られたのはそのためである。

ではなぜ間接参照による取得時だけ速度が一定ではないのか。
それは

間接参照による取得時だけヒントが使われない

からだ。
すなわち、毎回ハッシュ値が再計算されているのである。

検証

間接参照による取得の実装は tTJSInterCodeContext::GetPropertyIndirect にある。
tjsInterCodeExec.cpp

本当にヒントを使わないことが原因なのか確認するために
間接参照による取得時にもヒントを使うように改造してみた。


pure loop                         : 17 ms
>set
dic["X"] = 999                    : 68 ms
dic["XXXXXXXXXX"] = 999           : 69 ms
dic["XXXXXXXXXXXXXXXXXXXX"] = 999 : 68 ms
dic.X = 999                       : 41 ms
dic.XXXXXXXXXX = 999              : 41 ms
dic.XXXXXXXXXXXXXXXXXXXX = 999    : 40 ms
>get
dic["X"]                          : 46 ms
dic["XXXXXXXXXX"]                 : 46 ms
dic["XXXXXXXXXXXXXXXXXXXX"]       : 46 ms
dic.X                             : 33 ms
dic.XXXXXXXXXX                    : 33 ms
dic.XXXXXXXXXXXXXXXXXXXX          : 33 ms

期待通り一定速度になった!

ヒントを使わない理由

間接参照による設定時にはヒントを使っているので
取得時だけヒントを使わない理由はあまりないように思える。
ソースには
// TODO: verify here needs hint holding
と記述があるので、ヒントを使うべきか検討中…
といったかんじだろうか。

『その文字列の内容から計算されるハッシュ値』と『ヒント』が常にイコールなら
取得時にヒントを使ってもおそらく何も問題は起きないだろう。
しかしどうやら、常にイコールなわけではないようだ。
ヒント作成後に文字列が内部的に改変された場合、ヒントはクリアも更新もされないからである。

文字列が後から改変された状態で辞書を参照すると、ヒントを使った要素の簡易検索に失敗し
ハッシュ値が再計算されヒントが再設定され、もう一度検索が行われる。
すなわちヒントによる検索が逆に無駄な処理になってしまう。

そういった問題を回避するために、間接参照ではヒントを使わないようにしているものと思われる。
直接参照でヒントが使われるは、直接参照のキー文字列は必ず文字列定数だからだろう。
定数なので文字列が後から改変される心配がない、ということだ。

ただTJS上での文字列操作は、文字列の内容をいじるのではなく、
新しく文字列を生成するようになっているため
文字列が後から改変されるといった状況は根本的に起こらないような気もする。
何か見落としているだけかもしれない。

ちなみに辞書への要素の追加時とdelete演算子による削除時にも
文字列が保持しているヒントは実質的に使われず必ずハッシュ値が再計算されるようだ。

まとめ

ヒントが使われない理由はともあれ、このようなことから間接参照による取得は
直接参照に比べて大きくパフォーマンスが落ちる場合がある。
全般的に間接参照よりも直接参照の方が少しだけ速いことからも
直接参照を使える場面では、直接参照を使ったほうが良いと言えるだろう。


Leave a Reply

*