NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
parallel.hpp
Go to the documentation of this file.
1
14#ifndef NUMERICAL_PARALLEL_HPP
15#define NUMERICAL_PARALLEL_HPP
16
17#include <algorithm>
18#include <atomic>
19#include <charconv>
20#include <chrono>
21#include <condition_variable>
22#include <cstddef>
23#include <exception>
24#include <limits>
25#include <memory>
26#include <mutex>
27#include <span>
28#include <string>
29#include <string_view>
30#include <system_error>
31#include <thread>
32#include <vector>
33
34#if defined(_WIN32)
35# include <process.h>
36#else
37# include <pthread.h>
38# include <unistd.h>
39#endif
40#if defined(__linux__)
41# include <fstream>
42# include <map>
43# include <string>
44# include <utility>
45# include <sched.h>
46#elif defined(__APPLE__)
47# include <sys/sysctl.h>
48#endif
49
50namespace numerical::detail {
51
55 {
56#if defined(_WIN32)
57 return static_cast<long>(_getpid());
58#else
59 return static_cast<long>(getpid());
60#endif
61 }
62
64 inline constexpr std::size_t no_core {std::numeric_limits<std::size_t>::max()};
65
71 [[nodiscard]] inline std::vector<std::size_t> worker_cores(std::size_t cores,
72 std::size_t threads)
73 {
74 std::vector<std::size_t> out(cores != 0 ? cores : threads - 1, no_core);
75 for (std::size_t c {0}; c < cores; ++c) {
76 out[c] = c;
77 }
78 return out;
79 }
80
83 [[nodiscard]] constexpr bool sits_out(std::size_t worker,
84 std::size_t caller) noexcept
85 {
86 return worker != no_core && worker == caller;
87 }
88
89#if defined(__linux__)
91 [[nodiscard]] inline std::string first_line(const std::string& path)
92 {
93 std::ifstream file {path};
94 std::string line;
95 std::getline(file, line);
96 return line;
97 }
98
105 [[nodiscard]] inline std::vector<cpu_set_t> core_sets_from(const cpu_set_t& allowed,
106 const std::string& cpu_root) noexcept
107 {
108 try {
109 std::map<std::pair<long, long>, std::size_t> index; // (package, core) → its set
110 std::vector<cpu_set_t> sets;
111 for (std::size_t cpu {0}; cpu < static_cast<std::size_t>(CPU_SETSIZE); ++cpu) { // the macros take a size_t
112 if (CPU_ISSET(cpu, &allowed) == 0) { // NOLINT(hicpp-signed-bitwise): the system's macro
113 continue;
114 }
115 const std::string topology {cpu_root + "cpu" + std::to_string(cpu) + "/topology/"};
116 const long core {std::stol(first_line(topology + "core_id"))};
117 const long package {std::stol(first_line(topology + "physical_package_id"))};
118 const auto [where, added] {index.try_emplace({package, core}, sets.size())};
119 if (added) {
120 sets.emplace_back();
121 CPU_ZERO(&sets.back()); // NOLINT(hicpp-signed-bitwise): the system's macro
122 }
123 CPU_SET(cpu, &sets[where->second]); // NOLINT(hicpp-signed-bitwise): the system's macro
124 }
125 return sets;
126 }
127 catch (...) {
128 return {};
129 }
130 }
131
136 [[nodiscard]] inline std::vector<cpu_set_t> core_sets() noexcept
137 {
139 CPU_ZERO(&allowed); // NOLINT(hicpp-signed-bitwise): the system's macro
140 static_cast<void>(sched_getaffinity(0, sizeof(allowed), &allowed)); // on failure the set stays empty
141 return core_sets_from(allowed, "/sys/devices/system/cpu/");
142 }
143
145 [[nodiscard]] inline std::vector<std::size_t> processor_cores(const std::vector<cpu_set_t>& cores)
146 {
147 std::vector<std::size_t> table(CPU_SETSIZE, no_core);
148 for (std::size_t c {0}; c < cores.size(); ++c) {
149 for (std::size_t cpu {0}; cpu < table.size(); ++cpu) {
150 if (CPU_ISSET(cpu, &cores[c]) != 0) { // NOLINT(hicpp-signed-bitwise): the system's macro
151 table[cpu] = c;
152 }
153 }
154 }
155 return table;
156 }
157
160 [[nodiscard]] inline std::size_t core_of(const std::vector<std::size_t>& table,
161 int cpu) noexcept
162 {
163 // Through the subspan from `cpu`: GCC 15 at -O3 reads `table[cpu]` behind an index check (a conditional or an
164 // early return) before the check, and refuses the subscript past the end (-Werror=array-bounds).
165 const std::span<const std::size_t> rest {std::span {table}.subspan(cpu < 0 ? table.size() : std::min(table.size(), static_cast<std::size_t>(cpu)))};
166 return rest.empty() ? no_core : rest.front();
167 }
168
171 inline void pin_to_core(const std::vector<cpu_set_t>& cores,
172 std::size_t index) noexcept
173 {
174 if (index < cores.size()) {
175 (void)sched_setaffinity(0, sizeof(cpu_set_t), &cores[index]);
176 }
177 }
178
179#endif
180
185 [[nodiscard]] inline std::size_t physical_cores() noexcept
186 {
187#if defined(__linux__)
188 return core_sets().size();
189#elif defined(__APPLE__)
190 int cores {0};
191 std::size_t size {sizeof(cores)};
192 (void)sysctlbyname("hw.physicalcpu", &cores, &size, nullptr, 0); // on failure cores stays 0
193 return static_cast<std::size_t>(std::max(cores, 0));
194#else
195 return 0;
196#endif
197 }
198
201 [[nodiscard]] constexpr std::size_t pool_threads(std::size_t logical,
202 std::size_t physical,
203 std::size_t quota = 0) noexcept
204 {
205 const std::size_t hardware {std::max<std::size_t>(1, logical)};
206 const std::size_t cores {physical == 0 ? hardware : std::min(physical, hardware)};
207 return quota == 0 ? cores : std::max<std::size_t>(1, std::min(cores, quota));
208 }
209
212 [[nodiscard]] constexpr std::size_t quota_processors(long long quota,
213 long long period) noexcept
214 {
216 }
217
220 [[nodiscard]] inline std::size_t cpu_max_processors(std::string_view text) noexcept
221 {
222 const auto number {[](std::string_view digits, long long& value) {
223 const auto [end, error] {std::from_chars(digits.data(), digits.data() + digits.size(), value)};
224 return error == std::errc {} && end == digits.data() + digits.size();
225 }};
226 while (!text.empty() && (text.back() == '\n' || text.back() == ' ')) {
227 text.remove_suffix(1);
228 }
229 const std::size_t space {text.find(' ')};
230 long long quota {0};
231 long long period {0};
232 if (space == std::string_view::npos || !number(text.substr(0, space), quota) || !number(text.substr(space + 1), period)) {
233 return 0;
234 }
236 }
237
238#if defined(__linux__)
246 [[nodiscard]] inline std::size_t cgroup_quota()
247 {
248 std::size_t least {0};
249 const auto keep {[&least](std::size_t processors) {
250 if (processors != 0 && (least == 0 || processors < least)) {
252 }
253 }};
254 std::ifstream self {"/proc/self/cgroup"};
255 std::string line;
256 std::string group;
257 while (std::getline(self, line)) {
258 if (line.rfind("0::", 0) == 0) {
259 group = line.substr(3);
260 }
261 }
262 while (!group.empty() && group != "/") {
263 keep(cpu_max_processors(first_line("/sys/fs/cgroup" + group + "/cpu.max")));
264 group.erase(group.rfind('/'));
265 }
266 keep(cpu_max_processors(first_line("/sys/fs/cgroup/cpu.max")));
267 for (const char* const v1 : {"/sys/fs/cgroup/cpu", "/sys/fs/cgroup/cpu,cpuacct"}) {
268 const std::string quota {first_line(std::string {v1} + "/cpu.cfs_quota_us")};
269 const std::string period {first_line(std::string {v1} + "/cpu.cfs_period_us")};
270 keep(cpu_max_processors(quota + " " + period));
271 }
272 return least;
273 }
274
276 [[nodiscard]] inline std::size_t cgroup_processors() noexcept
277 {
278 try {
279 return cgroup_quota();
280 }
281 catch (...) { // a file or a string that cannot be had: no quota known
282 return 0;
283 }
284 }
285
286#endif
287
289 [[nodiscard]] inline std::size_t quota_limit() noexcept
290 {
291#if defined(__linux__)
292 return cgroup_processors();
293#else
294 return 0;
295#endif
296 }
297
306 [[nodiscard]] inline std::size_t hardware_threads() noexcept
307 {
308 static const std::size_t threads {pool_threads(std::thread::hardware_concurrency(), physical_cores(), quota_limit())};
309 return threads;
310 }
311
317 inline constexpr std::chrono::microseconds spin_time {500};
318
320 template <typename Ready>
321 void spin_until(const Ready& ready)
322 {
323 const std::chrono::steady_clock::time_point until {std::chrono::steady_clock::now() + spin_time};
324 while (!ready() && std::chrono::steady_clock::now() < until) {
325 std::this_thread::yield();
326 }
327 }
328
330 using chunk_runner = void (*)(const void* body, std::size_t begin, std::size_t end);
331
333 using side_runner = void (*)(const void* side);
334
339 struct pool_job
340 {
342 const void* body {};
343 std::size_t count {};
344 std::size_t chunk {};
345 std::size_t chunks {};
346 std::size_t helpers {};
347 std::size_t core {no_core};
348 std::atomic<std::size_t> joined {0};
349 std::atomic<std::size_t> next {0};
350 std::atomic<std::size_t> finished {0};
351 std::mutex lock;
352 std::condition_variable done;
353 std::vector<std::exception_ptr> failed;
354
357 {
358 for (std::size_t c {next.fetch_add(1)}; c < chunks; c = next.fetch_add(1)) {
359 try {
360 run(body, c * chunk, std::min(count, (c + 1) * chunk));
361 }
362 catch (...) {
363 failed[c] = std::current_exception();
364 }
365 if (finished.fetch_add(1) + 1 == chunks) {
366 const std::lock_guard<std::mutex> held {lock};
367 done.notify_all();
368 }
369 }
370 }
371 };
372
375 {
376 explicit worker_bell(std::size_t on) : core {on}
377 {}
378
379 const std::size_t core;
380 std::atomic<bool> asleep {false};
381 std::mutex lock;
382 std::condition_variable rung;
383 };
384
387 [[nodiscard]] constexpr bool wants(std::size_t core,
388 std::size_t caller,
389 std::size_t helpers) noexcept
390 {
391 if (core == no_core) {
392 return true;
393 }
394 if (core == caller) {
395 return false;
396 }
397 const std::size_t rank {caller == no_core || core < caller ? core : core - 1};
398 return rank < helpers;
399 }
400
410 {
411 public:
412
413 thread_pool(const thread_pool&) = delete;
417 ~thread_pool() = delete;
418
425 {
426 if (thread_pool* const ready {instance().load(std::memory_order_acquire)}; ready != nullptr) {
427 return *ready;
428 }
429 // Made and started under the start lock, which a fork takes first (lock_for_fork): no child is
430 // forked while the pool is part made, a static's guard or a lock held by a thread the child has not (its first
431 // shared() then waited for ever).
432 const std::lock_guard<std::mutex> one {start_lock()};
433#if !defined(_WIN32)
435 // Without the handlers (no memory for them), a fork during a first start stays as it was.
437#endif
438 static thread_pool* const created {new thread_pool {}}; // once, kept past a start that failed
439 static thread_pool* const pool {[] {
440 created->start();
441 instance().store(created, std::memory_order_release);
442 return created;
443 }()};
444 return *pool;
445 }
446
448 [[nodiscard]] static std::mutex& start_lock() noexcept
449 {
450 static std::mutex lock;
451 return lock;
452 }
453
456 {
457 return instance().load();
458 }
459
465 bool release_on_workers(void ( *release )(),
466 std::chrono::milliseconds wait)
467 {
468 if (owner_ != current_process()) {
469 return true;
470 }
471 const std::lock_guard<std::mutex> one {release_lock_}; // one request at a time
472 std::size_t target {0};
473 {
474 const std::lock_guard<std::mutex> held {lock_};
475 release_.store(release);
476 target = (releases_.fetch_add(1) + 1) * workers_; // every worker acknowledges each request once
477 }
478 for (const std::unique_ptr<worker_bell>& bell : bells_) {
479 { const std::lock_guard<std::mutex> held {bell->lock}; }
480 bell->rung.notify_one();
481 }
482 const std::chrono::steady_clock::time_point until {std::chrono::steady_clock::now() + wait};
483 while (released_.load() < target && std::chrono::steady_clock::now() < until) {
484 std::this_thread::yield();
485 }
486 return released_.load() >= target;
487 }
488
496 const void* body,
497 std::size_t count,
498 std::size_t chunk,
499 std::size_t chunks,
500 std::size_t helpers,
501 side_runner side = nullptr,
502 const void* side_body = nullptr)
503 {
504 bool idle {false};
505 // A forked child has none of the parent's workers, and their locks may be held for good: it runs alone.
506 if (owner_ != current_process() || !busy_.compare_exchange_strong(idle, true)) {
507 return false;
508 }
509 struct release
510 {
511 std::atomic<bool>& busy;
512
513 explicit release(std::atomic<bool>& flag) : busy {flag}
514 {}
515
516 release(const release&) = delete;
517 release& operator=(const release&) = delete;
518 release(release&&) = delete;
519 release& operator=(release&&) = delete;
520 ~release()
521 {
522 busy.store(false);
523 }
524 } const freed {busy_};
525 const auto job {std::make_shared<pool_job>()};
526 job->run = run;
527 job->body = body;
528 job->count = count;
529 job->chunk = chunk;
530 job->chunks = chunks;
531 job->helpers = helpers;
532#if defined(__linux__)
534#endif
535 job->failed.resize(chunks);
536 {
537 const std::lock_guard<std::mutex> held {lock_};
538 current_ = job;
539 generation_.fetch_add(1);
540 }
541 for (std::size_t w {0}; w < bells_.size(); ++w) { // the workers the run wants, asleep: not the one on the caller's core
542 worker_bell& bell {*bells_[w]};
543#if defined(__linux__) // elsewhere no worker is pinned, and every one may join
544 if (!wants(bell.core, job->core, helpers)) {
545 continue;
546 }
547#endif
548 if (bell.asleep.load()) {
549 { const std::lock_guard<std::mutex> held {bell.lock}; }
550 bell.rung.notify_one();
551 }
552 }
553 std::exception_ptr side_failed;
554 if (side != nullptr) {
555 try {
557 }
558 catch (...) {
559 side_failed = std::current_exception();
560 }
561 }
562 job->work();
563 const auto all_done {[&job] { return job->finished.load() == job->chunks; }};
565 {
566 std::unique_lock<std::mutex> held {job->lock};
567 job->done.wait(held, all_done);
568 }
569 if (side_failed) {
570 std::rethrow_exception(side_failed);
571 }
572 for (const std::exception_ptr& error : job->failed) {
573 if (error) {
574 std::rethrow_exception(error);
575 }
576 }
577 return true;
578 }
579
580 private:
581
582 thread_pool() = default;
583
585#if !defined(_WIN32)
588 {
589 start_lock().lock(); // released by unlock_after_fork, in the parent and in the child
590 }
591
594 {
595 start_lock().unlock();
596 }
597
598#endif
599
600 [[nodiscard]] static std::atomic<thread_pool*>& instance() noexcept
601 {
602 static std::atomic<thread_pool*> pool {nullptr};
603 return pool;
604 }
605
611 void start()
612 {
613 // From the first worker not started: a start that failed part way keeps those it started. A bell joins bells_
614 // once its thread runs, into room reserved first, so that no thread is left serving a bell destroyed by a throw.
615#if defined(__linux__)
616 const std::vector<cpu_set_t> cores {core_sets()};
617 const std::vector<std::size_t> wanted {worker_cores(cores.size(), hardware_threads())};
619 bells_.reserve(wanted.size());
620 for (std::size_t w {bells_.size()}; w < wanted.size(); ++w) {
621 const std::size_t core {wanted[w]};
622 auto bell {std::make_unique<worker_bell>(core)};
623 worker_bell* const rung {bell.get()};
624 std::thread {[this, cores, core, rung] {
625 pin_to_core(cores, core);
626 serve(*rung);
627 }}.detach();
628 bells_.push_back(std::move(bell));
629 ++workers_;
630 }
631#else
632 const std::vector<std::size_t> wanted {worker_cores(0, hardware_threads())};
633 bells_.reserve(wanted.size());
634 for (std::size_t w {bells_.size()}; w < wanted.size(); ++w) {
635 auto bell {std::make_unique<worker_bell>(wanted[w])};
636 worker_bell* const rung {bell.get()};
637 std::thread {[this, rung] { serve(*rung); }}.detach();
638 bells_.push_back(std::move(bell));
639 ++workers_;
640 }
641#endif
642 }
643
647 {
648 [[maybe_unused]] const std::size_t core {bell.core};
649 std::size_t seen {0};
650 std::size_t released {0}; // the release requests this worker has served
651#if defined(__linux__)
652 bool spin {true}; // the worker that sat a run out sleeps till the next: polling, it slowed its core's caller
653#endif
654 for (;;) {
655 const auto started {[this, &seen, &released] { return generation_.load() != seen || releases_.load() != released; }};
656#if defined(__linux__)
657 if (spin) {
659 }
660#else
662#endif
663 if (!started()) { // asleep till a run that wants it rings: one that leaves it out never wakes it
664 bell.asleep.store(true);
665 std::unique_lock<std::mutex> held {bell.lock};
666 bell.rung.wait(held, started);
667 bell.asleep.store(false);
668 }
669 if (const std::size_t requested {releases_.load()}; requested != released) { // between runs: its workspaces go
670 release_.load()();
671 released_.fetch_add(requested - released);
673 }
674 if (generation_.load() == seen) { // woken for a release alone
675 continue;
676 }
677 std::shared_ptr<pool_job> job;
678 {
679 const std::lock_guard<std::mutex> held {lock_};
680 seen = generation_.load();
681 job = current_;
682 }
683#if defined(__linux__) // elsewhere no worker is pinned, so none sits out
684 spin = !sits_out(core, job->core);
685 if (!spin) {
686 continue;
687 }
688#endif
689#if defined(__linux__)
690 // By rank among the cores, the caller's aside, not by arrival: a run of few threads then takes the same cores
691 // from one run to the next, their caches still warm (ten AVX-512 cores, an LU of order 1024 on two threads:
692 // 21.5 → 14.6 ms, on four 18 → 11.4; six AVX2 cores unchanged).
693 const bool wanted {wants(core, job->core, job->helpers)};
694#else
695 const bool wanted {true};
696#endif
697 if (wanted && job->joined.fetch_add(1) < job->helpers) { // as many workers as the run's threads, the caller aside
698 job->work();
699 }
700 }
701 }
702
703 std::mutex lock_;
704 std::vector<std::unique_ptr<worker_bell>> bells_;
705 std::shared_ptr<pool_job> current_;
706 std::atomic<std::size_t> generation_ {0};
707 std::atomic<bool> busy_ {false};
708 std::mutex release_lock_;
709 std::atomic<void (*)()> release_ {nullptr};
710 std::atomic<std::size_t> releases_ {0};
711 std::atomic<std::size_t> released_ {0};
712 std::size_t workers_ {0};
713#if defined(__linux__)
714 std::vector<std::size_t> processor_cores_;
715#endif
717 };
718
720 [[nodiscard]] inline std::atomic<std::size_t>& thread_cap() noexcept
721 {
722 static std::atomic<std::size_t> cap {0};
723 return cap;
724 }
725
729 inline constexpr std::size_t work_per_thread {std::size_t {1} << 16};
730
734 inline constexpr std::size_t elementwise_chunk {work_per_thread / 4};
735
739 inline constexpr std::size_t vector_speedup {4};
740
748 [[nodiscard]] inline std::size_t threads_for(std::size_t count,
749 std::size_t work_per_index,
750 std::size_t hardware)
751 {
752 const std::size_t total {work_per_index != 0 && count > std::numeric_limits<std::size_t>::max() / work_per_index
753 ? std::numeric_limits<std::size_t>::max()
754 : count * work_per_index};
755 return std::min({total / work_per_thread, count, std::max<std::size_t>(1, hardware)});
756 }
757
760 inline constexpr std::size_t memory_element_weight {4};
761
766 [[nodiscard]] inline std::size_t parallel_threads(std::size_t count,
767 std::size_t work_per_index)
768 {
769 const std::size_t cap {thread_cap().load()};
770 return threads_for(count, work_per_index, cap == 0 ? hardware_threads() : std::min(cap, hardware_threads()));
771 }
772
789 template <typename Body>
790 void parallel_for(std::size_t count,
791 std::size_t work_per_index,
792 const Body& body)
793 {
794 const std::size_t threads {parallel_threads(count, work_per_index)};
795 const auto runner {[](const void* erased, std::size_t begin, std::size_t end) {
796 const Body& work {*static_cast<const Body*>(erased)};
797 for (std::size_t i {begin}; i < end; ++i) {
798 work(i);
799 }
800 }};
801 if (threads < 2) {
802 runner(&body, 0, count);
803 return;
804 }
805 // Up to four chunks a thread, taken as threads free up, so a slower core holds back no one.
806 const std::size_t chunks {std::max<std::size_t>(1, std::min(count, threads * 4))};
807 const std::size_t chunk {((count + chunks) - 1) / chunks}; // a last chunk past the count runs nothing
808 if (!thread_pool::shared().try_run(runner, &body, count, chunk, chunks, threads - 1)) {
809 runner(&body, 0, count);
810 }
811 }
812
825 template <typename Body,
826 typename Side>
827 void parallel_for_beside(std::size_t count,
828 std::size_t work_per_index,
829 const Body& body,
830 const Side& side)
831 {
832 const std::size_t cap {thread_cap().load()};
833 const std::size_t threads {threads_for(count, work_per_index, cap == 0 ? hardware_threads() : std::min(cap, hardware_threads()))};
834 const auto runner {[](const void* erased, std::size_t begin, std::size_t end) {
835 const Body& work {*static_cast<const Body*>(erased)};
836 for (std::size_t i {begin}; i < end; ++i) {
837 work(i);
838 }
839 }};
840 const auto beside {[](const void* erased) { (*static_cast<const Side*>(erased))(); }};
841 if (threads >= 2) {
842 const std::size_t chunks {std::max<std::size_t>(1, std::min(count, threads * 4))};
843 const std::size_t chunk {((count + chunks) - 1) / chunks};
844 if (thread_pool::shared().try_run(runner, &body, count, chunk, chunks, threads - 1, beside, &side)) {
845 return;
846 }
847 }
848 side();
849 runner(&body, 0, count);
850 }
851
853 inline constexpr std::size_t zero_chunk {std::size_t {1} << 12};
854
862 template <typename T>
863 [[nodiscard]] constexpr std::size_t fault_chunk(std::size_t count) noexcept
864 {
865#if defined(__linux__)
866 constexpr std::size_t huge_page {std::size_t {1} << 21U};
867 constexpr std::size_t huge_least {std::size_t {1} << 24U};
868 if (count >= huge_least / sizeof(T)) {
869 return huge_page / sizeof(T);
870 }
871#else
872 (void)count;
873#endif
874 return zero_chunk;
875 }
876
880 inline constexpr std::size_t zero_work {1};
881
890 template <typename T>
891 void parallel_zero(T* out,
892 std::size_t count)
893 {
894 if (count < 2 * (work_per_thread / zero_work)) { // too little to pay for a second thread
895 std::fill(out, out + count, T {});
896 return;
897 }
898 const std::size_t piece {fault_chunk<T>(count)};
899 parallel_for((count + piece - 1) / piece, piece * zero_work, [out, count, piece](std::size_t chunk) {
900 const std::size_t begin {chunk * piece};
901 std::fill(out + begin, out + std::min(count, begin + piece), T {});
902 });
903 }
904
907 template <typename T>
908 void parallel_fill(T* out,
909 std::size_t count,
910 const T& value)
911 {
912 if (count < 2 * (work_per_thread / zero_work)) { // too little to pay for a second thread
913 std::fill(out, out + count, value);
914 return;
915 }
916 const std::size_t piece {fault_chunk<T>(count)};
917 parallel_for((count + piece - 1) / piece, piece * zero_work, [out, count, piece, &value](std::size_t chunk) {
918 const std::size_t begin {chunk * piece};
919 std::fill(out + begin, out + std::min(count, begin + piece), value);
920 });
921 }
922
929 template <typename T>
930 void parallel_copy(const T* in,
931 std::size_t count,
932 T* out)
933 {
934 if (count < 2 * (work_per_thread / zero_work)) { // too little to pay for a second thread
935 std::copy(in, in + count, out);
936 return;
937 }
938 const std::size_t piece {fault_chunk<T>(count)};
939 parallel_for((count + piece - 1) / piece, piece * zero_work, [in, out, count, piece](std::size_t chunk) {
940 const std::size_t begin {chunk * piece};
941 std::copy(in + begin, in + std::min(count, begin + piece), out + begin);
942 });
943 }
944} // namespace numerical::detail
945
946namespace numerical {
947
953 inline void set_max_threads(std::size_t threads) noexcept
954 {
955 detail::thread_cap().store(threads);
956 }
957
964 [[nodiscard]] inline std::size_t environment_threads(const char* numerical,
965 const char* omp) noexcept
966 {
967 const auto trimmed = [](std::string_view text) noexcept {
968 while (!text.empty() && (text.front() == ' ' || text.front() == '\t')) {
969 text.remove_prefix(1);
970 }
971 while (!text.empty() && (text.back() == ' ' || text.back() == '\t')) {
972 text.remove_suffix(1);
973 }
974 return text;
975 };
976 const auto count = [](std::string_view digits) noexcept {
977 std::size_t value {0};
978 for (const char c : digits) {
979 if (c < '0' || c > '9') {
980 return std::size_t {0};
981 }
982 value = std::min<std::size_t>((value * 10) + static_cast<std::size_t>(c - '0'), std::size_t {1} << 31U);
983 }
984 return value;
985 };
986 const std::string_view own {trimmed(numerical == nullptr ? "" : numerical)};
987 if (!own.empty()) {
988 return count(own);
989 }
990 const std::string_view list {omp == nullptr ? "" : omp};
991 return count(trimmed(std::string_view {list.data(), std::min(list.size(), list.find(','))}));
992 }
993
995 [[nodiscard]] inline std::size_t max_threads()
996 {
997 const std::size_t cap {detail::thread_cap().load()};
998 const std::size_t hardware {detail::hardware_threads()};
999 return cap == 0 ? hardware : std::min(cap, hardware);
1000 }
1001} // namespace numerical
1002
1003#endif // NUMERICAL_PARALLEL_HPP
The threads every kernel shares, started once: a parallel_for costs a wake-up, not a thread start.
Definition parallel.hpp:410
std::mutex lock_
Guards current_ and generation_.
Definition parallel.hpp:703
thread_pool & operator=(thread_pool &&)=delete
bool release_on_workers(void(*release)(), std::chrono::milliseconds wait)
Runs release on every worker, each on its own thread between two runs, never inside one,...
Definition parallel.hpp:465
static void unlock_after_fork() noexcept
pthread_atfork's handler after a fork, in the parent and in the child: the start lock released.
Definition parallel.hpp:593
static thread_pool * started() noexcept
The pool if shared has started it, else nullptr (asking starts nothing).
Definition parallel.hpp:455
thread_pool & operator=(const thread_pool &)=delete
std::shared_ptr< pool_job > current_
The latest run.
Definition parallel.hpp:705
static thread_pool & shared()
The pool, started on first use with a worker per hardware thread beside the caller.
Definition parallel.hpp:424
thread_pool(thread_pool &&)=delete
std::size_t workers_
The threads started.
Definition parallel.hpp:712
thread_pool(const thread_pool &)=delete
std::mutex release_lock_
One release request at a time.
Definition parallel.hpp:708
static void lock_for_fork() noexcept
The started pool, nullptr before.
Definition parallel.hpp:587
std::atomic< void(*)()> release_
What a release request runs on each worker.
Definition parallel.hpp:709
std::atomic< bool > busy_
Whether a run holds the pool.
Definition parallel.hpp:707
void start()
Starts the workers (after construction: each uses the pool), worker_cores: on Linux one per core,...
Definition parallel.hpp:611
bool try_run(chunk_runner run, const void *body, std::size_t count, std::size_t chunk, std::size_t chunks, std::size_t helpers, side_runner side=nullptr, const void *side_body=nullptr)
Runs chunks chunks of chunk indices up to count on the caller and at most helpers workers,...
Definition parallel.hpp:495
std::vector< std::unique_ptr< worker_bell > > bells_
Each worker's, added once it runs; read once the pool is published.
Definition parallel.hpp:704
std::atomic< std::size_t > releases_
Counts the release requests.
Definition parallel.hpp:710
std::atomic< std::size_t > released_
Counts the workers' acknowledgements.
Definition parallel.hpp:711
void serve(worker_bell &bell)
A worker on core: waits for a run (polling a while, then asleep), works on it unless it sits it out,...
Definition parallel.hpp:646
static std::atomic< thread_pool * > & instance() noexcept
Definition parallel.hpp:600
static std::mutex & start_lock() noexcept
The lock under which shared makes and starts the pool, and which a fork takes before it forks.
Definition parallel.hpp:448
long owner_
The process whose threads they are.
Definition parallel.hpp:716
std::atomic< std::size_t > generation_
Counts the runs (polled without the lock).
Definition parallel.hpp:706
What every exception NumericAL throws is, beside its standard base (all but std::bad_alloc and std::s...
Definition vector.hpp:40
constexpr std::size_t no_core
No core: a worker free to run anywhere, or a caller on a processor the pool does not know.
Definition parallel.hpp:64
constexpr std::size_t zero_chunk
The elements one index of parallel_zero writes: eight 4 KiB pages of double.
Definition parallel.hpp:853
void 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 ...
Definition parallel.hpp:891
void 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),...
Definition parallel.hpp:827
constexpr bool 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 pe...
Definition parallel.hpp:83
constexpr std::size_t zero_work
The work of zeroing one element, in multiply-adds: a second thread from 1 MiB of double....
Definition parallel.hpp:880
constexpr std::size_t quota_processors(long long quota, long long period) noexcept
The processors a CPU quota of quota microseconds a period allows, rounded up (cgroup v1's cpu....
Definition parallel.hpp:212
std::vector< std::size_t > 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 th...
Definition parallel.hpp:71
std::size_t parallel_threads(std::size_t count, std::size_t work_per_index)
The threads parallel_for shares count indices of work_per_index out to (threads_for): the hardware's,...
Definition parallel.hpp:766
std::size_t cpu_max_processors(std::string_view text) noexcept
quota_processors of cgroup v2's cpu.max text, "<quota> <period>" ("max" for none): 0 for none or a te...
Definition parallel.hpp:220
constexpr std::size_t vector_speedup
The multiply-adds a vectorised inner loop does in the time of one in work_per_thread's dependent chai...
Definition parallel.hpp:739
constexpr bool 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 th...
Definition parallel.hpp:387
void(*)(const void *side) side_runner
A task the caller of a run does before it takes chunks (parallel_for_beside), type-erased.
Definition parallel.hpp:333
constexpr std::size_t work_per_thread
The work one thread must have to pay for starting it: about 60 µs of multiply-adds,...
Definition parallel.hpp:729
void 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,...
Definition parallel.hpp:930
constexpr std::size_t elementwise_chunk
The elements one task of an element-wise operation takes, a quarter of a thread's work: a tensor of a...
Definition parallel.hpp:734
constexpr std::chrono::microseconds spin_time
How long a thread polls before it sleeps: kernels run in quick succession (a matrix product packs,...
Definition parallel.hpp:317
std::size_t 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,...
Definition parallel.hpp:748
void(*)(const void *body, std::size_t begin, std::size_t end) chunk_runner
A chunk of a parallel_for, type-erased: runs body(i) for i in [begin, end).
Definition parallel.hpp:330
constexpr std::size_t pool_threads(std::size_t logical, std::size_t physical, std::size_t quota=0) noexcept
The pool's threads from the logical hardware threads, the physical cores and the processors a CPU quo...
Definition parallel.hpp:201
void spin_until(const Ready &ready)
Polls ready, yielding the core between polls, until it holds or spin_time has passed.
Definition parallel.hpp:321
void parallel_for(std::size_t count, std::size_t work_per_index, const Body &body)
Runs body(i) for every i in [0, count).
Definition parallel.hpp:790
long current_process() noexcept
This process's identifier: a pool started before a fork belongs to the parent, whose threads the chil...
Definition parallel.hpp:54
void parallel_fill(T *out, std::size_t count, const T &value)
Sets the count elements at out to value, split across the threads as parallel_zero is,...
Definition parallel.hpp:908
std::atomic< std::size_t > & thread_cap() noexcept
The most threads a parallel_for uses (0: as many as the pool has), set by numerical::set_max_threads.
Definition parallel.hpp:720
std::size_t quota_limit() noexcept
The processors the CPU quotas over this process allow (cgroup_processors on Linux),...
Definition parallel.hpp:289
std::size_t physical_cores() noexcept
The physical cores this process may run on, or 0 where the system does not say. Linux: core_sets; mac...
Definition parallel.hpp:185
std::size_t hardware_threads() noexcept
The threads the pool runs, the caller's included (at least 1), known without starting the pool: one p...
Definition parallel.hpp:306
constexpr std::size_t fault_chunk(std::size_t count) noexcept
The elements one index of parallel_zero or parallel_copy takes of count: zero_chunk,...
Definition parallel.hpp:863
constexpr std::size_t memory_element_weight
The weight of an element a pass bound by the memory writes or moves, against a multiply-add,...
Definition parallel.hpp:760
The NumericAL public API.
Definition amx.hpp:44
std::size_t max_threads()
The threads a kernel may use: the cap if one is set, else the hardware threads (starting none).
Definition parallel.hpp:995
std::size_t environment_threads(const char *numerical, const char *omp) noexcept
The cap of threads the environment asks for, as the Python package and OpenBLAS read it: numerical (N...
Definition parallel.hpp:964
void set_max_threads(std::size_t threads) noexcept
Caps the threads a kernel uses at threads, the caller's included (1: none beside it,...
Definition parallel.hpp:953
T min(const tensor< T > &t)
The smallest element (a NaN, if there is one), of a transpose's elements as they lie (in any order th...
One parallel_for handed to the pool: its chunks, the next one to take, and how many are done....
Definition parallel.hpp:340
chunk_runner run
The chunk runner.
Definition parallel.hpp:341
std::atomic< std::size_t > finished
The chunks done.
Definition parallel.hpp:350
std::size_t chunk
Indices per chunk.
Definition parallel.hpp:344
std::size_t count
The number of iterations.
Definition parallel.hpp:343
std::mutex lock
Orders the last chunk's signal against the caller's sleep.
Definition parallel.hpp:351
std::size_t core
The caller's core: its worker sits it out (sits_out).
Definition parallel.hpp:347
std::atomic< std::size_t > joined
The workers that asked to.
Definition parallel.hpp:348
std::size_t helpers
The workers that may join it beside the caller.
Definition parallel.hpp:346
std::size_t chunks
Chunks.
Definition parallel.hpp:345
std::atomic< std::size_t > next
The next chunk to take.
Definition parallel.hpp:349
void work() noexcept
Takes chunks until none is left, keeping the exception each throws.
Definition parallel.hpp:356
std::condition_variable done
Signalled when the last chunk finishes.
Definition parallel.hpp:352
const void * body
The body it is handed.
Definition parallel.hpp:342
std::vector< std::exception_ptr > failed
The exception of each chunk, if it threw.
Definition parallel.hpp:353
A worker's own wake-up: its core, whether it sleeps, and what wakes it.
Definition parallel.hpp:375
const std::size_t core
The core it is pinned to, or no_core.
Definition parallel.hpp:379
std::condition_variable rung
Signalled when a run that wants it starts.
Definition parallel.hpp:382
std::atomic< bool > asleep
Set before it checks for a run and sleeps.
Definition parallel.hpp:380
std::mutex lock
Orders a ring against its sleep.
Definition parallel.hpp:381