技術文章＞テキストエディタ実装技術その２

テキストエディタ用バッファの各種データ構造とその評価 (2)

Nobuhide Tsuda

5-Sep-2009

概要

テキストエディタ用バッファの概要にさらっと触れ、階層的データ構造およびピーステーブル（piece table）について述べる。
それらを筆者が実装したクラスについてパフォーマンス計測を行った結果を報告する。

基本事項
階層的データ構造
ピーステーブル
まとめ

基本事項

バッファとは1次元的に並んだ文字を管理するクラスである。
シーケンシャルアクセス、編集（削除・挿入）機能が必須（文字インデックス、行番号によるランダムアクセスもできた方がよい）
必要充分な機能・高信頼性・高速性・メモリ効率の良さ・拡張性が求められる
下図の様なSTL互換の C++インタフェースを定義することができる
シーケンスデータのデータ構造はクラスにより様々で、それによりバッファクラスの特徴・性能が決まる。

全置換の例：

    void replace_all(CEditBuffer &eb, const string &pat, const string &rep)
    {
        CEditBuffer::char_iterator itr = eb.char_begin();
        CEditBuffer::char_iterator eitr = eb.char_end();
        while( (itr = find_string(itr, eitr, pat)) != eitr ) {    //  パターンを検索
            itr = eb.erase(itr, itr + pat.size());  //  パターンを削除
            itr = eb.insert(itr, rep);              //  置換文字列を挿入
            ++itr;
            eitr = eb.char_end();
        }
    }

gap_vector<char> は驚くほど高性能（速度、メモリ効率）
ただし、巨大な文書に対しては問題が無くはない

課題

巨大ファイルの取り扱い

ファイルサイズが大きく、読み込みに時間がかかったり、メモリに全部を読み込むことができない場合がある。
前者の対策として ViVi 2.x では遅延リード機能を実装しているが、ファイル末尾から読み込むことが出来ないなどの問題がある。

仮想メモリのように主記憶に読み込めないデータは外部記憶装置上に置き、クラス外からはシームレスに利用できるのが望ましい。
仮想バッファ？

文字コード

内部コードをUnicodeなどに固定した場合、ファイル読込時の変換に時間的空間的コストがかる
かと言って参照のたびに変換を行うのは処理時間的に問題かもしれない
このような場合、変換結果をキャッシュするのが定跡だが、gap_vector との相性はよくない。

行単位情報の取り扱い

データ構造が行単位でない場合、行数カウント処理が別途必要になる。
編集フラグなどの行単位情報の管理も必要
gap_vector<char> を使用する場合は、行フラグ情報を別途保持するか、シーケンスデータに埋め込む必要がある。
後者の場合、文字オフセットを指標とするランダムアクセスが不可能になるし、シーケンシャルアクセス速度も低下する。

階層的データ構造

階層的データ構造とは

シーケンスなデータを取り扱うデータ構造は多種類あり、一長一短がある
それらを下図の様に階層的（再帰的？）に配置することで、異なった特徴を持つデータ構造を作ることができる

たとえば、array（固定長配列）はシーケンスデータを取り扱うのに最も自然なデータ構造だが、サイズ固定であるためにバッファに用いるには難がある。
しかし、vector<array<char>> のように、可変個の array を vector で管理してやれば、固定長というデメリットが致命的なものではなくなる。
ただし、管理コストが新たに発生するので、管理・被管理データ構造を慎重に選ぶ必要がある。

シーケンスデータのための基本データ構造

データ構造	概要	ランダムアクセス	挿入削除
array	固定長配列	O(1)	O(N)、サイズを超えるデータを格納できない
vector	可変長配列	O(1)	O(N)
gap_vector	中央に gap を持つ可変長配列	O(1)	局所的であれば O(1)
list	双方向リスト	O(N)	O(1)
list with cache	キャッシュ付き双方向リスト	局所的であれば O(1)	O(1)
BST	二分探索木（バランス二分木）	O(logN)	O(logN)
スパン	データ領域を所有しない配列的なもの	O(1)	直接的な挿入削除はできない

各種データ構造

vector類をvector類で管理する組み合わせについて、考察とパフォーマンス測定を行う。
測定項目は以下の項目とする。

バッファ構築時間
シーケンシャルアクセス＋1文字削除時間・使用メモリ量
シーケンシャルアクセス＋1文字挿入時間・使用メモリ量

vector<shared_ptr<array<char>>>

最も基本的な組み合わせ。
STL には array が無いので、reserve であらかじめ領域を確保しサイズを固定にした vector<char> を代わりに用いる。
array のサイズは 32KB としてみる。array サイズを変えた場合の計測は余裕があれば行う。
文字データが array サイズ以上になった場合、可能なら前後の array に送る。そうでない場合は新たに array を作成する。

編集コストおよびブロック分割時コストは、ブロックサイズを B とすれば O(B) である。
ブロックサイズは小さいほどよいが、あまり小さいと管理コストが増大する。

