Object pool and fast creation of heap objects

I want to share the next bike of my own assembly in C ++. Bicycle can quickly create and produce objects. As a result, we get the speed of creating (not returning) objects 30% faster than just with new. The object pool is not a new thing, and in general - what can we say about it? But as they say - the main thing in the details.

It so happened that it took me a huge amount of small objects in a C ++ project. At what they needed, as it turned out, in a heap. Objects were nothing more than a description of a position in space. And they contained a 4x4 matrix of double type and several auxiliary variables. Having simplified the original form, we assume that the class (in this case, the structure) has the form:

struct Position{ double m[16]; int s; } 

That is - about 132 bytes.
Having tried several ways, among which was the creation of objects simply through new, I came to the conclusion that it is better to do this using the object pool. For new right in the forehead is a resource-intensive operation.

At once I will make a reservation that with boost , and others like them know very remotely. And therefore, perhaps I describe a bicycle here. However, I personally did not find anything like this (very likely, from what I didn’t know how to call it correctly), but what happened turned out to work very quickly.
')
The object pool is fairly well-known, and in general is a simple pattern to implement. It would seem that there is a difficult thing - create a stack of objects and, as necessary, give it away. When everything is distributed - create more. If the object is no longer needed, we return it to the stack of free objects, instead of deleting it. Let's give an example of the class implementing this pattern:

 template <typename T, unsigned int chunk_size = 100> class Factory { public: inline T* get(){ if(free_ptrs.empty()){ makeMore(); } T* obj = free_ptrs.back(); free_ptrs.pop_back(); return obj; } inline void free(T* obj){ free_ptrs.push_back(obj); } private: std::vector<T> buffer; std::vector<T*> free_ptrs; //   ( ,  chunk_size = 1 ).  chunk_size = 1   loop. void makeMore(){ //   vector.reserve() ,     reserve     //  vector.size() ,     .   //    STL. for (int i = 0; i < chunk_size ; ++i) { buffer.emplace_back(); //         ! free_ptrs.emplace_back(&buffer.back()); //     } } } 

Application:

 Factory<Position> pool; pool.get(); 

Consider the disadvantages of the above method:
- In practice, the creation of a huge number (10,000 - 1,000,000) of small objects in the heap caused a significant decline in productivity. Of course, such hesitation in the work will be observed only at the initial initialization. But still. If you can do well, why not do it?
- The object class being created must have a default constructor!
- The object is returned in an uncertain state. You can of course add a constructor / initializer call, but more on that below.

It was noticed that objects are sooo smartly created in native arrays:

 T* array = new T[]; 

And according to this, we try to create and store objects in a similar way.
It would seem to be enough to make an STL buffer. Reserve. But with each increase in the array, a new native array is created, and then another one by the designer of the copy / transfer in it of all the already existing elements. That is, if we don’t want to add a transfer constructor to the class of our objects, then it will work very slowly.
So, let's rewrite our pool in order to store objects in such buffers:

 template <typename T, unsigned int chunk_size = 100> class Factory { public: inline T* get(){ if(free_ptrs.empty()){ makeMore(); } T* obj = free_ptrs.back(); free_ptrs.pop_back(); return obj; } inline void free(T* obj){ free_ptrs.push_back(obj); } private: /** * @brief Use this against std::vector - because * vector have linear size complexity on reserve. * NOT grow size, but whole size! */ struct Buffer{ T* array; int size; Buffer(int num = chunk_size){ array = new T[num]; size = num; } /** * @brief IMPORTANT! Due to ussage with vector must have it. * @param other */ Buffer(Buffer&& other) noexcept{ size = other.size; array = other.array; other.array = nullptr; } ~Buffer(){ if (array != nullptr){ delete []array; } } }; std::vector<Buffer> buffers; std::vector<T*> free_ptrs; void makeMore(){ buffers.emplace_back(chunk_size); Buffer &buf = buffers.back(); for (int i = 0; i < buf.size; ++i) { free_ptrs.emplace_back(&buf.array[i]); } } }; 

As you can see, the buffer class has a copy constructor. We need it for those cases when std :: vector will decide to perform a reallocate array.
As a result, the initial initialization of the pool accelerated almost in times.

The final touch - using the variety of the new command, we divide the process of allocating memory for the buffer, and the actual constructor call. As a result, it allows us, firstly, to get an “not dirty” object, and secondly, it will allow us to use objects without a default constructor.


The main task, for me, was precisely the fast filling of std :: vector with these small objects. From that the tests are somewhat specific. In my case, the time to fill in with the pool and with emplace_back is the same. When you reuse the pool - naturally the pool wins.