catalogue
1.2.1 introduction to member variables
1.2.2 introduction to member functions
preface
We know that users must apply for memory through the operating system, which opens up a space from the heap for users. However, if space is frequently applied to the operating system, the operating system needs to open up space for users frequently. However, the operating system needs to manage many things, which will lead to the low efficiency of the operating system.
Memory pool is a large piece of memory opened up by the operating system. When users need to apply for space, they directly apply for space from the memory pool without going through the operating system. Only when the memory pool space is insufficient, apply to the operating system for a large space as the memory pool.
In this way, when users need space, they don't need to ask the operating system for space frequently. Improved efficiency.
1, Fixed length memory pool
1.1 concept
Fixed length memory pool: the size of memory divided from the memory pool each time is fixed.
Fixed length memory pool is a large memory space. Each time you need to apply for memory, you can allocate it directly from the memory pool. When the user space is used up, it cannot be released directly, because a large amount of memory is applied for at the time of application, and a small part cannot be released. The fixed length memory pool uses a linked list to connect small pieces of memory for next use.
Therefore, when the user applies for space from the fixed length memory pool, the fixed length memory pool will first detect whether there is a small block of memory in the linked list, directly apply to the user, and no part of the memory block is allocated to the user.
- Advantages: simple and rough, high efficiency of distribution and release, and effective in solving problems in specific scenarios in practice.
There is no need to frequently apply for space from the operating system (this is the advantage of memory pools). Because it is fixed in length, there is no need to find memory blocks of appropriate size from the linked list, but only need to allocate them directly.
- Disadvantages: the function is single, which can only solve the memory demand of fixed length. In addition, the occupied memory is not released.
Since the size of memory divided from the memory pool is fixed each time, if the fixed length memory pool is used as the memory pool of STL container, it is necessary to define different fixed length memory pools for different containers. Because different containers have different node sizes. vector is not yet available.
1.2 realization
1.2.1 introduction to member variables
Member variables include a chain header pointer and a large block of memory.
struct Memory{
Memory(){
leftsize = 1024 * 1;
memory = (char *)malloc(leftsize);
std::cout << (void *)memory << std::endl;
head = memory;
}
char *memory = nullptr;//Memory pool
Memory *next = nullptr;//Point to the next chunk of memory
size_t leftsize = 0;//Remaining space
char *head = nullptr;
~Memory(){
free(head);
}
};
//Connect large memory blocks to facilitate release
Memory *m = nullptr;
void *freelist = nullptr;//The free chain header pointer saves the space used by the userWhy is the chain header node directly defined as a void * pointer instead of a structure pointer?
The nodes of the linked list do not need to save valid values, but only the address of the next memory block. We directly use the cut memory block space to save the address of the next memory block. void * can receive any pointer type.
For example, under the 32 platform, the first 4 bytes of the divided memory block are used to save the address of the next memory block.
Why is a large block of memory encapsulated as a structure rather than directly set as a pointer?
In order to facilitate the release of space, it is introduced below.
Why is the structure variable block memory of char * type?
char * step size is 1 byte, which is convenient to calculate the space requested by the user.
1.2.2 introduction to member functions
The fixed length memory pool provides two interfaces to users, one is to apply for space from the memory pool, and the other is to return the applied space to the memory pool.
Request space from memory block
- First, check whether the free linked list has memory blocks
- If there is a memory block, delete the memory block directly to the user.
- If not, cut the memory block into the large memory block. If there is no large block of memory, you need to apply to the system. If there is memory, directly cut the memory to the user.
- The remaining space size of the memory block needs to be recorded to prevent the application from crossing the boundary. If the remaining space is not enough, you need to apply for a large block of memory from the system.
Return the requested space to the memory pool
- Insert the returned space header directly into the free linked list
1.2.3 details
Cutting a piece of memory from a large block of memory is not really direct cutting. Instead, move the head pointer of the large block of memory backward by the requested size bit, and then the front space will not be allocated to the user.
- Because the linked list directly uses the divided memory block to save the address of the next memory block, what if the applied memory block is less than the number of pointer bytes?
Make a judgment. When the size of the applied memory block is equal to the pointer size of the current platform, round it up directly, and the size of the cut memory block is the pointer size.
//The memory block that may be cut is smaller than the pointer size
static size_t GetSize(){
if (sizeof(T) < sizeof(void*)){
return sizeof(void*);
}
else{
return sizeof(T);
}
}- How to make the linked list node memory block to save the address of the next memory block?
Using forced conversion and dereference
//On 32-bit platform, strong conversion to int * and dereference to obtain 4-byte space *(int *)obj = freelist; //On the 64 bit platform, strong convert to long long *, and then dereference to get 8 bytes *(long long*) obj = freelist;
- 32 refers to the pointer size of 4 bytes under the platform and 8 bytes under the 64 bit platform. How to allocate space in the linked list memory block to save the address of the next memory block?
//1. Through judgment
if(sizeof(void*) == 4){
{
//On 32-bit platform, strong conversion to int * and dereference to obtain 4-byte space
*(int *)obj = freelist;
}
else{
//On the 64 bit platform, strong convert to long long *, and then dereference to get 8 bytes
*(long long*) obj = freelist;
}
//2. Directly obtain the pointer size space. When dereferencing, void * directly refers to the pointer size
*(void**)obj = freelist;- How to destroy a fixed length memory pool?
Connect the large memory pool with a linked list and save the starting address of the large memory. When destroying, you only need to traverse the linked list directly to free up space. This is why it is necessary to set the applied large space as a structure.
struct Memory{
Memory(){
leftsize = 1024 * 1;
memory = (char *)malloc(leftsize);
std::cout << (void *)memory << std::endl;
head = memory;
}
char *memory = nullptr;//Memory pool, large block of memory, char * step size of one byte, easy to allocate
Memory *next = nullptr;//Point to the next memory pool
size_t leftsize = 0;//Remaining space
char *head = nullptr;//Save the starting address of the memory block for easy release
//Destructor
~Memory(){
free(head);
}
};
void Destroy(){
while (m){
Memory *tmp = m;
m = m->next;
delete tmp;//Call the structure destructor to destroy the space
}
}
1.3 code
#pragma once
#include "Comment.h"
struct Memory{
Memory(){
leftsize = 1024 * 1;
memory = (char *)malloc(leftsize);
std::cout << (void *)memory << std::endl;
head = memory;
}
char *memory = nullptr;//Memory pool, large block of memory, char * step size of one byte, easy to allocate
Memory *next = nullptr;//Point to the next memory pool
size_t leftsize = 0;//Remaining space
char *head = nullptr;//Save the starting address of the memory block for easy release
~Memory(){
free(head);
}
};
template<class T>
class ObjectPool{
private:
//Connect large memory blocks to facilitate release
Memory *m = nullptr;
void *freelist = nullptr;//The free chain header pointer saves the space used by the user
//The memory block that may be cut is smaller than the pointer size
static size_t GetSize(){
if (sizeof(T) < sizeof(void*)){
return sizeof(void*);
}
else{
return sizeof(T);
}
}
//Pointers can also be used without reference
static void*& GetIndex(T*& obj){
return (*(void **)obj);
}
void Destroy(){
while (m){
Memory *tmp = m;
m = m->next;
delete tmp;
}
}
public:
T* New(){
//First, see if there is any in the linked list
//No memory pool cut
T* obj = nullptr;
if (freelist){
obj = (T*)freelist;
//Next position in the linked list
freelist = GetIndex(obj);
return obj;
}
else{
//There may be no memory pool, you need to apply or there is not enough space
if (m == nullptr || m->leftsize < sizeof(T)){
//Connect
Memory *tmp = new Memory();
tmp->next = m;
m = tmp;
}
obj = (T*)m->memory;
m->memory += GetSize();
m->leftsize -= GetSize();
//Locate new, open up space at obj, and call the constructor
new(obj)T;
return obj;
}
}
void Delete(T* obj){
//Call destructor
obj->~T();
//No free, apply for large space, no free part of space
//Directly use the cut memory to save the address of the next linked list
//Strong conversion to void * *, and then dereference to prevent the number of pointer bytes from being different on different platforms
//Head insert
GetIndex(obj) = freelist;
freelist = obj;
}
~ObjectPool(){
Destroy();
}
};