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

概要

前稿で、 ピーステーブルデータ構造を用いたバイナリエディタ用仮想バッファ第１版のC++による実装と評価結果について報告した。 筆者環境での総合処理速度測定結果は gap_vector を用いた版の約1/10 という燦々たるものであった。 しかし、バイナリエディタ用ということで、バッファサイズが変化しない場合についてのみ測定を行った上に、 テキストエディタ用バッファとして必須の undo/redo 機能を実装しておらず、ピーステーブルデータ構造の長所がでづらい比較であった。 そこで本稿ではバッファサイズが変化する場合についても評価を行うとともに、 undo/redo 機能の実装方法を説明し、 それを実装した場合の評価結果について報告する。

目次（予定所要時間）：

1. 基本事項（8分）
2. 仮想バッファ第１版パフォーマンス再測定（2分）
3. undo/redo 実装（10分）
4. パフォーマンスチューニング（7分）
5. 評価・考察（2分）
6. まとめ（1分）

基本事項

• バッファとは

  1次元のテキストデータ（シーケンスデータ）を管理するクラス。
  基本機能：内容参照、編集（挿入・削除）
  テキストエディタのエンジンにあたる部分で、必要十分な機能・高品質・高速・高メモリ効率・拡張性が求められる。

• バッファのデータ構造

  行単位双方向リンク（vi）、ギャップバッファ（emacs）などがあり、それぞれ一長一短がある。
  ギャップバッファ（= gap_vector<uchar>）はメモリ効率・処理速度の両面で非常に優れたデータ構造だが、 メインメモリ容量以上のテキストを処理できないという問題がある。 64ビットOSであれば4GB以上のバッファ容量を確保可能であるが、データ移動のたびにスワップ処理が発生し、 パフォーマンスが著しく低下する可能性がある。
  シーケンスコンテナを階層的に組み合わせることで新たな特徴をもつデータ構造を作成でき、仮想バッファ化も可能になる
  　　例：行単位双方向リンク、ピーステーブルなど

• 実装方針：

  テスト容易性・拡張性・可換性を高めるために、STL に準じたインタフェースを持つのがよいと考える。
  テンプレートによるジェネリックな実装はクラスの再利用性を高めるとともに、クラスのソフトウェアIC化にも大変有効である。
  イテレータをインタフェースに利用することで、ソースコード上のクラス間依存を低減することもできる。
  

• ViVi のバッファを変更する場合の課題：
  1. 文字コード変換をいつ行うか？
     　表示：HDD (SJIS, UTF8,...) → バッファ → 行管理？ → view-tokenizer → TextOut (Win32API、SJIS or UTF16)
     　カーソル移動、検索処理なども多文字コードに対応する必要がある
  2. 行単位の処理をどのように実装するか？
     　行管理クラスを導入する？ or イテレータだけでやりくり？
  3. 巨大ファイルの取り扱い　（← 今ここ）
  
  
• 仮想バッファとは

  メインメモリ容量を超えるテキストデータをそれと意識せず操作できるバッファを「仮想バッファ」と呼ぶことにする。

