- คอขวดของ 1BRC คือการพาร์สค่าอุณหภูมิใน CSV จำนวน 1 พันล้านค่าให้เร็วสุดขีด และ โค้ด SWAR ของ merykitty โดย Quân Anh Mai ได้รับความสนใจเพราะแปลงอุณหภูมิเป็นจำนวนเต็มด้วยการดำเนินการ ALU แบบคงที่โดยไม่ใช้
if
- โค้ดนี้ใช้แนวทาง SWAR(SIMD Within A Register) ที่จัดการ 8 ไบต์ใน
long หนึ่งตัวพร้อมกัน ประมวลผลอักขระหลายตัวในรีจิสเตอร์ CPU ทั่วไปเหมือนทำงานขนานกัน
- ลำดับการประมวลผลคือ ตรวจจับเครื่องหมายลบ, ลบเครื่องหมาย, หาตำแหน่งจุดทศนิยม, จัดเรียงเป็น
XY.Z, แปลงตัวเลข ASCII, การคูณวิเศษ, แล้วใช้เครื่องหมาย
- รูปแบบอินพุตมีสี่แบบคือ
-XX.X, -X.X, X.X, XX.X และจะเลื่อนไบต์โดยอิงตำแหน่งจุดทศนิยม เพื่อปรับความยาวที่ต่างกันให้มีการจัดวางบิตเหมือนกัน
- แทนที่จะลดด้วย branch และลูป โค้ดนี้ใช้คุณสมบัติของรหัส ASCII, two's complement, bit mask และคุณสมบัติ shift-add ของการคูณอย่างละเอียด เพื่อพาร์สได้ประสิทธิภาพสูง
การพาร์สอุณหภูมิที่กลายเป็นคอขวดใน 1BRC
- ใน One Billion Row Challenge(1BRC) งานสำคัญที่กลายเป็นคอขวดคือการพาร์สค่าอุณหภูมิจากไฟล์ CSV ให้เร็วมาก
- แค่การปรับแต่งก่อนหน้านี้ก็ทำให้โค้ด Java แบบ parallel ที่เขียนตามปกติเร็วขึ้นจาก 71 วินาทีเป็น 1.7 วินาที แล้ว
- รูปแบบอุณหภูมินั้นเรียบง่าย แต่ถ้าต้องพาร์ส 1 พันล้านค่าให้ต่ำกว่า 1 วินาที ค่าใช้จ่ายเล็กน้อยก็สะสมจนใหญ่ได้
- รูปแบบที่เป็นไปได้คือ
-XX.X, -X.X, X.X, XX.X
- ผู้เข้าร่วมช่วงแรกใช้
Double.parseDouble() แต่ต่อมาก็มี parser แบบกำหนดเองที่ไม่ใช้ลูปปรากฏขึ้น
- ส่วนหนึ่งของโซลูชัน @merykitty ของ Quân Anh Mai ประมวลผลด้วยการอ่านไฟล์ครั้งเดียวโดยไม่มี
if และแพร่หลายจนเหมือนเป็นองค์ประกอบมาตรฐานของโซลูชันอันดับต้น ๆ ของ 1BRC
- Thomas Wuerthinger ผู้ชนะ ระบุชื่อ Quân Anh ไว้เป็นส่วนหนึ่งของทีมที่มีส่วนช่วยในโซลูชันของเขา
โค้ดของ merykitty ทำอะไร
- โค้ดรับ
long ที่มีอินพุต CSV 8 ไบต์อยู่ภายใน แล้วคืนค่า อุณหภูมิแบบจำนวนเต็ม ซึ่งเท่ากับอุณหภูมิจริงคูณ 10
- อินพุตถูกอ่านจากไฟล์ CSV ที่
mmap ไว้โดยตรงผ่านการอ่านหน่วยความจำ native และส่วนนั้นถูกแยกเป็นประเด็นต่างหาก
- การคำนวณประกอบด้วยงาน ALU 18 รายการในลำดับคงที่
- bit shift, AND, NOT, XOR
- การบวก, การลบ, การคูณ
Long.numberOfTrailingZeros()
numberOfTrailingZeros() ใช้คำสั่ง CPU เฉพาะผ่าน intrinsic ของคอมไพเลอร์ JDK
- เนื่องจากจัดการหลายไบต์ด้วยรีจิสเตอร์และคำสั่ง CPU ทั่วไป ไม่ใช่คำสั่งเฉพาะทาง SIMD ปกติ จึงเข้าข่ายแนวทาง SWAR
- โค้ดตัวอย่างเป็นเวอร์ชันที่ปรับจากต้นฉบับเล็กน้อยเพื่อให้อ่านง่ายขึ้น ส่วนต้นฉบับอยู่ที่ CalculateAverage_merykitty.java
ขั้นตอนการประมวลผลทั้งหมด
- โค้ดพาร์สอุณหภูมิตามลำดับต่อไปนี้
- ตรวจว่าตัวอักษรแรกเป็น
- หรือไม่เพื่อดูว่าเป็นค่าลบหรือไม่
- ถ้ามีอักขระเครื่องหมาย ให้ทำไบต์นั้นเป็น 0
- หาตำแหน่งของจุดทศนิยม
.
- เลื่อนบิตภายใน
long เพื่อให้ตัวเลขเข้ากับเทมเพลต XY.Z
- แปลงอักขระ ASCII เป็นค่าตัวเลขจริง
- คูณหลักแต่ละตำแหน่งด้วยน้ำหนัก
1x, 10x, 100x แล้วรวมกัน
- ใช้เครื่องหมายในขั้นสุดท้าย
- ภายนอกดูเหมือนเป็นปัญหาการพาร์สระดับสูง แต่ทุกขั้นตอนถูกทำด้วยการดำเนินการ ALU เท่านั้น
ขั้นที่ 1: ตรวจจับเครื่องหมายลบ
- การตรวจจับเครื่องหมายเริ่มจากโค้ดต่อไปนี้
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
- หากสลับลำดับเพื่ออธิบาย จะมองได้คล้าย
( ~(inputData << 59) ) >> 63
- ใน ASCII เครื่องหมายลบ
- มี บิตที่ 4 เป็น 0 ขณะที่อักขระตัวเลขมีบิตนี้เป็น 1 จึงใช้คุณสมบัตินี้
- เมื่อเลื่อนอินพุตไปทางซ้าย 59 บิต บิตที่ใช้แยกแยะของอักขระตัวแรกจะย้ายไปอยู่บิตสูงสุด
- หลังจาก NOT เพื่อกลับบิต แล้วทำ arithmetic right shift 63 บิต บิตสูงสุดจะกระจายไปทั่วทั้ง
long
- ผลลัพธ์
broadcastSign จะเป็นบิต 1 ทั้งหมดหากมีเครื่องหมายลบ และเป็นบิต 0 ทั้งหมดหากไม่มี
ขั้นที่ 2: ลบอักขระเครื่องหมาย
- เมื่อข้อมูลว่าเป็นค่าลบหรือไม่ถูกเก็บไว้ใน
broadcastSign แล้ว ก็ลบอักขระเครื่องหมายออกจากข้อมูลอินพุต
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
- ถ้า
broadcastSign เป็น 1 ทั้งหมด broadcastSign & 0xFF จะทำให้เฉพาะ 8 บิตล่างสุดเป็น 1
- เมื่อ NOT จะได้ mask ที่มีเฉพาะ 8 บิตล่างสุดเป็น 0
- เมื่อนำไป AND กับ
inputData เครื่องหมาย - ในไบต์ล่างสุดจะถูกลบออก
- ถ้าไม่มีเครื่องหมายลบ
broadcastSign จะเป็น 0 ดังนั้น mask จะเป็นบิต 1 ทั้งหมด และไบต์ตัวเลขจะยังคงอยู่
ขั้นที่ 3: หาตำแหน่งจุดทศนิยม
- ตำแหน่งจุดทศนิยมคำนวณด้วยโค้ดต่อไปนี้
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
- อักขระ
. ก็มีคุณสมบัติว่า บิตที่ 4 เป็น 0 เช่นเดียวกับเครื่องหมายลบ
- เพื่อดูเฉพาะบิตที่ 4 ของตำแหน่งจุดทศนิยมที่เป็นไปได้ จะใช้ mask
DOT_DETECTOR = 0x10101000
- ใน
negatedInput ซึ่งเป็นอินพุตที่ถูกกลับบิต บิตดังกล่าวของตำแหน่งจุดทศนิยมจะกลายเป็น 1
Long.numberOfTrailingZeros() คืนตำแหน่งของบิต 1 นี้
- ในตัวอย่าง
-10.8 จุดทศนิยมอยู่ที่ตำแหน่งบิต 28 จึงได้ dotPos = 28
ขั้นที่ 4: จัดเรียงให้เข้ากับเทมเพลตคงที่
- เลื่อนอินพุตไปทางซ้ายโดยอิงตำแหน่งจุดทศนิยม เพื่อให้เข้ากับเทมเพลตเดียวกันเสมอ
long alignedToTemplate = withSignRemoved << (28 - dotPos);
0 0 0 Z . Y X 0
- ที่นี่
X คือหลักสิบ, Y คือหลักหน่วย, Z คือทศนิยมตำแหน่งแรก
0 หมายถึงไบต์ที่มีค่า 0 ไม่ใช่ ASCII "0"
- หลังลบเครื่องหมายแล้ว อินพุตอาจมีหนึ่งในสี่การจัดวางนี้
0 0 0 Z . Y X 0
0 0 0 0 Z . Y 0
0 0 0 0 Z . Y X
0 0 0 0 0 Z . Y
-10.8 มี dotPos = 28 อยู่แล้ว จึงมีระยะเลื่อนเป็น 0
-7.7 มีจุดทศนิยมอยู่ที่ตำแหน่งบิต 20 จึงเลื่อนไปทางซ้าย 8 บิต หรือหนึ่งไบต์ ทำให้ตำแหน่ง X เป็น 0
ขั้นที่ 5: แปลงตัวเลข ASCII เป็นค่า
- หลังจัดเรียงแล้ว ให้เหลือเฉพาะค่าตัวเลขจากอักขระ ASCII
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
- ตัวเลข ASCII
0 ถึง 9 มีค่าเลขฐานสิบหกตั้งแต่ 0x30 ถึง 0x39
- ถ้าเหลือไว้แค่ 4 บิตล่าง รหัสอักขระจะกลายเป็นค่าตัวเลขจริง
- ใช้ mask ที่มี
F เฉพาะตำแหน่งตัวเลขในเทมเพลต
0 0 0 Z . Y X 0
000000F000F0F00
- ตัวอย่าง
-10.8 หลังใช้ mask จะเหลือเฉพาะค่าที่แทน Z=8, Y=0, X=1
ขั้นที่ 6: รวมค่าประจำหลักด้วยการคูณวิเศษ
- ค่าสัมบูรณ์สุดท้ายต้องคำนวณเป็น
100 * X + 10 * Y + Z
- ใช้คุณสมบัติที่ว่าการคูณเป็นการผสมผสานของ shift และการบวก เพื่อคำนวณน้ำหนักของหลายหลักด้วยการคูณครั้งเดียว
- ก่อนอื่น ถ้าคิดเป็น
X + Y + Z จะสามารถรวมผลบวกไว้ในช่วงบิตเฉพาะได้ โดยนำ digits ที่ shift ไปที่ตำแหน่ง 0, 16, 24 บิตมาบวกกัน
- การผสม shift-add นี้เขียนแทนด้วยการคูณแบบต่อไปนี้ได้
0x1 + 0x10000 + 0x1000000
- ในความเป็นจริง แต่ละหลักมีน้ำหนักต่างกัน ดังนั้น
MAGIC_MULTIPLIER จึงประกอบขึ้นดังนี้
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
0x3FF คือ mask สำหรับแยกเฉพาะผลลัพธ์กว้าง 10 บิต
- แม้
100 * X อาจโตถึง 10 บิตและทับซ้อนกับบิตข้างเคียงได้ แต่เพราะสองบิตขวาสุดของ Y * 100 เป็น 0 จึงมีพื้นที่บิตที่จำเป็นพอดี
- merykitty ใส่คอมเมนต์ในส่วนนี้ว่า
// That was close :)
ขั้นที่ 7: ใช้เครื่องหมายโดยไม่ต้อง branch
- ถึงตอนนี้มีค่าสัมบูรณ์
absValue และข้อมูลเครื่องหมาย broadcastSign แล้ว
broadcastSign ทำหน้าที่เป็น 0 ถ้าเป็นค่าบวก และ -1 ถ้าเป็นค่าลบ
- ใน two's complement จำนวนลบแสดงได้ด้วยสูตรต่อไปนี้
-n = NOT(n) + 1
- XOR ใช้เหมือน NOT แบบมีเงื่อนไขได้
n XOR -1 คือ NOT(n)
n XOR 0 คือ n
- ส่วน
+1 ที่เลือกทำได้ถูกจัดการด้วย -broadcastSign
temperature = (absValue ^ broadcastSign) - broadcastSign;
- ผลคือค่าบวกคงเดิม และค่าลบถูกแปลงเป็นค่าลบแบบ two's complement โดยไม่ใช้
if
โบนัส: คำนวณตำแหน่งเริ่มของแถว CSV ถัดไป
- ในโซลูชัน 1BRC ทั้งหมด ต้องคำนวณตำแหน่งเริ่มของบรรทัด CSV ถัดไปให้ต้นทุนต่ำด้วย
- หลังจุดทศนิยมจะมีทศนิยมหนึ่งหลักและอักขระขึ้นบรรทัดใหม่ตามมาเสมอ ดังนั้นจึงหาตำแหน่งเริ่มแถวถัดไปจากตำแหน่งจุดทศนิยมได้
dotPos เป็นตำแหน่งระดับบิต จึงใช้การ shift ขวา 3 บิตเพื่อหารด้วย 8
nextLineStart = (dotPos >>> 3) + 3;
+3 คือค่าที่ใช้ชี้ไปยังไบต์แรกหลังจุดทศนิยม, ทศนิยมหนึ่งหลัก และอักขระขึ้นบรรทัดใหม่
สรุป
- โค้ด SWAR ของ merykitty พาร์สรูปแบบสตริงอุณหภูมิ 4 แบบให้เป็นหนึ่งเดียวด้วยการดำเนินการระดับบิตแบบคงที่เท่านั้น
- แก่นสำคัญคือคุณสมบัติระดับบิตของรหัส ASCII, การจัดเรียงตามตำแหน่งจุดทศนิยม, การดึงตัวเลขด้วย mask, การรวมค่าประจำหลักด้วยการคูณ และการใช้เครื่องหมายตาม two's complement
- เมื่อแบ่งเป็นขั้นตอนก็สามารถตามการทำงานได้ แต่สิ่งที่น่าประทับใจคือการนำทั้งหมดนี้มาประกอบกันได้ภายในไม่กี่วันของการแข่งขันออนไลน์
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
เมื่อกว่า 2 ปีก่อนฉันได้รู้ว่า byte array view var handle ค่อนข้างเหมาะกับการสร้างรูทีน SWAR ที่มีประสิทธิภาพใน Java/Scala
ตัวอย่างการใช้ SWAR เช่นการพาร์สสตริง Base16/64,
java.time.*, การพาร์สค่าตัวเลขจาก byte array โดยตรง ฯลฯ ก็มีอยู่มากที่นี่เช่นกัน: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...คุณค่าหลักของ parser ที่ผ่านงานจริงคือ การตรวจจับและกู้คืนข้อผิดพลาด อย่างมีประสิทธิภาพ
และก็สงสัยว่าถ้าจะตรวจจับแล้วคืนค่า sentinel error แบบสไตล์โค้ดปัจจุบัน จะต้องทำงานเพิ่มอีกมากแค่ไหน
ไม่ได้สนใจถึงขั้นจะลองทำเองหรอก ;-)
MULเพื่อทำ shift/บวก เป็นวิธีที่รู้จักกันพอสมควรดูบทความของ Lemire: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
paper: https://arxiv.org/abs/1902.08318
Github: https://github.com/simdjson/simdjson
ยิ่งไปกว่านั้น 1BRC ทางการก็ระบุชัดว่าประเมินผลจาก RAM disk เพื่อจะตัดผลของความเร็ว I/O ออกไปให้หมด: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
“Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
เท่าที่เข้าใจอย่างจำกัดคือ ไฟล์ข้อความขนาดใหญ่ถูกดึงเข้า L1 แบบตามลำดับ และแต่ละค่าถูกอ่านหนึ่งครั้ง สำหรับโปรเซสเซอร์ส่วนใหญ่ การอ่านแบบนี้ทำได้สองครั้งต่อ cycle ส่วนที่ช้าคือการดึงจาก RAM เข้า L1 แต่การอ่านแบบตามลำดับนั้นค่อนข้างเร็ว
จากนั้นก็ประมวลผลต่อการอ่านแต่ละครั้ง คร่าว ๆ แล้วในเวอร์ชันที่ปรับแต่งดีน่าจะราว 4 cycle หลังจากนั้นต้องเขียนผลลัพธ์ไปที่ไหนสักแห่ง และก่อนหน้านั้นก็น่าจะต้องมีการอ่านแบบสุ่มอีกหนึ่งหรือสองครั้ง นี่คือส่วนที่คุณมองว่าเป็นคอขวด I/O ใช่ไหม?
ไม่ได้หมายความว่าชัดเจนว่า CPU เป็นตัวจำกัด แต่ก็ไม่ได้ดูชัดเจนเหมือนกันว่าไม่ใช่
แก้ไข: ผมไม่ได้คิดถึงความเป็นไปได้ที่คุณอาจหมายถึง “disk I/O” อย่างที่คนอื่นบอกกัน ตรงนี้แทบไม่ใช่ปัจจัยเลย
กล่าวคือข้อมูลทั้งหมดจะอยู่ใน RAM หรือให้แม่นยำกว่านั้นคืออยู่ใน page cache
ถ้าจำไม่ผิด การจัดการ overflow ค่อนข้างยุ่งยาก ผมชอบบทความนี้มาก
ยังมีคนที่รู้วิธีโปรแกรม CPU จริง ๆ และเข้าใจว่าตัวเองกำลังทำอะไรอยู่
เรื่องลึกลับจริง ๆ คือคนส่วนใหญ่ที่เรียกตัวเองว่าโปรแกรมเมอร์กลับขาด ความเข้าใจเชิงลึก และดูเหมือนไม่รู้ด้วยซ้ำว่าตัวเองขาดอย่างหนัก
และมันก็ใช้ได้ผลจริงด้วย ซึ่งเห็นได้จากโซลูชัน C# ที่ดูเหมือนจะเร็วที่สุดในบรรดา 1BRC ที่เผยแพร่มาจนถึงตอนนี้: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
ปัญหาคือค่าใช้จ่ายในการสร้างเวกเตอร์เริ่มต้นและดึงผลลัพธ์ออกมาจะสูงเกินไปหรือเปล่า
แต่ก็ยังน่าสงสัยว่า HotSpot จะทำเองได้หรือไม่ อีกประเด็นคือ submission 1BRC ส่วนใหญ่รันด้วย Graal เพื่อลด startup overhead
SSE2 พื้นฐานไม่มีการคูณ 32 บิตหรือ 64 บิต ดังนั้น การคูณ 32×32→64 บิต จึงเป็นปัญหา แต่ใน SSE4.1 มี
pmuldqที่เพิ่มเข้ามาตรงกับที่ต้องการพอดี อย่างไรก็ตามผลลัพธ์เป็น 64 บิต ดังนั้นถ้าจะประมวลผลเวกเตอร์ของจำนวนเต็ม 32 บิตทั้งชุด ก็ต้องทำโอเปอเรชันแบบนี้สองครั้งอีกทั้งฟิลด์อุณหภูมิมีความยาวแปรผัน ดังนั้นแม้เก็บแบบ columnar ก็อาจไม่ได้ประโยชน์มากนัก
แต่ SSE ถูกนำไปใช้หา ตัวคั่น ระหว่างชื่อกับอุณหภูมิได้สำเร็จ