Semua implementasi dalam satu file header .h: [fast_mem_pool.h]
Chips, mengapa pengalokasi ini lebih baik daripada ratusan yang serupa - di bawah batas.
Beginilah cara kerja sepeda saya.
1) Dalam build Rilis, tidak ada mutex dan tidak ada siklus tunggu untuk atom - tetapi pengalokasi bersifat siklik, dan terus-menerus meregenerasi sumber daya saat dilepaskan oleh utas. Bagaimana dia melakukannya?
Setiap alokasi RAM yang diberikan FastMemPool melalui fmalloc sebenarnya lebih untuk sebuah header:
struct AllocHeader {
// : tag_this = this + leaf_id
uint64_t tag_this { 2020071700 };
// :
int size;
// :
int leaf_id { -2020071708 };
};
Header ini selalu dapat diperoleh dari pointer yang dimiliki oleh pengguna dengan memutar mundur dari pointer (res_ptr) sizeof (AllocHeader):
Dengan isi header AllocHeader, metode ffree (void * ptr) mengenali alokasinya dan mencari tahu di mana lembar memori buffer melingkar dikembalikan :
void ffree(void *ptr)
{
char *to_free = static_cast<char *>(ptr)
- sizeof(AllocHeader);
AllocHeader *head = reinterpret_cast<AllocHeader *>(to_free);
Ketika pengalokasi diminta untuk mengalokasikan memori, pengalokasi melihat pada lembar larik lembar saat ini untuk melihat apakah pengalokasi dapat memotong ukuran yang diperlukan + ukuran ukuran tajuk (AllocHeader).
Dalam pengalokasi, lembar memori Leaf_Cnt dipesan terlebih dahulu, setiap lembar ukuran Leaf_Size_Bytes (semuanya tradisional di sini). Dalam mencari peluang alokasi, metode fmalloc (std :: size_t alokasi_size) akan melingkari daun dari array leaf_array, dan jika semuanya sibuk di mana-mana, maka, asalkan flag Do_OS_malloc diaktifkan, itu akan mengambil memori dari sistem operasi lebih besar dari ukuran yang diperlukan oleh sizeof (AllocHeader) - di luar memori diambil dari buffer melingkar internal atau dari OS, pengalokasi selalu membuat header dengan informasi layanan. Jika pengalokasi kehabisan memori dan Do_OS_malloc == false flag, maka fmalloc akan mengembalikan nullptr - perilaku ini berguna untuk mengontrol beban (misalnya, melewati frame dari kamera video saat modul pemrosesan frame tidak mengikuti FPS kamera).
Bagaimana bersepeda diterapkan
Pengalokasi siklik dirancang untuk tugas-tugas siklik - tugas tidak boleh bertahan selamanya. Misalnya, dapat berupa:
- alokasi untuk sesi pengguna
- pemrosesan bingkai aliran video untuk analitik video
- kehidupan unit tempur dalam game
Karena jumlah memory sheets dalam larik leaf_array bisa berapapun jumlahnya, maka pada limit tersebut dimungkinkan untuk membuat halaman untuk kemungkinan jumlah pasukan yang secara teori di dalam game, sehingga dengan kondisi unit yang putus, kita dijamin akan mendapatkan lembar memory gratis. Dalam praktiknya, untuk analitik video, 16 lembar besar biasanya cukup untuk saya, di mana beberapa lembar pertama disumbangkan untuk alokasi non-siklik jangka panjang saat detektor diinisialisasi.
Bagaimana keamanan benang diterapkan
Larik lembar alokasi berfungsi tanpa mutex ... Perlindungan terhadap kesalahan seperti "data race" dilakukan sebagai berikut:
char *buf;
// available == offset
std::atomic<int> available { Leaf_Size_Bytes };
// allocated ==
std::atomic<int> deallocated { 0 };
Setiap lembar memori memiliki 2 penghitung:
- tersedia yang diinisialisasi dengan ukuran Leaf_Size_Bytes. Dengan setiap alokasi, penghitung ini berkurang, dan penghitung yang sama berfungsi sebagai offset relatif terhadap awal lembar memori == memori dialokasikan dari akhir buffer:
result_ptr = leaf_array[leaf_id].buf + available_after;
- deallocated diinisialisasi {0} menjadi nol, dan dengan setiap deallocation pada sheet ini (saya belajar dari AllocHeader tentang sheet atau OS mana kesepakatan tersebut ditangani) penghitung ditingkatkan dengan volume yang dirilis:
const int deallocated = leaf_array[head->leaf_id].deallocated.fetch_add(real_size, std::memory_order_acq_rel) + real_size;
Segera setelah penghitung seperti ini (deallocated == (Leaf_Size_Bytes - tersedia)) cocok, ini berarti bahwa semua yang telah dialokasikan sekarang dilepaskan dan Anda dapat mengatur ulang sheet ke keadaan semula, tetapi ini adalah poin halus: apa yang akan terjadi jika setelah keputusan untuk mengatur ulang sheet kembali ke aslinya, seseorang mengalokasikan sebagian kecil memori dari sheet ... Untuk mengecualikan ini, gunakan pemeriksaan bandingkan_exchange_strong:
if (deallocated == (Leaf_Size_Bytes - available))
{ // ,
// , , Leaf
if (leaf_array[head->leaf_id].available
.compare_exchange_strong(available, Leaf_Size_Bytes))
{
leaf_array[head->leaf_id].deallocated -= deallocated;
}
}
Lembar memori disetel ulang ke keadaan semula hanya jika pada saat penyetelan ulang keadaan yang sama dari penghitung yang tersedia tetap ada, yaitu pada saat keputusan dibuat. Ta-daa !!!
Bonus yang bagus adalah Anda dapat menangkap bug berikut menggunakan header AllocHeader dari setiap alokasi:
- alokasi ulang
- deallocation memori orang lain
- buffer overflow
- akses ke area memori orang lain
Fitur kedua diterapkan pada peluang ini.
2) Kompilasi Debug memberikan informasi yang tepat di mana deallokasi sebelumnya selama redeallocation: nama file, nomor baris kode, nama metode. Ini diimplementasikan dalam bentuk dekorator di sekitar metode dasar (fmallocd, ffreed, check_accessd - versi debug dari metode memiliki d di bagian akhir):
/**
* @brief FFREE - free
* @param iFastMemPool - FastMemPool
* @param ptr - fmaloc
*/
#if defined(Debug)
#define FFREE(iFastMemPool, ptr) \
(iFastMemPool)->ffreed (__FILE__, __LINE__, __FUNCTION__, ptr)
#else
#define FFREE(iFastMemPool, ptr) \
(iFastMemPool)->ffree (ptr)
#endif
Makro preprocessor digunakan:
- __FILE__ - c ++ file sumber
- __LINE__ - nomor baris di file sumber c ++
- __FUNCTION__ - nama fungsi tempat ini terjadi
Informasi ini disimpan sebagai korespondensi antara penunjuk alokasi dan informasi alokasi di mediator:
struct AllocInfo {
// : , , :
std::string who;
// true - , false - :
bool allocated { false };
};
std::map<void *, AllocInfo> map_alloc_info;
std::mutex mut_map_alloc_info;
Karena kecepatan tidak begitu penting untuk debugging, mutex digunakan untuk melindungi std :: map standar. Parameter template (bool Raise_Exeptions = DEF_Raise_Exeptions) memengaruhi apakah akan menampilkan Exception pada kesalahan.
Bagi mereka yang menginginkan kenyamanan maksimal dalam build Release, Anda dapat menyetel flag DEF_Auto_deallocate, lalu semua alokasi malloc OS akan ditulis (sudah di bawah mutex di std :: set <>) dan dirilis di destruktor FastMemPool (digunakan sebagai pelacak alokasi).
3)Untuk menghindari kesalahan seperti "buffer overflow", saya merekomendasikan penggunaan pemeriksaan FastMemPool :: check_access sebelum mulai bekerja dengan memori yang dialokasikan. Sementara sistem operasi hanya mengeluh ketika Anda masuk ke RAM orang lain, fungsi check_access (atau makro FCHECK_ACCESS) menghitung oleh header AllocHeader apakah akan ada kelebihan alokasi yang diberikan:
/**
* @brief check_access -
* @param base_alloc_ptr - FastMemPool
* @param target_ptr -
* @param target_size - ,
* @return - true FastMemPool
*/
bool check_access(void *base_alloc_ptr, void *target_ptr, std::size_t target_size)
// :
if (FCHECK_ACCESS(fastMemPool, elem.array,
&elem.array[elem.array_size - 1], sizeof (int)))
{
elem.array[elem.array_size - 1] = rand();
}
Mengetahui penunjuk alokasi awal, Anda selalu bisa mendapatkan header, dari header kami mengetahui ukuran alokasi, dan kemudian kami menghitung apakah elemen target akan berada dalam alokasi awal. Cukup dengan memeriksa sekali sebelum memulai siklus pemrosesan pada akses maksimum yang memungkinkan secara teoritis. Sangat mungkin bahwa nilai-nilai yang membatasi akan menembus batas-batas alokasi (misalnya, dalam perhitungan diasumsikan bahwa beberapa variabel hanya dapat berjalan dalam kisaran tertentu karena proses fisika, dan oleh karena itu Anda tidak melakukan pemeriksaan untuk melanggar batas alokasi).
Lebih baik memeriksa sekali daripada membunuh seminggu kemudian mencari seseorang yang sesekali menulis data acak ke struktur Anda ...
4) Menyetel kode templat default pada waktu kompilasi melalui CMake.
CmakeLists.txt berisi parameter yang dapat dikonfigurasi, misalnya:
set(DEF_Leaf_Size_Bytes "65536" CACHE PATH "Size of each memory pool leaf")
message("DEF_Leaf_Size_Bytes: ${DEF_Leaf_Size_Bytes}")
set(DEF_Leaf_Cnt "16" CACHE PATH "Memory pool leaf count")
message("DEF_Leaf_Cnt: ${DEF_Leaf_Cnt}")
Ini membuatnya sangat mudah untuk mengedit parameter di QtCreator:
atau CMake GUI:
Kemudian parameter diteruskan ke kode selama kompilasi sebagai berikut:
set(SPEC_DEFINITIONS
${CMAKE_SYSTEM_NAME}
${CMAKE_BUILD_TYPE}
${SPEC_BUILD}
SPEC_VERSION="${Proj_VERSION}"
DEF_Leaf_Size_Bytes=${DEF_Leaf_Size_Bytes}
DEF_Leaf_Cnt=${DEF_Leaf_Cnt}
DEF_Average_Allocation=${DEF_Average_Allocation}
DEF_Need_Registry=${DEF_Need_Registry}
)
#
target_compile_definitions(${TARGET} PUBLIC ${TARGET_DEFINITIONS})
dan di kode menimpa nilai template di Default:
#ifndef DEF_Leaf_Size_Bytes
#define DEF_Leaf_Size_Bytes 65535
#endif
template<int Leaf_Size_Bytes = DEF_Leaf_Size_Bytes,
int Leaf_Cnt = DEF_Leaf_Cnt,
int Average_Allocation = DEF_Average_Allocation,
bool Do_OS_malloc = DEF_Do_OS_malloc,
bool Need_Registry = DEF_Need_Registry,
bool Raise_Exeptions = DEF_Raise_Exeptions>
class FastMemPool
{
// ..
};
Jadi template pengalokasi dapat dengan nyaman disesuaikan dengan mouse dengan mengaktifkan / menonaktifkan kotak centang parameter CMake.
5) Agar dapat menggunakan pengalokasi di kontainer STL dalam file .h yang sama, kapabilitas std :: alokator diimplementasikan sebagian di template FastMemPoolAllocator:
// compile time :
std::unordered_map<int, int, std::hash<int>,
std::equal_to<int>,
FastMemPoolAllocator<std::pair<const int, int>> > umap1;
// runtime :
std::unordered_map<int, int> umap2(
1024, std::hash<int>(),
std::equal_to<int>(),
FastMemPoolAllocator<std::pair<const int, int>>());
Contoh penggunaan dapat ditemukan di sini: test_allocator1.cpp dan test_stl_allocator2.cpp .
Misalnya, pekerjaan konstruktor dan destruktor pada alokasi:
bool test_Strategy()
{
/*
* Runtime
* ( )
*/
using MyAllocatorType = FastMemPool<333, 33>;
// instance of:
MyAllocatorType fastMemPool;
// inject instance:
FastMemPoolAllocator<std::string,
MyAllocatorType > myAllocator(&fastMemPool);
// 3 :
std::string* str = myAllocator.allocate(3);
// :
myAllocator.construct(str, "Mother ");
myAllocator.construct(str + 1, " washed ");
myAllocator.construct(str + 2, "the frame");
//-
std::cout << str[0] << str[1] << str[2];
// :
myAllocator.destroy(str);
myAllocator.destroy(str + 1);
myAllocator.destroy(str + 2);
// :
myAllocator.deallocate(str, 3);
return true;
}
6) Terkadang dalam proyek besar Anda membuat semacam modul, semuanya diuji secara menyeluruh - berfungsi seperti jam tangan Swiss. Modul Anda termasuk dalam detektor, bertempur - dan terkadang, sekali sehari, pustaka mulai jatuh ke dalam dump. Setelah menjalankan dump pada debugger, Anda menemukan bahwa di salah satu loop traversal pointer, alih-alih nullptr, seseorang menulis angka 8 ke pointer Anda - dengan pergi ke pointer ini Anda secara alami membuat marah sistem operasi.
Bagaimana kita bisa mempersempit kisaran kemungkinan penyebabnya? Sangat mudah untuk mengecualikan struktur Anda dari tersangka - mereka harus dipindahkan ke RAM ke tempat lain (di mana penyabot tidak membom):
Bagaimana ini bisa dilakukan dengan mudah dengan FastMemPool? Sangat sederhana: di FastMemPool, alokasi terjadi dengan menggigit dari akhir halaman memori - dengan meminta halaman memori lebih dari yang Anda butuhkan untuk bekerja, Anda menjamin bahwa awal halaman memori tetap menjadi tempat pengujian untuk pemboman kereta. Misalnya:
FastMemPool<100000000, 1, 1024, true, true> bulletproof_mempool;
void *ptr = bulletproof_mempool.fmalloc(1234567);
// ..
// - c ptr
// ..
bulletproof_mempool.ffree(ptr);
Jika di tempat baru seseorang membom bangunan Anda, maka kemungkinan besar Anda sendiri ...
Jika tidak, jika perpustakaan stabil, tim akan menerima beberapa hadiah sekaligus:
- algoritme Anda berfungsi seperti jam tangan Swiss lagi
- pembuat kode kereta sekarang dapat dengan aman mengebom area memori yang kosong (sementara semua orang mencarinya), pustaka tersebut stabil.
- jangkauan pengeboman dapat dipantau untuk mengubah memori - untuk memasang perangkap pada encoder kereta.
Secara total , apa saja kelebihan dari motor khusus ini:
- ( / )
- , Debug ,
- , /
- , ( nullptr), — , ( FPS , FastMemPool -).
Di perusahaan kami, pemasangan analisis geometri 3D dari lembaran logam memerlukan pemrosesan multi-threaded frame video (50FPS). Lembaran itu lewat di bawah kamera dan pada pantulan laser saya membuat peta lembaran 3D. FastMemPool digunakan untuk memastikan kecepatan maksimum bekerja dengan memori dan keamanan. Jika streaming tidak dapat mengatasi frame yang masuk, maka menyimpan frame untuk pemrosesan di masa mendatang dengan cara biasa akan menyebabkan konsumsi RAM yang tidak terkontrol. Dengan FastMemPool, jika terjadi overflow, nullptr hanya akan dikembalikan selama alokasi dan frame akan dilewati - dalam gambar 3D akhir, cacat seperti lompatan dalam langkah menunjukkan bahwa perlu menambahkan utas CPU ke pemrosesan.
Operasi utas bebas mutex dengan pengalokasi memori melingkar dan tumpukan tugas memungkinkan untuk memproses bingkai yang masuk dengan sangat cepat, tanpa kehilangan bingkai dan tanpa RAM yang meluap. Sekarang kode ini berjalan di 16 utas pada CPU AMD Ryzen 9 3950X, tidak ada kegagalan di kelas FastMemPool yang telah diidentifikasi.
Diagram contoh yang disederhanakan dari proses analisis video dengan kontrol kelebihan RAM dapat dilihat di kode sumber test_memcontrol1.cpp .
Dan untuk hidangan penutup: dalam skema contoh yang sama, tumpukan non-mutex digunakan:
using TWorkStack = SpecSafeStack<VideoFrame>;
//..
// Video frames exchanger:
TWorkStack work_stack;
//..
work_staff->work_stack.push(frame);
//..
VideoFrame * frame = work_staff->work_stack.pop();
Stand demo yang berfungsi dengan semua sumber ada di sini di gihub .