前回の記事では遮蔽処理にまつわる不可思議な現象を再現してみたが、
この現象を回避する方法は、現象の複雑さに対して実に簡単だ。

不具合の回避

onTimer関数に次の記述を追加してみよう。

  var step = 0;
  function onTimer()
  {
    switch(step)
    {
    case 0:
      // 黒レイヤーを上に移動(不具合発生)
      layerBlack.absolute = 10;
      break;
    case 1:
      // 無意味にopacityを変更する(不具合回避)
      layerBlack.opacity = 0;
      layerBlack.opacity = 255;
      break;
    }
    step++;
  }

一見無意味に思える処理だが、実際この処理を行うと正しい動作結果になる。
この回避方法の意味を知るには、吉里吉里の遮蔽処理の仕組みを理解する必要がある。

遮蔽処理の仕組み

全てのレイヤーはそれぞれ個別に UpdateExcludeRect(更新遮断矩形) という情報を持つ。
UpdateExcludeRect は、そのレイヤーが他のレイヤーによって遮蔽されている領域を表す。

UpdateExcludeRect の情報は、レイヤーの再描画時に利用される。
レイヤーの再描画範囲が UpdateExcludeRect に被る時、
再描画範囲は UpdateExcludeRect にって分割され
UpdateExcludeRect に含まれる領域の再描画が省かれる。
まさしく「更新を遮断する矩形」なのである。
これによって遮蔽されていてどうせ見えない領域の描画の無駄が削減される。

重要なのは UpdateExcludeRect の情報が更新されるタイミングである。
UpdateExcludeRect は再描画のたびに毎回更新されるわけではない。
UpdateExcludeRect の更新は、
再描画時に VisualStateChanged フラグが立っている時だけ行われる。
VisualStateChanged フラグは、遮蔽状態に変化がある操作が行われた時に立てられる。
よって遮蔽状態に変化がなければ UpdateExcludeRect は更新されない。

回避方法の意味

先の不具合は、この UpdateExcludeRect の情報が正しく更新されないことによって起こる。
absolute の操作によって遮蔽状態が変化するにもかかわらず、
VisualStateChanged フラグが立てられていないからである。

この不具合を回避するには、立てられていない VisualStateChanged フラグを立ててやればよい。
opacity を操作すれば VisualStateChanged フラグが立てられるので、
opacity を無意味に変更すれば VisualStateChanged フラグを間接的に立てることができる。
これにより不具合を回避することができるのである。

よりスマートな回避方法

問題のあるプロパティをオーバーライドしておくと
プロパティを操作する度にいちいち気を遣う必要がなく便利だろう。
把握している限りでは order, type プロパティにも同様の問題があるので、そちらも対処しておく。

class OcclusionLayer extends Layer
{
  function OcclusionLayer(window, parent)
  {
    super.Layer(...);

    // 遮蔽するように設定
    type = ltOpaque;
  }

  // VisualStateChanged フラグを間接的に立てる
  function notifyVisualStateChanged()
  {
    var temp = opacity;
    opacity = !opacity;
    opacity = temp;
  }

  property absolute
  {
    setter(v){ super.absolute = v; notifyVisualStateChanged(); }
    getter(){ return super.absolute; }
  }

  property order
  {
    setter(v){ super.order = v; notifyVisualStateChanged(); }
    getter(){ return super.order; }
  }

  property type
  {
    setter(v){ super.type = v; notifyVisualStateChanged(); }
    getter(){ return super.type; }
  }
}

まとめ

実はこの absolute の問題は、わたなべごうさんに修正していただき
最新の開発版の吉里吉里では修正されている。
今回紹介した回避方法は、古いバージョンの吉里吉里を使っている場合に
この問題に遭遇した時の応急策として使えるだろう。

吉里吉里では、かなり限定された状況で遮蔽処理が行われるが、
その遮蔽処理には、いくつか問題が潜んでいる。
遮蔽処理にまつわる問題は非常に複雑怪奇な現象を引き起こし
とにかく原因を特定しづらい。

不可思議な動作

まずは次のtjsスクリプトを実行して見て欲しい。

class TestWindow extends Window
{
  var layerGray;
  var layerBlack;
  var timer;

  function TestWindow()
  {
    super.Window();
    setInnerSize(800, 600);

    // プライマリレイヤー
    add(new Layer(this, null));
    primaryLayer.setImageSize(innerWidth, innerHeight);
    primaryLayer.setSizeToImageSize();
    primaryLayer.fillRect(0, 0, innerWidth, innerHeight, 0xFFFFFFFF); // 白

    // 灰色レイヤーを上に作る
    layerGray = new Layer(this, primaryLayer);
    initLayer(layerGray, 50, 50, 400, 400, 0xFF777777, 5, ltOpaque); // 灰
    
    // 黒レイヤーを下に作る
    layerBlack = new Layer(this, primaryLayer);
    initLayer(layerBlack, 100, 100, 400, 400, 0xFF000000, 0, ltOpaque); // 黒
    
    // 黒レイヤーに子レイヤーを作る
    var sub = new Layer(this, layerBlack);
    add(sub);
    initLayer(sub, 100, 100, 200, 200, 0xFFFF00FF, 0, ltAlpha); // 紫
    sub.opacity = 128; // 半透明
    
    // このタイミングで黒レイヤーを上に移動させると正しい動作結果になる
    // layerBlack.absolute = 10;
    
    // タイマーを起動
    timer = new Timer(onTimer, "");
    timer.interval = 1000;
    timer.enabled = true;
  }

  function finalize()
  {
    invalidate layerGray;
    invalidate layerBlack;
    invalidate timer;

    super.finalize();
  }

  function initLayer(layer, x, y, w, h, color, absolute, type)
  {
    layer.left = x;
    layer.top = y;
    layer.setImageSize(w, h);
    layer.setSizeToImageSize();
    layer.fillRect(0, 0, w, h, color);
    layer.absolute = absolute;
    layer.type = type;
    layer.visible = true;
  }

  var step = 0;
  function onTimer()
  {
    switch(step)
    {
    case 0:
      // 黒レイヤーを上に移動(不具合発生)
      layerBlack.absolute = 10;
      break;
    }
    step++;
  }
}

var win = new TestWindow();
win.visible = true;

これを実行すると次のような動作結果になる。(version2.32 rev2 で確認)

おかしい動作結果なのだが、何がおかしいかわかるだろうか？

紫色が明るすぎる！

のである。
次の部分のコメントアウトを外すと、正しい動作結果になるので確認してみよう。

    // このタイミングで黒レイヤーを上に移動させると正しい動作結果になる
    // layerBlack.absolute = 10;

紫色が暗くなった！
opcity=128なのだから、この程度の色合いが正しい。

さらに不可思議な動作

子レイヤーを作る部分を次のように書き換えると、さらに現象がわかりやすくなる。

    // 黒レイヤーに子レイヤーを作る
    for(var x=0; x<10; x++)
    {
      for(var y=0; y<10; y++)
      {
        var sub = new Layer(this, layerBlack);
        add(sub);
        initLayer(sub, 50+x*30, 50+y*30, 8, 8, 0xFFFF00FF, 0, ltAlpha); // 紫
        sub.opacity = 128; // 半透明
      }
    }

子レイヤーとして紫の四角をたくさん作成するようにしただけだ。
これを実行すると次のようになる。

背後の灰色が透けてしまっている！

コメントアウトをはずすとやはり正しい動作になるので確認しておこう。

何がおきているのか

この不可思議な現象は、遮蔽処理にまつわる問題によって引き起こされている。
遮蔽処理にミスが生じ、実際には遮蔽していないにもかかわらず、
遮蔽による最適化が行われてしまっているのである。

この現象の回避は、遮蔽処理の存在を知らないと非常に困難だろう。
詳しい原因の追求と回避方法についてはまた次回～

めざせ60FPS！の記事で、Foooの無効領域処理と遮蔽処理による最適化を紹介したが
この二つの最適化は、実は吉里吉里でも行われている。

無効領域処理

無効領域処理は常に自動的に行われている。
吉里吉里のウィンドウをアクティブにして「Shift+F11キー」を押すと
更新矩形の発生の様子を確認できる。
複数の矩形で管理されているため、期待通り効率的に動作する。

無効領域は描画関数を使ったり、レイヤーの見た目が変化する操作をすると自動的に発生する。
Layer クラスの update 関数で明示的に無効領域を発生させることもできる。
プラグインで新たに描画関数を作る時は、
描画を行った範囲を update 関数を使って無効領域にする必要がある点に注意が必要だ。
そうしないと描画が画面に反映されない。

ちなみに update 関数には少し癖がある。
詳しくは onPaintが二度呼ばれる問題 の記事を参照のこと。

遮蔽処理

吉里吉里が遮蔽処理を行うことはあまり知られていないかもしれない。
遮蔽処理は無効領域処理と違って、常に行われるわけではない。
遮蔽処理が行われるのは、レイヤーが不透明であることが保証される場合だけである。
言い変えるとレイヤーが

