Using Linux at the top when using std :: vector versus std :: list

Question

I noticed some interesting behavior in Linux regarding memory usage (RES), reported by top . I attached the following program, which allocates a couple of million objects on the heap, each of which has a buffer that is about 1 kilobyte. Pointers to these objects are tracked by either std::list or std::vector . An interesting behavior that I noticed is that if I use std::list , the memory usage indicated by top never changes during sleep periods. However, if I use std::vector , memory usage will drop to about 0 during these sleeps.

My test configuration:
Fedora Core 16
Kernel 3.6.7-4
g ++ version 4.6.3

What I already know:
1. std :: vector will redistribute (doubling its size) as needed.
2. std :: list (I beleive) selects its elements 1 at a time
3. both std :: vector and std :: list use default std :: allocator to get their actual memory
4. The program does not proceed; valgrind said no leaks are possible.

What bothers me:
1. Both std :: vector and std :: list use std :: allocator. Even if std :: vector performs batch redistribution, will std :: allocator allocate memory in much the same way as std :: list and std :: vector? In the end, this program is solo. 2. Where can I find out about Linux memory allocation behavior. I have heard claims that Linux supports the RAM assigned to the process even after it frees it up, but I don’t know if this behavior is guaranteed. Why does using std :: vector influence this behavior so much?

Thanks so much for reading this; I know this is a pretty fuzzy issue. The answer is “I'm looking here if this behavior is“ defined ”and where I can find its documentation.

 #include <string.h> #include <unistd.h> #include <iostream> #include <vector> #include <list> #include <iostream> #include <memory> class Foo{ public: Foo() { data = new char[999]; memset(data, 'x', 999); } ~Foo() { delete[] data; } private: char* data; }; int main(int argc, char** argv) { for(int x=0; x<10; ++x) { sleep(1); //std::auto_ptr<std::list<Foo*> > foos(new std::list<Foo*>); std::auto_ptr<std::vector<Foo*> > foos(new std::vector<Foo*>); for(int i=0; i<2000000; ++i) { foos->push_back(new Foo()); } std::cout << "Sleeping before de-alloc\n"; sleep(5); while(false == foos->empty()) { delete foos->back(); foos->pop_back(); } } std::cout << "Sleeping after final de-alloc\n"; sleep(5); } 

Answer 1

Memory is freed up based on a “chunk”. It is possible that when you use a list, the memory is fragmented into small tiny bits.

When distributed using a vector, all elements are stored in one large fragment, so for the memory deallocation code it is easy to say "Golly, I have a very large free region here, I'm going to release it back to the OS." It is also quite possible that when growing a vector, the memory allocator switches to the “big piece” mode, which uses a different distribution method than the “small part mode” - for example, you allocate more than 1 MB, the memory allocation code can see that as a good time, to start using a different strategy and just ask the OS for a "perfect fit" of memory. This large block is very easy to release back into the OS when it is released.

In your ohter hand, if you add to the list, you constantly ask for small bits, so the allocator uses a different strategy for requesting a large block and issuing small portions. It is difficult and time-consuming to ensure that ALL the blocks in the block are freed, so the distributor may well not be “worried” because there are chances that there are some regions that are “still in use” and then it can “anyway.”

I would also add that using the “vertex” as a measure of memory is not a particularly accurate method and very unreliable, since it very much depends on what the OS and the execution library do. The memory belonging to the process may not be "resident", but the process still has not freed it - it simply is not "present in real memory" (instead, in the swap section!)

And to your question “is it defined somewhere”, I think it is in the sense that the original third C / C ++ library defines it. But he did not define in the sense that somewhere he wrote that "it should have worked like that, and we promise never to deceive him." Libraries supplied in the form of glibc and libstd ++ will not say that they will change the internal functions malloc, free, new and delete, because new technologies and ideas have been invented - some of them can improve the situation, others can make the situation worse, for this scenario.

As noted in the comments, memory is not blocked by the process. If the kernel feels that memory is better used for something else [and the kernel is omnipotent here], then it will “steal” the memory from one running process and transfer it to another. Especially a memory that has not been touched for a long time.

Answer 2

1. Both std :: vector and std :: list use std :: allocator. Even if std :: vector performs batch redistribution, would std :: allocator be giving away memory in almost the same layout in std :: list and std :: vector? In the end, this program is single.

Well, what are the differences?

• std::list selects nodes one by one (for each node two more pointers are required in addition to your Foo * ). In addition, it never reassigns these nodes (this is guaranteed by the iterator's invalidation requirements for list ). Thus, std::allocator will request a sequence of fixed-size blocks from the main mechanism (perhaps malloc , which in turn will use the sbrk or mmap system calls). These fixed-size blocks may be larger than the node list, but if so, then they will all be the same default block sizes used by std::allocator .

• std::vector allocates an adjacent block of pointers without regard to overhead (which is everything in the vector parent). Each time push_back will overflow the current distribution, the vector will select a new, larger piece, move everything to a new piece and release the old one. Now the new piece will be something like a double (or 1.6 times or any other) size of the old one, since this is necessary in order to maintain a constant guarantee on push_back . So, pretty quickly, I would expect that the sizes it requests will exceed any reasonable default chunk size for std::allocator .

Thus, interesting interactions are different: one between std::vector and the underlying mechanism of the distributor, and one between std::allocator and this underlying mechanism.

2. Where can I find out about Linux memory allocation behavior. I have heard claims that Linux supports the RAM allocated to the process even after it frees it up, but I don’t know if this behavior is guaranteed. Why does using std :: vector influence this behavior so much?

There are several levels that may be of interest to you:

• Native container layout template: which we hope is described above
  • note that in real applications it is as important as the container is used.
• std::allocator , which can provide buffering level for small distributions
  • I do not think this is required by the standard, so it is specific to your implementation.
• The main distributor, which depends on your implementation of std::allocator (it can be, for example, malloc , however implemented by your libc)
• The VM scheme used by the kernel and its interactions with any syscall (3) ultimately use

---

In your particular case, I can think of a possible explanation for the fact that the vector obviously frees up more memory than the list.

Keep in mind that the vector ends with one adjacent distribution, and the set Foo will also be distributed adjacent. This means that when you free up all this memory, it’s pretty easy to understand that most of the basic pages are really free.

Now consider the distribution of node lists alternating from 1: 1 with Foo instances. Even if the distributor did some tweaking, it seems likely that the heap is much more fragmented than with std::vector . Therefore, when you free selected entries, it will take some work to find out if the base page is free, and there is no particular reason to expect this to happen (if the subsequent large allocation did not prompt to merge the heap entries).

Answer 3

The answer is optimizing the "fastbins" malloc. std :: list creates tiny (less than 64 bytes) distributions, and when it frees them up, they are not actually freed up, but go to the fastblock pool. This behavior means that the heap remains fragmented even after the list is cleared, and therefore it does not return to the system.

You can use malloc_trim (128 * 1024) to force them to clear. Or use mallopt (M_MXFAST, 0) to completely disable fastbins.

I believe that the first solution is more correct if you call it when you no longer need memory.

Answer 4

Smaller chunks go through brk and regulate the data segment and constant splitting and merging, and large chunks mmap - the process is a little less disrupted. more details ( PDF )

also the source code ptmalloc.