アクマくんにお願い:2000年05月上旬

_ 謎設計

久々に時間が取れたので、取り組める。嬉しい。

さて、 以前暖めてたアイディアの実装にとりかかるが、これがなかなか思ったよりも厄介。 ちょっと手をつけてみて直接には書き下せそうにないので、 もう少しメモに整理してみる。

まず、diff -n によって与えられた revision 間の差分を適用する部分。 適用とは言っても、以前書いたようにテキストレベルで作用させるのではなく、 テキストの chunk (塊)の列である revision を表現しておいて、 それから次の revision の chunk 列を計算する。 これが作業の中心である。

そこで、次のような初期状態とすることにする

旧 chunk list 変数
    |
    v
   (chunk1 chunk2 chunk3 ... chunkn)
補正行数変数 = 0

新 chunk list 変数
   ()

厄介なのは、次のような事情である。 ある特定の chunk に対して複数の append や delete の編集が 入ることもあるし、delete が複数の chunk に跨がって作用することもある。 編集される chunk は、そこが chunk 境界でなければ chunk の分断が生じる。 しかし、編集の対象とならなかった chunk は、 「そのまま」次の revision でも使いたい。 変更する必要のない chunk までコピーするのは不合理である。

幸い、diff -n による編集コマンドの出力は必ず対象テキスト行に関して 昇順であることが保証されているから、 編集が終了した chunk は忘れてしまうことができるだろう とりあえず、この方針でメモを書いてみる。 以下、面倒くさいのでメモだけ列挙。

• append 後の状態

  旧 chunk list
             |
             v           
     (chunk1 chunk2 chunk3 ... chunkn)
             |  \
       attr2-1  attr2-2
       'split    'nil
  
  補正行数 += 処理が終了した chunk の総行数(この場合 chunk1 のみ)
  
  新 chunk list
     (chunk1 chunk2-1 appended-chunk)
  

• delete 後の状態 (パターン1、delete 領域が単一 chunk の中にある場合)

  旧 chunk list
             |
             v           
     (chunk1 chunk2 chunk3 ... chunkn)
             |  \
       attr2-1  attr2-2  attr2-3
       'split  'deleted  'nil
  
  補正行数 += 処理が終了した chunk の総行数(この場合 chunk1 のみ)
  
  新 chunk list
     (chunk1 chunk2-1)
  

• delete 後の状態 (パターン2、delete 領域が複数 chunk に跨がっている場合)

  旧 chunk list
             |
             v           
     (chunk1 chunk2     chunk3      chunk4 ... chunkn)
             |  \       |            |    \
       attr2-1  attr2-2 attr3-1   attr4-1 attr4-2
       'split  'deleted 'deleted 'deleted 'nil
  
  補正行数 += 処理が終了した chunk の総行数(この場合 chunk1 のみ)
  
  新 chunk list
     (chunk1 chunk2-1)
  

ある chunk を分割した場合、 分割後の chunk の状態を split, deleted, nil という三つのシンボルで表現した。 split は分割後、新しい chunk list に追加されたもの、 deleted は delete コマンドで削除された chunk, nil はまだ未処理のもので、 今後削除されたり分割されたりする可能性のあるもの、である。

この元で、edit コマンドが作用する始点を発見して それ以前の chunk を新 chunk list にコピーする subroutine。

  while (見つかった chunk より前の chunk について順に) {
    if (chunk 唯一の attr が nil) {
      /* 分割されていない */
      chunk 全体を新 chunk リストに加える
    }
    else if (chunk の最後の attr が nil) {
      最後の attr を 'split に
      最後の attr に対応する子 chunk を作成して新 chunk リストに加える
    }
    旧 chunk list を進め、補正行数に追加する。
  }

  /* 見つかった chunk での処理 */
  if (始点に対応する attr が nil) {
    if (!始点が chunk の最後) {
      始点の marker を chunk に登録(分割)
      始点前の attr を 'split に、始点後の attr を 'nil に
      split に対応する子 chunk を作成して新 chunk リストに加える
    }
    else {
      最後の attr を 'split に
      最後の attr に対応する子 chunk を作成して新 chunk リストに加える
    }
  }

