Pluralsight FREE Week

Just a heads up to let you know that Pluralsight is unlocking its technology skills platform and making 7,000+ expert-led video courses, 40+ interactive courses and 20+ projects FREE for one week only (April 25th – May 1st).

This includes my courses on learning modern C++ from scratch, practical C++14 and C++17 features, introduction to data structures and algorithms in C++, getting started with the C language, and more.

Happy learning!

Adventures with string_view: Optimizing Code with O(1) Operations

Last time we saw that you can invoke the CString::GetString method to get a C-style null-terminated const string pointer, then pass it to functions that take wstring_view input parameters:

// name is a CString instance;
// DoSomething takes a wstring_view input parameter
DoSomething(name.GetString());

While this code works fine, it’s possible to optimize it.

As the saying goes, first make things work, then make things fast.

The Big Picture

A typical implementation of wstring_view holds two data members: a pointer to the string characters, and a size (or length). Basically, the pointer indicates where the string starts, and the size/length specifies how many consecutive characters belong to the string view (note that string views are not necessarily null-terminated).

The above code invokes a wstring_view constructor overload that takes a null-terminated C-style string pointer. To get the size (or length) of the string view, the implementation code needs to traverse the input string’s characters one by one, until it finds the null terminator. This is a linear time operation, or O(N) operation.

Fortunately, there’s another wstring_view constructor overload, that takes two parameters: a pointer and a length. Since CString objects know their own length, you can invoke the CString::GetLength method to get the value of the length parameter.

// Create a wstring_view from CString (*)
DoSomething({ name.GetString(), name.GetLength() });

The great news is that CString objects bookkeep their own string length, so that CString::GetLength doesn’t have to traverse all the string characters until it finds the terminating null. The value of the string length is already available when you invoke the CString::GetLength method.

In other words, creating a string view invoking CString::GetString and CString::GetLength replaces a linear time O(N) operation with a constant time O(1) operation, which is great.

Fixing and Refining the Code

When you try to compile the above code marked with (*), the C++ compiler actually complains with the following message:

Error C2398 Element '2': 
conversion from 'int' 
to 'const std::basic_string_view<wchar_t,std::char_traits<wchar_t>>::size_type' 
requires a narrowing conversion

The problem here is that CString::GetLength returns an int, which doesn’t match with the size type expected by wstring_view. Well, not a big deal: We can safely cast the int value returned by CString::GetLength to wstring_view::size_type, or just size_t:

DoSomething({ name.GetString(), 
    static_cast<size_t>(name.GetLength()) });

As a further refinement, we can wrap the above wstring_view-from-CString creation code in a nice helper function:

// Helper function that *efficiently* creates a wstring_view to a CString
inline std::wstring_view AsView(const CString& str)
{
    return { str.GetString(), 
             static_cast<size_t>(str.GetLength()) };
}

Measuring the Performance Gain

Using the above helper function, you can safely and efficiently create a string view to a CString object.

Now, you may ask, how much speed gain are we talking here?

Good question!

I have developed a small simple C++ benchmark, which shows that replacing a O(N) operation with a O(1) operation in this case gives a performance boost of 88 ms vs. 445 ms, which is an 80% performance gain! Wow.

Benchmark comparing two wstring_view constructor overloads
Benchmark comparing two wstring_view constructor overloads

If you want to learn more about Big-O notation and other related topics, you can watch my Pluralsight course on Introduction to Data Structures and Algorithms in C++.

Big-O doesn’t have to be boring!