C++ String Benchmark: STL vs. ATL vs. Custom Pool Allocator

As you probably already know, there are quite a few different kinds of strings available in C++. I was curious to compare the performance of Microsoft Visual Studio C++ STL string implementation versus ATL CString versus a custom string pool allocator.

Basically, the pool allocator maintains a singly-linked list of chunks, and string memory is carved from each chunk just increasing a string pointer. When there isn’t enough memory available in the current chunk to serve the requested allocation, a new chunk is allocated. The new chunk is safely linked to the previous chunk list maintained by the allocator object, and the memory for the requested string is carved from this new chunk. At destruction time, the linked list of chunks is traversed to properly release all the allocated memory blocks.

You can find the complete compilable C++ implementation code on GitHub.

I measured the execution times to create and fill string vectors, and the execution times to sort the same vectors.

TL;DR: The STL string performance is great! However, you can improve creation times with a custom pool allocator.

The execution times are measured for vectors storing each kind of strings: STL’s wstring, ATL’s CString (i.e. CStringW in Unicode builds), and the strings created using the custom string pool allocator.

This is a sample run (executed on a Windows 10 64-bit Intel i7 PC, with code compiled with Visual Studio 2019 in 64-bit release build):

As you can note, the best creation times are obtained with the custom string pool allocator (see the POL1, POL2 and POL3 times in the “Creation” section).

For example:

String type	Run time (ms)
ATL CStringW	954
STL std::wstring	866
Pool-allocated strings	506

In the above sample run, the pool-allocated strings are about 47% faster than ATL’s CString, and about 42% faster than STL’s wstring.

This was expected, as the allocation strategy of carving string memory from pre-allocated blocks is very efficient.

Regarding the sorting times, STL and the custom pool strings perform very similarly.

On the other hand, ATL’s CString shows the worst execution times for both creation and sorting. Probably this is caused by CString implementation lacking optimizations like move semantics, and using _InterlockedIncrement/_InterlockedDecrement to atomically update the reference count used in their CoW (Copy on Write) implementation. Moreover, managing the shared control block for CString instances could cause an additional overhead, too.

Historical Note: I recall that I performed a similar benchmark some years ago with Visual Studio 2008, and in that case the performance of ATL’s CString was much better than std::wstring. I think move semantics introduced with C++11 and initially implemented in VS2010 and then refined in the following versions of the C++ compiler, and more “programming love” given to the MSVC’s STL implementation, have shown their results here in the much improved STL string performance.

Benchmark Variation: Tiny Strings (and SSO)

It’s also possible to run the benchmark with short strings, triggering the SSO (to enable this, compile the benchmark code #define’ing TEST_TINY_STRINGS).

Here’s a sample run:

As you can see in this case, thanks to the SSO, STL strings win by an important margin in both creation and sorting times.