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

概要

テキストエディタのためのバッファの各種データ構造について述べ、
それらを筆者がC++で STLに準じたインタフェースを持つテンプレートクラスとして実装したものについて、
パフォーマンス（処理速度、使用メモリ量）計測を行った結果を報告する。
筆者が実際にテキストエディタを実装する場合にどのデータ構造がよいか、という視点で評価を行う。

目次：

1. はじめに
2. バッファに要求される機能・性能
3. バッファクラスのインタフェース
4. パフォーマンス計測
5. 各種データ構造
6. gap_vector<wchar_t> VS. list<wstring>
7. gap_vector<wstring>
8. 終わりに
9. 参考文献

本稿では（筆者が知っている）バッファの各種データ構造・実装について述べ、VC9 で実装したクラスのパフォーマンス計測を行い、それらの評価を行う。

バッファに要求される機能・性能

class CLineMgr
{
    .....
public:
    bool getLineText(int lineNum, CString&);    //  指定行番号（1..*）の文字列を CString に返す
    cchar *getLineText(int lineNum, int &length);    //  指定行番号（1..*）の文字列を返す
    .....
};

template<trypename CharType>
class CEditBuffer
{
    gap_vector<CharType>    m_buffer;
    .....
public:
    gap_vector<CharType>::const_iterator begin() const { return m_buffer.begin(); }
    gap_vector<CharType>::const_iterator end() const { return m_buffer.end(); }
    .....
}

    CEditBuffer eb;
    ....
    int sum = std::accumulate(eb.begin(), eb.end(), 0);     //  全文字コードの合計計算
    CEditBuffer::iterator itr = std::find(eb.begin(), eb.end(), 'X');  // 文字 'X' を検索
    .....

struct STextPos
{
    int m_line;    //  行番号（1..*）
    int m_offset;  // 行内オフセット（0..*）
};
class CLineMgr
{
    .....
public:
    bool    insert(const STextPos&, const CString&);
    bool    erase(const STextPos&, const STextPos&);
    ....
};

　第二の機会の法則（Low of Second Chance）：正しく理解するために最も大切なのは、インタフェースである。
　他のことは後でも直せる。インタフェースを間違えると、それを直す次の機会は無い。
　[Sutter04]（訳文は C++ Coding Standards より）

　バッファの実際の作りをプログラムの他の部分からできるだけ切り離すことが大切である。
　そのようにしておけば、下位のバッファ処理ルーチンを多少変更するだけのことで、
　与えられた基本方針のもとで能率向上をはかることができるのみならず、
　方針自体をすっかり変更することさえ可能である。

※ Data Structures for Text Sequences (1995) より

The C Interface

• Sequence Empty( );
• ReturnCode Insert( Sequence *sequence, Position position, Item ch );
• ReturnCode Delete( Sequence *sequence, Position position );
• Item ItemAt( Sequence *sequence, Position position );
• …

※ Data Structures for Text Sequences (1995) より

The C++ Interface

データ構造によらず、インタフェースを共通化したクラスを実装
インタフェースは原則 STL のコンテナクラスに準じたものとする。

利点：

• インタフェースの形式をどうするか悩まなくて済む
• STL/boost で実績のある方式であり、安心感がある
• STL/boost のアルゴリズムを直接的に利用できる
• バッファクラスのコンポーネント化が達成される
  ※注意：データ構造ごとに特性があるので、完全に置き換え可能になるわけではない。

欠点：

• データ構造によっては若干効率が犠牲になる場合がある
• 編集操作でイテレータが無効になる（バッファを利用するクラスがイテレータを保持する場合は注意）
• 絶縁方法がよくわからない？
• イテレータに慣れてないと分かりづらい？

以下に本稿で計測に用いたクラスのインタフェースを示す。

//  文字イテレータ
template<typename CharType>
class _edit_buffer_char_iterator : public std::iterator<std::bidirectional_iterator_tag, CharType>
{
    .....                                       //  文字イテレータ用データ
public:
    _edit_buffer_char_iterator(...);
    _edit_buffer_char_iterator(const _edit_buffer_char_iterator&);        //  コピーコンストラクタ
    _edit_buffer_char_iterator &operator=(const _edit_buffer_char_iterator &x);    //  代入演算子
    CharType &operator*();                      //  dereference
    _edit_buffer_char_iterator &operator++();                //  インクリメント
    _edit_buffer_char_iterator &operator--();                //  デクリメント
    bool operator==(const _edit_buffer_char_iterator &x);    //  等値比較
    bool operator!=(const _edit_buffer_char_iterator &x);    //  等値比較
};
//  行イテレータ
template<typename CharType>
class _edit_buffer_line_iterator : public std::iterator<std::bidirectional_iterator_tag, CharType>
{
    .....                                       //  行イテレータ用データ
public:
    _edit_buffer_line_iterator(...);
    _edit_buffer_line_iterator(const _edit_buffer_line_iterator&);
    .....
    _edit_buffer_char_iterator begin();    //  行の最初の文字へのイテレータを返す
    _edit_buffer_char_iterator end();      //  行の最後の文字の次へのイテレータを返す
};
template<typename CharType>
class edit_buffer
{
    //  Container   m_buffer;
public:
    edit_buffer();                           //  デフォルトコンストラクタ
    edit_buffer(const edit_buffer &);        //  コピーコンストラクタ
    ~edit_buffer();                          //  デストラクタ

    edit_buffer &operator=(const edit_buffer &);    //  代入演算子
public:
    typedef _edit_buffer_char_iterator char_iterator;
    char_iterator char_begin();    //  最初の文字へのイテレータを返す
    char_iterator char_end();      //  最後の文字の次へのイテレータを返す
public:
    typedef _edit_buffer_line_iterator line_iterator;
    line_iterator line_begin();   //  最初の行へのイテレータを返す
    line_iterator line_end();     //  最終行の次へのイテレータを返す
public:
    bool    empty() const;        //  バッファが空か？
    size_t  char_size() const;    //  文字数（0..*）を返す
    size_t  line_size() const;    //  行数（1..*）を返す
public:
    void    clear();              //  バッファ初期化
    template<typename InputIterator>
    void    assign(InputIterator first, InputIterator last);    //  バッファへ代入
    char_iterator   erase(char_iterator);               //  1文字削除、次の文字へのイテレータを返す
    char_iterator   insert(char_iterator, CharType);    //  1文字挿入、挿入文字へのイテレータを返す
};

基本的に vector 等と同じインタフェース
文字イテレータ、行イテレータであることを強調するために、iterator → char_iterator, line_iterator とした。

insert() が挿入した文字へのイテレータを返すのは STL 互換のため。
イテレータを文字カーソルと考えれば、挿入文字の次を返す方が自然かもしれない。
　　　　→ 別メソッドを導入する？

上記はパフォーマンス計測を行うための最小限のインタフェースであり、 実際にエディタを実装する場合は、範囲削除・文字列挿入・置換・undo/redo などのメソッドを追加した方がいいかもしれない。

以下に、上記クラスインタフェースの使用例を示しておく。

ファイル読み込み：

BOOL CMyEditorDoc::OnOpenDocument(LPCTSTR lpszPathName)
{
    vector<char> buf;
    vector<wchar_t> wbuf;
    lpszPathName をオープンし、buf に読み込む。
    文字コードを Unicode に変換し、buf -> wbuf 転送。
    CEditEngine *editEngine = getEditEngine();
    editEngine->assign(wbuf.begin(), wbuf.end());
}

画面描画：

void CMyEditorView::OnDraw(CDC* pDC)
{
    const CEditEngine *editEngine = getEditEngine();
    int y = 0;  //  表示座標
    for(CEditEngine::line_iterator li = 画面最上行, liend = editEngine->line_end();
        y が画面内 && li != liend;
        ++li, y += 行高)
    {
        1行表示(pDC, y, li);
    }
}
void CMyEditorView::1行表示(CDC* pDC, int y, const CEditEngine::line_iterator &li)
{
    int x = 0;
    CDrawTokenizer tn(li->begin(), li->end());
    for(CDrawTokenizer::iterator itr = tn.begin(), iend = tn.end();
        xが画面右を越えていない && itr != iend; ++itr)
    {
        *itr を表示;
        x += 表示幅(*itr);
    }
}

ちなみに これ は昔書いたコード。

1文字挿入、Delete

