vector reallocation C++

Question

I was working with memory optimization while loading data in Vectors . I want to know what happens with the memory used by Vector when vector reallocates . I mean is it freed by Vector or not ?

thnaks in advance .

Answer 1

For example, this is vector resize implementation in gcc 4.8.2:

  void resize(size_type __new_size)
  {
    if (__new_size > size())
      _M_default_append(__new_size - size());
    else if (__new_size < size())
      _M_erase_at_end(this->_M_impl._M_start + __new_size);
  }

So if new size is larger than the current vector size, _M_default_append is called:

template<typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_default_append(size_type __n)
{
  if (__n != 0)
    {
      if (size_type(this->_M_impl._M_end_of_storage 
                   - this->_M_impl._M_finish) >= __n)
        {
          std::__uninitialized_default_n_a(this->_M_impl._M_finish,
                                           __n, _M_get_Tp_allocator());
          this->_M_impl._M_finish += __n;
        }
      else // if new size is larger, execution flow goes here
        {
          //get size of a new memory block allocated for internal storage
          const size_type __len =
            _M_check_len(__n, "vector::_M_default_append");
          const size_type __old_size = this->size();
          //allocate new memory block
          pointer __new_start(this->_M_allocate(__len)); 
          pointer __new_finish(__new_start);
          __try
            {
              //move existing elements to a new memory if stored objects are movable
              //or just copy them
              __new_finish
                = std::__uninitialized_move_if_noexcept_a
                (this->_M_impl._M_start, this->_M_impl._M_finish,
                 __new_start, _M_get_Tp_allocator());
              //create new elements at the end of the storage
              std::__uninitialized_default_n_a(__new_finish, __n,
                                               _M_get_Tp_allocator());
              __new_finish += __n;
            }
          __catch(...)
            {
              // if exception was thrown while coping, destroy elements in new storage
              // and throw exception again
              std::_Destroy(__new_start, __new_finish,
                            _M_get_Tp_allocator());
              // deallocate new memory
              _M_deallocate(__new_start, __len);
              __throw_exception_again;
            }
          // call destructors of the elements in the old storage
          std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
                        _M_get_Tp_allocator());
          // deallocate memory used for the old storage
          // _M_deallocate here checks if _M_start is not null and 
          // calls allocator's deallocate method
          _M_deallocate(this->_M_impl._M_start,
                        this->_M_impl._M_end_of_storage
                        - this->_M_impl._M_start);
          // set new storage to this vector object
          this->_M_impl._M_start = __new_start;
          this->_M_impl._M_finish = __new_finish;
          this->_M_impl._M_end_of_storage = __new_start + __len;
        }
    }
}

So, as you can see, vector uses allocator's deallocate method to remove old storage. If this is the default std::allocator, it uses new and delete operators internally. This operators usually call malloc/free methods. Some malloc implementation have tools to profile heap and to detect memory bugs, also some have options to disable memory caching in internal arenas, so you can make it return memory to OS when free is called. See tcmalloc and jemalloc.

Answer 2

I am not allowed to comment due to less reputation, but you might find this helpful:

c++ Vector, what happens whenever it expands/reallocate on stack?

Answer 3

Failing to free memory that it was no longer using would be a fairly obvious bug in an implementation of std::vector. Of course, bugs do happen, so it's barely possible you could find such an implementation problem, but you'd normally expect vector to be fairly well tested so finding such a thing seems fairly unlikely (and if you did, it would probably be something that happened only under relatively obscure circumstances).

Of course, vector uses an Allocator argument (which defaults to std::allocator<T>) to do the actual allocation and freeing of memory (among other things). As such, a bug in the allocator class could lead to memory not being freed as intended either. Assuming you use std::allocator<T>, I'd be fairly surprised to see this happen, but if (for example) you're using somebody else's allocator class, problems could be quite a bit more likely (the allocator class' interface isn't immediately obvious, and good documentation on it isn't particularly common).

For what it's worth, in most (recent) implementations I've seen, vector expands by a factor 1.5 when it runs out of space. If the factor is smaller than the golden mean (~1.6) and the previous allocations are contiguous with each other, they'll (eventually) add up to a chunk that can satisfy a later requirement. If the factor is larger than the golden mean, they never will.

Answer 4

Bear in mind that if you measure memory usage based on "top" or "Task Manager", the memory "freed" is not necessarily actually "made to go away". Most modern heap managers don't free the memory all the way down to the OS level, since the expectation is that memory allocated once will be needed again. Only once the amount freed reaches a certain limit (of a contiguous range, so if there are small "islands" of still used memory in the sea of freed memory, it can't be freed as one block and will most likely stay with your application "forever").

There is nothing much you can do about this, just live with it. If you know beforehand how much memory you need, use reserve() to reserve it. If you don't, let it grow by itself. The memory is freed, it's just not given back to the actual OS as "free memory", it sits in the heap of your application. If there is low memory in the overall system, the memory that isn't used will be swapped out and other, more useful things will be loaded into memory in its place, so it's not "occupied and can never be used for anything else". (Of course, if you have little islands of used memory that gets accessed every now and again, then it's likely that the memory can't be reused).