type==ltOpaque && opacity==255

の時に遮蔽処理が行われるということだ。
(厳密に言うともうちょっと複雑だが)

遮蔽処理をいつの間にか使っているケース

描画処理を少しでも軽くしようと思案した時まず思いつくのが
背景レイヤーの type を不透明度を考慮するデフォルトのltAlphaではなく、
不透明度を無視する ltOpaque にすることだろう。
背景は常に不透明であり、不透明度が必要ないからだ。

背景レイヤーの face を書き込み先の不透明度を保証しない dfOpaque にすると、
さらに描画の効率化が期待できる。
もっとも face はデフォルトで dfAuto なので、type を ltOpaque にすると
いちいち face を設定しなくても dfOpaque が設定された状態と同じになる。

face が dfOpaque だと ltAdditive のような不透明度を考慮しない高速なレイヤ表示タイプを
子レイヤーに対して使うことができるというメリットもある。

そうこうしてレイヤーの type を ltOpaque にすると…そう
「type==ltOpaque かつ opacity==255」の条件を満たすことで
遮蔽処理が行われるようになる。
遮蔽処理のことを知らなくても自動的にさらに描画が効率化されるというわけだ！

とは言え…視覚的には何も変わらないので、
遮蔽処理が行われている事実はわかりにくいかもしれない。

まとめ

無効領域処理と遮蔽処理の効果は、Foooの動作サンプルを見てもわかる通り絶大である。
その存在を意識することで、より効率的な動作をさせることが可能となるだろう。
積極的に活用していきたいところだ。

が！
………遮蔽処理には大きな問題がいくつか潜んでいる。
そのお話はまた次回～

前回の記事で、== nullが激重になる原因が例外が投げられていることにあると述べたが
ソースコードを見て推測しただけで、きっちりトレースして調べたわけではなかったので
本当にそうなのか詳しく調べてみた。

現象の確認

Borland C++ Builder 6 のデバッガでステップ実行してみたところ
やはり例外が投げられていた。
eTJSVariantErrorという種類の例外だ。

この例外はtTJSVariant::NormalCompareのtry-catch節ですぐに捕まえられて
何事もなかったかのようにひっそりと処理されてしまうため
コンソールやSystem.exceptionHandlerなどでは捕捉できない。

負荷の特定

例外が投げられているのは確かだが、
異なる型との == null が重い原因は本当に例外のせいなのだろうか？
負荷の原因を細かく特定するため、ソースコードをいじって速度を計測してみた。

結果から、次のことがわかる。

例外処理が負荷の半分を占めている

そしてもう半分を TJSThrowVariantConvertError 内の処理が占めている。
TJSThrowVariantConvertError 内で行われている処理は
エラーメッセージを作成する文字列処理である。

修正案

実験結果から例外の負荷が非常に大きいとわかったので、
これを回避する方法について考えて見よう。

例外を投げているのはAsRealなので、
AsRealが例外を投げないようにする案がすぐ思いつくが、それはかなりデンジャラスである。
AsRealは他の場所でも使われているし、何よりAsRealが例外を投げるのはおそらく仕様上の動作であり、
その改変による影響範囲は計り知れない。

ここは実験(5)でやっていたように、
AsRealを呼ぶ前にtvtObjectを別途処理するようにするのが最もシンプルで安全な解決策だろう。
そもそもAsRealが呼ばれる時点で、型はInt、Real、Object、Octetの組み合わせしかないので
エラー検出をAsRealにわざわざ頼る必要は、もはやあまりないように思う。

tvtObjectやtvtOctetを判定ではじいて別途処理した場合、
判定回数が増加するというデメリットがある。
しかしそのデメリットは判定の優先順位の見直しである程度軽減できるだろう。
ObjectやOctetと他の型の値を比較するケースより、
IntとRealを比較するケースの方が圧倒的に多いであろうからだ。

さらなる最適化

またこれはあくまでアイデアにすぎないが、tvtObjectのような型の種類を表す定数を
ビットフラグ的な値にすれば、判定をより効率化できるかもしれない。

if(vt==tvtString || val2.vt==tvtString){ }
if(vt==tvtVoid || val2.vt==tvtVoid){ }
if((vt==tvtInt || vt==tvtReal) && (val2.vt==tvtInt || val2.vt==tvtReal)){ }
if(vt==tvtObject || val2.vt==tvtOject){ }
if(vt==tvtOctet || val2.vt==tvtOctet){ }

のような判定は

tjs_unit32 IntRealOR = tvtInt | tvtReal;
tjs_uint32 vtOR = vt | val2.vt; 
if(vtOR & tvtString){ }
if(vtOR & tvtVoid){ }
if(vtOR == IntRealOR){ } // vt != val2.vt なので == で済む
if(vtOR & tvtObject){ }
if(vtOR & tvtOctet){ }

に簡略できる。

まとめ

などなどいろいろ書いてみたけれど…
=== を使えばおおよそ問題を回避できるので、とりあえずそれで！

まずは次のTJSスクリプトを実行してみて欲しい。

function test()
{
  var TEST_NUM = 1000000;
  var begin, end;
  var v = 0;

  Debug.message("Test Num: "+TEST_NUM);

  begin = System.getTickCount();
  for(var i=0; i < TEST_NUM; i++) v == void;
  end = System.getTickCount();
  Debug.message("v(0) ==  void : %d ms".sprintf(end-begin));

  begin = System.getTickCount();
  for(var i=0; i < TEST_NUM; i++) v === void;
  end = System.getTickCount();
  Debug.message("v(0) === void : %d ms".sprintf(end-begin));

  begin = System.getTickCount();
  for(var i=0; i < TEST_NUM; i++) v == null;
  end = System.getTickCount();
  Debug.message("v(0) ==  null : %d ms".sprintf(end-begin));

  begin = System.getTickCount();
  for(var i=0; i < TEST_NUM; i++) v === null;
  end = System.getTickCount();
  Debug.message("v(0) === null : %d ms".sprintf(end-begin));
}

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

TJSの特殊値 void, null の比較の速度を計測している。
これを実行すると次のような結果になる。

Test Num : 1000000
v(0) ==  void : 38 ms
v(0) === void : 33 ms
v(0) ==  null : 11554 ms
v(0) === null : 38 ms

== null が激重！！！

100万回で 10秒近くということは…

1回あたり0.01msもかかっている！

たいしたことないように思えるかもしれないが
60FPSを実現するには17ms以内に１フレーム中の全ての処理を終えないといけないので
たった100回の比較で1ms食うというのは極めて甚大だ。

一方で、void との比較の場合は null のような問題は起きていない。
なぜこのようなことが起こるのか…

void と null の違い

この問題を追求するには、まず void と null の違いを理解する必要がある。
吉里吉里の値に関して詳しくはこちら。
TJS2 リファレンス > 言語リファレンス > 項

void は値が入ってないことを示す特殊値である。
変数に初期値を指定しない時、変数に最初に入っている値がこの void である。
内部実装では tvtVoid型 の値である。

null は何も指し示していないを示すObject型の値である。
内部実装では tvtObject型 の値である。

void と null は一見似たような性質の値に思える。
しかし

void と null は型が異なる

のである。
実はこの違いが決定的な差を生み出している。

== の実装

吉里吉里のソースコードを追いかけて、原因を探ってみよう。
==演算子が行う比較処理の実装は tTJSVariant::NormalCompare にある。
tjsVariant.h
tjsVariant.cpp

実装を見ると、比較する値の型が同一である場合は、なんら問題なく比較が行われている。
問題なのは、比較する値の型が同一でない場合だ。

型が異なる値の比較

型が異なる値を比較する場合、どんな処理が行われるのか。
その実装も tTJSVariant::NormalCompare にある。
型が異なる場合は…

値を実数に変換して比較する

ただしtvtVoid型とtvtString型については特別な実装が施されている。

tvtVoid型を他の型の値を比較する場合、
相手が数値または文字列であれば数値に変換し、voidを0とみなして比較が行われる。
それ以外の型と比較する場合は、常にfalseとなる。

tvtString型を他の型の値を比較する場合、
他方を文字列に変換して比較が行われる。

実数化の中身

実数化の処理はAsRealに記述されている。
tvtObject型の値がどう変換されるのか見ると…

  TJS_CONST_METHOD_DEF(tTVReal, AsReal, ())
  {
    TJSSetFPUE();

    switch(vt)
    {
    case tvtVoid:    return 0;
    case tvtObject:  TJSThrowVariantConvertError(*this, tvtReal);
    case tvtString:  return String->ToReal();
    case tvtInteger: return (tTVReal)Integer;
    case tvtReal:    return Real;
    case tvtOctet:   TJSThrowVariantConvertError(*this, tvtReal);
    }
    return 0.0f;
  }

例外が投げられている！

コレダー！！！
比較の度に例外が投げられていたのでは…
そりゃあー重いはずである。

AsReal から投げられた例外は tTJSVariant::NormalCompare でキャッチされ、falseを返す。