• ピーステーブルを用いた仮想バッファクラス図

          ┏━━━━━━━━━━━━━┓      0..*┏━━━━━━━━━┓
          ┃仮想buffer＜ROBuf, ABuf＞ ┃    ┌─→┃      Span        ┃
          ┠─────────────┨    │    ┠─────────┨
          ┃Span シーケンス           ┃◆─┘    ┃m_org : bool      ┃  オリジナルバッファ？
          ┃org(RO)バッファ           ┃◆──┐  ┃m_size : size_t   ┃  スパンサイズ
          ┃追加バッファ              ┃◆─┐│  ┃m_offset : size_t ┃  スパン先頭のバッファ内オフセット
          ┃...                       ┃    ││  ┠─────────┨
          ┃                          ┃    ││  ┗━━━━━━━━━┛
          ┠─────────────┨    ││ 1┏━━━━━━━━━┓
          ┃empty() const : bool      ┃    │└→┃    ROBuffer      ┃  ※ ポリシーで与える
          ┃size() const : size_t     ┃    │    ┠─────────┨
          ┃operator[](size_t) : uchar┃    │    ┠─────────┨
          ┃push_back(uchar)          ┃    │    ┃operator[](size_t)┃
          ┃erase(size_t)             ┃    │    ┃open(cchar*)      ┃
          ┃insert(size_t, uchar)     ┃    │    ┗━━━━━━━━━┛
          ┃replace(size_t, uchar)    ┃    │   1┏━━━━━━━━━┓
          ┃open(cchar*)              ┃    └─→┃   AddBuffer      ┃  ※ ポリシーで与える
          ┃write(cchar*)             ┃          ┠─────────┨
          ┃...                       ┃          ┠─────────┨
          ┗━━━━━━━━━━━━━┛          ┃operator[](size_t)┃
                                                  ┃push_back(uchar)  ┃  データは末尾に*のみ*追加可能
                                                  ┗━━━━━━━━━┛
  

  • Span シーケンスは編集位置情報を Org, Add バッファに振り分けるための情報を保持する。
    Span が保持するサイズ、オフセットの型は size_t とした。よって32bit版での最大サイズは4GBとなる。
    Span シーケンスを管理するデータ構造を何にするかという問題もあるが、第1版では gap_vector を使用した。
  • ROBuffer はリードオンリーのバッファクラスで、ファイルオープン機能とランダムアクセス演算子のみを持つ。
    少量サイズ（第1版では 4096バイト）のビューを介してデータにアクセスする。
  • AddBuffer は末尾にのみデータを追加することのできるimmutableなバッファである。
    バッファ内データが多量になると、自動的にデータをHDDにスワップアウトする機能を持つ。
  • ROBuffer, AddBuffer にはいくつかの実装方法が存在し、環境・条件により性能が異なる。 これらを容易に置換可能にするためにポリシーで与えることにする。
  • イテレータは非負整数に比べると処理コストが大きく、編集処理後に無効になることがあるので、 編集位置指定はバッファ先頭からのインデックス（非負整数）を用いることにする。

仮想バッファ第１版パフォーマンス再測定

• バイナリエディタ用に最大4GBまでを取り扱うことができる仮想バッファ第１版を実装しパフォーマンス測定を行った（2010/05/15）
  参照：バイナリエディタ用仮想バッファの実装と評価

  総合評価として、100メガバイトのファイルオープン、検索＆置換、ファイル別名保存 のタイムを計測
  ファイル内容は 0x00, 0x01 ... 0xfe, 0xff, 0xfe, ... 0x01, 0x00 の三角パターンの繰り返しとする
  0xff を検索し、それを 0x00 に置換し、結果を別ファイルへ書き出すものとする。

   1: template<typename Buffer>
   2: void benchmark_ReadReplaceWrite(cchar *className, cchar *fileName)
   3: {
   4:     {
   5:         std::string fn = fileName;
   6:         fn += ".dump";      //  出力ファイル名
   7:         std::cout << "\nbenchmark replace 0xff -> 0x00\n";
   8:         std::cout << className << " \"" << fileName << "\":\n";
   9:         boost::timer tm;
  10:         Buffer vv;
  11:         if( !vv.open(fileName) )
  12:             return;
  13:         double t1 = tm.elapsed();
  14:         for(uint ix = 0; ix < vv.size(); ++ix) {
  15:             if( vv[ix] == 0xff )
  16:                 vv.replace(ix, 0);      //  0xff なら 0x00 に置換
  17:         }
  18:         double t2 = tm.elapsed();
  19:         vv.write(fn.c_str());
  20:         double t3 = tm.elapsed();
  21:         std::cout << "size = " << vv.size() << "\n";
  22:         std::cout << "read time : " << t1 << "\n";
  23:         std::cout << "replace time: " << t2 - t1 << "\n";
  24:         std::cout << "write time: " << t3 - t2 << "\n";
  25:         std::cout << "TOTAL: " << t3 << "\n";
  26:     }
  27: }
  

  総合評価補足として、空のバッファに上記のトライアングルパターンを書き込むのに要する時間も計測した。

