ท้าทายการประมวลผล 1 พันล้านแถวด้วย Go: ลดเวลาจาก 1 นาที 45 วินาทีเหลือ 4 วินาทีด้วย 9 วิธี

 (benhoyt.com)
35 คะแนน โดย GN⁺ 2024-03-04 | 6 ความคิดเห็น | แชร์ทาง WhatsApp
  • 1BRC: ชาเลนจ์ให้เขียนโค้ดอ่านค่าการวัดอุณหภูมิจากไฟล์ข้อความที่มี 1 พันล้านแถว แล้วคำนวณอุณหภูมิต่ำสุด/เฉลี่ย/สูงสุดของแต่ละสถานี
  • จัดขึ้นระหว่างวันที่ 1 มกราคม 2024 ถึง 31 มกราคม 2024 โดยมีเป้าหมายคือใช้ Java รุ่นล่าสุดให้เกิดประโยชน์สูงสุด
  • จากนั้นผู้คนก็เริ่มสนใจและลองทำด้วยภาษาต่าง ๆ (Rust, Go, C++, SQL)
  • แนะนำโซลูชัน 9 แบบที่เขียนด้วย Go อย่างละเอียด (เรียงจากช้าไปเร็ว)

ค่าพื้นฐานสำหรับการวัด

  • ใช้คำสั่ง cat เพื่ออ่านข้อมูลข้อความ 1 พันล้านแถว (13GB) ใช้เวลา 1.052 วินาที
  • คำสั่ง wc ที่ประมวลผลไฟล์จริงใช้เวลาเกือบ 1 นาที (55.710 วินาที)
  • การแก้ปัญหาด้วยโซลูชัน AWK ใช้เวลา 7 นาที 35 วินาที

โซลูชัน 1: Go แบบเรียบง่ายและเป็นสำนวนมาตรฐาน

  • โซลูชันแรกที่ใช้ไลบรารีมาตรฐานของ Go ใช้เวลา 1 นาที 45 วินาที
  • อ่านแต่ละบรรทัดด้วย bufio.Scanner และแยกด้วย strings.Cut โดยใช้ ';' เป็นตัวคั่น
  • แปลงค่าอุณหภูมิด้วย strconv.ParseFloat และสะสมผลลัพธ์ด้วย map ของ Go

โซลูชัน 2: map ที่เก็บค่าพอยน์เตอร์

  • ใช้ map[string]*stats เพื่อหลีกเลี่ยงการแฮชสองครั้งใน map
  • การใช้ค่าพอยน์เตอร์ช่วยลดเวลาจาก 1 นาที 45 วินาทีเหลือ 1 นาที 31 วินาที

โซลูชัน 3: เลี่ยง strconv.ParseFloat

  • ใช้โค้ดที่เขียนเองเพื่อแปลงค่าอุณหภูมิแทน strconv.ParseFloat
  • ลดเวลาจาก 1 นาที 31 วินาทีเหลือ 55.8 วินาที

โซลูชัน 4: ใช้จำนวนเต็มแบบ fixed-point

  • แทนค่าอุณหภูมิเป็นจำนวนเต็มเพื่อหลีกเลี่ยงการคำนวณแบบ floating-point
  • ลดเวลาจาก 55.8 วินาทีเหลือ 51.0 วินาที

โซลูชัน 5: เลี่ยง bytes.Cut

  • แทนที่จะสแกนชื่อสถานีทั้งหมดเพื่อหา ';' ก็เปลี่ยนมาแยกข้อมูลจากท้ายบรรทัด
  • ลดเวลาจาก 51.0 วินาทีเหลือ 46.0 วินาที

โซลูชัน 6: เลี่ยง bufio.Scanner

  • เอา bufio.Scanner ออกแล้วอ่านไฟล์เป็นชังก์ขนาดใหญ่
  • ลดเวลาจาก 46.0 วินาทีเหลือ 41.3 วินาที

โซลูชัน 7: แฮชเทเบิลแบบกำหนดเอง

  • สร้างแฮชเทเบิลขึ้นมาเองแทนการใช้ map ของ Go
  • ลดเวลาจาก 41.3 วินาทีเหลือ 25.8 วินาที

