serde_json’da dize işleme %20 hızlandı

 (purplesyringa.moe)
2 puan yazan GN⁺ 2024-08-25 | 1 yorum | WhatsApp'ta paylaş
  • Rust ekosisteminde fiilen varsayılan JSON ayrıştırıcısı gibi kullanılan serde_json, dize ağırlıklı benchmark’larda yalnızca küçük iç optimizasyonlarla %10, %23, %32 performans artışı elde etti
  • Hata konumu hesaplaması, dizenin başını doğrudan taramak yerine satır sayısını ve son satır sonunu bulmak için memchr kullanacak şekilde değiştirildi; böylece başarılı yoldan 2 kattan fazla yavaş olan hata yolu farkı azaldı
  • Dize ayrıştırmanın çekirdek döngüsü \, " ve denetim karakterlerini ayrı ayrı aramak yerine SWAR ile tek seferde denetliyor; gerçek SIMD olmadan bile kısa dizelerde düşük gecikme sağlıyor
  • \u escape çözümleme, LUT, işaretli tamsayılar ve önceden kaydırılmış tablolarla dallanma ve shift maliyetini azalttı; Rusça War and Peace JSON ayrıştırması 284 MB/s’den 344 MB/s’ye hızlandı
  • Sonrasında darboğaz hâline gelen UTF-8 kodlama, char::encode_utf8 ve Vec::extend_from_slice kaynaklı başlatma/kopyalama maliyetlerinden kaçınan elle UTF-8 üretimi ile ele alındı; aynı benchmark 374 MB/s’ye çıktı

serde_json optimizasyonu neden büyük etki yaratıyor?

  • serde, Rust’ın önde gelen serileştirme/ters serileştirme framework’üdür; serde_json ise JSON işleme için resmi eşleşme olarak yaygın biçimde kullanılır
  • Yayın anı itibarıyla serde_json için ters bağımlılık sayısı 26.916, simd-json için ise 66 idi
  • Bu ölçekte kullanımda, serde_json içindeki küçük iyileştirmeler bile Rust ekosistemi genelinde birikimli etki yaratabilir
  • Birçok kullanıcının başka bir JSON ayrıştırıcıya kolayca geçmediği durumda, mevcut kütüphane içindeki düşük riskli optimizasyonlar pratiktir

Hata konumu hesaplaması: basit döngüden memchr’ye

  • Hata yolu benchmark’ında serde_json, aynı verinin başarılı yoluna kıyasla 2 kattan fazla yavaştı
    • canada, citm_catalog, twitter veri kümelerinde hata yolu, başarılı yola göre %48~%77 daha yavaştı
  • Darboğaz, hata mesajı biçimlendirmesi için indeksi line/column değerine çeviren position_of_index() fonksiyonuydu
    • Eski uygulama self.slice[..i] kısmını bayt bayt dolaşıyor ve \n gördükçe line ile column değerlerini güncelliyordu
  • Hesaplama iki aşamaya ayrılınca memchr uygulanabiliyor
    • self.slice[..i] içindeki \n sayısını sayarak 0 tabanlı line numarası bulunuyor
    • Son \n konumu bulunup i değerinden çıkarılarak column numarası elde ediliyor
  • memchr, tek karakter arama ve sayma için optimize edilmiş bir uygulama sunar; içeride SIMD kullanır
  • PR #1160 birleştirildikten sonra hata yolu performansı belirgin biçimde iyileşti
    • canada DOM için hata yolu 122 MB/s’den 216 MB/s’ye çıktı
    • citm_catalog struct için 195 MB/s’den 736 MB/s’ye çıktı
    • Hata yolu hâlâ başarılı yoldan yavaştı, ancak fark azaldı

