MySQL 8.0.33
Source Code Documentation
atomics_array_index_interleaved.h
Go to the documentation of this file.
1/* Copyright (c) 2020, 2023, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is also distributed with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have included with MySQL.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License, version 2.0, for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
22
23#ifndef CONTAINER_ARRAY_ATOMICS_INDEX_INTERLEAVED
24#define CONTAINER_ARRAY_ATOMICS_INDEX_INTERLEAVED
25
26#include <algorithm>
27#include <atomic>
28#include <cmath>
29#include <map>
30#include <memory>
31#include <sstream>
32#include <thread>
33#include <tuple>
34
35#include "sql/memory/aligned_atomic.h" // memory::minimum_cacheline_for
36
37namespace container {
38
39/**
40 Indexing provider that interleaves sequentially stored array elements in
41 order to keep them from being pulled to the same cache line, in order to
42 avoid false sharing and cache misses.
43
44 However, false sharing is only avoided for particular access patterns,
45 namely, when it is heuristically unlikely (or impossible) that concurrent
46 threads access array elements that are far apart.
47
48 The array layout is as follows. When each cache line has capacity for C
49 array elements, the array is sliced into C sub-arrays. The sub-arrays are
50 stored in an interleaved manner, such that the i'th sub-array uses the
51 i'th element within each cache line. For instance, if the machine uses
52 128 byte cache lines, and an array has 6 elements, and each elements uses
53 64 bytes, the array will be laid out as follows:
54
55 | byte position | element number | cache line # |
56 | 0 | 0 | 0 |
57 | 64 | 3 | 0 |
58 | 128 | 1 | 1 |
59 | 192 | 4 | 1 |
60 | 256 | 2 | 2 |
61 | 320 | 5 | 2 |
62
63 This class translates element-to-byte indexing as if each consecutive
64 array index has CPU cache line bytes between them, hence, interleaving
65 consecutive array indexes. The CPU cache line size is calculated at
66 runtime.
67 */
68template <typename T>
70 public:
71 using type = std::atomic<T>;
72
73 /**
74 Constructor for the class that takes the number of elements in the
75 array. This value may be increased in order to address CPU cache line
76 alignment.
77 */
78 Interleaved_indexing(size_t max_size);
79 /**
80 Class destructor.
81 */
82 virtual ~Interleaved_indexing() = default;
83 /**
84 The size of the array.
85
86 @return the size of the array
87 */
88 size_t size() const;
89 /**
90 Translates the element index to the byte position in the array.
91
92 @param index the element index to be translated.
93
94 @return the byte position in the byte array.
95 */
96 size_t translate(size_t index) const;
97 /**
98 The array element size, in bytes.
99
100 @return The array element size, in bytes.
101 */
102 static size_t element_size();
103
104 private:
105 /** The array size */
106 size_t m_size{0};
107 /** The size of the CPU cache line */
109 /** The number of array elements that fit a cache line */
110 size_t m_page_size{0};
111 /** The number of cache lines that fit in the byte array */
112 size_t m_pages{0};
113};
114} // namespace container
115
116template <typename T>
118 : m_cacheline_size{memory::minimum_cacheline_for<
120 m_page_size{m_cacheline_size / sizeof(Interleaved_indexing::type)},
121 m_pages{std::max(static_cast<size_t>(1),
122 (size + m_page_size - 1) / m_page_size)} {
123 this->m_size = this->m_pages * this->m_page_size;
124}
125
126template <typename T>
128 return this->m_size;
129}
130
131template <typename T>
133 return (((index % this->m_pages) * this->m_page_size) +
134 (index / this->m_pages)) *
136}
137
138template <typename T>
140 return sizeof(Interleaved_indexing::type);
141}
142
143#endif // CONTAINER_ARRAY_ATOMICS_INDEX_INTERLEAVED
Indexing provider that interleaves sequentially stored array elements in order to keep them from bein...
Definition: atomics_array_index_interleaved.h:69
size_t m_page_size
The number of array elements that fit a cache line.
Definition: atomics_array_index_interleaved.h:110
Interleaved_indexing(size_t max_size)
Constructor for the class that takes the number of elements in the array.
Definition: atomics_array_index_interleaved.h:117
size_t translate(size_t index) const
Translates the element index to the byte position in the array.
Definition: atomics_array_index_interleaved.h:132
size_t m_size
The array size.
Definition: atomics_array_index_interleaved.h:106
size_t m_cacheline_size
The size of the CPU cache line.
Definition: atomics_array_index_interleaved.h:108
size_t m_pages
The number of cache lines that fit in the byte array.
Definition: atomics_array_index_interleaved.h:112
static size_t element_size()
The array element size, in bytes.
Definition: atomics_array_index_interleaved.h:139
std::atomic< T > type
Definition: atomics_array_index_interleaved.h:71
virtual ~Interleaved_indexing()=default
Class destructor.
size_t size() const
The size of the array.
Definition: atomics_array_index_interleaved.h:127
Definition: atomics_array.h:38
Definition: aligned_atomic.h:43
static size_t minimum_cacheline_for()
Retrieves the amount of bytes, multiple of the current cacheline size, needed to store an element of ...
Definition: aligned_atomic.h:132
Definition: varlen_sort.h:183