で、この subroutine を使って、 delete command の実装

  まず始点 chunk を探す。始点 attr が nil でなければ error
  見つかった始点以前をシフト。
  終点 chunk を探す。
  while (見つかった終点 chunk より前の chunk について順に) {
    chunk の最後の attr が nil でなければ error
    最後に attr を 'delete にする
    revision を設定
  }
  if (!終点が chunk の最後) {
    終点の marker を chunk に登録(分割)
    終点前の attr を 'delete に、終点後の attr を 'nil に
    revision を設定
  }
  else {
    最後の attr を 'delete に
    revision を設定
  }

append command の実装はもっと簡単

  まず始点 chunk を探す。始点 attr が nil か delete でなければ error
  if (始点 attr が nil) {
    見つかった始点以前をシフト。
  }
  追加 text に対応する chunk を作成して、新 chunk リストに加える

_ 謎実装

家やファミレスで実装したり。

_ 謎デバッグ

edebug 便利だが、直感に反する動きをするんだよなぁ。 とりあえず、SPC, n, f を常用してます。 使いこなすにはもっと経験値が必要そうだけど、まあいいや。

_ 謎評価

とりあえずバグが取れたみたいなので動かしてみるが... 遅い。 main trunk に数個しか revision がないものならさして気にならないが、 数100個の revision があるものだと、上のアルゴリズムで数分待たされる。 これは前処理の部分なので、これでは実用にならない。 とりあえず byte-compile してみて、明かな部分を defmacro で書換えてみる。 もとい、defsubst なんてあるのか。こっちのほうがいいかな。

とりあえず、FreeBSD の @src/sys/kern/vfs_bio.c,v (最終 revision が 1.251 で このアルゴリズムを適用すると 1.1 での chunk 数が 2666 個だった) で byte-compile 版でテストしてみると 72 秒。 (Pentium MMX 200MHz, 64MB, FreeBSD 3.3) 前処理でこれでは使いものにならないなぁ。

とりあえず、profile を取りたいので調べてみると edebug の機能で coverage test 機能があるようなので、それを使ってみる。 (さすがに edebug に coverage test を入れると、 vfs_bio.c,v では遅すぎて終らないので、 もう少し revision 数の少ないファイルでテスト)

実行回数の多い行を探すと、どうやら次のような場所のが該当している。

• chunk list から特定の行番号を含む chunk を線型探索する部分。
• 始点検出と新規 check list への追加 subroutine の loop 部分。
• command 処理が終了後、旧 chunk list の残りを 新 chunk list に追加する loop 部分。

