ENH: Enable SVE detection for Highway VQSort by Mousius · Pull Request #25247 · numpy/numpy

Mousius · 2023-11-24T14:03:56Z

Leveraging the meson infrastructure to selectively enable SVE specifically for Highway, which already supports SVE.

| Change   | Before [94bc5640] <main>   | After [1ffedb85] <sve-sort>   |   Ratio | Benchmark (Parameter)                                                            |
|----------|----------------------------|-------------------------------|---------|----------------------------------------------------------------------------------|
| +        | 551±0.8μs                  | 654±5μs                       |    1.19 | bench_function_base.Sort.time_sort('merge', 'float32', ('random',))              |
| +        | 72.9±0.1μs                 | 80.5±0.08μs                   |    1.11 | bench_function_base.Sort.time_argsort('quick', 'float32', ('ordered',))          |
| +        | 553±1μs                    | 606±2μs                       |    1.1  | bench_function_base.Sort.time_sort('merge', 'float64', ('random',))              |
| +        | 41.9±0.3μs                 | 45.6±0.04μs                   |    1.09 | bench_function_base.Sort.time_argsort('merge', 'int32', ('sorted_block', 1000))  |
| +        | 493±1μs                    | 532±2μs                       |    1.08 | bench_function_base.Sort.time_sort('merge', 'float16', ('random',))              |
| +        | 73.7±0.2μs                 | 78.8±0.04μs                   |    1.07 | bench_function_base.Sort.time_argsort('merge', 'int32', ('sorted_block', 100))   |
| +        | 565±1μs                    | 600±1μs                       |    1.06 | bench_function_base.Sort.time_argsort('heap', 'float64', ('ordered',))           |
| +        | 465±1μs                    | 491±1μs                       |    1.06 | bench_function_base.Sort.time_argsort('heap', 'int32', ('reversed',))            |
| +        | 696±3μs                    | 739±2μs                       |    1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('random',))               |
| +        | 645±3μs                    | 684±3μs                       |    1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 10))      |
| +        | 651±1μs                    | 691±1μs                       |    1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 100))     |
| +        | 627±3μs                    | 665±1μs                       |    1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 1000))    |
| +        | 467±1μs                    | 494±0.7μs                     |    1.06 | bench_function_base.Sort.time_sort('heap', 'float32', ('ordered',))              |
| +        | 166±0.1μs                  | 174±1μs                       |    1.05 | bench_function_base.Sort.time_sort('merge', 'float32', ('sorted_block', 10))     |
| -        | 77.4±0.08μs                | 73.2±0.2μs                    |    0.95 | bench_function_base.Sort.time_argsort('merge', 'uint32', ('sorted_block', 100))  |
| -        | 379±1μs                    | 359±0.1μs                     |    0.95 | bench_function_base.Sort.time_sort('heap', 'int32', ('ordered',))                |
| -        | 341±0.5μs                  | 324±0.5μs                     |    0.95 | bench_function_base.Sort.time_sort('quick', 'float16', ('sorted_block', 1000))   |
| -        | 590±0.5μs                  | 554±1μs                       |    0.94 | bench_function_base.Sort.time_argsort('heap', 'float32', ('ordered',))           |
| -        | 239±5μs                    | 226±0.6μs                     |    0.94 | bench_function_base.Sort.time_argsort('merge', 'float16', ('sorted_block', 10))  |
| -        | 195±2μs                    | 184±1μs                       |    0.94 | bench_function_base.Sort.time_argsort('merge', 'float32', ('sorted_block', 10))  |
| -        | 692±2μs                    | 637±2μs                       |    0.92 | bench_function_base.Sort.time_argsort('merge', 'float32', ('random',))           |
| -        | 45.5±0.03μs                | 42.0±0.2μs                    |    0.92 | bench_function_base.Sort.time_argsort('merge', 'uint32', ('sorted_block', 1000)) |
| -        | 80.5±0.07μs                | 73.0±0.1μs                    |    0.91 | bench_function_base.Sort.time_argsort('quick', 'float64', ('ordered',))          |
| -        | 78.9±0.2μs                 | 71.7±0.2μs                    |    0.91 | bench_function_base.Sort.time_sort('quick', 'uint32', ('ordered',))              |
| -        | 79.2±0.1μs                 | 72.1±0.2μs                    |    0.91 | bench_function_base.Sort.time_sort('quick', 'uint32', ('reversed',))             |
| -        | 131±2μs                    | 118±0.8μs                     |    0.9  | bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 100))    |
| -        | 82.8±0.2μs                 | 73.7±0.3μs                    |    0.89 | bench_function_base.Sort.time_sort('quick', 'float32', ('ordered',))             |
| -        | 83.4±0.07μs                | 74.1±0.2μs                    |    0.89 | bench_function_base.Sort.time_sort('quick', 'float32', ('reversed',))            |
| -        | 78.6±0.2μs                 | 70.3±0.2μs                    |    0.89 | bench_function_base.Sort.time_sort('quick', 'int32', ('ordered',))               |
| -        | 79.2±0.09μs                | 70.8±0.08μs                   |    0.89 | bench_function_base.Sort.time_sort('quick', 'int32', ('reversed',))              |
| -        | 3.22±0.02μs                | 2.86±0μs                      |    0.89 | bench_function_base.Sort.time_sort('quick', 'uint32', ('uniform',))              |
| -        | 3.26±0.04μs                | 2.84±0μs                      |    0.87 | bench_function_base.Sort.time_sort('quick', 'int32', ('uniform',))               |
| -        | 82.6±0.06μs                | 71.1±0.08μs                   |    0.86 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 10))     |
| -        | 4.91±0.01μs                | 4.22±0μs                      |    0.86 | bench_function_base.Sort.time_sort('quick', 'int64', ('uniform',))               |
| -        | 79.0±0.2μs                 | 66.8±0.05μs                   |    0.85 | bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 1000))   |
| -        | 78.8±0.05μs                | 67.0±0.2μs                    |    0.85 | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 10))      |
| -        | 84.2±0.07μs                | 70.8±0.1μs                    |    0.84 | bench_function_base.Sort.time_sort('quick', 'float32', ('random',))              |
| -        | 89.4±0.1μs                 | 75.5±0.05μs                   |    0.84 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 1000))   |
| -        | 78.9±0.04μs                | 65.9±0.1μs                    |    0.84 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 10))       |
| -        | 85.4±0.06μs                | 71.9±0.05μs                   |    0.84 | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 1000))    |
| -        | 85.3±0.08μs                | 70.5±0.1μs                    |    0.83 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 1000))     |
| -        | 80.5±0.03μs                | 66.4±0.1μs                    |    0.83 | bench_function_base.Sort.time_sort('quick', 'uint32', ('random',))               |
| -        | 87.5±0.05μs                | 71.6±0.1μs                    |    0.82 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 100))    |
| -        | 80.4±0.05μs                | 65.4±0.07μs                   |    0.81 | bench_function_base.Sort.time_sort('quick', 'int32', ('random',))                |
| -        | 83.6±0.05μs                | 66.9±0.1μs                    |    0.8  | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 100))     |
| -        | 83.5±0.05μs                | 65.8±0.08μs                   |    0.79 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 100))      |
| -        | 6.87±0.01μs                | 5.13±0.08μs                   |    0.75 | bench_function_base.Sort.time_sort('quick', 'float32', ('uniform',))             |
| -        | 12.2±0.02μs                | 8.79±0.1μs                    |    0.72 | bench_function_base.Sort.time_sort('quick', 'float64', ('uniform',))             |
| -        | 193±0.5μs                  | 124±0.5μs                     |    0.65 | bench_function_base.Sort.time_sort('quick', 'float64', ('reversed',))            |
| -        | 27.7±0.2ms                 | 18.0±0.2ms                    |    0.65 | bench_function_base.Sort.time_sort_worst                                         |
| -        | 192±0.4μs                  | 123±0.2μs                     |    0.64 | bench_function_base.Sort.time_sort('quick', 'float64', ('ordered',))             |
| -        | 202±0.2μs                  | 128±0.04μs                    |    0.63 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 1000))   |
| -        | 203±0.5μs                  | 125±0.09μs                    |    0.62 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 100))    |
| -        | 199±0.4μs                  | 122±0.07μs                    |    0.61 | bench_function_base.Sort.time_sort('quick', 'float64', ('random',))              |
| -        | 195±0.4μs                  | 120±0.09μs                    |    0.61 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 10))     |
| -        | 215±0.3μs                  | 121±0.3μs                     |    0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('ordered',))               |
| -        | 216±0.3μs                  | 121±0.7μs                     |    0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('reversed',))              |
| -        | 225±0.3μs                  | 126±0.3μs                     |    0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 1000))     |
| -        | 223±0.2μs                  | 119±0.09μs                    |    0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('random',))                |
| -        | 219±0.06μs                 | 118±0.08μs                    |    0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 10))       |
| -        | 227±0.3μs                  | 123±0.2μs                     |    0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 100))      |

