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

概要

テキストエディタ ViVi ver 3.05/06 に実装予定のバイナリエディタ用仮想バッファの インタフェース・データ構造・アルゴリズムについて解説し、 VC9 を使って実装したものでパフォーマンス計測した結果を報告する。

目次：

1. はじめに
2. バッファ（5分）
3. リードオンリー仮想バッファ（10分）
4. スワップアウトを行わない編集可能仮想バッファ（10分）
5. スワップアウトを行う編集可能仮想バッファ（5分）
6. 総合評価（5分）
7. さいごに

はじめに

• 筆者は vi コマンドもサポートする Windows 用テキストエディタ ViVi を延々開発している。
  CSV、画像インライン表示、プロジェクト可視化などなどの機能を持つ
  開発環境：WinXP, VC9, ViVi
  ソース：約20万行（空行、コメント行を含む）
• 外部記憶容量の増大に伴ない、apache ログなどの巨大ファイルの内容を参照・編集したいという要望が増えてきた。
• 現状の ViVi はファイル内容をすべてメモリ上にあるバッファに読み込んでいるため巨大ファイルを編集どころか読み込むこともできない。 （開いているファイル数・編集履歴等にも依存するが、数100メガバイトが限界）
  → 主メモリ容量よりも大きなファイルを、そうと意識することなく取り扱える仮想バッファが必要
• バッファの仮想化を実現するためには、階層的データ構造を用いるとよいのだが、解決すべき課題がいくつかある
  • 文字コード変換をいつどのように行うのか？
    ファイルの文字コードは様々あるが、テキストを表示するために WinAPI に渡す場合は SJIS または Unicode である。
    いつどの時点で内部文字コードに変換するかを決めなくてはいけない。
  • 行の取り扱いをどうするのか？
    gap_vector, ピーステーブルは行に関する情報を保持しないが、行番号ジャンプや編集フラグ処理などで行単位処理が必要。
    どのように行情報を保持し（または保持せず）、処理をするかを決めなくてはいけない。
  → まずは、上記の問題に悩まされなくてすむバイナリエディタのバッファを仮想化してみることにした＠ViVi 3.05/06
  
• 最初からフルスペックなものを実装するといろいろ大変なので、以下のような作戦とする
  1. バッファサイズの上限は 4GB とする（それ以上のサイズのサポートは64bit OSに移行後とする）
  2. まずはリードオンリーな仮想バッファを実装・評価してみる
  3. 次に、編集可能だがスワップアウトを行わないものを実装・評価し、
  4. 最後にスワップアウトを行うフルスペックのものを実装・評価する
  5. 本稿では本格的なパフォーマンスチューニング・undo/redo機能実装は行わず、５月中旬以降の課題とする。

バッファ

• テキストエディタは、簡単に言うと、シーケンシャルなテキスト情報を保持し、ユーザの指示により内容を表示、修正するプログラムである。

  

• 通常はテキストデータをメンバ変数に持ち、データを参照、変数するメソッドを持つオブジェクトと、 ユーザの指示を解釈し、適切なメソッドを呼び出すオブジェクトを導入する。 前者をバッファ（エディットエンジンとも呼ばれる）、後者をUIオブジェクトと呼ぶ。

  

• バッファとは1次元的に並んだ文字を管理するクラスである。 車で言えばエンジンにあたるようなもので、テキストエディタの最も重要なモジュールのひとつである。
• 必要充分な機能・高信頼性・高速性・メモリ効率の良さ・拡張性 が求められる
• シーケンシャルアクセス、編集（削除・挿入）機能が必須 （文字インデックス、行番号によるランダムアクセスもできた方がよい）
• デバイス、インタフェースの進化により状況は常に変化するので、その時点で最適なデータ構造・アルゴリズム・実装方法に簡単に変更可能にしておくことが肝要
• 下図の様なSTL互換の C++インタフェースを定義することができる
• テキスト シーケンスのデータ構造はクラスにより様々で、それによりバッファクラスの特徴・性能が決まる。

  
                     ┏━━━━━━━━━━━━━━━━━━━┓
                     ┃        random_access_iterator        ┃
                     ┗━━━━━━━━━━━━━━━━━━━┛
                                       │
                                       △
                                       │
                     ┏━━━━━━━━━━━━━━━━━━━┓
               ←──┃          buffer::cursor              ┃──→
        operator--() ┠───────────────────┨ operator++()
                     ┠───────────────────┨
                     ┃operator*() const : uchar             ┃
                     ┃operator*() : uchar&                  ┃    //  undo 非対象
                     ┃operator==(const cursor&) const : bool┃
                     ┃operator>(const cursor&) const : bool ┃
                     ┃operator+=(int) : cursor&             ┃
                     ┃operator-(const cursor&) const : int  ┃
                     ┃.....                                 ┃
                     ┗━━━━━━━━━━━━━━━━━━━┛
                                       │
                                       ↓
      ┌───────────────────────────────────┐
      │                            text sequences                            │
      └───────────────────────────────────┘
       ↑
       │            ┏━━━━━━━━━━━━━━━━━┓
       │            ┃            buffer                ┃
       │            ┠─────────────────┨
       └─────◆┃                                  ┃
                     ┠─────────────────┨
                     ┃empty() const : bool              ┃
                     ┃size() const : size_t             ┃
                     ┃resize(size_t)  : void            ┃    //  undo 非対象
                     ┃operator[](uint) const : uchar    ┃
                     ┃operator[](uint) : uchar&         ┃    //  undo 非対象
                     ┃begin() : cursor                  ┃
                     ┃end() : cursor                    ┃
                     ┃open(cchar*) : bool               ┃
                     ┃write() : bool                    ┃
                     ┃insert(cursor, uchar) : cursor    ┃    //  undo 非対象
                     ┃erase(cursor, cursor) : cursor    ┃    //  undo 非対象
                     ┃replace(cursor, uchar) : cursor   ┃    //  undo 非対象
                     ┃insert(uint, uchar) : uint        ┃    //  undo 非対象
                     ┃erase(uint, cursor) : uint        ┃    //  undo 非対象
                     ┃replace(uint, uchar) : uint       ┃    //  undo 非対象
                     ┃                                  ┃
                     ┃doResize(size_t)  : void          ┃    //  undo 対象
                     ┃doInsert(uint, uchar) : uint      ┃    //  undo 対象
                     ┃doErase(uint, cursor) : uint      ┃    //  undo 対象
                     ┃doReplace(uint, uchar) : uint     ┃    //  undo 対象
                     ┃isUndoAvailable() const : bool    ┃
                     ┃isRedoAvailable() const : bool    ┃
                     ┃undo()                            ┃
                     ┃redo()                            ┃
                     ┃.....                             ┃
                     ┗━━━━━━━━━━━━━━━━━┛
  
  

リードオンリー仮想バッファ

• 最も簡単なリードオンリーな仮想バッファを実装し、パフォーマンス計測を行ってみる。
• ファイル先頭から末尾までをシーケンシャルアクセスするのに要する時間を計測する。
  ※ テキストエディタ用バッファにおいて、もっとも重要なのはシーケンシャルアクセスのパフォーマンスである。
• uchar operator[](uint) const; のみを実装する。
• リードオンリーなので undo/redo 機能を実装する必要がない。
• 利用可能なメインメモリ容量以上のテキストファイルの内容を参照するために、ファイル全体をメモリに読み込むことは行わない。
• データ構造：（デフォルトで）4096バイトのキャッシュバッファ（ビューとも呼ぶ）を用意する。

              ↓ビュー
              ┏━━┓
      ┌───╂──╂────────────────────────────┐
      │      ┃    ┃              text sequences                            │
      └───╂──╂────────────────────────────┘
              ┗━━┛
  

• アルゴリズムは単純で、operator[](uint) で参照された部分がキャッシュに存在しない場合は、 参照された部分をキャッシュに読み込むだけとする。
  ※ テキストエディタではアクセスされる部分は局所化されており、このような単純なアルゴリズムで問題ない。

    1: uchar CROBuffer::operator[](uint offset)
    2: {
    3:     if( m_hFile == INVALID_HANDLE_VALUE || offset >= m_size )
    4:         return 0;                       //  エラーの場合
    5:     if( !isViewAvailable(offset) &&     //  キャッシュバッファ内にデータがあるか？
    6:         !makeViewBuffer(offset) )       //  キャッシュバッファに読み込む
    7:     {
    8:         return 0;
    9:     }
   10:     return m_viewBuffer[offset - m_viewOffset];
   11: }
  

• キャッシュバッファの実装方法としては、以下の方法が考えられる。
  1. 配列を用意しておき、FILE API で読み込む

         ┏━━━━━━━━━━━━━━━━┓
         ┃        CROBuffer_Rd            ┃
         ┠────────────────┨
         ┃m_size : size_t                 ┃    //  ファイルサイズ
         ┃m_hFile : HANDLE                ┃    //  ファイルハンドル
         ┃m_viewOffset : uint             ┃    //  キャッシュバッファ先頭のファイル内オフセット
         ┃m_viewBuffer[VIEW_SIZE] : uchar ┃    //  キャッシュバッファ
         ┠────────────────┨
         ┗━━━━━━━━━━━━━━━━┛
     

  2. メモリマップトファイルを作成し、参照部分のビューを作成する

         ┏━━━━━━━━━━━━━━━━┓
         ┃        CROBuffer_MMF           ┃
         ┠────────────────┨
         ┃m_size : size_t                 ┃    //  ファイルサイズ
         ┃m_hFile : HANDLE                ┃    //  ファイルハンドル
         ┃m_hFileMap : HANDLE             ┃    //  メモリマップトファイルハンドル
         ┃m_viewOffset : uint             ┃    //  キャッシュバッファ先頭のファイル内オフセット
         ┃m_mapView : uchar*              ┃    //  ビュー先頭へのポインタ
         ┃m_mapViewEnd : uchar*           ┃    //  ビュー末尾へのポインタ
         ┠────────────────┨
         ┗━━━━━━━━━━━━━━━━┛
     

• ベンチマークプログラムを以下に示す

    1: template<typename Buffer>
    2: void benchmark(cchar *className, cchar *fileName)
    3: {
    4:     std::cout << "\n" << className << " \"" << fileName << "\":\n";
    5:     Buffer vb;
    6:     if( !vb.open(fileName) )
    7:         return;
    8:     std::cout << "seq-access:\n";
    9:     uint sum = 0;
   10:     boost::timer tm;
   11:     for(uint ix = 0; ix < vb.size(); ++ix)
   12:         sum += vb[ix];
   13:     double t = tm.elapsed();
   14:     std::cout << "sum = " << sum << "\n";
   15:     std::cout << "time: " << t << " (" << vb.size()/t/1000000 << " MB/sec)\n";
   16: }
  

• 計測内容：ファイルをオープンした後、先頭から最後までをシーケンシャルにアクセスするのに要する時間を計測する。
  HDD キャッシュが効いている場合とそうでない場合でタイムが異なるので、２回続けて計測する。
  → 画面表示を繰り返し行う場合はキャッシュが効いた状態となる。
• 計測結果を以下に示す
  比較のために、gap_vector, getc(), MMF で一括オープンした場合も計測した。

  リードオンリー仮想バッファの 100MB, 1.5GB, 3.2GB ファイルシーケンシャルアクセス時間： 結果

  シーケンシャルアクセス速度(MB/S)は以下の通り：
  

  	100MB		1.5GB		3.2GB
  gap_vector<uchar>	1085.110		未計測		未計測
  getc	14.192		14.004		未計測
  MMF一括読込後	1645.160		1416.970		読込不可
  CROBuffer_Rd 初回	103.553		78.5866		99.3717
  ２回目	384.9060		375.951		74.1967
  CROBuffer_MMF 初回	69.435		67.9337		69.3118
  ２回目	261.538		265.65		68.3198

  
  ※計測環境：ウルフデール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
• 結果・考察：
  • MMFは非常に高速だが、メモリに一括読み込みできる場合に限られるし、仮想メモリ空間をファイルサイズ分消費する。
    ※ 本計測はMMFバッファへの読み込み時間は含まれていない
  • 仮想バッファ：MMFビューを用いた版よりも、Win32API ReadFile() を用いた版の方が高速であった
    マップビューの切り替えのオーバヘッドが予想以上に大きい
  • 最初のシーケンシャルアクセスはディスクキャッシュが効かず、HDD転送速度が律速になっているようだ
  • シーケンシャルアクセスを２回行うと、２回目の転送速度は２〜３倍高速化した
    HDDキャッシュ容量はそう大きくなく（8〜16MB）、なぜ1.5GBファイルでも高速化するのかは謎
  • ファイルサイズが 1.5GB と 3.2GB で速度が大きく異なるのは、ディスクキャッシュが効くかどうかと思われる
  • ファイルサイズが巨大で無い場合は、MMF一括読み込みを利用するよう切り分けるのがいいかもしれない
• 仮想関数にした場合も計測

                          ┏━━━━━━━━━━━━━━━━━┓
                          ┃         CAbstractROBuffer        ┃
                          ┠─────────────────┨
                          ┠─────────────────┨
                          ┃empty() const = 0 : bool          ┃
                          ┃size() const = 0 : size_t         ┃
                          ┃operator[](uint) const = 0 : uchar┃
                          ┃open(cchar*) = 0 : bool           ┃
                          ┃.....                             ┃
                          ┗━━━━━━━━━━━━━━━━━┛
                                            │
                                            △
                                            │
                        ┌─────────┴─────────┐
                        │                                      │
        ┏━━━━━━━━━━━━━━━┓      ┏━━━━━━━━━━━━━━━┓ 
        ┃       CDrvdROBuffer_MMF      ┃      ┃       CDrvdROBuffer_Rd       ┃ 
        ┠───────────────┨      ┠───────────────┨ 
        ┠───────────────┨      ┠───────────────┨ 
        ┃empty() const : bool          ┃      ┃empty() const : bool          ┃ 
        ┃size() const : size_t         ┃      ┃size() const : size_t         ┃ 
        ┃operator[](uint) const : uchar┃      ┃operator[](uint) const : uchar┃ 
        ┃open(cchar*) : bool           ┃      ┃open(cchar*) : bool           ┃ 
        ┃.....                         ┃      ┃.....                         ┃ 
        ┗━━━━━━━━━━━━━━━┛      ┗━━━━━━━━━━━━━━━┛ 
  

  	100MB		1.5GB		3.2GB
  CROBuffer_Rd 初回	103.553		78.5866		99.3717
  ２回目	384.9060		375.951		未計測
  CDrvdROBuffer_Rd 初回	93.2358		108.141		106.76
  ２回目	197.674		199.489		未計測

  
  

  キャッシュが効かない場合の速度はほとんど変わらないが、キャッシュが効いていると半分程度の速度になる。 これはHDDの転送速度が律速の場合は仮想関数コールのオーバヘッドは効いてこないが、 HDDキャッシュが効いている場合はオーバヘッドを無視できなくなるということである。
  従って、一定サイズ以下の場合はMMFに一括読み込みを行うようにし、派生クラスを動的に切り替えるようにしても、 仮想関数コールのオーバヘッドでそれほど高速にはならないと考えられる。

スワップアウトを行わない編集可能仮想バッファ

• 仮想バッファを編集可能にするために、挿入された文字情報を保持する追加バッファと、 テキストシーケンスの一部分を管理する Span を導入し、 Span シーケンスでテキストシーケンス全体を表現する。 （階層的データ構造、ピーステーブル）

       buffer
      ┌────────┬─┬───────┬───────┐
      │                │  │              │              │ //  Span シーケンス
      └────────┴─┴───────┴───────┘
               │         │        │              │
               │         └────┼──────┐└───┐
               ↓                   ↓            ↓        ↓
      ┌────────┬─┬───────┐  ┌─┬───────┐
      │                │  │              │  │  │              │
      └────────┴─┴───────┘  └─┴───────┘
       Original Buffer                           Add Buffer
  

• 追加バッファサイズが大きくなりメインメモリを圧迫するようになった場合、 本来は追加バッファの一部を外部記憶装置にスワップアウトするのだが、この版ではその処理を行わない。
• Span は、オリジナルバッファ/追加バッファ、スパンに含まれるデータサイズ、スパン先頭位置のバッファ内オフセット情報を持つ。

      ┏━━━━━━━━┓
      ┃      Span      ┃
      ┠────────┨
      ┃m_org : bool    ┃
      ┃m_size : uint   ┃
      ┃m_offset : uint ┃
      ┠────────┨
      ┗━━━━━━━━┛
  

• uchar operator[](uint) const がコールされた場合は、インデックスに対応する Span を探し、Span 内オフセットを計算する。 次にオリジナルバッファまたは追加バッファを参照してデータを取り出す。 バッファを参照するときはリードオンリー仮想バッファと同じ処理を行う。

    1: //　　buffer[ix]──→ Span、span が指すバッファ内オフセット
    2: uchar buffer::operator[](uint ix) const
    3: {
    4:     if( ix が範囲外 ) return 0;
    5:     uint offset;    //  オリジナル/追加バッファ中のオフセット
    6:     const Span *span = findSpan(ix, offset);    //  ix に対応するSpanを探す。
    7:     if( span->isOriginalBuffer() )
    8:         return オリジナルバッファから offset 位置のデータを取得;
    9:     else
   10:         return 追加バッファから offset 位置のデータを取得;
   11: }
  

  バッファ内インデックスから対応するスパンを検索する処理時間は、スパンを格納するデータ構造に依存する。 ベクター類を用いた場合、スパン数を N とすれば、処理時間は O(N) になる。
  しかし、テキストエディタでは参照位置は局所化されており、直前にアクセスされた位置をキャッシュしておけば、 処理時間はほぼ O(1) となる。

• データ構造をより詳しく記述すると下図の様になる。

                     ┏━━━━━━━━━┓     0..* ┏━━━━━━━━┓
                     ┃      buffer      ┃    ┌─→┃      Span      ┃
                     ┠─────────┨    │    ┠────────┨
       ┌─────◆┃ファイル情報      ┃    │    ┃m_size : uint   ┃  スパンサイズ
       │        ┌─┃ビュー情報        ┃    │    ┃m_org : bool    ┃  オリジナルバッファ？
       │        │  ┃Span シーケンス   ┃◆─┘    ┃m_offset : uint ┃  スパン先頭のバッファ内オフセット
       │        │  ┃ビュー情報        ┃────┐┃                ┃
       │        │  ┃追加バッファ      ┃◆─┐  │┠────────┨
       │        │  ┠─────────┨    │  │┃                ┃
       │        │  ┃                  ┃    │  │┃                ┃
       │        │  ┗━━━━━━━━━┛    │  │┗━━━━━━━━┛
       │        ↓                            │  ↓
       ↓     ┏━━━┓                       ↓ ┏━━━┓
      ┌───╂───╂──────────┐┌─╂───╂─────────┐
      │      ┃      ┃  Original Buffer   ││  ┃      ┃    Add Buffer    │
      └───╂───╂──────────┘└─╂───╂─────────┘
              ┗━━━┛                          ┗━━━┛
  

  オリジナルバッファの部分は、先に実装した ROBuffer をそのまま利用すべきである。
  そのためには継承または委譲を使用する。

  
          ┏━━━━━━━━━┓
          ┃     ROBuffer     ┃
          ┠─────────┨
          ┠─────────┨
          ┗━━━━━━━━━┛
                   │
                   △
                   │is-a
          ┏━━━━━━━━━┓     0..* ┏━━━━━━━━┓
          ┃      buffer      ┃    ┌─→┃      Span      ┃
          ┠─────────┨    │    ┠────────┨
          ┃Span シーケンス   ┃◆─┘    ┃m_size : uint   ┃  スパンサイズ
          ┃ビュー情報        ┃────┐┃m_org : bool    ┃  オリジナルバッファ？
          ┃追加バッファ      ┃◆─┐  │┃m_offset : uint ┃  スパン先頭のバッファ内オフセット
          ┠─────────┨    │  │┠────────┨
          ┃                  ┃    │  │┃                ┃
          ┗━━━━━━━━━┛    │  │┗━━━━━━━━┛
                                    │  ↓
                                    ↓ ┏━━━┓
                                   ┌─╂───╂─────────┐
                                   │  ┃      ┃    Add Buffer    │
                                   └─╂───╂─────────┘
                                       ┗━━━┛
  

                                          ┏━━━━━━━━┓
                                  ┌──→┃    ROBuffer    ┃
                                  │has-a ┠────────┨
          ┏━━━━━━━━━┓  │      ┠────────┨
          ┃      buffer      ┃  │      ┗━━━━━━━━┛
          ┠─────────┨  │
          ┃orgバッファ       ┃◆┘  0..*┏━━━━━━━━┓
          ┃Span シーケンス   ┃◆───→┃      Span      ┃
          ┃ビュー情報        ┃────┐┠────────┨
          ┃追加バッファ      ┃◆─┐  │┃m_size : uint   ┃  スパンサイズ
          ┠─────────┨    │  │┃m_org : bool    ┃  オリジナルバッファ？
          ┃                  ┃    │  │┃m_offset : uint ┃  スパン先頭のバッファ内オフセット
          ┗━━━━━━━━━┛    │  │┠────────┨
                                    │  │┃                ┃
                                    │  │┗━━━━━━━━┛
                                    │  ↓
                                    ↓ ┏━━━┓
                                   ┌─╂───╂─────────┐
                                   │  ┃      ┃    Add Buffer    │
                                   └─╂───╂─────────┘
                                       ┗━━━┛
  

  追加バッファの部分も、機能が ROBuffer を拡張したものになっているので、クラス化して利用すべきである。
  よって、オリジナルバッファ・追加バッファをそれぞれクラス化し、 編集可能バッファからはそれらを委譲で利用するようにした。
  また、それらのクラスはポリシーとして編集可能バッファに渡すようにした。

          ┏━━━━━━━━━┓          ┏━━━━━━━━┓
          ┃      buffer      ┃    ┌─→┃    ROBuffer    ┃
          ┠─────────┨    │    ┠────────┨
          ┃orgバッファ       ┃◆─┘    ┠────────┨
          ┃                  ┃          ┗━━━━━━━━┛
          ┃Span シーケンス   ┃◆─┐0..*┏━━━━━━━━┓
          ┃                  ┃    └─→┃      Span      ┃
          ┃追加バッファ      ┃◆─┐    ┠────────┨
          ┠─────────┨    │    ┃m_size : uint   ┃  スパンサイズ
          ┃                  ┃    │    ┃m_org : bool    ┃  オリジナルバッファ？
          ┗━━━━━━━━━┛    │    ┃m_offset : uint ┃  スパン先頭のバッファ内オフセット
                                    │    ┠────────┨
                                    │    ┃                ┃
                                    │    ┗━━━━━━━━┛
                                    │    ┏━━━━━━━━┓
                                    └─→┃   AddBuffer    ┃
                                          ┠────────┨
                                          ┠────────┨
                                          ┃size()          ┃
                                          ┃empty()         ┃
                                          ┃operator[](uint)┃  //  const 
                                          ┃push_back(uchar)┃
                                          ┃.....           ┃
                                          ┗━━━━━━━━┛
  
  
  
  

    1: template<typename ROBuffer, typename AddBuffer>
    2: class CBuffer
    3: {
    4: protected:
    5:     uint    m_size;             //  バッファサイズ [0, 0xffffffff)
    6:     std::gap_vector<SVBSpan>    m_spans;        //  スパンベクター
    7: 
    8:     ROBuffer    m_orgBuffer;    //  オリジナルバッファ
    9:     AddBuffer   m_addBuffer;    //  追加ベクター
   10: public:
   11:     CBuffer() : m_size(0), m_spanCacheIX(0), m_spanCacheOffset(0) {}
   12:     ~CBuffer() { close(); }
   13: 
   14:     uchar   operator[](uint) const;
   15:     .....
   16: };
   17: template<typename ROBuffer, typename AddBuffer>
   18: uchar CBuffer<ROBuffer, AddBuffer>::operator[](uint ix)
   19: {
   20:     if( ix >= m_size ) return 0;
   21:     uint offset;    //  オリジナル or 追加バッファ内オフセット
   22:     const SVBSpan *span = getSpan(ix, offset);
   23:     if( span == NULL ) return 0;
   24:     if( span->isOrgBuffer() )
   25:         return m_orgBuffer[offset];
   26:     else
   27:         return m_addBuffer[offset];
   28: }
  

  スワップアウトを行わない追加バッファは std::vector で十分である。

    1: class CAddBuffer_vect
    2: {
    3:     std::vector<uchar>  m_buffer;
    4: public:
    5:     CAddBuffer_vect() {}
    6:     ~CAddBuffer_vect() {}
    7: 
    8: public:
    9:     size_t  size() const { return m_buffer.size(); }
   10:     bool    empty() const { return m_buffer.empty(); }
   11:     uchar operator[](uint ix) const { return m_buffer[ix]; }
   12: 
   13: public:
   14:     void    push_back(uchar x) { m_buffer.push_back(x); }
   15: };
  

