Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit489dfce

Browse files
committed
Remove reliance on const_trait in sort implementations
const_trait in conjunction with specialization wasdeemed not ready for usage in this scenario. Soinstead a two-stage trait specialization approachis used. This approach is likely worse forcompile-times. Future work that enablesconst_trait can revert back to the previousversion as outlined in the comment markedFIXME(effects).
1 parent83c530f commit489dfce

File tree

2 files changed

+66
-64
lines changed

2 files changed

+66
-64
lines changed

‎core/src/slice/sort/shared/smallsort.rs‎

Lines changed: 63 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -93,10 +93,62 @@ impl<T> UnstableSmallSortTypeImpl for T {
9393
impl<T:FreezeMarker>UnstableSmallSortTypeImplforT{
9494
#[inline(always)]
9595
fnsmall_sort_threshold() ->usize{
96-
matchconst{choose_unstable_small_sort::<T>()}{
97-
UnstableSmallSort::Fallback =>SMALL_SORT_FALLBACK_THRESHOLD,
98-
UnstableSmallSort::General =>SMALL_SORT_GENERAL_THRESHOLD,
99-
UnstableSmallSort::Network =>SMALL_SORT_NETWORK_THRESHOLD,
96+
<TasUnstableSmallSortFreezeTypeImpl>::small_sort_threshold()
97+
}
98+
99+
#[inline(always)]
100+
fnsmall_sort<F>(v:&mut[T],is_less:&mutF)
101+
where
102+
F:FnMut(&T,&T) ->bool,
103+
{
104+
<TasUnstableSmallSortFreezeTypeImpl>::small_sort(v, is_less);
105+
}
106+
}
107+
108+
/// FIXME(effects) use original ipnsort approach with choose_unstable_small_sort,
109+
/// as found here https://github.com/Voultapher/sort-research-rs/blob/438fad5d0495f65d4b72aa87f0b62fc96611dff3/ipnsort/src/smallsort.rs#L83C10-L83C36.
110+
pub(crate)traitUnstableSmallSortFreezeTypeImpl:Sized +FreezeMarker{
111+
fnsmall_sort_threshold() ->usize;
112+
113+
fnsmall_sort<F:FnMut(&Self,&Self) ->bool>(v:&mut[Self],is_less:&mutF);
114+
}
115+
116+
impl<T:FreezeMarker>UnstableSmallSortFreezeTypeImplforT{
117+
#[inline(always)]
118+
defaultfnsmall_sort_threshold() ->usize{
119+
if(mem::size_of::<T>()*SMALL_SORT_GENERAL_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE{
120+
SMALL_SORT_GENERAL_THRESHOLD
121+
}else{
122+
SMALL_SORT_FALLBACK_THRESHOLD
123+
}
124+
}
125+
126+
#[inline(always)]
127+
defaultfnsmall_sort<F>(v:&mut[T],is_less:&mutF)
128+
where
129+
F:FnMut(&T,&T) ->bool,
130+
{
131+
if(mem::size_of::<T>()*SMALL_SORT_GENERAL_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE{
132+
small_sort_general(v, is_less);
133+
}else{
134+
small_sort_fallback(v, is_less);
135+
}
136+
}
137+
}
138+
139+
/// SAFETY: Only used for run-time optimization heuristic.
140+
#[rustc_unsafe_specialization_marker]
141+
traitCopyMarker{}
142+
143+
impl<T:FreezeMarker +CopyMarker>UnstableSmallSortFreezeTypeImplforT{
144+
#[inline(always)]
145+
fnsmall_sort_threshold() ->usize{
146+
ifhas_efficient_in_place_swap::<T>()
147+
&&(mem::size_of::<T>()*SMALL_SORT_NETWORK_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE
148+
{
149+
SMALL_SORT_NETWORK_SCRATCH_LEN
150+
}else{
151+
SMALL_SORT_FALLBACK_THRESHOLD
100152
}
101153
}
102154

@@ -105,9 +157,13 @@ impl<T: FreezeMarker> UnstableSmallSortTypeImpl for T {
105157
where
106158
F:FnMut(&T,&T) ->bool,
107159
{
108-
// This construct is used to limit the LLVM IR generated, which saves large amounts of
109-
// compile-time by only instantiating the code that is needed. Idea by Frank Steffahn.
110-
(const{inst_unstable_small_sort::<T,F>()})(v, is_less);
160+
ifhas_efficient_in_place_swap::<T>()
161+
&&(mem::size_of::<T>()*SMALL_SORT_NETWORK_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE
162+
{
163+
small_sort_network(v, is_less);
164+
}else{
165+
small_sort_fallback(v, is_less);
166+
}
111167
}
112168
}
113169

@@ -137,37 +193,6 @@ const SMALL_SORT_NETWORK_SCRATCH_LEN: usize = SMALL_SORT_NETWORK_THRESHOLD;
137193
/// within this limit.
138194
constMAX_STACK_ARRAY_SIZE:usize =4096;
139195

140-
enumUnstableSmallSort{
141-
Fallback,
142-
General,
143-
Network,
144-
}
145-
146-
constfnchoose_unstable_small_sort<T:FreezeMarker>() ->UnstableSmallSort{
147-
ifT::is_copy()
148-
&&has_efficient_in_place_swap::<T>()
149-
&&(mem::size_of::<T>()*SMALL_SORT_NETWORK_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE
150-
{
151-
// Heuristic for int like types.
152-
returnUnstableSmallSort::Network;
153-
}
154-
155-
if(mem::size_of::<T>()*SMALL_SORT_GENERAL_SCRATCH_LEN) <=MAX_STACK_ARRAY_SIZE{
156-
returnUnstableSmallSort::General;
157-
}
158-
159-
UnstableSmallSort::Fallback
160-
}
161-
162-
constfninst_unstable_small_sort<T:FreezeMarker,F:FnMut(&T,&T) ->bool>()
163-
->fn(&mut[T],&mutF){
164-
matchconst{choose_unstable_small_sort::<T>()}{
165-
UnstableSmallSort::Fallback =>small_sort_fallback::<T,F>,
166-
UnstableSmallSort::General =>small_sort_general::<T,F>,
167-
UnstableSmallSort::Network =>small_sort_network::<T,F>,
168-
}
169-
}
170-
171196
fnsmall_sort_fallback<T,F:FnMut(&T,&T) ->bool>(v:&mut[T],is_less:&mutF){
172197
if v.len() >=2{
173198
insertion_sort_shift_left(v,1, is_less);
@@ -822,25 +847,3 @@ pub(crate) const fn has_efficient_in_place_swap<T>() -> bool {
822847
// Heuristic that holds true on all tested 64-bit capable architectures.
823848
mem::size_of::<T>() <=8// mem::size_of::<u64>()
824849
}
825-
826-
/// SAFETY: Only used for run-time optimization heuristic.
827-
#[rustc_unsafe_specialization_marker]
828-
traitCopyMarker{}
829-
830-
impl<T:Copy>CopyMarkerforT{}
831-
832-
#[const_trait]
833-
traitIsCopy{
834-
fnis_copy() ->bool;
835-
}
836-
837-
impl<T>constIsCopyforT{
838-
defaultfnis_copy() ->bool{
839-
false
840-
}
841-
}
842-
impl<T:CopyMarker>constIsCopyforT{
843-
fnis_copy() ->bool{
844-
true
845-
}
846-
}

‎core/src/slice/sort/stable/quicksort.rs‎

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -233,24 +233,23 @@ impl<T> PartitionState<T> {
233233
}
234234
}
235235

236-
#[const_trait]
237236
traitIsFreeze{
238237
fnis_freeze() ->bool;
239238
}
240239

241-
impl<T>constIsFreezeforT{
240+
impl<T>IsFreezeforT{
242241
defaultfnis_freeze() ->bool{
243242
false
244243
}
245244
}
246-
impl<T:FreezeMarker>constIsFreezeforT{
245+
impl<T:FreezeMarker>IsFreezeforT{
247246
fnis_freeze() ->bool{
248247
true
249248
}
250249
}
251250

252251
#[must_use]
253-
constfnhas_direct_interior_mutability<T>() ->bool{
252+
fnhas_direct_interior_mutability<T>() ->bool{
254253
// If a type has interior mutability it may alter itself during comparison
255254
// in a way that must be preserved after the sort operation concludes.
256255
// Otherwise a type like Mutex<Option<Box<str>>> could lead to double free.

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp