Skip to content

ENH: Use AVX512 FP16 ISA for sorting float16 arrays#23435

Merged
mattip merged 2 commits into
numpy:mainfrom
r-devulap:spr-simd-sort
May 4, 2023
Merged

ENH: Use AVX512 FP16 ISA for sorting float16 arrays#23435
mattip merged 2 commits into
numpy:mainfrom
r-devulap:spr-simd-sort

Conversation

@r-devulap

@r-devulap r-devulap commented Mar 22, 2023

Copy link
Copy Markdown
Member

Leverages AVX512 FP16 simd sort from x86-simd-sort to speed up sorting float16 arrays by nearly 3x.

       before           after         ratio
     [094416f7]       [9d1ef15e]
     <main>           <spr-simd-sort>
+     7.67±0.02μs      12.7±0.01μs     1.66  bench_function_base.Sort.time_sort('merge', 'int16', ('uniform',))
+     7.67±0.02μs      12.7±0.02μs     1.66  bench_function_base.Sort.time_sort('merge', 'int16', ('ordered',))
+      42.5±0.1μs       69.2±0.3μs     1.63  bench_function_base.Sort.time_sort('merge', 'uint32', ('sorted_block', 1000))
+     42.5±0.07μs       69.1±0.7μs     1.63  bench_function_base.Sort.time_sort('merge', 'int32', ('sorted_block', 1000))
+      78.5±0.3μs          128±1μs     1.62  bench_function_base.Sort.time_sort('merge', 'int32', ('sorted_block', 100))
+      78.6±0.2μs        125±0.5μs     1.60  bench_function_base.Sort.time_sort('merge', 'uint32', ('sorted_block', 100))
+       102±0.5μs          150±2μs     1.47  bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 1000))
+     8.53±0.02μs       12.1±0.1μs     1.42  bench_function_base.Sort.time_sort('merge', 'uint32', ('uniform',))
+     8.54±0.02μs       12.0±0.3μs     1.41  bench_function_base.Sort.time_sort('merge', 'uint32', ('ordered',))
+     18.1±0.03μs      23.7±0.06μs     1.31  bench_function_base.Sort.time_sort('merge', 'float64', ('uniform',))
+     18.1±0.01μs      23.6±0.05μs     1.30  bench_function_base.Sort.time_sort('merge', 'float64', ('ordered',))
+       142±0.1μs        173±0.3μs     1.22  bench_function_base.Sort.time_sort('merge', 'uint32', ('sorted_block', 10))
+       141±0.3μs        172±0.5μs     1.21  bench_function_base.Sort.time_sort('merge', 'int32', ('sorted_block', 10))
+     8.54±0.03μs       10.3±0.6μs     1.21  bench_function_base.Sort.time_sort('merge', 'int32', ('ordered',))
+     8.53±0.05μs       10.3±0.5μs     1.20  bench_function_base.Sort.time_sort('merge', 'int32', ('uniform',))
+      30.5±0.1μs       35.9±0.5μs     1.18  bench_function_base.Sort.time_sort('heap', 'int32', ('uniform',))
+         174±1μs          199±2μs     1.14  bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 100))
+       125±0.9μs        142±0.4μs     1.13  bench_function_base.Sort.time_sort('merge', 'float64', ('sorted_block', 100))
+       124±0.1μs        140±0.3μs     1.13  bench_function_base.Sort.time_sort('merge', 'float32', ('sorted_block', 100))
+       186±0.2μs        209±0.7μs     1.12  bench_function_base.Sort.time_sort('merge', 'float32', ('sorted_block', 10))
+      71.0±0.1μs       79.5±0.1μs     1.12  bench_function_base.Sort.time_sort('merge', 'float32', ('sorted_block', 1000))
+     73.0±0.07μs       79.5±0.4μs     1.09  bench_function_base.Sort.time_sort('merge', 'float64', ('sorted_block', 1000))
+     29.8±0.05μs       31.6±0.3μs     1.06  bench_function_base.Sort.time_sort('heap', 'uint32', ('uniform',))
+       720±0.9μs          765±6μs     1.06  bench_function_base.Sort.time_sort('heap', 'int32', ('reversed',))
+         869±3μs          921±6μs     1.06  bench_function_base.Sort.time_sort('merge', 'float64', ('random',))
+         314±3μs          332±2μs     1.06  bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 10))
+      19.4±0.1μs       20.5±0.2μs     1.05  bench_function_base.Sort.time_sort('merge', 'float64', ('reversed',))
+         971±4μs         1.02±0ms     1.05  bench_function_base.Sort.time_sort('heap', 'int16', ('sorted_block', 100))
+        1.09±0ms      1.15±0.01ms     1.05  bench_function_base.Sort.time_sort('heap', 'float64', ('sorted_block', 1000))
-         860±2μs          819±2μs     0.95  bench_function_base.Sort.time_sort('heap', 'float64', ('ordered',))
-         977±4μs          924±2μs     0.95  bench_function_base.Sort.time_sort('heap', 'int64', ('sorted_block', 1000))
-      18.0±0.7μs      16.9±0.05μs     0.94  bench_function_base.Sort.time_sort('merge', 'float32', ('reversed',))
-        70.3±2μs       65.3±0.2μs     0.93  bench_function_base.Sort.time_sort('heap', 'float16', ('uniform',))
-      18.1±0.3μs      16.8±0.07μs     0.93  bench_function_base.Sort.time_sort('merge', 'float32', ('uniform',))
-      18.1±0.1μs       16.7±0.1μs     0.92  bench_function_base.Sort.time_sort('merge', 'float32', ('ordered',))
-         943±4μs          869±5μs     0.92  bench_function_base.Sort.time_sort('merge', 'float32', ('random',))
-      36.4±0.5μs       32.4±0.2μs     0.89  bench_function_base.Sort.time_sort('heap', 'int16', ('uniform',))
-      55.4±0.4μs      48.2±0.02μs     0.87  bench_function_base.Sort.time_sort('merge', 'int64', ('sorted_block', 1000))
-      99.3±0.1μs       84.7±0.2μs     0.85  bench_function_base.Sort.time_sort('merge', 'int64', ('sorted_block', 100))
-      38.1±0.1μs       30.7±0.1μs     0.81  bench_function_base.Sort.time_sort('heap', 'int64', ('uniform',))
-         187±7μs        148±0.2μs     0.79  bench_function_base.Sort.time_sort('merge', 'int64', ('sorted_block', 10))
-     9.09±0.05μs      6.37±0.07μs     0.70  bench_function_base.Sort.time_sort('quick', 'float16', ('uniform',))
-     9.20±0.05μs      6.32±0.05μs     0.69  bench_function_base.Sort.time_sort('quick', 'float16', ('reversed',))
-       164±0.3μs      61.9±0.07μs     0.38  bench_function_base.Sort.time_sort('quick', 'float16', ('sorted_block', 100))
-       172±0.2μs      63.9±0.05μs     0.37  bench_function_base.Sort.time_sort('quick', 'float16', ('sorted_block', 1000))
-        170±0.2μs      63.2±0.02μs     0.37  bench_function_base.Sort.time_sort('quick', 'float16', ('sorted_block', 10))
-       169±0.4μs      62.7±0.05μs     0.37  bench_function_base.Sort.time_sort('quick', 'float16', ('random',))
-       180±0.2μs      65.8±0.08μs     0.37  bench_function_base.Sort.time_sort('quick', 'float16', ('ordered',))