本当の問題

原因は判明したが、よくよく考えるとこの問題は == null に限った問題ではない。
nullでなくても、Object型の値とInt型などの値を比較すれば発生しうる問題だからだ。
またOctetの場合も同様の問題が発生しうることがわかる。

そもそも null と数値を比較するなんてこと自体がおかしいと思うかもしれない。
しかし「数値とオブジェクトの両方が入りうる利便性の高い変数」を作った場合や
「値は設定されているが、不定であることを表す値」として
null を流用しようとした場合などにありえる話である。

対策

問題の原因を理解していれば、この問題を回避するのは簡単だ。

===を使えばいい

===演算子はより厳密な比較を行う比較演算子であり、
異なる型同士の比較の場合は常にfalseを返し､変換は行わない。

ただしObject型同士の比較は == と === とで作用が異なっている点に注意が必要だ。
===演算子はそのオブジェクトのコンテキスト(this)まで比較する。

まとめ

nullと比較する時は == ではなく === を使おう！

前回の「onPaintが二度呼ばれる問題」の記事において、
現象を確認するスクリプトを掲載し忘れていたのでこちらに掲載しておく。
とても簡単なスクリプトで現象を確認できる。

class TestLayer extends Layer
{
  var timer;
  var paintCount = 0;

  function TestLayer(window, parent)
  {
    super.Layer(...);
    timer = new Timer(onTimer, "");
    timer.interval = 1000;
    timer.enabled = true;
  }

  function finalize()
  {
    invalidate timer;
    super.finalize();
  }

  function onTimer()
  {
    Debug.message("onTimer");
    paintCount = 0;
    update();
  }

  function onPaint()
  {
    Debug.message("onPaint "+(++paintCount));
    update();
//  callOnPaint = false;
  }
}

class TestWindow extends Window
{
  function TestWindow()
  {
    super.Window(); 
    add(new TestLayer(this, null));
    visible = true;
  }
}

var window = new TestWindow();
Debug.console.visible = true;

タイマーで1秒ごとにonTimerを呼び出し、そこからupdate関数を呼び出している。
これを実行するとコンソールに…

onTimer
onPaint 1
onPaint 2
onTimer
onPaint 1
onPaint 2

と表示され続けるはずだ。
1度のonTimerの呼び出しに対してonPaintが二度呼ばれているのがわかる。
そしてcallOnPaint=false;のコメントアウトをはずして再度実行すると…

onTimer
onPaint 1
onTimer
onPaint 1

となる。
二度目のonPaintの呼び出しが抑制されている。

この動作は決して誤った動作ではない。
update関数の作用を正しく理解すると、むしろ至極当たり前の動作だと思えるだろう。
本当の問題はupdate関数を誤って使ってしまいがちなところにあるのである。

画面の再描画を効率化しようと思う時、
誰しもがまず思いつくであろうことがLayerクラスのonPaintイベントの利用だ。
データが変更された時にすぐに再描画を行わずupdate関数を呼び出しておいて
画面の描画前に呼ばれるonPaintでまとめて遅延描画する仕組みである。

シンプルな仕組みのように思えるが…
実はそこには大きな落とし穴があった。

onPaintの不可思議な動作

onPaintを使って再描画を効率化した際、逆に再描画が重くなるという現象に遭遇した。
なぜなのか詳しく調べてみると、意外な事実が判明した。

onPaintが連続して二度呼ばれている！

さらに詳しく調べると、最初に実行されたonPaintを抜ける時に
onPaintを呼び出すことを意味するcallOnPaintフラグがtrueになっていることがわかった。
これが原因っぽい気がするが…吉里吉里のリファレンスには

吉里吉里リファレンス Layerクラス callOnPaint
「onPaint イベント が処理し終わるとこのプロパティは自動的に偽に戻されます」

とあるので、onPaintを抜ける時にtrueになっていても問題ではなさそうだ。
しかし念のためにソースコードを見てみると…
………onPaintを呼び出す前にcallOnPaintフラグを落としている！
リファレンスの誤りだろうか。
途中で仕様変更されたのだろうか。

ともかく、やはりonPaintを抜ける時にcallOnPaintフラグがtrueになっているのが問題なかんじがする。
むしろonPaintを呼び出す前にcallOnPaintフラグが落とされるという事実と照らし合わせるとこれは
onPaint内の処理でcallOnPaintフラグを立てるような処理がなされていることを意味する。
しかしonPaint内でupdateを呼び出してはいないし、
callOnPaintフラグを直接いじるようなこともしていない…
ん、まてよ、updateといえば…

描画プラグインで無効領域を報告するためにupdateを呼び出してる！

そう、プラグインで拡張された描画関数を呼び出していたのである。
その中のupdate呼び出しがcallOnPaintフラグをtrueにしている真犯人だったのだ。

さてさてonPaintを抜ける時にcallOnPaintがtrueになる原因は判明したが、
それでなぜonPaintが二度呼ばれることになるのか。
それを理解するにはまず吉里吉里の再描画の仕組みと、
update関数の作用について知る必要がある。

画面の再描画の流れ

吉里吉里はイベントシステムである。
吉里吉里 イベントシステム

画面の再描画もイベントによって管理されている。
画面の再描画は描画イベント(tTVPWinUpdateEvent)が実行された時に行われる。

描画イベントは原則的になんらかの描画関数を呼び出した時に発行される。
また描画関数は描画した領域を無効領域として報告する。
発行された描画イベントはイベントキューに蓄えられる。
イベントキューに蓄えられる描画イベントは原則として各画面につき1個で、
重複するイベントは無視される。
そして描画イベントはイベント配信処理において低優先度で実行される。

描画イベントは実行されるとまず
callOnPaintフラグがtrueな全てのレイヤーに対してonPaintの呼び出しを行う。
次に全てのレイヤーの無効領域の範囲のバッファの更新を行う。
そしてバッファの最終的な合成結果を画面に転送する。

update関数の作用

update関数には3つの作用がある。

1.callOnPaintフラグをtrueにする
2.無効領域を報告する
3.描画イベント(tTVPWinUpdateEvent)を発行する

まず1によって次回の画面の再描画時にonPaintを呼ぶことを予約する。
ここで重要な事実がある。
callOnPaintフラグはあくまでonPaintを呼ぶ予約にすぎないということだ。
callOnPaintフラグを立てただけでは、画面の再描画は行われない。
画面の再描画が行われるのは、描画イベントが発行され実行された時である。

つまりレイヤーの再描画を行わせる目的で
layer.callOnPaint = true;
などとやっても期待するような動作にはならない。
update関数はcallOnPaintフラグをtrueにするのと同時に描画イベントを発行するので、
update関数を呼び出せば期待通り画面の再描画が行われる。

onPaintが二度呼ばれる理由

ここまでわかればonPaintが二度呼ばれる理由はすぐわかる。
onPaint関数内で、update関数を呼び出したらどうなるか。
callOnPaintフラグがtrueになり、描画イベントが発行される。
描画イベントが発行されるということは…画面の再描画が行われる！
そしてcallOnPaintフラグがtrueなので、再びonPaintが呼び出される！

しかしここでまた不思議なことがある。
そのような流れで再びonPaintが呼ばれるのであれば、
onPaintが無限に呼び出され続けることになりそうなものである。
けれどもそうはならない。

これにはイベントキューの処理上の仕様が関係している。
描画イベントは原則としてイベントキューに各画面につき1個しか蓄えられないのだが、
描画イベント実行中は例外的に2個までイベントキューに蓄えられるのである。
つまり現在実行中の描画イベントに加えて、もう1個イベントキューに蓄えられるということである。
これは言い換えれば、画面の再描画が行われるのは
一度のイベント配信処理において最大2回までということである。
よって無限に呼び出されるようなことにはならない。

update関数を呼ばなくても二度目の再描画は行われる

描画イベントは標準の描画関数を呼び出した時にも発行されるので
実はonPaintで標準の描画関数を使った際にも二度目の画面の再描画処理は行われる。

けれどもこれはほとんどの場合問題にならない。
なぜならonPaintで発生した無効領域はその後のバッファの更新で処理されるからだ。
バッファの更新を終えるとそこまでに蓄えられていた無効領域はクリアされる。
二度目の画面の再描画時には無効領域は空になっているので
実際には具体的な再描画はなんら行われずすぐに処理を終える。

しかし1度目のonPaintでupdateを呼び出して2度目のonPaintで描画を行った場合は
再び無効領域が発生し画面の再描画が再度実施されてしまう。
これは非常に無駄な処理になりかねない。

プラグインでupdateを使うのは誤り？

プラグインで独自の描画関数を追加する際には、吉里吉里の標準の描画関数と同じように
描画した領域を無効領域として報告するようにするのが正しい実装である。
もしそうしなければ、レイヤーのバッファの更新が正しく行われない可能性がある。
たまたま吉里吉里の標準の描画関数を一緒に呼び出していて
うまく動作する場合もあるが…たまたまにすぎない。

