C++ Block Allocator for creating new objects faster

Question

I have a piece of code that creates thousand of objects, and appends them to a vector. The following code is just an example of what is being done, even though the constructor has some parameters, and the for does not actually have that condition, but it serves the purpose of showing that it runs thousands of times.

vector<VolumeInformation*> vector = vector<VolumeInformation*>();
for (int i = 0; i < 5000; ++i) {
    VolumeInformation* info = new VolumeInformation();
    vector.push_back(info);
}

The code takes a lot of time to run, and I was trying to find a faster way of creating all the objects. I read about block allocators, but I am unsure if this is really meant for what I am trying to do, and if it really helps on getting this done faster. I would want to allocate memory for a thousand objects (for example), and keep on using that memory while it is still available, and then allocate some more when needed, avoiding having to allocate memory for a single object every time. Can this be done? Can you point me to somewhere where I can find an example on how to tell 'new' to use the previously allocated memory? If not for the objects itself, can the allocator be used for the memory of the vector (even though the object is what really needs speeding up)?

Thank you.

** UPDATE **

After all the answers and comments, I decided making a change in the code, so the vector would store the objects instead of the pointers, so I could use reserve to pre-allocate some memory for the vector, allowing to save some time by allocating memory for several object instances at once. Although, after doing some performance benchmark, I verify that the change I made is performing much worse, unless I know, ahead of time, the exact size of the vector. Here are my findings, I was wondering if someone could shed light into this, letting me know why this happens, if I am missing something here, or if the approach I was using before is really the best one.

Here is the code I used for benchmarking:

    vector<int> v = vector<int>();
    v.push_back(1);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);

    int testAmount = 200000;
    int reserve = 500000;

    Stopwatch w = Stopwatch();





    w = Stopwatch();
    vector<VolumeInformation> infos = vector<VolumeInformation>();
    infos.reserve(reserve);
    for (int i = 0; i < testAmount; ++i) {
        infos.emplace_back(&v, 1, 0, 0);
    }
    int elapsed = w.Elapsed();






    w = Stopwatch();
    vector<VolumeInformation*> infoPointers = vector<VolumeInformation*>();
    infoPointers.reserve(reserve);
    for (int i = 0; i < testAmount; ++i) {
        infoPointers.emplace_back(new VolumeInformation(&v, 1, 0, 0));
    }
    int elapsed2 = w.Elapsed();

If I comment out both reserve() lines, the version without pointers takes 32.701 seconds, while the pointer version takes 6.159! It takes 5+ times less than using a vector of objects.

If I use reserve, but set the amount of items to reserve to a value lower than the number of iterations, the vector of objects version still takes more time than the pointer version.

If I use reserve with a value higher or equal to the amount of iterations, the vector of objects version becomes a lot faster, taking only 270ms, against 8.901 seconds of the pointer version. The main issue here is that I do not know in advance the size that the vector will reach, as the iterations are not based in a hardcoded number, this was only to do the benchmarking.

Can someone explain why this happens, if there is another way around this, or if I am making anything wrong here?

Answer 1

You probably want to reserve space for your 5000 elements ahead of the loop:

vector.reserve(5000);
for (int i = 0; i < 5000; ++i) {
    VolumeInformation info = new VolumeInformation();
    vector.push_back(info);
}

this could save time by eliminating severals resizes as vector grows and if VolumeInformation costs a lot (in time) to copy.

Answer 2

vector is perfectly capable of pre-allocating a large block and using it for all the elements, if you just use it correctly:

// create 5000 default-constructed X objects
std::vector<X> v(5000);

Or if you need to pass constructor arguments:

std::vector<X> v;
v.reserve(5000);    // allocate block of memory for 5000 objects
for (int i=0 ; i < v.size(); ++i)
  v.emplace_back(arg1, arg2, i % 2 ? arg3 : arg4);

The last line constructs an X in the pre-allocated memory, with no copying, passing the function arguments to the X constructor.

I would want to allocate memory for a thousand objects (for example), and keep on using that memory while it is still available, and then allocate some more when needed, avoiding having to allocate memory for a single object every time.

std::vector does that automatically, you should probably stop using new and just have a vector<VolumeInformation> and put objects into it directly, instead of allocating individual objects and storing pointers to them.

Memory allocation is slow (see Why should C++ programmers minimize use of 'new'?), so stop allocating individual objects. Both the examples above will do 1 allocation, and 5000 constructor calls. Your original code does at least 5001 allocations and 5000 constructor calls (in typical C++ implementations it would do 5013 allocations and 5000 constructor calls).

** UPDATE **

If I comment out both reserve() lines, the version without pointers takes 32.701 seconds, while the pointer version takes 6.159! It takes 5+ times less than using a vector of objects.

Since you haven't actually shown a complete working program you're asking people to guess (always show the actual code!) but it suggests your class has a very slow copy constructor, which is used when the vector grows and the existing elements need to be copied over to the new memory (and the old elements are then destroyed).

If you can add a noexcept move constructor that is more efficient than the copy constructor then std::vector will use that when the vector needs to grow and will run much faster.

The main issue here is that I do not know in advance the size that the vector will reach, as the iterations are not based in a hardcoded number, this was only to do the benchmarking.

You could just reserve more elements than you are ever likely to need, trading higher memory usage for better performance.