ในโลกของการเขียนโปรแกรม การเพิ่มประสิทธิภาพโดยคอมไพเลอร์ควรจะทำให้โค้ดทำงานเร็วขึ้น ไม่ใช่ช้าลง แต่การวิเคราะห์ล่าสุดเกี่ยวกับประสิทธิภาพของ Rust ได้เผยให้เห็นกรณีที่น่าประหลาดใจ เมื่อระดับการเพิ่มประสิทธิภาพสูงสุดกลับทำให้ประสิทธิภาพแย่ลง ก่อให้เกิดการอภิปรายอย่างกว้างขวางในหมู่เหล่านักพัฒนาว่าเมื่อไหร่ที่การปรับปรุงคอมไพเลอร์จะกลายเป็นกับดักด้านประสิทธิภาพ
กรณีศึกษาประสิทธิภาพที่ผิดปกติ
นักพัฒนา Rust คนหนึ่งค้นพบล่าสุดว่า bounded priority queue ที่พวกเขาสร้างขึ้นเอง ทำงานช้าลงอย่างมากเมื่อคอมไพล์ด้วย opt-level = 3 เทียบกับ opt-level = 2 โดยโทษทางด้านประสิทธิภาพมีมากถึง 113% ในการทดสอบมาตรฐาน ผลลัพธ์ที่ขัดกับสามัญสำนึกนี้เกิดขึ้นแม้ว่าระดับการเพิ่มประสิทธิภาพทั้งสองระดับจะกำหนดเป้าหมายสถาปัตยกรรม Haswell เดียวกันและได้รับการทดสอบบนทั้ง AMD Zen 3 และ Intel Haswell ตัวจริง
โค้ดที่มีปัญหานั้นเกี่ยวข้องกับ sorted vector ที่ใช้ binary_search_by พร้อมกับฟังก์ชันเปรียบเทียบซึ่งเปรียบเทียบระยะห่างแบบ floating-point ก่อน แล้วจึงเปรียบเทียบ ID จำนวนเต็ม แม้ว่าโค้ดนี้จะดูเรียบง่าย แต่กลยุทธ์การเพิ่มประสิทธิภาพที่แตกต่างกันของคอมไพเลอร์ได้สร้างผลลัพธ์ assembly ที่แตกต่างกันอย่างมาก นำไปสู่ความคลาดเคลื่อนด้านประสิทธิภาพ
ในฟังก์ชันแบบมี branching (branchy function) นั้น id จะถูกเปรียบเทียบก็ต่อเมื่อ distance เท่ากันเท่านั้น และเนื่องจาก distance เป็น float สุ่ม เหตุการณ์นี้แทบไม่เคยเกิดขึ้นและ branch ที่สอดคล้องกันนั้นถูกทำนายได้อย่างเกือบจะสมบูรณ์แบบ ในทางตรงกันข้าม ฟังก์ชันแบบไม่มี branching (branchless function) จะเปรียบเทียบทั้ง id และ distance ตลอดเวลา ซึ่งเท่ากับทำงานเป็นสองเท่า
การเปรียบเทียบประสิทธิภาพ: ระดับการเพิ่มประสิทธิภาพ O2 เทียบกับ O3
- การเพิ่มประสิทธิภาพ O2: 44.1% ของตัวอย่างอยู่ใน binary_search_by, 25.68% อยู่ในฟังก์ชัน compare
- การเพิ่มประสิทธิภาพ O3: 79.6% ของตัวอย่างอยู่ใน binary_search_by, 63.57% อยู่ในฟังก์ชัน compare
- ค่าใช้จ่ายด้านประสิทธิภาพ: ช้าลง +113% เมื่อใช้ O3 เทียบกับ O2
ความลึกลับในระดับ Assembly
เมื่อนักพัฒนาตรวจสอบโค้ด assembly ให้ลึกลงไป พวกเขาพบว่า opt-level = 2 สร้างโค้ดที่ตรงไปตรงมาพร้อมกับการกระโดดแบบมีเงื่อนไข (conditional jumps) ในขณะที่ opt-level = 3 สร้างโค้ดที่ซับซ้อนมากขึ้นโดยใช้การเคลื่อนย้ายแบบมีเงื่อนไข (conditional moves) โดยทั่วไปแล้ว conditional moves ถูกมองว่าทันสมัยและมีประสิทธิภาพมากกว่าเพราะหลีกเลี่ยงการพลาดในการทำนาย branch แต่ในกรณีเฉพาะนี้ มันกลับสร้างสายการพึ่งพา (dependency chains) ที่กลายเป็นคอขวดด้านประสิทธิภาพ
การวิเคราะห์ทางทฤษฎีโดยใช้เครื่องมือเช่น uCA (uiCA) ทำนายว่าการใช้ conditional move จะมี throughput ต่ำกว่า 2.7 เท่า เนื่องจากปัญหาด้านการพึ่งพา สิ่งนี้เน้นย้ำให้เห็นว่าความซับซ้อนของ CPU สมัยใหม่ ซึ่งมีคุณสมบัติเช่นการทำงานแบบขนานในระดับคำสั่ง (instruction-level parallelism) การทำนาย branch และการทำงานแบบคาดการณ์ (speculative execution) บางครั้งสามารถทำงานสวนทางกับโค้ดที่ได้รับการเพิ่มประสิทธิภาพในแบบที่คาดไม่ถึง
ความแตกต่างของ Assembly Code
- O2: ใช้ conditional jumps (5 conditional jumps รวมถึงการตรวจสอบ NaN)
- O3: ใช้ conditional moves (4 conditional moves, 1 conditional jump)
- Theoretical throughput: การวิเคราะห์ assembly ของ O3 ด้วยเครื่องมือ uCA คาดการณ์ว่าต่ำกว่า 2.7 เท่า
การทดลองและแนวทางแก้ไขจากชุมชน
ชุมชนนักเขียนโปรแกรมได้ตอบสนองด้วยการทดสอบและวิเคราะห์อย่างกว้างขวาง นักพัฒนาบางคนพบว่าการเพิ่ม #[inline(always)] ไปยังฟังก์ชันเปรียบเทียบสามารถลดโทษของ O3 ลงได้ประมาณ 50% แม้ว่ามันจะทำให้ประสิทธิภาพของ O2 ลดลงเล็กน้อย บางคนค้นพบว่าการใช้ total_cmp สำหรับการเปรียบเทียบ floating-point แทนการจัดการ NaN ด้วยตนเอง สร้าง assembly ที่แตกต่างออกไปแต่ยังคงมีปัญหาด้านประสิทธิภาพที่คล้ายกัน
ผู้แสดงความคิดเห็นหลายคนระบุว่า profile-guided optimization (PGO) อาจช่วยให้ LLVM ตัดสินใจได้ดีขึ้นเกี่ยวกับเวลาที่ควรใช้ conditional moves เทียบกับการกระโดด (jumps) การอภิปรายยังกล่าวถึงบริบททางประวัติศาสตร์ โดยมีการอ้างอิงถึงปัญหาการถดถอยด้านประสิทธิภาพของ Rust ในอดีตที่เกี่ยวข้องกับการเพิ่มประสิทธิภาพการค้นหาแบบไบนารีและการใช้ conditional move
แนวทางแก้ไขที่ถูกหารือกัน
- เพิ่ม
[inline(always)]ให้กับฟังก์ชัน compare: ปรับปรุงประมาณ 50% ที่ O3, ลดลง 10% ที่ O2 - ใช้
std::hint::unlikelyกับ branch ที่เกิดขึ้นไม่บ่อย - แทนที่การเปรียบเทียบ float แบบ manual ด้วยเมธอด
total_cmp - Profile-guided optimization (PGO) เพื่อการตัดสินใจของ compiler ที่ดีขึ้น
ผลกระทบในภาพกว้าง
กรณีศึกษาเปิดเผยความจริงที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับกลยุทธ์การเพิ่มประสิทธิภาพของคอมไพเลอร์ ดังที่นักพัฒนาคนหนึ่งระบุ LLVM ไม่ได้สมมติว่าความเท่ากันของ float มีโอกาสเกิดขึ้นน้อยกว่าเงื่อนไขอื่นๆ ซึ่งสามารถนำไปสู่การเลือกเพิ่มประสิทธิภาพที่ไม่ได้ดีที่สุดสำหรับรูปแบบข้อมูลบางอย่าง เหตุการณ์นี้ทำหน้าที่เป็นเครื่องเตือนใจว่าการเพิ่มประสิทธิภาพโดยคอมไพเลอร์ไม่ใช่เวทมนตร์ มันคืออัลกอริทึมที่กำลังคาดเดาอย่างมีความรู้ ซึ่งบางครั้งอาจผิดพลาดสำหรับรูปแบบโค้ดเฉพาะบางอย่าง
การอภิปรายยังเน้นย้ำให้เห็นว่าการเลือกภาษาโปรแกรมมิ่งมีปฏิสัมพันธ์กับลักษณะของฮาร์ดแวร์อย่างไร CPU สมัยใหม่มีความซับซ้อนอย่างไม่น่าเชื่อ และลักษณะประสิทธิภาพของมันสามารถท้าทายสามัญสำนึกง่ายๆ เกี่ยวกับสิ่งที่เป็นโค้ดที่ได้รับการเพิ่มประสิทธิภาพ สิ่งที่ทำงานได้ดีบนสถาปัตยกรรมหนึ่งหรือกับรูปแบบข้อมูลหนึ่ง อาจล้มเหลวอย่างมากในสถานการณ์ที่แตกต่างออกไป
การเดินทางผ่านกับดักการเพิ่มประสิทธิภาพ
สำหรับนักพัฒนาที่กำลังเผชิญกับปัญหาที่คล้ายกัน ชุมชนได้เสนอแนวทางหลายประการ การใช้ std::hint::unlikely บน branch ที่แทบไม่เคยถูกใช้งานสามารถมีอิทธิพลต่อการตัดสินใจเพิ่มประสิทธิภาพได้ บางคนกล่าวถึงว่า __builtin_expect_with_probability ของ GCC/Clang พร้อมความน่าจะเป็น 0.5 สามารถบังคับให้ใช้ conditional move เมื่อเหมาะสม
ประเด็นสำคัญคือการเพิ่มประสิทธิภาพจำเป็นต้องอาศัยการทดสอบเชิงประจักษ์มากกว่าการตั้งสมมติฐาน ดังที่ผู้แสดงความคิดเห็นคนหนึ่งกล่าวอย่างรวบรัดว่า: และนี่คือเหตุผลว่าทำไมคุณต้องไปดู assembly ใน godbolt เพื่อดูว่าเกิดอะไรขึ้น กรณีนี้แสดงให้เห็นว่าแม้แต่นักพัฒนาที่มีประสบการณ์ก็ยังสามารถประหลาดใจกับพฤติกรรมของคอมไพเลอร์ได้ ซึ่งเน้นย้ำถึงความสำคัญของการทดสอบมาตรฐานและการวิเคราะห์ในระดับ assembly สำหรับโค้ดที่สำคัญต่อประสิทธิภาพ
ทีมพัฒนา Rust compiler ได้ปรับสมดุลการเลือกเพิ่มประสิทธิภาพเหล่านี้อย่างระมัดระวังมาโดยตลอด โดยปัญหาการถดถอยด้านประสิทธิภาพในอดีตแสดงให้เห็นว่า conditional moves สามารถทำงานได้เร็วกว่าในบางการทดสอบมาตรฐาน ในขณะที่ช้ากว่าในบางการทดสอบ ความแปรปรวนนี้ตอกย้ำว่าทำไมจึงไม่มีกลยุทธ์การเพิ่มประสิทธิภาพที่เหมาะกับทุกสถานการณ์ และทำไมนักพัฒนาคอมไพเลอร์จึงให้ระดับการเพิ่มประสิทธิภาพหลายระดับ แทนที่จะเป็นการตั้งค่าระดับเดียวที่เร็วที่สุด
ในภูมิทัศน์ที่พัฒนาอย่างต่อเนื่องของเทคโนโลยีคอมไพเลอร์และสถาปัตยกรรมฮาร์ดแวร์ กรณีเช่นนี้ทำหน้าที่เป็นเครื่องเตือนใจที่มีคุณค่าว่าการทำความเข้าใจปฏิสัมพันธ์ระหว่างโค้ด คอมไพเลอร์ และ CPU ยังคงเป็นสิ่งจำเป็นสำหรับการเขียนซอฟต์แวร์ที่มีประสิทธิภาพอย่างแท้จริง
อ้างอิง: When O3 is 2x slower than O2