LNK1248: イメージ サイズが最大許容サイズ (80000000) を超えています

ゼルコバの木の基本データはカードリンクテーブルと結婚リンクテーブルという2つの固定サイズのテーブルとして管理されている.その管理方式はゼルコバの木の長い開発史の中でなんども変遷してきた.テーブルにはデータオブジェクトへのリンクが格納され,「参照番号」と呼ぶフィールドでレコードを一意に識別している.当初はテーブルを全スキャンする方法でレコードの検索を行っていたが,レコードの追加・削除によってたびたび穴あきの状態になるのでテーブルの前詰めを行うようになった.現在は「テーブルの前詰め」は廃止され,代わりに「ルックアップテーブル」を使った管理に変更されている.これにはUNDOの導入・整備が進んだことなども関係しているのではないかと思われる.

参照番号=レコード番号という関係が維持できれば,テーブルにもっとも効率的にアクセスできるので,その方向に向かっていた時期もあったが,従来方式との互換性などの問題もあり,徹底することはできなかった.参照番号をシステムが任意に決定できていたころはそれでもなんとかなったのだが,コラッツ特注版で「隣接リストのインポート」という機能を導入したことで,大幅な見直しが必要になってきた.通常はオブジェクトが生成された時点ですでに「参照番号」の割当てが決まっているが,隣接リストのデータは「参照番号」を持っていないので,すべての関係を「名前」の参照関係から割り出さなくてはならない.

この問題に対処するために,「ハッシュ」という技法が導入された.「ハッシュ関数」はテキストをある固定長の配列インデックスに変換する関数で,生成される「ハッシュ値」が適当に分散するようなものである必要がある.ハッシュはデータを「辞書的に管理する技法」として広く用いられている.「隣接リスト」は任意のラベル付きグラフを扱うことができるが,ノードに番号を割り当てるというのがもっとも一般的なので,「名前」を「整数」に変換し,その下位ビットを固定長の2進数として切り出すことでハッシュ値の代用としている.ハッシュ値がテーブルサイズより小さいものであれば,それをそのままレコード番号(配列インデックス)として採用することができる.

その位置がすでに使われている場合(ハッシュ衝突)には,テーブルを上方に検索して空き位置を見つけて,それをレコード番号とし,その値を「参照番号」として割り当てる.この方式では,「参照番号=レコード番号」という理想型をつねに実現することができる.ただし,その参照番号がテーブル上に存在しないことを確認するためには,全テーブルをスキャンする以外ない※.この意味では「最善」ではないかもしれないが,「最適」であるとは言えるのではないだろうか?細部を残して実装はほぼ完了しているが,デスクトップ上にある「CollatzTest.G.ADL」というサンプルの描画には疑問がある.

※もし,「参照番号=レコード番号」がつねに成立しているのであれば,全スキャンするまでもなく一発で判定できる.「全スキャン」が必要となるのは,「参照番号=レコード番号」がまだシステム的に確立していないか,ないし,過去データとの互換性の問題と考えられる.

このサンプルが「木」というよりは「ブッシュ」のようなものになってしまうのは,このファイルに含まれるカードの一部が表示しきれていないためではないかと考えられる.これを確認するために,テーブルサイズを0x2000から0x4000に拡大してみたところ,「LNK1248: イメージ サイズ(82390000) が最大許容サイズ (80000000) を超えています」のエラーになった.⇒カードテーブルサイズを12000, 結婚テーブルサイズを9000に設定して読み取りは可能になったが,まだテーブルオーバーフローが163件発生している.すべてカードデータで,結婚リンクはカバーできているが,CARDLINK::SortMarriagePageで「兄弟順位子ども数オーバー 」という「データ不整合エラー」が8件発生している.

