Attempting to beat the standard.
Introduction:
This blogpost will cover my process of trying to create an associative container class in C++ that would beat the standard’s std::map<K, V> for an in-house C++ game engine.
First, let’s go over some basics. The C++17 standard has two ready made associative containers: the std::map<K, V> and std::unordered_map<K, V, S>. Std::map<K, V> is more suitable to traversal whereas std::unordered_map<K, V, S> is more suitable for single element access.
For the sake of simplicity, from now on I will be referring to all of these containers as well as mine as “map”s.
Design choices:
When implementing the class, I had the choice between a self balancing BST and a hash table. Since I wanted quick access to random elements rather than quick traversal of the container, I’ve settled on a hash table using the xxHash library.
Overview of the class:
A pre-existing allocator class available, I’ve used a linear allocator variation for this container.
Designing the container for large quantities of data, I’ve arranged the pairs of keys and values on the heap following a traditional Array of Structures approach (SoA).
It is noteworthy that while I did not investigate this path further, rearranging the data into an Array of Structures of Arrays may yield some better performance in combination with some SIMD code.
The pairs are stored on the heap via the LinearAllocator class that is initialized once at runtime.
The FixedMap<K, V, S> contains two pointers, one for the starting address of the array of pairs and one for the end address.
It also contains a reference to the LinearAllocator used by the instance as well as a size_t to keep track of the effective count of pairs initialized, the rest of the memory waiting to be used.
While I could have used a third pointer in place of the size_t to indicate the position of the last initialized pair, I’ve chosen (albeit without testing first) to use a size_t because both a pointer and a size_t take up 8 bytes, but to retireve the size using pointers would involve an unsigned integer substraction every time the size is required, whereas with a size_t, only the retireval of the variable is necessary each time without any extra operations and the variable is only incremented at insertion of a new element.
The rest of the class is self-explanatory with the exception of the Insert() and operator[] functions I will be going over below.
Overview of the benchmark:
The goal of this class was to try to optimize the performance of random access to the map without sacrificing performance on creation, destruction or insertion of elements in the map.
Therefore, I’ve devised two simple benchmarks to quantify the performance of all maps:
- The InitFillOutAndClear benchmark that measures the time required to get the maps into usable condition and for it’s destruction. This is the performance I didn’t want to impact negatively.
- The Access benchmark that measures the time required to retrieve a random element from the map. This is what I wanted to optimize.
The specs:
- CPU: Intel Core i7-4770 @ 3.40GHz
- Architecture: x86_64
- OS: Ubuntu 19.10
- Compiler: clang++-9
const size_t SIZE = 128; // max nbr of distinct chars
using Key = unsigned char; using Value = unsigned char;
void BM_StdMap_InitFillOutAndClear(benchmark::State& s) { for (auto _ : s) { StdMapType map = StdMap_Init(); StdMap_FillOut(map); StdMap_Clear(map); } }
void BM_FixedMap_InitFillOutAndClear(benchmark::State& s) { for (auto _ : s) { FixedMapType map = FixedMap_Init(); FixedMap_FillOut(map); FixedMap_Clear(map); } }
void BM_StdMap_Access(benchmark::State& s) { StdMapType map = StdMap_Init(); std::vector<Key> keys(SIZE); for (auto& key : keys) { key = GetNextKey(); map.insert({key, GetNextKey()}); } for (auto _ : s) { for (auto key : keys) { benchmark::DoNotOptimize(StdMap_Access(map, key)); } } }
void BM_FixedMap_Access(benchmark::State& s) { FixedMapType map = FixedMap_Init(); std::vector<Key> keys(SIZE); for (auto& key : keys) { key = GetNextKey(); map.Insert({key, GetNextKey()}); } for (auto _ : s) { for (auto key : keys) { benchmark::DoNotOptimize(FixedMap_Access(map, key)); } } }
BENCHMARK(BM_StdMap_InitFillOutAndClear);
BENCHMARK(BM_FixedMap_InitFillOutAndClear);
BENCHMARK(BM_StdMap_Access);
BENCHMARK(BM_FixedMap_Access);
BENCHMARK_MAIN();
For the sake of simplicity, I’ve used a simple char to char map. While I was initially planning to compare the performance of my custom container to std::map<K, V> only, out of interest, I’ve decided to include std::unordered_map<K, V, S> as well.
This proved to be interesting as it highlights the forces and weaknesses of these two standard containers.
Initial results:
Run on (8 X 3900 MHz CPU s)
CPU Caches:
L1 Data 32K (x4)
L1 Instruction 32K (x4)
L2 Unified 256K (x4)
L3 Unified 8192K (x1)
Load Average: 0.59, 0.57, 0.70
---------------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------------
BM_StdMap_InitFillOutAndClear 6012 ns 6004 ns 117269
BM_StdUnorderedMap_InitFillOutAndClear 5252 ns 5241 ns 132946
BM_FixedMap_InitFillOutAndClear 788 ns 784 ns 890144
BM_StdMap_Access 2043 ns 2033 ns 346052
BM_StdUnorderedMap_Access 379 ns 378 ns 1851365
BM_FixedMap_Access 4299 ns 4283 ns 162205
First attempts:
Wanting to put to use my newly acquired knowledge C++ syntax, I’ve firstly started to mess around with all the keywords I knew of.
I’ve tried changing arguments, methods, return values, local variables to const, to pointers, to const pointers, to references, to const references and back again, I’ve tried inlining code but none of it yielded any significant performance effects whatsoever.
The fact of the matter is simply that a compiler is able to detect and optimize code without the need for the programmer to be overly verbose about every line of code they write.
What made a difference: Size of the hash
Run on (8 X 3900 MHz CPU s)
CPU Caches:
L1 Data 32K (x4)
L1 Instruction 32K (x4)
L2 Unified 256K (x4)
L3 Unified 8192K (x1)
Load Average: 1.00, 1.00, 0.87
---------------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------------
BM_StdMap_InitFillOutAndClear 5897 ns 5897 ns 119377
BM_StdUnorderedMap_InitFillOutAndClear 5162 ns 5162 ns 137391
BM_FixedMap_InitFillOutAndClear 159 ns 159 ns 4392519
BM_StdMap_Access 2010 ns 2010 ns 352154
BM_StdUnorderedMap_Access 374 ns 374 ns 1858041
BM_FixedMap_Access 3825 ns 3825 ns 181454
A simple but valid optimization has been to simply reduce the size of the hashed keys I use to associate keys to values.
Xxhash supports 32 and 64 bit hashes that are simply unsigned longs and unsigned long longs respectively behind the hood.
While I started with 64 bit hashes, this would have allowed my maps to be 2^64 – 1 in size, or 18’446’744’073’709’551’615 elements long.
This would never be necessary as even the higher end consumer PC currently only boasts around 32 GB of RAM, so even filling out the whole RAM with char to char pairs would only use up under 1/500’000’000th of the possible unique hashes.
For this reason, I’ve switched to 32 bit hashes, which meant an increase of data being able to be transferred to the CPU’s cache each RAM access.
Realistically, a hash size of 16 bits would have been more suited as that number would allow 65’535 as the maximal length of a map, which is more than enough for anything a game engine might use maps for, however xxhash not supporting that size, I’ve settled on 32 bits.
What made a difference: Binary search
Run on (8 X 3900 MHz CPU s)
CPU Caches:
L1 Data 32K (x4)
L1 Instruction 32K (x4)
L2 Unified 256K (x4)
L3 Unified 8192K (x1)
Load Average: 0.23, 0.64, 0.88
---------------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------------
BM_StdMap_InitFillOutAndClear 5783 ns 5782 ns 111222
BM_StdUnorderedMap_InitFillOutAndClear 4983 ns 4983 ns 140539
BM_FixedMap_InitFillOutAndClear 146 ns 146 ns 4808496
BM_StdMap_Access 1928 ns 1928 ns 358820
BM_StdUnorderedMap_Access 362 ns 362 ns 1932198
BM_FixedMap_Access 825 ns 825 ns 845196
The binary search is a simple search algorithm that relies on the assumption that an array of elements is ordered in some way. In my case, the key values pairs of my container were stored in ascending order of hashed keys.
This algorithm ensures the retrieval of a value in O(log(n)) time.
The algorithm starts off in the middle of the array to search, and compares the current value (hashed key in my case) with the value we’re looking for. Since all elements are ordered, in my case in ascending order, we know that if the seeked value is smaller than the current one, it means that the value we’re looking for must be located to our left in memory (and vice-versa if the value seeked is greater than the current one).
Therefore, we simply disregard all values to our right, and move to the middle of the remaining range of elements. Rince and repeat until we find the value we’re looking for.
This exceedingly simple algorithm has brought the lookup time of the operator[] from ~3’750[ns] all the way down to 800[ns], effectively beating std::map<K,V> lookup times, although still two times slower than the std::unordered_map<K,V,S>.
The implementation of this search algorithm did come with a price however: all the pairs had to be arranged in an ascending manner by key hash.
To do so, I’ve firstly tried the naive approach of sorting the whole array of pairs every time a new element is inserted into it. The results were bad, as expected:
Run on (8 X 3900 MHz CPU s) CPU Caches: L1 Data 32K (x4) L1 Instruction 32K (x4) L2 Unified 256K (x4) L3 Unified 8192K (x1) Load Average: 1.80, 1.39, 1.49 --------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------- BM_StdMap_InitFillOutAndClear 6083 ns 6076 ns 104335 BM_StdUnorderedMap_InitFillOutAndClear 5378 ns 5372 ns 132287 BM_FixedMap_InitFillOutAndClear 70947 ns 70886 ns 9959 BM_StdMap_Access 2024 ns 2022 ns 348573 BM_StdUnorderedMap_Access 375 ns 375 ns 1878953 BM_FixedMap_Access 851 ns 850 ns 832079
Calling the sorting function manually after inserting all the new elements subsequently does avoid the performance hit, however this requires the programmer to explicitly call the sorting method upon every insertion of a new element, else the lookup would fail.
To get around this extra step, I has to modify the Insert() function. Where as before it would simply add the new element at the end of the array of pairs and then require a call to a sorting function, it was changed to traverse the ordered array until a matching spot for the new element was found.
For each subsequent element in the pairs array, the value of the current hashed key is compared to the one we’re trying to insert, and if the value of the key being inserted is bigger than the current one, all the remaining pairs are moved over, and the new pair is inserted in the freed up space.
This did increase insertion time drastically, however it still remained better than the standard implementation of both std::map<K,V> and std::unordered_map<K,V,S>.
Run on (8 X 3900 MHz CPU s) CPU Caches: L1 Data 32K (x4) L1 Instruction 32K (x4) L2 Unified 256K (x4) L3 Unified 8192K (x1) Load Average: 0.62, 0.93, 0.99 --------------------------------------------------------------------------------- Benchmark Time CPU Iterations --------------------------------------------------------------------------------- BM_StdMap_InitFillOutAndClear 5978 ns 5978 ns 118550 BM_StdUnorderedMap_InitFillOutAndClear 5223 ns 5223 ns 134915 BM_FixedMap_InitFillOutAndClear 3113 ns 3113 ns 223871 BM_StdMap_Access 2060 ns 2060 ns 348975 BM_StdUnorderedMap_Access 387 ns 387 ns 1804813 BM_FixedMap_Access 810 ns 810 ns 865248
Conclusion:
I couldn’t beat std::unordered_map<K, V, S> but did outperform std::map<K, V>. Further improvements could have been done by arranging the data into an Array of Structures of Arrays (AoSoA) and utilizing intrensics to speed up lookup and overall take inspiration from std::unordered_map<K,V,S> implementation to see what could be done to out-perform these.
Trying to beat the standard as a junior programmer is very interesting and teaches you a lot but it is hard. The programmers behind the standard’s implementations are very skilled and knowledgeable and for most cases, it is enough to use correctly the libraries provided rather than trying to re-invent the whole thing.
Optimization only makes sense if there is an obvious mismatch between the functionalities provided and the actual need. If there isn’t, a proper usage of existing libraries would most probably out-perform your own code.
This experience has also made obvious the perspicacity of a compiler, especially one such as clang. For the majority of cases you can throw at it, it is able to spot and optimize code without the need for the programmer to be overly verbose.
Finally, the usefulness of writing a blogpost has surprised me: in writing our own process down to explain it to someone else, not only are we gaining a deeper insight in the subject we’re trying to explain, but it also is a great way to spot flaws in a reasoning that might have seemed sound in a non written form.