経済循環系グラフと経済循環マトリックス

去年(2021)の5月頃から3ヶ月に渡って続いた「公共貨幣フォーラム」メーリングリストでの少数の主要メンバーとの対話ではグラフ理論を使った「貨幣循環論」を展開していたが,特にその中では「持続可能な経済循環系」を論じるのに「オイラー閉路」を用いていたのを思い出し,急遽ネットにアップロードしておくことにしたのはよいが,かなり手こずっている.わたしが発言した部分をまとめただけで124ページもあり,編集作業が思うに任せない状態になっている.現在,HTMLを編集するツールとしては,①LibreOffice,②Open Live Writer,③WordPressの3つがあるが,重過ぎて作業にならない.この中で一番軽いのはLibreOfficeだが,直接投稿できないというのが難点だ.

Open Live Writerでは一文字入力するだけでしばらく待たないと制御が戻ってこないという感じ,WordPressならなんとか応答してくれるが,「更新」ボタンが不能状態になってしまって,いざ保存することすらできなくなってしまう.⇒最終的にファイルを3つに分割することで何とか事態を収めた.ファイルを分割して3部構成とすることによって構成がわかり易くなり,論旨も明快になるという二次的な効果もあった.強調する語句を太字にしたり,引用と地の文を区別するために色分けするなどの下ごしらえは大体完了しているので,残っている主な仕事は「テーブル」の崩れを調整するだけになった.WordPressにはHTMLを編集するためのごく基本的な機能しか備わっていないので,Advanced Editor Toolsというプラグインをインストールした.これが入ると,フォントのサイズ変更やテーブルの編集ができるようになる.

何とか,パートⅠは片付いた!

エコロジカルに持続可能な経済循環系グラフ

一応パートⅠは仕上がったことにして,パートⅡに移ることにしよう.


二兎を追う者は一兎をも得ず

大分大きな穴が開いてしまったが,いつの間にか「世間」のGW最大10連休とかいう波に乗っていたのかもしれない.そう考えれば,もう少し遊んでいてもいいかな?とも思われるが,どうもこの流れで行くと,「もう少し」では済まなくなりそうな気配もある.こんなに離れているのであれば,きっちり整備してテストを仕掛けておけばよかったと思っても,もう遅い.この5日間テストを走らせていればどんなに遅くとも500点くらいまでは削減できていただろう.「極小反例サンプル」が手に入っていた可能性は高い.

いや,まだ遅くはない.これからもまだしばらく「開発」から逸れた状態が続く可能性は濃厚なので,それだけはやっておいた方がよいのではないか?現在仕掛りになっているのは,コラッツ予測問題のための検証ツールのプログラミングとそれに並行して実施しているゼルコバの木の整備だが,ここに来てにわかにもうひとつのミレニアム懸賞金問題が急浮上してきた.例の「数学・物理etc 談話室」で「ケーニヒスベルクの橋の問題」が話題となり,そこでまた大きな進展があったためだ.もう少し詰めないとものになるかどうかは分からないが,感触としては十分な手応えがある.「二兎を追う者は一兎をも得ず」と言われるが,「一石二鳥」ということわざもある.

https://www.facebook.com/groups/2354748741306929/posts/5048400828608360/

「ケーニヒスベルクの橋の問題」というのは,オイラー閉路と呼ばれる「一筆書き問題」だが,別のFBグループのメッセンジャーを使ってディスカッションでオイラー閉路を使って貨幣論を展開したことがあり,どこかにそれをまとめておこうと思いながらそのままになっていたので,まず,それをやっておくことにしよう.一ヶ月分くらいのメールを1本にまとめるだけだから,大した時間は掛からないだろう.⇒対話は主に公共貨幣フォーラムメンバーの下田氏,生島氏とわたしの間で行われたが,期間は2021/05/09~2021/08/01の3ヶ月で,わたしから発信したメールだけでも121ページ分もあり,対話者の分まで含めれば一冊の本になってしまうほどのボリュームがある.

整理手順としては,まず,ともかくメールボックスに入っているメール本文をコピーして,1本の新規メールに集め,それをHTMLで保存してLibreOfficeで編集できるようにしてみた.LibreOfficeからはPDFに保存できるので,それをアップロードするということも可能だが,OwnCloudはあまり使い勝手がよくないので,できればWordPressからの投稿という形にしたい.前に「数学・物理etc談話室」のスレッドまとめをテント村に投稿したときにも似たようなことをやっているが,このときは多分スレッドのコメントを1点づつOpen Live Writerにコピーしていたのではなかったろうか?

WordPressにログインし,編集画面で直接HTMLファイルの内容をコピーすると,一応WordPressで編集できるような状態にはなる.ただし,書式とテーブルは読み込まれるが,画像はリンク切れの状態になってしまう.従ってこの方式で行くとすればすべての画像を手操作で貼り込まなくてはならない.しかし,Open Live Writerでこのサイズのファイルを編集するのはかなりストレスがある.スクロールのたびにフリーズして,改行一つ受け付けるのにしばらく待たなくてはならない.⇒WordPressの編集画面ならそれほどストレスにはならない.画像はLibreでHTML出力したときに同時にファイルとして保存されているので,それを「メディアに追加」で読み込んでページに挿入するだけだ.一度この作業をやってしまえば,Open Live Writerでダウンロードしてローカルで編集することもできる.

画像ファイルの本数は6でそれほど多いものではなかった.編集と閲覧を一つのブラウザで実行できるので,ログインして編集というのもそれほど悪いものではない.と思ったが,なぜか「更新ボタン」が消えてしまう.というかグレー表示になって更新できない状態になってしまう.ネットで見るとこれは「クラシック」エディタに特有の現象で,「ブロック」エディタでは起こらないということのようなので,この際,ブロックエディタに移行することにした.「更新できない場合の対処法」というのもネット上にいろいろあったが,かなり面倒だ.

