En hızlı branchless ikili arama

• Bu makale, standart std::lower_bound fonksiyonundan iki kat daha hızlı ve daha kısa olan genel bir ikili arama C++ implementasyonunu ele alıyor.
• Yeni implementasyon, dallanma/koşullu sıçrama yerine koşullu taşıma komutlarına derlendiği için "dallanmasız"dır.
• İkili arama, sıralı bir listeyi ortadaki öğeden iki parçaya bölüp orta değeri verilen değerle karşılaştırarak çalışır. Karşılaştırmanın sonucuna göre aramaya iki alt listeden hangisinde devam edileceğine karar verilir.
• Makale ayrıca, işlemcinin komutları paralel çalıştırarak hızı artırdığı bir teknik olan dallanma tahmini kavramını da ele alıyor. Ancak ikili arama öngörülemez olduğundan, dallanma tahmini burada ideal değildir.
• Yazar, standart implementasyon ve branchless_lower_bound sürümünden daha hızlı olan yeni bir ikili arama implementasyonu olan sb_lower_bound'u tanıtıyor. Döngü içindeki komut sayısı çok daha az olduğu için daha hızlıdır.
• Yazar ayrıca, arama listesini bölmek için farklı bir yöntem kullanan daha hızlı bir sürüm olan bb_lower_bound'u da sunuyor.
• Makale, programın en yavaş kısmı işlemcinin tahmin edemediği arama ve/veya karşılaştırmalar içeriyorsa, clang'ı -mllvm -x86-cmov-converter=false ile denemenizi önererek sonlanıyor. Daha hızlı bir ikili aramaya ihtiyacınız varsa sb_lower_bound'u deneyin.
• Yazar ayrıca yeni ikili arama implementasyonlarının kodunu sağlıyor ve her birinin performansını ayrıntılı olarak tartışıyor.
• Makale, hot loop içindeki assembly komutu sayısını 9'dan 8'e düşüren sb_lower_bound'un yeniden düzenlenmiş bir sürümüyle güncellendi; bu da hızda küçük bir artış sağladı.
• Yazar ayrıca, belirli bellek bölümlerini önceden önbelleğe çekerek gerçekten ihtiyaç duyulduğunda yalnızca L1/L2 cache gecikmesinin yaşanmasını sağlayan prefetching kavramını da ele alıyor. 256KB+ için prefetching eklenmiş bir sb_lower_bound sürümü de sunuluyor.
• Makale Mihail Dumitrescu tarafından yazıldı ve 24 Haziran 2023'te yayımlandı.

[GN⁺]

Hacker News görüşleri

• Makale, dallanmasız ikili arama kavramını ve bunun potansiyel avantajlarını ele alıyor.
• Bir yorum, dallanmayı ortadan kaldırma gerekliliğini sorguluyor ve dal tahmini başarısızlığından kaynaklanan işlem hattı duraksamasının mimarinin özsel bir parçası olmadığını öne sürüyor.
• Yorumda ayrıca tüm işlemlerin özünde birer dallanma olduğu, ancak bu dallanmaların performansa zarar vermemesinin nedeninin ana işlem hattındaki dallanmalar olmamaları olduğu açıklanıyor.
• Başka bir yorum, lowerBound uygulamak için "bare-metal" bir dile derlenen Nim dilinin kullanılmasını öneriyor.
• Kodun ilk eşleşeni mi döndürdüğü yoksa herhangi bir eşleşeni mi döndürdüğü üzerine bir tartışma var; bu da kodun ne yaptığını anlamanın önemini vurguluyor.
• Bir yorum, blog yazısının sezgisel girişini övüyor; bu giriş, en hızlı genel amaçlı ikili arama C++ uygulamasını hızlıca sunuyor.
• Yorumda, Zig stdlib'in ikili arama için C++ çağırmadığı belirtiliyor ve Zig stdlib'deki ikili aramaya bir bağlantı veriliyor.
• İkili arama ve dallanma sorununa dair bir tartışma var; sorunun dallanmanın kendisi değil, karşılaştırma tamamlanana kadar sıradaki hangi bellek konumunun getirileceğinin bilinmemesinden kaynaklanan veri bağımlılığı olduğu öne sürülüyor.
• Yorumda, Cascade Lake işlemcideki ikili arama performans sonuçları paylaşılıyor ve clang'ın bu özel kodu optimize etmede gcc'den daha kötü olduğu öne sürülüyor.
• Bir yorum, "BUT RUST" bağlantısının nereye gittiğini sorguluyor ve bu bağlantının eski göründüğünü söylüyor.
• Yorumda, sonuçların daha karmaşık karşılaştırma işlevlerinde geçerli olmadığını belirtiliyor; en iyi performansın temel türler için sb_lower_bound, diğer durumlar için ise std::lower_bound kullanılarak elde edilebileceği öne sürülüyor.
• Son yorumda, öngörülemezlik niteliğinin artık cmov dönüşüm geçişini etkilediği belirtiliyor ve ek bilgi için bir bağlantı veriliyor.