simdjson - แยกวิเคราะห์ JSON ระดับ GB/วินาที

 (github.com)
19 คะแนน โดย xguru 2020-08-12 | 4 ความคิดเห็น | แชร์ทาง WhatsApp

  • ใช้ชุดคำสั่ง SIMD เพื่อแยกวิเคราะห์ได้เร็วกว่า parser แบบเดิม 2.5 เท่า

  • เลือก parser ที่ปรับแต่งเหมาะกับ CPU แต่ละรุ่นโดยอัตโนมัติขณะรันไทม์: Haswell (AVX2)/Westmere (SSE4.2)/ARM64/64 บิตอื่น ๆ

  • รองรับการตรวจสอบความถูกต้องของ JSON และ UTF-8 แบบสมบูรณ์

  • มีเพียงไฟล์ .h + .cpp อย่างละหนึ่งไฟล์

  • ใช้ชุดคำสั่งเพียง 25% เมื่อเทียบกับ RapidJSON และ 50% เมื่อเทียบกับ sajson

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

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

 
novemberoscar 2020-08-12

มี binding / port อยู่หลากหลายเลยนะ

  • ZippyJSON: Swift bindings สำหรับโปรเจ็กต์ simdjson.

  • libpy_simdjson: Python bindings ความเร็วสูงสำหรับ simdjson โดยใช้ libpy.

  • pysimdjson: Python bindings สำหรับโปรเจ็กต์ simdjson.

  • simdjson-rs: พอร์ตสำหรับ Rust.

  • simdjson-rust: Rust wrapper (bindings).

  • SimdJsonSharp: เวอร์ชัน C# สำหรับ .NET Core (ทั้ง bindings และ full port).

  • simdjson_nodejs: Node.js bindings สำหรับโปรเจ็กต์ simdjson.

  • simdjson_php: PHP bindings สำหรับโปรเจ็กต์ simdjson.

  • simdjson_ruby: Ruby bindings สำหรับโปรเจ็กต์ simdjson.

  • fast_jsonparser: Ruby bindings สำหรับโปรเจ็กต์ simdjson.

  • simdjson-go: พอร์ตสำหรับ Go ที่ใช้ Golang assembly.

rcppsimdjson: R bindings.
 
xguru 2020-08-12

เวอร์ชัน Rust - https://github.com/simd-lite/simd-json

เนื้อหาการบรรยายของนักพัฒนาที่งาน QCon "Parsing JSON Really Quickly: Lessons Learned"

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

บันทึกถอดเสียงของวิดีโอบรรยายที่ลิงก์ไว้:

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

พอสงสัยว่าทำไมถึงทำความเร็วได้ขนาดนี้เลยลองอ่านดู ก็รู้สึกได้ว่ามันแทบจะเป็นผลึกของสารพัดมนตร์ดำเลยทีเดียว สรุปประเด็นคร่าว ๆ ได้ดังนี้

[บทนำ]

ไลบรารีพาร์ส JSON ส่วนใหญ่ช้ากว่าความเร็วการอ่านแบบลำดับของไดรฟ์

  • บน system drive ของผม (ผู้บรรยาย Daniel Lemire) ความเร็วในการอ่านไฟล์ข้อความขนาดใหญ่แบบลำดับอยู่ที่ 2.2 GB/s แต่ความเร็วในการพาร์สของไลบรารี JSON หลัก ๆ ตามไม่ทัน

  • เนื่องจากแทบไม่มีไลบรารีไหนที่พาร์สได้เกิน 1 GB/s เราเลยตัดสินใจทำขึ้นมาเอง

  • ผลลัพธ์คือเราทำอัตราการประมวลผลได้จนใช้แบนด์วิดท์ของไดรฟ์ได้เต็มที่ คำนวณแล้วใช้ CPU แค่ 1.5 cycle ต่อข้อมูลนำเข้า 1 ไบต์เท่านั้น ทำได้อย่างไร?

[หลักการต่าง ๆ]