Mousius · 2023-11-24T14:06:47Z

@rdevulap don't panic; this was just so easy to do that I wanted to see if it would work 😸 I'll wait for your patches to be in and rebase on top of them.

@seiko2plus SVE features! Woo!

seiko2plus

LGTM, Thank you. Just a few changes more.

meson_cpu/arm/meson.build

numpy/_core/src/common/npy_cpu_features.c

numpy/_core/tests/test_cpu_features.py

seiko2plus · 2023-11-29T17:49:01Z

this was just so easy to do that I wanted to see if it would work 😸 I'll wait for your patches to be in and rebase on top of them.

This pr doesn't change any C/C++ code so it should be fine to merge it.

Mousius · 2023-11-29T17:54:08Z

this was just so easy to do that I wanted to see if it would work 😸 I'll wait for your patches to be in and rebase on top of them.

This pr doesn't change any C/C++ code so it should be fine to merge it.

This will conflict with https://github.com/numpy/numpy/pull/25045/files#diff-1df2f2cfde074ed7de97ebae8a7ef48ad000241256ea3f480f81b2598d03b4f8R784-R788

Leveraging the meson infrastructure to selectively enable SVE specifically for Highway, which already supports SVE. ``` | Change | Before [94bc564] <main> | After [1ffedb85] <sve-sort> | Ratio | Benchmark (Parameter) | |----------|----------------------------|-------------------------------|---------|----------------------------------------------------------------------------------| | + | 551±0.8μs | 654±5μs | 1.19 | bench_function_base.Sort.time_sort('merge', 'float32', ('random',)) | | + | 72.9±0.1μs | 80.5±0.08μs | 1.11 | bench_function_base.Sort.time_argsort('quick', 'float32', ('ordered',)) | | + | 553±1μs | 606±2μs | 1.1 | bench_function_base.Sort.time_sort('merge', 'float64', ('random',)) | | + | 41.9±0.3μs | 45.6±0.04μs | 1.09 | bench_function_base.Sort.time_argsort('merge', 'int32', ('sorted_block', 1000)) | | + | 493±1μs | 532±2μs | 1.08 | bench_function_base.Sort.time_sort('merge', 'float16', ('random',)) | | + | 73.7±0.2μs | 78.8±0.04μs | 1.07 | bench_function_base.Sort.time_argsort('merge', 'int32', ('sorted_block', 100)) | | + | 565±1μs | 600±1μs | 1.06 | bench_function_base.Sort.time_argsort('heap', 'float64', ('ordered',)) | | + | 465±1μs | 491±1μs | 1.06 | bench_function_base.Sort.time_argsort('heap', 'int32', ('reversed',)) | | + | 696±3μs | 739±2μs | 1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('random',)) | | + | 645±3μs | 684±3μs | 1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 10)) | | + | 651±1μs | 691±1μs | 1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 100)) | | + | 627±3μs | 665±1μs | 1.06 | bench_function_base.Sort.time_sort('heap', 'float16', ('sorted_block', 1000)) | | + | 467±1μs | 494±0.7μs | 1.06 | bench_function_base.Sort.time_sort('heap', 'float32', ('ordered',)) | | + | 166±0.1μs | 174±1μs | 1.05 | bench_function_base.Sort.time_sort('merge', 'float32', ('sorted_block', 10)) | | - | 77.4±0.08μs | 73.2±0.2μs | 0.95 | bench_function_base.Sort.time_argsort('merge', 'uint32', ('sorted_block', 100)) | | - | 379±1μs | 359±0.1μs | 0.95 | bench_function_base.Sort.time_sort('heap', 'int32', ('ordered',)) | | - | 341±0.5μs | 324±0.5μs | 0.95 | bench_function_base.Sort.time_sort('quick', 'float16', ('sorted_block', 1000)) | | - | 590±0.5μs | 554±1μs | 0.94 | bench_function_base.Sort.time_argsort('heap', 'float32', ('ordered',)) | | - | 239±5μs | 226±0.6μs | 0.94 | bench_function_base.Sort.time_argsort('merge', 'float16', ('sorted_block', 10)) | | - | 195±2μs | 184±1μs | 0.94 | bench_function_base.Sort.time_argsort('merge', 'float32', ('sorted_block', 10)) | | - | 692±2μs | 637±2μs | 0.92 | bench_function_base.Sort.time_argsort('merge', 'float32', ('random',)) | | - | 45.5±0.03μs | 42.0±0.2μs | 0.92 | bench_function_base.Sort.time_argsort('merge', 'uint32', ('sorted_block', 1000)) | | - | 80.5±0.07μs | 73.0±0.1μs | 0.91 | bench_function_base.Sort.time_argsort('quick', 'float64', ('ordered',)) | | - | 78.9±0.2μs | 71.7±0.2μs | 0.91 | bench_function_base.Sort.time_sort('quick', 'uint32', ('ordered',)) | | - | 79.2±0.1μs | 72.1±0.2μs | 0.91 | bench_function_base.Sort.time_sort('quick', 'uint32', ('reversed',)) | | - | 131±2μs | 118±0.8μs | 0.9 | bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 100)) | | - | 82.8±0.2μs | 73.7±0.3μs | 0.89 | bench_function_base.Sort.time_sort('quick', 'float32', ('ordered',)) | | - | 83.4±0.07μs | 74.1±0.2μs | 0.89 | bench_function_base.Sort.time_sort('quick', 'float32', ('reversed',)) | | - | 78.6±0.2μs | 70.3±0.2μs | 0.89 | bench_function_base.Sort.time_sort('quick', 'int32', ('ordered',)) | | - | 79.2±0.09μs | 70.8±0.08μs | 0.89 | bench_function_base.Sort.time_sort('quick', 'int32', ('reversed',)) | | - | 3.22±0.02μs | 2.86±0μs | 0.89 | bench_function_base.Sort.time_sort('quick', 'uint32', ('uniform',)) | | - | 3.26±0.04μs | 2.84±0μs | 0.87 | bench_function_base.Sort.time_sort('quick', 'int32', ('uniform',)) | | - | 82.6±0.06μs | 71.1±0.08μs | 0.86 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 10)) | | - | 4.91±0.01μs | 4.22±0μs | 0.86 | bench_function_base.Sort.time_sort('quick', 'int64', ('uniform',)) | | - | 79.0±0.2μs | 66.8±0.05μs | 0.85 | bench_function_base.Sort.time_sort('merge', 'float16', ('sorted_block', 1000)) | | - | 78.8±0.05μs | 67.0±0.2μs | 0.85 | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 10)) | | - | 84.2±0.07μs | 70.8±0.1μs | 0.84 | bench_function_base.Sort.time_sort('quick', 'float32', ('random',)) | | - | 89.4±0.1μs | 75.5±0.05μs | 0.84 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 1000)) | | - | 78.9±0.04μs | 65.9±0.1μs | 0.84 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 10)) | | - | 85.4±0.06μs | 71.9±0.05μs | 0.84 | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 1000)) | | - | 85.3±0.08μs | 70.5±0.1μs | 0.83 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 1000)) | | - | 80.5±0.03μs | 66.4±0.1μs | 0.83 | bench_function_base.Sort.time_sort('quick', 'uint32', ('random',)) | | - | 87.5±0.05μs | 71.6±0.1μs | 0.82 | bench_function_base.Sort.time_sort('quick', 'float32', ('sorted_block', 100)) | | - | 80.4±0.05μs | 65.4±0.07μs | 0.81 | bench_function_base.Sort.time_sort('quick', 'int32', ('random',)) | | - | 83.6±0.05μs | 66.9±0.1μs | 0.8 | bench_function_base.Sort.time_sort('quick', 'uint32', ('sorted_block', 100)) | | - | 83.5±0.05μs | 65.8±0.08μs | 0.79 | bench_function_base.Sort.time_sort('quick', 'int32', ('sorted_block', 100)) | | - | 6.87±0.01μs | 5.13±0.08μs | 0.75 | bench_function_base.Sort.time_sort('quick', 'float32', ('uniform',)) | | - | 12.2±0.02μs | 8.79±0.1μs | 0.72 | bench_function_base.Sort.time_sort('quick', 'float64', ('uniform',)) | | - | 193±0.5μs | 124±0.5μs | 0.65 | bench_function_base.Sort.time_sort('quick', 'float64', ('reversed',)) | | - | 27.7±0.2ms | 18.0±0.2ms | 0.65 | bench_function_base.Sort.time_sort_worst | | - | 192±0.4μs | 123±0.2μs | 0.64 | bench_function_base.Sort.time_sort('quick', 'float64', ('ordered',)) | | - | 202±0.2μs | 128±0.04μs | 0.63 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 1000)) | | - | 203±0.5μs | 125±0.09μs | 0.62 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 100)) | | - | 199±0.4μs | 122±0.07μs | 0.61 | bench_function_base.Sort.time_sort('quick', 'float64', ('random',)) | | - | 195±0.4μs | 120±0.09μs | 0.61 | bench_function_base.Sort.time_sort('quick', 'float64', ('sorted_block', 10)) | | - | 215±0.3μs | 121±0.3μs | 0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('ordered',)) | | - | 216±0.3μs | 121±0.7μs | 0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('reversed',)) | | - | 225±0.3μs | 126±0.3μs | 0.56 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 1000)) | | - | 223±0.2μs | 119±0.09μs | 0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('random',)) | | - | 219±0.06μs | 118±0.08μs | 0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 10)) | | - | 227±0.3μs | 123±0.2μs | 0.54 | bench_function_base.Sort.time_sort('quick', 'int64', ('sorted_block', 100)) | ```