• 前環境による想像処理時間測定結果：

  ※計測環境：ウルフデール3GHz (Bus 334MHz), 4GBMem (DDR2, Max bandwidth:400MHz), WinXP, VC9, Local SATA HDD
  ※HDBENCH による計測結果：Read 97,708KB/S, Write 79,875KB/S, FileCopy 4,043KB/S

  クラス	読込	検索・置換	書出	タイム合計	pat生成
  gap_vector	0.172	0.203	1.125	1.500	0.578
  同上	0.172	0.203	1.157	1.532	0.593
  CBuffer	0.0	1.766	11.578	13.344	7.235
  同上	0.0	1.750	9.656	11.406	8.172

  
  
• 前回はバイナリエディタ向け評価だったので、バッファサイズが変化しない置換処理時間のみ計測したが、 今回はテキストエディタ用バッファとしての評価なので、サイズが増減する場合についても計測を行う。
  また、開発マシンを変更したので、バッファサイズが変化しない場合も再測定を行う。
• 3バイトを５バイトで置き換えるベンチマークプログラムの一部を以下に示す。

   1:     cuchar *data = (cuchar*)"ABCDE";
   2:     const int dataLength = strlen((cchar*)data);
   3:     double t1 = tm.elapsed();
   4:     for(uint ix = 0; ix < vv.size() - 3; ) {
   5:         if( vv[ix] == 0xfd && vv[ix + 1] == 0xfe && vv[ix + 2] == 0xff) {
   6:             vv.erase(ix, ix + 3);
   7:             vv.insert(ix, data, data + dataLength);
   8:             ix += dataLength;
   9:         } else
  10:             ++ix
  11:     }
  

• 測定結果を以下に示す。

  ※計測環境：クラークデール3.46GHz (Bus 133), 4GBMem (DDR3, Max bandwidth:667), Win7(x64), VC9, Local SATA HDD
  ※HDBENCH による計測結果：Read 105,784/S, Write 57,527/S, FileCopy 4,012/S

  511バイト中の１バイトを１バイトで置換（0xff -> 0x00）：

  クラス	読込	検索・置換	書出	タイム合計	pat生成
  gap_vector	0.110	0.175	0.730	1.015	0.464
  同上	0.120	0.178	0.769	1.067	0.465
  CBuffer	0.0	1.453	1.311	2.764	2.107
  同上	0.0	1.448	1.269	2.717	2.126

  
  

  511バイト中の3バイトを5バイトで置換（0xfd 0xfe 0xff -> 0x41 0x42 0x43 0x44 0x45）：

  クラス	読込	検索・置換	書出	タイム合計
  gap_vector	0.110	0.481	0.849	1.440
  同上	0.120	0.494	0.673	1.325
  CBuffer	0.0	1.338	1.260	2.598
  同上	0.0	1.348	1.304	2.652

  
  

  511バイト中の5バイトを3バイトで置換（0xfd 0xfe 0xff 0xfe 0xfd -> 0x41 0x42 0x43）：

  クラス	読込	検索・置換	書出	タイム合計
  gap_vector	0.111	0.276	0.867	1.254
  同上	0.113	0.280	0.669	1.062
  CBuffer	0.0	1.370	1.371	2.741
  同上	0.0	1.345	1.297	2.642

  
  
• 測定環境を変えただけで、約10倍差が2.5〜3倍差に縮まってしまった。 CPU処理速度、メモリ転送速度、HDD転送速度、OSメモリ管理・ディスクキャッシュの違いなどが上記の原因として考えられるが、 はっきりしない。
• 置換によりバッファサイズが増加する場合、ギャップベクタは領域の再確保＆データコピー処理が余分に発生するために、 処理時間が増大する。

undo/redo 実装

