Allocator
14077 ワード
C++ allocator
C++のallocatorについて話します.C++STLでは多くのコンテナ(containers)が定義されており、各コンテナの2番目のテンプレートパラメータはallocatorタイプであることが知られています.例えばVC 10ではvectorクラスのテンプレートは次のように宣言されています.
template> class vector
しかし、allocatorをカスタマイズする人はほとんどいません.デフォルトのallocatorはもう十分です.二つ目は、確かにどう使えばいいか分からない.一般的にallocatorを再定義する必要はありません.カスタマイズの方法は、主にメモリ割り当てに関連する操作のパフォーマンスを向上させるためです.STLが提供する方式は性能が十分だ.実際、windowsプラットフォームでは、newの下位実装はC言語に基づくmalloc関数である.malloc関数ファミリーは、Windows HeapCreate、HeapAlloc、HeapFreeなどの関連APIに基づいて実現される(具体的には、%VSSInstallFolder%VCcrtsrcディレクトリのheapnit.c、malloc.c、new.cppなどの関連関数を参照).
まず性能の問題を抜きにして、私たちはどのように自分のallocatorを実現するかを見てみましょう.
C++2003標準ドキュメントではallocatorについての説明は多くありませんが、20.1ぐらいです.5 Allocator requirementsと20.4.1 The default allocatorの2つの主要な位置.内容は多くありませんが、自分のallocatorを書くのに十分です.
Allocator requirementsによると、typedefsをいくつか提供する必要があります.
ここには比較的理解しにくいものがあります:rebind.C++標準ではrebindをこう説明しています.
The member class template rebind in the table above is effectively a typedef template: if the name Allocator is bound to SomeAllocator, then
Allocator::rebind::other is the same type as SomeAllocator.
どういう意味だ?簡単な例で説明できます.
学校では、スタック、一方向リスト、ツリーなどのデータ構造を学んだことがあります.スタックとリストを比較して、何か大きな違いがあるか見てみましょう.データ構造の違いを除いてallocatorの観点から,スタックは格納要素自体であるが,リストは実際には直接格納要素自体ではないことが分かった.リストを維持するには、少なくともnextというポインタが必要です.したがって、intを保存するリストリストリストであるが、リストに格納されるオブジェクトはint自体ではなく、intを保存し、前後の要素を指すポインタも含むデータ構造である.ではlist>はどのようにしてこの内部データ構造を割り当てるかを知っていますか?結局allocatorはintタイプを割り当てる空間しか知らない.これがrebindが解決しなければならない問題です.allocator::rebind()では、割り当てのために作成できます.Nodeタイプスペースのディスペンサです.
次に、他のインタフェースを提供します.The default allocatorの説明に従って、次のインタフェースを提供します.
valのアドレスを返す
pointer allocate(size_type cnt, CHxAllocator::const_pointer pHint = 0)
スペースを割り当てる.mallocに似ています.pHintは無視でき,主にクラスライブラリに使用され,性能向上に用いられる.
void deallocate(pointer p, size_type n)
フリースペース、freeに似ています.
size_type max_size() const throw()
割り当て可能な最大数.
void construct(pointer p, const_reference val)
アドレスpが指す空間にvalを用いて埋め込む.構造関数への呼び出しを保証するためにpalcement newを使用する必要があります.
void destroy(pointer p)
pが指すメモリブロックの内容を解析する.一般に、調査構造関数を表示することによって実行されます.
allocator() throw () allocator(const_reference) throw () template allocator(CHxAllocator <_other> const&) throw() ~CHxAllocator() throw()
各種構造関数と解析関数
これらの関数をどのように実現するかは、標準ライブラリの実装を写すだけでいいです.cのmallocとfreeで実現したい場合は、次のように書くこともできます.
基本的には、私たちは簡単に自分のallocatorを実現しました.また、これらの最も主要なインタフェース関数に加えて、比較オペレータ==と!=、しかし、これらの手紙は標準ドキュメントに基づいてtrueとfalseを直接返します.
冒頭で述べたように、allocatorを書き換える主な目的は性を高めることです.では、どのようにしてパフォーマンスを向上させることができますか?WindowsのHeapXXXXスタックメモリAPIを直接使用しますか?実は、自分で使うと、性能の向上は明らかではありません.newを通じて、mallocを通じて、最後にHeapAllocを通じて直接HeapAllocを呼び出すよりも多くの言葉を使わないからです.高性能のallocatorをどのように実現するかは、memory poolの考え方を借りる必要があります.また,侯捷のstlソース剖析ではSGI STLが類似の考え方を用いて実現したallocを解析した.
C++のallocatorについて話します.C++STLでは多くのコンテナ(containers)が定義されており、各コンテナの2番目のテンプレートパラメータはallocatorタイプであることが知られています.例えばVC 10ではvectorクラスのテンプレートは次のように宣言されています.
template
しかし、allocatorをカスタマイズする人はほとんどいません.デフォルトのallocatorはもう十分です.二つ目は、確かにどう使えばいいか分からない.一般的にallocatorを再定義する必要はありません.カスタマイズの方法は、主にメモリ割り当てに関連する操作のパフォーマンスを向上させるためです.STLが提供する方式は性能が十分だ.実際、windowsプラットフォームでは、newの下位実装はC言語に基づくmalloc関数である.malloc関数ファミリーは、Windows HeapCreate、HeapAlloc、HeapFreeなどの関連APIに基づいて実現される(具体的には、%VSSInstallFolder%VCcrtsrcディレクトリのheapnit.c、malloc.c、new.cppなどの関連関数を参照).
まず性能の問題を抜きにして、私たちはどのように自分のallocatorを実現するかを見てみましょう.
C++2003標準ドキュメントではallocatorについての説明は多くありませんが、20.1ぐらいです.5 Allocator requirementsと20.4.1 The default allocatorの2つの主要な位置.内容は多くありませんが、自分のallocatorを書くのに十分です.
Allocator requirementsによると、typedefsをいくつか提供する必要があります.
1: template <typename T> 2: class CHxAllocator 3: { 4: public: 5: // typedefs... 6: typedef T value_type; 7: typedef value_type* pointer; 8: typedef value_type& reference; 9: typedef value_type const* const_pointer; 10: typedef value_type const& const_reference; 11: typedef size_t size_type; 12: typedef ptrdiff_t difference_type; 13: 14: // rebind... 15: template <typename _other> struct rebind { typedef CHxAllocator<_other> other; }; 16: };ここには比較的理解しにくいものがあります:rebind.C++標準ではrebindをこう説明しています.
The member class template rebind in the table above is effectively a typedef template: if the name Allocator is bound to SomeAllocator, then
Allocator::rebind::other is the same type as SomeAllocator.
どういう意味だ?簡単な例で説明できます.
学校では、スタック、一方向リスト、ツリーなどのデータ構造を学んだことがあります.スタックとリストを比較して、何か大きな違いがあるか見てみましょう.データ構造の違いを除いてallocatorの観点から,スタックは格納要素自体であるが,リストは実際には直接格納要素自体ではないことが分かった.リストを維持するには、少なくともnextというポインタが必要です.したがって、intを保存するリストリストリストであるが、リストに格納されるオブジェクトはint自体ではなく、intを保存し、前後の要素を指すポインタも含むデータ構造である.ではlist>はどのようにしてこの内部データ構造を割り当てるかを知っていますか?結局allocatorはintタイプを割り当てる空間しか知らない.これがrebindが解決しなければならない問題です.allocator::rebind
次に、他のインタフェースを提供します.The default allocatorの説明に従って、次のインタフェースを提供します.
pointer address(reference val) const
const_pointer address(const_reference val) constvalのアドレスを返す
pointer allocate(size_type cnt, CHxAllocator::const_pointer pHint = 0)
スペースを割り当てる.mallocに似ています.pHintは無視でき,主にクラスライブラリに使用され,性能向上に用いられる.
void deallocate(pointer p, size_type n)
フリースペース、freeに似ています.
size_type max_size() const throw()
割り当て可能な最大数.
void construct(pointer p, const_reference val)
アドレスpが指す空間にvalを用いて埋め込む.構造関数への呼び出しを保証するためにpalcement newを使用する必要があります.
void destroy(pointer p)
pが指すメモリブロックの内容を解析する.一般に、調査構造関数を表示することによって実行されます.
allocator() throw () allocator(const_reference) throw () template allocator(CHxAllocator <_other> const&) throw() ~CHxAllocator() throw()
各種構造関数と解析関数
これらの関数をどのように実現するかは、標準ライブラリの実装を写すだけでいいです.cのmallocとfreeで実現したい場合は、次のように書くこともできます.
1: pointer allocate(size_type cnt, CHxAllocator<void>::const_pointer pHint = 0) 2: { 3: UNREFERENCED_PARAMETER(pHint); 4: 5: if (cnt <= 0) 6: { 7: return 0 ; 8: } 9: 10: void* pMem = nullptr ; 11: if (max_size() < cnt || (pMem = malloc(cnt * sizeof(value_type))) == NULL) 12: { 13: throw std::bad_alloc(0); 14: } 15: 16: return static_cast (pMem); 17: } 18: 19: void deallocate(pointer p, size_type) 20: { 21: free(p); 22: } 23: 24: void construct(pointer p, const_reference val) 25: { 26: :: new ((void *)p) T(val); 27: } 28: 29: void destroy(pointer p) 30: { 31: p->~T(); 32: }基本的には、私たちは簡単に自分のallocatorを実現しました.また、これらの最も主要なインタフェース関数に加えて、比較オペレータ==と!=、しかし、これらの手紙は標準ドキュメントに基づいてtrueとfalseを直接返します.
冒頭で述べたように、allocatorを書き換える主な目的は性を高めることです.では、どのようにしてパフォーマンスを向上させることができますか?WindowsのHeapXXXXスタックメモリAPIを直接使用しますか?実は、自分で使うと、性能の向上は明らかではありません.newを通じて、mallocを通じて、最後にHeapAllocを通じて直接HeapAllocを呼び出すよりも多くの言葉を使わないからです.高性能のallocatorをどのように実現するかは、memory poolの考え方を借りる必要があります.また,侯捷のstlソース剖析ではSGI STLが類似の考え方を用いて実現したallocを解析した.