NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
buffer.hpp
Go to the documentation of this file.
1
6#ifndef NUMERICAL_BUFFER_HPP
7#define NUMERICAL_BUFFER_HPP
8
9#include <algorithm>
10#include <array>
11#include <atomic>
12#include <complex>
13#include <concepts>
14#include <cstddef>
15#include <cstring>
16#include <limits>
17#include <new>
18#include <memory>
19#include <type_traits>
20#include <utility>
21#include <vector>
22
23#include <mutex>
24
25// A function kept out of its callers, in the spelling each compiler takes.
26#if !defined(NUMERICAL_OUT_OF_LINE)
27# if defined(_MSC_VER) && !defined(__clang__)
28# define NUMERICAL_OUT_OF_LINE __declspec(noinline)
29# else
30# define NUMERICAL_OUT_OF_LINE [[gnu::noinline]] // NOLINT(cppcoreguidelines-macro-usage): an attribute, which no function can stand for
31# endif
32#endif
33
34#if defined(__linux__)
35# include <sys/mman.h>
36#endif
37
38namespace numerical {
39
40 namespace detail {
41
45 inline constexpr std::size_t thread_release_places {256};
46
50 {
51 std::array<void (*)(), thread_release_places> steps {};
52 std::size_t count {0};
53 };
54
57 {
58 thread_local thread_release_steps steps;
59 return steps;
60 }
61
65 inline bool on_release(void (*step)()) noexcept
66 {
68 if (registered.count == thread_release_places) {
69 return false;
70 }
72 ++registered.count;
73 return true;
74 }
75
78 {
80 for (std::size_t i {0}; i < registered.count; ++i) {
81 registered.steps[i]();
82 }
83 }
84
93 template <std::size_t Alignment,
94 std::size_t Places,
95 std::size_t Largest>
97 {
98 public:
99
101 static constexpr std::size_t alignment {Alignment};
102
104 static constexpr std::size_t largest {Largest};
105
108 {
109 static kept_blocks* const blocks {new kept_blocks}; // NOLINT(cppcoreguidelines-owning-memory): lives as long as the process
110 return *blocks;
111 }
112
113 kept_blocks() = default;
114
117 {
118 for (const block& b : kept_) {
119 if (b.start != nullptr) {
120 ::operator delete(b.start, std::align_val_t {alignment});
121 }
122 }
123 }
124
125 kept_blocks(const kept_blocks&) = delete;
129
131 [[nodiscard]] std::byte* take(std::size_t bytes,
132 std::size_t& got) noexcept
133 {
134 const std::lock_guard<std::mutex> held {lock_};
135 block* best {nullptr};
136 for (block& b : kept_) {
137 if (b.start != nullptr && b.bytes >= bytes && b.bytes / 2 < bytes && (best == nullptr || b.bytes < best->bytes)) {
138 best = &b;
139 }
140 }
141 if (best == nullptr) {
142 return nullptr;
143 }
144 got = best->bytes;
145 return std::exchange(best->start, nullptr);
146 }
147
153 [[nodiscard]] bool keep(std::byte* start,
154 std::size_t bytes) noexcept
155 {
156 if (bytes >= largest) {
157 return false;
158 }
159 std::byte* evicted {nullptr};
160 {
161 const std::lock_guard<std::mutex> held {lock_};
162 block* place {&kept_[0]};
163 for (block& b : kept_) {
164 if (b.start == nullptr || b.order < place->order) {
165 place = &b;
166 if (b.start == nullptr) {
167 break;
168 }
169 }
170 }
172 *place = block {start, bytes, ++kept_count_};
173 }
174 if (evicted != nullptr) {
175 ::operator delete(evicted,
176 std::align_val_t {alignment});
177 }
178 return true;
179 }
180
183 {
184 std::array<block, Places> freed {};
185 {
186 const std::lock_guard<std::mutex> held {lock_};
187 freed = std::exchange(kept_, std::array<block, Places> {});
188 }
189 for (const block& b : freed) {
190 if (b.start != nullptr) {
191 ::operator delete(b.start, std::align_val_t {alignment});
192 }
193 }
194 }
195
196 private:
197
198 struct block
199 {
200 std::byte* start {nullptr};
201 std::size_t bytes {0};
202 std::size_t order {0};
203 };
204
205 std::mutex lock_;
206 std::array<block, Places> kept_ {};
207 std::size_t kept_count_ {0};
208 };
209
210#if defined(__linux__)
212 using kept_huge_blocks = kept_blocks<std::size_t {1} << 21U, 2, std::size_t {1} << 26U>;
213
215 inline constexpr std::size_t huge_pages_least {std::size_t {1} << 24U};
216
218 inline constexpr std::size_t kept_pages_largest {huge_pages_least};
219#else
222 inline constexpr std::size_t kept_pages_largest {std::size_t {1} << 25U};
223#endif
224
229 using kept_page_blocks = kept_blocks<std::size_t {4096}, 4, kept_pages_largest>;
230
235 inline constexpr std::size_t kept_pages_least {std::size_t {1} << 20U};
236
238 template <typename T>
239 inline constexpr bool is_complex_number {false};
240
242 template <std::floating_point R>
243 inline constexpr bool is_complex_number<std::complex<R>> {true};
244
252 template <typename T>
253 struct default_init_allocator : std::allocator<T>
254 {
255 using value_type = T;
256
258 template <typename U>
259 struct rebind
260 {
262 };
263
265
268 // NOLINTNEXTLINE(hicpp-explicit-conversions,google-explicit-constructor): the containers rebind an allocator by this conversion
271
272#if defined(__linux__)
274 static constexpr std::size_t huge_page {kept_huge_blocks::alignment};
275
282 static constexpr std::size_t huge_least {huge_pages_least};
283
287 static constexpr std::size_t huge_colours {64};
288
291 [[nodiscard]] static constexpr bool on_huge_pages(std::size_t n) noexcept
292 {
293 return n <= (static_cast<std::size_t>(-1) - huge_page) / sizeof(T) && n * sizeof(T) >= huge_least;
294 }
295
296#endif
297
300 static constexpr std::size_t page_colours {16};
301
304 [[nodiscard]] static constexpr bool on_kept_pages(std::size_t n) noexcept
305 {
306 return n < kept_pages_largest / sizeof(T) && n * sizeof(T) >= kept_pages_least;
307 }
308
312 [[nodiscard]] T* allocate(std::size_t n)
313 {
314#if defined(__linux__)
315 if (on_huge_pages(n)) {
316 static std::atomic<std::size_t> colour {0};
317 const std::size_t offset {((colour.fetch_add(1) % huge_colours) * 4096) + alignof(std::max_align_t) * 4};
318 std::size_t bytes {((offset + (n * sizeof(T))) + huge_page - 1) / huge_page * huge_page};
319 std::byte* start {kept_huge_blocks::shared().take(bytes, bytes)};
320 if (start == nullptr) {
321 start = static_cast<std::byte*>(::operator new(bytes, std::align_val_t {huge_page}));
322 (void)madvise(start, bytes, MADV_HUGEPAGE); // a hint: the pages stay 4 KiB where the system declines
323 }
324 return placed(start, offset, bytes);
325 }
326#endif
327 if (on_kept_pages(n)) {
328 constexpr std::size_t page {kept_page_blocks::alignment};
329 // The block's size from the widest offset, whatever this one's: a count of elements then always asks for one
330 // size of block, so a buffer takes the block one of its size freed (sized from its own offset, a colour of 8
331 // or more took a page more than one below it, and found no kept block that fitted).
332 constexpr std::size_t widest {64 + ((page_colours - 1) * 256)};
333 static std::atomic<std::size_t> colour {0};
334 const std::size_t offset {64 + ((colour.fetch_add(1) % page_colours) * 256)};
335 std::size_t bytes {((widest + (n * sizeof(T))) + page - 1) / page * page};
336 std::byte* start {kept_page_blocks::shared().take(bytes, bytes)};
337 if (start == nullptr) {
338 start = static_cast<std::byte*>(::operator new(bytes, std::align_val_t {page}));
339 }
340 return placed(start, offset, bytes);
341 }
342 return std::allocator<T>::allocate(n);
343 }
344
346 void deallocate(T * at,
347 std::size_t n) noexcept
348 {
349#if defined(__linux__)
350 if (on_huge_pages(n)) {
352 return;
353 }
354#endif
355 if (on_kept_pages(n)) {
357 return;
358 }
359 std::allocator<T>::deallocate(at, n);
360 }
361
363 [[nodiscard]] static T* placed(std::byte* start,
364 std::size_t offset,
365 std::size_t bytes) noexcept
366 {
367 std::byte* const data {start + offset};
368 std::memcpy(data - sizeof(std::size_t), &offset, sizeof(std::size_t)); // the start, as the data's distance from it
369 std::memcpy(data - (2 * sizeof(std::size_t)), &bytes, sizeof(std::size_t)); // the block's size
370 return reinterpret_cast<T*>(data); // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): storage for T, aligned past max_align_t
371 }
372
378 template <typename Kept>
379 NUMERICAL_OUT_OF_LINE static void deallocate_kept(T* at) noexcept
380 {
381 auto* const data {reinterpret_cast<std::byte*>(at)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the storage's bytes
382 std::size_t offset {};
383 std::size_t bytes {};
384 std::memcpy(&offset, data - sizeof(std::size_t), sizeof(std::size_t));
385 std::memcpy(&bytes, data - (2 * sizeof(std::size_t)), sizeof(std::size_t));
386 if (!Kept::shared().keep(data - offset, bytes)) {
387 ::operator delete(data - offset,
388 std::align_val_t {Kept::alignment});
389 }
390 }
391
393 template <typename U>
394 requires (!is_complex_number<U>)
395 void construct(U* at) noexcept(std::is_nothrow_default_constructible_v<U>)
396 {
397 ::new (static_cast<void*>(at)) U;
398 }
399
404 template <typename U>
405 requires is_complex_number<U>
406 void construct([[maybe_unused]] U* at) noexcept
407 {
408#ifndef NDEBUG
409 const typename U::value_type nan {std::numeric_limits<typename U::value_type>::quiet_NaN()};
410 const std::array<typename U::value_type, 2> parts {nan, nan};
411 std::memcpy(static_cast<void*>(at), parts.data(), sizeof(parts)); // its two parts ([complex.numbers])
412#endif
413 }
414
416 template <typename U,
417 typename ... Args>
418 void construct(U * at,
419 Args&&... args)
420 {
421 ::new (static_cast<void*>(at)) U(std::forward<Args>(args)...);
422 }
423 };
424
429 template <typename T>
431 const std::vector<T>& other)
432 {
433 return std::equal(buffer.begin(), buffer.end(), other.begin(), other.end());
434 }
435 } // namespace detail
436
442 template <typename T>
443 using buffer = std::vector<T, detail::default_init_allocator<T>>;
444} // namespace numerical
445
446#endif // NUMERICAL_BUFFER_HPP
#define NUMERICAL_OUT_OF_LINE
Definition buffer.hpp:30
Blocks freed and kept for the next buffer that fits one: a fresh block's pages are each faulted in an...
Definition buffer.hpp:97
static kept_blocks & shared()
The process's blocks, never destroyed: a buffer of static storage may be freed after any destructor.
Definition buffer.hpp:107
static constexpr std::size_t alignment
The alignment of a block.
Definition buffer.hpp:101
bool keep(std::byte *start, std::size_t bytes) noexcept
Keeps the block at start of bytes if it is under largest, in place of the block kept longest when eve...
Definition buffer.hpp:153
std::array< block, Places > kept_
Definition buffer.hpp:206
kept_blocks(kept_blocks &&)=delete
kept_blocks & operator=(const kept_blocks &)=delete
void clear() noexcept
Frees every block kept (numerical::release_memory).
Definition buffer.hpp:182
static constexpr std::size_t largest
The bytes from which a freed block is freed at once, not kept.
Definition buffer.hpp:104
std::byte * take(std::size_t bytes, std::size_t &got) noexcept
A kept block of at least bytes and under twice as many, its size in got; nullptr if none.
Definition buffer.hpp:131
kept_blocks & operator=(kept_blocks &&)=delete
kept_blocks(const kept_blocks &)=delete
~kept_blocks()
Frees the blocks still kept.
Definition buffer.hpp:116
bool on_release(void(*step)()) noexcept
Registers step among the calling thread's thread_releases, while a place is left (a workspace past th...
Definition buffer.hpp:65
constexpr std::size_t kept_pages_least
The fewest bytes a buffer takes a kept block of 4 KiB pages for (kept_page_blocks): below,...
Definition buffer.hpp:235
constexpr std::size_t thread_release_places
The most workspaces a thread registers (on_release): one per kind, scalar type and slot,...
Definition buffer.hpp:45
void release_thread_memory()
Empties every workspace the calling thread keeps between calls: its thread_releases,...
Definition buffer.hpp:77
constexpr std::size_t kept_pages_largest
The bytes under which a buffer's block is a kept one, no huge pages asked: 32 MiB,...
Definition buffer.hpp:222
constexpr bool is_complex_number
Whether T is a std::complex of a floating-point type.
Definition buffer.hpp:239
bool operator==(const std::vector< T, default_init_allocator< T > > &buffer, const std::vector< T > &other)
Element-wise equality of a numerical::buffer and a std::vector, found by argument-dependent lookup th...
Definition buffer.hpp:430
thread_release_steps & thread_releases() noexcept
The calling thread's thread_release_steps.
Definition buffer.hpp:56
The NumericAL public API.
Definition amx.hpp:44
std::vector< T, detail::default_init_allocator< T > > buffer
The storage of vector, matrix and tensor, namely a std::vector whose buffer<T>(n) and resize(n) leave...
Definition buffer.hpp:443
The allocator of another element type, as std::allocator_traits rebinds it.
Definition buffer.hpp:260
The allocator of numerical::buffer. An element constructed with no value is default-initialised,...
Definition buffer.hpp:254
static void deallocate_kept(T *at) noexcept
Frees the block allocate gave from at, kept by Kept where it takes it. Out of line: inlined where a s...
Definition buffer.hpp:379
void construct(U *at) noexcept
construct of a complex number, whose default constructor zeroes: left as its memory holds it,...
Definition buffer.hpp:406
void construct(U *at, Args &&... args)
Constructs the element at at from args.
Definition buffer.hpp:418
static constexpr std::size_t page_colours
The data's offset past a kept block's start goes round 16 multiples of 256 bytes past a cache line th...
Definition buffer.hpp:300
static T * placed(std::byte *start, std::size_t offset, std::size_t bytes) noexcept
The data at offset into the block at start of bytes, the offset and the size kept before it.
Definition buffer.hpp:363
void deallocate(T *at, std::size_t n) noexcept
Frees what allocate gave for n elements.
Definition buffer.hpp:346
void construct(U *at) noexcept(std::is_nothrow_default_constructible_v< U >)
Default-initialises the element at at.
Definition buffer.hpp:395
static constexpr bool on_kept_pages(std::size_t n) noexcept
Whether n elements take a block of 4 KiB pages kept when freed (kept_page_blocks): from kept_pages_le...
Definition buffer.hpp:304
T * allocate(std::size_t n)
n elements: on huge pages from their least bytes on Linux, in a kept block of 4 KiB pages from kept_p...
Definition buffer.hpp:312
std::size_t order
When it was kept, the least the longest.
Definition buffer.hpp:202
std::byte * start
The block's start, nullptr for a free place.
Definition buffer.hpp:200
The calling thread's steps that empty the workspaces it keeps between calls, each registered by the w...
Definition buffer.hpp:50
std::array< void(*)(), thread_release_places > steps
The steps, in their order of registration.
Definition buffer.hpp:51