1BRC yarışmasına giriş
- 1BRC yarışmasında, “alışıldık şüpheliler” işlendiğinde CSV dosyasından sıcaklık ayrıştırmanın darboğaz olacağı öngörülüyordu.
- Sıcaklıklar
-XX.X, -X.X, X.X, XX.X olmak üzere dört biçimde gelebiliyordu ve başlangıçta Double.parseDouble() kütüphane çağrısı kullanılıyordu.
- Ancak kısa süre sonra özelleştirilmiş çözümler ortaya çıktı; bunlardan biri, döngü olmadan yalnızca iki dala sahip optimize edilmiş bir yöntem gibi görünüyordu.
- Ardından Quân Anh Mai(@merykitty) tarafından sunulan çözüm, Twitter'daki #1BRC etiketini alevlendirdi. Bu çözüm,
if deyimi olmadan yalnızca tek bir dosya okuma kullanıyordu.
merykitty'nin büyülü SWAR'ının analizi
- merykitty'nin kodu yalnızca 18 ALU işleminden oluşuyor ve
numberOfTrailingZeros() adlı tek bir düşük seviyeli fonksiyon çağrısı içeriyor.
- Girdi olarak verilen
long değeri, CSV'den gelen 8 baytı içeriyor; çıktı ise sıcaklığın tamsayı biçimi oluyor (gerçek sıcaklığın 10 katı).
- Bu teknik, “SIMD Within A Register” (SWAR) olarak adlandırılır ve standart CPU yazmaçları ile komutlarını kullanır.
- Kod; sayının negatif olup olmadığını algılama, işaret karakterini kaldırma, ondalık noktanın yerini bulma, içeriği şablona göre hizalama, ASCII karakterlerini sayısal değerlere dönüştürme, her basamağı ağırlığıyla çarpıp hepsini toplama ve işareti uygulama gibi adımlardan geçer.
- Bu adımların tamamı yalnızca ALU işlemleri kullanılarak gerçekleştirilir.
Sonuç
- merykitty'nin tüm bunları birkaç gün içinde tek başına nasıl başardığı, bir blog yazısıyla açıklanamayacak gerçek gizem.
- QuestDB açık kaynaklıdır ve Apache 2.0 lisansı altında hızlı veri ekleme ve SQL analiz özellikleri sunar.
GN⁺ görüşü
- Bu makale, basit bir sıcaklık ayrıştırma problemini çözmek için tasarlanan SWAR tekniğinin karmaşıklığını ve yaratıcılığını gösteriyor. Bu da programlamada bit işlemlerinin gücünü ve optimizasyonun önemini vurguluyor.
- Bu yaklaşım, özellikle sistem programlama ya da performansa duyarlı uygulama geliştirmeyle ilgilenen junior yazılım mühendisleri için ilgi çekici bir örnek olabilir.
- Bit işlemleri ve optimizasyon konusundaki anlayışı geliştirmek için, ilgili başlıkları veya problemleri ele alan çevrim içi kodlama yarışmaları ya da eğitimleri araştırmak faydalı olabilir.
- Bu tekniğin gerçek endüstriyel ortamlarda nasıl uygulanabileceği ve benzer optimizasyon yöntemlerini kullanan başka veritabanları ya da sistemler olup olmadığı konusunda ek araştırmaya ihtiyaç var.
- QuestDB gibi sistemleri devreye alırken yalnızca performans artışı değil, bakım kolaylığı, kodun okunabilirliği ve uzun vadeli teknik destek gibi diğer etkenler de dikkate alınmalıdır.
1 yorum
Hacker News görüşleri
simdjson makalesiyle ilgili Hacker News yorumlarının özeti:
Kod bağlamına dair yorum: Sunulan çözüm çok etkileyici, ancak verinin iyi yapılandırılmış olduğu varsayımını gerektiriyor. Verimli hata denetimi ve kurtarma özellikleri, deneyimli ayrıştırıcılarda büyük değer taşır.
Sayı ayrıştırma tekniği: Sayı bit alanlarını ilgili 10'un kuvvetleriyle ayrı ayrı çarpıp, MUL ile shift/toplama yapmak bilinen bir tekniktir. Lemire'in bloguna bakın.
SWAR (SIMD Within A Register) açıklaması: Java/Scala'da byte array view var handle'ları kullanarak verimli SWAR rutinleri uygulayan birçok örnek var.
SWAR'ın kısa tanımı: "SIMD Within A Register", tek bir register içinde SIMD işlemleri gerçekleştirmek anlamına gelir.
BRC (Branchless Ray Casting) için I/O darboğazı sorusu: CPU'nun darboğaz olmasının neden söylendiği anlaşılmıyor.
68000'de SWAR kullanım deneyimi: 4 byte'ı aynı anda paralel işlemek mümkündü, ancak overflow yönetimi zordu. İlgili makale çok beğenilmiş.
Durum uzayı ve süper optimize edici: Durum uzayı küçük olduğu için benzer sonuçlar üreten bir süper optimize edici olup olmadığı soruluyor.
AVX komutları ve Java'nın SIMD desteği: Bu algoritma AVX komutları kullanılarak 32 kat paralel çalıştırılabilir, ancak Java belirli durumlar dışında SIMD CPU kullanımını gerektiği gibi desteklemiyor.
Bit manipülasyonu anlayışı: Bu makale, bit manipülasyonunu daha önceki her şeyden daha iyi anlamayı sağlamış; ayrıca yazara 1BRC challenge için sunduğu Java çözümü nedeniyle teşekkür ediliyor.