Shamrock 2025.10.0
Astrophysical Code
Loading...
Searching...
No Matches
sort_by_keys.cpp
Go to the documentation of this file.
1// -------------------------------------------------------//
2//
3// SHAMROCK code for hydrodynamics
4// Copyright (c) 2021-2026 Timothée David--Cléris <tim.shamrock@proton.me>
5// SPDX-License-Identifier: CeCILL Free Software License Agreement v2.1
6// Shamrock is licensed under the CeCILL 2.1 License, see LICENSE for more information
7//
8// -------------------------------------------------------//
9
16
25#include <type_traits>
26#include <algorithm>
27#include <vector>
28
29namespace shamalgs::primitives::details {
30
33 template<class Tkey, class Tval>
35 sham::DeviceBuffer<Tkey> &buf_key, sham::DeviceBuffer<Tval> &buf_values, u32 len) {
36
37 std::vector<Tkey> key_stdvec = buf_key.copy_to_stdvec();
38 std::vector<Tval> val_stdvec = buf_values.copy_to_stdvec();
39
40 std::vector<Tkey> key_sub(key_stdvec.begin(), key_stdvec.begin() + len);
41 std::vector<Tval> val_sub(val_stdvec.begin(), val_stdvec.begin() + len);
42
44
45 std::copy(key_sub.begin(), key_sub.end(), key_stdvec.begin());
46 std::copy(val_sub.begin(), val_sub.end(), val_stdvec.begin());
47
48 buf_key.copy_from_stdvec(key_stdvec);
49 buf_values.copy_from_stdvec(val_stdvec);
50 }
51
52} // namespace shamalgs::primitives::details
53
54namespace shamalgs::primitives {
55
57 namespace impl {
58
60 struct StdSort {
61 static constexpr std::string_view variant_type_name = "std_sort";
62 };
63
66 static constexpr std::string_view variant_type_name = "batcher_odd_even_host_serial";
67 };
68
71 static constexpr std::string_view variant_type_name = "batcher_odd_even";
72 };
73
76 struct LsdRadixSortBasic {
77 static constexpr std::string_view variant_type_name = "lsd_radix_sort_basic";
78 };
79
81 constexpr std::string_view sort_by_keys_impl_name = "sort_by_keys";
82
83 shamalgs::
84 ImplVariantGlobal<StdSort, BatcherOddEvenHostSerial, BatcherOddEven, LsdRadixSortBasic>
85 sort_by_keys_impl{[](const sham::DeviceScheduler_ptr &dev_sched, auto &self) {
86 if (dev_sched->ctx->device->prop.type == sham::DeviceType::CPU) {
87 self.set(LsdRadixSortBasic{});
88 } else {
89 self.set(StdSort{});
90 }
91 }};
92
93 // Must come after the global it registers: same TU, so it is initialized after it
95
96 } // namespace impl
97
98 template<class Tkey, class Tval>
100 sham::DeviceBuffer<Tkey> &buf_key, sham::DeviceBuffer<Tval> &buf_values, u32 len) {
101
102 if (!impl::sort_by_keys_impl.is_set()) {
105 }
106
107 std::visit(
109 [&](impl::StdSort) {
110 device::details::sort_by_keys_std_sort(buf_key, buf_values, len);
111 },
114 },
117 buf_key.get_dev_scheduler_ptr(), buf_key, buf_values, len);
118 },
120 if constexpr (std::is_unsigned_v<Tkey>) {
122 buf_key.get_dev_scheduler_ptr(), buf_key, buf_values, len);
123 } else {
124 device::details::sort_by_keys_std_sort(buf_key, buf_values, len);
125 }
126 },
127 },
128 impl::sort_by_keys_impl.get());
129 }
130
131 template void sort_by_keys(
132 sham::DeviceBuffer<u32> &buf_key, sham::DeviceBuffer<u32> &buf_values, u32 len);
133
134 template void sort_by_keys(
135 sham::DeviceBuffer<u64> &buf_key, sham::DeviceBuffer<u32> &buf_values, u32 len);
136
137 template void sort_by_keys(
138 sham::DeviceBuffer<f64> &buf_key, sham::DeviceBuffer<f64> &buf_values, u32 len);
139
140 template void sort_by_keys(
141 sham::DeviceBuffer<f32> &buf_key, sham::DeviceBuffer<f32> &buf_values, u32 len);
142
143} // namespace shamalgs::primitives
Generic std::variant-based implementation selector.
std::uint32_t u32
32 bit unsigned integer
Batcher odd-even mergesort, native for any length.
A buffer allocated in USM (Unified Shared Memory).
void copy_from_stdvec(const std::vector< T > &vec)
Copy the content of a std::vector into the buffer.
std::shared_ptr< DeviceScheduler > & get_dev_scheduler_ptr()
Gets the Device scheduler pointer corresponding to the held allocation.
std::vector< T > copy_to_stdvec() const
Copy the content of the buffer to a std::vector.
This header file contains utility functions related to exception handling in the code.
Name-keyed registry of the implementation selectors (IImplVariant) of every algorithm.
#define SHAMALGS_REGISTER_IMPL(name, impl)
Register the implementation selector impl under name at static initialization.
void autoselect_impl(std::string_view alg, const sham::DeviceScheduler_ptr &sched)
Select the default implementation of alg for the device behind sched.
void sort_by_key_batcher_odd_even_host_reference(std::vector< Tkey > &keys, std::vector< Tval > &values)
Host reference of sort_by_key_batcher_odd_even.
void sort_by_key_batcher_odd_even(const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Sort key-value pairs of any length using a Batcher odd-even merge network.
constexpr std::string_view sort_by_keys_impl_name
Registry name, shared by its registration and the dispatch site(s).
namespace for primitive algorithm (e.g. sort, scan, reductions, ...)
void sort_by_keys(sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Sort key-value pairs using USM buffers (general length).
void sort_by_keys_batcher_odd_even_host_serial(sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Sort by keys algorithms.
Portable LSD radix sort by keys, parallelized over chunks of the input.
void sort_by_keys_lsd_radix_sort_basic(const sham::DeviceScheduler_ptr &sched, sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Stable LSD radix sort of (keys, values) on the first len elements (unsigned keys only).
std::sort based sort by keys implementation, shared by the sort by keys primitives
void sort_by_keys_std_sort(sham::DeviceBuffer< Tkey > &buf_key, sham::DeviceBuffer< Tval > &buf_values, u32 len)
Copy both buffers to host, std::sort the zipped key/value pairs, and copy back.
Copy the buffers to host, sort with Batcher's odd-even merge sort, and copy back.
Copy the buffers to host, sort with Batcher's odd-even merge sort, and copy back.
Copy the buffers to host, std::sort the zipped key/value pairs, and copy back.
Build an overload set out of several callables, for use with std::visit.