Click here to Skip to main content
15,883,647 members
Articles / Programming Languages / C++20
Tip/Trick

C++14/20 Heterogeneous Lookup Benchmark

Rate me:
Please Sign up or sign in to vote.
4.93/5 (8 votes)
18 Jan 2021CPOL3 min read 10K   62   4   6
Heterogeneous lookup with char* and string_view without temporary string instantiation in ordered and unordered containers

  

Introduction

C++14 introduced ordered transparency lookup which enables const char* and string_view lookup without string instantiation on map/set objects. C++20 introduced unordered transparency lookup that allows to do the same thing with unordered_map/unordered_set. We are officially in 2020 but as of writing time, the C++20 Standard is yet to be ratified by C++ committee. However, Visual C++ team has already implemented some of C++20 library features. Thanks, Billy O'Neal and VC++ team! In order to enable the latest C++ standard in VC++ to compile this benchmark, go to VC++ general property page and choose std:c++latest from the C++ Language Standard dropdown as shown below:

VC++ general property page

To help you understand the sv suffix in the later code, it has to be noted whenever sv is appended to a string literal, we are telling the compiler to create a string_view from literal. What is a string_view? string_view is a non-owning view to a not-null-terminating character buffer with its length. Care must be taken with accessing string_view that the original std::string or character buffer, it pointed to, must be still in scope.

C++
"xxx" // char string literal
"xxx"s // create std::string from literal
"xxx"sv // create std::string_view from literal

In a normal map::find(), a const char* string literal actually creates a temporary string while string_view results in a compilation error.

C++
std::map<std::string, size_t> mapNormal;
mapNormal.find("Susan");   // memory alloc
mapNormal.find("Susan"sv); // compile error with string_view

Let's see a transparent map. Transparent lookup name makes people instantly relate to opacity which had nothing to do at all with this feature. Geez, talk about bad naming! A transparent map is created by giving it a 3rd templated predicate of std::less<> which is otherwise std::less<std::string> when not specified. Now, no string instantiation is required when const char* and string_view is used. If you want to delve deeper as to how this magic works, read Bartlomiej Filipek's excellent blog post for more information.

C++
std::map<std::string, size_t, std::less<> > mapTrans;
mapTrans.find("Terry");   // no memory alloc but strlen() is used
mapTrans.find("Terry"sv); // no memory alloc

As with a normal unordered_map::find(), const char* string literal creates a temporary string while string_view results in a compilation error.

C++
std::unordered_map<std::string, size_t> unordmapNormal;
unordmapNormal.find("Susan");   // memory alloc
unordmapNormal.find("Susan"sv); // compile error with string_view

To create a transparent unordered_map, a hash functor with a transparent_key_equal type and () operator overloads for const char* and string_view has to be defined and passed to unordered_map as 3rd template type.

C++
struct MyEqual : public std::equal_to<>
{
	using is_transparent = void;
};

struct string_hash {
	using is_transparent = void;
	using key_equal = std::equal_to<>;  // Pred to use
    using hash_type = std::hash<std::string_view>;  // just a helper local type
    size_t operator()(std::string_view txt) const { return hash_type{}(txt); }
    size_t operator()(const std::string& txt) const { return hash_type{}(txt); }
    size_t operator()(const char* txt) const { return hash_type{}(txt); }
};

std::unordered_map<std::string, size_t, string_hash, MyEqual > unordmapTrans;
unordmapTrans.find("Terry");   // no memory alloc but strlen() is used
unordmapTrans.find("Terry"sv); // no memory alloc

The benchmark code is shown below. Ignore the total and grandtotal variables. Their only purpose is to prevent the compiler from optimizing away the for loops since they are not doing any useful work. Initially, I was using the associative container's [] operator for search but it turns out that [] does not accept string_view, so find() is used.

