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!

Adventures with string_view: Making string_view Play Well with ATL/MFC CString

Suppose that you have a C++ code base containing methods and functions that take ATL/MFC CString objects as input parameters, for example:

void DoSomething(const CString& s)

and you want to introduce the use of std::string_view in that code.

Let’s assume that your code base is built using Visual Studio in Unicode mode (Configuration Properties | Advanced | Character Set set to Use Unicode Character Set), which has been the default since Visual Studio 2005. In this case, CString is actually the wchar_t-based CStringW, and the matching std::basic_string_view is the wchar_t-based std::wstring_view.

(Note: It could be possible to convert between Unicode UTF-16 CStringW and UTF-8, and store the UTF-8 encoded text in a std::string object, and take a std::string_view on that, but let’s not make things even more complicated!)

So, you may think of adding a wstring_view overload like this:

void DoSomething(std::wstring_view s)

Unfortunately, that would cause a problem with your pre-existing perfectly compiling code. In fact, if you pass a string literal, like this:

DoSomething(L"Connie");

the C++ compiler now has two options for DoSomething: the initial form that takes a const CString&, and the new one that takes a wstring_view. The C++ compiler has no way to choose which overload to pick, so it emits an error complaining about the ambiguous call to the DoSomething overloaded function.

At this point, you may think of removing the previous CString overload, and only keep the new wstring_view version:

// Removed: void DoSomething(const CString&)
void DoSomething(std::wstring_view s)

OK, now the C++ compiler is happy as there is only one function to pick.

So, problem solved? Nope.  Don’t forget that this is C++! 😊 And things can get more “interesting” when you apparently solved one problem.

For example, in your existing code base you almost certainly have a number CString objects around. For the sake of simplicity, consider this code snippet:

CString name;
DoSomething(name);

This code worked perfectly fine before you added wstring_view, but now the compiler complains! The problem this time is that the C++ compiler cannot find a suitable way to convert from CString to wstring_view. How can you fix that?

Well, you can invoke the CString::GetString method. In fact, this method returns a const wchar_t* raw pointer to the NUL-terminated C-style string associated with the CString object. And wstring_view has a constructor overload that matches this particular case, constructing a view of the NUL-terminated character string passed as input pointer parameter.

This will work:

// name is a CString
DoSomething(name.GetString());

Another important consideration to make is that wstring_view is just a view to a string, so you must pay attention that the pointed-to string is valid for at least all the time you are referencing it via the wstring_view. In other words, pay attention to dangling references and string views that refer to strings that have been deallocated or moved elsewhere in memory.

 

Open Source: Who Pays for It?

Recently I worked on my C++ WinReg library for a couple of hours, adding some useful methods, testing them, and packaging the library for vcpkg distribution.

At a reasonable rate of $150/hour, that would be $300.

And that’s not even counting all the many hours I spent in total on this open-source project.

This library has currently more than 260 stars on GitHub, and many forks. It seems to me it is used by many people.

But who pays for it?

I think there should be some process to allow developers of useful open-source code hosted on GitHub (or on other platforms as well) to be fairly compensated for their work.

Simplifying Windows Registry Programming with the C++ WinReg Library

WinReg is a modern C++ library I wrote that exposes a high-level public interface to simplify the access to the Windows Registry.

For instance, instead of invoking low-level C-interface APIs like RegOpenKeyEx or RegQueryValueEx, you can simply create an instance of the winreg::RegKey class:

RegKey key(HKEY_CURRENT_USER, L"SOFTWARE\\SomeKey");

and invoke convenient RegKey’s methods like GetStringValue:

wstring s = key.GetStringValue(L"Connie");

Note that this library wraps low-level native Windows C API types into higher-level C++ classes like std::wstring for Registry string values, or std::vector<std::wstring> for multi-string values.

The C++ WinReg library is open source and freely available on GitHub.

Enjoy!

 

 

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

I was curious to compare the performance of the STL string implementation versus ATL CString, using Visual Studio 2019, so I wrote some simple C++ benchmark code for this purpose.

I also added into the mix a custom string pool allocator based on some code from The Old New Thing blog, that I modified and bug-fixed. This allocator basically 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 in the current chunk to serve the allocation, a new chunk is allocated. The new chunk is safely linked to the previous chunk list, and the memory for the requested strings is carved from this new chunk. The linked list of chunks is traversed at destruction time to properly release the allocated memory blocks.

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

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

These 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):

String benchmark: STL vs. ATL vs. custom string pool allocator
String benchmark: STL vs. ATL vs. custom string pool allocator

