Orz日記 by Akio Morita

_ [SAD]メモリ割り当てBackendの更新

LP64環境での中期的な運用維持のため、整理実施

• SADインタプリタヒープの返却機構の廃止 (未使用インターフェースの廃止)
• mmap(2)で仮想アドレス空間が予約可能な場合、自前の仮想アドレス割り当てを実施 (vm backend)
  • SAD Objectヒープとして最大16GBを利用可能 (但し、ガードページ・SADインタプリタスタックへの割り当て分を除く)
  • 現行実装では、FreeBSD上のMAP_GUARDオプションのみをサポート
• 仮想メモリ割り当て時のmalloc(3)の使用を取り止め、mmap(2)のみのサポートに移行

現行実装では、*list配列と*stk配列のアドレス空間共有を前提としているコードが残っていることから、一部制限あり

• SADインタプリタスタック割り当てにより利用可能なSAD Objectヒープ空間が減少する
• SADインタプリタスタック割り当てに失敗する (mmap backend)

将来的には、下記の依存コードの再実装後の*stk配列空間のアドレス分離により解消予定

• sortl インターフェース (実装設計検討中)
• string bufferインターフェース (界面層の調査中)
• evalエンジン (未着手)

_ [SAD]Sort backendの再実装

個別に実装されているsort algorithmをlibc等の実装に置き換える

quick sortに関しては、qsort_sを採用したが、ISO C11のExtension1なので未実装の環境が多いのが難点

関連するコードの検証・再実装を進めているうちにいくつかバグを発見

• Real型の順序付け(Order関数)が全順序になっていないので、Sort[]の出力が初期状態に依存する
  • Order[NaN, x] != -Order[x, NaN] である
• Unionのオプションで渡ってくる比較関数は、同値類の分類関数 SameTestのはずだが、順序付けに用いているので正しく機能しない

_ [SAD]sort再実装の残作業

次に作るもの

• sort済みlist containerへの1要素挿入 tfinsertsort
  • 挿入元と出力がlist containerなのでインタプリタヒープ断片化の原因となり得るが、それを変更するには構築途上のreference container型を導入する必要がある
  • ソースコンテナ内のNull[...]要素を展開する機能がある
    • テンポラリコンテナへのシーケンス展開エンジンが必要
• 整数配列へのインデックスソート tfsorti (tfsortsymbolstk実装用)(r6179にて実装 2021.05.20)
• 実数配列へのインデックスソート spsort (spkick実装用)(r6182にて実装 2021.05.20)
• Intersection/Complementの再実装
  • 現行実装には問題点あり
    • 3要素以上は、再帰呼び出しにて実装している (スタック消費)
    • Intersectionに関しては、サイズ最小のリストを種にすべき
    • 積集合・和集合の抽出に使う整列済みリストは、union_listで得られるリストコンテナを使っている (SADインタプリタヒープを消費・断片化している)
      • 再帰呼び出しでは、一時割り当てしたリストコンテナを再帰的に生産するので、ワーストケースのインタプリタヒープ消費は、種リストの長さNに対して $O(N^2)$ (再帰毎にリストが短くなるケースが最悪)
    • Intersection/Complementどちらの場合も、出力候補となるリストの長さは単調現象となるので、一時領域の再割り当てを行う必要は無い

性能に関しては、オリジナル実装では実数リスト等のケースで比較ルーチンがソートエンジン内に展開されているのに対して、qsort(3)等では関数呼び出しが必須となる点は不利だが、実数リストコンテナではインデックスソートではなく、出力配列を直接スワップすることで間接参照コストを低減する最適化を行ったため、N = 2^24でのテストでは、整列・逆整列・準整列・ランダムの各パターンで、オリジナル実装よりも概ね良好な性能が得られている

ISO C++がテンプレート版sortがつかえれば、比較ルーチンのinline展開により更なる改善が得られると思われる

_ [SAD]sequence container utility

list containerにする前の編集可能なsequence container utilityの設計案をまとめておく

内部構成

• slad_t *ad
• rval_t *av
• unsigned int n - current sequence length
• unsigned int nmax - maximum allocated length

長さに関しては、list containerが 2^31-1で制限されているので、 size_tでは無くintで充分(念のためにunsignedで定義すべき)

基本

• seq_alloc - 割付
• seq_free - 開放(adの参照先は、dereferenceしない)
• seq_resize - リサイズ
  • 編集作業用utilityなので、メモリ不足時にリカバリー出来るとは思えないので、真偽値を返すよりも abortしてしまう方が簡単か？(あるいは、seq構造体にエラーフラグを持たせておいて、最後に検出する)
  • 可変長バッファの再利用性を高めるために、適当な2^Nで丸める
• seq_load_list - list containerからロードする (stackへの展開動作の置き換え、Join実装)
• seq_expand_list - list containerから展開する (Null[...]を再帰展開する)
• seq_insert - sequenceへ挿入
• seq_ordered_insert - 整列sequenceへ挿入

更新系の動作に関しては、

• 破壊的更新 (resize動作を含む)
• 新しいsequenceの生成 (alloc動作を含む)
• list containerの生成

のバリエーションが考えられる

編集結果をlist containerやsequenceで返す場合、生成型の動作がメモリ割り当て効率的に望ましいが、命名規則を考える必要がある

