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

[fish]

I just add a large of elements and then delete them all in a
boost::unordered_map, then I saw the memory held by this program is
198M(greater than (64+4)*2M) and the unordered_map size is 0.

I test vector, 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;
}

 

[Luca Risolia]

I just add a large of elements and then delete them all in a
boost::unordered_map, then I saw the memory held by this program is
198M(greater than (64+4)*2M) and the unordered_map size is 0.

boost::unordered_map is probably not required to shrink the memory it
has already allocated for the old elements after you clear the map.

I don't know if the boost map version provides an explicit method to
shrink the used memory; in case you may want to try the clear and
minimize idiom:

https://en.wikibooks.org/wiki/More_C++_Idioms/Clear-and-minimize

"Standard library containers often allocate more memory than the actual
number of elements in them. Such a policy results in an optimization of
saving some allocations when a container grows in size. On the other
hand, when size of the container reduces, there is often leftover
capacity in the container. The leftover capacity of the container can be
unnecessary wastage of memory resources. clear-and-minimize idiom has
been developed to clear a container and reduce the extra capacity to a
minimum of zero and thereby saving memory resources."

 

[zoltan.juhasz]

I just add a large of elements and then delete them all in a
boost::unordered_map, then I saw the memory held by this program is
198M(greater than (64+4)*2M) and the unordered_map size is 0.

This is actually a fairly complex question, because many factors
might cause the observed behaviour:

- malloc's release policy, i.e.: when it is actually releasing
memory to the OS
- std::unordered_map underlying container's allocation /
release strategy (i.e. std::vector's reserved memory does not
shrink as you remove elements).

Since in this case you do not physically store the elements in
the map, but dynamically allocate, I suspect that your allocation
strategy triggers a pathological case, which can be described
as follows:

- 1, allocate 5GB memory (in smaller chunks, i.e. 100 bytes)
- 2, allocate additional 100 bytes
- 3, release memory allocated in 1,

Since many malloc implementation treats the heap memory as a single
stack, and when acquiring / releasing memory, it simply adjusts the
heap segment ptr via. sbrk or similar, the heap state can be
described as follows (ignoring details):

1. before allocating 5 GB

| |
| |
| |
+--+ <- current heap segment ptr
| |


2. malloc 5 GB

| |
+--+ <- current heap segment ptr
|XX|
|XX|
+--+ <- old heap segment ptr
| |


3. malloc additional 100 bytes

+--+ <- new heap segment ptr
|OO|
+--+ <- old1 heap segment ptr
|XX|
|XX|
+--+ <- old2 heap segment ptr
| |


4. delete / free the 5GB part

+--+ <- new heap segment ptr
|OO|
+--+ <- old1 heap segment ptr
| | <- Unused
| | <- Unused
+--+ <- old2 heap segment ptr
| |

Nothing happens as far as the OS is concerned, since allocator was
not able to release memory back to the OS, since the top of the heap
is being used. Ofc. if you malloc additional data, it most likely
will be served from the unused space between old1 and old2.

As you can see, you have to distinguish between memory actively used
by your code, and that is actively managed by the allocator. In this
case it is 100 byte vs 5GB + 100 byte + other stuff.

So without having further environment related details, I would guess
that using the previous example,

- large data-set is originated from your 'big_struct' allocations,
- smaller portion (that is staying on the top of the heap) is the
result of internal reallocation of the unordered_map's internal
bucket buffer.

Try to release the internal buffer with:

unordered_map< ... >().swap( myUnorderedObject )

which should get rid of the internal bucket buffer, thus removing
that small portion from the top of the heap, and malloc most likely
will be able to decrease the heap segment ptr.

Alternative solution is to simply 'pre-reserve' the appropriate
buffer size, thus avoiding the pathological case described above.

---

Additional notes:

I did not touch another but related aspect: just because your
application reports xMB of memory being used, it does not mean it
is resident in memory at all (i.e. no physical page is associated
with it).

Also, more sophisticated malloc's (i.e. jmalloc, tmalloc) provides
better release characteristics by creating internal size-based
segregation etc.

-- Zoltan

 

[Nobody]

I just add a large of elements and then delete them all in a
boost::unordered_map, then I saw the memory held by this program is
198M(greater than (64+4)*2M) and the unordered_map size is 0.

I test vector, no such problem. Why?

Dynamically-allocated memory isn't always returned to the OS when it's no
longer used. More often, it will simply be returned to the user-space heap
where it will be used to satisfy subsequent allocations.

Some implementations may return large, contiguous, wholly-unused chunks of
memory to the OS. This is more likely to be applicable to a vector than
to other containers.

Also: AFAIK, the standard doesn't even require containers to return memory
to the global heap when the number of elements is reduced. Unused memory
may be retained by the individual container instance, or by the allocator
class used by the container class.

 

[Juha Nieminen]

boost::unordered_map is probably not required to shrink the memory it
has already allocated for the old elements after you clear the map.

Nitpicking, but boost::unordered_map is not required to do anything
(except perhaps as in internal policy of the Boost project developers).

std::unordered_map may be a different issue, though.