• undo/redo 機能を実現するためには実行した編集操作を戻す・再実行するための情報をカプセル化したクラスを導入するとよい。、
• CUndoItem は各コマンドの抽象基底クラス。実際のコマンドクラスはそれから派生される。
• CUndoMgr はコマンドクラスオブジェクトを保持し、要求によりコマンドの戻し・再実行仮想関数を呼び出す。
• gap_vector を利用したバッファのクラス図を下図に示す。

  
  
      ┌──────┐           1┌────────┐        0..*┌───────┐
      │ buffer_GV  │◆────→│ CUndoMgr       │◆────→│  CUndoItem   │
      ├──────┤            ├────────┤            ├───────┤
      │m_undoMgr   │            │m_items         │            ├───────┤
      ├──────┤            │m_current : int │            │doUndo(b*) = 0│
      │do_insert() │            ├────────┤            │doRedo(b*) = 0│
      │do_erase()  │            │push_back(item*)│            └───────┘
      │insert()    │            │doUndo()        │                    │
      │erase()     │            │doRedo()        │                    │
      │...         │            │canUndo() : bool│                    △
      └──────┘            │canRedo() : bool│                    │
                                  └────────┘                    │
                                                              ┌─────┴─────┐
                                                              │                      │
                                                              │                      │
                                                    ┌─────────┐  ┌─────────┐
                                                    │CGVUndoItemInsert │  │ CGVUndoItemErase │
                                                    ├─────────┤  ├─────────┤
                                                    │m_first : index_t │  │m_first : index_t │
                                                    │m_last : index_t  │  │m_last : index_t  │
                                                    │m_buffer : v＜uc＞│  │m_buffer : v＜uc＞│
                                                    ├─────────┤  ├─────────┤
                                                    │doUndo(buffer_GV*)│  │doUndo(buffer_GV*)│
                                                    │doRedo(buffer_GV*)│  │doRedo(buffer_GV*)│
                                                    └─────────┘  └─────────┘
  

  insert(), erase() は undo/redo 対象とならないプリミティブなメソッド、
  do_insert(), do_erase() は undo/redo 対象となるメソッドである。

  do_insert() がコールされると、CUndoItemInsert オブジェクトが生成され、CUndoMgr::m_items キューに積まれる。

   1: void CBuffer_GV::do_insert(index_t ix, value_type v)
   2: {
   3:     ix = min(ix, size());
   4:     m_buffer.insert(ix, v);
   5:     m_undoMgr.push_back(new CUndoItemInsert(ix, v));
   6: }
  

• 挿入・削除 UndoItem オブジェクトは編集位置と挿入・削除文字列情報を保持する。
  挿入・削除サイズを保持し、挿入後または削除undo後は文字列情報を保持しないようにするデータ構造にすれば、 メモリ使用量を減らせるが、データ転送に時間を要するので、どちらがよいかは微妙である。
• 挿入・削除 UndoItem クラスの doUndo(), doRedo() が undo/redo 処理を行うメソッドである。
  どのバッファに対して編集を行うかの情報はメソッド引数でコール時に渡すことにした。
• undo/redo 関連のコードは以下の通り。

   1: void CBBUndoItemInsert::doUndo(CBuffer_GV *bb, index_t& pos)
   2: {
   3:     pos = m_first;
   4:     bb->erase(m_first, m_last);
   5: }
   6: void CBBUndoItemInsert::doRedo(CBuffer_GV *bb, index_t& pos)
   7: {
   8:     pos = m_first;
   9:     bb->insert(m_first, &m_buffer[0], &m_buffer[0] + m_buffer.size());
  10: }
  11: bool CBBUndoMgr::doUndo(CBuffer_GV *bb, uint& pos)
  12: {
  13:     if( !m_current ) return false;
  14:     m_items[--m_current]->doUndo(bb, pos);
  15:     return true;
  16: }
  17: bool CBBUndoMgr::doRedo(CBuffer_GV *bb, uint& pos)
  18: {
  19:     if( m_current >= m_items.size() ) return false;
  20:     m_items[m_current++]->doRedo(bb, pos);
  21:     return true;
  22: }
  

