Sunday, June 16, 2013

On pooling of objects that contain vectors

Recently I had an interesting exercise in de-leaking of our rather complex linguistic analysis system. Actually the system was rather solid and almost didn't leak, but under heavy load in production its memory usage grew slowly but steadily.

First approach was to use some free de-leaking tools, like Visual Leak Detector, but they didn't show any leaks - after application termination all objects were freed.

My next attempt was to analyze growth pattern of memory allocations. I created a small script to dump memory allocations every five minutes with UMDH (that could be found in Debugging Tools for Windows). After running this thing overnight I parsed outputs with another script and dumped it into huge Excel spreadsheet for further analysis.

I was surprised to see that there were only few allocations that had growing trend, and they all belong to the memory allocator within std::vector.

After few days I finally realized that it is not the size of the vector was growing, but their capacity. The problem was with rather complex, heavy-to-construct object that had few vectors in it. As the object was really complex and algorithm had to run very fast, objects were not constructed but rather taken from the pool.

Of course, before putting object back to pool it was cleared (e.g. the vector was empty after calling clear() method), but the underlying memory buffer that was allocated was not cleared. It would not be a problem if the vector in all cases would have similar size, however in our case average size was about 1.5, but the maximum size sometimes went up to 100.

This means that eventually after running long enough each pooled object will contain an empty vector that has a buffer to hold 100 elements.

Of course the fix was trivial, and such technique is mentioned in Effective STL by Scott Meyers. Instead of calling std::vector::clear() I did following:
std::vector<MyType>().swap(m_vMyTypes);
which basically swaps newly constructed (and thus empty) vector with existing one, freeing all memory that was held. Also the similar effect could be observed with std::deque collection - it also does not free allocated memory after call to clear().

This all means that everyone should be very careful when putting complex objects that contain STL collections into object pools.

7 comments:

  1. So technically speaking this case was not a leak at all, right? If your system was aimed to run 24\7 at some point you would reach PoolSize*MaxPoolObjectSize memory footprint and that's it, of course if your RAM could afford that much

    ReplyDelete
  2. Technically that is not a leak, but it has the same consequences - eventually you'll have to restart the service that runs 24\7 due to its workspace that grew beyond acceptable values

    ReplyDelete
  3. I had similar problem. The resolution was to keep track of total memory usage by objects of pool, and then if it gets above threshold upon returning the object to pool, freeing this object's vector allocations.
    Yet, this might not be enough, because freeing the object which overflows pool's total memory may be not efficient if the real big object has been returned before. In this scenario, we may constantly allocate and free very small chunk of memory, which isn't efficient. A solution to this would be to sort the objects in pool by their memory usage size (using a heap, for example), and then retrieving the largest of them for next usage.

    ReplyDelete
  4. In my situation I was not actually restricted by total memory usage, so tracking total size of the object looked like overkill. To reduce performance impact I implemented periodical 'deep' clean-up that actually frees vector's memory

    ReplyDelete
  5. what about calling http://en.cppreference.com/w/cpp/container/vector/shrink_to_fit after a "clear()" call?

    ReplyDelete
    Replies
    1. It is not better than swap() approach I have used - both involve memory (de)allocations. As I mentioned in previous comments swapping each time when object returns to the pool was rather expensive, so I did such clean-up after each document processed (that means few times per second).

      Delete
  6. Once I had a similar issue which happened because of a default vector allocator strategy which caused a memory fragmentation due to a frequent use of allocate/free with different object size, finally I got a bad_alloc while having hundreds of megabytes free memory in total. The solution was to use a custom allocator without allocating x2 (GCC) or 1.5 (CL) capacity for most frequently used objects.
    I believe it would be even more reasonable to cover immutable objects with flyweights (i.e. boost/flyweight.hpp) to avoid keeping any extra copies.

    ReplyDelete