C++
void benchmark(
    const std::vector<std::string>& vec_shortstr, 
    const std::vector<std::string_view>& vec_shortstrview, 
    const std::map<std::string, size_t>& mapNormal,
    const std::map<std::string, size_t, std::less<> >& mapTrans,
    const std::unordered_map<std::string, size_t>& unordmapNormal,
    const std::unordered_map<std::string, size_t, string_hash, MyEqual >& unordmapTrans)
{
    size_t grandtotal = 0;

    size_t total = 0;

    timer stopwatch;
    total = 0;
    stopwatch.start("Normal Map with string");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = mapNormal.find(vec_shortstr[j]);
            if(it!=mapNormal.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();

    total = 0;
    stopwatch.start("Normal Map with char*");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = mapNormal.find(vec_shortstr[j].c_str());
            if (it != mapNormal.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();

    total = 0;
    stopwatch.start("Trans Map with char*");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = mapTrans.find(vec_shortstr[j].c_str());
            if (it != mapTrans.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();
    
    total = 0;
    stopwatch.start("Trans Map with string_view");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstrview.size(); ++j)
        {
            const auto& it = mapTrans.find(vec_shortstrview[j]);
            if (it != mapTrans.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();
    
    total = 0;
    stopwatch.start("Normal Unord Map with string");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = unordmapNormal.find(vec_shortstr[j]);
            if (it != unordmapNormal.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();

    total = 0;
    stopwatch.start("Normal Unord Map with char*");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = unordmapNormal.find(vec_shortstr[j].c_str());
            if (it != unordmapNormal.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();

    total = 0;
    stopwatch.start("Trans Unord Map with char*");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstr.size(); ++j)
        {
            const auto& it = unordmapTrans.find(vec_shortstr[j].c_str());
            if (it != unordmapTrans.cend())
                total += it->second;
        }
    }
    grandtotal += total;
    stopwatch.stop();

    total = 0;
    stopwatch.start("Trans Unord Map with string_view");
    for (size_t i = 0; i < MAX_LOOP; ++i)
    {
        for (size_t j = 0; j < vec_shortstrview.size(); ++j)
        {
            const auto& it = unordmapTrans.find(vec_shortstrview[j]);
            if (it != unordmapTrans.cend())
                total += it->second;
        }
    }
    grandtotal += total;

    stopwatch.stop();

    std::cout << "grandtotal:" << grandtotal << " <--- Ignore this\n" << std::endl;
}

First, we run the benchmark with short text. The benchmark is built in Release x64 mode with /Ox, the highest compiler optimization. Short text should be faster since std::string is implemented with Short String Optimization(SSO), meaning std::string has a short buffer that is used whenever the text is short enough to fit in that buffer, instead of allocating on the heap. string_view has about the same performance as std::string that looks about right while const char* has worse performance in transparent map than normal map. It should be a bug which I shall report to Microsoft.

Short String Benchmark
======================
          Normal Map with string timing:  652ms
           Normal Map with char* timing:  723ms
            Trans Map with char* timing:  829ms
      Trans Map with string_view timing:  608ms

This is the short text benchmark result with unordered_map. The result is as expected.

    Normal Unord Map with string timing:  206ms
     Normal Unord Map with char* timing:  506ms
      Trans Unord Map with char* timing:  296ms
Trans Unord Map with string_view timing:  211ms

The long text benchmark result with map. The long text is ensured to be a minimum of 30 chars in order to exceed the short buffer to force memory allocation.

Long String Benchmark
=====================
          Normal Map with string timing:  589ms
           Normal Map with char* timing: 2292ms
            Trans Map with char* timing: 2442ms
      Trans Map with string_view timing:  602ms

The long text benchmark result with unordered_map.

    Normal Unord Map with string timing:  738ms
     Normal Unord Map with char* timing: 2382ms
      Trans Unord Map with char* timing: 1506ms
Trans Unord Map with string_view timing:  762ms

What about GCC and Clang? I do not have access to the latest C++ compilers on Linux. You are welcome to build and run the benchmark with GCC and Clang.

If you have been reading my articles over the years, you will notice they are usually performance-focused. In the new decade, I am going to shift my focus to code safety and developer life. If you are interested in these two topics, stay tuned!

References

History

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer (Senior)
Singapore Singapore
Shao Voon is from Singapore. His interest lies primarily in computer graphics, software optimization, concurrency, security, and Agile methodologies.

In recent years, he shifted focus to software safety research. His hobby is writing a free C++ DirectX photo slideshow application which can be viewed here.

Comments and Discussions

 
QuestionCompilation error on latest MSVC Pin
IndustrialMan18-Jan-21 4:03
IndustrialMan18-Jan-21 4:03 
AnswerRe: Compilation error on latest MSVC Pin
Shao Voon Wong18-Jan-21 14:13
mvaShao Voon Wong18-Jan-21 14:13 
QuestionSlight standard change Pin
liukidar20-Apr-20 8:30
liukidar20-Apr-20 8:30 
AnswerRe: Slight standard change Pin
Shao Voon Wong18-Jan-21 18:17
mvaShao Voon Wong18-Jan-21 18:17 
QuestionPerformance of different compilers Pin
E. Papulovskiy9-Jan-20 21:21
E. Papulovskiy9-Jan-20 21:21 
If you are so performance-focused, why do you use MSVC?

Being without a comparison of different compilers, this article seems incomplete. I'm curious if ICC will give better performance.
QuestionInteresting article Pin
Midnight4892-Jan-20 6:47
Midnight4892-Jan-20 6:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.