ATL::CStringW vs. std::wstring Performance: String Sorting and Comparisons

According to previous measurements, std::wstring performs better than ATL::CStringW:

  1. in all string concatenation tests
  2. when sorting string vectors that are made by small strings, thanks to std::basic_string’s SSO

So, I focused my attention on the string vector sorting scenario, and it seems to me that (at least in the VS2015 implementation), the slowdown of (non-SSO) wstrings is caused by wmemcmp calls, that are used to compare wstrings when sorting the string vectors. On the other hand, CStringW invokes wcscmp, that seems to run faster.

In fact, invoking std::sort with a custom comparator function that calls wcscmp to compare the C-style pointers returned by wstring::c_str, results in faster vector<wstring> sorting times. So, in this case wstring sorting performs better than CStringW even for non-SSO strings.

However, as Stephan T. Lavavej pointed out, std::basic_string supports embedded nulls, so wstring cannot use wcscmp (that works only for C-style null-terminated strings, without embedded nulls).

 

String Performance Tests: ATL vs. STL

I wrote some C++ code to test the performance of the ATL CStringW class vs. the C++ Standard Library’s std::wstring.

There are several aspects that can be considered when comparing string class performance: In the aforementioned code, I tested string vector sorting and string concatenation.

The code is available in this repository on GitHub.

You can take a look at the README for further details (including my test results).

 

Custom C++ String Pool Allocator on GitHub

I’ve uploaded on GitHub some C++ code of mine, implementing a custom string pool allocator.

The basic idea is to allocate big chunks of memory, and then serve single string allocations carving memory from inside those blocks, with a simple fast pointer increase.

There’s also a benchmark comparing this custom allocator vs. STL’s strings.

Custom string pool allocator benchmark results.
Custom string pool allocator benchmark results.

The results clearly show that both allocating strings that way, and sorting them, is faster than using the default std::wstring class.

 

The Small String Optimization

How do “Connie” and “meow” differ from “The Commodore 64 is a great computer”?

(Don’t get me wrong: They are all great strings! 🙂 )

In several implementations, including the Visual C++’s one, the STL string classes are empowered by an interesting optimization: The Small String Optimization (SSO).

What does that mean?

Well, it basically means that small strings get a special treatment. In other words, there’s a difference in how strings like “Connie”, “meow” or “The Commodore 64 is a great computer” are allocated and stored by std::string.

In general, a typical string class allocates the storage for the string’s text dynamically from the heap, using new[]. In Visual Studio’s C/C++ run-time implementation on Windows, new[] calls malloc, which calls HeapAlloc (…which may probably call VirtualAlloc). The bottom line is that dynamically-allocating memory with new[] is a non-trivial task, that does have an overhead, and implies a trip down the Windows memory manager.

So, the std::string class says: “OK, for small strings, instead of taking a trip down the new[]-malloc-HeapAlloc-etc. “memory lane” 🙂 , let’s do something much faster and cooler! I, the std::string class, will reserve a small chunk of memory, a “small buffer” embedded inside std::string objects, and when strings are small enough, they will be kept (deep-copied) in that buffer, without triggering dynamic memory allocations.”

That’s a big saving! For example, for something like:

std::string s{"Connie"};

there’s no memory allocated on the heap! “Connie” is just stack-allocated. No new[], no malloc, no HeapAlloc, no trip down the Windows memory manager.

That’s kind of the equivalent of this C-ish code:

char buffer[ /* some short length */ ];
strcpy_s(buffer, "Connie");

No new[], no HeapAlloc, no virtual memory manager overhead! It’s just a simple snappy stack allocation, followed by a string copy.

But there’s more! In fact, having the string’s text embedded inside the std::string object offers great locality, better than chasing pointers to scattered memory blocks allocated on the heap. This is also very good when strings are stored in a std::vector, as small strings are basically stored in contiguous memory locations, and modern CPUs love blasting contiguous data in memory!

Optimizations similar to the SSO can be applied also to other data structures, for example: to vectors. This year’s CppCon had an interesting session discussing that: “High Performance Code 201: Hybrid Data Structures”.

I’ve prepared some C++ code implementing a simple benchmark to measure the effects of SSO. The results I got for 200,000-small-string vectors clearly show a significant advantage of STL strings for small strings. For example: in 64-bit build on an Intel i7 CPU @3.40GHz: vector::push_back time for ATL (CStringW) is 29 ms, while for STL (wstring) it’s just 14 ms: one half! Moreover, sorting times are 135 ms for ATL vs. 77 ms for the STL: again, a big win for the SSO implemented in the STL!

 

