ปรับปรุงการประมวลผลสตริงของ serde_json ให้เร็วขึ้น 20%

 (purplesyringa.moe)
2 คะแนน โดย GN⁺ 2024-08-25 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • serde_json ซึ่งถูกใช้งานเสมือนเป็นตัวแยกวิเคราะห์ JSON พื้นฐานของ ecosystem Rust สามารถเพิ่มประสิทธิภาพได้ 10%, 23%, 32% ในเบนช์มาร์กที่มีสตริงจำนวนมาก ด้วยการปรับแต่งภายในเพียงเล็กน้อย
  • การคำนวณตำแหน่งของข้อผิดพลาดถูกเปลี่ยนจากการไล่สแกนส่วนต้นของสตริงโดยตรง มาเป็นการใช้ memchr เพื่อหาจำนวนบรรทัดและตำแหน่งขึ้นบรรทัดใหม่ล่าสุด ทำให้ช่องว่างด้านความเร็วของเส้นทาง error ซึ่งเคยช้ากว่าเส้นทางสำเร็จมากกว่า 2 เท่าลดลง
  • ลูปหลักของการ parse สตริงเปลี่ยนจากการหา \, " และอักขระควบคุมแยกกัน มาเป็นการตรวจพร้อมกันในครั้งเดียวด้วย SWAR ทำให้ได้ latency ต่ำกับสตริงสั้นแม้ไม่มี SIMD จริง
  • การถอดรหัส escape แบบ \u ลดต้นทุนของ branch และ shift ด้วย LUT, จำนวนเต็ม signed และตาราง shift ที่เตรียมไว้ล่วงหน้า ทำให้การ parse JSON ของ War and Peace ฉบับภาษารัสเซียเร็วขึ้นจาก 284 MB/s เป็น 344 MB/s
  • หลังจากนั้นคอขวดที่ย้ายไปอยู่ที่การเข้ารหัส UTF-8 ก็ถูกแก้ด้วย การสร้าง UTF-8 แบบแมนนวล เพื่อหลีกเลี่ยงต้นทุนการ initialize และคัดลอกของ char::encode_utf8 และ Vec::extend_from_slice ทำให้เบนช์มาร์กเดียวกันขึ้นไปถึง 374 MB/s

ทำไมการปรับแต่ง serde_json ถึงให้ผลมาก

  • serde คือเฟรมเวิร์ก serialization/deserialization หลักของ Rust และ serde_json คือชุดทางการสำหรับจัดการ JSON ที่ถูกใช้อย่างแพร่หลาย
  • ณ เวลาที่เผยแพร่ serde_json มี reverse dependency 26,916 รายการ ขณะที่ simd-json มี 66 รายการ
  • เมื่อมีการใช้งานในระดับนี้ แม้การปรับปรุงเล็กน้อยภายใน serde_json ก็สามารถสะสมผลกระทบต่อ ecosystem Rust ได้ทั้งระบบ
  • ในสถานการณ์ที่ผู้ใช้จำนวนมากไม่สามารถเปลี่ยนไปใช้ JSON parser ตัวอื่นได้ง่าย การ optimize แบบความเสี่ยงต่ำภายในไลบรารีเดิมจึงใช้งานได้จริง

การคำนวณตำแหน่งข้อผิดพลาด: จากลูปธรรมดาไปสู่ memchr

  • ในเบนช์มาร์กเส้นทาง error, serde_json ช้ากว่าเส้นทางสำเร็จของข้อมูลชุดเดียวกันมากกว่า 2 เท่า
    • ในชุดข้อมูล canada, citm_catalog, twitter เส้นทาง error ช้ากว่าเส้นทางสำเร็จ -48% ถึง -77%
  • คอขวดคือฟังก์ชัน position_of_index() ที่แปลง index เป็น line/column เพื่อจัดรูปแบบข้อความข้อผิดพลาด
    • implementation เดิมจะวนผ่าน self.slice[..i] ทีละไบต์ และอัปเดต line กับ column ทุกครั้งที่เจอ \n
  • เมื่อลองแยกการคำนวณเป็นสองขั้น ก็สามารถใช้ memchr ได้
    • นับจำนวน \n ใน self.slice[..i] เพื่อหาเลขบรรทัดแบบเริ่มจาก 0
    • หาตำแหน่ง \n ตัวสุดท้าย แล้วนำมาหักออกจาก i เพื่อหาหมายเลขคอลัมน์
  • memchr มี implementation ที่ optimize สำหรับการค้นหาและนับอักขระเดี่ยว และภายในใช้ SIMD
  • หลัง PR #1160 ถูกรวมเข้ามา ประสิทธิภาพของเส้นทาง error ดีขึ้นอย่างมาก
    • เส้นทาง error ของ canada แบบ DOM เพิ่มจาก 122 MB/s เป็น 216 MB/s
    • citm_catalog แบบ struct เพิ่มจาก 195 MB/s เป็น 736 MB/s
    • แม้เส้นทาง error ยังช้ากว่าเส้นทางสำเร็จ แต่ช่องว่างลดลง

