1 Milyar Satır Meydan Okuması

 (morling.dev)
2 puan yazan GN⁺ 2024-01-05 | 2 yorum | WhatsApp'ta paylaş
  • 2024 Ocak ayı boyunca düzenlenen One Billion Row Challenge(1BRC), 1 milyar satırlık bir metin dosyasını işleyerek Java'nın ne kadar hızlanabileceğini ölçen bir performans meydan okumasıydı
  • Girdi station;temperature biçiminde basit bir metin olsa da, her istasyon için minimum·ortalama·maksimum sıcaklığı hesaplayıp ad sırasına göre doğru biçimde yazdırmak gerekiyor
  • Uygulamada yalnızca Java'ya izin veriliyor; SDKMan dağıtımları ve openjdk.net Early Access derlemeleri kullanılabiliyor, ancak harici bağımlılıklar yasak
  • Katılımcılar GitHub'daki 1brc deposuna pull request ile gönderim yapıyor ve sağlanan temel uygulama ile doğru çıktı biçimini ve performansı karşılaştırabiliyor
  • Değerlendirme, aynı Hetzner Cloud CCX33 ortamında 5 çalıştırmanın ardından en düşük ve en yüksek süreler hariç tutularak kalan 3 çalıştırmanın ortalamasıyla liderlik tablosu sıralamasını belirliyor

1 milyar satırı en hızlı toplayan Java görevi

  • One Billion Row Challenge, 1 Ocak 2024 ile 31 Ocak 2024 arasında düzenlenen bir Java performans meydan okumasıydı
  • Katılımcılar, bir metin dosyasındaki sıcaklık ölçümlerini okuyup her meteoroloji istasyonu için minimum·ortalama·maksimum sıcaklığı hesaplayan bir Java programı yazdı
  • Zorluğun temel noktası, girdi dosyasının 1.000.000.000 satır olmasıydı
  • Girdi, her satırda bir ölçüm değeri bulunan basit bir yapıya sahipti
    • Örn: Hamburg;12.0
    • Örn: Bulawayo;8.9
    • Örn: Palembang;38.8
  • Çıktıda istasyon adları alfabetik sıraya göre sıralanmalı ve her istasyonun min/mean/max değerleri gösterilmeliydi
    • Örn: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Gönderim kuralları ve çalışma ortamı

  • Amaç, aynı işi yapan en hızlı Java uygulamasını oluşturmaktı
  • Optimizasyonda sanal iş parçacıkları, Vector API ve SIMD, GC optimizasyonu, AOT derleme gibi tekniklerden yararlanılabiliyordu
  • Temel kurallar şöyleydi
    • Gönderimler Java ile yazılmalıydı
    • SDKMan tarafından sunulan Java dağıtımları ve openjdk.net'in Early Access derlemeleri kullanılabiliyordu
    • Valhalla gibi OpenJDK projelerinin EA derlemelerine de izin veriliyordu
    • Harici bağımlılıklar kullanılamıyordu
  • Katılımcılar 1brc deposunu klonlayıp README yönergelerine göre uygulamalarını gönderiyordu
  • Temel uygulama, karşılaştırma ölçütü ve doğru çıktı biçimini kontrol etmek için sağlanmıştı
  • Gönderimler, upstream depoda pull request açılarak yapılıyordu

Liderlik tablosu hesaplama yöntemi ve topluluk paylaşımı

  • Değerlendirme Hetzner Cloud CCX33 instance'ı üzerinde yapılıyordu
    • Özellikler 8 dedicated vCPU, 32 GB RAM idi
    • Uçtan uca çalışma süresi time programıyla ölçülüyordu
    • Her gönderim art arda 5 kez çalıştırılıyordu
    • En yavaş ve en hızlı çalıştırmalar hariç tutuluyordu
    • Kalan 3 çalıştırma süresinin ortalaması ilgili gönderimin sonucu oluyordu
    • Sonuçlar leaderboard'a ekleniyordu
  • Optimizasyon teknikleriyle ilgili tartışmalar GitHub deposundaki discussion bölümünde sürüyordu
  • Java dışındaki dillerle yapılan uygulamaları paylaşmak için Show & Tell bölümü de hazırlanmıştı; Rust, Go, C++ gibi dillerdeki 1BRC uygulamaları paylaşılıyordu

