1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include <__algorithm/min.h>
10 #include <__algorithm/pstl_backends/cpu_backends/libdispatch.h>
11 #include <__config>
12 #include <dispatch/dispatch.h>
13 #include <thread>
14 
15 _LIBCPP_BEGIN_NAMESPACE_STD
16 
17 namespace __par_backend::inline __libdispatch {
18 
19 
20 void __dispatch_apply(size_t chunk_count, void* context, void (*func)(void* context, size_t chunk)) noexcept {
21   ::dispatch_apply_f(chunk_count, DISPATCH_APPLY_AUTO, context, func);
22 }
23 
24 __chunk_partitions __partition_chunks(ptrdiff_t element_count) {
25   if (element_count == 0) {
26     return __chunk_partitions{1, 0, 0};
27   } else if (element_count == 1) {
28     return __chunk_partitions{1, 0, 1};
29   }
30 
31   __chunk_partitions partitions;
32   partitions.__chunk_count_ = [&] {
33     ptrdiff_t cores = std::max(1u, thread::hardware_concurrency());
34 
35     auto medium = [&](ptrdiff_t n) { return cores + ((n - cores) / cores); };
36 
37     // This is an approximation of `log(1.01, sqrt(n))` which seemes to be reasonable for `n` larger than 500 and tops
38     // at 800 tasks for n ~ 8 million
39     auto large = [](ptrdiff_t n) { return static_cast<ptrdiff_t>(100.499 * std::log(std::sqrt(n))); };
40 
41     if (element_count < cores)
42       return element_count;
43     else if (element_count < 500)
44       return medium(element_count);
45     else
46       return std::min(medium(element_count), large(element_count)); // provide a "smooth" transition
47   }();
48   partitions.__chunk_size_       = element_count / partitions.__chunk_count_;
49   partitions.__first_chunk_size_ = partitions.__chunk_size_;
50 
51   const ptrdiff_t leftover_item_count = element_count - (partitions.__chunk_count_ * partitions.__chunk_size_);
52 
53   if (leftover_item_count == 0)
54     return partitions;
55 
56   if (leftover_item_count == partitions.__chunk_size_) {
57     partitions.__chunk_count_ += 1;
58     return partitions;
59   }
60 
61   const ptrdiff_t n_extra_items_per_chunk = leftover_item_count / partitions.__chunk_count_;
62   const ptrdiff_t n_final_leftover_items  = leftover_item_count - (n_extra_items_per_chunk * partitions.__chunk_count_);
63 
64   partitions.__chunk_size_ += n_extra_items_per_chunk;
65   partitions.__first_chunk_size_ = partitions.__chunk_size_ + n_final_leftover_items;
66   return partitions;
67 }
68 
69 // NOLINTNEXTLINE(llvm-namespace-comment) // This is https://llvm.org/PR56804
70 } // namespace __par_backend::inline __libdispatch
71 
72 _LIBCPP_END_NAMESPACE_STD
73