• ファイルオープンと operator[](uint) を実装し、シーケンシャルアクセス時間を計測した： 結果

  処理速度（MB/sec）の計測結果を一覧にしたものを下表に示す。

  	100MB		1.5GB		3.2GB
  CROBuffer_Rd 初回	103.553		78.5866		99.3717
  ２回目	384.9060		375.951		未計測
  CROBuffer_MMF 初回	69.435		67.9337		69.3118
  ２回目	261.538		265.65		未計測
  CBuffer SO無 初回	69.435		62.9477		68.9854
  ２回目	69.435		68.8927		70.4056

  
  ※計測環境：ウルフデール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

• 考察
  • スパンを導入した場合、operator[](uint) の処理には予想以上のオーバヘッダがあった
  • const_cursor を導入すると、高速化できるかもしれない （operator[](uint) は本来ランダムアクセスのための機能である。 カーソル（イテレータ）はデータをシーケンシャルにアクセスすることを前提とした最適化を施すことが可能）
  • スパン範囲チェックに時間を要しているので、１バイトごとではなく、複数バイトまとめて転送すれば高速化できるかもしれない
  • シーケンシャルアクセス時間はスパンの状態に依存するので、スパンが多数存在する場合も計測を行った方がいいかも
• 次に、削除メソッド erace(uint)、挿入メソッド insert(uint, uchar)、置換メソッド replace(uint, uchr) を実装し、 パフォーマンス計測してみる。
• 削除所為：削除する位置でスパンが分割される

       buffer           ↓erace()
      ┏━━━━━━━━━━━━━━━━━━┓
      ┃                                    ┃
      ┗━━━━━━━━━━━━━━━━━━┛
               │                 
               │                     
               ↓                     
      ┌──────────────────┐
      │                                    │
      └──────────────────┘
                        
                        ↓
       buffer           
      ┏━━━━━━━━┯━━━━━━━┓
      ┃                │              ┃
      ┗━━━━━━━━┷━━━━━━━┛
               │               │
               │               └─┐
               ↓                   ↓
      ┌────────┬─┬───────┐
      │                │  │              │
      └────────┴─┴───────┘
       Original Buffer
  

