เมื่อคอมไพเลอร์ทำให้คุณประหลาดใจ

• กรณีศึกษาการสังเกต ความแตกต่างด้านการปรับแต่งประสิทธิภาพของ GCC และ Clang เมื่อคอมไพล์ฟังก์ชันบวกจำนวนเต็มอย่างง่าย
• GCC ทำ การปรับแต่งลูปในรูปแบบ x*2 + 1 โดยบวกตัวเลขทีละสองค่าในลูป
• Clang ลบลูปทิ้งทั้งหมด และแทนที่การคำนวณด้วย สูตรแบบปิด v(v - 1)/2
• การแปลงนี้ทำให้โค้ดเปลี่ยนจาก O(n) เป็น O(1) พร้อมการย่อรูปทางคณิตศาสตร์โดยอัตโนมัติ
• เป็นตัวอย่างที่แสดงให้เห็นถึง ระดับการปรับแต่งอันชาญฉลาดของคอมไพเลอร์ จนทำให้แม้แต่ผู้เขียนที่ทำงานกับคอมไพเลอร์มานานกว่า 20 ปียังรู้สึกประหลาดใจ

---

การปรับแต่งลูปของ GCC

• เมื่อเขียนฟังก์ชันบวกจำนวนเต็มอย่างง่าย GCC จะสร้างโค้ดรวมผลแบบอิงลูปที่มีประสิทธิภาพ
  • ภายในลูปใช้คำสั่ง lea edx, [rdx+1+rax*2] เพื่อบวกตัวเลขสองค่าพร้อมกัน
  • นี่คือการแปลงการบวก x และ x+1 ให้อยู่ในรูป x*2 + 1
• เมื่อเพิ่มระดับการปรับแต่งเป็น -O3 ก็จะประมวลผลลูปได้เร็วขึ้นด้วย การบวกแบบขนาน (vectorization)
• วิธีลักษณะนี้เป็นรูปแบบการปรับแต่งดั้งเดิมที่ยังคงลูปไว้ แต่ เพิ่มประสิทธิภาพของการคำนวณให้สูงสุด

การปรับแต่งเชิงคณิตศาสตร์ของ Clang

• เมื่อนำโค้ดเดียวกันไปคอมไพล์ด้วย Clang ลูปจะหายไปทั้งหมด
  • Clang ตรวจสอบก่อนว่าค่าป้อนเข้าเป็นบวกหรือไม่ จากนั้นคำนวณด้วยชุดคำสั่ง lea, imul, shr
  • ผลลัพธ์สุดท้ายคือการแปลงเป็น (v² - v)/2 หรือก็คือ สูตรแบบปิดของผลรวมจำนวนเต็ม
• การแปลงนี้ลบลูปออกและแทนที่ด้วย การคำนวณเวลาคงที่ (O(1))
• ผู้เขียนอธิบายผลลัพธ์นี้ว่าเป็น “การค้นพบวิธีแก้เชิงคณิตศาสตร์ของผลรวมจำนวนเต็มได้ด้วยตัวเอง”

กระบวนการคลี่สูตร

• หากไล่ย้อนแอสเซมบลีที่ Clang สร้างขึ้นกลับไปในเชิงคณิตศาสตร์ จะได้การแปลงดังนี้
  • v + ((v - 1)(v - 2) / 2) - 1
  • เมื่อกระจายและจัดรูป จะย่อได้เป็น (v² - v)/2
• สุดท้ายจึงได้รูป v(v - 1)/2 ซึ่งสอดคล้องกับสูตรผลรวมจาก 1 ถึง v
• กระบวนการนี้ถูกยกเป็นตัวอย่างของ คอมไพเลอร์ที่รู้จำแพตเทิร์นทางคณิตศาสตร์และปรับแต่งได้

การทำงานอันชาญฉลาดของคอมไพเลอร์

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

บทสรุปและบริบทของซีรีส์