@r-devulap

r-devulap commented Mar 22, 2023

Copy link
Copy Markdown
Member Author

I am not able to explain why we see perf changes to merge sort. Any ideas?

@charris

charris commented Mar 22, 2023

Copy link
Copy Markdown
Member

Any ideas?

Hmm, might be compiler optimizations. Merge sort can actually be faster than quicksort when optimized. OTOH, I believe merge sort is now Timsort or radix sort (for small integers). Note that any replacement for merge sort needs to be a stable sort.

Might be worth profiling the code or changing the optimization level to see what effect that has.

@r-devulap

r-devulap commented Mar 23, 2023

Copy link
Copy Markdown
Member Author

Hmm, might be compiler optimizations. Merge sort can actually be faster than quicksort when optimized. OTOH, I believe merge sort is now Timsort or radix sort (for small integers). Note that any replacement for merge sort needs to be a stable sort.

This patch only adds vectorized quicksort. The code paths don't seem to interfere with other sorts and so I didn't expect it to affect performance of merge and heap sort. Is that assumption correct?

@seberg

seberg commented Mar 23, 2023

Copy link
Copy Markdown
Member

We sometimes see strange fluctuations. I have never quite figured out why unfortunately. malloc behavior might be involved, but seems weird. Compiler optimization just doing different choices also...