• 挿入処理：挿入するデータは追加バッファに追加され、スパンが作成される

       buffer           ↓insert()
      ┏━━━━━━━━━━━━━━━━━━┓
      ┃                                    ┃
      ┗━━━━━━━━━━━━━━━━━━┛
               │                 
               │                     
               ↓                     
      ┌──────────────────┐
      │                                    │
      └──────────────────┘
                        
                        ↓
       buffer           
      ┏━━━━━━━━┯━┯━━━━━━━━━┓
      ┃                │  │                  ┃
      ┗━━━━━━━━┷━┷━━━━━━━━━┛
               │         │        │
               │         └────┼──────┐
               ↓                   ↓            ↓
      ┌────────┬─────────┐  ┌─┬───────┐
      │                │                  │  │  │              │
      └────────┴─────────┘  └─┴───────┘
       Original Buffer                           Add Buffer
  

• 置換処理：置換するデータは追加バッファに追加され、スパンが作成される

       buffer             ↓replace()
      ┏━━━━━━━━━━━━━━━━━━┓
      ┃                                    ┃
      ┗━━━━━━━━━━━━━━━━━━┛
               │                 
               │                     
               ↓                     
      ┌──────────────────┐
      │                                    │
      └──────────────────┘
                        
                        ↓
       buffer           
      ┏━━━━━━━━┯━┯━━━━━━━┓
      ┃                │  │              ┃
      ┗━━━━━━━━┷┯┷━━━━━━━┛
               │         │        │
               │         └────┼──────┐
               ↓                   ↓            ↓
      ┌────────┬─┬───────┐  ┌─┬───────┐
      │                │  │              │  │  │              │
      └────────┴─┴───────┘  └─┴───────┘
       Original Buffer                           Add Buffer
  

• ファイルをオープン後、先頭の100MBについて、100バイトごとに1バイト削除・挿入・置換する時間を計測。
  比較のために gap_vector も同様の計測を行った。 結果

  クラス	削除	挿入	置換	置換後連続参照
  CBuffer_GV	0.078 (12.9474 MB/sec)	0.296 (3.48076 MB/sec)	0.032 (31.875 MB/sec)	0.11 (927.273 MB/sec)
  CBuffer SO無	0.047 (21.4873 MB/sec)	0.125 (8.24243 MB/sec)	0.109 (9.3578 MB/sec)	1.531 (66.6231 MB/sec)

  
  
• 考察
  • データの移動が全く無いため、削除処理は gap_vector よりも高速
  • 挿入、置換処理は追加バッファへの処理のため、削除の２〜３倍の時間を要する
  • 置換後のシーケンシャルアクセス速度は、編集を行わない場合（62〜70MB/sec）と大差ない
    → スパンのフラグメント化による影響よりも、スパン経由でバッファにアクセスする処理が重いと考えられる
  • gap_vector の挿入処理はバッファメモリ拡張を行うので、その分削除より時間がかかる。
  • gap_vector の置換処理はデータを上書きするだけなので、削除・挿入より高速になる。

スワップアウトを行う編集可能仮想バッファ

• 追加バッファサイズが一定サイズを超えた場合は、内容をテンポラリファイルに書き出す（スワップアウト）ことで、 メモリ容量以上の編集を可能にする。
• 仮想メモリにおいては、NRU, FIFO, LRU などなど様々なスワップアウトアルゴリズムが存在する。
• 本実験では、サイズが同一の、書き込み用ブロック、読み出し用ブロックをそれぞれひとつずつ用意することにした。
  ※ 書込用ブロックサイズは読出用ブロックサイズの整数倍であればよい
• 読み出し用ブロックは先のリードオンリーバッファと同じように最後にアクセスされた部分のみをキャッシュすることとした。
  ※ これは、追加バッファへのアクセスが局所化されている場合には問題ないが、そうでないとパフォーマンス低下をまねく。
  ※ 追加バッファへのアクセスが局所化されるかどうかは編集状態に依存する。

             読出用block                   書込用block（オンメモリ）
                  ↓                              ↓
      ┌───┳━━━┳───┬───┬───┳━━━┓
      │      ┃      ┃      │      │      ┃      ┃
      └───┻━━━┻───┴───┴───┻━━━┛
                                              ↑
                                        m_memBufferOffset
  

      ┏━━━━━━━━━━━━━━━━┓
      ┃        CAddBuffer_tf           ┃
      ┠────────────────┨
      ┃m_size : size_t                 ┃    //  ファイルサイズ
      ┃m_memBufferOffset : uint        ┃    //   オンメモリバッファ 先頭オフセット
      ┃m_memBuffer : vect＜uchar＞     ┃    //   オンメモリバッファ
      ┃m_hFile : HANDLE                ┃    //  ファイルハンドル
      ┃m_viewOffset : uint             ┃    //  キャッシュバッファ先頭のファイル内オフセット
      ┃m_viewBuffer[VIEW_SIZE] : uchar ┃    //  キャッシュバッファ
      ┠────────────────┨
      ┗━━━━━━━━━━━━━━━━┛
  

    1: uchar CAddBuffer_tf::operator[](uint ix) const
    2: {
    3:     if( ix >= m_size ) return 0;
    4:     if( ix >= m_memBufferOffset )   //  オンメモリの書込用ブロックにデータがあれば読み出し
    5:         return m_memBuffer[ix - m_memBufferOffset];
    6:     if( !isViewAvailable(ix) &&     //  読出用ブロックにデータが無ければ
    7:         !makeViewBuffer(ix) )       //  読出用ブロックを移動（ビューにデータ転送）
    8:     {
    9:         return 0;
   10:     }
   11:     return m_viewBuffer[ix - m_viewOffset];     //  読出用ブロックのデータを返す
   12: }
  

    1: void CAddBuffer_tf::push_back(uchar v)
    2: {
    3:     if( 書込ブロックが満杯 ) {
    4:         書込みブロックをテンポラリファイルに追加;
    5:         m_memBufferOffset += SIZE_ON_MEMORY;
    6:         m_memBuffer.clear();
    7:     }
    8:     m_memBuffer.push_back(v);
    9:     ++m_size;
   10: }
  

