Blender
V3.3
|
#include <unordered_set>
#include "BLI_array.hh"
#include "BLI_hash.hh"
#include "BLI_hash_tables.hh"
#include "BLI_probing_strategies.hh"
#include "BLI_set_slots.hh"
Go to the source code of this file.
Namespaces | |
blender | |
Macros | |
#define | LOAD_FACTOR 1, 2 |
#define | SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) |
#define | SET_SLOT_PROBING_END() SLOT_PROBING_END() |
Typedefs | |
template<typename Key , int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(Key)), typename ProbingStrategy = DefaultProbingStrategy, typename Hash = DefaultHash<Key>, typename IsEqual = DefaultEquality, typename Slot = typename DefaultSetSlot<Key>::type> | |
using | blender::RawSet = Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, RawAllocator > |
A blender::Set<Key>
is an unordered container for unique elements of type Key
. It is designed to be a more convenient and efficient replacement for std::unordered_set
. All core operations (add, remove and contains) can be done in O(1) amortized expected time.
In most cases, your default choice for a hash set in Blender should be blender::Set
.
blender::Set is implemented using open addressing in a slot array with a power-of-two size. Every slot is in one of three states: empty, occupied or removed. If a slot is occupied, it contains an instance of the key type.
Bench-marking and comparing hash tables is hard, because many factors influence the result. The performance of a hash table depends on the combination of the hash function, probing strategy, max load factor, key type, slot type and the data distribution. This implementation is designed to be relatively fast by default in all cases. However, it also offers many customization points that allow it to be optimized for a specific use case.
A rudimentary benchmark can be found in BLI_set_test.cc. The results of that benchmark are there as well. The numbers show that in this specific case blender::Set outperforms std::unordered_set consistently by a good amount.
Some noteworthy information:
add_new
and remove_contained
should be used instead of add
and remove
whenever appropriate. Assumptions and intention are described better this way._as
. The template parameters Hash and #IsEqual have to support the other key type. This can greatly improve performance when the set contains strings.print_stats
method can be used to get information about the distribution of keys and memory usage of the set.Possible Improvements:
Definition in file BLI_set.hh.
#define LOAD_FACTOR 1, 2 |
The max load factor is 1/2 = 50% by default.
Definition at line 145 of file BLI_set.hh.
Iterate over a slot index sequence for a given hash.
Definition at line 158 of file BLI_set.hh.
#define SET_SLOT_PROBING_END | ( | ) | SLOT_PROBING_END() |
Definition at line 161 of file BLI_set.hh.