parallel.hpp File Reference

A minimal std::thread parallel-for for the hot kernels. More...

#include <algorithm>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <cstddef>
#include <exception>
#include <limits>
#include <memory>
#include <mutex>
#include <span>
#include <thread>
#include <vector>
#include <unistd.h>

Include dependency graph for parallel.hpp:

Go to the source code of this file.

Classes
struct	numerical::detail::pool_job
	One parallel_for handed to the pool: its chunks, the next one to take, and how many are done. Each run has its own, so a worker still leaving one run never touches the next. More...
struct	numerical::detail::worker_bell
	A worker's own wake-up: its core, whether it sleeps, and what wakes it. More...
class	numerical::detail::thread_pool
	The threads every kernel shares, started once: a parallel_for costs a wake-up, not a thread start. More...

Namespaces
namespace	numerical
	The NumericAL public API.
namespace	numerical::detail

Typedefs
using	numerical::detail::chunk_runner = void(*)(const void *body, std::size_t begin, std::size_t end)
	A chunk of a parallel_for, type-erased: runs body(i) for i in [begin, end).
using	numerical::detail::side_runner = void(*)(const void *side)
	A task the caller of a run does before it takes chunks (parallel_for_beside), type-erased.

Functions
long	numerical::detail::current_process () noexcept
	This process's identifier: a pool started before a fork belongs to the parent, whose threads the child does not have.
std::vector< std::size_t >	numerical::detail::worker_cores (std::size_t cores, std::size_t threads)
	The core of each worker the pool starts beside its callers, from the cores known (0: none) and its threads (at least 1): one worker per core, pinned there, where the cores are known (each run then leaves out the one on the caller's core, sits_out); else threads − 1 workers free to move.
constexpr bool	numerical::detail::sits_out (std::size_t worker, std::size_t caller) noexcept
	Whether the worker pinned to core worker sits out a run whose caller is on core caller: one thread per core, as two on one core's hyperthreads share its multiply-add units. A free worker never does.
std::size_t	numerical::detail::physical_cores () noexcept
	The physical cores this process may run on, or 0 where the system does not say. Linux: core_sets; macOS: hw.physicalcpu.
constexpr std::size_t	numerical::detail::pool_threads (std::size_t logical, std::size_t physical) noexcept
	The pool's threads from the logical hardware threads and the physical cores (0: unknown): the cores where known, at least 1.
std::size_t	numerical::detail::hardware_threads () noexcept
	The threads the pool runs, the caller's included (at least 1), known without starting the pool: one per physical core where the system tells them (else one per hardware thread). Two threads on one core's hyperthreads share its multiply-add units: a product of order 128 on eight AVX2 cores with sixteen hyperthreads took 140 µs on sixteen threads, 71 on eight; order 2048, the same either way. Asked once, as the pool's workers are started once (glibc reads a file for the hardware threads on every call).
template<typename Ready >
void	numerical::detail::spin_until (const Ready &ready)
	Polls ready, yielding the core between polls, until it holds or spin_time has passed.
constexpr bool	numerical::detail::wants (std::size_t core, std::size_t caller, std::size_t helpers) noexcept
	Whether the worker on core joins a run of helpers workers whose caller is on caller: by rank among the cores, the caller's aside, so a run of few threads takes the same cores from one run to the next.
std::atomic< std::size_t > &	numerical::detail::thread_cap () noexcept
	The most threads a parallel_for uses (0: as many as the pool has), set by numerical::set_max_threads.
std::size_t	numerical::detail::threads_for (std::size_t count, std::size_t work_per_index, std::size_t hardware)
	How many threads count indices of work_per_index each pay for: one per work_per_thread, at most one per index and per hardware thread.
template<typename Body >
void	numerical::detail::parallel_for (std::size_t count, std::size_t work_per_index, const Body &body)
	Runs body(i) for every i in [0, count).
template<typename Body , typename Side >
void	numerical::detail::parallel_for_beside (std::size_t count, std::size_t work_per_index, const Body &body, const Side &side)
	Runs side on the caller while the pool's workers run body(i) for every i in [0, count), then lets the caller take the chunks left: one task beside a parallel loop, each touching what the other does not (a factorisation's next panel beside its trailing update). side's own parallel loops find the pool busy and run in its thread. Where the work pays for fewer than two threads, or the pool is busy, side runs, then the loop, on the caller. An exception of side comes back after the loop's chunks have joined, before theirs.