การค้นหา string escape: หา 3 เงื่อนไขพร้อมกันในครั้งเดียว

  • ลูปหลักเดิมของการ parse สตริงจะดูตาราง ESCAPE แล้วข้ามไบต์ที่ไม่ใช่ escape ไป
    • escape ที่ต้องจัดการในสตริง JSON คือ \, " และอักขระควบคุม ASCII ที่มีค่าไม่เกิน 0x1F
    • ตามสเปก JSON อักขระควบคุมภายในสตริงไม่ถูกอนุญาต
  • ความพยายามครั้งแรกใช้ memchr2 เพื่อหา \ หรือ " ก่อน แล้วค่อยตรวจอักขระควบคุมแยกต่างหาก
    • ทำให้ต้องวนอ่านสตริง สองรอบ คือรอบเร็วหนึ่งครั้งและรอบช้าอีกหนึ่งครั้ง จึงช้ากว่าเดิม
    • การ vectorize แค่ครึ่งหนึ่งแล้วปล่อยที่เหลือเป็น scalar ไม่ได้นำไปสู่การปรับปรุงโดยรวม
  • ความพยายามครั้งที่สองใช้ memchr2 ร่วมกับ SIMD แบบเขียนเองเพื่อตรวจว่าไม่มีอักขระควบคุม
    • สำหรับสตริงสั้น ต้นทุนของการเรียกฟังก์ชันเลือก implementation ตอนรันไทม์สูงเกินไป
    • สำหรับสตริงยาว ก็ยังมีปัญหาอ่านหน่วยความจำซ้ำสองครั้ง
  • implementation สุดท้ายจึงจัดรูปใหม่ให้หา \, " และอักขระควบคุมได้ใน pass เดียว

ใช้ SWAR เพื่อทำงานใกล้เคียง SIMD

  • เพื่อหลีกเลี่ยงการต้องมีโค้ด SIMD แยกตามแพลตฟอร์ม จึงใช้เทคนิค SWAR(SIMD Within A Register)
    • แทนที่จะใช้ SIMD 128 บิต ก็ปฏิบัติกับ word 64 บิตเสมือนเป็น 8 ไบต์
    • ใช้การคำนวณระดับบิตเพื่อตรวจพร้อมกันว่าแต่ละไบต์ตรงเงื่อนไขหรือไม่
  • การตรวจอักขระควบคุมแปลงเงื่อนไข c >= 0 && c < 0x20 ให้อยู่ในรูปการคำนวณบิต
    • สำหรับกลุ่ม 8 ไบต์ จะตรวจด้วย mask รูปแบบ !c & (c - 0x2020202020202020) & 0x8080808080808080
    • แม้ borrow จากการลบ 64 บิตอาจแพร่ไปยังไบต์ที่สูงกว่า แต่ไม่เป็นปัญหาสำหรับเป้าหมายที่ต้องการหาอักขระควบคุมตัวแรกจากตำแหน่งต่ำสุด
  • \ และ " ก็ตรวจด้วยแนวทางคล้ายกันและรวมเป็นนิพจน์เดียว
    • นิพจน์ทั้งหมดประกอบด้วยการคำนวณบิต 9 ขั้น
    • ถ้าเป็น SIMD บน x86 จะใช้เพียง 7 ขั้น จึงมี throughput สูงกว่า แต่สำหรับสตริงสั้น latency สำคัญกว่า
  • ใน json-benchmark โค้ด SWAR นี้มีประสิทธิภาพดีกว่าโค้ด SIMD จริง
  • สำหรับสตริงที่สั้นมาก SWAR อาจช้ากว่าโค้ด scalar
    • พบ regression แถวสตริงยาวประมาณ 5 อักขระ
    • เพื่อป้องกันแพตเทิร์นที่พบบ่อยอย่างสตริงว่าง "" และ escape ต่อเนื่อง \r\n, \uD801\uDC37 จึงมีการตรวจว่าตัวแรกเป็น escape หรือไม่ก่อนเข้าลูป SWAR
  • ผลของการ optimize การค้นหาสตริงแตกต่างกันไปตามชุดข้อมูล
    • twitter แบบ struct เพิ่มจาก 638 MB/s เป็น 785 MB/s หรือ +23%
    • twitter แบบ DOM เพิ่มจาก 305 MB/s เป็น 335 MB/s หรือ +10%
    • citm_catalog แบบ struct เพิ่มจาก 865 MB/s เป็น 905 MB/s หรือ +5%
    • สตริงว่างยังคงช้าลงไม่เกิน 2% ในบางไมโครบेंช์มาร์ก

การ optimize การถอดรหัส Unicode escape

  • serde_json รองรับทั้งสตริง Unicode แบบดิบและ escape แบบ \u
    • เช่น "🥺" และ "\ud83e\udd7a"
  • การถอดรหัสเลขฐานสิบหกแบบเดิมใช้ LUT 256 ช่องเพื่อแมปอักขระแต่ละตัวให้เป็นค่า 0~15
    • รองรับ '0'..='9', 'A'..='F', 'a'..='f'
    • อักขระไม่ถูกต้องจะถูกทำเครื่องหมายด้วย sentinel value
  • เนื่องจาก escape แบบ \u ต้องอ่านเลขฐานสิบหก 4 หลัก วิธีเดิมจึงมีทั้ง shift, add, compare และ conditional branch ในแต่ละรอบ
  • implementation ที่ปรับปรุงแล้วจะไม่คืน error ในทุกครั้งระหว่างวนลูป แต่ประมวลผลครบทั้ง 4 หลักก่อนแล้วค่อยตรวจความถูกต้อง
  • implementation สุดท้ายใช้ LUT แบบ [i8; 256] และกำหนดให้ digit ที่ไม่ถูกต้องเป็น -1 จากนั้นคำนวณด้วยจำนวนเต็ม 32 บิต
    • ถ้าสำเร็จผลลัพธ์จะไม่ติดลบ และถ้าล้มเหลวผลลัพธ์จะติดลบ
    • บน x86 การโหลดจากหน่วยความจำและ sign extension อาจรวมกันเป็น movsx ได้
  • เพื่อลด latency ของ shift จึงใช้ตารางสองชุด
    • HEX0: ค่าเดิม
    • HEX1: ตารางที่เลื่อนซ้าย 4 บิตไว้ล่วงหน้า
  • จากนั้นจัดรูปเป็น decode_four_hex_digits() ที่ unroll ลูปอย่างชัดเจน
  • การ optimize นี้ทำให้การ parse War and Peace ภาษารัสเซียในรูปแบบ JSON-encoded เร็วขึ้นจาก 284 MB/s เป็น 344 MB/s หรือ 21%

คอขวดที่ UTF-8 encoding และการสร้างแบบแมนนวล

  • หลังจาก optimize การถอดรหัส Unicode escape แล้ว คอขวดได้ย้ายไปอยู่ที่ การเข้ารหัส UTF-8
  • UTF-8 เข้ารหัส codepoint เป็น 1~4 ไบต์ตามความยาว
    • 1 ไบต์: 0xxxxxxx
    • 2 ไบต์: 110xxxxx 10xxxxxx
    • 3 ไบต์: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 ไบต์: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8 ใน Rust standard library เขียนลงบัฟเฟอร์ &mut [u8] ดังนั้นบัฟเฟอร์ต้องมีค่า u8 ที่ถูกต้องอยู่แล้ว
    • จึงไม่สามารถเขียนลงบัฟเฟอร์ที่ยังไม่ได้ initialize ได้โดยตรง
    • เนื่องจาก UTF-8 เป็น encoding ความยาวแปรผัน LLVM จึงลบ zeroization ที่ไม่จำเป็นออกได้ยาก
  • serde_json เดิมใช้วิธี scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • การใช้บัฟเฟอร์ภายในแบบ [0u8; 4] ในทางทฤษฎีอาจช่วย alias analysis ได้
    • แต่ในทางปฏิบัติ LLVM ยังคงสร้างการเรียก memcpy เพราะต้องคัดลอกข้อมูล 1~4 ไบต์ที่มีความยาวแปรผัน
  • เพื่อหลีกเลี่ยงการเรียก memset และ memcpy จึงสร้าง UTF-8 โดยตรง
    • ตัวอัลกอริทึมเองค่อนข้างเรียบง่าย แต่จำเป็นต้องใช้ unsafe
    • เมื่อรวมกับการเปลี่ยนแปลงเล็กน้อยอื่น ๆ เบนช์มาร์ก War and Peace ดีขึ้นเพิ่มจาก 344 MB/s เป็น 374 MB/s หรืออีก +9%

ผลลัพธ์สุดท้าย

  • ในเบนช์มาร์ก JSON ที่มีสตริงจำนวนมาก ประสิทธิภาพของ serde_json ดีขึ้น 10%, 23%, 32% ตามลำดับ
  • เนื่องจากข้อมูล JSON จำนวนมากมีสตริงเป็นสัดส่วนสูง การ optimize นี้จึงอาจส่งผลต่อโค้ด Rust จำนวนมากที่ใช้ serde_json
  • การปรับปรุงเกิดจากการกำจัดคอขวดหลายจุดต่อเนื่องกัน เช่น การคำนวณตำแหน่งข้อผิดพลาด การค้นหา string escape การถอดรหัส Unicode escape และการเข้ารหัส UTF-8

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-08-25
ความคิดเห็นบน Hacker News

  • ทริก UTF-8 ทำให้ค่อนข้างไม่สบายใจ เพราะเคยเห็นการโจมตีแบบทำให้ parser สับสนมาเยอะเกินไป
    ผมใช้ serde เพราะ ความถูกต้อง มากกว่าความเร็ว เลยหวังว่าจะได้ fuzz จนสุดทางด้วยการใส่สตริง UTF-8 ที่ผิดรูปแบบเข้าไปเป็นจำนวนมาก

    • โชคดีที่โครงสร้างของ UTF-8 เรียบง่ายมาก เมื่อเทียบกับ parser ทั่วไป
      ไม่ได้หมายความว่าจะไม่มีบั๊ก แต่ internal state ของ parser ไม่ควรใหญ่ และดูเหมือนว่าจะทำ exhaustive test ได้ด้วย
    • พื้นที่แบบนี้แหละที่อยากเห็นผลจากการรัน fuzzer
    • ถ้ามีตัวอย่างบั๊กประเภทนี้ที่นึกออกทันที ช่วยบอกได้ไหม?

  • เท่มากที่ serde ขยับเร็วขนาดนี้
    เมื่อกี้เพิ่งดู simdutf8 แล้วพบว่า PR สำหรับ การ parse UTF-8 ที่รองรับ SIMD ค้างมาเกือบ 5 ปีแล้ว
    https://github.com/rust-lang/rust/issues/68455

  • อ่านแล้วสนุกดี เพราะบล็อกของคนนี้ให้ ฟีล jart แรงมาก
    ตรงที่ว่า “คงต้องประดิษฐ์ล้อขึ้นมาใหม่ แต่พอคิดดูแล้วมันก็เจ๋งทีเดียว” นี่ไม่แน่ใจว่าพูดจริงหรือประชด
    อ่านแล้วเริ่มหัวเราะเยาะคนเขียน แต่หน้าที่เหลือดูเหมือนจะ self-deprecating ค่อนข้างหนัก

    • คำพูดนั้นน่าจะหมายถึงว่า แนวทาง นั้นค่อนข้างเจ๋ง ไม่ใช่ข้อเท็จจริงที่ว่าต้องประดิษฐ์ล้อใหม่
    • jart หมายถึงอะไร?

  • “การสอน วิธีคิด สำคัญพอ ๆ กับการสอนเขียนโค้ด แต่แทบไม่ค่อยเกิดขึ้น” งั้นเหรอ
    รู้สึกได้ถึงความโอหังที่คิดว่าอีกฝ่ายไม่คิด

    • ผมว่าในประโยคนั้นไม่มีความโอหังนะ
      ไม่ได้สมมติว่าคนอื่นไม่คิด แต่เป็นการสังเกตมากกว่าว่า บทความบล็อกและบทความวิธีใช้ส่วนใหญ่แสดงแค่ผลลัพธ์สุดท้าย แต่ไม่ค่อยแสดงขั้นตอนที่พาไปถึงตรงนั้น
    • ผู้เขียนไม่ได้อ้างแบบนั้น
      การสอนวิธีคิดหมายถึงต้องค้นคว้า และข้ามขั้นตอนนั้นไม่ได้ อีกทั้งการค้นคว้าก็ไม่ได้ทำให้ความรับผิดชอบในการสรุปด้วยตัวเองหายไป
      การข้ามอย่างใดอย่างหนึ่งในสองอย่างนี้ทำได้ง่าย แต่เป็นวิธีที่ผิด

  • serde_json พอ build แบบ debug กับ release อย่างละรอบ dependency ก็กินไป 3GB แล้ว
    ถ้าใช้ serde ในโปรเจกต์ที่ active อยู่ไม่กี่โปรเจกต์ พื้นที่ดิสก์ก็หมด
    ไม่เข้าใจว่าการ parse JSON ทำไมต้องมี dependency 3GB และถึงจะเห็นด้วยกับการใช้โค้ดซ้ำ แต่ dependency ฝั่ง JSON ของ serde ดูค่อนข้างรก
    แค่มี exploit ใน dependency ตัวใดตัวหนึ่ง Rust ecosystem ครึ่งหนึ่งก็เปราะบางแล้ว
    Rust ควรมี JSON ในตัว

    • dependency มีแค่ 5 ตัว และในนั้นตัวหนึ่งเป็น optional ส่วนอีกตัวคือ serde เอง: 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 }
      มีความเป็นไปได้สูงว่าสิ่งที่วัดจริง ๆ ไม่ใช่ “dependency 3GB”
      พูดเหมือนเป็นข้อเท็จจริงโดยไม่มีหลักฐาน เลยมั่นใจไม่ได้ แต่ถ้าให้เดา น่าจะใช้ #[derive(Serialize, Deserialize)] จำนวนมากจนเกิดการ generate โค้ดปริมาณมาก แล้วไปวัดขนาดทั้งไดเรกทอรี target
      การ build แบบง่าย ๆ อย่างที่คอมเมนต์อื่น ๆ แสดงออกมา อยู่ระดับไม่กี่สิบ MB
    • ผมมองว่าการใส่ JSON เข้าไปใน Rust ในตัวไม่ใช่แนวทางที่สมเหตุสมผล
      นั่นเป็นแค่วิธีดึง ความบวม เข้ามา และ standard library ก็ไม่ได้ต่างจาก crate อื่น นอกจากการรับประกันเสถียรภาพ จึงไม่มีข้อดี
      สุดท้ายมีผลแค่ผูก release cycle ของไลบรารีเข้ากับ release cycle ของ compiler
      จริง ๆ แล้วเมื่อก่อน rustc-serialize ก็ใกล้เคียงกับของในตัว และ Rust เคยลองแนวทางนั้นมาแล้ว
      อีกอย่าง serde_json ในสถานะเริ่มต้นก็ไม่ได้ใหญ่
      ทั้ง serde_json และ serde ไม่ได้ใหญ่ และทั้งคู่ยังคง MSRV ที่ต่ำมากซึ่ง crate อื่น ๆ รองรับได้ไม่ดี ดังนั้นโดยพื้นฐานแล้วจึงแทบมี dependency เยอะไม่ได้ด้วยซ้ำ
    • dependency bloat เป็นปัญหาทั่วทั้ง Rust
      dependency tree ของโปรเจกต์ Rust ที่มีขนาดพอสมควรจะกลายเป็นสิ่งที่ค่อนข้างน่ากลัวอย่างรวดเร็ว และการ audit dependency ทั้งหมดนี้แทบเป็นไปไม่ได้ในทางปฏิบัติ อีกทั้งความน่าเชื่อถือของหลายตัวก็ต่ำ
      หลังจากทำงานกับ Rust มาหลายปี ผมคงไม่แตะ Rust อีกจนกว่า ecosystem จะโตเต็มที่กว่านี้มาก
      ความเป็นผู้ใหญ่แบบนั้นคงต้องมาจากการที่บริษัทใหญ่ ๆ adopt กันในวงกว้าง ไม่อย่างนั้นก็อาจใช้เฉพาะกับโปรเจกต์ no-std, no-deps หรือโปรเจกต์ที่เป็นตัวแทน C ล้วน ๆ
      แต่ถ้า Zig เสถียรแล้ว ก็อาจเบียด Rust ออกจาก use case นี้ได้เหมือนกัน
    • Rust พ่น debug information ออกมามากผิดปกติ
      มันใหญ่แบบประหลาดเกินไปจนเดาว่าน่าจะเป็นบั๊ก
      ไม่ว่าจะ compile อะไรก็ตาม โฟลเดอร์ target จะสะสมเป็นระดับกิกะไบต์ แต่ก็ไม่ได้เป็นตัวแทนของ artifact สุดท้ายหลังลบ debug information ออก หรืออย่างน้อยใช้การตั้งค่าที่ละเอียดน้อยลง
    • ถ้าเป็นโปรเจกต์ที่มีขนาดพอสมควร โฟลเดอร์ target ดูเหมือนจะมีอย่างน้อยหลาย GB อยู่เสมอจริง ๆ