การแยกวิเคราะห์ protobuf ที่ความเร็วมากกว่า 2GB/s: เหตุผลที่ทำให้หลงรัก tail calls ในภาษา C (2021)

 (blog.reverberate.org)
1 คะแนน โดย GN⁺ 2024-08-20 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Tail Call: การเรียกฟังก์ชันที่เกิดขึ้นทันที ก่อนที่ฟังก์ชันจะคืนค่า หากเกิดการปรับแต่ง Tail Call จะใช้คำสั่ง jmp เพื่อลดการใช้ call stack
  • ข้อดี:
    • ลดการใช้หน่วยความจำสแตกจาก O(n) เหลือ O(1)
    • ตัด performance overhead ของการเรียกฟังก์ชันออก ทำให้ใช้เป็นโครงสร้างควบคุมการวนซ้ำที่มีประสิทธิภาพได้

ปัญหาของลูปอินเทอร์พรีเตอร์

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

การปรับปรุงลูปอินเทอร์พรีเตอร์ด้วย Tail Call

  • วิธีแก้: ใช้ Tail Call แยกแต่ละงานออกเป็นฟังก์ชันย่อย ๆ และให้แต่ละฟังก์ชันเรียกงานถัดไปด้วย Tail Call
  • ข้อดี:
    • ควบคุมการจัดสรรรีจิสเตอร์ได้
    • แยกเส้นทางแบบเร็วและแบบช้าออกจากกันเพื่อรักษาคุณภาพของโค้ด
    • สามารถปรับแต่งลำดับคำสั่งที่เป็นอิสระต่อกันได้

ข้อจำกัด

  • ปัญหาเมื่อมี non-tail call: หากมี non-tail call จะเกิด stack frame และข้อมูลถูกเก็บลงสแตก ทำให้ประสิทธิภาพลดลง
  • การจัดการข้อยกเว้นที่ซับซ้อน: หากการจัดการข้อยกเว้นซับซ้อน จะทำให้โค้ดซ้ำซ้อนและความซับซ้อนเพิ่มขึ้น
  • ปัญหาด้านการพกพา: แอททริบิวต์ musttail ไม่ใช่มาตรฐาน จึงไม่ได้รับการรองรับจากคอมไพเลอร์ทุกตัว

สรุปโดย GN⁺

  • การปรับแต่ง Tail Call มีบทบาทสำคัญต่อการเพิ่มประสิทธิภาพ และให้ผลลัพธ์ที่โดดเด่นโดยเฉพาะในการแยกวิเคราะห์ Protobuf
  • เทคนิคนี้สามารถนำไปใช้กับอินเทอร์พรีเตอร์ของภาษาหลักที่เขียนด้วย C ได้ด้วย เช่น Python, Ruby, PHP, Lua เป็นต้น
  • ปัญหาด้านการพกพาของแอททริบิวต์ musttail เป็นโจทย์ที่ยังต้องแก้
  • โปรเจ็กต์ที่มีความสามารถคล้ายกัน ได้แก่ LuaJIT, อินเทอร์พรีเตอร์ WebAssembly อย่าง wasm3 เป็นต้น

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

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

 
GN⁺ 2024-08-20
ความคิดเห็นบน Hacker News

  • ในข้อเสนอของมาตรฐาน C มีรูปแบบการรวม tail call แบบ return goto (expression);

    • แทนที่จะทำให้ [[musttail]] เป็นมาตรฐาน วิธีนี้รับประกันอายุการใช้งานของอ็อบเจ็กต์ภายในสโคป และไม่ต้องอาศัยการวิเคราะห์ escape อย่างกว้างขวาง

  • สำหรับแฟน Rust เคยมี RFC เก่าเกี่ยวกับการเพิ่มคีย์เวิร์ด become

    • ถูกเลื่อนออกไปเพื่อโฟกัสกับเป้าหมายของ edition 2018 แต่ช่วงหลังกำลังถูกนำกลับมาพูดถึงอีกครั้ง
    • มีความเป็นไปได้ว่าจะกลับมาอีก

  • ใน C++ วิธีที่ interpreter ใช้เพิ่มความเร็วโดยหลักคือการใช้ computed goto

    • สามารถหลีกเลี่ยงปัญหาเรื่อง calling convention ได้
    • การใช้สไตล์ computed goto หรือสไตล์ tail call สามารถลดแรงกดดันต่อ branch predictor ได้

  • ปัญหาของการสลับ context ด้วย tail call คือจำเป็นต้องมีฟังก์ชันที่ใช้ calling convention

    • ทำให้สิ้นเปลืองรีจิสเตอร์เพื่อกู้คืนสถานะตอนฟังก์ชันจบ
    • บล็อก luajit remake มีทางเลือกและการวิเคราะห์ในเรื่องนี้

  • หวังว่าแอตทริบิวต์ [[musttail]] จะแพร่ไปยัง GCC, Visual C++ และคอมไพเลอร์ยอดนิยมอื่น ๆ

    • กระบวนการเพิ่มแอตทริบิวต์ [[musttail]] เข้า GCC กำลังดำเนินอยู่

  • มีการกล่าวถึงการรองรับใน C++ พร้อมชี้ว่า C++ แทบไม่มี tail call เลย

    • ตัวอย่างเช่น การคืนค่าอ็อบเจ็กต์ของคลาสที่มี destructor ไม่ถือเป็น tail call

  • สงสัยว่าจะเกิดอะไรขึ้นหากโยน exception จากฟังก์ชัน C++ [[musttail]]

    • ตั้งคำถามว่า exception stack จะถูกแยกออกจากกันทั้งหมดหรือไม่

  • มีการกล่าวว่าตัวอย่างง่าย ๆ ไม่จำเป็นต้องใช้ __attribute__((musttail)) เพื่อให้ได้การสร้างโค้ดที่ดี

    • คงไม่ต้องกังวลมากนักกับความเร็วของการเรียกฟังก์ชันจัดการข้อผิดพลาด
    • โครงสร้างบางแบบสามารถสร้าง jump table ที่เชื่อถือได้

  • สงสัยเรื่องความเร็วของการใช้ trampoline โดยให้ฟังก์ชันคืนค่า function pointer แล้วไปเรียกจากลูปภายนอก

    • วิธีนี้มีข้อดีคือเป็น C แบบพกพาได้

  • มีคำขอให้ยกตัวอย่างเส้นทาง exception ที่ครอบด้วย [[musttail]] ให้ชัดเจนขึ้น

    • อธิบายว่าเหตุใด [[musttail]] จึงป้องกันการสร้าง stack frame และการ spill รีจิสเตอร์
    • การสร้าง stack frame และการ spill รีจิสเตอร์จะเกิดขึ้นก็ต่อเมื่อมีการเรียกเส้นทาง exception จริง ๆ
    • เนื่องจากเส้นทาง exception ถูกเรียกไม่บ่อย จึงไม่กระทบประสิทธิภาพมากนัก
    • ด้วยผลของ branch prediction ความเป็นไปได้ที่จะต้องทำงานเพิ่มอาจทำให้เส้นทางเร็วช้าลง