Google modern mimarilerde çalışan ilk vektörleştirilmiş Quicksort algoritmasını yayımladı

Google araştırmacıları, C++ standart kütüphanesindeki std::sort işlevinden yaklaşık 10 kat daha hızlı çalışan ve farklı işlemci mimarilerine taşınabilen ilk vektörleştirilmiş Quicksort algoritmasını açık kaynak olarak sundu. Paylaşılan kod, özellikle sütun tabanlı veri tabanlarında sıklıkla ihtiyaç duyulan sayı dizisi sıralama işlemlerini SIMD komut setleri yardımıyla hızlandırıyor. Algoritma, AVX-512, AVX2, Arm NEON, SVE ve RISC-V gibi modern mimariler üzerinde tek bir kod tabanıyla yüksek başarım sunuyor.

Sıralama sürecinde en çok işlemci zamanı alan bölümü diziyi bir pivot değere göre ikiye ayıran bölümleme adımı oluşturuyor. Geliştiriciler bu aşamayı hızlandırmak için yeni nesil komut setlerinde yer alan compress-store komutlarını ve bu komutun bulunmadığı durumlarda permütasyon işlemlerini kullandı. Highway adlı taşınabilir SIMD kütüphanesinden yararlanan ekip, yaklaşık 3 bin satırlık C++ kodunu her platform için yeniden yazma zorunluluğunu ortadan kaldırarak 16 bitten 128 bite kadar geniş bir veri tipi aralığını destekledi.

Yapılan performans ölçümlerine göre yeni algoritma, Intel Skylake işlemcide AVX-512 komut setiyle saniyede 1,1 GB sıralama hızına ulaştı ve standart C++ kütüphanesine kıyasla 9 ila 19 kat hız artışı sağladı. Kodlar Apple M1 yongasında Arm NEON üzerinde çalışırken de benzer şekilde yüksek verim gösterdi. Apache 2.0 lisansıyla GitHub üzerinde yayımlanan algoritma, tek bir işlemci çekirdeğinde yüksek hızlı veri işleme olanağı sağlıyor.