The Chinese Dictionary Loading Benchmark Revised

Available here on GitHub.

[…] All in all, I’d be happy with the optimization level reached in #2: Ditch C++ standard I/O streams and locale/codecvt in favor of memory-mapped files for reading files and MultiByteToWideChar Win32 API for UTF-8 to UTF-16 conversions, but just continue using the STL’s wstring (or CString) class!

Unicode UTF-16/UTF-8 Encoding Conversions: Win32 API vs. C++ Standard Library Performance

In this MSDN Magazine article, I showed how to convert Unicode text between UTF-16 and UTF-8 encodings using direct Win32 API calls (in particular, I discussed in details the use of the MultiByteToWideChar API).

In addition to that, the C++ standard library offers some classes to perform such conversions.

For example, you can combine std::codecvt_utf8_utf16 with std::wstring_convert to convert from a UTF-16-encoded std::wstring to a UTF-8 std::string:

#include <codecvt>  // for codecvt_utf8_utf16
#include <locale>   // for wstring_convert
#include <string>   // for string, wstring

...
std::wstring_convert<std::codecvt_utf8_utf16<wchar_t>, wchar_t> conversion;
std::wstring utf16 = L"Some UTF-16 string";
std::string utf8 = conversion.to_bytes(utf16);

I developed some C++ code to convert many strings and measure the time spent for the conversions using the aforementioned C++ standard library classes vs. direct Win32 API calls, and the result is clearly in favor of the latter (code compiled with VS2015 in release build):

STL: 1050 ms

Win32: 379 ms  << — Clearly wins

 

A Simple STL vs. ATL String Performance Test – And the Winner Is… STL!

EDIT: New Performance Test available here.

 

In addition to the previous GotW#45 tests executed for the ATL’s and STL’s strings, I wanted to try my own tests. So I developed some simple C++ code that builds a std::vector of strings, and then sorts that vector. This test is executed for both ATL’s CStringW and STL’s wstring. Both the insertion times and sorting times are recorded.

You can check it out on GitHub.

The code was compiled with VS2015, and executed on an Intel i7 workstation running Windows 10 64-bit.

As you can see from the following screenshots, the STL string class always wins (faster execution times). In particular, when the test is executed for tiny strings, the STL’s small string optimization (SSO) is a clear winner over ATL’s CString.

Testing ATL vs. STL String Performance
Testing ATL vs. STL String Performance
Testing ATL vs. STL String Performance (SSO)
Testing ATL vs. STL String Performance (SSO)

I recall I did some similar measurements with older VC++ compiler versions (probably VS2008) and ATL’s CString was a winner back then. C++11’s move semantics and other improvements in the MSVC compiler and in the STL implementation made an important difference here. Kudos to the Visual C++ Team’s compiler and STL library guys for the improvements!

 

Is Copy-on-write Really a Pessimization Under Multithreading?

Copy-on-write (COW) is an optimization technique used by several C++ classes, including the ATL’s CString class, and many classes in the Qt framework.

However, it seems that the C++11 standard bans the use of COW in std::string.

Many developers consider COW a “pessimization” under multi-threading, and to support their argument they usually point to a piece written by Herb Sutter (GotW#45).

I’m an intellectually curious person, so I wanted to test that code on modern systems. I downloaded the original GotW#45 code, did some adjustments to make it compile cleanly with Visual Studio 2015 at warning level 4, changed some stuff like using Windows high-performance counters to measure time (instead of GetTickCount), and added a couple of tests for STL’s std::string and ATL’s CStringA.

You can download the modified code here from GitHub.

On a modern Intel i7-based workstation, the results for 100-char-length strings seem to show that CString (which is COW-based) actually performs better than std::string in those tests.

100-char STL string slower than COW ATL CString
100-char-length std::string’s performance worse than COW-based ATL CString.

However, when strings of shorter lengths are tested (e.g. 10 chars), std::string wins.

So, probably COW is not always a pessimization: there are cases in which the size of the data to copy can have a significant impact.

It’s also interesting that the fbstring class, which is a drop-in replacement for std::string, claiming significantly increased performance, uses COW for large strings.

fbstring uses COW for large strings
fbstring uses COW for large strings

 

P.S. Of course, I’m aware that are several other aspects to consider from a performance perspective, including data locality, etc. Still, I think these results are interesting.