Ruminations on the standard C++ library — Dynamic arrays III—Cleaning up your mess

As it had happened many a time before I was, once again, stuck, the evening
before my homework was due, in the computer lab. This time, however, I wasn’t
alone. The computer lab was overstuffed with people working on assignments. Odd
phrases were thrown hither and yon through the room, people walking back and
forth between the printer room, other people discussing circuitry design. Enough
people to let you lose your focus one time too many.

As the strange, robed guy had shown me some time ago, I was working with
vector, storing pointers to structures in it. The structures
modeled an in-memory logging function, but that is beyond the point. The point
was that after having run for a few hours, it showed that the process was eating
over 800 MB of memory. Now, considering it was a straightforward program, I set
out to simplify it to figure out the source of the problem. Simplified my source
code looked as follows.

#include <vector>

struct A {
  size_t a_;
  A(size_t a) : a_(a) {}
  A(const A& a) : a_(a.a_) {}
  ~A() {}
};

int main() {
  std::vector<A*> as;

  size_t i = 0;
  while (1) {
    as.push_back(new A(i++));
    if (i == 400) {
      as.clear();
      i = 0;
    }
  }

  return 0;
}

So… it will add the 400 elements that are placed on the heap to the
vector as. Then when the counter reaches 400 it will empty the
list, thus freeing the memory, and keep on doing that for however long the
program is running, but why does it use up all the memory then?

‘It does what?!?’ an eerily familiar voice said behind me.

I heard the swirling of robes from a person turning around, and I realised I
must have said what I was thinking aloud.

I shrugged, ‘I don’t know, you told me that the vector would clean
up the memory it used when you removed elements from it. So when I call
as.clear() it should clean up the memory it had used, but
considering this program just increases its use of memory continuously, I guess
that’s not the case… but why?’

Someone from across the room called, ‘Hey, Ialmenes, have a minute?’

The robed man waved at them to acknowledge them and then returned his attention
to me.

‘What I said was correct, vector frees up the memory it has used
when you clear its contents. So why does your code not free up the memory when
you clear the vector?’ Ialmenes looked at me focused, ignoring the
chatter of the surrounding desks.

I looked back at my source code and pondered for a minute or so. Then I turned
back to Ialmenes and shrugged, ‘I have no idea, whatsoever.’

‘Ok… vector stores object of the type you ask it to by value.
Let’s investigate two ways to store integers.’ he pulled up a whiteboard that
was standing a few feet away and started writing.

#include <vector>

void test_1() {
  std::vector<int> vec;
  for (int i = 0; i < 10; ++i)
    vec.push_back(i);
  vec.clear();
}

void test_2() {
  std::vector<int*> vec;
  for (int i = 0; i < 10; ++i)
    vec.push_back(new int(i));
  vec.clear();
}

‘Ok let’s walk through what happens here… In the first function,
test_1, we have a vector that stores ints. That is, it stores actual
integers, not references or pointers to them, thus int is the value type
of vector<int>. That means when you insert one of the integers,
say i, then it copies the value of the integer into memory managed by
the vector. Thus, when we call clear we deallocate the memory used of
the objects of the value type stored in vector.’ Ialmenes looked up
at me. ‘With me so far?’

I nodded reluctantly. ‘We’re storing actual int objects in the
vector, not pointers to them.’

‘Ok, so with the next it’s pretty much the same thing, except we
are now storing int* objects. An int* object points to some place on
the heap, that is into the memory. This means that when we call clear
then we deallocate the pointers, not the memory that the pointers point
to.’ he cleared his throat and continued, ‘This is one of the critical
points to understand. The pointer is inside the vector whereas the
memory on the heap is away from the pointer – the pointer merely is a
way to access this memory, but you have to call delete on the pointer
for it to deallocate the memory on the heap that it points to. This
isn’t done by clear.’

‘So what you’re saying is that we throw away the pointers. And when
we have thrown away the pointers we have no way to know where the
allocated memory is, but it doesn’t go away for that reason. So we need
some way to call delete on each element of the vector of int*’s before
we clear the contents?’ I said, still feeling a bit uncertain about
what all was going on here.

Ialmenes nodded, seemingly satisfied with what I had said.
‘So, how do you presume we solve the memory leak?’

‘I suppose we need to call delete on each element before we clear
the contents of the vector?’ I said a bit hesitant.

He handed me the marker, ‘Pray, show me.’

I erased what he had written and started to write.

struct A {
  ...
};

int main() {
  std::vector<A*> as;

  size_t i = 0;
  while (1) {
    as.push_back(new A(i++));
    if (i == 400) {
      for (size_t j = 0; j < as.size(); ++j)
        delete as[j];
      as.clear();
      i = 0;
    }
  }

  return 0;
}

‘That should free all the memory allocated on the heap and then
clear out all the pointers.’ I said, satisfied at being able to pick
up his lengthy explanation.

Ialmenes smiled. ‘Yes, now that is one way to do it. Another way to
free up the memory and clear the vector would be like this…’ he took
a marker from a pocket in his robes.

while (!as.empty()) {
  delete as.back(); as.pop_back();
}

‘Which you pick is a matter of preference only, really,’ he
continued. ‘Now, fix your program, it should no longer use all the
memory on the server.’ continuing in a lower voice he said ‘and
managing to annoy everyone currently using that server as well.’ with
a smile he walked over to the group of people who had called for
him earlier.

I shook my head slightly. How could he go on doing this all night,
I was completely wasted after just this one teaching session with him.
I quickly pondered whether it would just be better to skip classes and
hang out here listening, but soon discarded the idea as I continued with
my assignment.

References

  1. C++ supports both normal and wide string literals. The latter exist to
    accommodate for programming with other character sets than the ‘normal’ ASCII
    character set, if you, for instance, want to implement a program for a language
    other than English.

Sub-Pages