cache implements a cache with properties similar to a cuckoo-set More...

#include <cuckoocache.h>

Collaboration diagram for CuckooCache::cache< Element, Hash >:

Public Member Functions
	cache ()
	You must always construct a cache with some elements via a subsequent call to setup or setup_bytes, otherwise operations may segfault. More...

uint32_t	setup (uint32_t new_size)
	setup initializes the container to store no more than new_size elements. More...

uint32_t	setup_bytes (size_t bytes)
	setup_bytes is a convenience function which accounts for internal memory usage when deciding how many elements to store. More...

void	insert (Element e)
	insert loops at most depth_limit times trying to insert a hash at various locations in the table via a variant of the Cuckoo Algorithm with eight hash locations. More...

bool	contains (const Element &e, const bool erase) const

Private Member Functions
std::array< uint32_t, 8 >	compute_hashes (const Element &e) const
	compute_hashes is convenience for not having to write out this expression everywhere we use the hash values of an Element. More...

constexpr uint32_t	invalid () const

void	allow_erase (uint32_t n) const
	allow_erase marks the element at index n as discardable. More...

void	please_keep (uint32_t n) const
	please_keep marks the element at index n as an entry that should be kept. More...

void	epoch_check ()
	epoch_check handles the changing of epochs for elements stored in the cache. More...

Private Attributes
std::vector< Element >	table
	table stores all the elements More...

uint32_t	size
	size stores the total available slots in the hash table More...

bit_packed_atomic_flags	collection_flags
	The bit_packed_atomic_flags array is marked mutable because we want garbage collection to be allowed to occur from const methods. More...

std::vector< bool >	epoch_flags
	epoch_flags tracks how recently an element was inserted into the cache. More...

uint32_t	epoch_heuristic_counter
	epoch_heuristic_counter is used to determine when an epoch might be aged & an expensive scan should be done. More...

uint32_t	epoch_size
	epoch_size is set to be the number of elements supposed to be in a epoch. More...

uint8_t	depth_limit
	depth_limit determines how many elements insert should try to replace. More...

const Hash	hash_function
	hash_function is a const instance of the hash function. More...

Detailed Description

template<typename Element, typename Hash>
class CuckooCache::cache< Element, Hash >

cache implements a cache with properties similar to a cuckoo-set

The cache is able to hold up to (~(uint32_t)0) - 1 elements.

Read Operations:

contains(*, false)

Read+Erase Operations:

contains(*, true)

Erase Operations:

allow_erase()

Write Operations:

Synchronization Free Operations:

User Must Guarantee:

1) Write Requires synchronized access (e.g., a lock) 2) Read Requires no concurrent Write, synchronized with the last insert. 3) Erase requires no concurrent Write, synchronized with last insert. 4) An Erase caller must release all memory before allowing a new Writer.

Note on function names:

The name "allow_erase" is used because the real discard happens later.
The name "please_keep" is used because elements may be erased anyways on insert.

Template Parameters

Element	should be a movable and copyable type
Hash	should be a function/callable which takes a template parameter hash_select and an Element and extracts a hash from it. Should return high-entropy uint32_t hashes for `Hash h; h<0>(e) ... h<7>(e)`.

Definition at line 160 of file cuckoocache.h.

Constructor & Destructor Documentation

◆ cache()

template<typename Element, typename Hash>

CuckooCache::cache< Element, Hash >::cache ( )

inline

You must always construct a cache with some elements via a subsequent call to setup or setup_bytes, otherwise operations may segfault.

Definition at line 327 of file cuckoocache.h.

Member Function Documentation

◆ allow_erase()

template<typename Element, typename Hash>

void CuckooCache::cache< Element, Hash >::allow_erase ( uint32_t n ) const

inlineprivate

allow_erase marks the element at index n as discardable.

Threadsafe without any concurrent insert.

Parameters

n	the index to allow erasure of

Definition at line 266 of file cuckoocache.h.

References CuckooCache::bit_packed_atomic_flags::bit_set(), and CuckooCache::cache< Element, Hash >::collection_flags.

