Memory Pool
http://reborn2266.blogspot.tw/2011/10/memory-pool.html http://www.codinglabs.net/tutorial_memory_pool.aspx
Why you should use
- Avoid the memory fragment
- Speed up the program
- Saving the time to find valid memory spaces
When should you use
Frequently using new and delete.
Basic Idea
DebugOnly.h
// file: DebugOnly.h
#ifndef DebugOnly_h_
#define DebugOnly_h_
#include <iostream>
#include <sstream> // std::stringstream
#include <string> // std::string
#define DEBUG true
void Log(std::string msg)
{
DEBUG && std::cout << msg << std::endl;
}
template<class T>
std::string ToAddressString(const T& t)
{
const void* address = static_cast<const void*>(&t);
std::stringstream ss;
ss << address;
return ss.str();
}
#endif // #ifndef DebugOnly_h_
Data.h
// file: Data.h
#ifndef Data_h_
#define Data_h_
#include "DebugOnly.h"
// Data Structure for Demo
// ===================================
struct Data
{
int mValue;
std::string mString;
Data(int val, std::string str)
: mValue(val)
, mString(str)
{
Log("<Data> Constructor");
}
~Data()
{
Log("<Data> Deconstructor");
}
};
// Helper functions
// ===================================
void PrintData(Data* data)
{
Log("[" + ToAddressString(*data) + "] " + // address
std::to_string(data->mValue) + " " + // value
data->mString); // string
}
#endif // #ifndef Data_h_
Basic.h
// file: Basic.h
#ifndef Basic_h_
#define Basic_h_
#include "DebugOnly.h"
#include <queue> // std::queue
template<typename T>
class BasicPool
{
public:
BasicPool()
{
Log("<BasicPool> BasicPool");
};
// Disallow the copy constructor
BasicPool(const BasicPool &)=delete;
// The move constructor
BasicPool(BasicPool&& other)
: mChunks(std::move(other.mChunks))
{
Log("<BasicPool> BasicPool << Move");
}
~BasicPool()
{
Log("<BasicPool> ~BasicPool");
Clear();
}
// Allocate a chunk of memory for the class object
void* Allocate()
{
Log("<BasicPool> Allocate");
// If there is no more available memory chunk,
// then we create a new one
if (mChunks.empty()) {
return ::operator new(sizeof(T));
}
// Otherwise, return a free memory chunk
void* chunk = static_cast<void*>(mChunks.front());
mChunks.pop();
return chunk;
}
// Reclaim the memory space from those no longer used objects
void Deallocate(void* obsolete)
{
Log("<BasicPool> Deallocate");
mChunks.push(static_cast<T*>(obsolete));
}
// Release all of the free memory chunks
void Clear()
{
Log("<BasicPool> Clear");
while (!mChunks.empty()) {
::operator delete(mChunks.front());
mChunks.pop();
}
}
private:
// Holding the pointers to the free memory chunks
std::queue<T*> mChunks;
};
#endif // #ifndef Basic_h_
main.cpp
// file: main.cpp
#include "Basic.h"
#include "Data.h"
#include "DebugOnly.h"
// Main Program
// ===================================
int main() {
// Declare a pool object
BasicPool<Data> pool;
// Create an instance of Data from the pool
void* freeSpace = pool.Allocate();
Data* data = new (freeSpace) Data(57, "Hello");
// Print it
PrintData(data);
// Destroy it
data->~Data();
pool.Deallocate(data);
// Print it again
PrintData(data);
// Create another instance of Data from the pool
void* freeSpace2 = pool.Allocate();
Data* data2 = new (freeSpace2) Data(75, "World");
// Print it
PrintData(data2);
// Destroy it
data2->~Data();
pool.Deallocate(data2);
// Print it again
PrintData(data2);
return 0;
}
The result is:
<BasicPool> BasicPool
<BasicPool> Allocate
<Data> Constructor
[0x7fdbd2500000] 57 Hello
<Data> Deconstructor
<BasicPool> Deallocate
[0x7fdbd2500000] 57 Hello
<BasicPool> Allocate
<Data> Constructor
[0x7fdbd2500000] 75 World
<Data> Deconstructor
<BasicPool> Deallocate
[0x7fdbd2500000] 75 World
<BasicPool> ~BasicPool
<BasicPool> Clear
The two objects have same address 0x7fdbd2500000.
More General
// Create an instance of Data from the pool
void* freeSpace = pool.Allocate();
Data* data = new (freeSpace) Data(57, "Hello");
We need to ask a memory space and then construct our data there.
// Destroy it
data->~Data();
pool.Deallocate(data);
And we also need to deconstruct our data and then return the memory space.
Maybe we can write functions to do these jobs.
Create_and_Destroy.h
// file: Create_and_Destroy.h
#ifndef CreateAndDestroy_h_
#define CreateAndDestroy_h_
#include "DebugOnly.h"
#include <queue> // std::queue
template<typename T>
class BasicPool
{
public:
BasicPool()
{
Log("<BasicPool> BasicPool");
};
// Disallow the copy constructor
BasicPool(const BasicPool &)=delete;
// The move constructor
BasicPool(BasicPool&& other)
: mChunks(std::move(other.mChunks))
{
Log("<BasicPool> BasicPool << Move");
}
~BasicPool()
{
Log("<BasicPool> ~BasicPool");
Clear();
}
// Allocate a chunk of memory for the class object
void* Allocate()
{
Log("<BasicPool> Allocate");
// If there is no more available memory chunk,
// then we create a new one
if (mChunks.empty()) {
return ::operator new(sizeof(T));
}
// Otherwise, return a free memory chunk
void* chunk = static_cast<void*>(mChunks.front());
mChunks.pop();
return chunk;
}
// Reclaim the memory space from those no longer used objects
void Deallocate(void* obsolete)
{
Log("<BasicPool> Deallocate");
mChunks.push(static_cast<T*>(obsolete));
}
// ******************************************************
// * Create and Destroy *
// ******************************************************
// Create a new class object
template<typename... Args>
T* Create(Args&& ...args)
{
T* space = (T*)(Allocate());
try {
new (space) T(std::forward<Args>(args)...);
} catch (...) { // Reclaim allocated memory if new operation failed.
mChunks.push(space);
throw;
}
return space;
}
// Destroy the obsoleted object and reclaim its memory space
void Destroy(T* obsolete)
{
obsolete->~T();
Deallocate(obsolete);
}
// ******************************************************
// Release all of the free memory chunks
void Clear()
{
Log("<BasicPool> Clear");
while (!mChunks.empty()) {
::operator delete(mChunks.front());
mChunks.pop();
}
}
private:
// Holding the pointers to the free memory chunks
std::queue<T*> mChunks;
};
#endif // #ifndef CreateAndDestroy_h_
main.cpp
// file: main.cpp
// #include "Basic.h"
#include "Create_and_Destroy.h"
#include "Data.h"
#include "DebugOnly.h"
// Main Program
// ===================================
int main() {
// Declare a pool object
BasicPool<Data> pool;
// Create an instance of Data from the pool
// void* freeSpace = pool.Allocate();
// Data* data = new (freeSpace) Data(57, "Hello");
Data* data = pool.Create(57, "Hello");
// Print it
PrintData(data);
// Destroy it
// data->~Data();
// pool.Deallocate(data);
pool.Destroy(data);
// Print it again
PrintData(data);
// Create another instance of Data from the pool
// void* freeSpace2 = pool.Allocate();
// Data* data2 = new (freeSpace2) Data(75, "World");
Data* data2 = pool.Create(75, "World");
// Print it
PrintData(data2);
// Destroy it
// data2->~Data();
// pool.Deallocate(data2);
pool.Destroy(data2);
// Print it again
PrintData(data2);
return 0;
}
The result is:
<BasicPool> BasicPool
<BasicPool> Allocate
<Data> Constructor
[0x7fb8cac04b30] 57 Hello
<Data> Deconstructor
<BasicPool> Deallocate
[0x7fb8cac04b30] 57 Hello
<BasicPool> Allocate
<Data> Constructor
[0x7fb8cac04b30] 75 World
<Data> Deconstructor
<BasicPool> Deallocate
[0x7fb8cac04b30] 75 World
<BasicPool> ~BasicPool
<BasicPool> Clear
The result is same except the address is changed to 0x7fb8cac04b30.
Overriding operator new and delete
Actually, the create and destroy are similar to new and delete.
Recall what they done in new and delete chapter.
We can override new and delete to do that jobs.
New_and_Delete.h
// file: New_and_Delete.h
#ifndef NewAndDelete_h_
#define NewAndDelete_h_
#include "DebugOnly.h"
#include <queue> // std::queue
template<typename T>
class BasicPool
{
public:
BasicPool()
{
Log("<BasicPool> BasicPool");
};
// Disallow the copy constructor
BasicPool(const BasicPool&)=delete;
// The move constructor
BasicPool(BasicPool&& other)
: mChunks(std::move(other.mChunks))
{
Log("<BasicPool> BasicPool << Move");
}
~BasicPool()
{
Log("<BasicPool> ~BasicPool");
Clear();
}
// Allocate a chunk of memory for the class object
void* Allocate()
{
Log("<BasicPool> Allocate");
// If there is no more available memory chunk,
// then we create a new one
if (mChunks.empty()) {
return ::operator new(sizeof(T));
}
// Otherwise, return a free memory chunk
void* chunk = static_cast<void*>(mChunks.front());
mChunks.pop();
return chunk;
}
// Reclaim the memory space from those no longer used objects
void Deallocate(void* obsolete)
{
Log("<BasicPool> Deallocate");
mChunks.push(static_cast<T*>(obsolete));
}
// Release all of the free memory chunks
void Clear()
{
Log("<BasicPool> Clear");
while (!mChunks.empty()) {
::operator delete(mChunks.front());
mChunks.pop();
}
}
private:
// Holding the pointers to the free memory chunks
std::queue<T*> mChunks;
};
template<typename T, template<typename = T> class Pool = BasicPool>
class MemoryPool
{
public:
// Override new
static void* operator new(size_t size)
{
Log("<MemoryPool> new");
return mPool.Allocate();
}
// Override delete
static void operator delete(void* p)
{
Log("<MemoryPool> delete");
mPool.Deallocate(p);
}
// Clear the pool
static void Clear()
{
Log("<MemoryPool> Clear");
mPool.Clear();
}
private:
// Allow only the inherited objects to call it
MemoryPool()
{
Log("<MemoryPool> MemoryPool");
};
MemoryPool(const MemoryPool&)
{
Log("<MemoryPool> MemoryPool << Move");
};
// Make the inherited objects to access its private members
friend T;
static Pool<T> mPool;
};
// Define the static pool variable that will be called
// in constructor and deconstructor
template<typename T, template<typename = T> class Pool>
Pool<T> MemoryPool<T, Pool>::mPool;
#endif // #ifndef NewAndDelete_h_
Data.h
// file: Data.h
#ifndef Data_h_
#define Data_h_
#include "New_and_Delete.h" // For MemoryPool
#include "DebugOnly.h"
// Data Structure for Demo
// ===================================
struct Data: public MemoryPool<Data> // Inherit to override new and delete
{
int mValue;
std::string mString;
Data(int val, std::string str)
: mValue(val)
, mString(str)
{
Log("<Data> Constructor");
}
~Data()
{
Log("<Data> Deconstructor");
}
};
// Helper functions
// ===================================
void PrintData(Data* data)
{
Log("[" + ToAddressString(*data) + "] " + // address
std::to_string(data->mValue) + " " + // value
data->mString); // string
}
#endif // #ifndef Data_h_
main.cpp
// file: main.cpp
#include "Data.h"
#include "DebugOnly.h"
// Main Program
// ===================================
int main() {
// Create an instance of Data from our pool
Data* data = new Data(99, "It seems normal");
// Print it
PrintData(data);
// Destroy it
delete data;
// Print it again
PrintData(data);
// Create another instance of Data from our pool
Data* data2 = new Data(999, "but it's different!");
// Print it
PrintData(data2);
// Destroy it
delete data2;
// Print it again
PrintData(data2);
return 0;
}
The result is:
<BasicPool> BasicPool
<MemoryPool> new
<BasicPool> Allocate
<MemoryPool> MemoryPool
<Data> Constructor
[0x7fb0d1404b30] 99 It seems normal
<Data> Deconstructor
<MemoryPool> delete
<BasicPool> Deallocate
[0x7fb0d1404b30] 99 It seems normal
<MemoryPool> new
<BasicPool> Allocate
<MemoryPool> MemoryPool
<Data> Constructor
[0x7fb0d1404b30] 999 but it's different!
<Data> Deconstructor
<MemoryPool> delete
<BasicPool> Deallocate
[0x7fb0d1404b30] 999 but it's different!
<BasicPool> ~BasicPool
<BasicPool> Clear
Again, same address 0x7fb0d1404b30 is used for two objects.
Performance Test
Now, we compare the time using memory pool mechanism or not.
New_and_Delete.h
#ifndef NewAndDelete_h_
#define NewAndDelete_h_
#include <queue> // std::queue
template<typename T>
class BasicPool
{
public:
BasicPool()
{
};
// Disallow the copy constructor
BasicPool(const BasicPool&)=delete;
// The move constructor
BasicPool(BasicPool&& other)
: mChunks(std::move(other.mChunks))
{
}
~BasicPool()
{
Clear();
}
// Allocate a chunk of memory for the class object
void* Allocate()
{
// If there is no more available memory chunk,
// then we create a new one
if (mChunks.empty()) {
return ::operator new(sizeof(T));
}
// Otherwise, return a free memory chunk
void* chunk = static_cast<void*>(mChunks.front());
mChunks.pop();
return chunk;
}
// Reclaim the memory space from those no longer used objects
void Deallocate(void* obsolete)
{
mChunks.push(static_cast<T*>(obsolete));
}
// Release all of the free memory chunks
void Clear()
{
while (!mChunks.empty()) {
::operator delete(mChunks.front());
mChunks.pop();
}
}
private:
// Holding the pointers to the free memory chunks
std::queue<T*> mChunks;
};
template<typename T, template<typename = T> class Pool = BasicPool>
class MemoryPool
{
public:
// Override new
static void* operator new(size_t size)
{
return mPool.Allocate();
}
// Override delete
static void operator delete(void* p)
{
mPool.Deallocate(p);
}
// Clear the pool
static void Clear()
{
mPool.Clear();
}
private:
// Allow only the inherited objects to call it
MemoryPool() {};
MemoryPool(const MemoryPool&) {};
// Make the inherited objects to access its private members
friend T;
static Pool<T> mPool;
};
// Define the static pool variable that will be called
// in constructor and deconstructor
template<typename T, template<typename = T> class Pool>
Pool<T> MemoryPool<T, Pool>::mPool;
#endif // #ifndef NewAndDelete_h_
DataTest.h
#ifndef DataTest_h_
#define DataTest_h_
#include "New_and_Delete.h"
// Data Structure for Test
// ===================================
struct Data
{
int mValue;
std::string mString;
Data(int val, std::string str)
: mValue(val)
, mString(str)
{
}
~Data() {};
};
struct DataWithPool: public MemoryPool<DataWithPool>
{
int mValue;
std::string mString;
DataWithPool(int val, std::string str)
: mValue(val)
, mString(str)
{
}
~DataWithPool() {};
};
#endif // #ifndef DataTest_h_
main.cpp
#include <iostream>
#include "DataTest.h"
#include "DebugOnly.h"
#define TIMES 40000
#define SIZE 1000
// Main Program
// ===================================
int main() {
// Without the Memory Pool Mechanism
Data* set[SIZE];
const clock_t beginTime1 = std::clock();
for (unsigned int i = 0 ; i < TIMES ; i++) {
// New the objects
for (unsigned int j = 0 ; j < SIZE ; j++) {
set[j] = new Data(99, "Hello World");
}
// Release the objects
for (unsigned int j = 0 ; j < SIZE ; j++) {
delete set[j];
}
}
std::cout << "time: " << float( std::clock() - beginTime1 ) / CLOCKS_PER_SEC << std::endl;
// With the Memory Pool Mechanism
DataWithPool* poolSet[SIZE];
const clock_t beginTime2 = std::clock();
for (unsigned int i = 0 ; i < TIMES ; i++) {
// New the objects
for (unsigned int j = 0 ; j < SIZE ; j++) {
poolSet[j] = new DataWithPool(99, "Hello World");
}
// Release the objects
for (unsigned int j = 0 ; j < SIZE ; j++) {
delete poolSet[j];
}
}
std::cout << "time: " << float( std::clock() - beginTime2 ) / CLOCKS_PER_SEC << std::endl;
return 0;
}
The results:
time: 5.3889
time: 3.63267
The number itself is meaningless.
It really depends on your computer environment.
The important thing is the comparison.
The result reveals the fact that
the new and delete with memory pool mechanism
is faster(3.63267) than without it(5.3889)!