• บทความนี้เป็นตอนที่ 24 ของซีรีส์ ‘Advent of Compiler Optimisations 2025’
• สำรวจกระบวนการที่คอมไพเลอร์ใช้การแปลงโค้ดเพื่อให้ได้ทั้ง การย่อรูปทางคณิตศาสตร์และประสิทธิภาพที่ดีขึ้น
• ผู้เขียนย้ำว่า “คอมไพเลอร์ยังคงทำให้ฉันประหลาดใจอยู่เสมอ” พร้อมเน้นถึง ความน่าทึ่งทางเทคนิคที่ยังคงอยู่แม้มีประสบการณ์ยาวนาน

[GN⁺]

ความเห็นบน Hacker News

• โค้ดที่ใช้ทำฟีเจอร์นี้อยู่ใน ScalarEvolution.cpp และ IndVarSimplify.cpp

  • น่าทึ่งที่โค้ดเกือบ 16,000 บรรทัด ถูกยัดอยู่ในไฟล์เดียว และก็ให้ความรู้สึกกังวลนิด ๆ ไปพร้อมกัน

• การเพิ่มประสิทธิภาพแบบนี้น่าสนใจมาก
  การ optimize ของคอมไพเลอร์แบ่งใหญ่ ๆ ได้เป็นสองแบบ — การวิเคราะห์การไหลของข้อมูล กับ การรู้จำแพตเทิร์นและแทนที่
  แบบแรกมีประโยชน์กับโปรแกรมส่วนใหญ่ ส่วนแบบหลังเป็นงานสะสมแพตเทิร์นที่ให้ผลตอบแทนลดลงเรื่อย ๆ
  ตัวอย่างที่ลิงก์มานั้นฉลาดและสนุก แต่ในทางปฏิบัติไม่ได้มีคุณค่ามากนัก ผมไม่เคยเขียนลูปแบบนั้นเลยตลอด 45 ปี
  แน่นอนว่าแพตเทิร์นการแทนที่แบบนี้ยังสำคัญ เพราะมันมักถูกสร้างขึ้นอัตโนมัติจากโค้ดระดับสูง
  พูดตรง ๆ คืออาจเป็นเพราะ optimizer ของผมทำ optimization แบบนี้ไม่ได้ เลยบ่นงอแงนิดหน่อย

  • จริง ๆ แล้วมันอาจมีคุณค่ามากกว่าที่คิด เพราะ SCEV (Scalar Evolution) ของ LLVM ใช้เพื่อการวิเคราะห์เป็นหลัก และช่วยให้ optimization อื่น ๆ นอกเหนือจากลูปคณิตศาสตร์เกิดขึ้นได้ด้วย
  • ยังไม่ชัดเจนว่ามีการทำ optimization อะไรไปบ้าง ตอนที่ผมเคยสร้างคอมไพเลอร์เฉพาะทางเมื่อก่อน ยังจำได้ว่าประหลาดใจที่คอมไพเลอร์จัดการได้ฉลาดกว่าการ optimize ที่ผมเขียนเอง

• นี่คือฟีเจอร์ที่เรียกว่า Scalar Evolution (SCEV) และใน LLVM มันถูกนำไปทำเป็น implementation ที่ค่อนข้างซับซ้อน

• มีกรณี optimization คล้ายกันใน บทความ “Do not optimize away”

  • คำอธิบายช่วงต้นของบทความนั้นผิดอยู่เล็กน้อย โค้ดบวกค่าตั้งแต่ 0 ถึง N แต่ไม่รวม N ดังนั้นจริง ๆ แล้วควรเป็น N(N-1)/2 ผลรวมทางคณิตศาสตร์ของ 1 ถึง N คือ N(N+1)/2 ดังนั้นถ้าจะไม่รวมขอบบน ก็ต้องแทน N ด้วย (N-1)
  • ผมคิดว่าคอมไพเลอร์ก็น่าจะยัง optimize สิ่งนี้ได้อยู่ อาจทำทั้งเวอร์ชัน constant folding และเวอร์ชันไม่คงที่ แล้วแตกแขนงตอนรันไทม์

