Write its memory management pool for a class and summarize the allocator class (three versions)

Write its memory management pool for a class and summarize the allocator class (three versions)

table of Contents

If we don t do memory management for objects, then every time we do

Foo* p = new Foo(x);
The malloc function is always called.
Although the malloc function is very fast, we still have the need to manage memory ourselves. It has been recorded
in blog.csdn.net/qq_42604176... that some operating systems calling malloc function multiple times will gradually divide the original large contiguous memory area into many very small and non-adjacent memory areas, that is, memory. Fragments. This is also a hidden danger.
We can first use the malloc function to apply for a large section of memory, and then cut it into several small blocks, and give a small block of memory every time an object is created. This is more efficient and easier to manage.
And if there is no special design, malloc is called once to create an object, and malloc will get two cookies (8 bytes). This will waste space when creating multiple objects.
The purpose of memory pool design is to increase speed and reduce waste.

Sample version 1: per-class allocator,1

The following is an example:

# include <cstddef> # include <iostream> using namespace std; class Screen { public : Screen ( int x): i (x) {}; int get () { return i;} void * operator new ( size_t ) ; void operator delete ( void *, size_t ) ; //... private : Screen* next; static Screen* freeStore; static const int screenChunk; private : int i; }; Screen* Screen::freeStore = 0 ; const int Screen::screenChunk = 24 ; copy the code

For memory management considerations, we need to dig a large block of memory, and the small blocks in the memory need to be linked together with pointers. So you can see that there will be a next pointer inside the above class, pointing to an object of type Screen. But there will be a pity this way, because there is an extra pointer, which leads to wasted space.

Next is the overloading of the function. The core operation step is the operation of the singly linked list. The free memory is made into a linked list, and each time a new memory is opened, one of the linked lists is allocated.

