container::Interleaved_indexing< T > Class Template Reference

Indexing provider that interleaves sequentially stored array elements in order to keep them from being pulled to the same cache line, in order to avoid false sharing and cache misses. More...

#include <atomics_array_index_interleaved.h>

Public Types
using	type = std::atomic< T >

Public Member Functions
	Interleaved_indexing (size_t max_size)
	Constructor for the class that takes the number of elements in the array. More...
virtual	~Interleaved_indexing ()=default
	Class destructor. More...
size_t	size () const
	The size of the array. More...
size_t	translate (size_t index) const
	Translates the element index to the byte position in the array. More...

Static Public Member Functions
static size_t	element_size ()
	The array element size, in bytes. More...

Private Attributes
size_t	m_size {0}
	The array size. More...
size_t	m_cacheline_size {0}
	The size of the CPU cache line. More...
size_t	m_page_size {0}
	The number of array elements that fit a cache line. More...
size_t	m_pages {0}
	The number of cache lines that fit in the byte array. More...

Detailed Description

template<typename T>
class container::Interleaved_indexing< T >

Indexing provider that interleaves sequentially stored array elements in order to keep them from being pulled to the same cache line, in order to avoid false sharing and cache misses.

However, false sharing is only avoided for particular access patterns, namely, when it is heuristically unlikely (or impossible) that concurrent threads access array elements that are far apart.

The array layout is as follows. When each cache line has capacity for C array elements, the array is sliced into C sub-arrays. The sub-arrays are stored in an interleaved manner, such that the i'th sub-array uses the i'th element within each cache line. For instance, if the machine uses 128 byte cache lines, and an array has 6 elements, and each elements uses 64 bytes, the array will be laid out as follows:

| byte position | element number | cache line # | | 0 | 0 | 0 | | 64 | 3 | 0 | | 128 | 1 | 1 | | 192 | 4 | 1 | | 256 | 2 | 2 | | 320 | 5 | 2 |

This class translates element-to-byte indexing as if each consecutive array index has CPU cache line bytes between them, hence, interleaving consecutive array indexes. The CPU cache line size is calculated at runtime.

Member Typedef Documentation

type

template<typename T >

using container::Interleaved_indexing< T >::type = std::atomic<T>

Constructor & Destructor Documentation

Interleaved_indexing()

template<typename T >

container::Interleaved_indexing< T >::Interleaved_indexing

(

size_t

max_size

)

Constructor for the class that takes the number of elements in the array.

This value may be increased in order to address CPU cache line alignment.

~Interleaved_indexing()

template<typename T >

virtual container::Interleaved_indexing< T >::~Interleaved_indexing ( )

virtualdefault

Class destructor.

Member Function Documentation

element_size()

template<typename T >

size_t container::Interleaved_indexing< T >::element_size

static

The array element size, in bytes.

Returns

The array element size, in bytes.

size()

template<typename T >

size_t container::Interleaved_indexing< T >::size

The size of the array.

Returns

the size of the array

translate()

template<typename T >

size_t container::Interleaved_indexing< T >::translate

(

size_t

index

)

const

Translates the element index to the byte position in the array.

Parameters

index

the element index to be translated.

Returns

the byte position in the byte array.

Member Data Documentation

m_cacheline_size

template<typename T >

size_t container::Interleaved_indexing< T >::m_cacheline_size {0}

private

The size of the CPU cache line.

m_page_size

template<typename T >

size_t container::Interleaved_indexing< T >::m_page_size {0}

private

The number of array elements that fit a cache line.

m_pages

template<typename T >

size_t container::Interleaved_indexing< T >::m_pages {0}

private

The number of cache lines that fit in the byte array.

m_size

template<typename T >

size_t container::Interleaved_indexing< T >::m_size {0}

private

The array size.

---

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

• sql/containers/atomics_array_index_interleaved.h