How can I release the free memory held by boost::unordered_map?

Question

I added a large number of elements and then deleted them all in a boost::unordered_map. Then I saw the memory held by this program is 198MB (greater than (64+4)*2M) and the unordered_map size is 0.

I then test a vector, and there is no such problem. Why?

#include <iostream>
#include <boost/unordered_map.hpp>

template <int N>
struct big_struct {
    char c[N];
};

int main(void) {
    typedef big_struct<64> data_type;
    typedef boost::unordered_map<int, data_type*> map_type;

    map_type m;

    for (int i = 0; i < 2000 * 1000; i++) {
            m.insert(std::make_pair(i, new data_type));
    }   

    for (map_type::iterator it = m.begin(); it != m.end();) {
            delete it->second;
            it = m.erase(it);
    }   

    std::cout << "finish, map size " << m.size() << std::endl;
    pause();

    return 0;
}

Answer 1

This is one clear example of what happens when boost become a standard part of C++.

std::unordered_map

is effectively lacking control on releasing memory, the above answer is not correct.

A std::unordered_map may not release any memory until a rehash happens. When a rehash may happen is documented, if you look at size() documentation it just says it is the number of elements, if you want an Idea of the real size you have to add a custom allocator inside the map and count allocated/deallocated bytes.

This is a pity because since the behaviour is not documented (there's not either some API to control that) you don't know if implementation free memory (good if you are going to not use the map for a while), or if implementation cache memory (good if you are going to insert again different elements).

This make using in a memory efficient way the unordered_map very hard. Also this basically leave room for huge memory usage without being documented (it is not stated anywhere that a map with NO ELEMENTS could take several hundreds megabytes)

Here's a custom allocator that profile memory usage

#include <unordered_map> //c++ container but in practice the same of boost
#include <memory>
#include <iostream>
using namespace std;

size_t counter = 0;

template <typename T>
class countingAllocator: public std::allocator<T>
{
public:
    typedef size_t size_type;
    typedef T* pointer;
    typedef const T* const_pointer;

    template<typename _Tp1>
    struct rebind
    {
            typedef countingAllocator<_Tp1> other;
    };

    pointer allocate(size_type n, const void *hint=0){
           counter += n;
            return std::allocator<T>::allocate(n, hint);
    }

    void deallocate(pointer p, size_type n){
            counter -= n;
            return std::allocator<T>::deallocate(p, n);
    }

    static size_t getAllocatedBytes() { return counter;}

    countingAllocator() throw(): std::allocator<T>() {}
    countingAllocator(const countingAllocator &a) throw(): std::allocator<T>(a) { }
    template <class U>                    
    countingAllocator(const countingAllocator<U> &a) throw(): std::allocator<T>(a) { }
    ~countingAllocator() throw() { }
};

template <int N>
struct big_struct {
    char c[N];
};

template<

    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

int main( int argc, char ** argv) {
    typedef big_struct<64> data_type;
    typedef std::unordered_map<int, data_type*, std::hash<int>, std::equal_to<int>, 
                            countingAllocator< std::pair< const int, data_type*>> > map_type;

    map_type m;

    for (int i = 0; i < 1000 * 1000; i++) {
            m.insert(std::make_pair(i, new data_type));
    }   

    for (map_type::iterator it = m.begin(); it != m.end();) {
            delete it->second;
            it = m.erase(it);
    }   

    std::cout << "allocated memory before returning " << countingAllocator< std::pair< const int, data_type*>> ::getAllocatedBytes() << std::endl;

    return 0;
}

and the output of the program:

allocated memory before returning 1056323

So basically that means that you need to call the map destructor in some way to properly get rid of the memory allocated previously and you can do that in several ways:

• put unordered_map into a shared_ptr
• make unordered_map going out of scope

I uploaded the profile code on my PublicProfileTests repository so that you can contribute

Answer 2

The language runtime holds on to the allocated memory, assuming that you might want to use it again. Returning millions of small blocks to the OS would take quite some time, and make your program run slower.

If you have a very large vector, that is still only a single memory block. Some compilers consider returning this kind of memory when it is not needed anymore. Returning one large block is considerably more efficient than a million small blocks.