Class providing support for cumulative sums. More...

#include <branch_selection.hpp>

Public Member Functions
	branchless_scan ()

dtype	get (uint8_t index) const
	Get the cumulative sum at `index`. More...

void	set (uint8_t index, dtype value)
	Set the value at `index` to `value`. More...

template<class T >
void	increment (uint8_t from, uint8_t array_size, T change)
	Increments all values in \([\mathrm{from}, \mathrm{array\_size})\) range. More...

void	insert (uint8_t index, uint8_t array_size, dtype a_value, dtype b_value)
	Inserts a new value into the cumulative sums. More...

void	remove (uint8_t index, uint8_t array_size)
	Removes a value from the cumulative sums. More...

void	clear_first (uint8_t n, uint8_t array_size)
	Removes the first `n` elements from the structure. More...

void	clear_last (uint8_t n, uint8_t array_size)
	Removes the last `n` elements from the structure. More...

void	append (uint8_t n_elems, uint8_t array_size, branchless_scan *other)
	Adds elements from `other` to the end of `this` More...

void	append (uint8_t index, dtype value)
	Adds single element to the end of `this` More...

void	prepend (uint8_t n_elems, uint8_t array_size, uint8_t o_size, branchless_scan *other)
	Adds elements form `other` to the start of `this` More...

uint8_t	find (dtype q) const
	Find the lowest child index s.t. the cumulative sum at the index is at least q. More...

Protected Attributes
dtype	elems_ [branches]

Detailed Description

template<class dtype, dtype branches>
class bv::branchless_scan< dtype, branches >

Class providing support for cumulative sums.

Supports maintaining cumulative sums for branching in internal nodes.

Querying is implemented as a branchless binary search using the sign bit for arithmetic instead of conditional moves.

Template Parameters

dtype	Integer type to use for indexing (uint32_t or uint64_t).
branches	Maximum branching factor of nodes.

Constructor & Destructor Documentation

◆ branchless_scan()

template<class dtype , dtype branches>

bv::branchless_scan< dtype, branches >::branchless_scan ( )

inline

Constructor creates an empty container for cumulative sums.

Member Function Documentation

◆ append() [1/2]

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::append	(	uint8_t	index,
		dtype	value
	)

inline

Adds single element to the end of this

Used when splitting root nodes.

Parameters

index	Size of this.
value	Value to append.

◆ append() [2/2]

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::append	(	uint8_t	n_elems,
		uint8_t	array_size,
		branchless_scan< dtype, branches > *	other
	)

inline

Adds elements from other to the end of this

Intended for use when rebalancing. Adds n_elemes elements from other to the end of "these" cumulative sums. Should be subsequently removed from other

Parameters

n_elems	Number of elements to append.
array_size	Number of elements stored in `this`.
other	Other cumulative size structure to copy from.

◆ clear_first()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::clear_first	(	uint8_t	n,
		uint8_t	array_size
	)

inline

Removes the first n elements from the structure.

Intended for use when rebalancing. A sibling has taken over some of the children and this is called to remove the moved children from the current node. Subsequent cumulative sums will be updated accordingly.

Parameters

n	Number of elements to remove.
array_size	Number of elements stored.

◆ clear_last()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::clear_last	(	uint8_t	n,
		uint8_t	array_size
	)

inline

Removes the last n elements from the structure.

Intended for use when rebalancing. A sibling has taken over some of the children and this is called to remove the moved children from the current node.

Parameters

n	Number of elements to remove.
array_size	Number of elements stored.

◆ find()

template<class dtype , dtype branches>

uint8_t bv::branchless_scan< dtype, branches >::find ( dtype q ) const

inline

Find the lowest child index s.t. the cumulative sum at the index is at least q.

This is implemented as a branchless binary search that uses the "sign bit" for index manipulations instead of conditional moves. This is the reason for limiting the maximum data structure size to (~dtype(0)) >> 1.

If \(q > \) elems_[branches - 1], this will return either the index of the last child or the index following the last child. Either way, this will likely very quickly lead to undefined behaviour and segmentation fault.

