Grok 10.0.0
vqsort.h
Go to the documentation of this file.
1// Copyright 2022 Google LLC
2// SPDX-License-Identifier: Apache-2.0
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8// http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16// Interface to vectorized quicksort with dynamic dispatch.
17// Blog post: https://tinyurl.com/vqsort-blog
18// Paper with measurements: https://arxiv.org/abs/2205.05982
19//
20// To ensure the overhead of using wide vectors (e.g. AVX2 or AVX-512) is
21// worthwhile, we recommend using this code for sorting arrays whose size is at
22// least 512 KiB.
23
24#ifndef HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_
25#define HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_
26
27#include "hwy/base.h"
28
29namespace hwy {
30
31// Tag arguments that determine the sort order.
33 constexpr bool IsAscending() const { return true; }
34};
36 constexpr bool IsAscending() const { return false; }
37};
38
39// Allocates O(1) space. Type-erased RAII wrapper over hwy/aligned_allocator.h.
40// This allows amortizing the allocation over multiple sorts.
42 public:
44 ~Sorter() { Delete(); }
45
46 // Move-only
47 Sorter(const Sorter&) = delete;
48 Sorter& operator=(const Sorter&) = delete;
49 Sorter(Sorter&& other) {
50 Delete();
51 ptr_ = other.ptr_;
52 other.ptr_ = nullptr;
53 }
55 Delete();
56 ptr_ = other.ptr_;
57 other.ptr_ = nullptr;
58 return *this;
59 }
60
61 // Sorts keys[0, n). Dispatches to the best available instruction set,
62 // and does not allocate memory.
63 void operator()(uint16_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
64 void operator()(uint16_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
65 void operator()(uint32_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
66 void operator()(uint32_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
67 void operator()(uint64_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
68 void operator()(uint64_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
69
70 void operator()(int16_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
71 void operator()(int16_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
72 void operator()(int32_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
73 void operator()(int32_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
74 void operator()(int64_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
75 void operator()(int64_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
76
77 void operator()(float* HWY_RESTRICT keys, size_t n, SortAscending) const;
78 void operator()(float* HWY_RESTRICT keys, size_t n, SortDescending) const;
79 void operator()(double* HWY_RESTRICT keys, size_t n, SortAscending) const;
80 void operator()(double* HWY_RESTRICT keys, size_t n, SortDescending) const;
81
82 void operator()(uint128_t* HWY_RESTRICT keys, size_t n, SortAscending) const;
83 void operator()(uint128_t* HWY_RESTRICT keys, size_t n, SortDescending) const;
84
85 void operator()(K64V64* HWY_RESTRICT keys, size_t n, SortAscending) const;
86 void operator()(K64V64* HWY_RESTRICT keys, size_t n, SortDescending) const;
87
88 // For internal use only
89 static void Fill24Bytes(const void* seed_heap, size_t seed_num, void* bytes);
90 static bool HaveFloat64();
91
92 private:
93 void Delete();
94
95 template <typename T>
96 T* Get() const {
97 return static_cast<T*>(ptr_);
98 }
99
100 void* ptr_ = nullptr;
101};
102
103} // namespace hwy
104
105#endif // HIGHWAY_HWY_CONTRIB_SORT_VQSORT_H_
#define HWY_RESTRICT
Definition: base.h:61
Definition: vqsort.h:41
void operator()(double *HWY_RESTRICT keys, size_t n, SortDescending) const
Sorter(const Sorter &)=delete
void operator()(uint16_t *HWY_RESTRICT keys, size_t n, SortAscending) const
static bool HaveFloat64()
void operator()(uint32_t *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(int32_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(uint16_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(K64V64 *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(float *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(int64_t *HWY_RESTRICT keys, size_t n, SortDescending) const
T * Get() const
Definition: vqsort.h:96
void operator()(uint128_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(uint32_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(uint64_t *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(uint128_t *HWY_RESTRICT keys, size_t n, SortAscending) const
void Delete()
void operator()(double *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(K64V64 *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(int32_t *HWY_RESTRICT keys, size_t n, SortAscending) const
void operator()(uint64_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(int64_t *HWY_RESTRICT keys, size_t n, SortAscending) const
Sorter & operator=(Sorter &&other)
Definition: vqsort.h:54
static void Fill24Bytes(const void *seed_heap, size_t seed_num, void *bytes)
void operator()(int16_t *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(float *HWY_RESTRICT keys, size_t n, SortDescending) const
void operator()(int16_t *HWY_RESTRICT keys, size_t n, SortAscending) const
Sorter(Sorter &&other)
Definition: vqsort.h:49
Sorter & operator=(const Sorter &)=delete
~Sorter()
Definition: vqsort.h:44
#define HWY_CONTRIB_DLLEXPORT
Definition: highway_export.h:14
Definition: aligned_allocator.h:27
Definition: base.h:271
Definition: vqsort.h:32
constexpr bool IsAscending() const
Definition: vqsort.h:33
Definition: vqsort.h:35
constexpr bool IsAscending() const
Definition: vqsort.h:36
Definition: base.h:264