• ファイルをオープン後、先頭の100MBについて、100バイトごとに1バイト削除・挿入・置換する時間を計測。 結果

  処理時間の計測結果を下表に示す。

  クラス	削除	挿入	置換	置換後連続参照
  CBuffer_GV	0.078 (12.9474 MB/sec)	0.296 (3.48076 MB/sec)	0.032 (31.875 MB/sec)	0.11 (927.273 MB/sec)
  CBuffer SO無	0.047 (21.4873 MB/sec)	0.125 (8.24243 MB/sec)	0.109 (9.3578 MB/sec)	1.531 (66.6231 MB/sec)
  CBuffer SO有	0.047 (21.4873 MB/sec)	0.109 (9.45233 MB/sec)	0.109 (9.3578 MB/sec)	1.531 (66.6231 MB/sec)

  
  
• 考察
  • スワップアウトを行う場合と行わない場合で、本実験ではほとんど差異はでなかった。
  • スワップアウト処理そのものが実行される頻度が少ないためと考えられる。
    本実験では 1MB のデータを追加バッファに追加しているので、1000000/4096. = 244 回の書出しが行われる。

総合評価

• 実務を想定したベンチマークにより、ViVi 3.04 で使用している gap_vector<uchar> バッファとのパフォーマンス比較を行う。
• 総合評価として、100メガバイトのファイルオープン、検索＆置換、ファイル別名保存 のタイムを計測する
  ファイル内容は 0x00, 0x01 ... 0xfe, 0xff, 0xfe, ... 0x01, 0x00 の三角パターンの繰り返しとする
  0xff を検索し、それを 0x00 に置換し、結果を別ファイルへ書き出すものとする。
• 総合評価補足として、空のバッファに上記のトライアングルパターンを書き込むのに要する時間も計測した。
• パフォーマンス計測結果は以下の通り。結果

  クラス	読込	検索・置換	書出	タイム合計	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

  
  
• gap_vector と比較した評価
  • gap_vector は最大1G程度しか読み込むことができないが、仮想バッファにより最大4Gまで取り扱い可能になった。
  • 通常の使用メモリ量は少ないが、編集を行った場合の増加は大きい
    
  • 実際にデータをメモリに転送しないのでファイルオープン自体は高速だが、参照・置換・書出は gap_vector ほど高速ではない
  → 特にシーケンシャルアクセスを高速化する必要があると考えられる。
  　　追加バッファの書出しブロックサイズを指定可能にするのも効果的かもしれない。

さいごに

まとめ：

• 最大容量4GBのバイナリエディタ用仮想バッファのインタフェースを決め、実装、パフォーマンス計測を行った。
• リードオンリーのオリジナルバッファ、追加バッファをクラス化し、ポリシー・委譲を利用することで、 見通しがよく拡張性に優れたクラス設計を実現できた。
• ピーステーブルデータ構造は、バッファを仮想化するためのよいデータ構造である。
• が、gap_vector と比べると低速なケースもあるので、高度なアルゴリズムの採用を含めたパフォーマンスチューニングが必要。

今後の課題・予定：

• undo/redo 機能実装
• パフォーマンスチューニング
  • イテレータ実装？
  • 複数バイトデータ転送？
  • 先読み？
  • 一間飛びブロック併合？
• 仮想関数を用いたクラスの動的切替え
• ViVi 3.05 への実装・評価・パフォーマンスチューニング
• ファイルロック問題対処

余談：

• 単体テストは非常に有効
• 複数の方法で実装を行ったクラスに対して、ランダムな操作を行い、結果を比較するのは、テスト自動化としていい作戦。

ご清聴、ありがとうございました。m(_ _)m