gap_vector<shared_ptr<array<char>>>

管理クラスを vector から gap_vector に変えたもの。
ブロックの挿入削除が局所的かつ頻繁であれば、パフォーマンスの向上が期待できる。

vector<shared_ptr<gap_vector<char>>>

ブロックのデータ構造を array → 固定サイズ gap_vector に変えたもの。
ブロック先頭・途中での挿入・削除が高速化される分、vector<array<char>> に比べてパフォーマンスが向上すると期待できる。
固定サイズにするのは、主記憶が足りなくなり外部記憶装置にスワップアウトする場合のスワップ領域管理処理の簡略化を図るため。

主記憶の使用メモリ量を節約するために、ブロックサイズは固定ではなく上限値を持つようににするのも一案である。
外部記憶の一時的に保存する場合は常に上限サイズ分の容量があるとみなせば、スワップ領域管理は固定ブロックサイズの処理で充分となる。

gap_vector<shared_ptr<gap_vector<char>>>

管理クラスを vector から gap_vector に変えたもの。
ブロックの挿入削除が局所的かつ頻繁であれば、パフォーマンスの向上が期待できる。

実装

ポリシーを用いたクラスを定義し、具体的なコンテナクラスはテンプレートパラメータで与える。
ブロックの移動を高速化するため、ブロックへの boost::shared_ptr<block_t> をコンテナに格納するようにした。

template<typename CharType,
    template<typename CharType, class Allocator = std::allocator<CharType>> class _Container,
    int BLOCK_SIZE = DEF_BLOCK_SIZE>
struct Block
{
    typedef _Container<CharType> Container;
    typedef typename Container::iterator ContainerIterator;

    size_t  m_line_size;        //  ブロックに含まれる改行数（\r\n はひとつと数える）
    Container   m_buffer;
    .....
};
template<typename CharType,
    //  ブロックを管理するコンテナクラス
    template<typename CharType, class Allocator = std::allocator<CharType>> class _BlockContainer,
    //  ブロック内の文字を管理するコンテナクラス
    template<typename CharType, class Allocator = std::allocator<CharType>> class _DataContainer,
    int BLOCK_SIZE = DEF_BLOCK_SIZE>
class edit_buffer_blocks
{
    typedef Block<CharType, _DataContainer, BLOCK_SIZE> block_t;
    typedef typename block_t::Container Container;
    typedef typename Container::iterator ContainerIterator;

    typedef std::gap_vector<boost::shared_ptr<block_t>> Blocks;
    typedef typename Blocks::iterator BlocksIterator;
    typedef typename Blocks::const_iterator BlocksConstIterator;
private:
    Blocks  m_blocks;
    size_t  m_char_size;
    size_t  m_line_size;
    .....
};

パフォーマンス計測

ブロック要素数を32*1024としてパフォーマンスを計測した。

vector が gap_vector より高速なのは、データタイプが基本型の場合の最適化が利いているため。
ブロックを管理するコンテナの性能よりも文字を管理するコンテナの性能が支配的。

10万行 = 100*10万 = 1000万バイトなので、10M/32K = 320ブロック。
ブロック数が少ないので管理クラスが vector と gap_vector でパフォーマンスの差がでない。

下図はブロックサイズを 32K から 1K に変更してみたもの。
gap_vector の場合は、処理速度がほとんどブロックサイズに依存しないが、 vector の場合はブロックサイズが小さくなればデータ移動量が減り高速になる。
ブロックサイズ：256バイトで、gap_vector とほぼ同じ処理時間になった。

本稿の削除処理時間計測ではブロック個数が増減しないため、ブロック数が増加する挿入処理で時間計測を行ってみた。
が、ブロック増加に伴う

まとめ

文字コンテナを別のコンテナで管理することで新たなデータ構造を構築できる。

ブロック（固定長配列類）を用いたデータ構造は単純で、gap_vector に比べてもそれほどパフォーマンスを損なわずに巨大サイズファイルにも対応可能である。

piece table

piece table とは

シーケンスデータを格納するのに最も自然なデータ構造は配列類だが、固定長・可変長配列にテキストを格納した場合、末尾以外での編集操作（挿入・削除）にデータの移動処理を伴うため、 O(N) の時間を要する。

速度低下を防ぐにはデータの移動を行わないようにするとよい。

スパンをコンテナで管理することでシーケンスデータを表現する。
スパンをピース（piece）とよび、ピースを管理するコンテナをピーステーブル（piece table）と呼ぶ。

ピースの具体的な実装方法としては、以下のようなものが考えられる。

（ピース先頭アドレス、ピースに含まれる文字数）
（ピース先頭アドレス、ピース最後の次のアドレス）、
（ピースを含むバッファ情報、バッファ内のピース先頭オフセット、ピースに含まれる文字数）