If elems_[branches - 1] > (~(dtype(0)) >> 1, querying is considered undefined behaviour.

This conditionally compiles the binary search based on acceptable branch factors. For low branching factors this is expected to be slightly slower than efficient vectorized linear searches. For higher branchin factors this branchless binary search should be faster as long as cache performance is good. Agressive prefetching is done in an attempt to ensure that cache misses don't occur during querying. See https://github.com/saskeli/search_microbench for a simple benchmark.

Parameters

q	Query target

Returns: \(\underset{i}{\mathrm{arg min}}(\mathrm{cum\_sums}[i] \geq q)\).

◆ get()

template<class dtype , dtype branches>

dtype bv::branchless_scan< dtype, branches >::get ( uint8_t index ) const

inline

Get the cumulative sum at index.

Parameters

index Index to query.

Returns: Cumulative sum at index.

◆ increment()

template<class dtype , dtype branches>

template<class T >

void bv::branchless_scan< dtype, branches >::increment	(	uint8_t	from,
		uint8_t	array_size,
		T	change
	)

inline

Increments all values in \([\mathrm{from}, \mathrm{array\_size})\) range.

Cumulative sums will always increment all subsequent values. Has to be passed as a parameter, since the value is not maintained by the branch_selection object.

The value may be negative or zero and will behave as expected.

Template Parameters

T	Either a signer or unsigned integer type.

Parameters

from	Start point of increment.
array_size	End point of increment (size of array).
change	Value to add ot each element in the range.

◆ insert()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::insert	(	uint8_t	index,
		uint8_t	array_size,
		dtype	a_value,
		dtype	b_value
	)

inline

Inserts a new value into the cumulative sums.

Intended for use when a new node is created between 2 exisiting nodes. Thus index is greater than 0 and less than array_size.

The cumulative sums of only 2 elements will be impacted since new "things" are not added. Rather some of the existing "things" are rebalanced, with the new element some of the "old" "things".

Parameters

index	Position of new element.
array_size	Number of elements currently in the array.
a_value	Value of the left element.
b_value	Value of the right element.

◆ prepend()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::prepend	(	uint8_t	n_elems,
		uint8_t	array_size,
		uint8_t	o_size,
		branchless_scan< dtype, branches > *	other
	)

inline

Adds elements form other to the start of this

Intended for use when rebalancing. Adds n_elemes elements from other to the start of "these" cumulative sums. Should be subsequently removed from other

Parameters

n_elems	Number of elements to append.
array_size	Number of elements stored in `this`.
o_size	Number of elements stored in `other`.
other	Other cumulative size structure to copy from.

◆ remove()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::remove	(	uint8_t	index,
		uint8_t	array_size
	)

inline

Removes a value from the cumulative sums.

Intended for use when merging nodes.

Does not update the cumulative sums as it is expected that the elements in the removed node have been moved.

Parameters

index	Position of element to remove.
array_size	Number of elements in the array.

◆ set()

template<class dtype , dtype branches>

void bv::branchless_scan< dtype, branches >::set	(	uint8_t	index,
		dtype	value
	)

inline

Set the value at index to value.

Does no updating of internal sums or parameter validation.

A call to get(i) will return v after a set(i, v) call. All other values will remain unchanged.

Parameters

index	Index of value to modify.
value	New value to set.

Member Data Documentation

◆ elems_

template<class dtype , dtype branches>

dtype bv::branchless_scan< dtype, branches >::elems_[branches]

protected

Underlying storage for cumulative sums.

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

bit_vector/internal/branch_selection.hpp

Public Member Functions

Protected Attributes

Detailed Description

template<class dtype, dtype branches> class bv::branchless_scan< dtype, branches >

Constructor & Destructor Documentation

◆ branchless_scan()

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ clear_first()

◆ clear_last()

◆ find()

◆ get()

◆ increment()

◆ insert()

◆ prepend()

◆ remove()

◆ set()

Member Data Documentation

◆ elems_

template<class dtype, dtype branches>
class bv::branchless_scan< dtype, branches >