แนะนำการแข่งขัน 1BRC
- ในการแข่งขัน 1BRC มีการคาดการณ์กันว่า หลังจากจัดการกับ "ผู้ต้องสงสัยตามปกติ" แล้ว คอขวดจะอยู่ที่การพาร์สอุณหภูมิจากไฟล์ CSV
- อุณหภูมิอาจอยู่ใน 4 รูปแบบคือ
-XX.X, -X.X, X.X, XX.X และในช่วงแรกใช้การเรียกไลบรารี Double.parseDouble()
- แต่ไม่นานก็มีโซลูชันแบบคัสตอมปรากฏขึ้น และหนึ่งในนั้นดูเหมือนจะเป็นวิธีที่ปรับแต่งมาอย่างดีซึ่งไม่มีลูปและมีเพียงสองสาขา
- จากนั้นแฮชแท็ก #1BRC บนทวิตเตอร์ก็ลุกเป็นไฟเพราะโซลูชันที่ Quân Anh Mai(@merykitty) นำเสนอ ซึ่งใช้เพียงการอ่านไฟล์ครั้งเดียวโดยไม่มี
if
วิเคราะห์ SWAR อันน่าอัศจรรย์ของ merykitty
- โค้ดของ merykitty ประกอบด้วยการทำงานของ ALU เพียง 18 ครั้ง และมีการเรียกฟังก์ชันระดับล่างเพียงตัวเดียวคือ
numberOfTrailingZeros()
- ค่า
long ที่รับเข้ามาจะบรรจุข้อมูล 8 ไบต์จาก CSV และผลลัพธ์คือค่าอุณหภูมิในรูปจำนวนเต็ม (เท่ากับอุณหภูมิจริงคูณ 10)
- เทคนิคนี้เรียกว่า "SIMD Within A Register" (SWAR) และใช้รีจิสเตอร์กับคำสั่งมาตรฐานของ CPU
- โค้ดนี้ทำงานผ่านขั้นตอนต่าง ๆ เช่น ตรวจจับว่าตัวเลขเป็นลบหรือไม่, ลบอักขระเครื่องหมาย, หาตำแหน่งจุดทศนิยม, จัดเรียงเนื้อหาให้ตรงกับเทมเพลต, แปลงอักขระ ASCII เป็นค่าตัวเลข, คูณน้ำหนักให้แต่ละหลักแล้วนำมาบวกกัน, และใส่เครื่องหมายกลับเข้าไป
- ขั้นตอนทั้งหมดนี้ดำเนินการโดยใช้เพียงการทำงานของ ALU
บทสรุป
- สิ่งที่เป็นปริศนาจริง ๆ ซึ่งอธิบายไม่ได้ด้วยบล็อกโพสต์ก็คือ merykitty ทำทั้งหมดนี้เพียงลำพังภายในไม่กี่วันได้อย่างไร
- QuestDB เป็นโอเพนซอร์ส และมอบความสามารถด้านการนำเข้าข้อมูลอย่างรวดเร็วและการวิเคราะห์ SQL ภายใต้สัญญาอนุญาต Apache 2.0
ความเห็นของ GN⁺
- บทความนี้แสดงให้เห็นถึงความซับซ้อนและความสร้างสรรค์ของเทคนิค SWAR ที่ถูกออกแบบมาเพื่อแก้ปัญหาง่าย ๆ อย่างการพาร์สอุณหภูมิ ซึ่งเน้นให้เห็นพลังของการทำงานระดับบิตและความสำคัญของการเพิ่มประสิทธิภาพในการเขียนโปรแกรม
- แนวทางแบบนี้อาจเป็นกรณีศึกษาที่น่าสนใจ โดยเฉพาะสำหรับวิศวกรซอฟต์แวร์ระดับเริ่มต้นที่สนใจการเขียนโปรแกรมระบบหรือการพัฒนาแอปพลิเคชันที่ไวต่อประสิทธิภาพ
- หากต้องการเพิ่มความเข้าใจเกี่ยวกับการทำงานระดับบิตและการเพิ่มประสิทธิภาพ การมองหาการแข่งขันเขียนโค้ดออนไลน์หรือบทเรียนที่เกี่ยวข้องกับหัวข้อหรือปัญหาในลักษณะนี้จะเป็นประโยชน์
- ยังจำเป็นต้องศึกษาต่อว่าเทคนิคนี้สามารถนำไปใช้ในสภาพแวดล้อมอุตสาหกรรมจริงได้อย่างไร และมีฐานข้อมูลหรือระบบอื่นใดที่ใช้เทคนิคการเพิ่มประสิทธิภาพในลักษณะใกล้เคียงกันหรือไม่
- เมื่อนำระบบอย่าง QuestDB มาใช้ ควรพิจารณาปัจจัยอื่นนอกเหนือจากประสิทธิภาพที่ดีขึ้นด้วย เช่น ความง่ายในการบำรุงรักษา ความอ่านง่ายของโค้ด และการสนับสนุนทางเทคนิคในระยะยาว
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
สรุปความคิดเห็นบน Hacker News ที่เกี่ยวข้องกับบทความ simdjson:
การตีความเกี่ยวกับบริบทของโค้ด: วิธีแก้ปัญหาที่นำเสนอนั้นยอดเยี่ยม แต่ต้องตั้งอยู่บนสมมติฐานว่าข้อมูลมีโครงสร้างที่ดี การตรวจสอบข้อผิดพลาดและความสามารถในการกู้คืนอย่างมีประสิทธิภาพมีคุณค่าสูงมากใน parser ที่ผ่านประสบการณ์มาอย่างยาวนาน
เทคนิคการ parse ตัวเลข: การคูณ bitfield ของตัวเลขด้วยกำลังของ 10 ของแต่ละหลัก แล้วใช้ MUL เพื่อ shift/บวก เป็นเทคนิคที่รู้จักกันดี ดูบล็อกของ Lemire ประกอบ
คำอธิบายเกี่ยวกับ SWAR (SIMD Within A Register): มีตัวอย่างมากมายของการทำ SWAR routine อย่างมีประสิทธิภาพใน Java/Scala โดยใช้ byte array view var handle
คำจำกัดความสั้น ๆ ของ SWAR: "SIMD Within A Register" คือการทำ SIMD ภายในรีจิสเตอร์เดียว
คำถามเกี่ยวกับคอขวด I/O ของ BRC (Branchless Ray Casting): ไม่เข้าใจว่าทำไม CPU ถึงเป็นคอขวด
ประสบการณ์การใช้ SWAR บน 68000: สามารถประมวลผลแบบขนานทีละ 4 ไบต์ได้ แต่การจัดการ overflow ค่อนข้างยุ่งยาก ชอบบทความนี้มาก
state space และ superoptimizer: มีคำถามว่าเพราะ state space มีขนาดเล็ก จึงมี superoptimizer ที่ให้ผลลัพธ์คล้ายกันอยู่แล้วหรือไม่
คำสั่ง AVX และการรองรับ SIMD ของ Java: อัลกอริทึมนี้สามารถทำงานแบบขนานได้ 32 เท่าด้วยคำสั่ง AVX แต่ก็น่าเสียดายที่ Java ยังไม่รองรับการใช้ SIMD ของ CPU ได้ดีนัก ยกเว้นบางกรณี
ความเข้าใจเกี่ยวกับการจัดการบิต: บทความนี้ช่วยให้เข้าใจการจัดการบิตได้ดีกว่าสิ่งอื่นใดก่อนหน้านี้ และขอขอบคุณผู้เขียนที่นำเสนอโซลูชัน Java สำหรับความท้าทาย 1BRC