しかし,ブロックエディタはやけくそ遅いような気がする.一文字入力するごとに,しばらく待たないと次の文字が入力できない…⇒やはり,これまで通り,クラッシックエディタを使うことにする.「更新ボタン」がグレーのときも,二度押しすると反応するようになった.⇒いや,ダメだ.Open Live Writerの動作はもっと悪い.カーソルを置くこともスクロールすることもできない.⇒このテキストもOLWで書いているが,問題なく動作している.おそらく,OLWの動作不良はテキストサイズが大き過ぎるためと思われる.どうにも手の打ちようがなくなってきた.前に作ったコラッツのスレッドまとめも結構大きかったような気はするのだが,こんなことはなかった…

一番確実なのはLibreだが,ここから直接投稿することはできない.完全に仕上げてから投稿するのならそれでもよいが,投稿した現物を見ながら編集するというのがわたしの流儀だ.2つくらいに分割して編集するということは考えられる.それができれば,最後にマージすればよい.

あきらめてここで打ち切るか,何か対策を考えるか?それが問題だ

なんとかメモリ不足の問題を解決して,CollatzTest 4000.ADLの極小反例サンプル抽出を行っているところだが,一晩走らせても,まだ80点しか削減されていない.全体で12243点もあるので,これでは焼け石に水だ.現行では,子どものいないノードだけを対象に削除テストを実行しているので,一度に1点しか削減できない.この「一度」というのに途方もない時間が掛かっている.あきらめてここで打ち切るか,何か対策を考えるか?それが問題だ.

▲単身婚ではCheckAtypicalMarriageでやることは何もないのではないか?また,結婚枠の順序が変わらない限り,Gringのリロードは不要なのではないか?⇒CheckAtypicalMarriageを実行しないと,NAMEBOX::DrawFooterLineでエラーで停止する.この関数では脚下垂線を描画しているが,下部垂線の長さを決めるパラメータが計算されていない.Gringのロードは一度だけ実行すればよいはずだが,GringChangedの中で実行しているcancelstackは必須のようだ.この辺りは後日見直すことにする.

▲12146点の「極小反例サンプル.ZEL」をデバッグモードでロード→ 「極小反例サンプル」を実行スタックオーバーフローが起きた.ResetAbsoluteで起きている.

image

この障害は前にも発生している(2022-04-28).原因は描画リストで世代枠が長いチェーンになっていること,系列世代枠が描画リストを長いものにしているという2点だ.ここでは,始系列を系図木オブエクトの左枝に接続するという修正を行っている(いたはずだ).⇒いや,暫定的にResetAbsoluteで世代枠を無視するということしかやっていない.⇒ダメだ.再実行しようとして,また,「アプリケーションはブレークモードになっています」が起きてしまった.EEFileLoadException (メモリの場所 0x00AF8DBC)というのが発生している.この障害はメモリ不足に関係しているように思われるが,よく分からない.起動して,まだ何も実行していない時点で起きているので,手も足も出ない.

image

2日前の版に戻って見たが,動作は変わらない.訳が分からないので,とりあえず,VS2017を修復インストールしてみる.⇒状況は同じだ.直近の3つの版を試してみたが,「ブレークモード」だ.2022-04-12まで戻ってようやく動いた.2022-04-30版では以下のメッセージが出た.

image

メモリリソースが足りないとなっている.この版ではコマンドラインでCollatz3950-10934.ADLを起動している.しかし,コマンドライン引数なしで起動しても,「ブレークモード」で停止する.4月29日に同じような事象があり,このときも「メモリリソースが足りません」となっていた,リリースモードでは立ち上がる→ テーブルサイズを縮小→ より小さいサンプルを作成,のように対処している.1月9日にも同種の事象があり,「ターゲットをAnyCPUからWin32に切り替えて動作するようになった」と記録している.この時期にはWindows 10とWindows 7の2つの環境を併用している.⇒確かに,これが当たりのようだ.

ここで「ターゲット」と言っているのは,ツールバーの「ソリューションプラットフォーム」と呼ばれる項目だ.VBのプロパティ→ コンパイル→ ターゲットCPUは「x86」,DLLのプロパティ→ ターゲットプロパティは「Windows 10」に固定されている.OCX,GCも同様だ.構成マネージャではVBのプラットフォームは「Any CPU」に固定で,それ以外は「Win32」に固定されている.

とんだ時間の無駄遣いをしてしまった.⇒仕掛りの最新版に戻って起動することはできたが,SetRowValue←BuildNewTableでoutOfMemoryExceptionが出てしまった.このサンプルは今まで動いていたはずなのだが…カスペルスキーの完全スキャンを実行していることが影響しているだろうか?カードテーブル情報をテキスト配列にコピーするようにしているので,確かに以前よりはメモリを余分に使うようにはなっていると思うが…⇒極小反例サンプルで参照しているのはカードの参照番号だけなので,その部分だけ格納するようにすれば大幅に削減できる.あるいは,このテキスト配列を作らないで,極小反例サンプルでGCから直接レコードを取り出すようにしてもよいのではないか?⇒とりあえず,前者の方法を試してみよう.

そもそも,バージョンが戻ってしまっている.というか,最終版がバックアップされていない.最終バックアップは2022-05-01-2で,これには2022/05/01のログの修正のすべては反映されていない.「BUNSFILEのバッファは常設とする@20220430」は入っているが,UNDOの修正は入っていないように思われる.ここからやり直すしかない.一度仮眠してデバッグを再開するときには,必ずバックアップを取るようにしないと失敗する…

OutOfMemoryExceptionにどう対処したらよいか?

デバッグモードでCollatz3950-10934.ADLを開いて保存しようとして,KAKEIZU::saveFamilyBaseでERR_NOMEMORYメモリ不足エラーが発生する.ヒープサイズは4294967296をリザーブしている.これでも足りないのだろうか?⇒メモリ不足はファイル書き込み用バッファのメモリ要求で発生している.要求サイズは45,904,944,このときまでに使用しているメモリ総量は106,632,555で,トータル152,537,499.これはヒープサイズの4,294,967,296より,ずっと小さい.おそらくメモリが断片化して連続した領域を確保できないためだろう.

まとめて書き込むのではなく,一行づつ書き込むことにすれば,それほど大きなバッファは必要ないのではないだろうか?⇒現行では,系図木処理から直接ファイルに書き込むのではなく,QUICKDBという簡易データベースシステムを経由して入出力するようになっている.QUICKDBではカードデータベース,結婚データベース,記録データベースを管理して,保存時にはそれらを一括して書き出している.バッファは一度確保されると,サイズオーバーにならない限りそれを使い続けるので,それほど効率の悪いことをやっている訳でもない.QUICKDBは外部ストレージとの入出力用にBUNSFILEというクラスを使っている.

KAKEIZUは人名データベースと結婚データベースという2つのQUICKDBを持っている.QUICKDBはBUNSFILEをメンバーとして持ち,BUNSFILEの中にバッファを確保している.また,これとは別にCOUPLINGにはCHUNKFILEというメンバーを持っている.CHUNKFILEは独立に記録データの入出力用としてFILEBUFFというバッファを持っている.CHUNKFILEはMFCクラスのCArchiveと連携している.⇒BUNSFILEのバッファを常設とし,起動時に一度生成してそのまま使うことにすれば少しは改善されるのではないか?⇒やってみよう.⇒対処した.最初に確保してしまえば,その後はメモリ操作不要になる.

新規ファイルを開いた状態からCollatz3950-10934.ADLをインポートでOutOfMemoryExceptionが発生する.このエラーはVBで発生している.何か対策はあるだろうか?BuildNewTableではDataGridView.Rows.Clearでコレクションを空にしている.これを削除ではなく,更新にすることは可能だろうか?⇒UpdateTableという関数もある.UpdateTableではレコードの更新を行う.行数が足りないときには追加することができるので,これでもカバーできるのではないか?⇒いや,効果ないだろう.新規ファイルから初めているので,一覧表は元々空の状態だ.つまり,絶対的に不足しているというしかない.

不要な列は表示しないというのは効果があるだろうか?ダメのようだ.しかし,テーブルを最初からそのようなものとして構築してやればかなり効果はあるのではないか?MAXITEMを変えればそのような状況になるが,至るところで「インデックスが配列の境界外です」になるのは避けられない.テーブルを操作するほとんどすべての関数で起きるだろう.エラーが200箇所以上発生する.⇒MAXITEMを調整してテーブルを縮小するというのはかなり難しい.そもそもADLのインポートはテーブルを媒介としているので,無理がある.

検証テストのテストカウントを3900としてもう少し小さなサンプルを作った.カード数は6165,結婚数4684になった.これなら楽にロードできそうだ.⇒ロードしたADLを名前を付けて保存で,BUNSFILEのバッファが空になっている.CloseFamilyBase→COUPLING::Cleanで空になっている.⇒Cleanの代わりにdoCleanを使うことで解消した.doCleanは自己の固有データ部のクリーンのみを実行する.CleanではdoCleanを実行し,かつ下位スロットをCleanしている.多少疑問の残るところだが,一応これでよいことにしておく.しかし,このサンプルは反例になっていない.ループカウント30で脱出してしまう.

Collatz3950-10934.ZELを開いた後,Collatz3950-10934.ZELを読み込もうとしてQUICKDB::lodquickで例外が発生した.アクセスヴァイオレーションが発生している.BUNSFILEのバッファは保持されている.⇒どうもこのファイルはこわれているようだ.ファイル冒頭のマジックナンバーを読み込むことができない.ファイルサイズも48KBしかない.本来なら3MBくらいはあるはずだ.多分ファイル保存操作中エラーが発生して中断になっているのだろう.

Collatz3950-10934.ZELを開いた後,Collatz4000.ADLをインポートしてTITLELINK::SetTitleInformationで(len != TitleInfo.Rtfsize)というエラーが出た.⇒その後,SetRowValue→BuildNewTable:rowindex=5003でOutOfMemoryExceptionになった.このサンプルはカード数12243, 結婚数10170で,カードテーブルサイズ=12300,結婚テーブルサイズ=10300という設定で走っている.⇒名前を付けて保存はできた.⇒メモリ不足が関係している可能性はある.

目下の懸案となっているのは以下の2点だ.①UNDOでShadowが空というエラーが起きている,②Collatz4000-12243.ZELでループカウントオーバーが起きる.上記のCollatz4000.ADLというサンプルは②の反例に該当する.これを極小反例サンプルの抽出に掛けたいところだが,メモリ不足になるというのが最大の問題だ.DLLで発生するメモリ不足に関しては何らかの抜本策も考えられるが,VBで起きているメモリ不足に関してはほとんど対策がないか限られている.一覧表をまったく生成しないことにすればかなり効果があるのではないかと思われるのだが,隣接リストのインポートではカードテーブルをデータの受け渡しに使っているので,それもかなり難しい.

ファイルから読み込んだ1行データをテーブルのレコードに変換しないで,テキストのまま保持するということはできるのではないか?もし,それが可能ならかなりメモリ使用量を削減できるような気がするのだが… ImportFileでは実際それをやっている.インポート自体はテーブルを使わずに実行できることは立証されているので,一覧表にレコードを追加しないで空のまま放置というのでよいのではないか?⇒なんとかこれで動くようになった.

REDLINEは50という設定でも1点検査するのに相当な時間が掛かり,空振りばかり続くのでもう少しヒット率を上げるために,子どものいないノードをピックアップしてテストすることにした.多分これなら時間とともに削減が進むだろう.⇒リリースモードに切り替えたら,大分速くなった.⇒速いはずだ.対象サンプルが違う.⇒そもそも,まだ動いていない.⇒ようやく動くようになったが,やはり,UNDOでエラーが発生している.これはおそらく,UNDOに関わる修正がまだ収束していないことを示すものと考えられるので,UNDO操作に集中してもう少し小さいサンプルで動作確認を行うことにする.

最小反例321ZELを開き,任意のカードを削除してUNDOBASE::SetUndoListで (!copynode->shadow)エラーが発生する.copynodeはUNDOの上書き対象ノードなので,すでにshadow付きになっているはず…⇒いや,copynode不在で新規に生成されたケースだ.できたてなのだから,shadowが入っていないのは当然なのではないか?少し古い版のコードを見る必要がある.⇒2022-02-26で見ると,/* 生成したばかりでshadowを持つはずがない@20170823 */というコメントが入っている.この位置にはshadowを設定するコードが入っているが,現行版では「1行削除@20220423」となっている.なぜだろう?かなり考え難い.※⇒編集ミスではないだろうか?