void * Screen:: operator new ( size_t size) { Screen *p; if (!freeStore) { //The linked list is empty, so a large chunk of memory is requested. size_t chunk = screenChunk * size; //Dug the memory of 24 objects at a time //Transform the pointer freeStore = p = reinterpret_cast <Screen* >( new char [chunk]); //Split a large block into small blocks and concatenate them as a linked list for (;p != &freeStore[screenChunk- 1 ]; ++p) p->next = p + 1 ; p->next = 0 ; } p = freeStore; freeStore = freeStore->next; return p; } Copy code

If it is recycled, the object is destroyed and the memory is relocated back to the linked list:
Note that the pointer to the recycled memory is placed at the head of the linked list, because the operation is faster. Just move the head pointer. Note that the memory here is not returned to the operating system, but the used memory is put into a linked list.

void Screen:: operator delete ( void *p, size_t ) { //Insert the delete object back to the front end of the free list ( static_cast <Screen*>(p))->next = freeStore; freeStore = static_cast <Screen*>(p); } Copy code

Test function:

cout << sizeof (Screen) << endl; //16 size_t const N = 100 ; Screen* p[N]; for ( int i = 0 ; i <N; ++i) p[i] = new Screen (i); //Output the first 10 pointers and compare their intervals: for ( int i = 0 ; i < 10 ; ++i) cout << p[i] << endl; for ( int I = 0 ; I <N; I ++) Delete P [I]; duplicated code

Effect: It
can be seen that the memory interval between each class is 16, and there is indeed no cookie memory.

16
00000280B9B21CF0
00000280B9B21D00
00000280B9B21D10
00000280B9B21D20
00000280B9B21D30
00000280B9B21D40
00000280B9B21D50
00000280B9B21D60
00000280B9B21D70
00000280B9B21D80

If we do not overload the two functions, the results obtained are as follows. Since the computer operating system is multi-process, there may be other tasks executed during memory allocation, resulting in memory not being continuous. It is estimated that the interval should be 5*16 .

16
000001BA32211920
000001BA322120A0
000001BA32211A10
000001BA32211970
000001BA32211C90
000001BA32212460
000001BA322124B0
000001BA32212500
000001BA32211EC0
000001BA322119C0

The PPT of Teacher Hou Jie is in VC6 and GNU environment, and the results are as follows:

Sample version 2: per-class allocator,2

This version mainly uses union to optimize the pointers of the first version.
Here is a brief review of union, after all, I have never used this thing.
For details, please refer to: blog.csdn.net/yuyanggo/ar...

The same memory segment can be used to store several different types of members, but only one of them can exist at a time, instead of storing several at the same time. In other words, only one member works at a moment, and other members do not work, that is, not all exist and work at the same time.
The effective member of the union variable is the last member stored. After a new member is stored, the original member loses its effect.

# include <iostream> using namespace std; union test { char mark; long num; float score; }a; int main () { //cout<<a<<endl;//wrong a.mark = 'b' ; cout<<a.mark<<endl; // output'b ' cout<<a.num<<endl; //98 ACSII value of character'b' cout<<a.score<<endl; //output error value a.num = 10 ; cout<<a.mark<<endl; //output line break Thank you very much Suxin for your correction cout<<a.num<<endl; //output 10 cout<<a.score<<endl; //output wrong value a.score = 10.0 ; cout<<a.mark<<endl; //output empty cout<<a.num<<endl; //output error value cout<<a.score<<endl; //output 10 return 0 ; } Copy code

Since the start addresses of all members in the union are the same, the values of &a.mark, &a.num, and &a.score are all the same.
Because things in the union share memory, static, reference-type variables cannot be defined.
It is also not allowed to store objects of classes with constructors, destructors, and copy constructors in the union, but you can store corresponding class object pointers. The compiler cannot guarantee that the constructor and destructor of the class are called correctly, and therefore, memory leaks may occur.

Next look at the second version:

class Airplane { private : struct AirplaneRep { unsigned long miles; char type; }; private : union { AirplaneRep rep; //This pointer points to the object in use Airplane* next; //This pointer points to the object on the free list }; //These methods are not the focus public : unsigned long getMiles () { return rep.miles;} char getType () { return rep.type;} void set ( unsigned long m, char t) { rep.miles = m; rep.type = t; } //Overload new and delete public : static void * operator new ( size_t size) ; static void operator delete ( void * deadObject, size_t size) ; private : static const int BLOCK_SIZE; static Airplane* headOfFreeList; }; Airplane* Airplane::headOfFreeList; const int Airplane::BLOCK_SIZE = 512 ; Copy code

The overload of new is similar to the first version

void * Airplane:: operator new ( size_t size) { //The size may be wrong when inheritance occurs if (size != sizeof (Airplane)) return :: operator new (size); Airplane* p = headOfFreeList; if (p) //If p is valid, move the head of the linked list down headOfFreeList = p->next; else { //If the linked list is empty, apply for a large block of memory Airplane* newBlock = static_cast <Airplane*>(:: operator new (BLOCK_SIZE * sizeof (Airplane))); //Wear the small piece into a freelist for ( int i = 1 ; i <BLOCK_SIZE- 1 ; ++i) newBlock[i].next = &newBlock[i+ 1 ]; newBlock[BLOCK_SIZE- 1 ].next = 0 ; p = newBlock; headOfFreeList = &newBlock[ 1 ]; } return p; } Copy code

The delete version is almost the same as the first version. There is the problem of not returning the memory to the operating system. This is not a memory leak, because the memory is still in our hands.

//operator delete intercepts a memory block //if the size is correct, add it to the front end of the freelist void Airplane:: operator delete ( void * deadObject, size_t size) { if (deadObject == 0 ) return ; if (size != sizeof (Airplane)) { :: operator delete (deadObject) ; return ; } Airplane* carcass = static_cast <Airplane*>(deadObject); carcass->next = headOfFreeList; headOfFreeList = carcass; } Copy code

Final version: static allocator

We just reloaded its new and delete separately for a class, which would lead to code duplication. We abstract the action just now and put it into a class.
Each allocator object is an allocator, it maintains a freelist in its body, and different allocator objects maintain different freelists.

class allocator { private : struct obj { struct obj * next ; }; public : void * allocate ( size_t ) ; void deallocate ( void *, size_t ) ; private : obj* freeStore = nullptr ; const int CHUNK = 5 ; //Here is a bit smaller for observation }; void allocator::deallocate ( void * p, size_t ) { //Retract *p and insert it into the free list front end ((obj*)p)->next = freeStore; freeStore = (obj*)p; } void * allocator::allocate ( size_t size) { obj* p; if (!freeStore) { //linked list is empty, so apply for a large chunk of size_t chunk = CHUNK * size; freeStore = p = (obj*) malloc (chunk); //Take the allocated chunk as a linked list //concatenate it for ( int i = 0 ; i <(CHUNK- 1 ); ++i) { p->next = (obj*)(( char *)p + size); p = p->next; } p->next = nullptr ; } p = freeStore; freeStore = freeStore->next; return p; } Copy code

The following is the class call allocator:
each allocator object is an allocator, it maintains a freelist in its body, and different allocator objects maintain different freelists.
All memory-related details are taken over by the allocator. Our job is to make application classes work correctly.

class Foo { public : long L; string str; static allocator myAlloc; public : Foo ( long l): L ( 1 ){} static void * operator new ( size_t size) { return myAlloc. allocate (size); } static void operator delete ( void * pdead, size_t size) { return myAlloc. deallocate (pdead,size); } }; allocator Foo::myAlloc; Copy code

The details of the specific memory allocation shown above are no longer known by the application class.
The test code is as follows: Be careful not to use using namespace std here; because there is also an allocator in the standard library.

# include <cstddef> # include <iostream> //using namespace std; namespace static_allocator { class allocator { private : struct obj { struct obj * next ; }; public : void * allocate ( size_t ) ; void deallocate ( void *, size_t ) ; private : obj* freeStore = nullptr ; const int CHUNK = 5 ; //Here is a bit smaller for observation }; void allocator::deallocate ( void * p, size_t ) { //Retract *p and insert it into the free list front end ((obj*)p)->next = freeStore; freeStore = (obj*)p; } void * allocator::allocate ( size_t size) { obj* p; if (!freeStore) { //linked list is empty, so apply for a large chunk of size_t chunk = CHUNK * size; freeStore = p = (obj*) malloc (chunk); //Take the allocated chunk as a linked list //concatenate it for ( int i = 0 ; i <(CHUNK- 1 ); ++i) { p->next = (obj*)(( char *)p + size); p = p->next; } p->next = nullptr ; } p = freeStore; freeStore = freeStore->next; return p; } class Foo { public : long L; std::string str; static allocator myAlloc; public : Foo ( long l): L ( 1 ) {} static void * operator new ( size_t size) { return myAlloc. allocate (size); } static void operator delete ( void * pdead, size_t size) { return myAlloc. deallocate (pdead, size); } }; allocator Foo::myAlloc; void test_static_allocator_3 () { std::cout << "\n\n\ntest_static_allocator()........../n" ; { Foo* p[ 100 ]; std::cout << "sizeof(Foo)= " << sizeof (Foo) << std::endl; for ( int i = 0 ; i < 23 ; ++i) { //23, arbitrary number, arbitrary Look at the result p[i] = new Foo (i); std::cout << p[i] << '' << p[i]->L << std::endl; } //Foo::myAlloc.check(); for ( int i = 0 ; i < 23 ; ++i) { delete p[i]; } //Foo::myAlloc.check(); } } } int main () { static_allocator:: test_static_allocator_3 (); return 0 ; } Copy code

The printing effect is as follows:

you can see that every time the allocator calls malloc, it takes 5 elements at a time. So every 5 elements must be adjacent. It can be seen between the third from the bottom and the fourth from the bottom of the rendering.
Focus on this writing.

Macro for version three

The specific steps are as follows, just replace the yellow part with the blue part.
Every time you use it, just call two macros directly inside the class.

Need to pay attention to a point of knowledge:
The "" after #define is a line continuation character, which means that the next line is immediately following the current line. It is generally used to divide a very long code statement into several zhuan segments (the statement itself must be a line ).
It should be noted that there can be no characters after/, except for line feed and carriage return, and spaces are not allowed:

# define DECLARE_POOL_ALLOC()/ public:/ void* operator new(size_t size) {return myAlloc.allocate(size);}/ void operator delete(void* p) {myAlloc.deallocate(p, 0);}/ protected:/ static allocator myAlloc; //IMPLEMENT_POOL_ALLOC - used in class implementation file # define IMPLEMENT_POOL_ALLOC(class_name)/ allocator class_name::myAlloc; //in class definition file class Foo { DECLARE_POOL_ALLOC () public : long L; string str; public : Foo ( long l): L (l) {} }; //in class implementation file IMPLEMENT_POOL_ALLOC (Foo) //in class definition file class Goo { DECLARE_POOL_ALLOC () public : complex< double > c; string str; public : Goo ( const complex< double >& x): c (x) {} }; Implementation File in class// IMPLEMENT_POOL_ALLOC (Goo) Copy the code