class CMyEditorView {
    CEditEngine::char_iterator m_cursor;   //  カーソル位置
    .....
};
void CMyEditorView::OnChar(UINT nChar, UINT nRepCnt, UINT nFlags)
{
    CEditEngine *editEngine = getEditEngine();
    m_cursor = editEngine->insert(m_cursor, nChar);     //  カーソル位置文字挿入
    ++m_cursor;         //  カーソル位置補正
    Invalidate();       //  画面無効化
}
void CMyEditorView::OnEditDelete()
{
    CEditEngine *editEngine = getEditEngine();
    m_cursor = editEngine->erase(m_cursor);         //  カーソル位置文字消去
    Invalidate();       //  画面無効化
}

Rule 2.  Measure.  Don't tune for speed until you've measured,
	and even then don't unless one part of the code overwhelms the rest.
	（計測すべし。計測するまでは速度のための調整をしてはならない。
	コードの一部が残りを圧倒しないのであれば、なおさらである。）

The number of ItemAt calls that were sequencial (one way from the last ItemAt) was
 always above 97% and usually above 99%. 
The number of ItemAt that were within 20 items of the previous ItemAt was always over 99%. 
The average number of characters from one ItemAt to the next was typically around 2
 but sometimes would go up to as high as 10 or 15.
Overall these experiments verify that the position of ItemAt calls are extremely localized.

※ Data Structures for Text Sequences より

処理時間が問題となるのは大域的な編集処理の場合である。
位置による処理時間の偏りを避けるため、シーケンシャルアクセスを行いながら削除・挿入を行う時間を計測する。

計測プログラム

文字コードは Unicode とする。

//	バッファ構築時間計測
template< typename TEditBuffer, typename InputIterator >
void measure_construct(InputIterator first, InputIterator last, int unit = 10000)
{
    TEditBuffer eb;
    InputIterator e = first;
    const int beg = 2;
    const int step = 2;
    for(int i = beg; i <= 100; i += step) {
        cout << i * unit << " ";
        e = find_nth(e, last, '\n', unit * step);
        boost::timer tm;
        eb.assign(first, e);    //  構築
        cout << tm.elapsed() << "\n";
    }
}

//  バッファ構築時使用メモリ計測
template< typename TEditBuffer, typename InputIterator >
void measure_construct_memory(InputIterator first, InputIterator last, int unit = 10000)
{
    TEditBuffer eb;
    size_t mem0 = get_used_memory_size();
    InputIterator e = first;
    const int beg = 2;
    const int step = 2;
    for(int i = beg; i <= 100; i += step) {
        cout << i * unit << " ";
        e = find_nth(e, last, '\n', unit * step);
        eb.assign(first, e);    //  構築
        size_t mem = get_used_memory_size();
        cout << mem - mem0 << "\n";
    }
}

//	シーケンシャルアクセス時間計測
template< typename TEditBuffer, typename InputIterator >
void measure_seq_access(InputIterator first, InputIterator last, int unit = 10000)
{
    TEditBuffer eb;
    eb.assign(first, last); //  構築
    const int beg = 2;
    const int step = 2;
    for(int i = beg; i <= 100; i += step) {
        int N = i * unit;
        cout << N << " ";
        boost::timer tm;
        const int loop = 100;
        for(int j = 0; j < loop; ++j) {
            int sum = 0;
            TEditBuffer::char_iterator itr = eb.char_begin();
            TEditBuffer::char_iterator iend = eb.char_end();
            for(int k = 0; itr != iend && k < N; ++itr, ++k)
                sum += *itr;
        }
        cout << tm.elapsed() / loop * 1000 << "\n";     //  1000 for msec
    }
}

//	シーケンシャルアクセス＋１文字削除時間計測
//	6文字進めて１文字削除を繰り返す
template< typename TEditBuffer, typename InputIterator >
void measure_seq_erase(InputIterator first, InputIterator last, int unit = 1000)
{
    TEditBuffer eb;
    InputIterator e = first;
    const int beg = 2;
    const int step = 2;
    for(int i = beg; i <= 100; i += step) {
        cout << i * unit << " ";
        e = find_nth(e, last, '\n', unit * step);
        eb.assign(first, e);    //  構築
        boost::timer tm;
        TEditBuffer::char_iterator itr = eb.char_begin();
        TEditBuffer::char_iterator iend = eb.char_end();
        while( itr != iend ) {
            for(int i = 0; i < 6 && itr != iend; ++i)
                ++itr;
            if( itr == iend ) break;
            itr = eb.erase(itr);        //  １文字削除
            iend = eb.char_end();       //  念のため
        }
        cout << tm.elapsed() << "\n";
    }
}