2022/04/23の修正は,「UNDOのShadowをfreeblock化」だ.shadowはフリーメモリなのだから,どこかでメモリを確保していなくてはならないはずだが,やっていないように見える.従来論理ではfreeblock::getmemでメモリを取得しているが,freeblockとして扱うためには,_getmem_を使う必要がある.このとき,MMTYPEを指定するようになっていて,MM_SHADOWという定数が新規に追加されている.⇒定義されているだけで,まったく使われていない.⇒修正した.(この修正は入れた記憶はあるが,誤って消してしまったのだろう)

一応,カード削除でUndo/Redoができるようになったが,カード数の表示が正しくない.Undoしても数字が元に戻らない.この数字はUpdateMaxCardで更新しているのだが…UpdateMaxCardの呼び出しが掛かって来ない.⇒「極小反例サンプル」対応でコストの掛かる処理を止めているためだ.①GetNewTable,②GetNewCard,③CenteringCardSubをパスしているが,おそらく,GetNewCardでUpdateMaxCardを実行していたものと思われる.⇒「極小反例サンプル検定の時間効率改善20220501」で対処した.

複数カードを選択して,逐次削除→全削除を実行→Undoして,UNDOSYSTEM::UndoProcessで(UndoCurptr->UndoNumber != UndoNumber)により停止した.2点選択して逐次削除→Undo→Undoで再現する.UndoCurptrのUndoNumberは1,UndoNumberは2になっている.明らかに大域変数のUndoNumberの方が誤っている.UndoしたときにはUndoNumberはデクリメントされなくてはならないはずだ.UndoNumberはUNDOBASEとUNDOSYSTEMで重複して調整されている.しかも,反対方向に調整している.どちらか一方は不用と思われる.UndoCurptrはnoduleクラスでも定義されている.UNDOCOMMANDはそれ自体noduleなので,混乱が生じている.noduleの側はUndoNumberとし,UNDOCOMMANDでは大文字のUndoNumberを使うようにしてみよう.⇒収まったようだ.

UNDOBASE::SetUndoList で(!copynode->shadow)により停止した

▲CollatzTest.G.ADLをインポートして,「極小反例サンプルの抽出」を実行中,UNDOBASE::SetUndoList で(!copynode->shadow)により停止した.最初のカード削除のUNDOSYSTEM::UndoStartで起きている.⇒「極小反例サンプル」のベースはUNDOなので,これができないと始まらない.UNDOに修正を入れた後,「極小反例サンプル」のテストを実行していなかったのではないか?もう少し小さいサンプルで確認してみよう.⇒いや,すでに小さいサンプルは解けるようになってしまっている.最新のサンプルはCollatz3950-10934.ADLだ.それより大きいサンプルは特にデバッグモードでは開けない.

デバッグモードでこのサンプルを開くことはできるが,極小反例サンプルを実行しようとするとSystem.OutofMemoryExceptionが発生する.⇒BuildNewTableで.Rows.Clearの後に,System.GC.Collectを実行して,OutofMemoryExceptionは解消した模様だ.現象を再現するまでの時間が掛かり過ぎるので,MAXREDLINEを暫定的に5に設定した.それにしても遅い… LINKTABLE::cardlink(refnum)ではrefnumとrecnを同一視するように論理修正した.marglink(refnum)も同じ.また,BASETABLE::delrecnとmaxrefnumを廃止した.AppendFileは修正が大きいので,暫定的にまるごと止めてある.

OSを再起動→デバッグを再開しようとして,「アプリケーションはブレークモードになっています」がまた出てしまった.「ハンドルされていない例外」として,「内部例外:FileLoadException: ファイルまたはアセンブリ ‘ZelkovaGC3.dll’、またはその依存関係の 1 つが読み込めませんでした。このコマンドを処理するにはメモリ リソースが足りません。 (HRESULT からの例外:0x80070008)」のように表示されている.

image

再起動前は問題なく動作していたのだが… カスペルスキーが走っていることが関係あるだろうか?⇒リリースモードなら立ち上がる.⇒しかし,極小反例サンプルではOutOfMemoryExceptionになってしまう.現在の設定はカードテーブル12200,結婚テーブル10200で,この設定ならリリースモードはもとより,デバッグモードでも障害地点まで走ることができたのだが… もっと小さいサンプルを作るしか,打つ手がない…


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

コントロールキー+マウスホイールでズーム

一段落付いたところで,修正をフィックスしておこう.⇒まず,UNDOに関する修正をフィックスしてしまおう.まだ,全面的な動作確認を行ってはいないが,今回の修正を不可逆的なものとして確定する.

  1. 「UndoNumberを設置する@20220418」7箇所
  2. 「UNDOのShadowをfreeblock化@20220423」2箇所
  3. 「UndoEndでコマンドを追加しない@20220424」→廃止
  4. 「ShadowチェーンからUNDOノードを検出する@20220423」1箇所
  5. 「UNDOTYPEを新設する@20220424」4箇所
  6. 「CommandStartで現コマンドを全クリア@20220425」3箇所
  7. 「CheckMaximalCompaction呼び出しを抑制@20220426」1箇所
  8. 「仮修正」27箇所

まだ,あれこれ対処する必要がある箇所はあると思われるが,一応完了したことにして,また,コラッツ木生成ツールに戻ることにしよう.どこいら辺から脇道に逸れて来たのか?ログで確認しておこう.⇒2022/04/12に「検証テストカウント3200のADLサンプルでハングする」という記事がある.おそらくこの辺りだろう.「TC3000という呪われたサンプル」は2022/04/15だ.