プラグインからの無効領域の報告にはupdate関数が一般的に使用されているようだ。
しかし無効領域の発生を報告するためだけを目的として
update関数を使用するのはおそらく本来誤りだ。

なぜなら吉里吉里の標準の描画関数は、update関数の2と3の処理しか行わないからである。
つまり1の動作…callOnPaintフラグを立てる処理が余計なのである。
そもそもupdate関数は本来onPaintとセットで使うべきものなのだろう。

しかし無効領域の報告だけを目的としてupdate関数を使ったプラグインが既に多くある。
その現状を踏まえた上で、この問題を回避する方法について考えてみよう。

対策1: onPaintで明示的にcallOnPaintフラグを落とすようにする

ズバリ言って、updateによってcallOnPaintがtrueにされてしまうのであれば
明示的にcallOnPaintフラグを落としてしまえばいい。
ここまでごちゃごちゃと理屈を述べてきたが、実際これだけでおおかた問題を回避できる。

function onPaint()
{
  // なんらかの描画処理

  callOnPaint = false;
}

対策2: onPaintで無駄な再描画をしないようにしておく

再描画フラグなどを独自に設けて、無駄な再描画をしないようにしておくのも良い方法だ。
何かが何かして二度目のonPaintが実行されたとしても、これならば無駄な再描画を確実に回避できる。

function onPaint()
{
  if(!isNeedRedraw) return;
  isNeedRedraw = false;

  // なんらかの描画処理
}

対策3: updateを呼ぶ際にcallOnPaintを維持するようにする

プラグイン側で無効領域の発生を報告するためだけにupdate関数を使うのは誤り！
とは言ってもそのようなことを直接できる関数はupdate関数しかないので
現実問題としてupdate関数を使わざるを得ない。

そこで、意図しない不必要なonPaintの呼び出しを避けるために
callOnPaintフラグを一時保存してupdateを呼び出した後に書き戻すようにする。
たとえば次のような関数を作って使うようにする。

static tjs_uint32 g_Hint_callOnPaint = 0;
static tjs_uint32 g_Hint_update = 0;

bool Update(iTJSDispatch2* pLayer, const RECT* pRect)
{
  // レイヤークラス取得
  tTJSVariant Value;
  TVPExecuteExpression(TJS_W("Layer"), &Value);
  iTJSDispatch2 *pLayerClass = Value.AsObjectNoAddRef();

  // パラメータを用意
  const int PARAM_NUM = 4;
  tTJSVariant Params[PARAM_NUM];
  Params[0] = pRect->left;
  Params[1] = pRect->top;
  Params[2] = pRect->right - pRect->left;
  Params[3] = pRect->bottom - pRect->top;

  // パラメータポインタの配列を用意
  tTJSVariant* ParamPtrs[PARAM_NUM];
  for(int i=0; i < PARAM_NUM; i++) ParamPtrs[i] = &Params[i];

  // callOnPaintを退避
  tTJSVariant callOnPaint;
  if(TJS_FAILED(pLayerClass->PropGet(0, TJS_W("callOnPaint"), &g_Hint_callOnPaint, &callOnPaint, pLayer))) return false;

  // 領域更新
  tTJSVariant result;
  if(TJS_FAILED(pLayerClass->FuncCall(0, TJS_W("update"), &g_Hint_update, &result, PARAM_NUM, ParamPtrs, pLayer))) return false;

  // callOnPaintを復元
  if(TJS_FAILED(pLayerClass->PropSet(0, TJS_W("callOnPaint"), &g_Hint_callOnPaint, &callOnPaint, pLayer))) return false;

  return true;
}

まとめ

onPaint関数はさらにpiledCopy関数の呼び出し時や
トランジッション時にも呼ばれる可能性があるため問題はいっそう複雑だ。
update関数の使い方には細心の注意を心がけたい。

吉里吉里(TJS2)のDictionary(辞書配列)の作成に関する高速化策について
試しにいじってみた内容を具体的にメモがてら書いておく。
コードの黄色文字が追加修正部分。

吉里吉里公式のソースコードはこちら。
https://sv.kikyou.info/trac/kirikiri/

吉里吉里のソースコードのビルドには古いBorland C++ Builderが必要。
kirikiri2\src\core\environ\win32 に
5, 6, 2006, 2007のプロジェクトファイルがあるのでそれを使う。
6を使ったが若干修正が必要だった。いじろうとする人はまずここで躓くかも。

ハッシュテーブルに再構築用の関数を追加

ハッシュテーブルの実装を担っているのはtTJSCustomObjectクラスである。
現在の要素数から適切なハッシュテーブルサイズを計算して
ハッシュテーブルの再構築を行うRebuildHash関数が既にあるので
これを分解してハッシュテーブルを外から細かく操作する関数を追加する。

tjsObject.h
class tTJSCustomObject : public tTJSDispatch
{
  // 略
public:
  // ハッシュテーブル操作
  tjs_int CalcHashSize(tjs_int count);
  void RebuildHashByCount(tjs_int count);
  void RebuildHashBySize(tjs_int size);
}

tjsObject.cpp
// 要素数から適切なハッシュテーブルサイズを計算する
tjs_int tTJSCustomObject::CalcHashSize(tjs_int count)
{
  // decide new hash table size
  tjs_int r, v = count;

  // 略(ReubildHash関数からコピペ)

  return newhashsize;
}

// ハッシュテーブルを要素数指定で再構築する
void tTJSCustomObject::RebuildHashByCount(tjs_int count)
{
  RebuildHashBySize(CalcHashSize(count));
}

// ハッシュテーブルをサイズ指定で再構築する
void tTJSCustomObject::RebuildHashBySize(tjs_int size)
{
  // rebuild hash table
  RebuildHashMagic = TJSGlobalRebuildHashMagic;
  tjs_int newhashsize = size;
  if(newhashsize == HashSize) return;

  // 略(ReubildHash関数からコピペ)
}

辞書に再構築用の関数を追加

Dictionaryの実装はtTJSDictionaryNIクラスにあるのでそこにもリビルド用の関数を追加する。
tTJSCustomObjectクラスのオブジェクトを内包しているので単に処理を受け渡すだけである。
またリビルドが適切かどうか判断するために要素数とハッシュサイズを取得する関数も追加しておく。

tjsDictionary.h
class tTJSDictionaryNI : public tTJSNativeInstance,
              public tTJSSaveStructuredDataCallback
{
  // 略
public:
  // ハッシュテーブル操作
  void RebuildHashByCount(tjs_int count);
  void RebuildHashBySize(tjs_int size);
  tjs_int GetHashSize() const;
  tjs_int GetCount() const;
}

tjsDictionary.cpp
// ハッシュテーブルを要素数指定で再構築する
void tTJSDictionaryNI::RebuildHashByCount(tjs_int count)
{
  Owner->RebuildHashByCount(count);
}

// ハッシュテーブルをサイズ指定で再構築する
void tTJSDictionaryNI::RebuildHashBySize(tjs_int size)
{
  Owner->RebuildHashBySize(size);
}

// ハッシュテーブルサイズを取得
tjs_int tTJSDictionaryNI::GetHashSize() const
{
  return Owner->HashSize;
}

// 要素数を取得
tjs_int tTJSDictionaryNI::GetCount() const
{
  return Owner->Count;
}

rebuild関数を追加する

さてこれで準備が整った。
まず最も簡単な作業から。
吉里吉里のDictionaryクラスにrebuild関数を追加する。

tjsDictionary.cpp
TJS_BEGIN_NATIVE_METHOD_DECL(/*func.name*/rebuild)
{
  TJS_GET_NATIVE_INSTANCE(/* var. name */ni, /* var. type */tTJSDictionaryNI);
  if(!ni->IsValid()) return TJS_E_INVALIDOBJECT;

  tjs_uint32 count = 0;
  if(numparams >= 1 && param[0]->Type() != tvtVoid)
    count = (tjs_int)*param[0];

  ni->RebuildHashByCount(count);

  return TJS_S_OK;
}
TJS_END_NATIVE_STATIC_METHOD_DECL(/*func.name*/rebuild)

アサイン時に予め再構築する

アサインの修正も簡単だ。
Dictionaryのassign関数と、assignStruct関数の具体的な処理は
Assign, AssignStructure関数にあるのでそこをちょこっとだけいじる。

