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