• ピーステーブルに undo/redo を実装する場合、オリジナル・追加バッファは immutable なので、 undo/redo Item にはテキストデータは不要で、編集位置とピース情報のみを保持するだけでよい。

  
  
      ┌──────┐           1┌────────┐        0..*┌───────┐
      │ buffer_PT  │◆────→│ CUndoMgr       │◆────→│  CUndoItem   │
      ├──────┤            ├────────┤            ├───────┤
      │m_undoMgr   │            │m_items         │            ├───────┤
      ├──────┤            │m_current : int │            │doUndo(b*) = 0│
      │do_insert() │            ├────────┤            │doRedo(b*) = 0│
      │do_erase()  │            │push_back(item*)│            └───────┘
      │insert()    │            │doUndo()        │                    │
      │erase()     │            │doRedo()        │                    │
      │...         │            │canUndo() : bool│                    △
      └──────┘            │canRedo() : bool│                    │
                                  └────────┘                    │
                                                              ┌─────┴─────┐
                                                              │                      │
                                                              │                      │
                                                  ┌──────────┐  ┌──────────┐
                                                  │CPTUndoItemInsert   │  │ CPTUndoItemErase   │
                                                  ├──────────┤  ├──────────┤
                                                  │m_first : index_t   │  │m_first : index_t   │
                                                  │m_last : index_t    │  │m_last : index_t    │
                                                  │m_spans : v＜Span＞ │  │m_spans : v＜Span＞ │
                                                  ├──────────┤  ├──────────┤
                                                  │doUndo(buffer_PT*)  │  │doUndo(buffer_PT*)  │
                                                  │doRedo(buffer_PT*)  │  │doRedo(buffer_PT*)  │
                                                  └──────────┘  └──────────┘
  

• PT仮想バッファの場合も、ギャップベクターの場合とほとんど同じである。PTはデータが削除されても それがオリジナル・追加バッファに残っているので、データを UndoItem がデータを保持する必要がなく、 スパン配列としてデータへのポインタを保持していれば充分である。
• undo/redo 関連のコードは以下の通り。

   1: template<typename ROBuffer, typename AddBuffer>
   2: bool CBuffer<ROBuffer, AddBuffer>::do_erase(uint first, uint last)
   3: {
   4:     std::vector<SVBSpan> vs;
   5:     getSpans(vs, first, last);
   6:     bool rc = erase(first, last);
   7:     m_undoMgr.push_back(boost::shared_ptr<CPTUndoItem<ROBuffer, AddBuffer>>
   8:                             (new CPTUndoItemErase<ROBuffer, AddBuffer>(first, last, vs)));
   9:     return true;
  10: }
  11: 
  12: template<typename ROBuffer, typename AddBuffer>
  13: struct CPTUndoItemErase : public CPTUndoItem<ROBuffer, AddBuffer>
  14: {
  15:     index_t m_first;
  16:     index_t m_last;
  17:     std::vector<SVBSpan>    m_spans;    //  削除された部分のスパン
  18: public:
  19:     CPTUndoItemErase(index_t first, index_t last, const std::vector<SVBSpan> &vs)
  20:         : m_first(first), m_last(last), m_spans(vs), CPTUndoItem(UNDOITEM_TYPE_ERASE) {}
  21: public:
  22:     void doUndo(CBuffer<ROBuffer, AddBuffer> *bb, uint &pos)
  23:     {
  24:         bb->insertSpans(pos = m_first, m_spans);
  25:     }
  26:     void doRedo(CBuffer<ROBuffer, AddBuffer> *bb, uint &pos)
  27:     {
  28:         bb->erase(pos = m_first, m_last);
  29:     }
  30: };
  