編集処理：

ピース途中の文字を削除する場合は、ピースを分割する。

[Delete] を連続して押した場合の様に、直前に削除した範囲の次の文字を削除する場合は、ピースが保持するスパン先頭情報を修正するだけでよい（文字数情報を保持している場合はデクリメントも必要）。

ピース途中に文字を挿入する場合は、ピースを分割し、間に新規ピースを挿入する。
挿入された文字はバッファに追加され、新規ピースはそれを指す。

続けて文字を挿入する場合、挿入された文字はバッファに追加され、直前に挿入したピースを修正する（ピースに含まれる文字数を増加させる or end ポインタを更新する）

特徴・考察：

バッファ内の文字が移動されることも、削除されることも無い（immutable）
ピースを vector, list 類で管理する場合、ランダムアクセスは O(P) （P はピース数）
ピースを BST で管理すれば、ランダムアクセスは O(logP)
配列に比べて挿入・削除は高速だが、同じ文字数の置換はむしろ処理時間がかかる
小さいピースが大量にある場合、メモリ効率が悪化する。また、シーケンシャルアクセス速度が低下する
　　→複数のピースをひとつにまとめることでメモリ使用量を減らせる場合がある
バッファの未参照領域が発生するが、undo/redo 用に再利用できる
バッファはひとつの連続した領域である必要はない。複数の固定長ブロックとすることで仮想バッファに対応できそう
ファイルから読み込む場合、メモリマップトファイルなどを使って、ファイルバッファを直接参照することも可能
　　（ただし、文字コードが内部文字コードと異なる場合は問題となる）
バッファの文字コードを統一せず、イテレータがピース経由でアクセスするときにコード変換を行うことも可能
バッファが immutable なので、クリップボードへのコピー時にテキストを直接コピーせず、コピー範囲のピース情報を保持しておき、ペースト時にバッファを参照することでコピペすることが可能。
ただし、undo を行った場合に undo した情報をバッファから削除するようにした場合はその限りではない。

実装

内部バッファ文字コード＝インタフェース文字コードとして実装した。
ピースは２つのポインタで構成するようにした（8byte）。
ピースを管理するコンテナはポリシーで指定可能にした。

template<typename CharType,
    //  ピースを管理するコンテナ
    template<typename CharType, class Allocator = std::allocator<CharType>> class _PieceContainer>
class edit_buffer_pt
{
    .....
};

パフォーマンス計測

piece_table<char> のパフォーマンス計測を行い, gap_vector<shared_ptr<gap_vector<char>>>, gap_vector<char> との比較を行う。
測定項目は以下の4項目とする。（バッファ構築時メモリ使用量には差が無いので省略した）

バッファ構築時間
シーケンシャルアクセス時間（バッファ構築直後＆7文字に1文字置換処理後）
シーケンシャルアクセス＋1文字削除時間・使用メモリ量
シーケンシャルアクセス＋1文字挿入時間・使用メモリ量

シーケンシャルアクセス処理速度は上図のような測定結果となった。
gap_vector<char> は編集を行っても、1文字あたりのシーケンシャルアクセス速度が変化することはないが、 piece table の場合は、ピースに含まれる文字数が減り、ピース個数が増えるので、イテレータの処理が重くなる。

100バイト＊10万行 = 1000万文字なので、7文字に1文字削除した場合のピース数は 1000万/7 = 142万ピースとなる。
現在の実装では1ピースのメモリ消費量は8バイトなので、142万*8 = 1142万バイトもの容量を消費することになる。これは元のバッファ容量の 8/7 のサイズである。

まとめ

編集処理は、gap_vector<char> 並に高速である。編集箇所が非局所的であってもおｋ。
小ピースが大量にできない限り、メモリ効率はよい。
大量の小ピースがメモリを消費する問題は、undo のための情報を保持する場合にも同様であり、致命的な問題ではないと考える。

ピーステーブルはテキストを格納するバッファをスワップアウトする機能を組み込むことで仮想バッファ化も可能だと考える。

まとめ

ViVi 3.x のバッファデータ構造として何を採用するかを決めるために、バッファクラスのインタフェースを決め、各種データ構造を実装し、パフォーマンスを計測したみた。

テキストをメモリにすべて読み込める場合には gap_vector<char> はテキストエディタ用バッファのデータ構造としてメモリ効率・処理速度・実装容易性の点で、もっとも優れたデータ構造と言える。
メモリにすべて読み込めないような巨大テキストの場合、ピーステーブルなどの階層的データ構造を採用する必要がある。

ViVi 3.x では、内部 Unicode 化・巨大ファイル対応を 3.03/04 以降としたので、それまでは gap_vector<char> を採用するつもりである。
クラスインタフェースを標準化していれば、データ構造を変更しても、それを利用する側のソース修正はほとんど無いはずである。

参考文献

Data Structures for Text Sequences (1998) by Charles Crowley