この記事では、このような手法をいくつか検討します。 この記事の例は（たとえば、 これとは異なります）、new演算子とdelete演算子をオーバーロードしているため、構文構成が最小限になり、プログラムの変更が簡単になります。 プロセスで見つかった落とし穴についても説明します（もちろん、標準を最初から最後まで読んだ指導者は驚かないでしょう）。
0.メモリを手動で操作する必要がありますか？
まず、アロケーターがいかにスマートにメモリーの処理を高速化できるかを確認します。
C ++およびC＃の簡単なテストを作成します（C＃は、オブジェクトを世代別に分割したり、異なるサイズのオブジェクトに異なるプールを使用したりするなど、優れたメモリマネージャーで知られています）。
class Node { public: Node* next; }; // ... for (int i = 0; i < 10000000; i++) { Node* v = new Node(); }
class Node { public Node next; } // ... for (int l = 0; l < 10000000; l++) { var v = new Node(); }
例のすべての「球面真空」にもかかわらず、時間差は10倍であることが判明しました（62 ms対650 ms）。 さらに、c＃の例は終了し、c ++の良好なトーンの規則に従って、選択したオブジェクトを削除する必要があります。これにより、ギャップがさらに増加します（最大2580ミリ秒）。
1.オブジェクトプール
明らかな解決策は、OSからメモリの大きなブロックを取得し、それを等しいサイズの（ノード）ブロックに分割し、メモリを割り当てるときにプールからブロックを取得し、解放時にプールに戻すことです。 プールを整理する最も簡単な方法は、単一リンクリスト（スタック）を使用することです。
プログラムには最小限の介入のタスクがあるため、できることはBlockAllocの混合物をNodeクラスに追加することだけです。
class Node : public BlockAlloc<Node>
まず、OSまたはCランタイムから取り出す大きなブロック（ページ）のプールが必要です。 mallocおよびfree関数の上に整理できますが、効率を高めるため（抽象化の余分なレベルをスキップするため）、VirtualAlloc / VirtualFreeを使用します。 これらの関数は、4Kの倍数であるブロックにメモリを割り当て、64Kの倍数であるブロックにプロセスアドレス空間を予約します。 コミットオプションと予約オプションを同時に指定することで、もう1つの抽象化レベルをスキップし、1回の呼び出しでアドレス空間を予約し、メモリページを割り当てます。
PagePoolクラス
inline size_t align(size_t x, size_t a) { return ((x-1) | (a-1)) + 1; } //#define align(x, a) ((((x)-1) | ((a)-1)) + 1) template<size_t PageSize = 65536> class PagePool { public: void* GetPage() { void* page = VirtualAlloc(NULL, PageSize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); pages.push_back(page); return page; } ~PagePool() { for (vector<void*>::iterator i = pages.begin(); i != pages.end(); ++i) { VirtualFree(*i, 0, MEM_RELEASE); } } private: vector<void*> pages; };
次に、特定のサイズのブロックのプールを整理します
クラスブロックプール
template<class T, size_t PageSize = 65536, size_t Alignment = 8 /* sizeof(void*) */> class BlockPool : PagePool<PageSize> { public: BlockPool() : head(NULL) { BlockSize = align(sizeof(T), Alignment); count = PageSize / BlockSize; } void* AllocBlock() { // todo: lock(this) if (!head) FormatNewPage(); void* tmp = head; head = *(void**)head; return tmp; } void FreeBlock(void* tmp) { // todo: lock(this) *(void**)tmp = head; head = tmp; } private: void* head; size_t BlockSize; size_t count; void FormatNewPage() { void* tmp = GetPage(); head = tmp; for(size_t i = 0; i < count-1; i++) { void* next = (char*)tmp + BlockSize; *(void**)tmp = next; tmp = next; } *(void**)tmp = NULL; } };
コメント// todo：lock（this）は、スレッド間同期を必要とする場所をマークします（たとえば、EnterCriticalSectionまたはboost :: mutexを使用します）。
ページの「フォーマット」がブロックをプールに追加するためにFreeBlock抽象化を使用しない理由を説明します。 もし何かが
for (size_t i = 0; i < PageSize; i += BlockSize) FreeBlock((char*)tmp+i);
FIFOの原則に基づいたそのページは、「その逆」とマークされます。
行のプールから要求されたいくつかのブロックは、アドレスが減少します。 プロセッサは戻りたくないので、これからPrefetchを壊します（ UPD ：最新のプロセッサには関係ありません）。 ループでマークアップを行う場合
for (size_t i = PageSize-(BlockSize-(PageSize%BlockSize)); i != 0; i -= BlockSize) FreeBlock...
マークアップループはアドレスに戻ります。
これで準備が完了したので、不純物クラスを説明できます。
template<class T> class BlockAlloc { public: static void* operator new(size_t s) { if (s != sizeof(T)) { return ::operator new(s); } return pool.AllocBlock(); } static void operator delete(void* m, size_t s) { if (s != sizeof(T)) { ::operator delete(m); } else if (m != NULL) { pool.FreeBlock(m); } } // todo: implement nothrow_t overloads, according to borisko' comment // http://habrahabr.ru/post/148657/#comment_5020297 // Avoid hiding placement new that's needed by the stl containers... static void* operator new(size_t, void* m) { return m; } // ...and the warning about missing placement delete... static void operator delete(void*, void*) { } private: static BlockPool<T> pool; }; template<class T> BlockPool<T> BlockAlloc<T>::pool;
（s！= Sizeof（T））チェックが必要な理由を説明します
彼らはいつ発砲しますか？ 次に、ベースTから継承されたクラスが作成/削除されます。
相続人は通常のnew / deleteを使用しますが、BlockAllocを追加することもできます。 したがって、プログラムで何かを壊すことを恐れることなく、プールを使用するクラスを簡単かつ安全に決定します。 多重継承もこの混合物でうまく機能します。
できた BlockAllocノードを継承して再テストします。
テスト時間は120ミリ秒になりました。 5倍高速。 しかし、c＃では、アロケーターの方が優れています。 おそらくリンクリストだけではありません。 （newの直後にすぐにdeleteを呼び出して、データをキャッシュに入れて多くのメモリを無駄にしない場合、62ミリ秒になります。奇妙なことに、.NET CLRのように、解放されたローカル変数を対応するプールにすぐに返すように、 gcを待たずに）
2.コンテナとそのカラフルなコンテンツ
後者の寿命が親の寿命より長くないように、多くの異なる子オブジェクトをそれ自体に格納するクラスにしばしば遭遇しますか？
たとえば、NodeクラスとAttributeクラスで満たされたXmlDocumentクラス、およびノード内のテキストから取得したc-line（char *）にすることができます。 または、ディレクトリを再読み取りして変更されなくなったときに一度読み込まれるファイルマネージャ内のファイルとディレクトリのリスト。
はじめに示したように、削除は新規よりもコストがかかります。 記事の第2部の考え方は、Parentオブジェクトに関連付けられた大きなブロック内の子オブジェクトにメモリを割り当てることです。 親オブジェクトが削除されると、通常どおり、子にはデストラクタが呼び出されますが、メモリを返す必要はありません。1つの大きなブロックで解放されます。
PointerBumpAllocatorクラスを作成します。このクラスは、大きなブロックから異なるサイズの断片を噛み、古いブロックが使い果たされたときに新しい大きなブロックを割り当てることができます。
PointerBumpAllocatorクラス
template<size_t PageSize = 65536, size_t Alignment = 8 /* sizeof(void*) */> class PointerBumpAllocator { public: PointerBumpAllocator() : free(0) { } void* AllocBlock(size_t block) { // todo: lock(this) block = align(block, Alignment); if (block > free) { free = align(block, PageSize); head = GetPage(free); } void* tmp = head; head = (char*)head + block; free -= block; return tmp; } ~PointerBumpAllocator() { for (vector<void*>::iterator i = pages.begin(); i != pages.end(); ++i) { VirtualFree(*i, 0, MEM_RELEASE); } } private: void* GetPage(size_t size) { void* page = VirtualAlloc(NULL, size, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); pages.push_back(page); return page; } vector<void*> pages; void* head; size_t free; }; typedef PointerBumpAllocator<> DefaultAllocator;
最後に、オーバーロードされたnewと削除されたChildObjectの混合物について説明し、指定されたアロケーターへのアクセスを削除します。
template<class T, class A = DefaultAllocator> struct ChildObject { static void* operator new(size_t s, A& allocator) { return allocator.AllocBlock(s); } static void* operator new(size_t s, A* allocator) { return allocator->AllocBlock(s); } static void operator delete(void*, size_t) { } // *1 static void operator delete(void*, A*) { } static void operator delete(void*, A&) { } private: static void* operator new(size_t s); };
この場合、子クラスに不純物を追加することに加えて、newのすべての呼び出しを修正する必要があります（または「factory」パターンを使用します）。 new演算子の構文は次のとおりです。
新規（...演算子のパラメーター...）ChildObject（...コンストラクターパラメーター...）
便宜上、A＆またはA *を受け入れる2つの新しい演算子を定義しました。
アロケーターがメンバーとして親クラスに追加される場合、最初のオプションがより便利です。
node = new(allocator) XmlNode(nodename);
アロケーターが祖先（不純物）として追加される場合、2番目の方が便利です。
node = new(this) XmlNode(nodename);
ポインターとリンクが相互に変換されることは明らかです。これらのケースは分離され、余分なアイコンがなくなります。
deleteを呼び出すための特別な構文はありません;コンパイラは、オブジェクトを作成するために使用された新しい演算子に関係なく、標準の削除（* 1とマーク）を呼び出します。 つまり、削除構文は正常です。
delete node;
ChildObject（またはその後継）のコンストラクターで例外が発生した場合、このオブジェクトの作成時に使用されたnew演算子の署名に対応する署名でdeleteが呼び出されます（最初のパラメーターsize_tはvoid *に置き換えられます）。
new演算子をprivateセクションに配置すると、アロケーターを指定せずにnewを呼び出すことを防ぎます。
Allocator-ChildObjectペアの完全な使用例を次に示します。
例
class XmlDocument : public DefaultAllocator { public: ~XmlDocument() { for (vector<XmlNode*>::iterator i = nodes.begin(); i != nodes.end(); ++i) { delete (*i); } } void AddNode(char* content, char* name) { char* c = (char*)AllocBlock(strlen(content)+1); strcpy(c, content); char* n = (char*)AllocBlock(strlen(name)+1); strcpy(n, content); nodes.push_back(new(this) XmlNode(c, n)); } class XmlNode : public ChildObject<XmlNode, XmlDocument> { public: XmlNode(char* _content, char* _name) : content(_content), name(_name) { } private: char* content; char* name; }; private: vector<XmlNode*> nodes; };
おわりに この記事は1.5年前にサンドボックス用に書かれましたが、残念ながらモデレーターはそれを嫌いました。