• undo/redo を実装した場合のパフォーマンス測定結果：

  511バイト中の１バイトを１バイトで置換（0xff -> 0x00）：

  クラス	読込	検索・置換	書出	タイム合計	バッファ破棄
  gap_vector	0.113	2.907	0.658	3.678	18.609
  同上	0.114	5.374	0.723	6.211	20.870
  同上	0.111	3.423	0.665	4.199	18.115
  CBuffer	0.000	4.189	1.092	5.281	18.447
  同上	0.001	4.474	1.079	5.554	18.381

  
  

  511バイト中の3バイトを5バイトで置換（0xfd 0xfe 0xff -> 0x41 0x42 0x43 0x44 0x45）：

  クラス	読込	検索・置換	書出	タイム合計
  gap_vector	0.109	2.681	0.748	3.538
  同上	0.118	6.934	0.678	7.724
  CBuffer	0.000	5.670	1.312	6.982
  同上	0.000	5.658	1.120	6.778

  
  

  511バイト中の5バイトを3バイトで置換（0xfd 0xfe 0xff 0xfe 0xfd -> 0x41 0x42 0x43）：

  クラス	読込	検索・置換	書出	タイム合計
  gap_vector	0.109	2.441	0.835	3.385
  同上	0.117	6.426	0.681	7.224
  CBuffer	0.0	5.484	1.107	6.591
  同上	0.0	5.637	1.124	6.761

  
  
• 総合処理速度比は2倍以内になった。
  gap_vector を使用する版の場合、2回目の検索・置換処理に有意に時間がかかっているのは謎。
  もしかしたらスワップ処理が発生しているのかもしれない。

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

• 「最初から過度な最適化は行わない方がよい」という原則があるので、書きやすさ・理解しやすさを優先して実装した。
  実際にパフォーマンス測定を行い、問題となる部分を見つけたら、その時点でパフォーマンスチューニングを行う。
• 100メガバイトのファイルにて、511バイトごとに1バイトを置換処理した後、バッファオブジェクトを破棄すると、 約20秒もの処理時間を要するようになってしまった。
• 100メガ/511*2 = 約40万個の UndoItem オブジェクトが生成され、その破棄処理に時間がかかっているのが原因と推測される。
• boost::object_poot を使用することで、多数オブジェクトの破棄処理を高速化することができる。
  ※ UndoItem の種類数分の object_pool を用意する必要があるのがいまいち・・・

  
  
      ┌──────┐           1┌────────┐        0..*┌───────┐
      │ buffer_GV  │◆────→│ CUndoMgr       │    ┌──→│  CUndoItem   │
      ├──────┤            ├────────┤    │      ├───────┤
      │m_undoMgr   │            │m_items         │──┘      ├───────┤
      ├──────┤            │m_current : int │            │doUndo(b*) = 0│
      │do_insert() │            │m_pool_erase    │◆───┐  │doRedo(b*) = 0│
      │do_erase()  │            │m_pool_insert   │◆─┐  │  └───────┘
      │insert()    │            ├────────┤    │  │          │
      │erase()     │            │doUndo()        │    │  └─────│───────┐
      │...         │            │doRedo()        │    │              △              │
      └──────┘            │canUndo() : bool│    │              │              │
                                  │canRedo() : bool│    │              │              │
                                  └────────┘    │  ┌─────┴─────┐  │
                                                          │  │                      │  │
                                                          ↓  │                      │  ↓
                                                    ┌─────────┐  ┌─────────┐
                                                    │CGVUndoItemInsert │  │ CGVUndoItemErase │
                                                    ├─────────┤  ├─────────┤
                                                    │m_ix : index_t    │  │m_ix : index_t    │
                                                    │m_buffer : v＜uc＞│  │m_buffer : v＜uc＞│
                                                    ├─────────┤  ├─────────┤
                                                    │doUndo(buffer_GV*)│  │doUndo(buffer_GV*)│
                                                    │doRedo(buffer_GV*)│  │doRedo(buffer_GV*)│
                                                    └─────────┘  └─────────┘
  

