JSONデコード: C++: 高速化準備(専用のallocator作成)

C++のデフォルトのnewは、小さいサイズのメモリを大量に割り当てるのが遅いということは有名(?)なので、JSONパーサ用に、専用のallocatorクラスを作成することにした。

今回作成したallocatorクラスのテンプレートとしては、『C++編（標準ライブラリ）　第２８章　アロケータ』にあるものを参照させてもらった。

メインのパーサの方のコードとまとめてしまおうかとも思ったのだが、allocatorクラスだけでもそこそこの量があるので、別々の記事として扱うことにする。

メモリ割り当て戦略

今回採用したメモリ割り当て戦略は以下の通り。

初めに、(ある程度)大量のメモリをまとめて確保(new)しておく。
割り当て要求がきたら、1で確保したメモリブロックの先頭から順に必要なサイズを渡す。
- なお、既存のメモリブロックを使いきってしまった場合は、新たなメモリブロックを確保する。
メモリブロックは、JSONパースメソッド(json::parser.parse)呼び出し毎に、初期化し再利用する。(=再び先頭から割り当てるようにする)
- ※json::parser.parseが返す値(json::value)は、次回のjson::parser.parse呼び出しまでしか有効ではない。

要は、「メモリを大量に確保しておき、そこから順番に割り当てる」、というだけの単純な方法だ。

これだと、メモリ割り当てがO(1)で行える。
また、メモリブロックを再利用するための特別な処理も必要ない*1のでnewしたオブジェクトに対してdeleteを呼び出す必要がない、という利点もある。
※ ↑は一般的には嘘。deleteには、メモリ解放とデストラクタ関数呼び出しの役割があるので、前者が必要なくても後者のためにdeleteは呼ぶ必要がある。ただし、今回作成したJSONパーサのvalueクラスはデストラクタ関数を呼び出す必要が無いので、deleteを呼び出さなくても問題がない。(実装依存の最適化。std::listの実装によっては問題あり?)

ただし、大きな制限として、json::parser.parseメソッドが返すjson::valueの値は、次の同メソッド呼び出しまでの間しか有効ではないので、永続的に参照したい場合は、パース結果のjson::valueを別のメモリ領域にコピーするか、パースごとに異なるjson::parserインスタンスを用いる必要がある。(メモリブロックはjson::parser単位で保持・管理されているため。)

ついでに(STLのコンテナに自作allocatorを渡す場合の云々)

allocatorクラスの実装の参考させてもらった『C++編（標準ライブラリ）　第２８章　アロケータ』の中には、次のような記述があった。

実際には、指定したアロケータを、STLのコンテナが使用してくれるかどうかは別問題です。std::vectorやstd::deque を除けば、他のコンテナは内部に、各要素を表現するためのクラスや構造体を持ち、それらを連結するためにポインタを保持しています。例えば、std::listは双方向リストになっているので、各要素の構造体と、ある要素の前後の要素を連結するためのポインタを持ちます（双方向リストについては、アルゴリズムとデータ構造編第１２章を参照）。std::listに新たな要素が追加され、新しく領域を確保する必要があるとき、実際に確保したいのはアロケータのテンプレート引数に指定した型ではなく、各要素を表現する構造体の型であるはずです。実際にstd::listを宣言するとき、

std::list > nums;

のように書きますが、この場合、独自のアロケータCMyAllocatorが確保する型はint型な訳です。つまり、int型用のアロケータなので、各要素を表現する構造体の型とは一致するはずがありません。従って、std::listは、プログラマがせっかく定義したアロケータを使うことがないことになります。

つまりは、「std::list(など)に独自のallocatorを渡しても使われない」ということが云われているのだと思うが、g++を使って試した限りは、そんなことはなかった。

例えば次のようなコードを見てみる。

// MyClass型の要素を持つstd::listを定義
// アロケータにはMyAllocator<MyClass>を渡す
typedef std::list<MyClass, MyAllocator<MyClass> > my_list;

main() {
  my_list list;

  // ※1 要素を追加するために、どんなアロケータが使われている?
  list.push_back(MyClass()); 
}

/** ※1 **
ここでは、listにノードを追加するために(ノード用のメモリを確保するために)、
MyAllocator<std::_List_node<MyClass> >.allocateというメソッドが呼び出されていた。

使われているクラスは、MyAllocator<std::_List_node<MyClass> >。

つまり、型は違う(MyAllocator<MyClass>ではない)が、アロケータとしては、ちゃんと自分が指定したクラスが使われている。

---------------
(想像だが)std::listは、下のような感じの定義になっているのだろうか?
namespace std{
  template <class T, class Allocator>
  class list {
    typedef Allocator::rebind<_List_node<Allocator::value_type> >::other node_allocator;
    
    ...
  };
}
*/

