simdjson - JSON’u GB/sn düzeyinde ayrıştırma

 (github.com)
19 puan yazan xguru 2020-08-12 | 4 yorum | WhatsApp'ta paylaş

  • SIMD komut setini kullanarak mevcut ayrıştırıcılardan 2,5 kat daha hızlı ayrıştırma

  • Çalışma zamanında CPU’ya göre optimize edilmiş ayrıştırıcının otomatik seçimi: Haswell (AVX2) / Westmere (SSE4.2) / ARM64 / diğer 64 bit

  • Tam JSON ve UTF-8 doğrulama desteği

  • Tek bir .h + .cpp dosyası

  • RapidJSON’a kıyasla %25, sajson’a kıyasla %50 daha az komut seti kullanımı

İlgili okumalar

4 yorum

 
novemberoscar 2020-08-12

Görünüşe göre çeşitli binding / portlar var

  • ZippyJSON: simdjson projesi için Swift binding'leri.

  • libpy_simdjson: libpy kullanan, simdjson için yüksek hızlı Python binding'leri.

  • pysimdjson: simdjson projesi için Python binding'leri.

  • simdjson-rs: Rust portu.

  • simdjson-rust: Rust wrapper'ı (binding'ler).

  • SimdJsonSharp: .NET Core için C# sürümü (binding'ler ve tam port).

  • simdjson_nodejs: simdjson projesi için Node.js binding'leri.

  • simdjson_php: simdjson projesi için PHP binding'leri.

  • simdjson_ruby: simdjson projesi için Ruby binding'leri.

  • fast_jsonparser: simdjson projesi için Ruby binding'leri.

  • simdjson-go: Golang assembly kullanan Go portu.

rcppsimdjson: R binding'leri.
 
xguru 2020-08-12

Rust sürümü - https://github.com/simd-lite/simd-json

QCon'da geliştiricinin sunum içeriği "JSON'u Gerçekten Çok Hızlı Ayrıştırmak: Öğrenilen Dersler"

https://www.youtube.com/watch?v=wlvKAT7SZIQ
 
kunggom 2020-08-13

Bağlantısı verilen konuşma videosunun dökümü:

https://www.infoq.com/presentations/simdjson-parser/

Bunu nasıl bu kadar hızlı yapabildiklerini merak edip okudum; gerçekten de türlü türlü kara büyünün bir araya gelmiş hali gibi görünüyor. Ana noktaları kabaca şöyle özetleyebilirim.

[Giriş]

Çoğu JSON ayrıştırma kütüphanesi, diskin sıralı okuma hızından daha yavaştır

  • Benim (konuşmacı Daniel Lemire) sistem sürücümde büyük metin dosyalarını sıralı okuma hızı 2.2 GB/s, ama başlıca JSON kütüphanelerinin ayrıştırma hızı buna yetişemiyordu.

  • 1 GB/s’yi aşan ayrıştırma hızına sahip kütüphane pek azdı; biz de kendimiz yapmaya karar verdik.

  • Sonuç olarak, disk bant genişliğinin tamamını kullanabilen bir işleme hızına ulaştık. Hesaplayınca, girişteki her 1 bayt için CPU’da yalnızca 1.5 çevrim harcamış olduk. Bunu nasıl başardık?

[Çeşitli ilkeler]

Dallanma ifadelerinden olabildiğince kaçının

  • Örneğin rastgele sayıları bir diziye koyan basit bir koda, sayının tek olup olmadığını kontrol eden tek bir if ekleseniz bile kod 5 kat yavaşlar. Bunun nedeni, CPU dallanma tahmini başarısız olduğunda maliyetin yüksek olmasıdır.

  • Yukarıda verilen kodda if ifadesi bit işlemleriyle kaldırılırsa hız neredeyse eski haline döner.

  • Kodu tekrar tekrar çalıştırırsanız dallanma tahmininin doğruluğu artabilir ve performans kaybı azalabilir, ama bu sonuçta deterministik olmayan bir davranıştır; yani dallanma tahmini devreye girdiğinde performansı öngörmek ya da ölçmek zorlaşır.

Daha geniş word’ler kullanmak için SIMD’den yoğun biçimde yararlanın

  • SIMD komutları kullanıldığında 64 bitten daha geniş word register’ları kullanılabilir; böylece çevrim başına daha fazla veri işlenebilir. (Örneğin SSE ve NEON 128 bit, AVX ise 256 bit.) Bu yüzden mümkün olduğunca SIMD’yi yoğun biçimde kullandılar. Giriş verisinin her 1 baytı için yalnızca 1.5 çevrim kullanabilmelerinin sırrı buydu.

  • SIMD kullanmak için belirli işlemcilere bağımlı intrinsic function’lar kullandılar. Assembly dilini doğrudan kullanmak ise önerilmiyor.

Bellek/nesne tahsisinden kaçının

  • simdjson’da JSON verisi tek bir uzun bant gibi ele alınıyor ve veriler yeniden kullanılıyor. Yani string’ler ya da sayılar için ayrı ayrı bellek ayırmak yerine her şey doğrusal biçimde işleniyor. Bu yaygın bir numara.

Performansı sürekli ölçün

  • Geliştirme benchmark odaklı yapıldı. CI sistemlerinde performans benchmark’ları da yer alıyor.

  • Bu arada CPU yoğun bir iş yaparken işlemcinin çalışma frekansının sürekli değiştiğini akılda tutmak gerekir.

[Gerçek örnekler]

Örnek 1: Geçerli UTF-8 olup olmadığını doğrulamak

  • Girilen rastgele verinin geçerli UTF-8 code point’lerinden oluşup oluşmadığını doğrulamak, genelde çok sayıda dallanma içeren bir iştir.

  • Biz, SIMD ile 32 baytlık veriyi en fazla 20 çevrimde, hiç dallanma olmadan geçerli UTF-8 mi diye doğrulayan bir yöntem geliştirdik.

  • UTF-8 baytlarının tamsayı değeri en fazla 244 olabilir; bu yüzden SIMD komutuyla veriyi 256 bitlik bir register’a koyup her bayttan 244 tamsayısını saturation arithmetic ile çıkarıyor, sonra da sıfır olmayan bir değer kalıp kalmadığını kontrol ediyorsunuz.

  • Bu yöntem, dallanma kullanan yönteme göre 20 kattan daha hızlı!

Örnek 2: Karakter türlerini sınıflandırmak

  • JSON ayrıştırmak için virgül, iki nokta, parantez, boşluk gibi çeşitli karakterleri türlerine göre sınıflandırmak gerekir.

  • x86-64 ve ARM NEON’da, 16 baytlık lookup table’a tek seferde bakabilen komutlar vardır.

  • 1 baytı üst 4 bit ve alt 4 bit olarak ayırıp, önceden hazırlanmış 2 lookup table’ı ayrı ayrı uyguladıktan sonra sonuçları AND işleminden geçirirsiniz.

  • Kod biraz kirli görünebilir ama yalnızca 5 komutla, dallanma olmadan 16 karakter sınıflandırılabilir.

Örnek 3: Escape karakterlerini tespit etmek

  • Ters eğik çizgi (\) ile başlayan escape karakterlerini dallanma olmadan tespit etmek mümkün mü? Özellikle ters eğik çizginin kendisini escape etmek için peş peşe ters eğik çizgiler geldiği durumları da ele almak gerekir.

  • Böyle durumlarda yalnızca tek numaralı ters eğik çizgilere bakmanın işe yaradığı bir numara var.

  • Çift konumları ve tek konumları gösteren bitmask’leri sabit olarak tutup, karmaşık bit işlemlerinden geçirerek escape karakterleri dallanma olmadan ayıklayabilirsiniz.

  • Escape edilmiş tırnakları ayıkladıktan sonra geriye, string’i gösteren tırnaklar kalır.

  • Böyle elde edilen tırnak konumlarını bir bitmask olarak tutup art arda xor bit işlemleri uygularsanız, string konumlarını gösteren bir bitmask elde edersiniz. Bu kısım çoğu işlemcide tek komutla yapılabilir.

  • Bit kümelerini string konumlarıyla eşleştirmede de bazı numaralar var ama zaman olmadığı için geçiyorum.

Örnek 4: Sayı ayrıştırmak

  • Sayı ayrıştırmak son derece pahalı bir iştir. İyi optimize edilmiş bir C fonksiyonuyla kayan noktalı sayı ayrıştırma benchmark’ı yapıldığında 0.09 GB/s gibi akıl almaz derecede düşük bir hız çıktı. Bu açık bir darboğazdı.

  • Sayı ayrıştıran kodların çoğu genellikle veriyi bir seferde bayt bayt işler. Bu asla hızlı değildir.

  • 8 karakteri alıp tek bir 64 bit tamsayıya dönüştürün, ardından konuşmacının bir cumartesi gecesi geç saatlerde bulduğu özel bir formüle sokun; böylece bu 8 karakterin art arda gelen 8 basamaklı bir sayı olup olmadığını anlayabilirsiniz. Bu özellikle çok basamaklı sayıların ayrıştırılmasının daha uzun sürmesi nedeniyle önemlidir.

  • Stack Overflow’da 8 basamaklı tamsayıyı hızlı ayrıştıran bir kod parçası da varmış. SIMD ile biraz daha iyileştirilebilir, ama asıl önemli olan bu şekilde bir seferde çok veri işleme stratejisine dair fikir edinmek.

[Diğerleri]

Runtime dispatch

  • Donanıma bağımlı kod çok fazla olduğundan her işlemci için optimize edilmiş fonksiyonlar ortaya çıkıyor; ama çalışma anında işlemci türüne uygun fonksiyonu seçip çalıştırmak oldukça zordu.

  • Bunun nesi zor diye anlamayabilirsiniz, ama asıl mesele bunu derleyici türünden bağımsız, taşınabilir kodla gerçekleştirmekti. Bazı derleyicilerde hata vardı; ayrıca dil düzeyinde de bunun için özel bir destek yoktu.

  • Bu nokta önemliydi, çünkü simdjson diğer projelere kolayca entegre edilebilen, tek header dosyasından oluşan açık kaynak bir kütüphane.

Diğer

  • Çeşitli dillerde kullanılabilmesi için wrapper’ları var.

  • Bir Rust portu var; Go ve C# portları da hazırlanıyor, ama Java portu yok.

  • Bu projede kullanılan çeşitli matematiksel formüller ortak yazar Geoff Langdale ile birlikte geliştirildi ve konuyla ilgili bir makale VLDB Journal’da yayımlandı. ( https://doi.org/10.1007/s00778-019-00578-5 )
 
xguru 2020-08-13

Vay canına, çok keyifle okudum. Teşekkürler!