• จุดที่เจ๋งจริง ๆ ของ optimization นี้คือมันมีความ ทั่วไป (generic)
  ไม่ใช่แค่รู้จำแพตเทิร์น “ผลรวมของลำดับจำนวนเต็มจำกัด” แต่เป็นการประยุกต์ใช้แบบทั่วไป ซึ่งน่าประทับใจมาก

• ดูเหมือนว่าคอมไพเลอร์อาจเพิ่ม closed form ได้อีกหลายแบบ แค่สงสัยว่ามันคุ้มค่าหรือเปล่า
  แนวคิดที่เกี่ยวข้องคือ Wilf–Zeilberger pair

• ผมแปลกใจอีกครั้งที่ GCC ช้ากว่า Clang
  ทั้งที่ GCC นำมาก่อนตั้ง 20 ปี แต่ก็ยังมีกรณีที่ Clang สร้างโค้ดได้เร็วกว่า
  เมื่อก่อนตอนดึงบิตออกมา Clang ใช้แค่การ shift สองครั้ง แต่ GCC ใช้ถึงสามครั้ง

  • ระหว่าง GCC กับ LLVM/Clang มีช่องว่างด้านเทคโนโลยีคอมไพเลอร์อยู่หนึ่งช่วงรุ่น GCC ยังเป็นโปรเจกต์ที่ยอดเยี่ยมมาก แต่ได้ยินมาว่าในเชิงสถาปัตยกรรมมันทำให้การนำ เทคนิค optimization สมัยใหม่ ไปใช้ยาก
  • ประสิทธิภาพจริงของทั้งสองคอมไพเลอร์ใกล้เคียงกัน พวกมันมี optimization pass ต่างกัน จึงให้ผลต่างกันไปตามสถานการณ์
  • ตอนเริ่มต้น GCC ถูกออกแบบด้วยอุดมคติที่เน้น ไลเซนส์ ทำให้ขยายต่อได้ไม่ดีนัก ทุกวันนี้ดีขึ้นมากแล้ว แต่ตัว code generator ก็ยังซับซ้อนอยู่ ในทางกลับกัน Clang มีโครงสร้างเรียบง่ายกว่า จึงทำ implementation ของ optimization ได้ง่ายกว่า ส่วนตัวผมรู้สึกว่า output ของ MSVC กับ ICC ก็ค่อนข้างดีเหมือนกัน
  • เป็นโค้ดเกี่ยวกับ bitfield หรือเปล่า? GCC ทำ optimization ส่วนนั้นได้ไม่ค่อยดีเป็นพิเศษ

• ผมสงสัยว่าจะมีใครเคยลอง optimization ที่แทน ปัญหาการระบายสีกราฟ (graph coloring) ด้วยค่าคงที่ไหม

  • graph coloring เป็นปัญหา NP-hard เลยยากที่จะเปลี่ยนให้เป็น O(1) ได้ ถ้าเป็นกราฟเชิงระนาบก็ใช้ทฤษฎีบทสี่สีได้ แต่คำตอบก็ไม่ได้ออกมาเหมือนเดิมเสมอไป ผมแค่อยากคุยเรื่องทฤษฎีกราฟเฉย ๆ

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

• ตอนแรกผมแปลกใจที่ Matt ไม่รู้เรื่องพฤติกรรมแบบนี้
  สมัยเรียนมหาวิทยาลัย ผมเองก็เคยเล่นกับ LLVM IR แล้วช็อกที่เห็น recursion ถูกย่อให้เป็นการคูณ
  การที่ Matt ไม่รู้อาจหมายความว่า optimization นี้ใช้ได้เฉพาะกับเคสง่าย ๆ ที่เขาไม่ได้แตะ

  • จริง ๆ เขารู้อยู่แล้ว ในงานบรรยายปี 2017 เขาพูดถึงตัวอย่างเดียวกันนี้ด้วยตัวเอง
    ลิงก์วิดีโอ YouTube