Advanced SIMD Algorithms in Pictures

Advanced SIMD algorithms in pictures

Denis Yaroshevskiy

This talk

https://tinyurl.com/dymeetcpp2023
memcmp
copy_if
set_intersection
sort

memcmp

eve library

github
Joel Falcou, Jean-Thierry Lapresté, Denis Yaroshevskiy
SIMD in C++20: EVE of a new Era
eve::algo::mismatch

Vector Processor Extensions

x86

128 bits: SSE2, SSE3, SSSE3, SSE4, SSE4.1, SSE4.2
256 bits: AVX, AVX2, XOP
512 bits: AVX512 and its myriad of sub-genre

ARM

128 bits: NEON, ASIMD
SVE (VLS/VLA)

PowerPC
WASM

What's inside mismatch?

find_if + zip

mismatch from scratch

copy_if

compress_copy (pure simd)

compress instructions (avx512, sve)
tiny lookup tables (@aqrit)
bmi2 (Peter Cordes)
switch + shuffle (@Z boson)

compress_copy (simd/scalar)

Peter Cordes, Ilya Albrecht

set_intersection

set intersection (simd/simd)

Faster-Than-Native Alternatives for x86 VP2INTERSECT Instructions
Guillermo Diez-Canas

sort

Previous work (0)

2010 Seven Degrees Of Freedom A Question of Sorts
2014 Kyle Hegeman (@khegeman) floki
2018 Bérenger Bramas: A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake: arXiv:1704.08579
2020 Dan Shechter (damageboy) This goes to 11

Previous work (1)

2021 Bérenger Bramas: A fast vectorized sorting implementation based on the ARM scalable vector extension
2022 Mark Blacher, Joachim Giesen, Peter Sanders, Jan Wassenberg Google's Vectorized and performance-portable Quicksort (arXiv:2205.05982)
2023 Raghuveer Devulapalli and others (Intel) x86-simd-sort

sort(wide)

2010 Seven Degrees Of Freedom A Question of Sorts

sort(wide)

sorting networks
bitonic sort

Quick Sort (components)

pivot selection
partition
insertion sort

Pivot Selection

2023 Raghuveer Devulapalli and others (Intel) x86-simd-sort

Partition

2020 Dan Shechter (damageboy) This goes to 11

~sort

Thanks

Joel Falcou, Jean-Thierry Lapresté
Amazing people mentioned

Links