tjsDictionary.cpp
void tTJSDictionaryNI::Assign(iTJSDispatch2 * dsp, bool clear)
{
  // copy members from "dsp" to "Owner"

  // determin dsp's object type
  tTJSArrayNI *arrayni = NULL;
  tTJSDictionaryNI *dicni = NULL;
  if(dsp && TJS_SUCCEEDED(dsp->NativeInstanceSupport(TJS_NIS_GETINSTANCE,
    TJSGetArrayClassID(), (iTJSNativeInstance**)&arrayni)) )
  {
    // convert from array
    if(clear) Owner->Clear();

    // 予め要素数指定で再構築する
    tjs_int count = Owner->Count + arrayni->Items.size()/2;
    if(64 <= count) // 足きり
      Owner->RebuildHashByCount(count);
    
    tTJSArrayNI::tArrayItemIterator i;
    for(i = arrayni->Items.begin(); i != arrayni->Items.end(); i++)
    {
      tTJSVariantString *name = i->AsStringNoAddRef();
      i++;
      if(arrayni->Items.end() == i) break;
      Owner->PropSetByVS(TJS_MEMBERENSURE|TJS_IGNOREPROP, name,
        &(*i),
        Owner);
    }
  }
  else if(dsp && TJS_SUCCEEDED(dsp->NativeInstanceSupport(TJS_NIS_GETINSTANCE,
    TJSGetDictionaryClassID(), (iTJSNativeInstance**)&dicni)) )
  {
    // dictionary
    if(clear) Owner->Clear();
    tAssignCallback callback;
    callback.Owner = Owner;

    // 予め要素数指定で再構築する
    tjs_int count = Owner->Count + dicni->GetCount();
    if(64 <= count) // 足きり
      Owner->RebuildHashByCount(count);

    dsp->EnumMembers(TJS_IGNOREPROP, &tTJSVariantClosure(&callback, NULL), dsp);
  }
  else
  {
    // otherwise
    if(clear) Owner->Clear();
    tAssignCallback callback;
    callback.Owner = Owner;

    dsp->EnumMembers(TJS_IGNOREPROP, &tTJSVariantClosure(&callback, NULL), dsp);

  }
}

void tTJSDictionaryNI::AssignStructure(iTJSDispatch2 * dsp,
  std::vector &stack)
{
  // assign structured data from dsp
  tTJSDictionaryNI *dicni = NULL;
  // tTJSArrayNI *dicni = NULL; // 元々これだったけどミス？
  if(TJS_SUCCEEDED(dsp->NativeInstanceSupport(TJS_NIS_GETINSTANCE,
    ClassID_Dictionary, (iTJSNativeInstance**)&dicni)) )
  {
    // copy from dictionary
    stack.push_back(dsp);
    try
    {
      Owner->Clear();

      // 予め要素数指定で再構築する
      tjs_int count = dicni->GetCount();
      if(64 <= count) // 足きり
        Owner->RebuildHashByCount(count);
      
      tAssignStructCallback callback;
      callback.Dest = Owner;
      callback.Stack = &stack;

      dsp->EnumMembers(TJS_IGNOREPROP, &tTJSVariantClosure(&callback, NULL), dsp);
    }
    catch(...)
    {
      stack.pop_back();
      throw;
    }
    stack.pop_back();
  }
  else
  {
    TJS_eTJSError(TJSSpecifyDicOrArray);
  }
}
void tTJSDictionaryNI::AssignStructure

ロード時に予め再構築する

ロード時の処理は(const)がつく場合とつかない場合とで処理が異なるが
とりあえず(const)がつく場合だけ修正。

この修正は少々手間だ。
データ文字列の解析時に構文解析と意味解析を同時に行っているため、
要素を実際に追加する前に要素の総数がわからないからである。
そこで要素をすぐに辞書に追加せずにいったんリストに蓄え、
要素の総数が判明したら一気に要素を追加するようにする。

まず、式ノードに追加要素を一時保管する処理を追加する。

tjsInterCodeGen.h
class tTJSExprNode
{
  // 略
protected:
  // 追加要素一時保管処理
  struct SElementData
  {
    tTJSString name;
    tTJSVariant value;
  };
  list< SElementData* > *pElementTempList;
public:
  void AddDictionaryElementExBegin();
  void AddDictionaryElementEx(const tTJSString & name, const tTJSVariant & val);
  void AddDictionaryElementExEnd();
}

tjsInterCodeGen.cpp
#include "tjsObject.h"
#include "tjsDictionary.h"

tTJSExprNode::tTJSExprNode()
{
  // 略  
  pElementTempList = NULL;
}

// 辞書に要素追加開始
void tTJSExprNode::AddDictionaryElementExBegin()
{
  pElementTempList = new list< SElementData* >;
}

// 辞書に要素追加
void tTJSExprNode::AddDictionaryElementEx(const tTJSString & name, const tTJSVariant & val)
{
  SElementData* pData = new SElementData;
  pData->name = name;
  pData->value = val;
  pElementTempList->push_back(pData);
}

// 辞書に要素追加終了
void tTJSExprNode::AddDictionaryElementExEnd()
{
  tjs_uint32 Size = pElementTempList->size();
  if(Size == 0)
  {
    delete pElementTempList;
    pElementTempList = NULL;
    return;
  }

  // 予め要素数指定で再構築する
  if(64 <= Size) // 足きり
  {
    tTJSDictionaryNI *dicni = NULL;
    tTJSVariantClosure clo = Val->AsObjectClosureNoAddRef();
    if(TJS_SUCCEEDED(clo.Object->NativeInstanceSupport(TJS_NIS_GETINSTANCE,
      TJSGetDictionaryClassID(), (iTJSNativeInstance**)&dicni)) )
    {
      dicni->RebuildHashByCount(Size);
    }
  }
  
  // 辞書に蓄えておいた要素を流し込む
  list< SElementData* >::iterator it  = pElementTempList->begin();
  list< SElementData* >::iterator end = pElementTempList->end();
  while(it != end)
  {
    SElementData* pElement = *it;
    AddDictionaryElement(pElement->name, pElement->value);
    delete pElement;
    it++;
  }
  pElementTempList->clear();

  delete pElementTempList;
  pElementTempList = NULL;
}

次に構文解析処理で一時保管用関数を使用するように修正。
AddDictionaryElementをAddDictionaryElementExに置き換える。

※追記
以下のtjs.tab.cppはtjs.yから生成されるファイルで、
正式にはそちらのファイルを修正してbisonを通して生成すべきのようです。
じんさんご指摘ありがとうございます。

tjs.tab.cpp
/* Line 1455 of yacc.c  */
#line 839 "syntax/tjs.y"
    { tTJSExprNode *node =
                      cc->MakeNP0(T_CONSTVAL);
                      iTJSDispatch2 * dsp = TJSCreateDictionaryObject();
                      node->SetValue(tTJSVariant(dsp, dsp));
                      dsp->Release();
                      cc->PushCurrentNode(node);
                      cn->AddDictionaryElementExBegin(); ;}
    break;

  case 255:
  
/* Line 1455 of yacc.c  */
#line 846 "syntax/tjs.y"
    { (yyval.np) = cn; 
      cn->AddDictionaryElementExEnd();
      cc->PopCurrentNode(); ;}
    break;

  case 259:

/* Line 1455 of yacc.c  */
#line 859 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (4)].num)), - lx->GetValue((yyvsp[(4) - (4)].num))); ;}
    break;

  case 260:

/* Line 1455 of yacc.c  */
#line 860 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (4)].num)), + lx->GetValue((yyvsp[(4) - (4)].num))); ;}
    break;

  case 261:

/* Line 1455 of yacc.c  */
#line 861 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (3)].num)), lx->GetValue((yyvsp[(3) - (3)].num))); ;}
    break;

  case 262:

/* Line 1455 of yacc.c  */
#line 862 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (3)].num)), tTJSVariant()); ;}
    break;

  case 263:

/* Line 1455 of yacc.c  */
#line 863 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (3)].num)), (yyvsp[(3) - (3)].np)->GetValue()); ;}
    break;

  case 264:

/* Line 1455 of yacc.c  */
#line 864 "syntax/tjs.y"
    { cn->AddDictionaryElementEx(lx->GetValue((yyvsp[(1) - (3)].num)), (yyvsp[(3) - (3)].np)->GetValue()); ;}
    break;

まとめ

足きりの定数は適当に決めたものである。
pElementTempListは例外が飛んだ場合などに備えてクリア処理やデストラクタでも破棄すべきだろう。
辞書生成直後に再構築するようなケースではコンストラクタを通した方がより無駄がないと思うが
今回はできるだけ元の構造をいじらないアプローチにしてみた。

Dictionaryの作成が遅くなる理由が判明したわけだが、
これはちょっと工夫すれば格段に高速化できる余地がありそうだ。
しかしズバリ言って、現バージョンの吉里吉里ではおそらく解決方法はない。
Dictionaryクラスには内部のハッシュテーブルを操作するような関数が存在しないからだ。
そこで吉里吉里のソースコードをいじる形で、いくつか解決案を考えてみよう。

案１: 検索しないようにする

辞書への要素の追加が重くなっているそもそもの原因は、
同一キーの要素がないか検索を行っている処理にある。
辞書に追加するキーに重複がないと予めわかっている場合は、
この検索処理は完全に無駄な処理だ。

検索処理を省いてしまえば、ハッシュテーブルが小さくても
要素の追加処理の負荷は軽微なものになる。
これは抜本的な解決策のように思える。

例えば要素追加時に検索を行わないようにするDirtyフラグを作り、
絶対に同一キーの要素が追加されないとわかっている時にフラグをONにして要素を追加し、
追加し終わったらフラグをOFFにする…といったような実装が考えられる。