Mousius · 2023-12-08T14:37:20Z

@seiko2plus I've rebased this on top of @rdevulap's changes, I think this is good to go?

seiko2plus

LGTM, Thank you!

github-actions bot added the 01 - Enhancement label Nov 24, 2023

Mousius force-pushed the highway-vqsort-sve branch from 0d56dbb to 20b5f2d Compare November 24, 2023 14:40

seiko2plus requested changes Nov 29, 2023

View reviewed changes

meson_cpu/arm/meson.build Outdated Show resolved Hide resolved

numpy/_core/src/common/npy_cpu_features.c Show resolved Hide resolved

seiko2plus reviewed Nov 29, 2023

View reviewed changes

numpy/_core/tests/test_cpu_features.py Outdated Show resolved Hide resolved

Mousius force-pushed the highway-vqsort-sve branch from 4c05be1 to 027cce0 Compare November 29, 2023 17:53

Mousius force-pushed the highway-vqsort-sve branch from 027cce0 to f0b936d Compare November 29, 2023 18:09

Mousius added 2 commits December 8, 2023 13:40

Add test and link SVE to ASIMDHP

682d33c

Mousius force-pushed the highway-vqsort-sve branch from f0b936d to 682d33c Compare December 8, 2023 13:42

seiko2plus approved these changes Dec 11, 2023

