Monday, June 16, 2008

The beginnings: Speeding up C++ STL Vector applications

Having started this blog quite some time ago, I didn't have any idea what I was going to post in it. I only knew that it would contain tips and tricks for AIX which one might find handy, some of which one might find elsewhere, some of which one may not find elsewhere. I still am not sure as to what sort of tips and tricks I'm going to put, but I'll put them, thats for sure. Don't ask me about the frequency.

This first post is for guys who use STL Vectors heavily in their C++ code. If you guys want an improvement in performance, you might want to use the 3.1 malloc allocation policy. All you have to do is to export one of the following environment variable before running your code:

export MALLOCTYPE=3.1 #for 32-bit applications
export MALLOCTYPE=3.1_64BIT #for 64-bit applications

How does it help? Well, it appears, that a vector keeps growing itself as and when it needs. Hence a lot of calls to realloc(). What happens with the 3.1 allocation policy is that requests are rounded up to the next higher power of 2. That is if you request 1026 bytes, you get 2048 bytes. Hence when a realloc is done, it often returns without doing any work since the memory is already there.
3.1 is also faster than the default allocation policy as the default allocation policy uses a tree based data structure, essentially forcing the average time of O(log(n)), 3.1 is a bucket-based allocator with time complexit O(1).
The caveat to using 3.1 is that it is wasteful of memory, so its upto you to decide what you want to compromise on. Memory usage or speed.

How we found this out? Well, we were running some benchmark tests, and on exporting MALLOCTYPE=3.1 we found the performance to shoot up by 40%. Of course, the benchmark we were running was memory bound.

No comments: