BLI_probing_strategies.hh File Reference

#include <numeric>
#include <limits>
#include "BLI_sys_types.h"

Go to the source code of this file.

Classes
class	blender::LinearProbingStrategy
class	blender::QuadraticProbingStrategy
class	blender::PythonProbingStrategy< LinearSteps, PreShuffle >
class	blender::ShuffleProbingStrategy< LinearSteps, PreShuffle >

Namespaces
namespace	blender

Macros
#define	SLOT_PROBING_BEGIN(PROBING_STRATEGY, HASH, MASK, R_SLOT_INDEX)
#define	SLOT_PROBING_END()

Typedefs
using	blender::DefaultProbingStrategy = PythonProbingStrategy<>

Detailed Description

This file implements different probing strategies. Those can be used by different hash table implementations like blender::Set and blender::Map. A probing strategy produces a sequence of values based on an initial hash value.

A probing strategy has to implement the following methods:

• Constructor(uint64_t hash): Start a new probing sequence based on the given hash.
• get() const -> uint64_t: Get the current value in the sequence.
• next() -> void: Update the internal state, so that the next value can be accessed with get().
• linear_steps() -> int64_t: Returns number of linear probing steps that should be done.

Using linear probing steps between larger jumps can result in better performance, due to improved cache usage. It's a way of getting the benefits or linear probing without the clustering issues. However, more linear steps can also make things slower when the initial hash produces many collisions.

Every probing strategy has to guarantee that every possible uint64_t is returned eventually. This is necessary for correctness. If this is not the case, empty slots might not be found.

The SLOT_PROBING_BEGIN and SLOT_PROBING_END macros can be used to implement a loop that iterates over a probing sequence.

Probing strategies can be evaluated with many different criteria. Different use cases often have different optimal strategies. Examples:

• If the hash function generates a well distributed initial hash value, the constructor should be as short as possible. This is because the hash value can be used as slot index almost immediately, without too many collisions. This is also a perfect use case for linear steps.
• If the hash function is bad, it can help if the probing strategy remixes the hash value, before the first slot is accessed.
• Different next() methods can remix the hash value in different ways. Depending on which bits of the hash value contain the most information, different rehashing strategies work best.
• When the hash table is very small, having a trivial hash function and then doing linear probing might work best.

Definition in file BLI_probing_strategies.hh.

Macro Definition Documentation

SLOT_PROBING_BEGIN

#define SLOT_PROBING_BEGIN	(		PROBING_STRATEGY,
			HASH,
			MASK,
			R_SLOT_INDEX )

Value:

  PROBING_STRATEGY probing_strategy(HASH); \
  do { \
    int64_t linear_offset = 0; \
    uint64_t current_hash = probing_strategy.get(); \
    do { \
      int64_t R_SLOT_INDEX = int64_t((current_hash + uint64_t(linear_offset)) & MASK);

Both macros together form a loop that iterates over slot indices in a hash table with a power-of-two size.

You must not break out of this loop. Only return is permitted. If you don't return out of the loop, it will be an infinite loop. These loops should not be nested within the same function.

PROBING_STRATEGY: Class describing the probing strategy. HASH: The initial hash as produced by a hash function. MASK: A bit mask such that (hash & MASK) is a valid slot index. R_SLOT_INDEX: Name of the variable that will contain the slot index.

Definition at line 222 of file BLI_probing_strategies.hh.

SLOT_PROBING_END

#define SLOT_PROBING_END

(

)

Value:

    } while (++linear_offset < probing_strategy.linear_steps()); \
    probing_strategy.next(); \
  } while (true)

Definition at line 230 of file BLI_probing_strategies.hh.