5

I have an STL container (std::list) that I am constantly reusing. By this I mean I

  1. push a number of elements into the container
  2. remove the elements during processing
  3. clear the container
  4. rinse and repeat a large number of times

When profiling using callgrind I am seeing a large number of calls to new (malloc) and delete (free) which can be quite expensive. I am therefore looking for some way to preferably preallocate a reasonably large number of elements. I would also like my allocation pool to continue to increase until a high water mark is reach and for the allocation pool to continue to hang onto the memory until the container itself is deleted.

Unfortunately the standard allocator continually resizes the memory pool so I am looking for some allocator that will do the above without me having to write my own.

Does such an allocator exist and where can I find such an allocator?

I am working on both Linux using GCC and Android using the STLPort.

Edit: Placement new is ok, what I want to minimize is heap walking which is expensive. I would also like all my object to be as close to eachother as possible to minimize cache misses.

Improve this question
12
  • new and delete's may be the object destructors and constructors contained in the container which makes it somewhow unavoidable Commented Jun 21, 2013 at 10:17
  • @fatih_k This would only hold if the list holds pointers to dynamically allocated objects, though. Which the OP would probably know to avoid, I believe. Commented Jun 21, 2013 at 10:20
  • @Angew, destructors of objects are only called when contained elements are objects instead of being pointers. std::container's does not take the ownership of pointers Commented Jun 21, 2013 at 10:25
  • placement new is ok, I just want to minimize calls to malloc and free Commented Jun 21, 2013 at 10:30
  • 1
    I think you should have a look at these allocator examples: - drdobbs.com/cpp/improving-performance-with-custom-pool-a/… - codeproject.com/Articles/4795/… Commented Jun 21, 2013 at 10:34

4 Answers 4

Reset to default
7

It sounds like you may be just using the wrong kind of container: With a list, each element occupies a separate chunk of memory, to allow individual inserts/deletes - so every addition/deletion form the list will require a separate new()/delete().

If you can use a std::vector instead, then you can reserve the required size before adding the items.

Also for deletion, it's usually best not to remove the items individually. Just call clear() on the container to empty. it.

Edit: You've now made it clear in the comments that your 'remove the elements during processing' step is removing elements from the middle of the list and must not invalidate iterators, so switching to a vector is not suitable. I'll leave this answer for now (for the sake of the comment thread!)

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Except I would like to remove elements in the middle of the list without the memory shuffle that std::vector will entail
@doron Does the order inside the contain matter? If not, you could simply swap to-be-deleted with the last element and pop_back(). No shuffle.
@doron Still, the memory shuffle might be quite less than you think. Look at Bjarne Stroustrup explaining the benefits of vector vs list channel9.msdn.com/Events/GoingNative/GoingNative-2012/… (starts at 44:40) In short, even if you remove a lot and insert a lot, the time for linear search in a list completely dominates the processing time, because the objects are scattered around in memory and that hurts cpu caching.
@doron "Except I would like to remove elements in the middle of the list without the memory shuffle that std::vector will entail" - You're already using a profiler, so just risk a test and compare the speed of vector's shuffle madness to list's allocation madness. The results might be surprising (and might shatter your believes on big-O notation ;)).
@doron Then this is indeed a perfect (if not the only reasonable) use-case for a std::list and is what you should have mentioned in your first comment on this answer instead of the perfomance argument, since the former is a hard reason why you cannot use a std::vector and not a to be discussed away pseudo-reason.
|
6

The allocator boost::fast_pool_allocator is designed for use with std::list.

The documentation claims that "If you are seriously concerned about performance, use boost::fast_pool_allocator when dealing with containers such as std::list, and use boost::pool_allocator when dealing with containers such as std::vector."

Note that boost::fast_pool_allocator is a singleton and by default it never frees allocated memory. However, it is implemented using boost::singleton_pool and you can make it free memory by calling the static functions boost::singleton_pool::release_memory() and boost::singleton_pool::purge_memory().

Improve this answer

4 Comments

this is is the approach I am interested in. I will take a look at this in more detail
I like the idea. My only problem is that the pool is a singleton and the memory is never freed which is a problem when using a long running program for which my list is seldom used.
I like this answer better than mine, now!
I ended up solving this problem by adding "next" pointers to my already existing data structures and managing the linked list myself. However for a general case, I like this answer best.
0

You can try and benchmark your app with http://goog-perftools.sourceforge.net/doc/tcmalloc.html, I've seen some good improvements in some of my projects (no numbers at hand though, sorry)

EDIT: Seems the code/download has been moved there: http://code.google.com/p/gperftools/?redir=1

Improve this answer

2 Comments

I am trying to avoid malloc entirely since malloc allows memory allocations of all sizes. In my container, I do a memory grab and then use the fact that all the elements are the same size so that there is no need for heap walking.
Read through their tests and benchmarks, they are very good with small objects, and tcmalloc never reduces the heap (malloc always grows when needed, free never relinquish to the OS)
-1

Comment was too short so I will post my thoughts as an answer.

IMO, new/delete can come only from two places in this context.

I believe std::list<T> is implemented with some kind of nodes as normally lists are, for various reasons. Therefore, each insertion and removal of an element will have to result in new/delete of a node. Moreover, if the object of type T has any allocations and deallocations in c'tor/d'tor, they will be called as well.

You can avoid recreation of standard stuff by reiterating over existing nodes instead of deleting them. You can use std::vector and std::vector::reserve or std::array if you want to squeeze it to c-level.

Nonetheless, for every object created there must be called a destructor. The only way I see to avoid creations and destructions is to use T::operator= when reiterating over container, or maybe some c++13 move stuff if its suitable in your case.

Improve this answer

2 Comments

Well, constructors and destructors won't neccessarily cause a new/delete anyway and I guess restructuring the to be contained elements is not an option for the OP at all.
@ChristianRau, that is why I said "if the object of type T has any allocations and deallocations". Well actually I made a typo. I rephrased it. Of course they do not have new/delete, but if they have, they will surely manifest.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.