Note

サイト
最近のコメント
 | 

2004-05-28

風向きは東いつだって東

昨日は、日帰りで大阪行って帰ってきただけ…つまらないつまらないつまらない。

収穫はたこ焼きとヘイスティングス二冊と贈本用に「バーチャルガール」「サリーはわが恋人」なり。

[] ギャップバッファ

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

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というのは私の鈍速なバイナリエディタ。データは無変換で、単方向リンクリストで管理しています。…で、言い訳ですが、テキストエディタ風の表示もできるというかそっちがメインな謎エディタですので、正直かなり無駄の多いことをしています。

[] あがき

↑では、余計な事を書かずにバッファのデータ構造だけに絞れば良かったと後悔しつつ、高速化を試みるテスト

頻繁に呼ばれる、位置(Integer)から行(双方向リンクリストの要素)を探す関数キャッシュみたいなものをかますと、巨大ファイルの編集に関しては、特に後半の編集に、微妙に改善が見られました。前の方の編集は、後の全ての行に対してリンクリストを辿って位置情報とかインクリメントしていかないといけないのがネックなのでしょう。つーかバッファのデータ構造全く関係無さそうだなあ。

しかし体感的には、やはり色分け処理のほうが重く感じます。編集そのものが重く感じるのは3MBぐらいからなんですけど、色分けはWindows.pasでもうだめ。

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

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

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

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

k.inabak.inaba 2004/05/28 19:59 そういう解釈になる…のかな?「Thebeのように編集地点で切断する。ただし最大二分割しかせず、三分割になりそうだったら真ん中のバッファを左右のどっちかにくっつけちゃう」感じです。巨大ファイルの先頭辺りと末尾辺りを交互に編集されると弱いんですけど、そういうことする人はあんまり多くないんじゃないかと思って。

ytqwertyytqwerty 2004/05/28 22:47 あー…えーと…そうですね。見たコードがたまたまvectorの後ろの方を利用していただけで、並べておく必要は無いですものね。

ytqwertyytqwerty 2004/05/28 23:07 ちなみに1MB強のWindows.pasの先頭と末尾を交互に編集しても、特に遅れは感じられなかったので全然問題ないです>greenpad

yaneuraoyaneurao 2004/05/28 23:32 1MBなんか、memcpyで0.05秒かからないわけで、方式によらずまともな速度が出ないほうがむしろ異常です。せめて100Mから1Gぐらいのファイルでやらないと何の参考にもならないような..。>バイナリエディタとしての性能ならば

ytqwertyytqwerty 2004/05/28 23:44 体感で速ければOKですっ(実際にthebeでは遅いのがわかるんですから…涙)。それと私の書き方が悪かったのですがk.inabaさんのgreenpadはテキストエディタですよ。

yaneuraoyaneurao 2004/05/28 23:54 1M程度のファイルで体感的に遅いのってメモリコピーが遅いだけじゃ?ちゃんとMMX用のqword単位で転送するルーチン書いてますか?

ytqwertyytqwerty 2004/05/29 00:03 本文を直してる間に書かれてしまいました。エディタってのはバッファ以外にも行の管理とか色分けとか色々あるわけで…そういうものの構造とバッファのデータ構造が、両方とも高速に編集できるように噛み合って無いのが遅い理由と思ってます。正直に言えば転送自体も言語ランタイムの転送関数ですのでREP MOVSDだったりしますが、おっしゃる通りそれでも1MBなんて一瞬ですので…。

yaneuraoyaneurao 2004/05/29 00:12 ほむほむ..テキストエディタも真面目に設計するとなかなか難しいんですな..

k.inabak.inaba 2004/05/29 00:17 20メガ行で

k.inabak.inaba 2004/05/29 00:20 失礼。マシンにもよりますが20メガ行くらいで試すとだんだんヘタってきます>GreenPad。でもこっちの場合は、先に文字コード変換とかメモリアロケータが目に見えて重くなるので直すならそっちなんですよね(^^;

k.inabak.inaba 2004/05/29 00:26 純粋にバイナリエディタのみだと改行位置の把握が要らないので楽ですけど、テキストエディタ的なバッファ構造でパフォーマンスを出そうと思うと大変だろうなぁ…というのが最初にThebeを見たときの感想でした。

ytqwertyytqwerty 2004/05/29 00:38 事実パフォーマンスは最悪ですので、笑ってやってください。

k.inabak.inaba 2004/05/29 08:09 いえ、やっている処理の量を考えると十分動いてるほうではないかと思います。GreenPは特に色分け方面はかなり逃げまくってますで。

k.inabak.inaba 2004/05/29 08:19 文字コードのは’a’限定で、[字句解析]で指定した正規表現を全部’|’で並べたようなNFAで判定処理みたいな感じでしょうか。もしそうならばDFA化すればほとんどtrieみたいなオートマトンに変換されそうなので、結構高速化するかも。何ともわかりませんが…

ytqwertyytqwerty 2004/05/29 15:54 trie…(また知らない言葉だ)…木構造の事ですか。はい。おっしゃる通りです。暇を見てDFAも勉強しなければ…

 | 
カレンダー
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 02 | 03 |