As you can note, the best creation times are obtained with the custom string pool allocator. This was expected, as the allocation strategy of carving string memory from pre-allocated blocks is very efficient.

On the other hand, regarding the sorting times, STL and the custom pool strings perform very similarly.

ATL’s CString, which is based on CoW (Copy on Write), shows the worst times for both creation and sorting.

Benchmark Variation: Tiny Strings

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

String benchmark with tiny strings: STL vs. ATL vs. custom string pool allocator
String benchmark with tiny strings: STL vs. ATL vs. custom string pool allocator

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

Note: Making the Sorting Comparison Uniform

I’d also like to clarify that, to make the sorting comparison more uniform, I used custom comparator functions with std::sort, invoking wcscmp for each kind of strings. In fact, spelunking in the VS 2019 STL and ATL implementation code (Thank You, Step Into Specific menu), I found that std::wstring invokes wmemcmp (file <xstring>, line #235), while ATL::CString uses wcscmp (file <cstringt.h>, line #564). Probably std::wstring uses wmemcmp because wstring instances can contain embedded NULs.

 

The Case of the Context-Menu Shell Extension That Doesn’t Get Invoked by Explorer

A developer was working on a context-menu shell extension.

He wrote all the skeleton infrastructure code, including some code to display the selected files when the shell extension gets invoked by Windows Explorer. It’s kind of the “Hello World” for context-menu shell extensions.

He happily builds his code within Visual Studio, copies the shell extension DLL to a virtual machine, registers the extension in the VM, right-clicks on a bunch of files… but nothing happens. His extension’s menu items just don’t show up in the Explorer context-menu.

What’s going wrong, he thought?

He starts thinking to all sorts of hypotheses and troubleshooting strategies.

He once again manually registers the COM DLL that implements the shell extension from the Command Prompt:

regsvr32 CoolContextMenuExtension.dll

A message box pops up, informing him that the registration has succeeded.

He tries right-clicking some files, but, once again, his extension’s menu items don’t show up.

He then checks that the extension was properly registered under the list of approved shell extensions (this was part of his shell extension infrastructure C++ code):

HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Shell Extensions\Approved

He finds the GUID of the shell extension in there, as expected.

He then checks that the extension was registered under the proper subkey in HKEY_CLASSES_ROOT. Found it there, too!

He starts wondering… what may be going so wrong?

He checks the C++ infrastructure code generated by the ATL Visual Studio wizard, including his own additions and modifications. The implementations of DllRegisterServer and DllUnregisterServer seem correct.

He also checks his own C++ code in the C++ class that implements the shell extension’s COM object. He has correctly implemented IShellExtInit::Initialize, and the three methods of IContextMenu: GetCommandString, InvokeCommand, and QueryContextMenu.

He takes a look at the class inheritance list: both IShellExtInit and IContextMenu are listed among the base classes.

The IShellExtInit and IContextMenu COM interfaces are correctly listed among the base classes.
The IShellExtInit and IContextMenu COM interfaces are correctly listed among the base classes.

He feels desperate. What’s going wrong?? He wrote several shell extensions in C++ in the past. Maybe there’s some bug in the current version of Visual Studio 2019 he is using?

Why wasn’t his context-menu shell extension getting called by Explorer?

 

I took a look at that code.

At some point, I was enlightened.

I gave a look at the COM interface map in the header file of the C++ shell extension class.

There’s a bug in the shell extension C++ object’s COM interface map.
There’s a bug in the shell extension C++ object’s COM interface map.

Wow! Can you spot the error?

Something is missing in there!

In fact, in addition to deriving the C++ shell extension class from IContextMenu, you also have to add an entry for IContextMenu in the COM map!

I quickly added the missing line:

    COM_INTERFACE_ENTRY(IContextMenu)

The COM interface map, with both the IShellExtInit and IContextMenu entries.
The COM interface map, with both the IShellExtInit and IContextMenu entries.

I rebuilt the extension, registered it, and, with great pleasure and satisfaction, the new custom items in the Explorer’s context-menu showed up! And, after selecting a bunch of files to test the extension, the message box invoked by the shell extension C++ code was correctly shown.

All right! 😊

So, what was going wrong under the hood?

Basically, since the context-menu shell extension was correctly registered under the proper key in the Windows Registry, I think that Windows Explorer was actually trying to invoke the shell extension’s methods.

In particular, I think Explorer called QueryInterface on the shell extension’s COM object, to get a pointer to IContextMenu. But, since IContextMenu was missing from the COM map, the QueryInterface code implemented by the ATL framework was unable to return the interface pointer back to Explorer. As a consequence of that, Explorer didn’t recognize the extension as a valid context-menu extension (despite the extension being correctly registered in the Windows Registry), and didn’t even call the IShellExtInit::Initialize method (that was actually available, as IShellExtInit had its own entry correctly listed in the COM map from the beginning).

The bug is in the details!

So, the moral of the story is to always check the COM map in addition to the base class list in your shell extension’s C++ class header file. The COM interfaces need to both be in the base class list and have their own entries in the COM map.

And, in addition, to me this experience has suggested that it would have been great if Visual Studio had issued at least a warning for having the IContextMenu COM interface listed among the base classes, but missing from the COM map! This would be an excellent time-and-bug-saving addition, Visual Studio IDE/Visual C++/Visual Assist X teams!

 

Where Should I Register My Context-Menu Shell Extension to Operate on All Files and Folders?

A developer was working on a context-menu shell extension. He registered the extension under:

HKEY_CLASSES_ROOT\*\shellex\ContextMenuHandlers

The developer noted that his context-menu extension was called for all files. But he also wanted his extension to be called for all directories.

If you want your context-menu shell extension to be invoked on all files and all file folders, the correct key to use for registration is HKCR\AllFileSystemObjects, not HKCR\*.

For more information, MSDN has a list of Predefined Shell Objects.

 

Simplifying Windows Registry Programming with the C++ WinReg Library

The native Windows Registry API is a C-interface API, that is low-level and kind of hard and cumbersome to use.

For example, suppose that you simply want to read a string value under a given key. You would end up writing code like this:

Sample code excerpt to read a string value from the Windows Registry using the native Windows API.
Sample code excerpt to read a string value from the Windows Registry using the native Windows API.

And this is just the part to query the destination string length. Then, you need to allocate a string object with proper size (and pay attention to proper size-in-bytes-to-size-in-wchar_ts conversion!), and after that you can finally read the actual string value into the local string object.

That’s definitely a lot of bug-prone C++ code, and this is just to query a string value!

Moreover, in modern C++ code you should prefer using nice higher-level resource manager classes with automatic resource cleanup, instead of raw HKEY handles.

Fortunately, it’s possible to hide that kind of complex and bug-prone code in a nice C++ library, that offers a much more programmer-friendly interface. This is basically what my C++ WinReg library does.

You can query a string value with just one simple line of C++ code using WinReg.
You can query a string value with just one simple line of C++ code using WinReg.

WinReg is an open-source C++ library, available on GitHub. For the sake of convenience, I packaged and distribute it as a header-only library, which is also available via the vcpkg package manager.

If you need to access the Windows Registry from your C++ code, you may want to give C++ WinReg a try.

 

Printing UTF-8 Text to the Windows Console: Sample Code

In a previous blog post, you saw that to print some UTF-8-encoded text to the Windows console, you first have to convert it to UTF-16.

In fact, calling _setmode to change stdout to _O_U8TEXT, and then trying to print UTF-8-encoded text with cout, resulted in a debug assertion failure in the VC++ runtime library. (Please take a look at the aforementioned blog post for more details.)

That blog post lacked some compilable demo code showing the solution, though. So, here you are:

// Test printing UTF-8-encoded text to the Windows console

#include "UnicodeConv.hpp"  // My Unicode conversion helpers

#include <fcntl.h>
#include <io.h>
#include <stdint.h>
#include <iostream>
#include <string>

int main()
{
    // Change stdout to Unicode UTF-16.
    //
    // Note: _O_U8TEXT doesn't seem to work, e.g.:
    // https://blogs.msmvps.com/gdicanio/2017/08/22/printing-utf-8-text-to-the-windows-console/
    //
    _setmode(_fileno(stdout), _O_U16TEXT);


    // Japanese name for Japan, encoded in UTF-8
    uint8_t utf8[] = {
        0xE6, 0x97, 0xA5, // U+65E5
        0xE6, 0x9C, 0xAC, // U+672C
        0x00
    };
    std::string japan(reinterpret_cast<const char*>(utf8));

    // Print UTF-16-encoded text
    std::wcout << Utf16FromUtf8("Japan") << L"\n\n";
    std::wcout << Utf16FromUtf8(japan)   << L'\n';
}

This is the output:

Unicode UTF-8 text converted to UTF-16 and printed out to the Windows console

All right.

Note also that I set the Windows console font to MS Gothic to be able to correctly render the Japanese kanjis.

The compilable C++ source code, including the implementation of the Utf16FromUtf8 Unicode conversion helper function, can be found here on GitHub.