หลีกเลี่ยงคำสั่งแตกแขนงให้มากที่สุด

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

  • ถ้าเอา if ออกจากโค้ดตัวอย่างข้างต้นด้วยการใช้ bit operation ความเร็วจะแทบกลับไปเท่าเดิม

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

ใช้ SIMD อย่างเต็มที่เพื่อใช้ word ที่กว้างขึ้น

  • เมื่อใช้คำสั่ง SIMD จะสามารถใช้รีจิสเตอร์ที่กว้างกว่า word 64 บิตได้ ทำให้ประมวลผลข้อมูลได้มากขึ้นใน 1 cycle (เช่น SSE และ NEON เป็น 128 บิต, AVX เป็น 256 บิต) ดังนั้นจึงพยายามใช้ SIMD ให้มากที่สุดเท่าที่ทำได้ นี่คือเคล็ดลับที่ทำให้ใช้ได้เพียง 1.5 cycle ต่อข้อมูลนำเข้า 1 ไบต์
  • เพื่อใช้ SIMD เราใช้ intrinsic function ที่ผูกกับโปรเซสเซอร์บางชนิด ไม่แนะนำให้ใช้ assembly โดยตรง

หลีกเลี่ยงการจัดสรรหน่วยความจำ/อ็อบเจ็กต์

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

วัดประสิทธิภาพอย่างต่อเนื่อง

  • พัฒนาแบบ Benchmark-driven และใน CI ของเราก็รวม performance benchmark ไว้ด้วย

  • อีกอย่าง ถ้าจะทำงานที่ใช้ CPU หนัก ๆ ต้องจำไว้ว่า operating frequency ของ CPU เปลี่ยนอยู่ตลอดเวลา

[ตัวอย่างจริง]

ตัวอย่าง 1: ตรวจสอบว่าเป็น UTF-8 ที่ถูกต้องหรือไม่

  • งานตรวจสอบว่าข้อมูลใด ๆ ที่รับเข้ามาเป็น code point ของ UTF-8 ที่ถูกต้องหรือไม่นั้น โดยทั่วไปเป็นงานที่มีคำสั่งแตกแขนงหลายจุด

  • เราคิดวิธีตรวจสอบข้อมูล 32 ไบต์ว่าเป็น UTF-8 ที่ถูกต้องหรือไม่ด้วย SIMD แบบไม่มีการแตกแขนง โดยใช้ไม่เกิน 20 cycle

  • เนื่องจากไบต์ของ UTF-8 มีค่าเป็นจำนวนเต็มได้ไม่เกิน 244 จึงสามารถใส่ข้อมูลเข้ารีจิสเตอร์ 256 บิตด้วยคำสั่ง SIMD แล้วลบจำนวนเต็ม 244 ออกจากแต่ละไบต์ด้วย saturation arithmetic (การคำนวณที่จำกัดช่วงของผลลัพธ์) จากนั้นก็แค่ตรวจว่ามีค่าที่ไม่เป็นศูนย์หรือไม่

  • วิธีนี้เร็วกว่าวิธีที่ใช้คำสั่งแตกแขนงมากกว่า 20 เท่า!

ตัวอย่าง 2: จำแนกประเภทตัวอักษร

  • หากจะพาร์ส JSON จำเป็นต้องแยกประเภทอักขระต่าง ๆ เช่น comma, colon, วงเล็บ, ช่องว่าง ฯลฯ

  • บน x86-64 และ ARM NEON มีคำสั่งที่ใช้ค้นหา lookup table ขนาด 16 ไบต์ได้ในครั้งเดียว

  • แยก 1 ไบต์ออกเป็น 4 บิตบนและ 4 บิตล่าง นำไปใช้กับ lookup table 2 ชุดที่เตรียมไว้ล่วงหน้า แล้วนำผลลัพธ์มา AND กัน

  • แม้โค้ดจะดูรก ๆ แต่สามารถจำแนกอักขระได้ 16 ตัวด้วยคำสั่งเพียง 5 คำสั่งโดยไม่มีการแตกแขนง