コメントにある通り、特殊化に使われている型は違うが、自分が指定したallocatorクラス(のテンプレート)がちゃんと使われている。
そして、allocatorの場合、型の情報は大抵、割り当てるメモリのサイズを知るため(sizeof(型))にしか使われないと思うので、実際に使われる型が自分が(ソースコードで明示的に)指定した型と異なっていても、ほとんど問題はないのではないかと思う。

とはいっても、これはあくまでもg++(4.2.4)での挙動で、しかも簡単にしか試していないので、あまり確かなものではないが...。

ソースコード

残りは、ソースコード。

// json_allocator.h
#ifndef JSON_ALLOCATOR_H

#include <vector>

namespace json{
  // チャンク(メモリブロック)を保持する構造体
  struct chunk{
    chunk(unsigned init_size=0x8000) 
      :offset(0), max_chunk_size(init_size) 
    {
      chunks.push_back(new char[max_chunk_size]);
    }
    ~chunk() {
      for(unsigned i=0; i < chunks.size(); i++)
        delete [] chunks[i];
    }
    
    std::vector<char*> chunks;         // チャンクの配列
    unsigned           max_chunk_size; // 一番大きいチャンク(= chunks.back())のサイズ
    unsigned           offset;         // 未使用のメモリ開始位置
  };

  template <class T>
  class allocator {
  public:
    /**********/
    /* 型関連 */
    // 型定義
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
  
    // アロケータをU型にバインドする
    template <class U>
    struct rebind { typedef allocator<U> other; };
  
    /******************/
    /* コンストラクタ */
    allocator(chunk& cnk) : cnk_(cnk) {}

    template <class U> allocator(const allocator<U>& src) 
      : cnk_(const_cast<chunk&>(src.get_chunk())) {}


    /*******************************************/
    /* STLのアロケータクラスに必要なメソッド群 */
    // メモリを割り当てる
    pointer allocate(unsigned num){
      if(cnk_.offset+sizeof(T)*num >= cnk_.max_chunk_size){
        // メモリが足りない場合は、chunkを増やす
        cnk_.max_chunk_size *= 2;
        cnk_.chunks.push_back(new char [cnk_.max_chunk_size]);
        cnk_.offset=0;
        
        return allocate(num); // もう一度allocate
      }
      
      // offsetから、sizeof(T)*num分だけ、メモリを割り当てる
      // XXX: ここでコンストラクタを呼び出すのは間違っている気がする(2009/11/19)
      pointer ptr = new (cnk_.chunks.back()+cnk_.offset) T[num];
      cnk_.offset += sizeof(T)*num;
      return ptr;      
    }

    // 割当て済みの領域を初期化する
    void construct(pointer p, const T& value) {
      new( (void*)p ) T(value);
    }

    // メモリを解放する
    // ※ 何も行わない
    void deallocate(pointer p, unsigned num) {}

    // 初期化済みの領域を削除する
    void destroy(pointer p) { p->~T(); }


    /**************************/
    /* JSONに必要なメソッド群 */
    // 未使用メモリ開始位置(offset)を0にリセットする
    void reset() {
      cnk_.offset = 0;
      if(cnk_.chunks.size() > 1) {
        // チャンクが複数ある場合は、一番最後のもの以外はdeleteする
        char *tmp = cnk_.chunks.back();
        for(unsigned i=0; i < cnk_.chunks.size()-1; i++)
          delete [] cnk_.chunks[i];
        cnk_.chunks.clear();
        cnk_.chunks.push_back(tmp);
      }
    }
    
    // chunkの未使用メモリ開始位置(offset)を設定する
    // JSONのparse_stringのために、特別に用意
    void set_tail(char* ptr) {
      cnk_.offset = ptr-cnk_.chunks.back();
    }

    // 引数のポインタ(ptr)が、あらかじめ確保しているメモリブロックの範囲内かどうかを判定する
    // 範囲外なら、trueを返す
    // ※ 上限のみをチェックしている
    bool out_of_range(char* ptr) {
      return cnk_.chunks.back()+cnk_.max_chunk_size <= ptr;
    }
    
    // 2番目のコンストラクタで使用
    const chunk& get_chunk() const { return cnk_; }    

  private:
    chunk& cnk_;
  };
}

#endif

*1:メモリブロックを再利用するには、未使用領域の開始位置を指すポインタ(インデックス)を0に設定しさえすれば良い