/ExcaliburHash

Excalibur Hash is a high-speed hash map and hash set, ideal for performance-critical uses like video games

Primary LanguageC++MIT LicenseMIT

ExcaliburHash

Actions Status codecov Build status MIT

About

Excalibur Hash is a high-speed hash map and hash set, ideal for performance-critical uses like video games. Its design focuses on being friendly to the CPU cache, making it very efficient and fast. It uses an open addressing hash table and manages removed items with a method called tombstones.

Engineered for ease of use, Excalibur Hash, in a vast majority of cases (99%), serves as a seamless, drop-in alternative to std::unordered_map. However, it's important to note that Excalibur Hash does not guarantee stable addressing. So, if your project needs to hold direct pointers to the keys or values, Excalibur Hash might not work as you expect. This aside, its design and efficiency make it a great choice for applications where speed is crucial.

Excalibur Hash is an extremely fast hash map/hash set implementation designed to be used for performance-critical applications (like video games) It is an open addressing hash table designed to be friendly to the CPU cache, and it supports element erasing by tracking removed items using tombstones.

It is super easy to use, and (in 99% of cases) it can be used as a drop-in replacement for std::unordered_map (Excalibur Hash doesn't guarantee stable addressing, so if you need to keep raw pointers to key/value it won't work as expected)

Performance

In this section, you can see a performance comparison against a few popular hash table implementations. This comparison will show their speed and efficiency, helping you understand which hash table might work best for your project.

Unless otherwise stated, all tests were run using the following configuration

OS: Windows 11 Pro (22621.2861)
CPU: Intel i9-12900K
RAM: 128Gb 

Performance test repositoty

absl::flat_hash_map
boost::unordered_map
ska::flat_hash_map
ska::unordered_map
folly::F14ValueMap
llvm::DenseMap
Luau::DenseHashMap
tsl::robin_map
google::dense_hash_map
std::unordered_map

CtorDtor

Create and immediatly delete 300,000 hash tables on the stack, using a 'heavyweight' object as the value. This test quickly shows which hash map implementations 'cheat' by creating many key/value pairs in advance.

Performance comparison

ClearAndInsertSeq

  1. Create a hash table
  2. Clear the hash table
  3. Insert 599,999 sequential values
  4. Repeat steps 2-3 (25 times)
  5. Destroy the hash table

Performance comparison

InsertRndClearAndReInsert

  1. Create a hash table
  2. Insert 1,000,000 unique random int numbers
  3. Clear the hash table
  4. Reinsert 1,000,000 unique random int numbers into the same cleared map.
  5. Destroy the hash table
  6. Repeat steps 1-5 (10 times)

Performance comparison

InsertRndAndRemove

  1. Create a hash table
  2. Insert 1,000,000 unique random int numbers
  3. Remove all of the inserted entries one by one until the map is empty again.
  4. Destroy the hash table
  5. Repeat steps 1-4 (10 times)

Performance comparison

CtorSingleEmplaceDtor

  1. Create a hash table
  2. Insert a single key/value int the hash table
  3. Destroy the hash table
  4. Repeat steps 1-3 (300,000 times)

Performance comparison

InsertAccessWithProbability10

  1. Create a hash table
  2. Insert or increment 1,000,000 values where 10% of keys are duplicates (10% of operations will be modifications and 90% will be insertions)
  3. Destroy the hash table
  4. Repeat steps 1-3 (8 times)

Performance comparison

InsertAccessWithProbability50

  1. Create a hash table
  2. Insert or increment 1,000,000 values where 50% of keys are duplicates (50% of operations will be modifications and 50% will be insertions)
  3. Destroy the hash table
  4. Repeat steps 1-3 (8 times)

Performance comparison

SearchNonExisting

  1. Create a hash table
  2. Insert 1,000,000 unique random int numbers
  3. Search for non existent keys (10,000,000 times)
  4. Destroy the hash table

Performance comparison

SearchExisting

  1. Create a hash table
  2. Insert 1,000,000 unique random int numbers
  3. Search for existent keys (10,000,000 times)
  4. Destroy the hash table

Performance comparison

ClearAndInsertRnd

  1. Create a hash table
  2. Insert 1,000,000 unique random int numbers
  3. Destroy the hash table
  4. Repeat steps 1-3 (25 times)

Performance comparison

Summary

Below, you can find all the tests combined into a single table using normalized timings where 1.0 is the fastest implementation, 2.0 is twice as slow as the fastest configuration, and so on.

OS: Windows 11 Pro (22621.2861)
CPU: Intel i9-12900K
RAM: 128Gb 

Intel Summary

OS: Windows 11 Home (22631.2861)
CPU: AMD Ryzen5 2600
RAM: 16Gb 

AMD Summary

Usage

Here is the simplest usage example.

#include "ExcaliburHash.h"

int main()
{
  // use hash table as a hash map (key/value)
  Excalibur::HashTable<int, int> hashMap;
  hashMap.emplace(13, 6);

  // use hash table as a hash set (key only)
  Excalibur::HashTable<int, nullptr_t> hashSet;
  hashSet.emplace(13);

  return 0;
}

More detailed examples can be found in the unit tests folder.