mallocの紹介
mimallocは、2019年にマイクロソフトリサーチによって公開され、オープンソース化された新しいメモリ割り当てライブラリです：
コード量が少ない、コアコード3500行未満
tcmalloc ~20k LOC
jemalloc ~25k LOC
市販されている他のメモリ・アロケータよりもはるかにパフォーマンスが優れています。
tcmallocより7%高速%
jemallocの14倍高速%
部分的に保存された3つのスライスのフリーリスト
データアクセスの局所性の向上
アクセス競合の低減
パフォーマンスを極限まで最適化するため、アロックおよびフリーの高速パスをサポートします。
アロケータがメンテナンス・タスクを処理するために適切なタイミングで高速パスから離れるように、タイム・ケイデンスを導入します。
メモリ割り当てと解放のメカニズム
mimallocのメモリ割り当てと解放メカニズムのハイライト：
極端なアイドルリストのスライス
アロケーションとリリースの主要な経路は深く最適化され、それ以外のケースはすべてジェネリック・メソッドに委ねられます。
ロックは使用せず、マルチスレッドのデータ競合はすべてアトミック操作で解決します。最悪の場合の上限はメタデータの約0.2パーセントで、実際に割り当てられた領域の16.7パーセント以上は無駄になりません。
フリーリストのスライス機構
フリーリスト
従来のメカニズムのようにサイズ・クラス全体ではなく、mimallocページごとに空きリストを維持します。
現在のページの空きリストが空でない限り、mallocは、ヒープに新たに空き領域があるかどうかに関係なく、このページにメモリを確保し続けることができます。
これにより、新しく割り当てられたメモリの空間的な局所性が向上し、新しく割り当てられたアドレスのほとんどが同じページに配置されるため、L2キャッシュのヒット率が向上します。
ローカルフリーリスト
大きなオブジェクトを解放すると、多くのオブジェクトを再帰的に解放する連鎖反応が起こり、最悪の場合、制御不能な空き時間が発生する可能性があります。そのため、解放オブジェクトの数を制限し、メモリが逼迫したときに解放されるように後続の解放オブジェクトをリストに置く必要があります。ただし、malloc_genericが一定間隔で呼び出されるようにする仕組みが必要です。
malloc_genericは、フリーリストが割り当てられたときに呼び出され、アトミック操作を使ってローカルのフリーリストを新しいフリーリストに変換します。
page->free = page->local_free; // move the list page->local_free = NULL; // and the local list is empty again- フリーリストは成長せず、一定時間後に必ず割り当てられるので、このメカニズムは、malloc_generic割り当てコードが常に一定の間隔で実行されるように、タイムケイデンスを導入することと等価であり、いくつかの時間のかかる操作のオーバーヘッドを均等にするために使用することができます：
- 参照カウント削減の遅延によるフリー
- 安定したハートビートの維持
- スレッドの空きリストからのメモリ奪還
スレッドリリースリスト
mimallocでは、mimallocページは "スレッドローカル "ヒープに属し、スレッドのすべてのメモリ確保は、ロックなしで、このスレッドローカルヒープから行われます。
しかし、どのスレッドもこのスレッドによって割り当てられたメモリを解放することができます。このスレッドがこのスレッドのローカルヒープ上のデータを解放するためにロックが必要ないことを保証するために、他のスレッドによって解放されたメモリを別のスレッドフリーリストに置くことによって、malloc の高速パス上のアトミック操作を減らすこともできます。
- 他のスレッドがこのスレッドによって割り当てられた領域を解放すると、atomic_push メソッドを呼び出して、対応するアドレスをこのスレッドの空きリストにアトミックに配置します：
void atomic_push( block_t** list, block_t* block ) { do { block->next = *list; } while (!atomic_compare_and_swap(list, block, block->next)); }各スレッドで操作されるオブジェクトは、メモリ解放時に個々の mimalloc ページにスライスされ、スレッド間の競合を減らします。
時々、スレッドの空きリストをアトミックに空きリストに移動し、リモートからの解放を一括処理します。
tfree = atomic_swap( &page->thread_free, NULL ); append( page->free, tfree );
具体的な実装
mallocの実装
void* malloc_small( size_t n ) { // 0 < n <= 1024 heap_t* heap = tlb; //スレッドローカルストレージポインタが指すスレッドローカルヒープ。 page_t* page = heap->pages_direct[(n+7)>>3]; // divide up by 8 block_t* block = page->free; //空きリスト if (block==NULL) return malloc_generic(heap,n); // slow path page->free = block->next; //空きリストのポインタを移動する page->used++; return block; }//slow path，mimallocメカニズムの実装は、このメソッドがたまに void* malloc_generic( heap_t* heap, size_t size ) { deferred_free(); // ユーザー定義メソッドを呼び出す // 既存のページを繰り返し処理する foreach( page in heap->pages[size_class(size)] ) { page_collect(page); //ページ上のスペースを取り戻す if (page->used - page->thread_freed == 0) { page_free(page); } else if (page->free != NULL) { return malloc(size); } } .... // 既存のページに空き領域がない場合、ページを再割り当てし、新しいページから領域を確保する。 } void page_collect(page) { page->free = page->local_free; // 空きリストをローカルの空きリストに設定する。 page->local_free = NULL; // 空のローカル空きリスト ... // アトミックにスレッド解放リストを処理する }無料の実施
void free( void* p ) { //pがあるセグメントを見つける。 segment_t* segment = (segment_t*)((uintptr_t)p & ~(4*MB)); if (segment==NULL) return; //pがあるページを見つける。 page_t* page = &segment->pages[(p - segment) >> segment->page_shift]; block_t* block = (block_t*)p; if (thread_id() == segment->thread_id) { // freeはこのスレッドが割り当てたメモリである。 block->next = page->local_free; page->local_free = block; page->used--; if (page->used - page->thread_freed == 0) page_free(page); } else { // freeは他のスレッドによって割り当てられたメモリである。 atomic_push( &page->thread_free, block); atomic_incr( &page->thread_freed ); } }