Python has a whole story of having to enable profiling guided optimization to avoid fluctations, although they are in a somewhat different boat since they probaly look more at small overheads than a single core function being optimized differently.

@Mousius Mousius mentioned this pull request Mar 28, 2023
Merged
@r-devulap r-devulap mentioned this pull request Mar 28, 2023
Merged
@mattip

mattip commented Mar 29, 2023

Copy link
Copy Markdown
Member

What happens when not using g++-12?

@r-devulap

r-devulap commented Mar 29, 2023

Copy link
Copy Markdown
Member Author

What happens when not using g++-12?

without gcc >= 12.x, this patch is essentially ignored and produces identical library as the main branch. Confirmed that it causes NO changes in benchmarks.

@mattip

mattip commented Mar 29, 2023

Copy link
Copy Markdown
Member

Hmm. So we would need to add a CI run with gcc 12+ to make sure this code continues to function?

@r-devulap

r-devulap commented Mar 29, 2023

Copy link
Copy Markdown
Member Author

Hmm. So we would need to add a CI run with gcc 12+ to make sure this code continues to function?

yup yup, I'm working on it.

@r-devulap

r-devulap commented Mar 29, 2023 •
edited
Loading

Copy link
Copy Markdown
Member Author

Hmm. So we would need to add a CI run with gcc 12+ to make sure this code continues to function?

Would also need to run on Intel SDE with Sapphire Rapids option.

@r-devulap r-devulap mentioned this pull request Mar 30, 2023
Merged
@r-devulap

r-devulap commented Mar 30, 2023

Copy link
Copy Markdown
Member Author

WIll rebase after we merge #23502

@r-devulap

r-devulap commented Apr 5, 2023

Copy link
Copy Markdown
Member Author

rebased.

@mattip

mattip commented Apr 7, 2023

Copy link
Copy Markdown
Member

without g++12: confirmed that it causes NO changes in benchmarks.

Great. Do the regressions in merge sort still occur?

@r-devulap r-devulap mentioned this pull request Apr 28, 2023
Merged
@r-devulap

r-devulap commented May 1, 2023

Copy link
Copy Markdown
Member Author

@mattip Looks like it, spent a lot of time narrowing down why code placement is affecting performance but to no avail :(

@mattip mattip added the triage review Issue/PR to be discussed at the next triage meeting label May 2, 2023
@mattip

mattip commented May 2, 2023

Copy link
Copy Markdown
Member

Marking for discussion at an upcoming triage meeting for the performance slowdown on unrelated code.

@InessaPawson InessaPawson added triaged Issue/PR that was discussed in a triage meeting and removed triage review Issue/PR to be discussed at the next triage meeting labels May 3, 2023
seiko2plus
seiko2plus approved these changes May 3, 2023
View reviewed changes

@seiko2plus seiko2plus left a comment

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM, Thank you!. since this pull-requests only targets Intel Sapphire Rapids and no way to verify it by me or the team due to the lk of hardware, I think its fine to go with the current benchmark even with the understandable downgrades as we discussed on the latest triage meeting.

@mattip mattip merged commit 9163e93 into numpy:main May 4, 2023
@mattip

mattip commented May 4, 2023

Copy link
Copy Markdown
Member

Thanks @r-devulap

@seiko2plus seiko2plus mentioned this pull request May 4, 2023
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@seiko2plus seiko2plus seiko2plus approved these changes

Assignees

No one assigned

Labels

01 - Enhancement triaged Issue/PR that was discussed in a triage meeting

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@r-devulap @charris @seberg @mattip @seiko2plus @InessaPawson