Saeid Yazdani Saeid Yazdani - 2 months ago 7
C++ Question

Deleting elements in vector takes forever to complete

I have a vector of pointers that I really need to make sure the used memory is free before proceeding with other tasks in the program. I do not want to rely on operating system to manage the calls to

delete
so I want to do on my own because later I want to move this code to an embedded platform with limited memory. I have wrote the code below to test a simple scenario: I have choosed the int pointer just for example...the actual data might be something else! e.g. a POD or class

#include <vector>
#include <iostream>
#include <Windows.h>

#define NUM_ELEMENTS 1000000

double PCFreq = 0.0;
__int64 CounterStart = 0;

void StartCounter()
{
LARGE_INTEGER li;
if (!QueryPerformanceFrequency(&li))
std::cout << "QueryPerformanceFrequency failed!\r\n";

PCFreq = double(li.QuadPart) / 1000.0;

QueryPerformanceCounter(&li);
CounterStart = li.QuadPart;
}
double GetCounter()
{
LARGE_INTEGER li;
QueryPerformanceCounter(&li);
return double(li.QuadPart - CounterStart) / PCFreq;
}

int main()
{
/***** CREATE VECTOR **********/
std::cout << "Generating " << NUM_ELEMENTS
<< " elements." << std::endl;

StartCounter();
std::vector<int *>* vec = new std::vector<int*>;
for (size_t i = 0; i < NUM_ELEMENTS; i++)
{
vec->push_back(new int(i));
}

std::cout << vec->size() << " Have been generated in "
<< GetCounter() << "ms" << std::endl;
std::cout << "Destroying the vector..." << std::endl;

/***** DELETE VECTOR **********/

StartCounter();

while (!vec->empty())
{
delete vec->back(), vec->pop_back();
}

vec->clear();
delete vec;

std::cout << "It took " << GetCounter() << "ms to empty the vector!\r\n"
<< "Press ENTER to exit." << std::endl;

//wait for key to exit
std::cin.get();

return 0;
}


And here is the output to console:

Generating 1000000 elements.
1000000 Have been generated in 1077.96ms
Destroying the vector...
It took 16834.9ms to empty the vector!
Press ENTER to exit.


As you can see it takes about 1s to populate the vector but it takes almost 17s to get rid of it.

The code works, for 1000000 elements I get about 35MB of memory and then it starts to shrink back to about 1 MB just before the wait key part. But why it is so slow? how can I improve this behavior?

Hmmm....no one cared to read my question carefully....anyways it was the visual studio playing dumb...I ran the program standalone and it took less than 100ms to fill and delete the vector! hope this experience is useful to others as well

Answer

The improvement is trivial: use vector<int> instead of vector<int*>, since you're storing only one element per pointer.

If your data is larger and you really need to store pointers, use unique_ptr or boost::ptr_vector. This isn't 1980 anymore, you can use RAII.

As for slow cleanup, it's probably because your runtime has a lot of entries in their small allocation structures and has to walk them all to find the correct one.

If you need to have a vector of pointers but need faster deallocation, try keeping the vector of pointers as it is and keep the actual data in deque-like container (a list of array<data_t,32>, perhaps? You'd have to do the index-keeping yourself, but it'd speed up deletion if that's the bottleneck).