コラッツ木生成ツールの方は,A面とB面の3機能(コラッツ数列,アドレス変換,幹線木)の動作チェックが終わって,検証テストに入ったところだ.A面とB面3機能に関しては,一般木と仮想木の両サイドをチェックしているが,検証テストはまだ一般木のテスト中だ.今回修正で一般木のテストはパスできたと思われるので,仮想木の動作チェックに移行するところだが,コラッツ木生成ツールに移る前に懸案をいくつか片付けておきたい.

  1. コラッツ特注版のための例外措置としての「中吊りを強制」をオプションとして切り替え可能にする
  2. 系図画面のモードで「縦書き」と「横書き」をオプションとして切り替えできるようにする
  3. MAXIMALGRAPH::MergeUpperSegmentで結婚点一致の条件を緩和しているが,許容値上限の是非を確認する
  4. スケールの大きいファイルを開いたとき,メモリ不足のため「生描画に切り替えます」という動作になっているが,ズーム倍率を調整して回避できるのではないか?
  5. コントロールキー+ホイールでズームできるようにする また,ズームボタンを押したときのタイマーの初期値をもっと小さくする

項目5から片付けよう.現行でも,ホイール操作によるスクロールはサポートされているし,ズーム動作はズームイン,ズームアウトボタンとして実装されている.問題は,ホイール操作はOCXの受けるイベント,ボタン操作はVBのイベントになっているという点だ.いや,ホイールイベント自体はVBで取っているようだ.FramePositionというメソッドで受渡ししている.⇒いや,その前にCtrl+リールというのはすでに「水平スクロール」として使われている.「Ctrl+ホイール」でズームというのはかなり一般化しているので,仕様変更した方がよい.ホイールスクロールは,ALTキーで受けることにしよう.⇒実装した.ZOOMINTERVALを200(ms),ZOOMRATEを0.95に設定した.

項目4は現状とする.

▲ADLファイルをダブルクリックで起動できるが,データ数が上限を超えていますのエラーが反復表示される.サンプルはCollatzTest.G.ADL.しかし,ファイルメニュー→隣接リストのインポートでは問題なく読み込める.実際データは4720点しか入っていない.⇒おかしい.隣接リストのインポートとコマンドライン起動で異なる動作になっている.どちらもまったく同じコードを実行しているように見えるのだが…

Dim NewFileName As String = MakeAdjacencyList(.FileName)
OpenFileProc(NewFileName, OPENMOD.FULLIMPORT)

BASETABLE::emptyrecnでは,maxrecn < tablesizeで上限オーバーを検査している.maxrecn=tablesizeという状態になっているため,上限オーバーと判定されている.このmaxrecnという数は「有効なレコード数」となっているが,ややあいまいなところがある.おそらく,有効なデータの最大レコード番号という意味で使われているのではないかという気がする.maxrecnのアクセス関数として_maxrecnが使われている.レコード番号とデータカウントの混乱を避けるために,maxrecnではなく,dataCountという変数を用いることにする.アクセス関数はDataCountとしておこう.

どうもこの修正は野火のように際限なく拡がりそうな気配だ.ある時期に,効率的な観点から「参照番号とレコード番号を一致させる」ということを試みた時期があり,その残滓が残っていると見られる.つまり,参照番号をインデックスとしてテーブルに直接アクセスできるという設計で,このためには参照番号はテーブルサイズより必ず小さくなくてはならない.これはUNDOでカードを元の位置に戻さなくてはならないという辺りからの発想ではないかと思われるが,本来的にはその必要はなかったのではないだろうか?つまり,UNDOはカードのリンクがテーブル上のどこに配置されていたとしても,動作可能であるはずだ.

コラッツ特注版では原則として参照番号と名前は一致することを建前としているが,実際にはハッシュ衝突が多発するため,番号と位置が一致しない場合が発生し得る.一度修正を戻して,バックアップを取ってから始めた方が賢明かもしれない.リリース版のバックアップはあるが,リール・ズームを導入しているので,そこまで戻してから出直すことにする.実際のデータがどうなっているのかは分からないが,参照番号<テーブルサイズというのは悪い設計ではないと思われる.参照番号の位置にそのカードが存在しない場合は,つねに前方を検索するという探索法はそれほど効率の悪いものではないと考えられる.ただし,テーブルの上端に達した場合には下端に戻って検索を続ける必要がある.

現行論理はほぼそれに沿ったものになっているはずだが,ハッシュで衝突が起きた場合でかつテーブル上限を超えた場合の始末が入っていない.この修正をまず入れておく必要がある.⇒LINKTABLE::GetRefnumに修正をいれたところ,この関数内ですでにオーバーフローが発生している.確かに,ADL.CSVファイルを見ると8192点のレコードが入っている.MAXPDB=0x2000=8192だから上限に達している.テーブルは1発進なので(MAXPDB-1)個までしか収納できない.ハッシュ関数には0x1FFFを使っているので,生成される参照番号は8191までだ.⇒tablesizeは内部変数なので,実際のテーブルサイズより1小さく設定しておくことにしよう.

テーブルオーバーフローを無視して処理を進めることで系統並び替えまでは進んだが,絶対座標変換で例外が発生してしまった.Bobject::ResetAbsoluteでスタックオーバーフローが発生している.なぜだろう?NAMEBOX::DrawNameText→ PrintParameter→ getGenerationでエラーが出るようになった.getGenerationでは絶対座標系から呼び出されることを禁止している.しかし,これまでは何の問題もなく動作していたのだが… 暫定的にPRINTPARAMETERを止めてみよう.→描画できた.親子関係がぶつぶつに途切れているため,「木」というよりは「ヤブ」と言うより,ほとんど「草原」に近いものになっている.「横幅に合わせてズーム」しても,19%以上には拡大できない.「メモリ描画環境を使わない」ときは,ズーム倍率の制限は不用なのではなかったろうか?

いずれにせよ,ほとんど「手が付けられない」レベルに悪い.ファイル上のデータは8192点なので,テーブルオーバーフローになるのは高々1件に留まるはずなのに,ぼろぼろオーバーフローが発生している.いや,実際に登録に失敗しているカード数はそれほど多くはない.7331964,7326588の2点だけのように思われる.コマンドライン起動ではなく,隣接リストのインポートでも結果は同じだ.上記で「ファイルメニュー→隣接リストのインポートでは問題なく読み込める」としているのは,おそらくサンプルを取り違えたのだと思う.

