Google, std::sort'a kıyasla 19 kata kadar hızlanan vektörize Quicksort'u açık kaynak yaptı

Bellek veriyolu hızlarında çalışan taşınabilir bir sıralama

Google, sayı dizilerini C++ standart kütüphanesindeki std::sort'tan yaklaşık on kat daha hızlı sıraladığını söylediği, açık kaynak ve vektörize bir Quicksort yayımladı; kod, modern CPU mimarileri arasında taşınabilir kalıyor. Şirketin Brain Computer Architecture Research grubundan Jan Wassenberg tarafından kaleme alınan Google Open Source Blog gönderisine göre kod, bazı donanımlarda mevcut mimariye özel sıralamaları geride bırakıyor ve GitHub'da Apache 2.0 lisansıyla erişilebilir. Gönderi bu hafta Hacker News ana sayfasında yeniden gündeme geldi.

Çalışmanın motivasyonu, tek bir kaydın tüm alanlarını birlikte gruplandırmak yerine tek bir sütundaki tüm değerleri bitişik biçimde depolayan kolonlu (columnar) veritabanlarına doğru yaşanan geçiş. Blogda açıklandığı gibi bu düzen, SQL sorgu yürütmede iki temel işlem olan filtrelemeyi ve sıralamayı belirgin biçimde daha ucuz hale getiriyor; yeni sıralamanın hedeflediği veri düzeni de tam olarak bu.

Hızlanma nereden geliyor

Sıralama onlarca yıldır incelenen bir konu; dolayısıyla büyük bir kazanç yeni bir algoritmadan değil, donanımdan gelmek zorunda. Anahtar, tek bir komutu aynı anda birkaç bağımsız değere uygulayan SIMD (single instruction, multiple data): örneğin AVX-512'de komut başına 16 float32 değeri, Arm NEON'da ise dört değer işlenebiliyor.

Engel, SIMD'ın bağımsız elemanlar üzerinde çalışması, sıralamanın ise komşu elemanları yeniden düzenlemesi. Wassenberg'in anlattığı çözüm, vektörizasyonu algoritmanın CPU zamanının çoğunu tüketen Quicksort'un bölümleme (partitioning) adımında yoğunlaştırmak. Dizi, pivot değerinin altındaki ve üstündeki elemanlar olacak biçimde tekrar tekrar bölünüyor; bir alt dizi yeterince küçüldüğünde — bu uygulamada 256 eleman — ilgili makalede belgelenmiş özel bir yordama devrediliyor.

x86 AVX-512, Arm SVE ve RISC-V V gibi modern komut setleri, bu iş için birebir uygun bir compress-store komutu içeriyor: pivottan küçük olan elemanları işaretleyen evet/hayır bayraklarından oluşan bir mask verildiğinde, komut yalnızca işaretli elemanları ardışık belleğe yazıyor. Maskın tersini alıp işlemi tekrarlamak diğer bölümü yazıyor. Compress-store bulunmayan komut setlerinde, özellikle AVX2'de, blogda belirtildiğine göre önceki araştırmalar bu işlemin permute komutlarıyla nasıl taklit edilebileceğini göstermiş.

Tek uygulama, altı komut seti

Önceki vektörize sıralamalar tek bir komut seti için yazılmıştı. Google'ın Highway taşınabilir SIMD kütüphanesi üzerine kurulu bu proje, her platform için yaklaşık 3.000 satır C++ kodunu yeniden yazmadan, üç mimariye yayılan altı komut setinde çalışan ilk vektörize Quicksort olarak tanımlanıyor. Highway, compress-store varsa onu seçiyor, yoksa permute tabanlı taklide geçiyor ve çalışma zamanında (runtime) kullanılabilir en iyi yolu belirliyor.

Uygulama ayrıca girdi aralığını genişletiyor: Önceki en iyi uygulama yalnızca 32 bit tam sayıları desteklerken, yeni sıralama 16 bitten 128 bite kadar girdileri destekliyor.

Kıyaslama sayıları

Blog gönderisine göre, Apple M1 (Arm NEON) üzerinde bir milyon adet 32, 64 veya 128 bitlik sayıyı sıralamak sırasıyla 499, 471 ve 466 MB/s verim sağlıyor. AVX-512 destekli 3 GHz'lik bir Intel Skylake'de bu rakamlar üç genişlikte de yaklaşık 1.120 MB/s'ye yükseliyor. AVX2 donanımında yeni kod 798 MB/s ölçülüyor ve önceki AVX2 için optimize edilmiş en iyi uygulamanın 699 MB/s değerinin önünde.

Standart kütüphaneyle kıyaslama asıl çarpıcı olan: Aynı CPU'da std::sort üç genişlik için 58, 128 ve 117 MB/s'ye ulaşabiliyor; bu da hızlanmayı sayı türüne göre 9x ile 19x arasına koyuyor. Blog ayrıca Highway CPU'nun desteklediğini algıladığı için AVX-512'nin kod değişikliği olmadan AVX2'den 1,4–1,6 kat daha hızlı çalıştığını belirtiyor.

Neden önemli

Sıralama geleneksel olarak görece pahalı bir işlem olarak görülüyordu; gönderi, tek bir CPU çekirdeğinde yaklaşık 1 GB/s hızla sıralama yapabilmenin önceden pratik olmayan uygulama ve yeteneklerin önünü açabileceğini savunuyor — kolonlu veritabanı motorları ve genel olarak veri işleme hatları için çekici bir öngörü.

Geliştiriciler için iki pratik çıkarım var. Birincisi, sıralamanın kendisi şu anda izin veren bir lisansla kullanılabilir; yazarlar GitHub'da soru ve sorun bildirimlerine davet ediyor. İkincisi, bu, Highway gibi taşınabilir SIMD soyutlama katmanlarının neler başarabileceğinin somut bir kanıtı: eskiden elle yazılmış, mimariye özel kod gerektiren performans, sunucu CPU'nun sunduğu vektör komutlarına otomatik olarak uyum sağlayan tek bir kod tabanından elde ediliyor.