そのまま続行して,MainExperiment→ FoldingChannelsでスタックオーバーフローが発生する.コラッツ特注版ではノード対オブジェクトは扱わないので,この関数をパスするように暫定修正して,今度はTreeView::MakeAbsolute→ ResetAbsoluteでスタックオーバーフローが起きた.ゼルコバの木ではすべてのオブジェクトはTREEVIEWをルートとする「木」を構成している.系図木の本体を構成するTRIBEBOX, NAMEBOX, MARGBOXなど通常の描画オブジェクトは高さで最大2168の範囲に収まっているが,その後ろに世代枠オブジェクトが直列に接続して長いチェーンになっていた.このチェーンの長さは6899を超えるもので,これがスタックオーバーフローの原因となっている.

世代枠オブジェクトは各世代ごとに配置され,その世代に属するオブジェクトが占める矩形領域を計算するために用いる.世代枠を世代順につないで管理するための世代枠リストには,①基本世代枠リストと②系列世代枠リストの二種があり,それぞれ,それらを管轄するTREEVIEWとTRIBEBOXに接続している.すべての描画オブジェクトは描画リストに接続することによって相対的な位置決めを行っているので,世代枠リストは座標計算には関わりがない.世代枠自体は計算結果を受け取るだけの完全に受動的な立場なので,計算自体はその世代枠がどこに接続されているかには影響しないため,世代枠がこのような変則的な状態にあることがまったく認識されていなかった.

いずれにしても,初歩的な欠陥と考えられるので仕立て直ししなくてはならない.不審なのは,このチェーンの先頭世代枠がNAMEBOXに接続しているように見えることだ.サンプルがちょっと大き過ぎて持て余すところだが,不良の要因は単純なので(極小反例サンプルを求めることなく)このまま続けることにしよう.先頭世代枠は系列先祖ノードの#424347 4549(0)に接続している.これは始系列の先祖ノードだ.とりあえず,これをTREEVIEWに繋ぎ変えてみよう.系列枠はTREEVIEWの右枝に接続しているはずだから,左枝は空いているはずだ.かなり初期のバージョンでは世代コンテキストという描画オブジェクトがあってその下に世代枠を接続するようになっていたが,現在は省かれている.

世代枠リストは系統並び替えのたびに再構築されているので,多分系統並び替えの冒頭でやっているはずだ.TRIBELIST::BuildGeneListでは,基本世代枠リストの先頭世代枠はTREEVIEWに接続されている.このオブジェクトは#804687で,問題の世代枠#805131とは異なる.おそらく,この世代枠は基本世代枠ではなくて,系列世代枠なのだろう.⇒現行方式には明らかに大きな欠陥がある.たとえば,

  • 系列枠がNAMEBOX(優先実ノード)に繋がっているため,描画リストが「木」というより,一本のチェーンのように数珠つなぎになっている
  • すべての世代枠が途切れのない一本のチェーンになっている