İlgili okumalar

2 yorum

 
GN⁺ 2024-01-05
Hacker News yorumları

  • Şu anda en iyi performansı veriyor gibi görünen çözüm [0], hash çakışmalarını hesaba katmadığı için veri kümesinde yeterince çok farklı şehir varsa yanlış sonuç üretecek gibi görünüyor
    Bir şeyi kaçırıp kaçırmadığımı merak ediyorum
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Doğru. Dün bu sorun ortaya çıktı; gerçekten de iki çözüm, belirli bir veri kümesine göre ayarlanmış hash fonksiyonlarına dayanarak tüm gözlem istasyonu adlarında çalışmalı kuralını ihlal ediyordu, ama değerlendirme sırasında gözden kaçmış
      Şimdilik bu girdileri liderlik tablosundan kaldırdık; iki yazar da gönderilerini düzeltiyor, sonrasında yeniden eklenecekler
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Aşağıdaki yaklaşımla tamamının 0,3 saniye içinde işlenebileceğini düşünüyorum
    Sıcaklıklar tek ondalık basamaklı olduğundan genel durumda yaklaşık 400 değer yeterli; yer adları da yaklaşık 400 ile sınırlı olduğundan sıcaklık×yer adı kombinasyonları için yaklaşık 160 bin girdilik bir lookup table oluşturulabilir
    Bu 160 bin girdiyi, 4 baytlık bir register içinde hangi döndürme konumunda olurlarsa olsunlar hash tablosunda benzersiz bucket'lara eşleyen bir durum makinesi otomatik üretilebilir; 32 bitlik durum register'ında her döngüde durum geçiş tablosu sorgusu ve sonraki 4 baytla XOR yapılır
    Tüm veriyi bellek hızında tarayıp duruma göre sayaçları artırmak yeterli; yalnızca 65K durum olduğu için sayaçlar cache'e sığar
    AVX512 ile çekirdek başına bu 32 bitlik durum makinelerinden 512 tanesini paralel çalıştırabilirsiniz, yani hesaplamanın darboğaz olmayacağını düşünüyorum
    Geçerli bir bucket'a eşlenmeyen yüksek/düşük sıcaklıklar veya bilinmeyen yer adları yavaş koda devredilir; minimum/maksimum işleme de böyle bir escape ile yapılırsa yalnızca birkaç bin kez gerçekleşir
    Bu yöntemin tek bir AVX512 çekirdeğiyle bile bellek hızında çalışabileceğini, bu yüzden birden fazla çekirdeğe bölmenin avantajı olmadığını düşünüyorum

    • Lookup table'a gerek yok. İstenen yalnızca minimum/ortalama/maksimum olduğu için verileri saklamadan tek geçişte hepsi hesaplanabilir
      Gerekenler 400 öğeli bir hash tablosu, çalışma anındaki minimum·ortalama·maksimum için 3 kayan nokta değeri ve ortalamayı güncellemek için bir sayaç tamsayısı
      Adlar için 16 bayt kullansanız bile tamamı 16KB içinde kalır
      Çalışma süresini I/O belirler; ardından muhtemelen JSON ayrıştırma gelir
    • Tek çekirdek bellek bant genişliğini doyuramaz. Çekirdek, bellek paralelliği ve gecikme süresiyle sınırlıdır
      Modern x86 sunucu yongalarının çoğu saat döngüsü başına 2 SIMD load'u retire edebilir; bu yüzden AVX2 ile 1GHz'de yaklaşık 32GB/s mümkündür, çekirdek başına bant genişliğini maksimize etmek için AVX-512 şart değildir
      Ama DRAM'den okuyorsanız çok daha erken, tipik sunucularda muhtemelen 10–16GB/s civarında takılırsınız
      Verinin çoğu RAM'e taştığı sürece tek çekirdek throughput'u ciddi biçimde düşer; büyük streaming işlerinde çok çekirdekli paralellik neredeyse her zaman kazanç sağlar
      L3 cache'ten çok daha büyük bir bellek bloğu ayırıp, sayfa hatalarını önceden tetikledikten sonra, sıkı bir döngüde açılmış vektör load'ları (AVX2/AVX-512) yaparsanız bunu kolayca görebilirsiniz
    • Sonraki durum her zaman önceki duruma bağlıyken durum makinesini nasıl paralel çalıştırabileceğinizi bilmiyorum
      Ayrıca durum register'ını nasıl yorumlayacağınız da soru işareti. Girişteki 4 baytla XOR yapılırsa beklenmeyen yer adlarında fiilen 4,7 milyar olası değerden herhangi biri olabilir
      Beklenen bir yer adı olsa bile 4 bayttan uzunsa, ortak öneke sahip başka adlardan ayırt etmek için her biri için birden çok durum gerekmez mi diye düşünüyorum
    • Kural yorumunu kontrol etmek gerekiyor gibi. Bilinen 400 yer adına özelleşip yavaş yolla ek adları destekleyen kodun geçerli olup olmadığı net değil
      Kurallar, veri üreteci sabit bir gözlem istasyonu adı kümesi kullansa bile her çözümün keyfi UTF-8 gözlem istasyonu adlarında çalışması gerektiğini söylüyor
    • Yer adlarını bulmak için sonuçta tüm dosyayı okuyup ayrıştırmak gerekiyor

  • En yavaş çalıştırmayı ve en hızlı çalıştırmayı atıp kalan üç çalıştırmanın ortalamasını almak yerine, en yavaş iki çalıştırmayı atmak ya da sadece en hızlı değeri kabul etmek bence daha iyi
    İyi bir çalıştırma sonucunu atmak için geçerli bir neden olduğunu düşünmüyorum

    • Bu, kırpılmış ortalama (Trimmed Mean) denen oldukça standart bir ölçüm yöntemidir: https://statisticsbyjim.com/basics/trimmed-mean/
    • En iyi çalıştırmayı atmak için bir neden var. Sistemin öngörülebilir davrandığını ve sadece arka plan işleri yüzünden yavaşladığını varsayarsanız en iyi çalıştırmayı kullanmak mantıklı olabilir
      Ama programın içinde en ufak bir belirsizlik kaynağı varsa —ki bu sanıldığından yaygındır— en iyi süre temsil gücü düşük olabilir
      Bununla ilgili https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... iyi bir yazı
    • En hızlı çalıştırmayı atmayı kabul edilemez buluyorsanız, en yavaş çalıştırmayı atmayı neden desteklediğinizi merak ediyorum

  • Kuralları didikleyen biri olarak, ilk çalıştırmada arka plan daemon’ını başlatıp dosyanın tamamını belleğe yükleyip sabitlemek, ardından sonraki çalıştırmaların fiilen yalnızca doğrusal tarama yapması için önbelleği de önceden ısıtmak isteyebilirsiniz.
    İlk çalıştırmada sonucu önceden hesaplamak da, kuralları ne kadar esneterek yorumladığınıza bağlı olarak mümkün görünüyor; sayıları önceden daha yoğun bir biçime ayrıştırıp sonraki çalıştırmalarda doğrudan kümülatif toplam olarak okumak da mümkün olabilir.
    Yarışmanın ruhuna hiç uymuyor, ama görünen kurallara göre yasaklanmış gibi de durmuyor.
    Ön hesaplamadan hoşlanmıyorsanız girdiyi önceden sıralamak ya da önceden ayrıştırmak; sıkıştırma, sıralama, sıralanmış bellek yerleşimi gibi hilelere başvurmak da mümkün.
    Uç bir örnek olarak calculate_time betiğini 0 saniye döndürecek, rakipler içinse 9999 döndürecek şekilde yamalamak bile mümkün olabilir.

    • Katılımcılara yarışmada gerçekten kullanılacak dosyanın aynısını verirseniz asıl sorun ortaya çıkar.
      Girdiyi hiç okumadan yanıtı tek satır olarak sabit kodlamaktan, dosya içeriğini bilmiyormuş varsayarak işlemeye kadar ön hesaplamanın gri alanı yaklaşık bir milyar aşamadan oluşur.
      Neyin adil ön hesaplama olup neyin olmadığına karar verme yarışmasına dönüşebilir.
      Bu yüzden makine öğrenmesi yarışmaları katılımcılara nihai veriyi göstermez.
    • Bu, kuralları ihlal edecek gibi görünüyor.
      Hesaplamanın uygulama çalıştırıldığı anda gerçekleşmesi gerektiği, ölçüm dosyasını derleme aşamasında işleyip sonucu ikili dosyanın içine gömmenin yasak olduğu belirtilmiş.
    • Bence kurallarda her çalıştırmanın ayrı bir tmpfs içinde yapılacağı ve çalıştırmalar arasında tüm süreçlerin ve sayfa önbelleğinin temizleneceği açıkça belirtilmeli.

  • Bu sadece disk hızına bağlı bir problem değil mi diye düşünüyorum. SIMD ya da çok iş parçacığı gibi optimizasyonların anlamlı olup olmayacağından emin değilim.
    Farklı gözlem istasyonu sayısına ve hash arama yöntemlerine göre değişir elbette, ama giriş/çıkışa kıyasla ölçülebilir düzeyde olup olmayacağı konusunda şüpheliyim.

    • Disk erişimi paralelleştirilebilir ve NVMe çok hızlı olduğundan darboğaz diskten çok CPU tarafında olabilir.
      Modern donanımı varsayarak tasarlanan sistemler bundan yararlanır; çalıştığım redpanda.com da buna bir örnek.
      Ayrıştırma, hesaplama süresinin büyük bir bölümünü oluşturur ve ayırıcıları bulmak için SWAR gibi SIMD teknikleri yardımcı olabilir.
      Bu tür algoritmaların temiz bir uygulamasını görmek istiyorsanız Stringzilla iyi bir örnek: https://github.com/ashvardanian/StringZilla
      İlk çalıştırmadan sonra dosyanın tamamen bellekte önbelleğe alınması konusuna burada yanıt verdim: https://news.ycombinator.com/item?id=38864034
    • Tamamen iş yüküne ve donanıma bağlı. Sıradan tüketici tipi SSD’ler bile 2TB’ın yalnızca 700GB’ı kullanılıyorsa 7GB/s’yi (56Gbps) rahatça sürdürebilir.
      Tipik sunucularda bu SSD’lerden 15 tane takmaya yetecek kadar PCIe hattı olduğundan, sunucu giriş/çıkış bant genişliği bellek bant genişliğine yakın seviyededir.
      Daha pahalı sunucularda PCIe 5.0 gibi daha hızlı ve daha fazla hat bulunur.
      Bu dosya 1 milyar satır olduğu için sıkıştırıldığında yaklaşık 1GB’dır ve atılan ilk çalıştırmadan sonra belleğe gireceğinden bu senaryoda giriş/çıkış bant genişliği önemli değildir.
      GitHub deposunda sıkıştırılmamış hâlinin 12GB olduğu yazıyor; bu da yine giriş/çıkış bant genişliğinin önemli olmadığını doğruluyor.
    • Daniel Lemire’in şu sunumu ilginç: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      Ana fikir, diskin nadiren darboğaz olduğudur.
    • İşletim sistemine ve dosya sistemine bağlı. Girdi dosyası yaklaşık 12GB ve 32GB bellekli bir makinede 5 kez çalıştırılıyor; bu yüzden ilk çalıştırmadan sonra dosyanın tamamı bellekte önbelleğe alınabilir.
      Örneğin Linux’ta ext2 kullanılırsa ilk çalıştırmadan sonra tüm dosyanın önbelleğe alınması olasıdır, ama ZFS’te böyle olmayabilir.
    • En hızlı ayrıştırma için her şeyi RAM’e alıp sondan geriye doğru işlemek açıkça en iyi yol gibi görünüyor.
      Böylece sayılar düşük basamaktan yüksek basamağa doğru gelir; ardından ayırıcı ve string gelir, EOF ya da satır sonu görülene kadar ilerlenir.

  • Kurallara göre gönderilerin tüm girdiler için doğru çalışması gerekiyor, ama create_measurements.sh ile oluşturulan belirli girdiye göre ayarlanabileceği ve muhtemelen ayarlanması gerektiği anlamına geliyor gibi görünüyor.
    Örneğin verilen gözlem istasyonu kümesine özel perfect hash function kullanan bir gönderi hayal edilebilir.

    • Böyle bir gereklilik varsa test verisini örnek veriden farklı yapmak akıllıca olur.
      Böylece aşırı uyumlu optimizasyonların önüne geçilebilir.
    • UTF-8 yüzünden çok daha zorlaşıyor. Ama kuralların ruhunu değil yalnızca metnini izlerseniz, 127’den büyük bir byte algılandığı anda yavaş uygulamaya devretmek yeterli olur.
      127’den büyük byte, çok baytlı bir UTF-8 karakteri anlamına gelir.

  • Eğlence olsun diye awk ile Java arasında hız karşılaştırması yaptım.
    awk -F';' ile istasyon bazında toplam, adet, minimum ve maksimumu biriktirip END kısmında ortalamayı hesaplayarak yazdıran bir betik.

    • PostgreSQL’in file foreign data wrapper’ı ile hız karşılaştırmasını görmek isterim: https://www.postgresql.org/docs/current/file-fdw.html
      file_fdw ile CSV dosyasını dış tablo yapıp GROUP BY station_name ile MIN, AVG, MAX hesaplama yöntemi.
    • ClickHouse local ile çalıştırınca yaklaşık 15,2 saniye çıkıyor.
      clickhouse local içinde file('measurements.txt', 'CSV', 'station String, t Float32') okunup istasyon bazında min, max, avg gruplanıyor ve max_threads = 8 ile çalıştırılıyor.
      Zamanın büyük kısmı dosya ayrıştırmaya gidiyor.
    • sum değişkeni epey büyüyebileceğinden akışlı ortalama kullanmak daha iyi olur.
      Örneğin new_mean = ((n*old_mean)+temp)/(n+1) gibi bir yöntem.

  • İlginç bir meydan okuma ama yalnızca Java’ya özel olması üzücü. İnsanların doğrudan JVM bayt kodunu elle üretmeye başlayacağı zamanı merakla bekliyorum

    • Tartışmaya bakılırsa farklı dillerden gönderimler de var gibi. Go, Rust, Python, C++ vb. var
      [0] https://github.com/gunnarmorling/1brc/discussions
    • Ya da “Java ile yazılmalı” ifadesi “çalıştırmanın başlangıcında JVM kullanılmalı” diye de yorumlanabilir; Java’dan başka bir süreç başlatmak da kesinlikle mümkün

  • Eğlenceli. Advent of Code sonrası etkinliği gibi hissettiriyor
    Diller arası adil bir karşılaştırma olacaksa make ve derleme süresi de dahil edilmeli. Java/Maven’ı birkaç yıldır kullanmıyordum; ./mvnw clean verify indirmesinin ikinci dakikada hâlâ sürdüğünü görünce nedenini yeniden hatırladım

    • Java derleme süresi çok hızlıdır. Şu anda ölçtüğünüz şey internet hızı
      Ayrıca artımlı derleme araçları arasında Gradle daha hızlıdır
    • Derleme süresi dahil edilecekse programlama süresi de dahil edilmeli; ikisi de kodun ömrü boyunca kaç kez çalıştırılacağına bölünmeli
      Programlamayı öğrenmek için harcanan sürenin uygun bir oranı da eklenmeli
      Böyle bir meydan okumada çok saf bir sürümün kazanma ihtimali yüksek olur; bunun hem gerçekçi olmadığını hem de meydan okumanın amacına aykırı olduğunu düşünüyorum
    • Neden clean yaptığınızı anlamıyorum
      Önbelleği çöpe atıp sonra yavaş demek gibi
    • Maven gerekli değil
      Harici bağımlılık kullanılamayacağı yazıyor

  • Çek Teknik Üniversitesi’ndeki C dersinde buna çok benzer bir ödev vardı
    Tüm öğrenci gönderimleri sürekli sıralama tablosunda değerlendiriliyordu; daha iyi not için ek puanlar, fiilen de statü puanı kazanmak isteyen birçok öğrenci onlarca saatini optimizasyona harcadı
 
dlehals2 2024-01-10

Birinci olan 6 saniye sürmüş.. gerçekten şaşırtıcı