しかし同一キーの要素がないか検索しないということは底知れない危険性を孕んでいる。
人間はミスをする生き物なので、うっかり同一キーの要素を入れてしまったり
何かの手違いでフラグをONにしっぱなしにしてしまう可能性がある。
要素を一気に流し込むassignのような関数内でON/OFFを行うようにすれば
OFFにし忘れるミスは防げるが…人為的ミスが入り込む可能性は依然拭いきれない。

仮に同一キーの要素を複数ハッシュテーブルに追加してしまった場合…
おそらくソレによって生じるバグの原因を突き止めることは相当困難だろう。
検索自体を省く方法は確実に効果が見込めるが、そこには大きなリスクがつきまとう。

案２: 検索を高速化する

検索を省かず、検索処理を見直して高速化する方法はどうだろう。
例えば同一値のリストをただのリストではなく『ソート済みリスト』にする。
ソート済みリストにすればリストの最後まで要素を調べなくても
リストの途中で同一キーの要素がないことを判断することが可能になる。
平均２倍程度の高速化が期待できる。

しかしリストをソート済みリストにすると、
高速化の目的で行われている別のトリックが使えなくなる問題がある。
そのトリックとは、要素が検索された時にその要素をリストの先頭に繰り上げて
次回の検索を最適化する処理だ。
この処理ができなくることとのトレードオフはなんとも難しい。
またこのような挙動変更は互換の点においてもややリスクがある。

案３: ハッシュテーブルを予め大きくしておく

検索が遅くなる原因は、ハッシュテーブルが小さすぎて
同一ハッシュ値の要素のリストがものすごく伸びてしまうことにある。
これは裏を返せば、ハッシュテーブルを予め十分な大きさにしてから
要素を追加すれば問題を回避できるということである。

この方法が効果的なシチュエーションは限定的ではあるが、
検索処理は省かないし、人為的ミスが入り込む余地も少ないし、
挙動も変化しないので、リスクはほとんどないと言っていい。
そして何よりDictionaryの仕組み自体には手を入れないので
ほんの少しの修正で実現可能だ。

ただし追加する要素数が少ない場合は、
ハッシュテーブルの再構築が逆に無駄な処理になるので
ある程度の数で処理を足きりする必要があるだろう。
そのためにも具体的にハッシュテーブルの初期サイズがどのくらいなのか確認しておこう。

吉里吉里のハッシュテーブルの実装はこちら。
tjsObject.h
tjsObject.cpp

初期サイズはtjsObject.hのTJS_NAMESPACE_DEFAULT_HASH_BITSで定義されている。
値は3だ。実際のテーブルサイズは(1<<bits)で計算されるので…
要するに8である。すごく小さい！

そしてこのテーブルサイズにおける適切な要素数は
tjsObject.cppの”decide new hash table size”の部分で行われている計算式に基づけば、
テーブルサイズの半分からその半分の間…つまり2～3である。

ハッシュテーブルのサイズを予め大きくしておくことはかなり効果がありそうだ。
それではこの方向性で具体的な高速化策を考えてみよう。

高速化策１: ハッシュテーブルを再構築する関数を追加する

RebuildHashの仕組みを流用して、ハッシュテーブルを
指定の要素数に適したサイズに再構築するrebuild関数を追加する。
スクリプトで要素を大量に追加する前にこの関数を呼び出すことで
大幅な高速化が期待できる。

高速化策２: ロード時に予め再構築する

辞書に大量の要素を追加する際に極めて重くなるのは、
辞書の読み込み処理においても同じである。
そこで辞書の読み込み処理の部分でも、
ハッシュテーブルを適切なサイズにしてから要素を追加するように改造する。

具体的には辞書に追加する要素をいったんリストに蓄え、
要素数が判明したら再構築を行って、その後で辞書に要素を流し込むようにする。

高速化策３: アサイン時に予め再構築する

配列や辞書のアサイン時にもはやり同様に重くなる。
アサイン時には追加要素数は自明なので、この改造はすごく簡単だ。

実験してみる

で、実際にこの３つの対策を施したexeを作りテストしてみた。
テストスクリプトは以下の通りだ。

class SimpleWindow extends Window
{
  function SimpleWindow()
  {
    super.Window();
    add(new Layer(this, null));
    visible = true;
  }
  function finalize()
  {
    super.finalize();
  }
}

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

//////////////////////////////////////////////////////////////////////
// 補助
//////////////////////////////////////////////////////////////////////

// 計測開始/終了
var g_timeBegin;
function testBegin()
{
  System.doCompact(); // メモリ強制開放

  g_timeBegin = System.getTickCount();
}
function testEnd()
{
  return System.getTickCount() - g_timeBegin;
}

//////////////////////////////////////////////////////////////////////
// テスト本体
//////////////////////////////////////////////////////////////////////

var FIND_NUM = 1000; // 検索回数
var FILE_NAME = System.dataPath+"test.txt"; // 一時ファイル名
  
function testMain(CreateNum, testCase, count)
{
  //------------------------------------------------------------------
  // 準備
  //------------------------------------------------------------------

  var CREATE_NUM = CreateNum; // 作成要素数

  // 検索対象をランダムに作成
  // *2 して「ヒットしないもの」も探す
  var findTable = [];
  for (var i = 0; i < FIND_NUM; i++)
  {
    findTable[i] = int (Math.random()*(CREATE_NUM*2-1));
  }

  //------------------------------------------------------------------
  // 配列
  //------------------------------------------------------------------

  // 作成
  var array1 = [];
  testBegin();
  for(var i = 0; i < CREATE_NUM; i++)
  {
    var name = "hash_number_is_" + "%06d".sprintf(i);
    array1[i] = name;
  }
  var timeArrayCreate = testEnd();

  // 保存
  testBegin();
  array1.saveStruct(FILE_NAME);
  var timeArraySave = testEnd();

  // 読み込み
  testBegin();
  var array2 = Scripts.evalStorage(FILE_NAME);
  var timeArrayLoad = testEnd();

  // アサイン実行
  testBegin();
  var array3 = [];
  array3.assign(array1);
  var timeArrayAssignA = testEnd();

  // 検索
  // findは返り値を受けとらないと処理されないことに注意
  testBegin();
  var temp;
  for (var i = 0; i < FIND_NUM; i++)
    temp = array1.find("hash_number_is_" + "%06d".sprintf(findTable[i]));
  var timeArrayFind = testEnd();

  //------------------------------------------------------------------
  // 辞書
  //------------------------------------------------------------------

  // 作成
  var dictionary1 = %[];
  testBegin();
  for(var i = 0; i < CREATE_NUM; i++)
  {
    var name = "hash_number_is_" + "%06d".sprintf(i);
    dictionary1[name] = i;
  }
  var timeDictionaryCreate = testEnd();

  // 作成2(指定数でRebuildHashする)
  var dictionaryX = %[];
  var timeDictionaryCreate2 = -1;
  if(typeof global.Dictionary.rebuild != "undefined")
  {
    testBegin();
    (global.Dictionary.rebuild incontextof dictionaryX)(CREATE_NUM); // 追加関数
    for(var i = 0; i < CREATE_NUM; i++)
    {
      var name = "hash_number_is_" + "%06d".sprintf(i);
      dictionaryX[name] = i;
    }
    timeDictionaryCreate2 = testEnd();
  }

  // 保存
  testBegin();
  (global.Dictionary.saveStruct incontextof dictionary1)(FILE_NAME);
  var timeDictionarySave = testEnd();

  // 読み込み
  testBegin();
  var dictionary2 = Scripts.evalStorage(FILE_NAME);
  var timeDictionaryLoad = testEnd();

  // アサイン実行(辞書:assign)
  testBegin();
  var dictionary3 = %[];
  (global.Dictionary.assign incontextof dictionary3)(dictionary1);
  var timeDictionaryAssignD = testEnd();

  // アサイン用配列作成
  var dictionary_array = [];
  for(var i = 0; i < CREATE_NUM; i++)
  {
    var name = "hash_number_is_" + "%06d".sprintf(i);
    dictionary_array[i*2] = name;
    dictionary_array[i*2+1] = i;
  }

  // アサイン実行(配列)
  testBegin();
  var dictionary4 = %[];
  (global.Dictionary.assign incontextof dictionary4)(dictionary_array);
  var timeDictionaryAssignA = testEnd();

  // アサイン実行(辞書:assignStruct)
  testBegin();
  var dictionary5 = %[];
  (global.Dictionary.assignStruct incontextof dictionary5)(dictionary1);
  var timeDictionaryAssignS = testEnd();

  // 辞書検索時間測定
  testBegin();
  for (var i = 0; i < FIND_NUM; i++)
    temp = dictionary1["hash_number_is_" + "%06d".sprintf(findTable[i])];
  var timeDictionaryFind = testEnd();

  // 辞書検索時間測定(指定数でRebuildHashしたもの)
  var timeDictionaryFind2 = -1;
  if(timeDictionaryCreate2 != -1)
  {
    testBegin();
    for (var i = 0; i < FIND_NUM; i++)
      temp = dictionaryX["hash_number_is_" + "%06d".sprintf(findTable[i])];
    timeDictionaryFind2 = testEnd();
  }

  //------------------------------------------------------------------
  // 記録
  //------------------------------------------------------------------

  data_timeArrayCreate[testCase][count] = timeArrayCreate;
  data_timeArraySave[testCase][count] = timeArraySave;
  data_timeArrayLoad[testCase][count] = timeArrayLoad;
  data_timeArrayAssignA[testCase][count] = timeArrayAssignA;
  data_timeArrayFind[testCase][count] = timeArrayFind;

  data_timeDictionaryCreate[testCase][count] = timeDictionaryCreate;
  data_timeDictionaryCreate2[testCase][count] = timeDictionaryCreate2;
  data_timeDictionarySave[testCase][count] = timeDictionarySave;
  data_timeDictionaryLoad[testCase][count] = timeDictionaryLoad;
  data_timeDictionaryAssignD[testCase][count] = timeDictionaryAssignD;
  data_timeDictionaryAssignA[testCase][count] = timeDictionaryAssignA;
  data_timeDictionaryAssignS[testCase][count] = timeDictionaryAssignS;;
  data_timeDictionaryFind[testCase][count] = timeDictionaryFind;
  data_timeDictionaryFind2[testCase][count] = timeDictionaryFind2;

  //------------------------------------------------------------------
  // 後始末
  //------------------------------------------------------------------

  invalidate findTable;

  invalidate array1;
  invalidate array2;
  invalidate array3;

  invalidate dictionary1;
  invalidate dictionary2;
  invalidate dictionary3;
  invalidate dictionary4;
  invalidate dictionary5;
  invalidate dictionary_array;
  invalidate dictionaryX;
}

//////////////////////////////////////////////////////////////////////
// テストループ
//////////////////////////////////////////////////////////////////////

var data_createNum = [];

var data_timeArrayCreate = [];
var data_timeArraySave = [];
var data_timeArrayLoad = [];
var data_timeArrayAssignA = [];
var data_timeArrayFind = [];
var data_timeDictionaryCreate = [];
var data_timeDictionaryCreate2 = [];
var data_timeDictionarySave = [];
var data_timeDictionaryLoad = [];
var data_timeDictionaryAssignD = [];
var data_timeDictionaryAssignA = [];
var data_timeDictionaryAssignS = [];
var data_timeDictionaryFind = [];
var data_timeDictionaryFind2 = [];

var testCase = 0;
for(var CreateNum=100000; CreateNum<=100000; CreateNum+=10000)
{
  data_createNum[testCase] = CreateNum;

  // 計測データを格納する配列を作成  
  data_timeArrayCreate[testCase] = new Array();
  data_timeArraySave[testCase] = new Array();
  data_timeArrayLoad[testCase] = new Array();
  data_timeArrayAssignA[testCase] = new Array();
  data_timeArrayFind[testCase] = new Array();
  data_timeDictionaryCreate[testCase] = new Array();
  data_timeDictionaryCreate2[testCase] = new Array();
  data_timeDictionarySave[testCase] = new Array();
  data_timeDictionaryLoad[testCase] = new Array();
  data_timeDictionaryAssignD[testCase] = new Array();
  data_timeDictionaryAssignA[testCase] = new Array();
  data_timeDictionaryAssignS[testCase] = new Array();
  data_timeDictionaryFind[testCase] = new Array();
  data_timeDictionaryFind2[testCase] = new Array();

  // 割り込みによって値にぶれが出る場合があるので
  // 同じケースについて何度か計測する
  // 計測したうちのもっとも小さい値を使う
  for(var count=0; count<5; count++)
  {
    testMain(CreateNum, testCase, count);
  }
  
  // 計測データを昇順にソート  
  data_timeArrayCreate[testCase].sort();
  data_timeArraySave[testCase].sort();
  data_timeArrayLoad[testCase].sort();
  data_timeArrayAssignA[testCase].sort();
  data_timeArrayFind[testCase].sort();
  data_timeDictionaryCreate[testCase].sort();
  data_timeDictionaryCreate2[testCase].sort();
  data_timeDictionarySave[testCase].sort();
  data_timeDictionaryLoad[testCase].sort();
  data_timeDictionaryAssignD[testCase].sort();
  data_timeDictionaryAssignA[testCase].sort();
  data_timeDictionaryAssignS[testCase].sort();
  data_timeDictionaryFind[testCase].sort();
  data_timeDictionaryFind2[testCase].sort();

  // 出力
  Debug.message("===========================================");
  Debug.message("create num           : %8d"
    .sprintf(data_createNum[testCase]));
  Debug.message("find num             : %8d"
    .sprintf(FIND_NUM));
  Debug.message("array      create    : %8d ms"
    .sprintf(data_timeArrayCreate[testCase][0]));
  Debug.message("array      save      : %8d ms"
    .sprintf(data_timeArraySave[testCase][0]));
  Debug.message("array      load      : %8d ms"
    .sprintf(data_timeArrayLoad[testCase][0]));
  Debug.message("array      assignA   : %8d ms ※arrayをassign"
    .sprintf(data_timeArrayAssignA[testCase][0]));
  Debug.message("array      find      : %8d ms"
    .sprintf(data_timeArrayFind[testCase][0]));
  Debug.message("dictionary create    : %8d ms"
    .sprintf(data_timeDictionaryCreate[testCase][0]));
  Debug.message("dictionary create2   : %8d ms ※予めrebuildしたもの"
    .sprintf(data_timeDictionaryCreate2[testCase][0]));
  Debug.message("dictionary save      : %8d ms"
    .sprintf(data_timeDictionarySave[testCase][0]));
  Debug.message("dictionary load      : %8d ms"
    .sprintf(data_timeDictionaryLoad[testCase][0]));
  Debug.message("dictionary assignD   : %8d ms ※dictionaryをassign"
    .sprintf(data_timeDictionaryAssignD[testCase][0]));
  Debug.message("dictionary assignA   : %8d ms ※arrayをassign"
    .sprintf(data_timeDictionaryAssignA[testCase][0]));
  Debug.message("dictionary assignS   : %8d ms ※dictionaryをassignStruct"
    .sprintf(data_timeDictionaryAssignS[testCase][0]));
  Debug.message("dictionary find      : %8d ms"
    .sprintf(data_timeDictionaryFind[testCase][0]));
  Debug.message("dictionary find2     : %8d ms ※予めrebuildしたもの"
    .sprintf(data_timeDictionaryFind2[testCase][0]));
  Debug.message("===========================================");

  testCase++;
}

ループしてないfor文や、いちいちデータを蓄えてる無駄っぽい処理はグラフ作成用である。
まずは改造前のkrkr.exeで速度を計測してみよう。
手持ちの2.32.2.426で試した。

create num           :   100000
find num             :     1000
array      create    :       77 ms
array      save      :      515 ms
array      load      :      127 ms
array      assignA   :        1 ms ※arrayをassign
array      find      :     5311 ms
dictionary create    :     5685 ms
dictionary create2   :       -1 ms ※予めrebuildしたもの
dictionary save      :      976 ms
dictionary load      :     2579 ms
dictionary assignD   :     1355 ms ※dictionaryをassign
dictionary assignA   :     5252 ms ※arrayをassign
dictionary assignS   :     1327 ms ※dictionaryをassignStruct
dictionary find      :       85 ms
dictionary find2     :       -1 ms ※予めrebuildしたもの

そしてこちらが改造版。

create num           :   100000
find num             :     1000
array      create    :       90 ms
array      save      :      549 ms
array      load      :      121 ms
array      assignA   :        2 ms ※arrayをassign
array      find      :     5402 ms
dictionary create    :     5646 ms
dictionary create2   :       88 ms ※予めrebuildしたもの
dictionary save      :     1025 ms
dictionary load      :      216 ms
dictionary assignD   :       32 ms ※dictionaryをassign
dictionary assignA   :       18 ms ※arrayをassign
dictionary assignS   :       32 ms ※dictionaryをassignStruct 
dictionary find      :       86 ms
dictionary find2     :        1 ms ※予めrebuildしたもの

軽く10～100倍速くなってる！

ちょっと驚きの数字だが、もっともこれはあくまで追加する要素数が10万個の場合の数値である。
辞書の作成が重い原因は、リストが伸びれば伸びるほど検索に時間がかかることに起因しているので
要素数に対する処理時間のグラフは２次曲線を描く。
またキーとなっている文字列の長さも大きく影響している。
つまり追加する要素数がめちゃくちゃ多いからこそこれほど劇的な差になっているのであって
これをもってして辞書が超高速になったと思うのは早合点である。

しかしこの高速化策によって要素数に対する処理時間のグラフは一次曲線(直線)になる。
この高速化策は導入コストもリスクも低いので、ほとんどの場合有用だろう。
実際にグラフを作ってみたのでご覧いただきたい。

改造前

改造版

検索のグラフがちょっとがくがくしてるが、検索回数が少ないのと、
検索をランダムにしているためだろう。検索回数は1000回固定である。

まとめると…
Dictionaryは決して遅くはない。むしろ速い。
しかし使い方を誤ると極端に遅くなってしまう場合がある。
けれどもその仕組みを理解し適切に扱うことで問題を回避できる。
ということである。

ご参考までに。

吉里吉里のDictionaryの作成がやたらめったら遅いという話を
方々で見かけたので、こちらのサイトを参考に原因を探ってみた。
※有用な情報を公開されている先人の方々に感謝いたします。

吉里吉里/KAG小技集 > 配列と辞書、どちらが早い？

掲載されているテストスクリプトを実行してみると…

配列作成中 ...完了。
ary作成時間は93msです。
hash作成時間は5562msです。
ary検索時間は2msです。
hash検索時間は63msです。

確かに書かれているような結果になった。
しかし吉里吉里のソースコードを見ながら原因を探っていくうちに
どうもこのテストスクリプトにはいくつか複雑な問題があることがわかった。

Dictionaryの仕組み

Dictionaryクラスは連想配列(辞書配列)の一種で『ハッシュテーブル』という仕組みで実装されている。
通常の配列は整数値をインデックスとして使いその値の位置にデータを格納するが、
連想配列は文字列などの任意の値をキーとして使いデータを格納する。
Dictionaryクラスは文字列をキーとするハッシュテーブルである。

ハッシュテーブルの構造は基本的にはただの配列だ。
ハッシュテーブルではキーからハッシュ値を計算し、
そのハッシュ値をインデックスとして配列に値を格納する。

通常の配列に比べて余計な手間がかかっているように思うかもしれないが
このようにすることでキーに整数以外の値を使うことができるし、
要素の挿入・削除・検索を通常の配列よりもずっと高速に行うことができる。

ハッシュテーブルの落とし穴

しかしハッシュテーブルには2つの大きな落とし穴がある。

1つ目の落とし穴は異なるキーであってもハッシュ値が同じ値になる場合があるということである。
これはすなわちテーブルの同じ位置に2つ以上の要素が入る可能性があることを意味する。
Dictionaryではテーブルに格納される要素を連結リストにして複数の値を格納できるようにしている。

2つ目の落とし穴は、テーブルとなる配列を十分な大きさで確保しておかなければならないという点だ。
キーから計算されたハッシュ値はテーブルのサイズに合わせて切り取って使われる。
しかしテーブルのサイズが小さすぎると、切り取られたハッシュ値が高い頻度で重複するようになる。
ハッシュ値が頻繁に重複すると、テーブルの各要素のリストがどんどん伸びていくような形になる。
最悪の場合、ただのリストとほとんど変わらなくなり、連想配列である恩恵が失われてしまう。

かと言って、使うかもわからないの巨大なテーブルを常に用意しておくのもそれはそれで無駄だ。
キャッシュ効率が悪くなり逆に遅くなってしまう場合もある。
すなわちハッシュテーブルを効果的に使うには、適切なテーブルのサイズをいかに決めるか。
そこが肝心なのである。

Array.findが速すぎる

ハッシュテーブルについて理解したところで、さっきのテストスクリプトの結果を見てみよう。
1つ明らかに不可解な点がある。
配列の検索に比べて辞書の検索が遅すぎるのだ。
辞書の検索は配列に比べて高速になるはずである。
というかよくよく考えてみると辞書の検索が遅いわけではなく、むしろ…

配列の検索が爆速すぎる！

いくらなんでも速過ぎである。
吉里吉里のソースコードを見てみると原因は明らかだった。

tjsArray.cpp
findの実装は877行目あたり(2013/2/28現在)

Array.findは、戻り値を返す先がないと何も処理しないような実装になってる！
つまりそもそも検索処理は一切行われていない。
爆速なのは当たり前だ。

正しく検索されるようにするには

var temp = ary.find("hash_number_is_" + "%06d".sprintf(chknums[i]));

のようにして、返り値の受け取り先を用意する必要がある。
このようにして実行しなおすと…

配列作成中 ...完了。
ary作成時間は94msです。
hash作成時間は5520msです。
ary検索時間は5350msです。
hash検索時間は37msです。

期待通り(？)激遅になった！

辞書検索が速くなっているが、これはおそらくキャッシュ効率の影響だろう。

辞書作成が重い原因

そしてもう1つ不可解な点がある。
それは辞書作成の遅さに対して辞書検索が速すぎる点だ。
数値が小さいのは試行回数が少ないからだが、それにしてもちょっと速い。
不可解じゃない？いやいや不可解なのである。
なぜ不可解なのか説明するには、
そもそも辞書作成がなぜこんなに遅くなってるのかについてまず言及する必要があるだろう。

吉里吉里のDictionaryのソースコードはこちら。
tjsDictionary.cpp

辞書作成が遅い原因をずばり言おう。
辞書作成が遅いのは、辞書に追加する要素数に対して

ハッシュテーブルが小さすぎるせいである。

ハッシュテーブルが小さいとどういうことが起こるのか。
それはさっき述べた通りだ。
ハッシュ値の重複が頻繁に起き、ハッシュテーブル内の同じ位置に要素がどんどん追加されていく。
同ハッシュ値の要素はリストとして繋がれていく。
ハッシュテーブルが小さく、追加する要素数がものすごく多い場合、
このリストはものすごい長さになってしまう。

ただ…要素をリストに繋ぐ処理の負荷は軽微なもので、それ自体はさほどたいした負荷ではない。
重さの原因になっているのは、リストに新しく要素を繋ぐ際に、
リスト内に同じキーの要素がないか検索する処理の部分だ。
特に前出のサンプルスクリプトのようなケースの場合、
リスト内に同じキーの要素があるはずがないので
処理上最悪のケース…すなわちリストの頭から末尾まで毎回毎回検索が行われる。
この処理による負荷は膨大なものになる。

すなわちハッシュテーブルが小さいことによって、
辞書検索処理が極めて重くなってしまっているというのが、
辞書作成が異常に重くなる真相である。

辞書検索が速すぎる

これを理解すると、さっき辞書検索が速すぎる！と言った意味がわかるだろう。
むちゃくちゃ速いというわけではないが、なんだか想像より速い。
辞書検索処理はハッシュテーブルが小さいことによってかなり重くなってるはずなのだ。
配列の時のように検索処理自体が行われなくなっているわけでもない。
検索はキッチリ行われている！
どういうことなのか。

これはソースコードを注意深く見ると理由がわかる。
辞書検索を速くしているのは、RebuildHashという仕組みだ。
1.5秒ごとに発生するイベントによって辞書にRebuildHashフラグが立てられ、
このフラグが立った辞書を参照するとハッシュテーブルの再構築が行われるという
トリッキーな仕組みである。

ハッシュテーブルの再構築とは、辞書に格納されている要素数に応じて
ハッシュテーブルのサイズを調整するという処理だ。
この処理によってハッシュテーブルが拡張され同一要素のリストが十分に短くなる。
同一要素のリストが十分に短くなれば、リスト検索の負荷もほとんどなくなる。
ゆえに速くなるのである。

ハッシュテーブルの再構築の効果

ここでまたテストスクリプトを振り返ってみよう。
このテストスクリプトの2つめの問題は
辞書を作成した後に「完了。」と表示を行っている部分にある。
それこそが辞書検索が速くなっている鍵なのだ！

吉里吉里はイベントシステムであり、溜まったイベントはシステムに処理が返った時に実行される。
つまり『1.5秒ごとに発生するイベント』は、システムに処理を返した時に初めて実行される。
そう、「完了。」と表示している部分、そこでシステムに処理が返りイベントが実行されているのである。
これにより次に辞書を参照した時、最初に辞書の再構築が実施される。

この動作を確認するために、試しに辞書検索速度を計測する前に
1回だけ辞書検索する処理を入れて計測してみよう。

配列作成中 ...完了。
ary作成時間は94msです。
hash作成時間は5861msです。
ary検索時間は5497msです。
hash検索時間は1msです。

辞書検索が爆速！

実は30ms以上かかっていたのはハッシュテーブルの再構築の処理であり、
辞書検索自体はこれだけ高速なのである。
ただしハッシュテーブルが適切な大きさならば、だ。

次に完了と表示している部分を削除して実行してみよう。
これで、ハッシュテーブルが再構築されなかった場合の辞書検索の速度がわかる。

配列作成中 ...
ary検索時間は5354msです。
hash検索時間は90msです。

再構築処理分を加味した値よりちょっと重い。
再構築された場合と比べると…尋常じゃなく重い！
これがハッシュテーブルのサイズが適切でない場合の辞書検索の重さである。
辞書作成時にはこの負荷が大きくのしかかっているのだ。

ということで辞書作成がなぜ重いのか、原因が明確になった。
この問題を解決する方法についてはまた次回～