とりあえず、新 chunk list への追加を nconc で手を抜いているところを 新 chunk list の終端部分(の直前)を保持しておいて、 毎度まいど nconc のたびに新 chunk list を走査しないようにしてやるだけで、 72秒が28秒に短縮(^^;

どうもデザイン的に複雑にしている割には、効果が出ていない。 よく考えるともう少し単純化できるところがあるようだ。 旧 chunk list の先頭に分割された chunk をそのまま残しておくのではなく、 分割された親の代りに未処理の子 chunk を代りに置くようにすれば良いのではないか?

また、それ以外にも chunk list という構造自体に問題がある。 ほとんどの時間は長い chunk list の走査と、chunk list を構成する chunk (のポインタ)のコピーに費されているようだ。 これは、その時点で最も細い chunk をそのまま list にして保持しているために、 revision 数が多くなると chunk が細かすぎて、chunk list が長くなる。 始点検出ルーチンの loop 部分に比べて始点検出ルーチンの呼出し回数はずっと少い。 ということは各編集 command の毎に平均数十個もの chunk pointer を そのままコピーしているわけで、 これを減らすようにできればもうすこしマシになるのではないか。 その為には単純に chunk list として保持していてはダメで、 ある時点の chunk 列を木構造にまとめて保持して必要な木(あるいは部分木) のレベルで移動するようにしてやる必要がありそうだ。 うーん、merge/split のアルゴリズムをきちんと調べないとダメかなあ。

手元の備忘メモをそのまま日記にしてるので、 文体、意味不明、その他の点は御容赦を。 それから、さすがにこれだけの内容を今日一日でやった訳ではないけど、 実際に書いた日に分けるのが面倒なので、そのまま。

というわけで、別アルゴリズムの実装を検討する。

_ 問題点

chunk 分割アルゴリズムを適用すると、 差分の適用ごとに chunk が分割されていくので、 ある程度の長期にわたって開発されて続けているファイルに対しては、 chunk 数が数千ものオーダになる。

今回のアルゴリズムが失敗だったのは、 各 revision は chunk の単純な列構造によって構成されてるからである。 このように chunk が数千もの revision に対して 差分の適用をすると、 その差分自体は数個の編集コマンドしか含まないものであっても、 差分適用のたびに新しい列を構成しなければならないからである。 確かにほとんどの chunk 自体は再構成をする必要がないので変更はないが、 あまりにも chunk が細かいので chunk を指す列構造の複製の時間が 馬鹿にならないのである。 また編集対象となる chunk を線型探索する時間も問題である。

それから、列構造全体が必ず複製されるのは、記憶領域的問題もある。 ある順序構造を一旦構成したら、可能であれば複数の revision 間でそれを共有したい。

そこで、chunk の列構造の代りに chunk の木構造を持つことにする。 木構造の高さを適切に制御できれば、 編集対象 chunk の探索は対数時間で可能そうだ。 そして編集対象とならなかった chunk が 構成する部分木はその中身を変更せずに そのまま次の revision の chunk 木の一部にしてしまえばよさそうだ。

木構造もいろいろあるが、木の高さを適切に制御するためには AVL 木や B木のように部分木の高さの違いが一定に押えられている構造が 必要だろう。 とりあえず、ここでは B木を採用してみることにする。

_ B木 構造

B木は一般に、 ディスク上に効率よくインデックス構造を導入するのに使われるが、 必ずしもディスク上だけの構造とは限らず、 メモリ上の構造としても利用できる。

各ノードの最大要素数を決定する定数を M と置くと、B木には

1. root の要素数は二つ以上(B-tree 全体の要素数が一つ以下の場合を除く)
2. root 以外のノードの要素数は M/2 以上 M 以下
3. 全ての葉は同じレベルにある

という性質がある。 ただし、 ここでは chunk 木として利用するために、 各種 B 木の実装にある「キー」を省略して単純化した。

一般に、 AVL 木等の B 木以前の木が、木の変更操作をトップダウンで行うのに対し、 B 木は木の変更をボトムアップで行うのが特徴である。

キーは、そのノード内での相対行番号である。 あるノードの子が n 個とすると、そのノードのキーの数は通常 n+1 個であるが、 相対行番号として先頭を常に 0 とすることで、 実際に記憶しておくキーは n 個でよい。

_ 分割アルゴリズム

ある revision の B木が与えられたとして、 その B木に差分(編集コマンドの列)を適用して 新しい revision のB木を構成する。

編集 command 毎に分割点を計算し、 以前の編集点(あるいは先頭)以降、 分割点までの部分木を順に 新しい B木に連結する。 B木同士の連結を行う subroutine が下請けに必要。

その図を書こうと思ったが面倒なのでパス。

木の中での編集の位置を整数のリストで表現する。 (1 2 2 N) というリストは、 root から見て1番目の部分木の2番目の部分木の 2番目の chunk の N 行目の直前という意味である。 最初の部分木は0と定義する。 また最初の行は0行目である。 位置がちょうど部分木の間や chunk の間を指す場合、 もっと短いリストで表現する。 例えば "(1)" は最初の部分木の直後を指している。 これは位置としては "(1 0 0 0)" に等しいが、 部分木の内部でないことも表現している。

search(tree, pos)
{
  if (pos < 0)
    error
  else if (pos == 0)
    return list(0)

  for (i = 0; tree.pos[i] < pos; i++)
    if (i >= tree.length)
      error

  if (pos == tree.pos[i])
    return list(i+1)

  if (i == 0)
    return cons(i,search(tree.node[i], pos))
  else
    return cons(i,search(tree.node[i], pos-tree.pos[i-1]))
}

delete command の開始点を "last"、 終了点を "deleted" という変数にリスト形式で格納することにする。 その上で、数字のついた部分木を数字順に新しい B木に連結する。 実際には直前の "deleted" で指した場所から "last" の場所までを B木に連結することにして、 "deleted" の値を "(0)" で初期化しておけば良い。 開始点が直前の "deleted" より前であればエラーである。

append command の対象行は "deleted" より前であってもよい。 この場合は何もせず、apppend で指定された chunk を生成して 新B木に連結する "last" より前であればエラーである。 "deleted" より後であれば、delete command と同様、 直前の "deleted" で指した場所から append 行までを B木に連結する。 この後、append 行のリストを "deleted" と "last" に格納して、 apppend で指定された chunk を生成して新B木に連結する。

search アルゴリズムで作られた位置リストが二つ与えられた時、 その間にある部分木を列挙していくアルゴリズムは次の通り。

shift(tree, posA, posB)
{
  nA = car(posA)
  nB = car(posB)

  if (tree は実は chunk) {
    shift_newchunk(tree, nA, nB)
    return
  }

  if (nA < nB) {
    if(cdr(posA) != nil)
      shift_after(tree.node[nA], cdr(posA))
    else
      nA-- /* 木の先頭、shift_after よりも shift_subtree を使う */
    for (i = nA+1; i < nB; i++)
      shift_subtree(tree.node[i])
    if (cdr(posB) != nil)
      shift_before(tree.node[nB], cdr(posB))
  }
  else if (nA == nB) {
    shift(tree[nA], cdr(posA), cdr(posB))
  }
  else
    error
}

shift_after(tree, posA)
{
  nA = car(posA)

  if (tree は実は chunk) {
    shift_newchunk(tree, nA, chunk の終り)
    return
  }

  if (cdr(posA) != nil)
    shift_after(tree.node[nA], cdr(posA))
  else
    nA-- /* 木の先頭、shift_after よりも shift_subtree を使う */

  for (i = nA+1; node の終りまで; i++)
    shift_subtree(tree.node[i])
}

shift_before(tree, posB)
{
  nB = car(posB)

  if (tree は実は chunk) {
    shift_newchunk(tree, chunk の最初, nB)
    return
  }

  for (i = 0; i < nB; i++)
    shift_subtree(tree.node[i]);

  if (cdr(posB) != nil)
    shift_before(tree.node[nB], cdr(posB))
}

これで、切断点 posA, posB を与えるとその間の 部分木に対して先頭方向から順に、shift_subtree() を呼出す。あるいは切断点が chunk の中にあれば、 shift_newchunk() を呼出す。

編集の対象とならなかった編集点の間のテキストは、 このアルゴリズムでなるべく大きな部分木に順次分解し、 新規の木に追加していくのである。 部分木の追加アルゴリズムを上手く作れば、 編集点の近傍以外の部分木はかなり共有されるはずと期待できる。

次に必要なのは、B 木同士を連結してより大きな B木を構成する アルゴリズムだろう。B 木の部分木はそれ自体 B 木の条件を満しているので、 構成されたものも B 木であれば、B 木同士の連結だけを考えれば良いのである。

_ B木連結アルゴリズム

前の木をA、後ろの木を B とする。 下請けの concat1 はノードのリストを返す。 リスト中にノードが二つある場合は、 B木のpromotion(昇進)が発生している。

concat(A, B)
{
  rval = concat1(A, B)
  if (rval.長さ == 1)
    return rval[0]
  else { /* root promotion */
    r = 新ノード(長さ = 2, level = max(A.level, B.level)+1)
    r[0] = rval[0]
    r[1] = rval[1]
    return r
  }
}

concat1(A, B)
{
  if (A.高さ < B.高さ) {
    rval = concat1(A, B.root[0]);
    if (rval.長さ + B.root.長さ - 1 <= M) {
      新ノード = rval + B.root[1...N](level = B.level)
      return list(新ノード)
    }
    else {
      /* rval + B.root[1...N] を二つに分割 */
      新ノード1 = rval + B.root[1...N]の前半
      新ノード2 = rval + B.root[1...N]の後半
      return list(新ノード1, 新ノード2)
    }
  }
  else if (A.高さ > B.高さ) {
    /* 対称なので略 */
  }
  else if (A.高さ == B.高さ) {
    if (A.root.長さ + B.root.長さ <= M) {
      新ノード = A.root.[0...L] + B.root[0...N](level = A.level)
      return list(新ノード)
    }
    else {
      /* A.root.[0...L] + B.root[0...N] を二つに分割 */
      新ノード1 = A.root.[0...L] + B.root[0...N]の前半
      新ノード2 = A.root.[0...L] + B.root[0...N]の後半
      return list(新ノード1, 新ノード2)
    }
  }
}

なお、「新ノード」は概念的なもので、 必ずしも新しいノードをその都度 allocate しなくても良いが、 古い revision で確保されたノードに対しては副作用は禁物である。 ノードに生成された revision 番号を入れておき、 古いノードに対する操作の場合は allocate しなおすことにする。

このアルゴリズムは一応、独自に考えたものではあるが、 通常の B木への要素の追加アルゴリズムを微妙に変化させたものに過ぎない。 要素なら葉の位置に追加するけれども、 同様の追加を高さの枝で行う、というただそれだけの話。 双方同じ高さの木の場合だけ、特別扱いするが、これも難しいことは何もない。

_ 実装、評価

新しいコードは elisp で 500 行程度かな。 edebug でぼちぼちデバッグする。

うーん、あまり速くなった気はしないけども、こころもち早いかなぁ。 変更個所の少い revision 間では、以前と比べてかなり短時間で 終っている気もする。

動きだしたようなので edebug の test coverage 機能で 各行の実行回数を測定。 実行回数の多いところを中心に、cond の順序とか、 defsubst の検討とか、loop 外への処理の括り出しとかみなおしてみる。 うーむ、これだけデータを食わせて、一度も実行されない部分が結構ありますね。 そのあたりはまだバグが隠れている可能性も高そう。

実行時間の測定。 前回と同一条件で、28 秒 -> 12 秒で、それなりの効果は出ている模様。 あと、感覚的にメモリの消費も減っているような気もするが、こっちは ちゃんと計測していないからなあ。 限界気味だし、vfs_bio.c,v は相当 revision 数も行数も多い部類に入るので、 一般的な用途だとかろうじて許容範囲内かなぁ。 このあたりはもう少し実装してから、 実際にいろんな人に使ってもらわないと何とも言えないかも。 スケーラビリティは圧倒的に高くなっている気がする(多分、 編集コマンド一つあたりの処理速度は (log chunk の個数)^2)けど、 各操作が複雑になってますからね。 それから、ノード辺りの最大分岐数を 8 で実装してますけど、 これも調整が必要。

tree からテキストの復元コードを実装してみる。 良かった、正しく復元できている模様。 でも、同一バッファにいろんな revision を復元してみると、 やたら emacs が太ってくる気がするので、 undo を禁止してみたら効果があるようだ。

_ TODO

あと、やりたいことを忘れないうちにメモ。

• 木の node 数のチューン
• 木の走査アルゴリズム。 関数の入口で葉か枝かを判断するよりは 部分木の高さを明示的に保持しておいて、 「再帰呼出し -> すぐ葉の処理」の部分を親側で直接葉の処理を呼出すようにする。 かなり関数の呼出し回数が節約できるはず
• 部分木連結アルゴリズムの改良。同じレベルの部分木を複数連結する場合は、 各々の部分木ごとに連結関数を呼びだすよりも、まとめて連結するアルゴリズム にした方が効率が良さそう。
• annotate, vc-annotate みたいな色分け。
• 特定行の生成 revision(過去)/削除 revision(未来)へ jump。
• diff 表示の実装、直前 diff と、特定 revision との diff
• diff 込みのテキスト表示(全テキストをバッファに入れるが、 差分部分をわかるようにする)色分け diff
• revision 前後移動時の、「現在行」の保存。
• branch 表示の show/hide
• revisions バッファの見栄え。日時,author,TAG,log の先頭などの表示。
• log バッファ中の日時、author, TAG 名の表示。色分け。 "Submitted-by:" などの色付け。
• log バッファの表示 on/off
• window configuration の選択(逆 T 型、3段型)
• 複数 revision に渡る grep, (text/log)
• vc や emerge, ediff との連携

_ diff の実装

二つの revision 間の「共通chunk」がわかる、というのが第一ステップ。 chunk 構成中に各 chunk について生成された revision と削除される revision (これは、枝別れによって複数ありうる) がわかるので、双方を chunk に記録しておく。そうすると、chunk を見ればその chunk の有効範囲が わかるので、一方の revision の各 chunk を走査しつつ、 相方の revision での chunk の生死を判別すれば、 「共通chunk」が決定できる。 現在行の保存も、この考えの延長で対処できそう。

_ 配布

そろそろ総計 1500 行にもなるし、簡単 annotate も実装できたから この状態でも有用なのは確かで...

むう、しかし、ドキュメントが無い。ドキュメント文字列が一行もない。 (コメントは若干あるが...) ドキュメント文字列もコメントも全部英語にする つもりだけど、ぼちぼち書くしかないかなぁ。 全くないからコードを読む以外利用不可能と見た。

それよりもライセンスどうすべ。 今回は完全に scratch build だから、自由に設定できるんだが。 配布を考えると、GPL にして本家の lisp ディレクトリを目指すべきなんだろうけど、 full scratch のものを GPL にするのは何だかなぁ。

BSDL にするのも芸がないし。どうせ自分で自由に設定できるだから、 偶数番は GPL で奇数番は BSDL にするとか(ぉ

それよりこっちを何とかせい。

masanari さんのところから。

タイプＧ・・・・・完璧主義者タイプ

■ セロトニン：High　→ これが多い人ほど、几帳面で協調性や秩序を重んじ、粘りがあります。ただし、いろいろと考えすぎて決断に要する時間が長くなる傾向があります。しかし、この指数が高すぎると、人はあまりにも考えすぎて神経質かつ臆病で、不安をかかえやすくなります。

■ ノルアドレナリン：High　→ これが多い人ほど勝ち気で負けず嫌い。自己中心的でマイペースを崩しません。自己評価を傷つけられると容易に他人を攻撃するため、嫌われることもあります。どちらかというと衝動的でカッとなりやすいほうなので、特に対人関係には注意が必要です。

■ ドーパミン：High　→ これが多い人ほど何にでも興味を示し、外向的で快活になります。ちょっとしたことにも喜びを感じることができ、心にゆとりが生まれるために、他人を気づかう余裕ができます。このホルモンが多い人は性格にマイナス面があっても表には現れないと言う特徴があります。

■ 一般： 好きなものに対する集中力は人並み以上のために、その分野では優れた能力を発揮し、人に認められます。繊細で細かく、粘りもあり、まわりから高い評価を得る一方、あなたはその完璧さを他人に強制し嫌がられることもありそうです。その場合、自分を認めてくれない人に対しては冷たい態度をあらわにしてしまいます。知性が豊かで、気まじめに物事をこなす能力があるにもかかわらず、さらに完璧にしようとする裏側には自信のなさが潜んでいそう。

■ 好きなタイプの女性： 貞操観念が低かったり、だらしがなかったり、知的に劣る女性ではルックスがよくてもとびつきません。外見がちゃらちゃらせず、一途さを示す女性にひかれます。つまり、好みに最もうるさいタイプと言えそうです。

■ 恋をするとこう変わる： 他の女性にモテるにもかかわらず、誠実で一途なところがあります。しかも標的を定め、相手の女性攻略にも熱心です。ただし、女性に熱中するあまり、仕事や勉強がお留守になることもあるでしょう。基本的にみかけよりもまじめなタイプです。

■ 恋愛アドバイス： 完璧主義のあなたは相手の不完全さを指摘する傾向にあります。もちろん冗談交じりに指摘するので、それほどいやみはないのですが、知らないうちに相手を傷つけることも多いと言えます。妥協すること、許すことを覚えればすばらしい恋愛が可能になるでしょう。あまり相手にいろんなことを要求しすぎないよう注意して下さい。

だそうな。

UserKernelConfig の OpenBSD からの NetBSD への移植です。

起動時に cfdata を変更してますが、 これが dconf に与える影響はすごく微妙。 多分 dconf の方をこれに適合するように設計することは可能だと思われます。 OpenBSD の実装の方は attr とか触っているようで非常に微妙ですが、 NetBSD の方はそのあたりを(多分意図的に)除いてあるような気もしますし、 希望も多いようなので、たぶんこのままいっちゃって問題もないような気もしますが、 uch さんとか gehenna ちゃんの意見も聞きたいところ。

いずれにしろ OpenBSD にあるような "add" 相当のコマンドは欲しいですけど、 これも dconf に影響大ですし。 (昔、newconfig で私が "clone" と言っていたものと同じ操作です、これは)