[External] Adding `ankerl` `unordered_dense`

[loumalouomega]

📝 Description

Introduction

Adding ankerl unordered_dense, which provides top performance hashsed iterators: https://martin.ankerl.com/2022/08/27/hashmap-bench-01/. MIT license and header only.

Initial testing during efforts to modernize data_value_container, at the end current brute force solution for small number of variables is faster, but I found thatankerl` in my tests was the faster solution.

The using them to replace our current containers (not used anywhere).

Key Features

1. Performance:

   • Optimized for fast lookups and insertions.
   • Minimizes memory usage by densely packing the data.

2. Robin Hood Hashing:

   • Ensures even distribution of elements, reducing clustering.
   • Backward shift deletion minimizes gaps in the table when elements are removed.

3. Template Customization:

   • Supports custom hash functions, key equality checks, allocators, and bucket types.
   • Provides both map (key-value pairs) and set (keys only) interfaces.

4. Hashing Algorithm:

   • Based on wyhash, a fast and high-quality hashing algorithm.
   • Provides built-in and extensible hash function templates.

5. API Compatibility:

   • Follows the conventions of the standard library's std::unordered_map and std::unordered_set.
   • Offers additional non-standard features like extract for moving data and replace for bulk updates.

6. Exception Safety:

   • Designed with robust exception handling in mind.
   • Ensures no memory leaks or corruption even during exceptions.

7. Modular and Extensible:

   • Offers segmentation options for memory management.
   • Integrates with polymorphic memory resources (PMR) for custom allocation strategies.

8. C++17 and Higher:

   • Requires C++17 or newer due to the use of features like std::optional, std::tuple, and advanced template metaprogramming.

Main Components

1. Hashing:

   • Customizable via the hash template, supporting standard types, strings, and custom objects.
   • Uses a combination of mixing and bit manipulation for uniform distribution.

2. Buckets:

   • The Bucket structure stores metadata (distance and fingerprint) and an index into the value container.

3. Data Storage:

   • Utilizes a segmented_vector or std::vector to store data contiguously.
   • The segmentation option (segmented_map or segmented_set) improves memory management for large datasets.

4. Load Factor:

   • Maintains a default maximum load factor of 0.8, adjustable by the user.
   • Automatically grows the table to maintain performance.

5. Transparent Lookup:

   • Supports heterogeneous lookups (e.g., std::string_view for std::string keys).

6. Iterators:

   • Provides standard iterators for traversal.
   • Iterator invalidation rules are similar to std::unordered_map.

🆕 Changelog

• Adding ankerl unordered_dense
• Using in Kratos containers

[loumalouomega]

* [`tsl::robin_map`](https://github.com/Tessil/robin-map)

This one is super slow at least for moderate sizes in my own tests.

[loumalouomega]

If you are not familiar with google's benchmark framework, I can shoot you an example with std::unordered_map and you can build on top of that for the other implementations.

I would like to have something standarized in Kratos instead of just hand made each time. It is not possible to reuse our GTest infrastructure?

[matekelemen]

* [`tsl::robin_map`](https://github.com/Tessil/robin-map)

This one is super slow at least for moderate sizes in my own tests.

Maybe, but that just highlights the dangers of taking devs benchmarks of their own libs at face value. The author of tsl::robin_map also did a benchmark that painted his own implementation in a rather flattering light.

[matekelemen]

If you are not familiar with google's benchmark framework, I can shoot you an example with std::unordered_map and you can build on top of that for the other implementations.

I would like to have something standarized in Kratos instead of just hand made each time. It is not possible to reuse our GTest infrastructure?

I'm all for something standardized, but GTest is definitely not a benchmarking library. Google's framework is pretty simple and very popular, but I'm open to other suggestions.

[loumalouomega]

* [`tsl::robin_map`](https://github.com/Tessil/robin-map)

This one is super slow at least for moderate sizes in my own tests.

Maybe, but that just highlights the dangers of taking devs benchmarks of their own libs at face value. The author of tsl::robin_map also did a benchmark that painted his own implementation in a rather flattering light.

Yes, in fcat this was the first one I tried and it was the slowest one of all I tried.

[loumalouomega]

If you are not familiar with google's benchmark framework, I can shoot you an example with std::unordered_map and you can build on top of that for the other implementations.

I would like to have something standarized in Kratos instead of just hand made each time. It is not possible to reuse our GTest infrastructure?

I'm all for something standardized, but GTest is definitely not a benchmarking library. Google's framework is pretty simple and very popular, but I'm open to other suggestions.

Maybe we can at least add a cmake loop to compile the benchmarks ...

[matekelemen]

Maybe we can at least add a cmake loop to compile the benchmarks ...

I'd put the benchmarks in a different repo, similar to how we deal with examples.

[loumalouomega]

Maybe we can at least add a cmake loop to compile the benchmarks ...

I'd put the benchmarks in a different repo, similar to how we deal with examples.

Usually code of benchmakes is not very different from tests. Examples are huge in comparison.

[RiccardoRossi]

Tonadd my two cents to Mate'@ comments:

• memory occupation particularly for the dqtabase is of paramount importance. One simple way to improve efficiency is to decrease the loadfactor, but we cannot affor it in the database
• portability
• maintenance: is there a team behind the lib?