• 破棄時間は、object_pool を利用することで約20秒から約8秒に短縮できた。
• vector<uchar> データ部分も独自のヒープで管理することにすれば、処理時間を1秒以下に短縮できると期待される。
• 下図に保存データ領域をヒープ上に取る場合のクラス図を示す。

  
  
      ┌──────┐           1┌────────┐        0..*┌─────────┐
      │ buffer_GV  │◆────→│ CUndoMgr       │    ┌──→│   CGVUndoItem    │
      ├──────┤            ├────────┤    │      ├─────────┤
      │m_undoMgr   │            │m_items         │──┘      │m_type            │
      ├──────┤            │m_current : int │            │m_flags           │
      │do_insert() │            │m_pool          │◆────→│m_first : index_t │
      │do_erase()  │            │m_heap : v＜uc＞│            │m_last : index_t  │
      │insert()    │            ├────────┤            │m_hp_ix : index_t │
      │erase()     │            │doUndo()        │            ├─────────┤
      │...         │            │doRedo()        │            └─────────┘
      └──────┘            │canUndo() : bool│                                  
                                  │canRedo() : bool│                                  
                                  └────────┘                                  
  

   1: bool CGVUndoMgr::doUndo(CBuffer_GV *bb, uint& pos)
   2: {
   3:     if( !m_current ) return false;
   4:     const CGVUndoItem *ptr = m_items[--m_current];
   5:     cuchar *heap = &m_heap[ptr->m_hp_ix];
   6:     switch( ptr->m_type ) {
   7:     case UNDOITEM_TYPE_ERASE:
   8:         bb->insert(ptr->m_first, heap, heap + ptr->data_size());
   9:         break;
  10:     case UNDOITEM_TYPE_INSERT:
  11:         bb->erase(ptr->m_first, ptr->m_last);
  12:         break;
  13:     }
  14:     return true;
  15: }
  

• ヒープ領域を用いて undo/redo を実装した場合のパフォーマンス測定結果：

  511バイト中の１バイトを１バイトで置換（0xff -> 0x00）：

  クラス	読込	検索・置換	書出	タイム合計	バッファ破棄
  gap_vector	0.111	0.196	1.107	1.414	0.008
  同上	0.113	0.197	0.679	0.989	0.008
  同上	0.112	0.197	0.728	1.037	0.008
  CBuffer	0.000	4.189	1.092	5.281	18.447
  同上	0.001	4.474	1.079	5.554	18.381

  
  
• ヒープを利用し、データメモリ破棄を一括して行うことで、破棄時間を 0.008秒に短縮することができた。
  ついでに置換処理も数倍高速化されてしまった。
• 今回は実装しなかったが、ヒープではなく AddBuffer を利用すれば古いデータがHDDに自動的にスワップアウトされるので、 より多量のコマンドの undo/redo が可能となる。
• 同様に、ピーステーブル仮想バッファもヒープを使用するように修正してみた。

  
  
      ┌──────┐           1┌────────┐        0..*┌─────────┐
      │ buffer_PT  │◆────→│ CUndoMgr       │    ┌──→│   CPTUndoItem    │
      ├──────┤            ├────────┤    │      ├─────────┤
      │m_undoMgr   │            │m_items         │──┘      │m_type            │
      ├──────┤            │m_current : int │            │m_flags           │
      │do_insert() │            │m_pool          │◆────→│m_first : index_t │
      │do_erase()  │            │m_spans : v＜s＞│            │m_last : index_t  │
      │insert()    │            ├────────┤            │m_hp_fst : index_t│
      │erase()     │            │doUndo()        │            │m_hp_sz : index_t │
      │...         │            │doRedo()        │            ├─────────┤
      └──────┘            │canUndo() : bool│            └─────────┘
                                  │canRedo() : bool│                                  
                                  └────────┘                                  
  

   1: bool    doUndo(CBuffer<ROBuffer, AddBuffer> *bb, uint &pos)
   2: {
   3:     if( !m_current ) return false;
   4:     const undoitem_t *ptr = m_items[--m_current];
   5:     SVBSpan *hp_first = &m_spans[ptr->m_hp_first];
   6:     SVBSpan *hp_last = hp_first + ptr->m_hp_size;
   7:     switch( ptr->m_type ) {
   8:     case UNDOITEM_TYPE_ERASE:
   9:         bb->insertSpans(ptr->m_first, hp_first, hp_last);
  10:         break;
  11:     case UNDOITEM_TYPE_INSERT:
  12:         bb->erase(ptr->m_first, ptr->m_last);
  13:         break;
  14:     }
  15:     return true;
  16: }
  