//	シーケンシャルアクセス＋１文字挿入時間計測
//	7文字進めて１文字（'#'）挿入を繰り返す
template< typename TEditBuffer, typename InputIterator >
void measure_seq_insert(InputIterator first, InputIterator last, int unit = 1000)
{
    TEditBuffer eb;
    InputIterator e = first;
    const int beg = 2;
    const int step = 2;
    for(int i = beg; i <= 100; i += step) {
        cout << i * unit << " ";
        e = find_nth(e, last, '\n', unit * step);
        eb.assign(first, e);    //  構築
        boost::timer tm;
        TEditBuffer::char_iterator itr = eb.char_begin();
        TEditBuffer::char_iterator iend = eb.char_end();
        while( itr != iend ) {
            for(int i = 0; i < 7 && itr != iend; ++i)
                ++itr;
            if( itr == iend ) break;
            itr = eb.insert(itr, '#');        //  １文字挿入
            ++itr;
            iend = eb.char_end();
        }
        cout << tm.elapsed() << "\n";
    }
}

C2D（ウルフデール） 3Ghz, 4GMem, WinXP, VC9

各種データ構造

gap_vector<wchar_t> VS. list<wstring>

ランダムアクセスは O(1) だが、編集（挿入・削除・置換）処理は O(N)。
一括構築（assign）は高速で無駄なメモリ領域を発生させない。
欠点：特に大量のテキストがあるとき、先頭付近での挿入・削除は大量のデータの移動を伴うため 非常に遅い。 （gap_vector 参照）
末尾への挿入は O(1) だが、容量が足りなくなった場合、メモリをリアロケートし、データをコピーする必要がある。
同一サイズの置換はデータを書き換えるだけなので高速

gap_vector<wchar_t>

テキストエディタでは編集箇所が局所化されていることを利用したデータ構造。 （gap_vector 参照）
vector に比べ、安定的に優れたパフォーマンスを発揮する。
ランダムアクセスは O(1) で、編集（挿入・削除・置換）処理もおおむね O(1)
list に比べ、使用メモリ量が少ない。
編集処理のたびに行数更新処理が必要。コードが少し煩雑になる？
処理を行単位に記述したい場合、そのつど行の切り分け処理が必要になる。
　　　　→ 行イテレータを実装しておけば おｋ

限界：メモリに入りきらないデータを取り扱うことは出来ない

list<wstring>

行長が膨大になることは稀なので、1行を string (== vector<char>) で管理し、 行を双方向リンクで管理する。

行の挿入・削除処理は O(1) となる。
行番号を指標に行をランダムアクセスすることは出来ない（無理やり行うと O(N)）が、通常はシーケンシャルアクセスで充分。
（ランダムアクセス的にプログラムを記述したい場合、 行番号キャッシュ法 が有効）

文字イテレータオブジェクトは行イテレータをメンバ変数に持ち、インクリメント・デクリメントで境界チェックを行い、文字イテレータを更新する。

欠点：行長が長い（1行100万文字とか）と、レスポンスが悪くなる（→ ViVi 2.x デモ）。

欠点：行数が膨大な場合、無駄なメモリ（ポインタ＊２、メモリ管理のための領域）を大量に消費し、 new, delete が非常に遅くなる。
　　　　→ メモリ管理部分・処理速度に関する解決方法：boost::pool または同等機構（ViVi で採用）

テキストデータを外部記憶に置くことで、メインメモリに入りきらないファイルも編集できなくは無い。

実装

gap_vector<wchar_t>

バッファクラスは gap_vector<wchar_t> オブジェクトをメンバ変数にもつ。
（gap_vector<wchar_t> の実装は gap_vector で使った簡易的実装によるもの）

assign() は、gap_vector<wchar_t> の assign() をそのままコールする。

文字イテレータは gap_vector<wchar_t>::iterator をそのまま用いる。

編集メソッドは gap_vector<wchar_t> の編集メソッドをそのままコールする。

文字数は gap_vector<wchar_t>::size() をそのまま利用。
行数は必要になったときに数える or 行数を保持し、編集のたびに更新する。

行数カウント：

//  CRLF/CR/LF で行を区切る関数
template
InputIterator get_next_line(InputIterator itr, InputIterator end)
{
    int ch = '\0';      //  直前文字
    while( itr != end ) {
        if( ch == '\r' ) {
            if( *itr == '\n' ) ++itr;
            break;
        }
        ch = *itr;
        ++itr;
        if( ch == '\n' ) break;
    }
    return itr;
}
template<typename InputIterator>
size_t get_line_count(InputIterator itr, InputIterator end)
{
    size_t c = 0;
    while( itr != end ) {
        ++c;
        itr = get_next_line(itr, end);
    }
    return c;
}

編集時に行数更新を行う場合：

//  1文字削除時の行数更新
template<typename InputIterator>
void update_line_size_at_erase(size_t &line_size,
                                size_t char_size,
                                const InputIterator &itr,
                                const InputIterator &cibegin,
                                const InputIterator &ciend)
{
    InputIterator i2(itr);
    InputIterator iend2(ciend);
    switch( *itr ) {
    case '\n':
        //  直前が \r でなければ --行数
        if( itr == cibegin || *--i2 != '\r' && --iend2 != itr )
            --line_size;
        break;
    case '\r':
        //  バッファは \r のみ または 次が \n でなければ --行数
        if( ++i2 != ciend && *i2 != '\n' || char_size == 1 )
            --line_size;
        break;
    default:
        //  バッファは \r のみ または 最終文字でその前が改行
        if( char_size == 1 || --iend2 == itr && (*--i2 == '\n' || *i2 == '\r') )
            --line_size;
        break;
    }
}

//  1文字挿入時の行数更新
template<typename InputIterator, typename CharType>
void update_line_size_at_insert(size_t &line_size,
                                bool    empty,
                                CharType ch,
                                const InputIterator &itr,
                                const InputIterator &cibegin,
                                const InputIterator &ciend)
{
    InputIterator i2(itr);
    switch( ch ) {
    case '\n':
        //  直前が \r で無ければ（バッファが空の場合はここに含まれる） ++行数、
        //  ただし itr がバッファ末尾の場合、その前が改行でない限り ++行数 しない
        if( itr == cibegin || *--i2 != '\r' && (itr != ciend || *i2 == '\n') )
            ++line_size;
        break;
    case '\r':
        //  バッファが空 または 直後が \n で無ければ ++行数
        if( empty || itr != ciend && *itr != '\n' )
            ++line_size;
        break;
    default:
        //  バッファが空 または バッファ末尾挿入で、直前が改行の場合は ++行数
        if( empty || itr == ciend && (*--i2 == '\n' || *i2 == '\r') )
            ++line_size;
        break;
    }
}
class edit_buffer
{
    size_t  m_line_size;        //  行数
    .....
    //  itr 位置の文字を削除し、その次の文字へのイテレータを返す
    char_iterator   erase(char_iterator itr)
    {
        char_iterator ciend = char_end();
        if( itr == ciend ) return itr;
        update_line_size_at_erase(m_line_size, char_size(), itr, char_begin(), ciend);
        return char_iterator(m_buffer.erase(itr.m_itr));
    }
    //  itr 位置直前に文字を挿入し、その文字へのイテレータを返す
    char_iterator   insert(char_iterator itr, CharType ch)
    {
        update_line_size_at_insert(m_line_size, empty(), ch, itr, char_begin(), char_end());
        return char_iterator(m_buffer.insert(itr.m_itr, ch));
    }
};

list<wstring>

バッファクラスは list<wstring> オブジェクトをメンバ変数にもつ。

assign() は、行ごとに切り分け、それを push_back() で行追加を行う。

文字イテレータは list<wstring>::iterator をメンバ変数に持ち、wstring::iterator をラップする。

最初の版：

    class char_iterator : public std::iterator<std::bidirectional_iterator_tag, CharType>
    {
        typename tstring::iterator  m_itr;      //  文字イテレータ
        typename tstring::iterator  m_iend;     //  文字イテレータ
        typename ContainerIterator  m_litr;     //  行イテレータ
        edit_buffer_li_str  *m_p;               //  親コンテナへのイテレータ
        .....
    };

