Python'da hesaplama ağırlıklı kodları hızlandırmak için genellikle iyi bir algoritma seçmek, derlenmiş bir dille Python eklentisi yazmak ve paralellik eklemek önerilir. Peki ya daha fazla hıza ihtiyacınız varsa? scikit-learn'ün gradient histogram boosting algoritmasındaki gerçek bir problemi ele alalım: Büyük bir kayan nokta dizisini 0-254 aralığına eşit şekilde dağıtmak. Bu işlem, değerleri 255 kovaya ayırmak için sıralanmış sınırlar üzerinde ikili arama yapar. Son zamanlarda Quansight'taki çalışmam sırasında Paul Khuong'un yazılarından ilham alarak bu uygulamayı önemli ölçüde hızlandırdım. Nasıl mı? Kodun CPU ile savaşmasını engelleyerek.
Bu makalede, basitleştirilmiş bir örnek üzerinde hızlandırma adımlarını göstereceğim. Ardından, son sürümün orijinalinden 6 kat daha hızlı çalıştığı bir dizi ek optimizasyon göstereceğim. Düşük seviyeli donanım konularına hızlıca değineceğim: talimat düzeyinde paralellik, branş (yanlış) tahmini, bellek önbellekleri, SIMD ve daha fazlası. Bu sadece bir makale, sadece nelerin mümkün olduğuna kısa bir giriş yapabilir; derinlemesine bir eğitim işlevi göremez.
Başlangıç noktası: Standart ikili arama. Orijinal scikit-learn kodu Cython ile yazılmıştı, ancak bu makale için Rust kullanacağım. Aşağıda, belirtilen sınırlar dizisine göre bir kova bulmak için tasarlanmış standart bir ikili arama uygulaması var. Bu kod, Rust'ın normal < operatörü yerine özel bir karşılaştırma fonksiyonu kullanır çünkü NaN karşılaştırmaları tutarsızlık yaratır. Kod, her değer için ikili arama yaparak sonuç vektörüne ekler. Python'a bağlamak için PyO3 ve NumPy kullanılır, ancak bu makalenin odak noktası değil.
Branş yanlış tahminleri kodunuzu yavaşlatır. Modern CPU'lar, tek bir çekirdekte birden fazla bağımsız talimatı aynı anda çalıştırabilir (talimat düzeyinde paralellik). Ancak if/while/for gibi dallanmalar sorun yaratır: CPU, hangi dalı paralel olarak çalıştıracağını tahmin etmek zorundadır. Branş tahmincisi doğru tahmin ederse hızlı, yanlış tahmin ederse yavaş çalışır. Yukarıdaki ikili arama algoritması, her adımda bir branş içerir ve bu branşların tahmin edilmesi zordur çünkü her seferinde rastgele gibi bir seçim yapılır. Bu da branş yanlış tahminlerine yol açar.
Branş yanlış tahminlerini azaltmak için bir teknik, dallanmayı ortadan kaldırmaktır. Örneğin, ikili aramada koşullu atlamayı kaldırarak dallanmasız bir sürüm yazabiliriz. Ancak bu, her adımda iki indeks hesaplamayı ve ardından doğru olanı seçmeyi gerektirir; bu da ekstra hesaplama yükü getirir. Daha etkili bir yöntem, veri yapısını değiştirmektir. Örneğin, Eytzinger düzeni, ikili arama ağacını bir dizi içinde belirli bir sırayla yerleştirerek önbellek dostu hale getirir ve branş tahminini iyileştirir.
Nasıl Önlem Alınmalı?
SIMD (Tek Talimat Çoklu Veri) kullanarak da hızlanma sağlanabilir. SIMD, bir talimatla birden fazla veri öğesi üzerinde işlem yapmanızı sağlar. Örneğin, karşılaştırma talimatları aynı anda dört değeri karşılaştırabilir. Ancak SIMD ile ikili arama yapmak, dallanma sorununu daha da karmaşık hale getirir. Bunun yerine, doğrusal arama gibi basit algoritmalar SIMD ile hızlandırılabilir. Sonuç olarak, doğru optimizasyonlarla orijinal koddan 6 kata kadar hız artışı elde edilebilir. Bu makale, düşük seviyeli optimizasyonların gücünü göstermeyi amaçlıyor; daha fazla bilgi için kaynaklara başvurabilirsiniz.
Kaynak: pythonspeed.com