template<typename T >
constexpr std::size_t	numerical::detail::fault_chunk (std::size_t count) noexcept
	The elements one index of parallel_zero or parallel_copy takes of count: zero_chunk, or, from the size at which a buffer takes Linux's 2 MiB pages (16 MiB), one such page's worth, so that no two threads fault in the same page: they waited on each other's fault there (six x86-64 AVX2 cores, 32 MiB zeroed into fresh memory 3.6 → 2.5 ms; the LU and Cholesky of order 2000, their operand copied by eight 4 KiB pages a thread, took 2 to 4 % longer than with one thread's copy).
template<typename T >
void	numerical::detail::parallel_zero (T *out, std::size_t count)
	Sets the count elements at out to zero, split across the threads the work pays for: a fresh result's pages are first touched, and faulted in, by several threads, where a sequential fill pays every fault on one (a product on eight arm64 threads: 16 % faster at order 512, 7 % at 1024). The zero is a constant in each chunk's fill, which the compiler turns into the C library's zeroing (on arm64 it clears whole cache lines without reading them; a value passed in, stored element by element, was 4 % slower at order 1024 on one thread).
template<typename T >
void	numerical::detail::parallel_copy (const T *in, std::size_t count, T *out)
	Copies the count elements at in to out, split across the threads the work pays for, as parallel_zero does: a fresh copy's pages are faulted in by several threads, where a sequential copy pays every fault on one (a 2 MiB copy into fresh memory took 0.85 ms on one x86-64 core in a container, a third of the Cholesky factorisation of order 512).
void	numerical::set_max_threads (std::size_t threads) noexcept
	Caps the threads a kernel uses at threads, the caller's included (1: none beside it, and no thread is started); 0 lifts the cap. For a process that runs several kernels side by side (one per worker process, say), so that together they do not ask for more threads than the machine has.
std::size_t	numerical::max_threads ()
	The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).

Variables
constexpr std::size_t	numerical::detail::no_core {std::numeric_limits<std::size_t>::max()}
	No core: a worker free to run anywhere, or a caller on a processor the pool does not know.
constexpr std::chrono::microseconds	numerical::detail::spin_time {500}
	How long a thread polls before it sleeps: kernels run in quick succession (a matrix product packs, then computes, panel after panel), and a thread woken from sleep starts tens of microseconds late, its wake-up paid by the caller of the next run, about 10 µs a sleeping worker on six x86-64 cores. A factorisation's steps last about 100 µs at order 256, so at 100 µs the workers one step left out were asleep for the next (an LU of order 256: six x86-64 cores 560 → 500 µs at 500; eight arm64 cores 358 → 324).
constexpr std::size_t	numerical::detail::work_per_thread {std::size_t {1} << 16}
	The work one thread must have to pay for starting it: about 60 µs of multiply-adds, six times the cost of a start (measured on arm64: 16 indices of 4096 ran 80 µs sequentially, 92 µs on eight threads; of 16384, 324 µs and 128 µs).
constexpr std::size_t	numerical::detail::elementwise_chunk {work_per_thread / 4}
	The elements one task of an element-wise operation takes, a quarter of a thread's work: a tensor of a million shares out (M1 Pro, 2000 × 2000 doubles added: 3.1 → 1.4 ms), one of a few hundred thousand stays within its time (a sixteenth: 300 × 300 plus a row 13 % slower, each task setting up its odometer).
constexpr std::size_t	numerical::detail::vector_speedup {4}
	The multiply-adds a vectorised inner loop does in the time of one in work_per_thread's dependent chain: a product weighs its work by it (at order 64, a matrix product on eight threads took 95 µs, on one 35 µs).
constexpr std::size_t	numerical::detail::zero_chunk {std::size_t {1} << 12}
	The elements one index of parallel_zero writes: eight 4 KiB pages of double.
constexpr std::size_t	numerical::detail::zero_work {1}
	The work of zeroing one element, in multiply-adds: a second thread from 1 MiB of double. Below, the allocator mostly hands back memory already touched, and zeroing 512 KiB took 4.5 µs on one arm64 thread, 9 µs split across eight.

Detailed Description

A minimal std::thread parallel-for for the hot kernels.

The only standard-library parallelism a header-only, zero-dependency leaf can use portably: std::thread, no TBB, no execution policies, started once in a shared pool. numerical::detail::parallel_for splits a counted range across the hardware threads — each index is handled by exactly one thread, so a body that writes a disjoint slice of the output per index stays race-free and deterministic (the result is identical to the sequential run, bit for bit). The caller states the work of one index; a range runs on as many threads as its work pays for, and sequentially when that is fewer than two, since waking a thread and handing it work costs time too.

Definition in file parallel.hpp.