各種テキストエディタのデータ構造と処理を邪推する
私はついさっき*1知りました。
触れ込みは以下の通り。
小さいメモリ（50MB以下）で大規模テキストファイル（300GB、2,000億行）を編集できる世界唯一の超巨大テキストエディター
http://www.szkwjp.com/index.html
興味深いのは他のエディタとの比較。
この比較文を元に、それぞれのエディタのデータ構造を想像して楽しんでみます。
比較文が 2008 年と結構古いので、現在のバージョンとは異なる可能性があります。参考程度ということで。
鈴川エディタ
なぜ、50MB 以下のメモリで 300GB のテキストファイルが読み込めるのか。その種明かしは、オリジナルのファイルを 2MB 程度の作業用ファイルに分割し、それらを操作しているためだと思われます。
これなら 300GB のファイルを開く際に、最初の 2MB を作業用ファイルに保存しそれを読み込み、後は裏で作業用ファイル作成を継続すれば、一瞬で開けそう。
多分 300GB をスクロールしてシークすると、300GB の作業ファイルが作成されるはずで、ディスクの空きがない場合には開けないのではないかという疑惑が持たれます。もし、ディスクが枯渇する前に作業用ファイルを優先度が低いものから削除するという実装になっているなら、なかなかのもの。
E
248GB 以上、21 億行が読み込める有名エディタ。おそらく EmEditor でしょう。
このテキストエディターの改行時間は行数は問題にせずファイルサイズだけでテストすると、4GB → 5秒、10GB → 20秒、20GB → 3分、100GB → 16分でした。サイズと行数でテストすると、（2.1GB、1億行） → 25秒、（4.3GB、2億行） → 4分、（11GB、5億行） → 14分、（22GB、10億行） → 25分、（44GB、20億行） → 53分、という結果でした。これで、自ら謳うファイルサイズと行数を編集可能というにはだいぶ無理があります。後者の改行テストでは、改行時間は読み込み時間より長くかかります。
タスクマネージャによると、使用メモリは460MB前後、物理メモリは92〜98％、CPU使用率は10％前後でした。
これだけのサイズ（44GB）のファイルを編集できるということは、メモリに全部読み込むのではなく、何らかの方法で部分的に読み込んでいるのだと思います。
- 2.1GB、1 億行のテキストファイルに改行を挿入: 25 秒
- 4.3GB、2 億行のテキストファイルに改行を挿入: 4 分
- 11GB、5 億行のテキストファイルに改行を挿入: 14 分
- 22GB、10 億行のテキストファイルに改行を挿入: 25 分
- 44GB、20 億行のテキストファイルに改行を挿入: 53 分
部分的に読み込んでいるにも関わらず、行数が増えると処理時間も増えています。見たところ O(n) です。
他のエディタと比較して、1 億行のファイルで 25 秒かかるのは、何か行数に関わる状態管理を行なっている可能性が高いです。行数を数え上げているとか、強調構文をパースしなおしているとか、エディタコンポーネントが足を引っ張っているとか、そんなところでしょうか。
M
2GB、20 億行が読み込める有名エディタ。おそらく MIFES でしょう。
6億行の改行だけのテキストファイル（1.2GB）ではメモリ不足になります。5億行の改行だけのテキストファイル（1GB）では、改行時間は一瞬間です。サクサクと操作できます。このとき使用メモリは1430MBでした。メモリを3GBに増量すれば、自ら謳うファイルサイズと行数のテキストファイルを編集することができるかもしれません。
おそらくファイル全体をメモリに読み込むのでしょう。1GB のファイルを読み込んで、1.43GB のメモリ使用量は、優秀なのかそうでないのかよくわかりません。約 1.5 倍というのが、ギャップバッファっぽい感じがします。
H
4GB、1000 万行が読み込める有名エディタ。おそらく秀丸でしょう。
扱うことができるファイルサイズはかなり大きいのですが、扱うことができる行数がかなり小さいのが特徴です。ファイルサイズが4GBに近くなると、改行時間は数秒かかります。2GB以下ならば、1,000万行近くでもサクサクと操作できます。
扱える行数が 1000 万行というのは、あえて制限しているような感じがします。秀丸は一行の文字列が長いと極端に動作が遅くなるので、行データは vector で保持しているような気がします。1000 万行にあえて制限するのは、O(n) の処理が足を引っ張って、まともに編集できなくなるため、でしょうか。
P
1.6GB、8000 万行が読み込めたエディタ。おそらく Peggy ではないかと。
左の性能は、メモリいっぱいまで読みこんだ場合です。もう少しメモリを増量するか、ファイルサイズと行数を減らすと、サクサクと操作できるようです。ヘルプに関しては、日本のテキストエディターでは一番立派です。
評価は 8 GB を搭載している PC で行われているので、それで 1.6GB までしか読み込めないのは、メモリ効率がわるいのではないか、と推測されます。しかし、MIFES の評価に「メモリを3GBに増量すれば」とあるので、評価環境は実は 8GB もメモリが搭載されていない可能性もあり、なんだかよくわかりません。
もし極端にメモリ効率が悪いということであれば、内部文字コードが独自形式（UCS に付加情報を持たせる、あるいは UCS + オリジナル文字コード、ひょっとすると TRON コードなど）の可能性があります。
動作面では、1GB オーバーのファイルでサクサク動くのであれば、優秀だと思います。
500MB 〜 1GB、数千万行クラス
このクラスはまともなテキストエディターといえます。サクサクとキー操作できるのですが、メモリ不足で扱うことができるファイルサイズと行数がこの程度にとどまっています。
100 〜 500MB、100万行 〜数千万行クラス
ほとんどのテキストエディターはこのクラスです。
開くファイルサイズよりだいぶ大きいメモリを使うのが特徴です。100MBのファイルで250MBぐらいメモリを消費するものがあります。このクラスには注目すべきテキストエディターもいくつかあります。玉石混淆です。
注目すべきテキストエディタは、ずばり Apsaly ですか？文章が古いので Sublime Text ということはなさそう。
*1:この記事は下書きで 4 ヶ月寝かせておいたので、正確には今年初め