テスト中のサンプルはCollatzTest.G.ADLだが,似た名前のCollatzTree.G.ADLというのがデスクトップにある.リリース版の動作をチェックしてみたが同じ結果になった.このサンプルが「ブッシュ」のようになってしまうのは,オリジナルのADLがそのようなファイルになっているためだろう.つまり,このサンプルは上限を遥かに超えたサンプルを生成して,大量の足切りが発生していたのだと思う.従って,現行の仕掛り版は基本的なところでは正しく動作していると言ってよいと思う.

極小反例を探す長いジャーニーが終わった

UNDOには大分てこずったが,なんとか落ち着いたようだ.極小反例サンプルは307点まで縮小することができたが,サンプル生成中にスタックオーバーフローが発生する.スタックオーバーフローが発生する時点はまだ特定できていないが,極小反例307.ZELから開始すると,単点削除検査を24回繰り返したところで発生することは確実なので,シューティングは時間の問題と思われる.障害はUNDOBASE::CommandEnd sc=478の後に発生しているので,まず,ここで停止してみよう.⇒i=20から開始してもスタックオーバーフローが起きる.多分,i=24から一発で再現できると思うのでやってみる.⇒再現する.

障害はカード@233をFAMILYTREE::DeleteCardDataで削除→ UNDOBASE::CommandEndの出口→ TopologicalSortを実行で起きている.TRIBEBOX::StackTribeGene→ TRIBEBOX::CompleteTribeBox→ HorizontalSegmentで起きる.⇒TightenUpLooseで起きているようだ.⇒MAXIMALGRAPH::tightenUpLoose→ TightenLowerBoxのようだ.⇒どうも,かなり筋の悪い障害だ.障害の発生する時点が刻々と変化してしまう.エラートラップにも落ちないようになって,最後はスタックオーバーフローも発生せず,Access violationで終了になってしまった.⇒NAMEBOX::TightenLowerBoxでGP例外が発生している.

どうも,このTightenLowerBoxで循環が発生しているように思われる.⇒以下のような三つ巴の再入呼び出しが実行されている.

MAXIMALGRAPH::IsMargBoxFixed→ MAXIMALGRAPH::IsNameBoxFixed→ NAMEBOX::TightenLowerBox→ MAXIMALGRAPH::IsMargBoxFixed

また,IsNameBoxFixedは自分自身を再帰的に呼び出しているが,この呼出では深いネストは発生していないように思われる.⇒いや,入っている.むしろこれが原因かもしれない.基本的にこれらの呼び出しは垂直に下降する方向に進むようなフローになっているはずなので,循環するというのはかなり奇妙だ.再入経路にはいろいろなパターンがある.

TightenLowerBox→ IsMargBoxFixed→ TightenLooseBox→ TightenUpLoose→ CheckMaximalCompaction→ MaximalCompaction→ TightenUpLoose→ TightenLowerBox→

これは,かなり無茶な仕掛けと言ってよいのではないだろうか?⇒MAXIMALGRAPH::TightenUpLooseの中からTRIBEBOX::CheckMaximalCompactionを呼び出すという動作を抑制するようにした.⇒これで問題は解けてしまった.すでに問題は解決しているので,この件に関してはもはや「極小反例サンプル」というものも存在しない.⇒試しに,CollatzTest 3000-4619.ZELを開いてみよう.これはコラッツ検証テストが出力した4619点サンプルだ.⇒問題なく開けた(と言ってもループカウント43でギリギリだが).計算完了までに2分近く掛かっている.

image

長いジャーニーになったが,収穫は大きい.UNDOを見直す機会が得られたこと,また古い年老いた蛇をついに捕らえることができたことなど…この不良はバグというよりは,設計ミスと呼ぶべきだろう.今回確立された「極小反例サンプル抽出の自動化」という技法は応用が効くので,今後のシューティングの決め手になるだろう.実際,今回は「極小反例サンプル」に到達する以前の段階で,不良をあぶり出すことができた.数千点というような大規模なサンプルで起きている障害をこれまでのような方法で追いかけていてもおそらく埒が明かなかったのではないかと思う.4600点から300点くらいまで縮小できれば自ずと見えてくるものがある.⇒リリース版を起こしておこう.「Version 2.2.2.008 Release 2022-04-26」とした.

インストールしようとしたら,また,何か分からないことを言い始めた.確かにどこかで見た記憶はあるが,通常は発生しない…

image

アンインストールしようとしても,同じメッセージが出てくる.⇒2.2.2.003.msiの場所を探してアンインストールした.コラッツ木生成ツール→VerifyでTest count:5000を指定して,Open Zelkova Treeで開くことができた.生成されたサンプルは7925点で,現在設定されている最大カード数=8192=0x2000のほぼ上限に近い.とりあえず,このくらいまでできればよいのではないかと思う.

UNDOに関していくつか重要な修正を行った

UNDOに関していくつか重要な修正を行った.①UndoNumberを設置する,②ShadowチェーンからUNDOノードを検出する,③UNDOのShadowをfreeblock化など.①はUNDOノードの重複を避けるために,コマンド発行ごとにインクリメントされる値で,保全対象のオブジェクトにはこの値が格納され,すでに格納済であるか否かを判断する材料とする.②は従来方式ではコマンドに連結されたUNDOノードリングをスキャンしていたのを,オブジェクトのShadowチェーンを直接操作する方式に変更した.この方がスキャンの範囲を狭めることができる.③は②を実現するために必要となった措置で,これまではヒープから直接切り出していたバックアップイメージ領域をfreeblockのオブジェクトとして管理できるようにするものである.

昨日のログではこれらの修正後,ある程度改善されたとしているが,実質的にはまったく変化していない.つまり,依然としてUNDOノードの増殖は続いている.これに対処するために,UNDOノードリング上に同じタイプで完全に同内容のイメージが存在するためには,リングに追加しないようにしたところ,一昨日の障害が再発してしまった.