View reviewed changes

seiko2plus merged commit 0be4154 into numpy:main Dec 11, 2023

This was referenced Dec 14, 2023

ENH: Enable 16-bit VQSort routines on AArch64 #25346

Merged

BUG, SIMD: Fix quicksort build error when Highway/SVE is enabled #25397

Merged

rgommers mentioned this pull request Dec 22, 2023

BUG: crashes in sort/argsort on macOS arm64 #25464

Closed

Mousius mentioned this pull request Jan 8, 2026

ENH, SIMD: Add CPU feature detection and simd functions for AArch64 SVE #22265

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Comments

ENH: Enable SVE detection for Highway VQSort#25247

ENH: Enable SVE detection for Highway VQSort#25247
seiko2plus merged 2 commits intonumpy:mainfrom
Mousius:highway-vqsort-sve

Mousius commented Nov 24, 2023

Uh oh!

Mousius commented Nov 24, 2023

Uh oh!

seiko2plus left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

seiko2plus commented Nov 29, 2023

Uh oh!

Mousius commented Nov 29, 2023

Uh oh!

Mousius commented Dec 8, 2023

Uh oh!

seiko2plus left a comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Uh oh!

Comments

Conversation

Mousius commented Nov 24, 2023

Uh oh!

Mousius commented Nov 24, 2023

Uh oh!

seiko2plus left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

seiko2plus commented Nov 29, 2023

Uh oh!

Mousius commented Nov 29, 2023

Uh oh!

Mousius commented Dec 8, 2023

Uh oh!

seiko2plus left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants