reclaiming memory guarantees
i...@mailinator.com
Hi guys,
In Item 17 of Effective STL Meyers writes (in the paragraph before last)
about the swap idiom for all containers in general though the examples he
gives beforehand are only for vectors and strings.
So I was thinking whether, say map().swap(map) would be more effective (in
terms of reclaiming memory) than just map.clear()?
AFAIK there is in the standard that forces an STL implementation of an
associative
container to deallocate all of the memory on element erase (and clear is
just an erase for the entire range). Furthermore nothing requires the
associative
container to allocate exactly the required amount of memory needed for a
new element when it is added. There were rumours that RogueWave STL did just
that.
Furthermore, http://www.sgi.com/tech/stl/FAQ.html, quote:
"... The primary design criterion for the default STL allocator was to
make it no slower than the HP STL per-class allocators, but potentially
thread-safe,
and significantly less prone to fragmentation. Like the HP allocators, it
does not maintain the necessary data structures to free entire chunks of
small objects when none of the contained small objects are in use. This is
an intentional choice of execution time over space use. It may not be
appropriate
for all programs. On many systems malloc_alloc may be more space efficient,
and can be used when that is crucial."
It doesn't look possible to deduce from the quote above what really happens
with the swap trick, when the standard allocator (and not malloc_alloc) is
used. Of course, it doesn't discuss the distinction between swap and erase.
And it shouldn't. It only says the memory may not be released anyway - but
wouldn't the same apply to any erase, both vectors and maps, say, possibly
rendering the swap trick useless in _all cases_ ?
- IY
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Marsh Ray
> ... memory may not be released anyway - but
> wouldn't the same apply to any erase, both vectors and maps, say, possibly
> rendering the swap trick useless in _all cases_ ?
C++ Coding Standards - Sutter, Alexandresu
http://www.amazon.com/gp/product/0321113586
"Although the C++ standard library containers provide no guaranteed
way to trim excess capacity, the following 'swap trick' idiom works in
practice to get rid of excess capacity"
I think "in practice" is the best of a guarantee you'll get.
C++ working draft even says of the delete operator:
"Remarks: It is unspecified under what conditions part or all of such
reclaimed storage is allocated by a subsequent call to operator new or
any of calloc, malloc, or realloc, declared in <cstdlib>."
So even if a container guaranteed to delete something, that wouldn't
necessarily translate to a guarantee that you could re-alloc that
space immediately, which is usually the definition of "freeing memory"
I care about.
- Marsh
Alberto Ganesh Barbati
>
> "... The primary design criterion for the default STL allocator was
> to make it no slower than the HP STL per-class allocators, but potentially
> thread-safe, and significantly less prone to fragmentation. Like the HP
> allocators, it does not maintain the necessary data structures to free
> entire chunks of small objects when none of the contained small objects
> are in use. This is an intentional choice of execution time over space
> use. It may not be
> appropriate for all programs. On many systems malloc_alloc may be more
> space efficient, and can be used when that is crucial."
>
> It doesn't look possible to deduce from the quote above what really
> happens with the swap trick, when the standard allocator (and not
> malloc_alloc) is used. Of course, it doesn't discuss the distinction
> between swap and erase. And it shouldn't. It only says the memory may
> not be released anyway - but wouldn't the same apply to any erase, both
> vectors and maps, say, possibly rendering the swap trick useless in _all
> cases_ ?
You are making a big confusion, IMHO. There are (at least) three levels
of memory "usage" to consider:
1) memory under OS control: this memory is available for any use. It may
or may not be costly to get, especially in little chunks.
2) memory under allocator control: this memory is available for any use
but only through the allocator itself. When the allocator runs out of
memory, it reclaims some more from the OS. When the allocator has unused
memory, it may release it to the OS or keep it. (A degenerate allocator
will always release it, such an allocator will never keep memory under
its control)
3) memory under container control: this memory is available to the
container only.
But now the big question is: what is "free" memory? Can you say that
memory of type 2 is not "free"? It is indeed available for any other
container using the same allocator. If all your containers use the same
allocator, what difference does it make if the memory comes directly
from the OS or from the allocator itself? If you are using the default
allocator, which relies on ::operator new and ::operator delete, then
the memory is also available for all other "normal" allocation through
non-overridden new/delete.
The big issue about the swap() trick is that containers (in particular
std::vector) are allowed to keep some memory of type 3 even if they are
not using it. Such memory can be thought as been wasted, because the
container is not using it and no other container has access to it. Yet
the container can think of it as "free" memory!
By using the swap trick, you have the guarantee (trust me) that all
memory of type 3 is returned to the allocator. Now, the allocator has a
choice: either keep it (the memory becomes of type 2) or release it to
the OS (the memory becomes of type 1). In either case, the memory can be
considered "free" from a certain point of view.
You have to look at the big picture. There is no absolute "free" or
"allocated" memory. It's all about who has control on the memory and how
such control is transfered. Whenever you speak about "free" memory, be
sure to have a clear point of view of what you mean by that.
HTH,
Ganesh
i...@mailinator.com
{ Please don't top-post. -mod }
Thank you, that's what I suspected. So we only have this 'in practice' guarantee,
which any STL implementation free to deviate from.
However, do you know if this guarantee holds for associative containers?
That is, we know, in practice, that the swap trick should trim the memory
of a vector, in a non-eccentric STL implementation, but would it trim the
excessive memory of a map (if the map pre-allocates memory, for example)?
IMO it would be fair to assume that if the STL implementation bothers to
pre-allocate memory in map implementation, they would trim it when the swap
trick is applied.
-- IY
Brendan Miller
...
> By using the swap trick, you have the guarantee (trust me) that all
> memory of type 3 is returned to the allocator. Now, the allocator has a
> choice: either keep it (the memory becomes of type 2) or release it to
> the OS (the memory becomes of type 1). In either case, the memory can be
> considered "free" from a certain point of view.
Some related thoughts, since I thought your discussion of the various
levels of memory allocation was interesting.
I don't believe that type 2 memory is *ever* returned to type 1 memory in
real world systems. If you allocate a couple of gigabytes of memory, free
it, and then spend the rest of the life time using only a couple of
gigabytes, your total heap size should stay at 2 gigabytes, even if 99% of
the heap is sitting unused.
Are there any malloc implementations that are actually known to return
memory to the os?
On unix systems, sbrk and brk are used by malloc to manage heap size.
However, my understanding is they can only manage a contiguous heap, i.e.
cannot unmap pages in the middle of the heap, only increment or decrement
the heap size. Because of this, and the fact that C and C++ don't compact
the heap, it's impossible to unmap pages given the interface available.
I suppose this doesn't really matter on systems with virtual memory, since
memory used by a process but not accessed on a regular basis gets swapped
out and only uses harddrive space.
However, especially on a 64 bit system, it should be possible to
accidentally start chewing through harddrive space until you run out by
spawning a number of long running processes that *collectively* only use a
small amount of memory at any given time, but individually use multiple
gigabytes of memory for brief amounts of time (think daemons/servers).
Remember that linux systems typically use a small seperate partition for
swap space. In that case, to save hd space you might actually want to kill
and restart long running processes. This is kind of analogous to the swap
trick, only on a different level.
Maybe I'm wrong about the hd space issue, and there's some vm trick that
prevents long running process' heaps from getting too bloated over time;
however, I can't think of how that would be done.
Brendan
Erik Wikström
> { Please don't top-post. -mod }
>
>
> Thank you, that's what I suspected. So we only have this 'in practice' guarantee,
> which any STL implementation free to deviate from.
>
> However, do you know if this guarantee holds for associative containers?
> That is, we know, in practice, that the swap trick should trim the memory
> of a vector, in a non-eccentric STL implementation, but would it trim the
> excessive memory of a map (if the map pre-allocates memory, for example)?
>
> IMO it would be fair to assume that if the STL implementation bothers to
> pre-allocate memory in map implementation, they would trim it when the swap
> trick is applied.
While I have not checked I doubt that any implementation pre-allocates
for any container except vector (and perhaps dequeu, can't remember how
it works) since the benefit of doing so is quite small since no re-
allocation is need of already existing elements when new ones are
inserted. This would also mean that the memory freed by removing one
element will probably directly be available for new allocations.
--
Erik Wikström
Erik Wikström
> I don't believe that type 2 memory is *ever* returned to type 1 memory in
> real world systems. If you allocate a couple of gigabytes of memory, free
> it, and then spend the rest of the life time using only a couple of
> gigabytes, your total heap size should stay at 2 gigabytes, even if 99% of
> the heap is sitting unused.
>
> Are there any malloc implementations that are actually known to return
> memory to the os?
OpenBSD does, and I'm sure there are others.
> On unix systems, sbrk and brk are used by malloc to manage heap size.
> However, my understanding is they can only manage a contiguous heap, i.e.
> cannot unmap pages in the middle of the heap, only increment or decrement
> the heap size. Because of this, and the fact that C and C++ don't compact
> the heap, it's impossible to unmap pages given the interface available.
The trick is to not used brk/sbrk and instead use mmap (or similar) so
you can unmap unused memory.
> I suppose this doesn't really matter on systems with virtual memory, since
> memory used by a process but not accessed on a regular basis gets swapped
> out and only uses harddrive space.
>
> However, especially on a 64 bit system, it should be possible to
> accidentally start chewing through harddrive space until you run out by
> spawning a number of long running processes that *collectively* only use a
> small amount of memory at any given time, but individually use multiple
> gigabytes of memory for brief amounts of time (think daemons/servers).
> Remember that linux systems typically use a small seperate partition for
> swap space. In that case, to save hd space you might actually want to kill
> and restart long running processes. This is kind of analogous to the swap
> trick, only on a different level.
>
> Maybe I'm wrong about the hd space issue, and there's some vm trick that
> prevents long running process' heaps from getting too bloated over time;
> however, I can't think of how that would be done.
Unless you can return the memory to the OS, or use non-backed memory
(which does not get swapped out) you can not solve this with just VM
trickery. If you have to write such a system you should consider
spawning a new process for the operations that takes lots of memory.
--
Erik Wikström
Alberto Ganesh Barbati
>
> Some related thoughts, since I thought your discussion of the various
> levels of memory allocation was interesting.
>
> I don't believe that type 2 memory is *ever* returned to type 1 memory in
> real world systems. If you allocate a couple of gigabytes of memory, free
> it, and then spend the rest of the life time using only a couple of
> gigabytes, your total heap size should stay at 2 gigabytes, even if 99% of
> the heap is sitting unused.
>
> Are there any malloc implementations that are actually known to return
> memory to the os?
>
Of course, mine was an oversimplification of the issue, just the sake of
brevity. The fact is that in any implementations there are several
"tiers", the first one usually being the OS (if there's one! there are
embedded systems that don't have a real OS to speak about) and the last
one being a single object. Each tier requests memory from the previous
one and provides memory to the subsequent one(s). While descending this
hierarchy the memory becomes progressively "less free".
For example, there is usually a fourth tier which I didn't mention:
1) OS
2) C runtime
3) allocator
4) container
In this respect, the container could not even be consider a "leaf" in
this hierarchy, so we should add a fifth tier representing the container
element.
There are OSes which have system calls (for example CreateHeap on Win32)
which can be used to provide additional tiers.
To help debugging, I've seen several projects introducing another tier:
1) OS
2) C runtime
3) debug hooks
4) allocator
5) object
So, you see, speaking of when memory is swapped to disk may be an
important detail, but it's nothing more than an implementation-dependent
issue which is way outside the scope of my post and of a C++ discussion
in general.
Just my opinion,
Ganesh