โซลูชัน 8: ประมวลผลชังก์แบบขนาน

  • ทำให้โค้ดแบบเรียบง่ายและเป็นสำนวนมาตรฐานทำงานแบบขนาน จนลดเวลาจาก 1 นาที 45 วินาทีเหลือ 24.3 วินาที

โซลูชัน 9: รวมทุกการปรับแต่งและการประมวลผลแบบขนาน

  • นำทุกเทคนิคการปรับแต่งมารวมกับการประมวลผลแบบขนาน จนลดเวลาจาก 24.3 วินาทีเหลือ 3.99 วินาที

ตารางผลลัพธ์

  • มีตารางเปรียบเทียบโซลูชัน Go ทั้งหมด รวมถึงโซลูชัน Go และ Java ที่เร็วที่สุด
  • เวอร์ชัน Go ที่เร็วที่สุดประมวลผลได้ใน 2.90 วินาที ส่วนเวอร์ชัน Java ใช้ 0.953 วินาที
  • เวอร์ชัน Java ที่ใช้เวลาไม่ถึง 1 วินาทีเป็นผลงานของ Thomas Wuerthinger (ผู้สร้าง GraalVM) ซึ่งน่าจะทำได้เพราะเป็นผู้เชี่ยวชาญด้านนี้โดยตรง

ความเห็นส่งท้าย

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

ความเห็นของ GN⁺

  • บทความนี้สำรวจวิธีต่าง ๆ ในการปรับแต่งการประมวลผลข้อมูลขนาดใหญ่ด้วยภาษา Go จึงเป็นกรณีศึกษาด้าน performance optimization ที่น่าสนใจ
  • ยังแสดงให้เห็นว่าการก้าวข้ามไลบรารีมาตรฐานของ Go ไปใช้โครงสร้างข้อมูลที่สร้างเอง เช่น แฮชเทเบิลแบบกำหนดเอง มีบทบาทสำคัญในกระบวนการปรับแต่ง
  • บทความเน้นย้ำประสิทธิผลของการประมวลผลแบบขนาน และการผสานการปรับแต่งบนคอร์เดี่ยวเข้ากับการทำงานแบบขนานเพื่อให้ได้ประสิทธิภาพที่ดีขึ้นอย่างมาก
  • บทความนี้ให้มุมมองที่เป็นประโยชน์กับวิศวกรซอฟต์แวร์ที่พัฒนาแอปพลิเคชันที่ไวต่อประสิทธิภาพ
  • อย่างไรก็ดี ความมีประโยชน์ของการปรับแต่งระดับนี้ในสภาพแวดล้อมโปรดักชันจริงอาจแตกต่างกันไปตามกรณีใช้งาน ไม่ใช่ทุกแอปพลิเคชันที่จะต้องการการปรับแต่งระดับนี้

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

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

 
cosine20 2024-03-07

อยากรู้เหมือนกันว่าในขั้นตอนที่ 7 มีการทำอะไรเกิดขึ้นแบบเจาะจงบ้าง เป็นช่วงที่ประสิทธิภาพดีขึ้นอย่างมากเลย 555
 
sddsdd94 2024-03-06

น่าสนใจที่เขาแยกเป็นแต่ละสเต็ปแล้วแสดงเวลาในการปรับปรุงประสิทธิภาพให้เห็น 555
 
galadbran 2024-03-05

แค่ใช้ wc ก็ใช้เวลาแค่นาทีเดียวเอง.... สุดยอดที่สุดก็คือการไม่ต้องเขียนโค้ดนี่แหละ... ฮ่าๆ
 
jhbaek 2024-03-05

ขอบคุณที่แชร์บทความดีๆ ครับ ทำให้นึกถึงช่วงหนึ่งที่เคยหมกมุ่นกับการปรับแต่งประสิทธิภาพระบบมากๆ เลย 555
พอมีประสบการณ์พัฒนามากขึ้น ก็เจออยู่บ่อยๆ ว่าโค้ดที่ปรับแต่งจนสุดทางนั้นดูแลรักษายาก ทำให้ในสภาพแวดล้อมขององค์กรใช้งานจริงได้ลำบาก เลยค่อยๆ ห่างออกมาจากเส้นทางของการ optimization ไปเองครับ (จู่ๆ ก็กลายเป็นการทบทวนตัวเองส่วนตัวเลย)
 
misolab 2024-03-05

โค้ดที่ปรับให้เหมาะกับองค์กร!!
 