Referenced by CuckooCache::cache< Element, Hash >::contains(), and CuckooCache::cache< Element, Hash >::epoch_check().

◆ compute_hashes()

template<typename Element, typename Hash>

std::array<uint32_t, 8> CuckooCache::cache< Element, Hash >::compute_hashes ( const Element & e ) const

inlineprivate

compute_hashes is convenience for not having to write out this expression everywhere we use the hash values of an Element.

We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a manner which preserves as much of the hash's uniformity as possible. Ideally this would be done by bitmasking but the size is usually not a power of two.

The naive approach would be to use a mod – which isn't perfectly uniform but so long as the hash is much larger than size it is not that bad. Unfortunately, mod/division is fairly slow on ordinary microprocessors (e.g. 90-ish cycles on haswell, ARM doesn't even have an instruction for it.); when the divisor is a constant the compiler will do clever tricks to turn it into a multiply+add+shift, but size is a run-time value so the compiler can't do that here.

One option would be to implement the same trick the compiler uses and compute the constants for exact division based on the size, as described in "{N}-bit Unsigned Division via {N}-bit Multiply-Add" by Arch D. Robison in 2005. But that code is somewhat complicated and the result is still slower than other options:

Instead we treat the 32-bit random number as a Q32 fixed-point number in the range [0,1) and simply multiply it by the size. Then we just shift the result down by 32-bits to get our bucket number. The results has non-uniformity the same as a mod, but it is much faster to compute. More about this technique can be found at http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

The resulting non-uniformity is also more equally distributed which would be advantageous for something like linear probing, though it shouldn't matter one way or the other for a cuckoo table.

The primary disadvantage of this approach is increased intermediate precision is required but for a 32-bit random number we only need the high 32 bits of a 32*32->64 multiply, which means the operation is reasonably fast even on a typical 32-bit processor.

Parameters

e	the element whose hashes will be returned

Returns: std::array<uint32_t, 8> of deterministic hashes derived from e

Definition at line 243 of file cuckoocache.h.

References CuckooCache::cache< Element, Hash >::hash_function, and CuckooCache::cache< Element, Hash >::size.

Referenced by CuckooCache::cache< Element, Hash >::contains(), and CuckooCache::cache< Element, Hash >::insert().

◆ contains()

template<typename Element, typename Hash>

bool CuckooCache::cache< Element, Hash >::contains	(	const Element &	e,
		const bool	erase
	)		const

inline

Definition at line 467 of file cuckoocache.h.

References CuckooCache::cache< Element, Hash >::allow_erase(), CuckooCache::cache< Element, Hash >::compute_hashes(), and CuckooCache::cache< Element, Hash >::table.

◆ epoch_check()

template<typename Element, typename Hash>

void CuckooCache::cache< Element, Hash >::epoch_check ( )

inlineprivate

epoch_check handles the changing of epochs for elements stored in the cache.

epoch_check should be run before every insert.

First, epoch_check decrements and checks the cheap heuristic, and then does a more expensive scan if the cheap heuristic runs out. If the expensive scan succeeds, the epochs are aged and old elements are allow_erased. The cheap heuristic is reset to retrigger after the worst case growth of the current epoch's elements would exceed the epoch_size.

Definition at line 289 of file cuckoocache.h.

References CuckooCache::cache< Element, Hash >::allow_erase(), CuckooCache::bit_packed_atomic_flags::bit_is_set(), CuckooCache::cache< Element, Hash >::collection_flags, CuckooCache::cache< Element, Hash >::epoch_flags, CuckooCache::cache< Element, Hash >::epoch_heuristic_counter, CuckooCache::cache< Element, Hash >::epoch_size, and CuckooCache::cache< Element, Hash >::size.

Referenced by CuckooCache::cache< Element, Hash >::insert().

◆ insert()

template<typename Element, typename Hash>

void CuckooCache::cache< Element, Hash >::insert ( Element e )

inline

insert loops at most depth_limit times trying to insert a hash at various locations in the table via a variant of the Cuckoo Algorithm with eight hash locations.

It drops the last tried element if it runs out of depth before encountering an open slot.

Thus

insert(x); return contains(x, false);

is not guaranteed to return true.

Parameters

e	the element to insert

Postcondition: one of the following: All previously inserted elements and e are now in the table, one previously inserted element is evicted from the table, the entry attempted to be inserted is evicted.

Swap with the element at the location that was not the last one looked at. Example:

1) On first iteration, last_loc == invalid(), find returns last, so last_loc defaults to locs[0]. 2) On further iterations, where last_loc == locs[k], last_loc will go to locs[k+1 % 8], i.e., next of the 8 indices wrapping around to 0 if needed.

This prevents moving the element we just put in.

The swap is not a move – we must switch onto the evicted element for the next iteration.

Definition at line 392 of file cuckoocache.h.

References CuckooCache::bit_packed_atomic_flags::bit_is_set(), CuckooCache::cache< Element, Hash >::collection_flags, CuckooCache::cache< Element, Hash >::compute_hashes(), CuckooCache::cache< Element, Hash >::depth_limit, CuckooCache::cache< Element, Hash >::epoch_check(), CuckooCache::cache< Element, Hash >::epoch_flags, CuckooCache::cache< Element, Hash >::invalid(), CuckooCache::cache< Element, Hash >::please_keep(), and CuckooCache::cache< Element, Hash >::table.

◆ invalid()

template<typename Element, typename Hash>

constexpr uint32_t CuckooCache::cache< Element, Hash >::invalid ( ) const

inlineprivate

Definition at line 257 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::insert().

◆ please_keep()

template<typename Element, typename Hash>

void CuckooCache::cache< Element, Hash >::please_keep ( uint32_t n ) const

inlineprivate

please_keep marks the element at index n as an entry that should be kept.

Threadsafe without any concurrent insert.

Parameters

n	the index to prioritize keeping

Definition at line 275 of file cuckoocache.h.

References CuckooCache::bit_packed_atomic_flags::bit_unset(), and CuckooCache::cache< Element, Hash >::collection_flags.

Referenced by CuckooCache::cache< Element, Hash >::insert().

◆ setup()

template<typename Element, typename Hash>

uint32_t CuckooCache::cache< Element, Hash >::setup ( uint32_t new_size )

inline

setup initializes the container to store no more than new_size elements.

setup should only be called once.

Parameters

new_size the desired number of elements to store

Returns: the maximum number of elements storable

Definition at line 340 of file cuckoocache.h.

References CuckooCache::cache< Element, Hash >::collection_flags, CuckooCache::cache< Element, Hash >::depth_limit, CuckooCache::cache< Element, Hash >::epoch_flags, CuckooCache::cache< Element, Hash >::epoch_heuristic_counter, CuckooCache::cache< Element, Hash >::epoch_size, immer::detail::log2(), CuckooCache::bit_packed_atomic_flags::setup(), CuckooCache::cache< Element, Hash >::size, and CuckooCache::cache< Element, Hash >::table.

Referenced by CuckooCache::cache< Element, Hash >::setup_bytes().

◆ setup_bytes()

template<typename Element, typename Hash>

uint32_t CuckooCache::cache< Element, Hash >::setup_bytes ( size_t bytes )

inline

setup_bytes is a convenience function which accounts for internal memory usage when deciding how many elements to store.

It isn't perfect because it doesn't account for any overhead (struct size, MallocUsage, collection and epoch flags). This was done to simplify selecting a power of two size. In the expected use case, an extra two bits per entry should be negligible compared to the size of the elements.

Parameters

bytes the approximate number of bytes to use for this data structure.

Returns: the maximum number of elements storable (see setup() documentation for more detail)

Definition at line 367 of file cuckoocache.h.

References CuckooCache::cache< Element, Hash >::setup().

Member Data Documentation

◆ collection_flags

template<typename Element, typename Hash>

bit_packed_atomic_flags CuckooCache::cache< Element, Hash >::collection_flags

mutableprivate

The bit_packed_atomic_flags array is marked mutable because we want garbage collection to be allowed to occur from const methods.

Definition at line 171 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::allow_erase(), CuckooCache::cache< Element, Hash >::epoch_check(), CuckooCache::cache< Element, Hash >::insert(), CuckooCache::cache< Element, Hash >::please_keep(), and CuckooCache::cache< Element, Hash >::setup().

◆ depth_limit

template<typename Element, typename Hash>

uint8_t CuckooCache::cache< Element, Hash >::depth_limit

private

depth_limit determines how many elements insert should try to replace.

Should be set to log2(n)

Definition at line 198 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::insert(), and CuckooCache::cache< Element, Hash >::setup().

◆ epoch_flags

template<typename Element, typename Hash>

std::vector<bool> CuckooCache::cache< Element, Hash >::epoch_flags

mutableprivate

epoch_flags tracks how recently an element was inserted into the cache.

true denotes recent, false denotes not-recent. See insert() method for full semantics.

Definition at line 177 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::epoch_check(), CuckooCache::cache< Element, Hash >::insert(), and CuckooCache::cache< Element, Hash >::setup().

◆ epoch_heuristic_counter

template<typename Element, typename Hash>

uint32_t CuckooCache::cache< Element, Hash >::epoch_heuristic_counter

private

epoch_heuristic_counter is used to determine when an epoch might be aged & an expensive scan should be done.

epoch_heuristic_counter is decremented on insert and reset to the new number of inserts which would cause the epoch to reach epoch_size when it reaches zero.

Definition at line 184 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::epoch_check(), and CuckooCache::cache< Element, Hash >::setup().

◆ epoch_size

template<typename Element, typename Hash>

uint32_t CuckooCache::cache< Element, Hash >::epoch_size

private

epoch_size is set to be the number of elements supposed to be in a epoch.

When the number of non-erased elements in an epoch exceeds epoch_size, a new epoch should be started and all current entries demoted. epoch_size is set to be 45% of size because we want to keep load around 90%, and we support 3 epochs at once – one "dead" which has been erased, one "dying" which has been marked to be erased next, and one "living" which new inserts add to.

Definition at line 194 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::epoch_check(), and CuckooCache::cache< Element, Hash >::setup().

◆ hash_function

template<typename Element, typename Hash>

const Hash CuckooCache::cache< Element, Hash >::hash_function

private

hash_function is a const instance of the hash function.

It cannot be static or initialized at call time as it may have internal state (such as a nonce).

Definition at line 204 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::compute_hashes().

◆ size

template<typename Element, typename Hash>

uint32_t CuckooCache::cache< Element, Hash >::size

private

size stores the total available slots in the hash table

Definition at line 167 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::compute_hashes(), CuckooCache::cache< Element, Hash >::epoch_check(), and CuckooCache::cache< Element, Hash >::setup().

◆ table

template<typename Element, typename Hash>

std::vector<Element> CuckooCache::cache< Element, Hash >::table

private

table stores all the elements

Definition at line 164 of file cuckoocache.h.

Referenced by CuckooCache::cache< Element, Hash >::contains(), CuckooCache::cache< Element, Hash >::insert(), and CuckooCache::cache< Element, Hash >::setup().

The documentation for this class was generated from the following file:

src/cuckoocache.h

Dash Core Source Documentation (0.16.0.1)

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename Element, typename Hash> class CuckooCache::cache< Element, Hash >

Constructor & Destructor Documentation

◆ cache()

Member Function Documentation

◆ allow_erase()

◆ compute_hashes()

◆ contains()

◆ epoch_check()

◆ insert()

◆ invalid()

◆ please_keep()

◆ setup()

◆ setup_bytes()

Member Data Documentation

◆ collection_flags

◆ depth_limit

◆ epoch_flags

◆ epoch_heuristic_counter

◆ epoch_size

◆ hash_function

◆ size

◆ table

template<typename Element, typename Hash>
class CuckooCache::cache< Element, Hash >