Tiplarni dinamik tarzda

Pul obʻyektlari. Pul obʻyektlari uchun aniq echim - OS dan katta xotira blokini olish va uni teng blokli o‘lchamlarga bo‘lishdir sizeof(node). Xotirani ajratishda blokni puldan olinadi va uni bo‘shatishda uni pulga qaytariladi. Pulni tashkil qilishning eng oson usuli - bitta aloqa stekni (stack) ishlatishdir.
Maqsad dasturda minimal qayta aniqlashlar bo‘lgani uchun, BlockAlloc sinfni merosxo‘ri sifatida Node sinfini tanlashdir.

class Node : public BlockAlloc

Avvalo, OS yoki C-runtime dan katta bloklar uchun bir pul olish kerak. Buni malloc va free funksiyalari bilan tashkil qilish mumkin, lekin katta samaradorligi uchun (ortiqcha abstraksiya bosqichini o‘tkazish uchun), Virtualloc/Virtualfreye funksiyalaridan foydalanish maqsadga muvofiq. Bu vazifalar 4 karrali bo‘lgan bloklarga xotira ajratadi va 64 karrali bo‘lgan bloklar jarayon manzili uchun oraliq saqlab turadi. Bir vaqtning o‘zida commit va reserve imkoniyatlari ko‘rsatilgan holda yana bir darajada ko‘tarilib, manzil oraliqni rezervlash va bitta chaqirish bilan xotira bloklarini ajratamiz.
PagePool sinfi dastur fragmenti.

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 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::iterator i = pages.begin(); i != pages.end(); ++i) { VirtualFree(*i, 0, MEM_RELEASE); } } private: vector pages; };

Berilgan o‘lchamga mos, pul bloklarni hosil qilish uchun BlockPool sinfini yaratamiz.
BlockPool sinfining dastur fragmentlari:

template class BlockPool : PagePool {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;}};

Potoklar orasidagi sinxronzatsiyani tashkil qilish uchun berilgan manzil todo: lock(this) izohga olib qo‘yilgan. Buning uchun EnterCriticalSection yoki boost::mutex dan foydalanish ham mumkin.
Agar biror narsa yozilgan bo‘lsa, bloklar majmuini formatlashda abstrakt FreeBlock pulga blok qo‘shish ishlatilmaydi. O‘ylab ko‘ring.

for (size_t i = 0; i < PageSize; i += BlockSize) FreeBlock((char*)tmp+i);

FIFO tamoyilidagi bloklar majmui teskari bo‘lib qoladi.

5.1-rasm. FIFO tamoyilidagi bloklar majmui.

Puldan ketma-ket so‘ralgan bir necha blok manzillar kamayib ketadi. Shuningdek protsessor orqaga qaytishni yoqtirmaydi, chunki uning Prefetch amalii buziladi (UPD: zamonaviy protsessorlar uchun tegishli emas). Agar takrorlanish bilan almashtirilsachi?

for (size_t i = PageSize-(BlockSize-(PageSize%BlockSize)); i != 0; i -= BlockSize) FreeBlock

Takrorlanishda almashtirishlar manzillar bo‘yicha orqaga bajariladi.
Tayyorgalik ko‘rilganidan so‘ng, sinf obʻyektni yozish mumkin:

template 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); } } static void* operator new(size_t, void* m) { return m;} static void operator delete(void*, void*) { } private: static BlockPool pool;}; template BlockPool BlockAlloc::pool;

Sinfda ular ishlaganda nima uchun if (s != sizeof(T)) kerak. T bazaviy sinfdan mo‘rosxo‘r sinf yaratilgan va o‘chirilgan bo‘lsa? degan savol bo‘lishi mumkin.
Merosxo‘rlar odatda oddiy new/delete operatorlari bilan ishlatiladi, shuningdek BlockAlloc ni ham joylatirish mumkin. Bu yo‘l bilan oson va xavfsiz dasturda biror narsa buzib qo‘rqmasdan, pullar foydalanishga qaratilgan sinflar aniqlash mumkin. Bir nechta merosxo‘rlar ham bu bilan yaxshi ishlaydi.
BlockAlloc dan mo‘rosxo‘r sifatida Node ni olamiz va yana sinov o‘tkazamiz.
Sinov natijasiga qarasak, 5 barovar tez va 120 msda bajarilmoqda. Ammo, c# allokator hali ham yaxshi. Mumkin u yerda oddiy bo‘lmagan bir aloqali ro‘yxatdan foydalanilgandir. Agar, new operatoridan so‘ng zudlik bilan delete operatori ishlatilsa, xotira kamroq ishlatiladi va keshda maʻlumotlar ham kamayadi va natijani 62 msda olish mumkin. Qiziqarli tomoni shundaki, . NET CLR da GC ni kutmasdan pulga mos bo‘sh qolgan lokal o‘zgaruvchini tez qaytaradi.