ตัวอย่าง 3: ตรวจจับ escape character

  • จะตรวจจับ escape character ที่เขียนโดยใส่แบ็กสแลช () ไว้ข้างหน้าโดยไม่ใช้คำสั่งแตกแขนงได้หรือไม่? โดยเฉพาะต้องรองรับกรณีที่มีแบ็กสแลชติดกันเพื่อ escape ตัวแบ็กสแลชเองด้วย

  • ในกรณีแบบนี้มีทริกว่าดูเฉพาะแบ็กสแลชลำดับคี่ก็พอ

  • ถ้ากำหนดบิตมาสก์ที่แทนตำแหน่งคู่และตำแหน่งคี่เป็นค่าคงที่ แล้วผ่าน bit operation ที่ซับซ้อน ก็จะกรอง escape character ได้โดยไม่ต้องแตกแขนง

  • เมื่อตัดเครื่องหมายอัญประกาศที่ถูก escape ออกแล้ว สิ่งที่เหลือก็คือเครื่องหมายอัญประกาศที่ใช้ระบุสตริง

  • หากนำตำแหน่งของเครื่องหมายอัญประกาศที่ได้มาเก็บเป็นบิตมาสก์ แล้วทำ xor bit operation ซ้ำไปเรื่อย ๆ ก็จะได้บิตมาสก์ที่บอกตำแหน่งของสตริง ซึ่งบนโปรเซสเซอร์ส่วนใหญ่จัดการได้ด้วยคำสั่งเดียว

  • ยังมีทริกในการจับคู่ระหว่างชุดบิตกับตำแหน่งของสตริงอีก แต่ขอข้ามไปเพราะเวลาไม่พอ

ตัวอย่าง 4: พาร์สตัวเลข

  • การพาร์สตัวเลขเป็นงานที่มีต้นทุนสูงมาก เมื่อลอง benchmark การพาร์ส floating point ด้วยฟังก์ชัน C ที่ปรับแต่งมาดีแล้ว กลับได้ความเร็วสุดช็อกเพียง 0.09 GB/s ชัดเจนว่าเป็นคอขวด

  • โค้ดพาร์สตัวเลขส่วนใหญ่มักทำงานทีละไบต์ ซึ่งไม่เร็วเลย

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

  • เห็นใน Stack Overflow ก็มี code snippet สำหรับพาร์สจำนวนเต็ม 8 หลักอย่างรวดเร็วอยู่เหมือนกัน ถ้าใช้ SIMD ก็อาจปรับปรุงได้อีกบ้าง แต่ประเด็นสำคัญคือการได้ไอเดียเรื่องกลยุทธ์แบบประมวลผลข้อมูลครั้งละมาก ๆ เช่นนี้

[อื่น ๆ]

runtime dispatch

  • เนื่องจากมีโค้ดที่พึ่งพาฮาร์ดแวร์อยู่มาก จึงมีฟังก์ชันที่ปรับแต่งเฉพาะสำหรับแต่ละโปรเซสเซอร์ออกมา และการทำให้ตอนรันเลือกเรียกฟังก์ชันที่เหมาะกับชนิดของโปรเซสเซอร์นั้นเป็นเรื่องที่ยากพอสมควร

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

  • จุดนี้สำคัญเพราะ simdjson เป็นไลบรารีโอเพนซอร์สแบบ single header file ที่ผนวกเข้ากับโปรเจ็กต์อื่นได้ง่าย

อื่น ๆ

  • มี wrapper สำหรับหลายภาษาเพื่อให้ใช้งานได้จากหลายภาษา

  • มีเวอร์ชันพอร์ตไป Rust แล้ว และกำลังเตรียมพอร์ตไป Go กับ C# แต่ไม่มีพอร์ตสำหรับ Java

  • สูตรคณิตศาสตร์หลายอย่างที่ใช้ในโปรเจ็กต์นี้คิดขึ้นร่วมกับ Geoff Langdale ผู้เขียนร่วม และได้ตีพิมพ์บทความที่เกี่ยวข้องใน VLDB Journal แล้ว ( https://doi.org/10.1007/s00778-019-00578-5 )
 
xguru 2020-08-13

โอ้ อ่านได้เพลินมากครับ ขอบคุณ!