ギャップバッファ

Thebe

初めて見た構造なのでメモです。

http://www.kmonos.net/wlog/39.php#_2322040527
http://aiwww.main.eng.hokudai.ac.jp/~takty/program.html

なるほどなるほど。
現在編集しているあたりを差分として、線形配列の最後のほうに固めておいて、編集カーソルが移動したら書き戻す構造ですか。…という解釈でいいですか？
線形配列は一般的に言えば挿入、削除が遅いですが、数個移動させるだけでいい最後のほうはそうでもないので、賢い構造と思います。たまたま私が見たのがvectorの後ろを再利用してるだけで、データを前半と後半にわけてその間を編集して、また別の場所を編集する時はそこでわけ直して他をマージ…ってのが正しい解釈のようです。

ちなみにThebeでは、可変サイズのバッファを単方向リンクリストでつないだものを使ってます。最初は連続メモリですが編集が起きた位置で前後に切ってしまうわけです。ある程度(1kbだったか？)よりも細切れになってしまうようなら切らずに直接そこを書き換える方針です。ランダムアクセスでも、ユーザーが編集した地点のうち距離が近いものを除外した数だけリンクをたどれば到達できますので、まあまあじゃないかと思ってますが、Thebeの動作を見てればわかるように巨大なファイルには弱いです。

それとは別に、双方向リンクリストで行とかUTF16化済みデータとか色分けの管理を行っていますので、開くファイルの約3〜5倍強のメモリを消費してしまうのがなんとも。逐次UTF16化するようにすればメモリは節約できるでしょうが、速度が心配です。

CyberXに4MBとかのファイルを開くのが遅いと言われたときはうわーって感じでしたが、10MBぐらいは楽勝で扱えないとバイナリエディタを名乗れないかも…ですね。純テキストエディタのgreenpadと勝負しても仕方ないかもしれませんが、それにしたってthebeは遅すぎる…もっともこれは、むしろ色分けや改行の処理が遅いことがわかってます。肝心なのは、バッファより、そういうのも含めたトータルなデータ構造なんでしょうね…。

混乱を防ぐために書いておきます。
greenpadというのはk.inabaさんの高速なテキストエディタ。データはUTF-16で、ギャップバッファと呼ばれる構造で格納しているらしいです。読み書きに対応した文字コードが多いのが特徴で、私はブラウザのソース表示エディタに使わせていただいています。
thebeというのは私の鈍速なバイナリエディタ。データは無変換で、単方向リンクリストで管理しています。…で、言い訳ですが、テキストエディタ風の表示もできるというかそっちがメインな謎エディタですので、正直かなり無駄の多いことをしています。

あがき

Thebe

↑では、余計な事を書かずにバッファのデータ構造だけに絞れば良かったと後悔しつつ、高速化を試みるテスト。
頻繁に呼ばれる、位置(Integer)から行(双方向リンクリストの要素)を探す関数にキャッシュみたいなものをかますと、巨大ファイルの編集に関しては、特に後半の編集に、微妙に改善が見られました。前の方の編集は、後の全ての行に対してリンクリストを辿って位置情報とかインクリメントしていかないといけないのがネックなのでしょう。つーかバッファのデータ構造全く関係無さそうだなあ。
しかし体感的には、やはり色分け処理のほうが重く感じます。編集そのものが重く感じるのは3MBぐらいからなんですけど、色分けはWindows.pasでもうだめ。

これを解決するには、次のような選択肢があると思われます。

  1. 凝った色分け処理をやめる
  2. 凝った色分け処理をやめる
  3. 凝った色分け処理をやめる

色分け用の限定正規表現はNFAでマッチさせてますけど、DFAにしたって効果なんか見込めませんよねえ、ええ、うん、そうにちがいない。
(昔アルゴリズムの本を見てDFAのところで頭が痛くなったらしい)

そして、私はまた余計な事を書いてしまったと後悔するに違いない──