GN⁺ 2024-03-04
ความคิดเห็นจาก Hacker News
  • ผู้ใช้คนแรกกล่าวว่า เนื่องจากตนไม่มีประสบการณ์ในการปรับแต่งโค้ดเพื่อจัดการข้อมูลมาก่อน ส่วนแรกที่ใช้ cat, wc เป็นต้น เพื่อหาค่าพื้นฐานจึงน่าสนใจเป็นพิเศษ และมองว่านี่เป็นวิธีง่าย ๆ ในการได้ช่วงค่าที่ "สมเหตุสมผล"
  • ผู้ใช้คนที่สองกล่าวถึงกรณีที่ใช้ไลบรารี Polars ซึ่งใช้เวลา 33 วินาที และแสดงความสนใจในโซลูชันที่ง่ายที่สุดซึ่งให้ประสิทธิภาพใกล้เคียงกับโซลูชันที่ปรับแต่งด้วยมือที่เร็วที่สุด
  • ผู้ใช้คนที่สามบอกว่ารายงานการวิเคราะห์ประสิทธิภาพของภาษา Go ชวนสับสน และอธิบายว่าเมื่อเวลาในการทำงานของโค้ดบางบรรทัดดูไม่เป็นไปตามสัญชาตญาณ อาจเป็นเพราะข้อมูลคาดเดาได้ยากและตัวทำนายการแตกแขนอาจทำนายผิด
  • ผู้ใช้คนที่สี่แชร์ผลการทำ 1BRC (1 Billion Row Challenge) ด้วยภาษา Go และบอกว่าได้เรียนรู้เทคนิคการปรับแต่งเฉพาะของ Go หลายอย่าง เช่น การอ่านหน่วยความจำโดยไม่ตรวจสอบขอบเขตด้วย unsafe.Pointer, ฟังก์ชันในแพ็กเกจ bytes และ bits ของไลบรารีมาตรฐานที่เขียนด้วยแอสเซมบลี, การตั้งค่าเพื่อปิด garbage collection และวิธีตรึง goroutine ไว้กับเธรด
  • ผู้ใช้คนที่ห้ากล่าวอ้างว่า ระหว่างที่นักพัฒนาภาษาอื่นยังเตรียมการกันอยู่ นักพัฒนา shell script คงจัดการข้อมูล 1 พันล้านแถวแบบเฉพาะงานนั้นเสร็จไปแล้ว
  • ผู้ใช้คนที่หกยืนยันว่าฐานข้อมูลเร็วกว่าซอร์สโค้ดฝั่งแอปพลิเคชัน ซับซ้อนน้อยกว่า และทนทานต่อการอัปเดตข้อมูลมากกว่า พร้อมเน้นว่าควรให้ฐานข้อมูลทำงานมากกว่านี้
  • ผู้ใช้คนที่เจ็ดเล่าว่าในปี 2010 ตนเคยพัฒนาเว็บแอปสำหรับค้นข้อมูลสภาพภูมิอากาศของ Environment Canada จำนวน 270 ล้านแถวด้วย PostgreSQL และซอฟต์แวร์นี้เคยได้รับรางวัล โดยแอปถูกปรับแต่งให้สร้างรายงานได้ภายในไม่ถึง 1 นาที
  • ผู้ใช้คนที่แปดกล่าวว่าเป็นเรื่องเท่มากที่โค้ดแบบขนานในภาษา Go ยังรักษาสไตล์โค้ดตามแนวทาง idiomatic ของ Go เอาไว้ได้
  • ผู้ใช้คนที่เก้ากล่าวว่าเวลาใช้ CLI จัดการไฟล์ข้อความขนาดใหญ่ หากข้ามการพาร์ส Unicode ไป awk, grep และเครื่องมืออื่น ๆ จะเร็วขึ้นไปอีกขั้น และอ้างว่าเพียงเพิ่ม LC_ALL=C ให้โซลูชัน awk ก็สามารถลดเวลาประมวลผลให้ต่ำกว่า 1 นาทีได้
  • ผู้ใช้คนสุดท้ายกล่าวว่าน่าสนใจที่เวอร์ชัน Java ที่เร็วที่สุดยังเร็วกว่าเวอร์ชัน Go ที่เร็วที่สุด และประเมินว่าประสิทธิภาพของ Java Virtual Machine (JVM) นั้นดีมาก