パフォーマンスチューニング版：

    class char_iterator : public std::iterator<std::bidirectional_iterator_tag, CharType>
    {
        const CharType *m_itr;      //  文字イテレータ
        const CharType *m_iend;     //  最終文字イテレータ
        typename ContainerIterator  m_litr;     //  行イテレータ
        edit_buffer_li_str  *m_p;               //  親コンテナへのイテレータ
        .....
    };

編集メソッドは基本的に wstring の編集メソッドをコールするが、改行を意識した処理が必要となる。

文字数情報はメンバ変数に保持し、編集メソッドで更新する。
行数は list<wstring>::size() を利用する。

計測結果

バッファ構築時間・消費メモリ

下図に、Unicode (98文字 + CRLF) * 2千〜100万行のシーケンシャルデータでバッファを構築する時間、消費メモリ量測定結果を示す（測定プログラムは ここ を参照）。

構築時間は gap_vector<wchar_t> が list<wstring> より約10倍高速、 消費メモリ量は後者が前者より約50%多いメモリを消費
（10万行（== 1千万文字）構築時消費メモリ 前者：20,135,936 byte、後者：29,691,904 byte）、
という結果になった。

list<wstring> が遅く、メモリを浪費する原因：

• list ノード、wstring のためのメモリアロケートに時間がかかる。
  （C++は大量回数のメモリアロケートが遅い。ついでに言うと破棄も遅い）

シーケンシャルアクセス

（測定プログラムは ここ を参照）

測定結果は上図の通り。
当初、list::iterator の wstring::iterator を用いていた版は、gap_vector よりも倍程度遅かったが、 ポインターを用いるようパフォーマンスチューニングした版は、逆にgap_vector よりも倍以上速くなった。

シーケンシャルアクセスは、抽象的なポインタを進める処理と、 そのブロックが終了した時に次のブロックに進む処理の２つから成る。
gap_vector は後者の処理は必要ないが、現在の版では抽象的なポインタを進めるとき、 バッファの終わりとギャップ位置かどうかの判定を行っており、それが速度低下の原因と考えられる。

削除処理

下図に、Unicode (98文字 + CRLF) * 2千〜10万行のデータについて、先頭から6文字進めて1文字削除をバッファ最後まで繰り返した場合の測定結果を示す。
gap_vector<wchar_t>, list<wstring> の処理速度は大差なく、どちらも約0.25秒/10万行であった。

次に削除処理自体の処理速度を見るために、先頭から5文字進めて2文字削除をバッファ最後まで繰り返した場合を測定した結果を以下に示す。
gap_vector<wchar_t> は1文字削除とほとんど処理時間が変わらないが、list<wstring> は約2倍の処理時間を要した。

挿入処理

下図に、Unicode (98文字 + CRLF) * 2千〜10万行のデータについて、先頭から7文字進めて '#' を1文字挿入をバッファ最後まで繰り返した場合の測定結果を示す。

結論

単純な list<wstring> では、どう贔屓目に見ても gap_vector<wchar_t> の性能（処理速度・メモリ効率）にはかなわないように見える。

それでもやっぱり vi が好き！

gap_vector<wstring>

class edit_buffer
{
    .....
    template<typename InputIterator>
    void    assign(InputIterator first, InputIterator last)
    {
        m_size = last - first;
        m_buffer.clear();
        while( first != last ) {
            InputIterator next = get_next_line(first, last);
            m_buffer.push_back(tstring(first, next)tr);
            first = next;
        }
    }
    .....
}

class edit_buffer
{
    .....
    template<typename InputIterator>
    void    assign(InputIterator first, InputIterator last)
    {
        m_size = last - first;
        m_buffer.clear();
        m_buffer.reserve(get_line_count(first, last));    //  行数分の要素をリザーブ
        while( first != last ) {
            InputIterator next = get_next_line(first, last);
            m_buffer.push_back(tstring(first, next)tr);
            first = next;
        }
    }
    .....
}

list を gap_vector に変更すると、速度・メモリ効率が若干改善される。
行番号で行をランダムアクセスできるという利点もある。

終わりに

次稿では、list<wstring> の性能向上と piece_table について述べる予定。

参考文献

1. "Software Tools", Braian W. Kernighan, P.J. Plauger, 1976
2. Data Structures for Text Sequences (1998) by Charles Crowley