Dize escape araması: üç koşulu tek seferde bulmak

  • Dize ayrıştırmanın eski çekirdek döngüsü, ESCAPE tablosuna bakarak escape olmayan baytları atlıyordu
    • JSON dizelerinde işlenmesi gereken escape hedefleri \, " ve 0x1F altındaki ASCII denetim karakterleridir
    • JSON standardına göre dize içinde denetim kodlarına izin verilmez
  • İlk deneme, memchr2 ile önce \ veya " bulup ardından denetim karakterlerini ayrıca kontrol etme yöntemiydi
    • Dizeyi hızlı bir kez ve yavaş bir kez olmak üzere iki kez dolaştığı için eskisinden yavaştı
    • Yalnızca basit yarıyı vektörleştirip kalanı skaler bırakmak genel bir iyileşmeye dönüşmedi
  • İkinci deneme, memchr2 ve denetim karakteri olmadığını kontrol eden elle yazılmış SIMD yapısıydı
    • Kısa dizelerde runtime seçim fonksiyonu çağrısının maliyeti yük oluyordu
    • Uzun dizelerde belleği iki kez okuma sorunu devam ediyordu
  • Nihai uygulama, \, " ve denetim karakterlerini tek geçişte bulacak şekilde toparlandı

SWAR ile SIMD’ye yakın işleme

  • Platforma özel SIMD kodu eklememek için SWAR (SIMD Within A Register) tekniği kullanıldı
    • 128 bit SIMD yerine 64 bit word, 8 bayt gibi ele alınıyor
    • Bit işlemleriyle her baytın koşulu sağlayıp sağlamadığı aynı anda denetleniyor
  • Denetim karakteri kontrolü, c >= 0 && c < 0x20 koşulunun bit işlemleri biçimine dönüştürülmesiyle işleniyor
    • 8 baytlık gruplarda !c & (c - 0x2020202020202020) & 0x8080808080808080 biçiminde bir maskeyle kontrol ediliyor
    • 64 bit çıkarma işlemindeki borrow daha yüksek baytlara yayılabilir; ancak amaç en düşük konumdaki denetim karakterini bulmak olduğundan bu sorun yaratmıyor
  • \ ve " de benzer yöntemle denetlenip tek ifadede birleştirildi
    • İfadenin tamamı 9 bit işleminden oluşuyor
    • x86 SIMD ile 7 işlem gerekirdi; bu yüzden throughput daha düşük olsa da kısa dizelerde gecikme daha önemlidir
  • json-benchmark üzerinde bu SWAR kodu gerçek SIMD kodundan daha verimliydi
  • Çok kısa dizelerde SWAR, skaler koddan yavaş olabilir
    • Yaklaşık 5 karakterlik dizelerde gerileme görüldü
    • Boş dize "" ve ardışık escape \r\n, \uD801\uDC37 gibi yaygın kalıpları korumak için SWAR döngüsüne girmeden önce ilk karakterin escape olup olmadığı kontrol ediliyor
  • Dize arama optimizasyonunun sonuçları veri kümesine göre değişti
    • twitter struct 638 MB/s’den 785 MB/s’ye, yani %23 arttı
    • twitter DOM 305 MB/s’den 335 MB/s’ye, yani %10 arttı
    • citm_catalog struct 865 MB/s’den 905 MB/s’ye, yani %5 arttı
    • Boş dize, belirli bir mikro benchmark’ta hâlâ %2 içinde yavaşladı

Unicode escape çözümleme optimizasyonu

  • serde_json, ham Unicode dizeleri de \u escape’lerini de işler
    • Örnek: "🥺" ve "\ud83e\udd7a"
  • Eski hex çözümleme, her karakteri 0~15 değerine eşlemek için 256 öğeli LUT kullanıyordu
    • '0'..='9', 'A'..='F', 'a'..='f' aralıklarını işliyordu
    • Geçersiz karakterler sentinel değerle işaretleniyordu
  • \u escape’i 4 hex digit okuduğundan, eski yöntemde her yinelemede shift, add, karşılaştırma ve koşullu dallanma bulunuyordu
  • İyileştirilmiş uygulama, döngü içinde her seferinde hata döndürmek yerine 4 basamağın tamamını işledikten sonra geçerliliği kontrol ediyor
  • Nihai uygulama, [i8; 256] LUT içinde geçersiz digit’i -1 yapıyor ve hesaplamayı 32 bit tamsayıyla gerçekleştiriyor
    • Başarılı olduğunda sonuç negatif olmuyor; başarısız olduğunda negatif oluyor
    • x86’da bellek yükleme ve sign extension movsx ile birleştirilebiliyor
  • Shift gecikmesini azaltmak için iki tablo kullanılıyor
    • HEX0: özgün değer
    • HEX1: değeri önceden 4 bit sola kaydırılmış tablo
  • Döngüyü açıkça unroll eden decode_four_hex_digits() uygulamasıyla düzenlendi
  • Bu optimizasyon, Rusça War and Peace’i JSON-encoded biçimde ayrıştırma performansını 284 MB/s’den 344 MB/s’ye çıkararak %21 iyileştirdi

UTF-8 kodlama darboğazı ve elle üretim

  • Unicode escape çözümlemeden sonra darboğaz UTF-8 kodlamaya kaydı
  • UTF-8, codepoint’i uzunluğa göre 1~4 bayt olarak kodlar
    • 1 bayt: 0xxxxxxx
    • 2 bayt: 110xxxxx 10xxxxxx
    • 3 bayt: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 bayt: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • Rust standart kütüphanesindeki char::encode_utf8, &mut [u8] buffer’a yazdığı için buffer’ın hâlihazırda geçerli u8 değerleri içermesi gerekir
    • Başlatılmamış buffer’a doğrudan yazılamaz
    • UTF-8 değişken uzunluklu bir kodlama olduğundan LLVM’in gereksiz zeroization işlemini kaldırması zordur
  • serde_json, scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes()) yöntemiyle işliyordu
    • Yerel [0u8; 4] buffer kullanıldığında teorik olarak alias analizinin yardımcı olması mümkün
    • Pratikte ise 1~4 baytlık değişken uzunluklu kopyalama nedeniyle LLVM bir memcpy çağrısı üretiyor
  • memset ve memcpy çağrılarından kaçınmak için UTF-8 doğrudan üretildi
    • Algoritmanın kendisi basit olsa da unsafe gerekiyordu
    • Birkaç küçük değişiklikle birlikte War and Peace benchmark’ı 344 MB/s’den 374 MB/s’ye çıkarak ek %9 iyileşti

Nihai sonuç

  • Dize ağırlıklı JSON benchmark’larında serde_json performansı sırasıyla %10, %23, %32 iyileşti
  • Birçok JSON verisi bol miktarda dize içerdiğinden, bu optimizasyon serde_json kullanan Rust kodlarının geneli üzerinde etkili olabilir
  • İyileştirme; hata konumu hesaplaması, dize escape araması, Unicode escape çözümleme ve UTF-8 kodlama gibi farklı darboğazların sırayla ortadan kaldırılmasıyla gerçekleştirildi

İlgili okumalar

1 yorum

 
GN⁺ 2024-08-25
Hacker News yorumları

  • UTF-8 hilesi, parser karıştırma saldırılarını çok gördüğüm için beni epey tedirgin ediyor
    serde’yi hızdan çok doğruluk için kullanıyorum; umarım hatalı UTF-8 dizgileriyle ağzına kadar doldurup sonuna kadar fuzz etmişlerdir

    • Neyse ki UTF-8’in yapısı ortalama bir parser’a kıyasla çok basit
      Bu, bug yok demek değil; ama parser’ın iç durumu büyük olmamalı ve exhaustive test de mümkün görünüyor
    • Tam da böyle alanlarda fuzzer çalıştırmanın sonuçlarını görmek isterim
    • Bu tür bug’lardan aklına hemen gelen bir örnek varsa paylaşabilir misin?

  • serde’nin bu kadar hızlı ilerlemesi harika
    Az önce simdutf8’e bakıyordum; SIMD destekli UTF-8 parsing PR’ının neredeyse 5 yıldır beklediğini fark ettim
    https://github.com/rust-lang/rust/issues/68455

  • Bu kişinin blogunda güçlü bir jart havası sezdim, okuması keyifliydi
    “Tekerleği yeniden icat etmemiz gerekecek, ama düşününce bu epey hoş” kısmı ciddi mi ironi mi anlayamadım
    Okuyup yazara gülerek kahkaha atmaya başladım, ama sayfanın geri kalanı epey güçlü bir öz eleştiri gibi görünüyor

    • Bence orada hoş olan şey, tekerleği yeniden icat etmek zorunda olmak değil, yaklaşımın kendisi
    • jart ne demek?

  • “Düşünmeyi öğretmek, kodlamayı öğretmek kadar önemlidir ama neredeyse hiç yapılmaz” ha
    Karşı tarafın düşünmediğini varsayan bir kibir hissediyorum

    • O cümlede kibir olduğunu sanmıyorum
      Başkalarının düşünmediğini varsaymaktan çok, çoğu blog yazısı ve kullanım yazısının yalnızca nihai sonucu gösterdiği, oraya giden adımları ise çoğu zaman göstermediği gözlemine benziyor
    • Yazar böyle bir iddiada bulunmuyor
      Düşünmeyi öğretmek; araştırma yapman gerektiği, o adımı atlayamayacağın ve araştırma yapmış olmanın kendi sonucuna varma sorumluluğunu ortadan kaldırmadığı anlamına geliyor
      İkisinden birini atlamak kolaydır ama yanlış yoldur

  • serde_json’da debug build ve release build’i birer kez alınca bağımlılıklar 3GB ediyor
    Birkaç aktif projede serde kullanırsan disk alanın tükeniyor
    JSON parsing için neden 3GB bağımlılık gerektiğini bilmiyorum; kod yeniden kullanımına karşı değilim ama serde’nin JSON tarafındaki bağımlılıklar epey dağınık görünüyor
    O bağımlılıklardan birinde tek bir exploit çıksa Rust ekosisteminin yarısı zafiyetli hale gelir
    Rust’ta JSON yerleşik olmalı

    • Bağımlılık sadece 5 tane; bunlardan biri opsiyonel, biri de serde’nin kendisi: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      3GB bağımlılık derken gerçekte ölçtüğün şeyin bu olmaması çok muhtemel
      Kanıt olmadan gerçekmiş gibi söylediğin için emin olamıyorum; ama tahminimce çok fazla #[derive(Serialize, Deserialize)] kullanıldığı için büyük miktarda kod üretilmiş ve ardından tüm target dizininin boyutunu ölçüyorsun
      Basit bir build, diğer yorumların gösterdiği gibi onlarca MB düzeyinde çıkıyor
    • Rust’a JSON’u yerleşik eklemenin makul bir yaklaşım olduğunu düşünmüyorum
      Bu yalnızca şişkinliği içeri çekmenin bir yolu olur; standart kütüphane, kararlılık garantisi dışında diğer crate’lerden farklı olmadığı için bir avantaj sağlamaz
      Sonuçta yalnızca kütüphane yayın döngüsünü compiler yayın döngüsüne bağlamış olursun
      Aslında eskiden rustc-serialize yerleşiğe yakındı ve Rust bu yolu zaten denedi
      Ayrıca varsayılan halde serde_json büyük değil
      Ne serde_json ne de serde büyük; ikisi de diğer crate’lerin pek iyi desteklemediği çok düşük bir MSRV’yi koruyor, bu yüzden pratikte çok fazla bağımlılığa sahip olmaları da mümkün değil
    • Bağımlılık şişkinliği Rust genelinde bir sorun
      Biraz ölçekli herhangi bir Rust projesinin bağımlılık ağacı kısa sürede epey korkunç hale geliyor; tüm bu bağımlılıkları denetlemek gerçekçi değil ve önemli bir kısmına duyulan güven de düşük
      Birkaç yıl Rust ile çalıştıktan sonra, ekosistem çok daha olgunlaşana kadar Rust’a tekrar dokunacağımı sanmıyorum
      Bu olgunlaşma büyük ölçekli kurumsal benimsemeyle gelecek; yoksa ancak no-std, no-deps, saf C alternatifi projelerde kullanırım
      Yine de Zig kararlı hale gelirse bu kullanımda bile Rust’ı yerinden edebilir
    • Rust anormal derecede fazla debug bilgisi üretiyor
      O kadar tuhaf biçimde büyük ki bunun basitçe bir bug olacağını tahmin ediyorum
      Ne derlersen derle target klasöründe gigabaytlar birikiyor; ama bu, debug bilgisi kaldırılmış ya da en azından daha az ayrıntılı ayarlar kullanılmış nihai çıktıyı temsil etmiyor
    • Belli bir ölçeği olan projelerde target klasörü kelimenin tam anlamıyla her zaman en az birkaç GB oluyor gibi