Eski sort paketi Go'da yalnızca sort.Interface soyutlamasına dayanıyordu; bu, her karşılaştırma ve değiştirme işlemi için arayüz tabloları üzerinden dinamik yöntem çağrısını zorunlu hale getiriyordu. Bu dolaylılık, derleyici içindeki satırları engelliyor, sanal tabloda gösterici takibi nedeniyle önbellek hatalarına yol açıyor ve arayüz değerinin kendisi için yığın tahsislerini zorunlu hale getiriyordu; bu da, ilkel verilerin yüksek frekanslı sıralaması için önemli bir şekilde verimliliği etkiliyordu.
Go 1.18'de generics'in tanıtılması, constraints.Ordered ile kısıtlanan tür parametrelerini kullanarak slices paketinin (Go 1.21'de stabilize edildi) kullanılmasını sağladı. Bu değişiklik, derleyicinin, karşılaştırma mantığını doğrudan algoritmanın sıcak döngüsüne yerleştiren tür-spesifik sıralama rutinleri üretmesini sağlayan derleme zamanı kodu üretimine (GC şekil stensili) olanak tanıdı. Ayrıca, genel uygulama pdqsort (deseni yenen hızlı sıralama) kullanıyor; bu, giriş desenlerine göre ekleme sıralaması, hızlı sıralama ve yığın sıralaması arasında uyumlu bir şekilde geçiş yaparak, yansıma ve arayüz çağrılarının yükünü ortadan kaldırırken, optimal önbellek yerelliğini koruyor.
Yüksek frekanslı bir telemetri servisi, saniyede milyonlarca sensör okumalarını alıyor ve bunları, bir sütunlu veritabanına kalıcı hale gelmeden önce Unix zaman damgasına göre sıralanması gereken 10,000 elemanlık gruplara tamponluyordu.
İlk uygulama, zaman damgalarını karşılaştıran yansıma tabanlı bir kapatma ile sort.Slice kullandı. Fonksiyonel olsa da, CPU profilleme, toplam uygulama zamanının %18'inin reflect.Value.call ve arayüz dönüşüm yükü içinde tükendiğini ortaya çıkardı; buna ek olarak, yansıma süresince geçici tahsislerden kaynaklanan belirgin bir çöp toplama baskısı vardı.
Mühendislik ekibi, üç farklı yaklaşımı değerlendirdi. İlk seçenek, özel bir SensorSlice türünde sort.Interface'i manuel olarak uygulamaktı. Bu strateji, yansıma yükünü başarıyla ortadan kaldırdı ancak arayüz sanal tablosu üzerinden dolaylı yöntem çağrılarıyla ilgili maliyeti korudu ve sadece %12'lik bir marjinal performans iyileştirmesi sağladı; zira yöntem göstericileri üzerinde sürekli önbellek hataları devam ediyordu.
İkinci yaklaşım, potansiyel olarak düşman girdi desenleri için kesin O(n log n) en kötü durum gecikmesini garanti etmek üzere sort.Sort aracılığıyla saf bir yığın sıralaması uygulaması kullanmayı öngördü. Ancak bu yaklaşım, sensör verilerinin genellikle ağ tamponlaması ve ardışık örnekleme nedeniyle neredeyse önceden sıralanmış olarak geldiği operasyonel gerçeğini göz ardı etti; bu da yığın sıralamasının daha kötü sabitlerinin, yaygın durumlar için uyarlanabilir algoritmalara göre boşa harcanmasına neden oldu.
Üçüncü çözüm, kod tabanını slices paketinden slices.SortFunc'a taşıyarak, func(a, b SensorReading) bool { return a.Timestamp < b.Timestamp } gibi basit bir azalma fonksiyonu geçti. Bu fonksiyon, dış durumu yakalamadan yalnızca değer parametreleri üzerinde çalıştığı için, derleyici bunu düzgün bir şekilde pdqsort rutinine iç içe yerleştirdi. Algoritma, telemetri verisinin kısmen sıralı doğasını otomatik olarak algıladı ve küçük partisyonlar için ekleme sıralamasını kullandı; böylece p99 sıralama gecikmesini 4 kat azaltarak tahsis yükünü tamamen ortadan kaldırdı.
Neden slices.Sort, yalnızca karşılaştırılabilir alanlar içeren struct'ların bir dilimini aldığında derlenmiyor?
slices.Sort fonksiyonu, tür parametresinin constraints.Ordered'ı tatmin etmesini gerektirir; bu da kullanımını yalnızca < (küçüktür) operatörünü yerel olarak destekleyen türlerle sınırlı hale getirir; bunu sağlamak için tamsayılar, kayan sayılar ve dizeler gibi türler kullanılabilir. karşılaştırılabilir türleri eşitlik kontrolünü (== ve !=) desteklese de, bunlar sıralama için gerekli olan bir sıralama ilişkisini doğası gereği tanımlamazlar. Go'da struct'lar sıralı değildir; dolayısıyla bir struct'a karşı küçükten büyüğe operatörü uygulanmaya çalışıldığında, statik olarak sıralama olamayacak bir tür olduğu belirtilen derleme hatası oluşur. Bu nedenle, özel struct'ların bir dilimini sıralamak için geliştiricilerin slices.SortFunc kullanması ve belirli alanları karşılaştırarak sıralama mantığını tanımlayan bir karşılaştırma fonksiyonu sağlaması gerekir.
Generic slices paketinde kullanılan pdqsort algoritması, sıradan hızlı sıralama uygulamalarının tipik O(n²) en kötü durum davranışına karşı nasıl koruma sağlar?
pdqsort (deseni yenen hızlı sıralama), düşmanca ve patolojik girdilere karşı birkaç çalışma zamanı sezgisi ile savunma yapar. Yüksek kaliteli pivotlar seçmek için elemanları örnekler (üçün ortalaması veya doksan dokuzun ortalaması), zaten sıralı veya ters sıralı dizileri tespit eder ve çok az benzersiz değere sahip durumları belirler. Bu desenleri algıladığında, küçük partisyonlar için ekleme sıralamasına veya büyük dejeneratif partisyonlar için yığın sıralamasına geçiş yapar; böylece O(n log n) en kötü durum performansını garanti ederken, uygun veriler üzerinde O(n) hızını korur. Bu, daha eski hızlı sıralama uygulamalarının sıralı girişlerde, her zaman ilk veya son elemanı pivot olarak seçmeleri halinde, rastgeleleştirme olmaksızın, kararlılıkla dörtgen şekilde düşebileceği anlamına gelir.
slices.SortFunc kullanırken, çevredeki kapsamdan değişkenleri yakalayan bir kapanış neden bağımsız bir üst düzey işlevden önemli ölçüde daha kötü performans gösterir ve bu nasıl teşhis edilebilir?
Eğer bir kapanış, dış kapsamdan bir gösterici veya dilim gibi yığına kaçan değişkenleri yakalarsa, derleyici bu değişkenleri depolamak için yığın üzerinde bir kapanış nesnesi tahsis etmek zorundadır ve bu nesneye işlevi çağırdığında bir gösterici ile geçer. Bu, karşılaştırma işlevinin mid-stack iç içe yerleştirilmesini engeller, sıralama sırasında her karşılaştırma için tam bir yöntem çağrısı yükünü zorunlu hale getirir. Milyonlarca karşılaştırma içeren büyük veri kümeleri için bu, iç içe geçirilmiş karşılaştırmalara kıyasla performansı %20-40 oranında azaltabilir. Adaylar, derleyici bayrağını go build -gcflags="-m" kullanarak yığın içi yerleştirme kararlarını inceleyerek bunu teşhis edebilir; eğer derleyici, kapanış yükü nedeniyle işlevin "iç içe yerleştirilemeyeceğini" bildirirse, karşılaştırmayı bağımsız bir üst düzey işleve dönüştürmek veya değişken yakalamalarını ortadan kaldırmak, optimal performansı geri kazandıracaktır.