これまでは高々数百点のサンプルしか扱って来なかったため,これらの欠陥が表面化することはなかったが,一万点を超えるようなサンプルでは隠せない.描画リストは内部的にはYリストと呼ばれているが,その名の通り右枝と左枝の二方向に分岐した二元木を構成する.系図木を構成するために二元木というプリミティブな構成を選択した理由は,右枝をそのノードの内部構造(部分木)とし,左枝には同位ノードを接続するようにすると,二元木を使ってごく自然に多元木を表象することができるからである.最大枝数が固定した多元木よりフレキシブルに任意の木を構成できると考えられた.(とは言え,Yリストは隠蔽リスト呼ばれるもうひとつの分岐を持っているので,実際には三元木である

当初の系図木には世代枠という要素は含まれておらず,主に結婚枠と人名枠のみから構成され,頂点に特殊オブジェクトとして系図木(TREEVIEW)というオブジェクトがあるという単純な構成だった.系図木上で結婚枠と人名枠は,人名枠→ 結婚枠→ 人名枠→ のように交互に現れるから,系図木は2色で色分けすることのできる二部グラフと考えることもできる.画面上では人名枠は結婚枠内の要素となるから,図式的には系図木は結婚枠という要素のみからなる「結婚木」であると見ることもできる.先祖ノード(とその配偶者)だけは例外的に結婚枠の中に入っていないが,これはいま考えると敗因だったような気もする.⇒おそらく,この「コラッツ特注版」の挑戦が完結した時点でここに戻ることになると思う.「コラッツ特注版」は「単純な木」であり,「結婚木」も「単純な木」と考えられるから,「系統並び替え」を「もっとも単純なトポロジーソート」として再編成できるはずだ.

世代枠は基本的に計算結果を記録する場所でしかないので,描画リスト(という名前の木)から世代枠を完全に外してしまうということも考えられなくもない.ゼルコバの木ではすべての描画要素は描画リスト上にあり,また描画リスト上にある任意のオブジェクトは描画可能だが,「世代枠を描画する」こともあるというのが問題をややこしくしている.描画リスト上にあるノードを「無視する」ということは可能だろうか?もし,それが可能なら,現状で対処できるということにもなるのだが…⇒そういうことはありそうな気がする.やってみよう.⇒できた!

image

ただし,最後にメモリ不足が発生している(バックアップ中).⇒バックアップを止めても状況は変わらない.少し拡大してみよう.

image

このADLは生成時のテーブル上限までの行数を持っているが,実際にはそれを上回るデータを抱えている.コラッツ木生成ツールでは行数で管理できると思っていたようだが,そういう訳にはゆかないようだ.しかし,検証テストで生成される隣接リストに含まれるノード数を正確に数えるのはかなり難しい.検証テストでは,ルート1→奇数Nまでの経路に含まれる枝を拾い出しているので,大量の重複が発生し,それを整理してまとめたものを出力しているが,基準となっているのは最左列のノード番号だけで,それ以外の右側の列に含まれるノードに関してはどのような統計も取っていないためだ.それをやろうとすれば,ほとんどグラフを実際に生成するのと同等のコストが掛かってしまうので,実際的ではない.⇒このサンプルの出所だけは突き止めておこう.1~1000では1595点のグラフが生成される.1~3000では4720点サンプルだ.1~4000では…エラーが出た.

image

CollatzTree.G.ADLをインポート→アプリ終了でエラーが出た.CollatzTree.G.ADLで「絶対座標系で不正原点」というエラーが起きている.障害が起きているのは世代枠オブジェクトだ.

#19939 g GENEBOX 19939 Bobject::getorigin route=#19932 ▲【103 GENEBOX 19932】

これは仕方ないのではないだろうか?上記の1~4000の隣接リストを開発環境で開いて,エラーなしで描画できた.コラッツ木ツールから起動されるZTアプリはバージョンが古いためだろう.「世代枠は絶対座標系変換から除外@22020428」でエラーの出力を止めた.

1~4000では登録カード数11999点,結婚数8999点というファイルが生成されたが,テーブルオーバーフローが232件発生している.従って,本来なら12231点のカードが出力されたものと思われる.結婚テーブルのオーバーフローも大量に発生し,データ不整合が起きている.⇒カードテーブルサイズを13000,結婚テーブルサイズを10000にしてみよう.⇒起動時にEEFileLoadException 例外が発生する.おそらくメモリ不足と思われる.⇒カードテーブルサイズを12500,結婚テーブルサイズを10200に設定して完成図を出力できた.カード数12243,結婚数10170.⇒いや,ダメだ.崩れている.

image

ループカウントオーバーが発生しているのだろうか?⇒確かに「三極検定レッドラインオーバー」が起きている.少し延長してみよう.⇒ループカウント上限を100まで上げてみたが,抜けられない.まだ,どこかにバグが残っているのだろうか?⇒Collatz4000-12243.ZELとして保存した.⇒ZELファイルを取って,また,「極小反例サンプル」に仕掛けてみよう.⇒ダメだ.メモリ不足が起きてしまった.

image

この問題は64ビットに移行すれば解決するのかもしれないが,そればかりはちょっと今日明日の仕事ではない.スタックサイズはまだ削れる可能性があるのでそれをやるしかなさそうだ.

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA