Dictionaryの具体的修正点

吉里吉里(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は例外が飛んだ場合などに備えてクリア処理やデストラクタでも破棄すべきだろう。
辞書生成直後に再構築するようなケースではコンストラクタを通した方がより無駄がないと思うが
今回はできるだけ元の構造をいじらないアプローチにしてみた。