2021/heterogeneous-access-cpp20/

[utterances-bot]

C++20: Heterogeneous Lookup in (Un)ordered Containers - C++ Stories

Would you like to gain 20…35 or even 50% speed improvements when searching in associative containers? In this blog post, we’ll explore a technique called “heterogenous access” that offers such impressive speedups. We’ll explore ordered containers, and the support for unordered collections added recently in C++20. Recap on heterogeneous lookup in ordered containers Let’s bring the example and have a look at how this feature works for ordered containers.

https://www.cppstories.com/2021/heterogeneous-access-cpp20/

[2kaud]

Nice!

[Scutum13]

If your are looking for literals you can use string literals instead of char arrays:

std::cout << intMap.contains("Hello Super Long String"s) << '\n';

Since C++17 string literals are even constexpr, so there is no allocation at runtime anymore.

[Scutum13]

correct: since C++20.

[cptFracassa]

@Scutum13: My understanding is that cannot use constexpr strings outside constexpr functions, even in c++20, so what you suggest will not work.

[2kaud]

@cptFracassa is correct for standard C++20. Currently allocated memory (ie for std::string) within a constexpr context cannot be referenced outside of that context. So within a constexpr function, memory can be allocated, used and de-allocated but cannot be referenced outside. As the memory allocated for std::string is required to be used outside of its context it is currently not allowed so constexpr std::string (and other containers) cannot be defined as constexpr.

There could be a case made that if std::string uses SBO then providing the size of the stored data doesn't exceed the size of the SBO, then in this special case std::string could be made constexpr.

It would be possible to remove this SBO restriction for constexpr string and for other containers by storing the result in the .exe . As constexpr means read-only and already c-style const strings can be stored in read-only (ie in the .exe), this could be done.

[jsribar]

Just for the record: a map with const char* as a key:

std::map<const char*, int, decltype([](const char* s1, const char* s2) { return strcmp(s1, s2) < 0; })>

triggers only 3 allocations during map initialization (compared to 9 allocations for intMap and trIntMap) and no allocation on find method invocation.

Also, benchmarks show that performance is comparable to unordered map. Bellow is the benchmark output on Visual Studio 2022. Normal Map with const char* corresponds to the map defined above, Unord Map with const char* corresponds to the equivalent unordered map defined as:

std::unordered_map<const char*, size_t, decltype([](const char* s) { return std::hash<std::string_view>{}(s); }), decltype([](const char* s1, const char* s2) { return strcmp(s1, s2) == 0; })>

Short String Benchmark
======================
          Normal Map with string timing:  628ms
           Normal Map with char* timing:  780ms
     Normal Map with const char* timing:  331ms
            Trans Map with char* timing:  903ms
      Trans Map with string_view timing:  598ms
    Normal Unord Map with string timing:  176ms
     Normal Unord Map with char* timing:  428ms
      Unord Map with const char* timing:  207ms
      Trans Unord Map with char* timing:  248ms
Trans Unord Map with string_view timing:  176ms

Long String Benchmark
=====================
          Normal Map with string timing:  618ms
           Normal Map with char* timing: 2331ms
     Normal Map with const char* timing:  705ms
            Trans Map with char* timing: 2192ms
      Trans Map with string_view timing:  621ms
    Normal Unord Map with string timing:  709ms
     Normal Unord Map with char* timing: 2162ms
      Unord Map with const char* timing: 1361ms
      Trans Unord Map with char* timing: 1427ms
Trans Unord Map with string_view timing:  739ms

[fenbf]

thanks for the benchmark results @jsribar

[kobi-ca]

same comment on the missing space here: 35% performance gain for long text (dynamic memory allocation in std::stringtemporary). between string and temporary