_ [SAD]Intersection/Complement

sort engine入れ替え後にregressionしたので調査したが、リストをスタック上に展開して舐める際に、空のリストが考慮されていないのが、原因だった

オリジナルコードだと、直前にUnion1をスタック経由で呼び出す際の引数がスタック上に存在するので、無効参照を避けているが、演算結果は結果が正しくない

問題を起こすのは、第二引数が空のリストのケース

Intersection[{3,1,{},2}, {}]

空集合との積集合なので{}を返すべきところを{{}}を返す

Complement[{3,1,{},2}, {}]

空集合を除外するので、{1,2,3,{}}を返すべきところを{1,2,3}を返す

さらに、戻り値の構築をitflistで行うため、スタックが空(空集合)のケースでは、itflistからitfcrelistmへ頭部(ntfoper, mtfleftbrace)で移譲され、itfcrelistmが構築済みのiaxnulll空リストコンテナの参照を返すが、その後にcopyheadで頭部を挿入する過程で、構築済み空リストが汚染されている

_ [SAD]再入可能なqsort(3)

標準化という意味での本命は、ISO C11 Annex.Kのqsort_s(3)だけど実装している環境はFreeBSDやMicrosoftぐらいか？

glibcのqsort_rは戻り値が無い以外は、ほぼqsort_s

次点は、ISO C++にlabmdaで標準化された無形クロージャに対応する機能がISO Cで標準化されることとだが…どうなんでしょう？

実装例的には、LLVM/clangのBlock構文拡張がそのものズバリなのだが…

GCCのNested Function拡張も近いけど、あくまでもローカルスコープ上で定義・参照可能な関数なので、リテラルで引数に積めない、クロージャとして戻り値に出来ないあたりがlambdaやBlock構文拡張に劣る

実用面では、FreeBSDのGitHubからqsort/qsort_sの実装を持ち込む辺りか？

古い教科書には、平均的なケースではオーバーヘッドが多いmergesortはquicksortに勝てない的な言説が書かれているが、現代的なハードウェアでの実測だと比較回数が同程度の状況でmergesortがquicksortに劣る事例は以外と少ない、またその差が小さい模様

初期順序が同一でも比較操作時の間接参照が増えるとquicksortに逆転されることから、キャッシュ階層が深い計算機環境では、mergesortの方がメモリアクセスの連続性が高い(マージ操作)ためにキャッシュ効き易いためではと推測される

ちなみに、heapsortの実行時間は$N\log{N}$で安定だが、quick/mergesortに比べて数倍〜10倍程度遅い模様

$O(N)$の作業領域が安定して確保出来る状況であれば、mergesortを標準にしたほうが良さそうだが、標準実装してるのはBSD系ぐらいで、再入可能なmergesortを標準実装してるのはBlock拡張付きのDarwinとFreeBSDぐらいなのが玉に瑕

_ [SAD]*sort_sもどき

NetBSD上では、マシンスタックを使ったGCC nested functionが動かないので、 FreeBSDのlibc/stdlibからqsort.c/merge.c/heapsort.cを持ってきて、qsort_sもどきのinterfaceを持ったre-entrant sortを実装した

主な違いは、errno_t型やrsize_t型をintとssize_tに置き換え、mergesort/heapsort系は戻り値がerrnoでは無く、元と同じ0 or -1な点

現行の利用用途では、戻り値は失敗時の分岐条件に使うだけなのでこれで十分

_ [SAD]作業予定のアップデート

1. mk/sad.framework.mk を mk/Uses/Framework.mkへ再編
2. mk/sad.bultin.mk を mk/Uses/Builtin.mkへ再編
   • Builtinの切り離しは、USES+=Builtin:foo=offの形式にする (Builtin_ARGS変数経由で制御)
3. build frameworkの内部変数の整理統合
4. configuration sampleのクリーンアップ
5. sequence container utility実装
6. Intersection/Complement (sequence container utilityベース)
   • Intersectionは、引数列中の最短リストUnionして種に使う
   • Complementは、第一引数をUnionして種に使う

_ [SAD]LINEバグ

LINE["S", position + frac]の動作が、Twiss[*, position + frac]系と異なるバグが昔から知られているが、少し深堀りしてみた

原因は、positionの次のbeamline-elementがOFFSET付きMARKerの場合、beamlineに沿った内部配列の次の要素が物理的に異なる場所を指しているにも関わらず、線形補間するためであるが、自体はもう少しややこしい模様

明らかに線形の変化で無い要素に関しては、qfraccompで一時的にbeamline-elementのパラメータをfracでスケールして部分的に再計算しているため、GEOなどは正しく扱われている模様

現時点で判明している正しくないLINEのkeywordは以下の通り

• S,LENG - itfpos配列の線形補間
• GAMMA,GAMMABETA - itfgamm配列の線形補間
• SIG* - 光学関数は再計算しているが、itfgamm配列の線形補間を結果のスケーリングに使っている

調査過程で、SIZE*keywordに関しては、itfsize配列の割り当て状況を検査していないので、SEGVで落ちるケースが発見された

Rev.6409時点では、S,LENG,GAMMA,GAMMABETAの補間は修正済み、SIZE*に関しては未割り当て時はエラーを返すように変更済み