• ヒープ領域を用いて undo/redo を実装した場合のパフォーマンス測定結果：

  511バイト中の１バイトを１バイトで置換（0xff -> 0x00）：

  クラス	読込	検索・置換	書出	タイム合計	バッファ破棄
  gap_vector	0.111	0.196	1.107	1.414	0.008
  同上	0.113	0.197	0.679	0.989	0.008
  同上	0.112	0.197	0.728	1.037	0.008
  CBuffer	0.000	2.812	1.209	4.021	0.001
  同上	0.000	2.743	1.469	4.212	0.001

  
  

  511バイト中の3バイトを5バイトで置換（0xfd 0xfe 0xff -> 0x41 0x42 0x43 0x44 0x45）：

  クラス	読込	検索・置換	書出	タイム合計
  gap_vector	0.114	0.590	0.994	1.698
  同上	0.120	0.513	0.841	1.474
  CBuffer	0.0	2.767	1.214	3.981
  同上	0.0	2.791	1.368	4.177

  
  
• データをシーケンシャルにアクセスする場合、イテレータを実装することで、 ランダムアクセス演算子を用いるよりも処理を高速化できると期待できる。
• おまけ （参照：サクラエディタはベンチマークの夢を見るか？）

  	(3文字→5文字置換)*70万回
  gap_vector + undo/redo	0.18秒
  E v10.0体験版	約1秒
  H v8.01	約1.5秒（高速置換）
  PT仮想バッファ	3.4秒
  ViVi 3.05.048 :%s	3.58秒
  メモ帳	5秒
  サクラエディタ Athlon 64 X2 4200+	56秒
  サクラエディタCore 2 Duo E6300	65秒
  T v0.93	高速置換モード無し

  ※ サクラエディタ以外は筆者環境（クラークデール、win7(x64)）で計測

評価・考察

• 理論的には、gap_vector・PT仮想バッファともに、読み込み・検索・置換・書き出し処理時間はデータサイズに対して線形となる。
• メモリ消費量：

  	データ	undo/redo
  gap_vector	1.5 * N	sizeof(UndoItem) + 挿入・削除データ
  PT仮想バッファ	R + A + S * sizeof(Span)	sizeof(UndoItem)

  ※ N：データサイズ、R：ROバッファ ビューサイズ、A：追加バッファ ビュー・追加エリアサイズ、S：スパン数
  ※ 前稿・本稿では R = 4096, A = 4096 + 4096 = 8192、sizeof(Span) = 8

• 100MBのファイルに対して、511バイト中の3バイトを5バイトで置き換えた場合のメモリ消費量：

  	データ	undo/redo
  gap_vector	200MB	(20+3+5) * 195,694 = 5,479,432
  PT仮想バッファ	4,096 + 8,192 + 391,389 * 8 = 3,143,400	20 * 195,694 = 3,913,880

• PT仮想バッファのオリジナル・追加バッファのデータはimmutable（的）であり、 undo/redo のためにデータを別途保存する必要がないというアドバンテージがある。
• ピーステーブルを用いた仮想バッファは、gap_vector と比べて遜色ない処理速度をもち、 使用可能メモリ領域以上の容量のデータを効率的に取り扱うことができる。 テキストエディタ用バッファのデータ構造としてよい選択肢であると考える。
• 現状の版は size_t が32ビットであるために4GBという上限があるが、これを64ビット化することでより大容量のデータ処理が可能となる。
• 仮想バッファであっても、32ビットOS下では4GB上限、64ビットOSでは4GB超というのが、バランス的にいいのではないかと考えている。

まとめ

• ピーステーブルデータ構造を使用し、最大サイズ4GBの仮想バッファに undo/redo 機能を実装し、 gap_vector を使用したものとの比較を行った。
• 計測環境が変わったのも一因であるが、総合的な処理速度は gap_vector と大差無いようになった。
• まずは ViVi 3.07/08 で、バイナリモード用バッファとして採用してみる予定である。