▲UNDOBASE::UndoProcess→ TOPOLOGY::RebuildCardList→ NAMESORT::NameSort→ NAMESORT::SortNameSub→ compnode のコールバックでcard2の参照番号が0になっている.⇒この障害は,2022-04-23に初発したもので,「オブジェクトのコピーにUndoNumberを格納していたことが誤動作の原因」として廃止しているが,その後の修正で,オブジェクトのコピーの前にUndoNumberを設定しているので,シャドーにもそれがコピーされている.

前回はこの障害をカードテーブル上のカードの参照番号がゼロとなるタイミングをSWOで追いかけて突き止めているので,試してみよう.⇒UNDOSYSTEM::RestoreShadowで完全に白紙のシャドーがリストアされている.このUNDOのノードのSSNは#614867.どこでこのノードが生成されたかを見る必要がある.このノードはCARDLINK#2246のバックアップだ.CARDLINK#2246はカード番号@479の「479」というカードで,カード削除の対象カードだ.

UNDOチェーンには#2246のバックアップは「削除」コマンド分しか残っていない.BackupPointDataでは保全されているので,上書きされてしまったのではないだろうか?⇒UNDOBASE::SetUndoListの修正にミスがあった.ただしこれを訂正後,COUPLING::TopologicalSort→ TOPOLOGY::SortAncestorTableで「先祖ノード数がゼロ」という別の障害が出てきた.カードテーブルには分散しているが,カードは入っている.maxrecn=361でtablesizeは8192,基準ノードは@23だ.

senzosu=1となっているが,Senzolist配列には何も入っていない.TOPOLOGY::SortAncestorTableで先祖リストを生成している.⇒カードテーブルにアクセスできていない.getmaxrecnが返す値がカードテーブルの範囲をカバーしていない.⇒BASETABLE::getmaxrenはmin(maxrefnum, tablesize)を返しているが,テーブルはmaxrefnumよりも拡がっている.⇒暫定的にtablesizeを返すようにした.むしろ最大レコード番号を返せるようにした方がよいのだが… ⇒これで収まるかと思われたが,まだ(max < 1)が起きる.

▲極小反例 361.zelでカード@479を単点削除した後のUndo出口→ 系統並び替え→ TribeDecomposition→ SortAncestorTableで(max < 1) で停止する.基準ノードは@479.これは,UNDOがよく機能していないことを示すものではないか?対象ノードの親がQに入っていないため離脱している.Qへの登録はTOPOLOGY::InitializeDecompositionとTOPOLOGY::GetkinshipDegreeで実行されている.InitializeDecompositionはTOPOLOGY::TribeDecompositionで実行される.TOPOLOGY::TribeDecompositionはTOPOLOGY::FilteringKinshipから呼び出される.FilteringKinshipはTribeDecompositionに先行する.

@479の親は#1841@35で,InitializeDecompositionではQに登録されている.⇒@ 35はQに入っている.先祖ノードであることも確認されている.問題は優先ノードが一致しないという点だ.これは,InitializeDecompositionではやっていない.⇒少し混乱している.Undo後の系統並び替えの基準ノードは@23で,先祖ノードは@35だ.@479を削除した後,Undoしているのだから,元の原木に戻っているはずだ.それが,実際は@479を削除して4系列に分解したままの状態になっているということだろう.おそらく,@479の事前バックアップデータが上書きされてしまっているのだろう.つまり,事後データは別途保存されなくてはならないというところが崩れているのだろう.⇒UNDONODEクラスにUNDOTYPE undotypeを新設し,createを廃止して,SetUndoListの引数のcopymodeと統合してundotypeに吸収した.UNDOTYPE は「SetUndoListのノード生成時の動作種別」で,以下のように類別される.

  1. UNDO_DEL = -2, オブジェクトの削除コマンド
  2. UNDO_NEW,         オブジェクトの新規生成コマンド
  3. UNDO_NORMAL,   オブジェクトが保全されている場合は上書きしない
  4. UNDO_COPY,        オブジェクトが保全されている場合は上書きする
  5. UNDO_MAKE,        つねにUNDOノードを新規生成する

この修正によって動作はかなり改善されたが,まだ時間経過とともにUNDOノードが増殖するという傾向は残っている.以前は等比級数的に増加していたところが,等差級数的に近くなっている.現行論理では,一つのオブジェクトに対して,undotypeが同じUNDOノードは生成されないようになっているから,オブジェクト1個につき,最大でも5個以上のリングにはならないはずなのだが…また,1個につき上限が5個で,かつ毎回Undoしているのだから,単調増加することはあり得ないように思われるのだが…少しランニングさせて様子を見ることにしよう.やはり,各回につき10個くらいづつ増加している…

どうも,UNDOBASE::CommandEndでコマンドオブジェクトを一つ追加しているというのが敗因であるように思われる.このコマンドは完全にダミーの役割しか果たしていないのだが,これがあると,UndoとRedoの状態の管理がかなりシンプルなものになるという理由から導入されたものだ.しかし,これを廃止するということは本質的な改善にはならないのではないか?というのは,この位置にはリングノードはまったく追加されていないからだ.

コマンドを実行するときには,最初に現在のUndo位置のコマンドリングを完全に削除してからコマンドの実行に入る.従って,つねに白紙状態から実行に移ることになる.これならリングノードの増殖が起こる余地はないと考えられるのだが…もし,それで差し支えないのなら,現行論理のまま,UNDOの現在位置の一つ前の位置まで戻して,そこをクリーンアップすればよいのではないか?いや,むしろ,CommandEndで書き込みしている部分を前方に移動すべきなのではないか?

UNDOのShadowをfreeblock化

極小反例サンプル抽出ツールで全選択が2回入った後,UNDO処理が遅くなるという事象が発生している.バックアップされるオブジェクトの個数が急速に増加しているためだが,その原因はどうも,UndoRedoの動作不良によるものらしい.カード#485を削除すると系図木は3系統に分裂する.このうち始系列を除く2系列は先祖ノードだけの孤立系列で,先祖ノードはそれぞれ,#1294と#5174だ.この時点ではUNDOのコマンドチェーンは,{17, 6, 6, 1}のようになっている.ここで{n1, n2,…}はコマンドのバックアップオブジェクトの個数の並びである.

このあと,カード#497を削除すると,コマンドチェーンは{17, 6, 6, 16, 1}のように変化する.しかし,このあと実行されるUndoでは,チェーンは変化せず,{17, 6, 6, 16, 1}のままになっている.そのまま続行すると,チェーンは{17, 6, 6, 37, 1}のように変化し,チェーンの4番目のコマンドのオブジェクト数は1→ 16→ 37→ 79→ 160→ 366→… のように単調に増加を続けるようになる.そもそも,Undoしているのにコマンドチェーンの長さが短くならないというのがおかしい.⇒いや,勘違いしている.UndoRedoで変化するのはUNDOの現在位置UndoCurptrだけで,コマンドチェーンは不変だ.

従って,カード#497の削除後のUndoで,コマンドチェーンが{17, 6, 6, 16, 1}→ {17, 6, 6, 16, 1}のように変化していないという動作は正しい.実際,UndoCurptrの位置を[]で示すと,{17, 6, 6, 16, [1]}→ {17, 6, 6, [16], 1}のように移動している.この後,カード削除を実行すると,[16]の位置に新たなバックアップが書き込まれるため,その分だけUndoノードが増加する.この辺りの論理は書き換えていないつもりだが,だとすれば以前からこのような動作になっていたことになる…確認してみよう.⇒2022-03-03という版を見てみよう.この版ではUNDO処理はコンパイルオプションで止めてある.⇒… なんということだろう!この版では極小反例 461.zelが何の苦もなく開けてしまった…

image

ということは,これらの反例が開けなくなったのは比較的最近の修正によるということになってしまう.⇒いや,少なくとも「BUG3000-1906.ZEL」は解けない.⇒やはり,解けていないようだ.371点の反例までは解けるが,550点反例では解けなくなる.この事象は計算誤差をどの程度に見込むかなどによって微妙に動作が変化するため,最新版で解けないサンプルが古い版で解けるということもあり得るだろう.

ようやく,なぜこういう事象が起きているのか?という理由がわかった.UNDOでバックアップを取るときのロジックの穴を塞ぐためにUndoCounterというグローバル変数を設け,コマンドを生成するたびにインクリメントするようにして,対象オブジェクトを保全するときにはこの値をオブジェクトに記録し,重複バックアップを回避するように修正しているが,これが却って裏目に出ているということのようだ.UndoCounterはインクリメントするだけの値なので,Undoでコマンドチェーンを遡った状態で新たなコマンドが実行されたときには,前に保全されているオブジェクトであってもUndoCounter値が小さいためにバックアップが再実行されることになる.これを避けるためにはUndoCounterの値をUndoRedoの動作に合わせなくてはならない.

類似パラメータとして,UndoCountというのがある.これはコマンドを生成するたびにインクリメントされるが,ある定数MAXUNDOCOUNTに達したときには,それ以上のコマンド生成を停止し,UndoChainを一つ前に進める.UndoCounterは現状ではMAXUNDOCOUNTに関わりなく,つねに1インクリメントするようになっている.必要な修正はUndoCounterの値をUndoでは1デクリメントし,Redoでは1インクリメントするようにすることだろう.それでよいのかどうか?確認してみよう.⇒ダメだ.さっぱり作動していない.

チェック用のコードなどを入れて,358点まで縮小したサンプルから開始したところ,何点か単点削除検査の後,スタックオーバーフローが発生した.また別の障害が出てきた可能性があるので,元のサンプルでテストし直してみる.⇒コマンドにも時点のUndoCounterを記入するように修正してみたが,全削除2回のあとの単点削除でUndoCounterの不一致が発生した.UndoCurptr->UndoCounterの値は98で,UndoCounterの値は99だ.DumpUndoChainでUndoCounterの値も表示するようにしてみよう.

UndoCounterとUndoCurptrは完全に同期している必要がある.つまり,UndoCurptrが更新される場所ではつねにUndoCounterも更新されなくてはならない.UndoCurptrがリセットされるときには,UndoCounterもゼロリセットされなくてはならないだろう.⇒対処した.UndoCounterはUndoNumberにリネームした.3回目の単点削除→Undo中に発生している.

▲UNDOBASE::UndoProcess→ TOPOLOGY::RebuildCardList→ NAMESORT::NameSort→ NAMESORT::SortNameSub→ compnode のコールバックでcard2の参照番号が0になっている.これまではこのようなことは起きていなかった… 参照番号の入っていないオブジェクトはSWOでもトレースできない.カードテーブルのインデックスが3であるという手掛かりしかない.PDBのsnumは8だ.⇒おかしい.サンプルファイルをロードした時点でこのカードがヒットしない.いや,この[3]というインデックスはカードテーブルではなく,そのルックアップテーブルのインデックスだ.カードテーブルは1発進だが,ルックアップテーブルはゼロ発進になっている.

ルックアップテーブルは毎回作り直ししているので,障害が起きたときのインデックスを参照しても情報がつかめない.⇒これは,参照番号が消えたのではなく,リンクだけが残った状態ではないか?検定では,#23削除→ Undo→ #32削除→ Undo→ #41削除→ Undo で障害が発生している.直近の修正が影響していることは間違いない… ⇒一つ余分なことをしていた.オブジェクトのコピーにUndoNumberを格納していたことが誤動作の原因と思われる.これは不用な動作だった.しかし,依然としてバックアップが増殖してしまう状況は変わらない.

▲nodule::setShadowでエラーが発生した.この関数はShadowチェーンの更新用関数で,オブジェクトのShadowチェーンの末尾に新たに生成されたShadowを繋ぎ込むものだが,対象Shadowイメージにリンクが残っている.このリンクは不正リンクでおそらく,ゴミと思われる.⇒いや,違う.Shadowというのは,オブジェクトの時点におけるコピーだから,その時点でそのオブジェクトがすでにShadowを持っていれば,当然shadow->Shadowには値が入っていると考えられる.

修正した.しかし,いままで一度もここで停止しなかったという点に関しては不審が残る.大分まともな動作になってきたが,まだ検定が進んだ段階でバックアップ個数が再び増加し始める.このまましばらく走らせてどうなるか見てみることにしよう.