การพาร์ส protobuf ที่มากกว่า 2GB/s: การออกแบบอินเทอร์พรีเตอร์ความเร็วสูงใน C ด้วย tail call (2021)

 (blog.reverberate.org)
1 คะแนน โดย GN⁺ 2024-08-20 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เมื่อ Clang เพิ่ม musttail ทำให้ภาษาในตระกูล C สามารถใช้ tail call ที่รับประกันได้ และเมื่อนำไปใช้กับตัวพาร์ส protobuf ก็สาธิตประสิทธิภาพได้ มากกว่า 2GB/s
  • แก่นสำคัญคือทำให้การเรียกฟังก์ชันใกล้เคียงกับ jmp มากกว่า call ลดการใช้สแตกของการเรียกต่อเนื่องจาก O(n) เป็น O(1) และจัดการได้เหมือนลูปวนซ้ำ
  • protobuf wire format ต้องตีความแท็ก/ค่าและกระโดดแยกไปยังฟิลด์ที่มาในลำดับใดก็ได้ ทำให้โครงสร้าง while + switch แบบเดิมมีโจทย์การปรับแต่งคล้ายกับ การ dispatch opcode ของอินเทอร์พรีเตอร์
  • ตัวพาร์สเชิงทดลองของ upb เชื่อมฟังก์ชันพาร์สขนาดเล็กด้วย tail call แทนฟังก์ชันขนาดใหญ่หนึ่งตัว จึงหลีกเลี่ยง การใช้สแตก·register spill·prologue/epilogue บน fast path
  • วิธีนี้มีข้อจำกัดคือถ้ามี non-tail call ปะปน คุณภาพโค้ดจะแย่ลงอย่างมาก และ musttail เป็นส่วนขยายที่ไม่ใช่มาตรฐาน ดังนั้นหากจะนำตัวพาร์สเร็วไป deploy จริง ต้องมีวินัยด้านรูปแบบการเรียกและมาตรการด้าน portability

การพาร์ส protobuf ความเร็วสูงที่เปิดทางโดย Clang musttail

  • มีการเพิ่มแอตทริบิวต์ของ statement [[clang::musttail]] / __attribute__((musttail)) เข้าใน main branch ของ Clang ทำให้ C, C++, Objective-C ได้รับ การรับประกัน tail call
  • ในที่นี้ tail call ไม่ได้ใช้เป็นเทคนิคของ functional programming แต่ใช้เป็น เครื่องมือ optimization เพื่อลดต้นทุนการ branch ของตัวพาร์สและอินเทอร์พรีเตอร์
  • เมื่อนำเทคนิคนี้ไปใช้กับการพาร์ส protobuf ใน upb pull/310 ก็สาธิตประสิทธิภาพการพาร์สได้ มากกว่า 2GB/s
    • ถูกนำเสนอว่าเร็วกว่าระดับสูงสุดก่อนหน้ามากกว่าสองเท่า
    • เนื่องจากมีหลายเทคนิคช่วยกัน จึงไม่ถูกต้องที่จะตีความว่า “เร็วขึ้น 2 เท่าเพราะ tail call อย่างเดียว”
    • tail call เป็นหนึ่งในองค์ประกอบหลักที่ทำให้ประสิทธิภาพที่เพิ่มขึ้นนี้เป็นไปได้
  • การเปลี่ยนแปลงหลังจากนั้นกล่าวถึงใน A Tail Calling Interpreter For Python (And Other Updates)

เหตุผลที่ tail call ทำงานเหมือนโครงสร้างวนซ้ำ

  • tail call คือ การเรียกฟังก์ชันครั้งสุดท้าย ที่ทำก่อนฟังก์ชันจะ return
  • เมื่อใช้ tail call optimization คอมไพเลอร์จะสร้างคำสั่ง jmp แทน call ปกติ
    • ข้ามการสร้าง stack frame ใหม่หรือการบันทึก return address
    • ผู้เรียก f() กระโดดไปยังผู้ถูกเรียก g() โดยตรง
    • g() return ตรงกลับไปยังฟังก์ชันที่เคยเรียก f()
  • ด้วยคุณสมบัตินี้ tail call จึงใช้แทนโครงสร้างวนซ้ำได้
    • แม้มี tail call ต่อเนื่องกัน n ครั้ง การใช้สแตกก็ลดจาก O(n) เป็น O(1)
    • overhead ของ call หายไป ทำให้จัดการการเรียกฟังก์ชันได้เหมือน branch ทั่วไป
  • แนวคิดนี้ไม่ใช่ของใหม่ และย้อนกลับไปได้ถึงบทความปี 1977 ของ Guy Steele และ “Lambda Papers” ช่วงปี 1975~1980
  • Clang สามารถ optimize tail call ได้อยู่แล้วใน build แบบ optimization เช่น -O2 แต่พฤติกรรมเดิมใกล้เคียงกับ best-effort
    • ใน build ที่ไม่เปิด optimization มีโอกาสสูงที่จะคอมไพล์เป็น call จริง
    • หากจะใช้ tail call เป็นโครงสร้างวนซ้ำอย่างปลอดภัย ต้องรับประกัน optimization ในทุก build mode
    • musttail ให้การรับประกันนี้

คอขวดแบบเดียวกันของลูปอินเทอร์พรีเตอร์และตัวพาร์ส protobuf

  • Mike Pall จาก LuaJIT เขียนอินเทอร์พรีเตอร์ LuaJIT 2.x ด้วย assembly ไม่ใช่ C และมองว่านี่เป็นเหตุผลสำคัญที่ทำให้อินเทอร์พรีเตอร์เร็ว
  • คอมไพเลอร์ C เจอปัญหาเด่นสองอย่างโดยเฉพาะใน main loop ของอินเทอร์พรีเตอร์
    • ยิ่งฟังก์ชันใหญ่และ control flow ซับซ้อนขึ้น register allocator ก็ยิ่งรักษาข้อมูลสำคัญไว้ใน register ได้ยาก
    • หาก fast path และ slow path ปะปนอยู่ในฟังก์ชันเดียวกัน slow path จะลดคุณภาพโค้ดของ fast path ไปด้วย
  • protobuf wire format ก็มีโครงสร้างคล้ายอินเทอร์พรีเตอร์
    • wire format เป็นลำดับของ คู่แท็ก/ค่า
    • แท็กมีหมายเลขฟิลด์และ wire type
    • แท็กทำงานคล้าย opcode ที่บอกว่าจะพาร์สข้อมูลของฟิลด์นั้นอย่างไร
    • หมายเลขฟิลด์สามารถมาในลำดับใดก็ได้ จึงต้องพร้อม dispatch ไปยังส่วนใดก็ได้ของโค้ด
  • ตัวพาร์ส protobuf แบบเดิมมักใช้โครงสร้าง switch ภายในลูป while และตลอดช่วงเวลาส่วนใหญ่ที่ protobuf มีอยู่ วิธีนี้ถูกใช้เป็นแนวทางระดับสูงสุด
  • ในการพาร์สจริง ข้อยกเว้นอย่าง wire type ไม่ตรงกัน ข้อมูลเสียหาย หรือถึงจุดสิ้นสุดบัฟเฟอร์ อาจเกิดขึ้นได้แทบทุกขั้นตอน
    • fast path ต้องคงให้สั้นและเสถียรที่สุดเท่าที่ทำได้
    • กรณียากต้องใช้ fallback code ที่ใหญ่และซับซ้อนกว่า และบางครั้งมีการเรียกฟังก์ชันแบบ out-of-line ด้วย

การออกแบบตัวพาร์ส upb บนพื้นฐาน tail call

  • ตัวพาร์สเชิงทดลองของ upb ไม่ใช้ฟังก์ชันพาร์สขนาดใหญ่หนึ่งตัว แต่แยกแต่ละ operation เป็น ฟังก์ชันขนาดเล็ก หนึ่งตัว
  • แต่ละฟังก์ชันเรียก operation ถัดไปด้วย tail call
    • ด้วย calling convention ของ x86-64 ทำให้อาร์กิวเมนต์ร่วมสำหรับการพาร์สถูกส่งผ่าน register
    • ฟังก์ชันพาร์สทั้งหมดใช้ชุดอาร์กิวเมนต์เดียวกัน ลดการย้ายค่าระหว่างการเรียก
  • ฟังก์ชันตัวพาร์สฟิลด์ fixed-width 4 ไบต์ในตัวอย่างทำงานตามลำดับนี้
    • decode ข้อมูลฟิลด์จาก data
    • หาก wire type ไม่ตรง ให้ MUSTTAIL return ไปยัง fallback()
    • ข้ามแท็กและบันทึกข้อมูลลงใน message
    • อ่านแท็กถัดไป แล้ว tail call ไปยัง dispatch() ซึ่ง branch ไปยังตัวพาร์สฟิลด์ที่เหมาะสม
  • assembly ที่ Clang สร้างไม่มี prologue·epilogue·register spill·การใช้สแตก บน fast path
    • จุดจบมีเพียง jmp ไปยัง fallback หรือ dispatch
    • อาร์กิวเมนต์อยู่ใน register ที่ถูกต้องอยู่แล้ว จึงไม่ต้องมีโค้ดส่งพารามิเตอร์เพิ่มเติม
  • โครงสร้างนี้มองลูปอินเทอร์พรีเตอร์ขนาดใหญ่ในเชิงแนวคิดเป็นฟังก์ชันซับซ้อนหนึ่งตัว แต่ในการ implement จริงจะแยกเป็นฟังก์ชันระดับ basic block แล้วส่งต่อ control flow ด้วย tail call
  • การแยก fast path และ slow path ออกเป็นคนละฟังก์ชัน ลดโอกาสที่การเปลี่ยน fallback code จะสั่นคลอนคุณภาพโค้ดของ fast path
    • หากจำเป็นสามารถใช้ noinline เพื่อกันการ inline ได้
    • สามารถตรึงลำดับ assembly ของ fast path ได้แทบทั้งหมด

คุณภาพการสร้างโค้ด C ที่เห็นจากตัวอย่าง LuaJIT

  • เมื่อนำ pattern เดียวกันไปใช้กับตัวอย่าง LuaJIT ก็สามารถได้ผลลัพธ์จากโค้ด C ที่ใกล้เคียง assembly ที่เขียนด้วยมือ
  • ฟังก์ชันตัวอย่าง ADDVN ทำงานดังนี้
    • ดึง register และ index ของ constant จากคำสั่ง
    • หาก type check ล้มเหลว ให้ย้ายไป fallback
    • บวก constant เข้ากับค่าใน register
    • อ่าน opcode ถัดไป แล้ว tail call ไปยังฟังก์ชันในตาราง opcode
  • จุดที่ยังปรับปรุงได้ใน assembly ที่สร้างขึ้นมีค่อนข้างเล็ก
    • มี jmp แยกหลัง conditional branch
    • ใช้การโหลดเข้า rax แล้ว jmp rax แทน jmp qword ptr [rsi + 8*rax]
  • ประเด็นเหล่านี้ถูกมองเป็นปัญหาเล็ก ๆ ด้าน code generation ที่สามารถปรับปรุงใน Clang ได้

ข้อจำกัดเรื่อง non-tail call และ portability

  • จุดที่ต้องระวังที่สุดของวิธีนี้คือ หากมี non-tail call อยู่ในฟังก์ชัน คุณภาพ assembly จะแย่ลงอย่างมาก
    • non-tail call เพียงครั้งเดียวบังคับให้สร้าง stack frame
    • ข้อมูลจำนวนมากอาจถูก spill ลงสแตก
  • เพื่อหลีกเลี่ยงสิ่งนี้ ต้องมีวินัยในการ inline การเรียกฟังก์ชันอื่น หรือทำเฉพาะ tail call เท่านั้น
  • ในการพาร์ส protobuf การจัดการ varint เป็นจุดยากที่เป็นตัวอย่างเด่น
    • กรณีที่พบบ่อยและเร็วคือ varint ขนาด 1 ไบต์
    • varint ที่ยาวกว่านั้นไม่ใช่ข้อผิดพลาด แต่เป็นกรณีที่ไม่ค่อยพบ
    • หาก inline การจัดการข้อยกเว้นนี้ คุณภาพโค้ดของ fast path อาจแย่ลง
    • หาก tail call ไปยังฟังก์ชัน fallback จะกลับมาทำ operation เดิมต่อได้ไม่ง่ายหลังประมวลผลแล้ว fallback จึงต้องจัดการ operation ให้จบเอง
    • ผลคือเกิด code duplication และความซับซ้อน
  • ในอัปเดต 2025-01-27 มีการเพิ่มวิธีบรรเทาปัญหานี้ด้วย calling convention
    • __attribute__((preserve_most)) เป็น calling convention ที่ใช้กับ fallback function ได้ โดยย้ายภาระการรักษา register เกือบทั้งหมดไปให้ callee และย้ายต้นทุน spill ไปฝั่ง fallback
    • บั๊ก Clang crash ที่เกี่ยวข้องกับ attribute นี้ ได้รับการแก้ไขในปี 2023
    • __attribute__((preserve_none)) เป็น calling convention ที่ใช้กับฟังก์ชันที่ทำ tail calling ได้ โดยตัดภาระการรักษา register และใช้ register สำหรับอาร์กิวเมนต์ได้มากขึ้น
    • ในสองวิธีนี้ preserve_none ถูกประเมินว่าเป็นตัวเลือกที่ดีกว่าเพราะรุกล้ำน้อยกว่า
  • ข้อจำกัดอีกอย่างคือ musttail เป็น ส่วนขยายของคอมไพเลอร์ที่ไม่ใช่มาตรฐาน
    • คาดหวังว่าจะกระจายไปยัง GCC, Visual C++ ฯลฯ และถูกทำให้เป็นมาตรฐาน แต่ไม่ใช่เรื่องในเร็ว ๆ นี้
    • เมื่อไม่มี musttail ต้องมี return จริงอย่างน้อยหนึ่งครั้งต่อการวนซ้ำเชิงแนวคิดของลูป
    • upb ยังไม่ได้ implement fallback นี้ และคาดว่าจะต้องมี macro ที่ tail call ไปยัง dispatch หรือเพียง return ตามความพร้อมใช้งานของ musttail

สถานะการนำไปใช้ใน upb และความเป็นไปได้ในการขยายผล

  • ตัวพาร์สที่มากกว่า 2GB/s ถูกส่งเข้าไปยัง upb ซึ่งเป็นไลบรารี protobuf ขนาดเล็กที่เขียนด้วย C
  • โค้ดดังกล่าวทำงานได้ครบถ้วนและผ่าน protobuf conformance test ทั้งหมด แต่ ณ เวลาที่เขียน ยังไม่ได้ rollout ที่ใด
  • การออกแบบนี้ยังไม่ได้ implement ใน protobuf เวอร์ชัน C++
  • ต่อมาเมื่อ upb ถูกอัปเดตให้ใช้ musttail อุปสรรคใหญ่ข้อหนึ่งในการทำตัวพาร์สเร็วให้ใช้ใน production ก็ถูกขจัดออกไป
  • เทคนิคเดียวกันนี้อาจให้ประโยชน์ด้านประสิทธิภาพอย่างมากกับอินเทอร์พรีเตอร์ภาษาหลักที่เขียนด้วย C เช่น Python, Ruby, PHP, Lua เป็นต้น

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

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

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

  • ในข้อเสนอของมาตรฐาน C มีไวยากรณ์สำหรับ tail call โดยอยู่ในรูป return goto (expression);
    จุดที่ชอบมากกว่า [[musttail]] แบบมาตรฐานคือมีการรับประกันว่าอายุของออบเจ็กต์ภายในฟังก์ชันจะสิ้นสุดลงแล้ว ดังนั้นจึงทำให้ implement ได้โดยไม่ต้องพึ่ง escape analysis ในวงกว้าง
    [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

    • สงสัยว่าทำไม return goto ถึง implement ได้ง่ายกว่า ดูเผิน ๆ แล้ว [[musttail]] ก็น่าจะทำให้อายุของออบเจ็กต์ภายในฟังก์ชันสิ้นสุดลงเหมือนกัน
      ลองไล่อ่านเร็ว ๆ เห็นว่าฟังก์ชันที่ถูกเรียกในตำแหน่ง tail ต้องมี ชนิดเดียวกัน กับเป้าหมายที่เรียก เงื่อนไขนี้มีไว้เพื่อรับประกันว่าไม่ต้องแปลงค่าที่ return และพื้นที่สำหรับส่งอาร์กิวเมนต์กับ calling convention ยังถูกรักษาไว้
      คำบ่นที่ผมเห็นบ่อยเกี่ยวกับ [[musttail]] ที่ผมเคย implement ใน Clang คือข้อจำกัดนี้เข้มงวดเกินความจำเป็น สถาปัตยกรรมบางแบบยอมให้ทำ tail call ได้แม้ชนิดจะไม่ตรงกันทั้งหมด: https://github.com/llvm/llvm-project/issues/54964
      ถ้าจะบอกว่า “งั้นโค้ดก็พกพาไม่ได้สิ” ก็ถูก แต่การ optimize แบบ tail call เองโดยเนื้อแท้ก็ไม่ได้พกพาได้อยู่แล้ว เช่น target บางตัวอย่าง WASM ที่ไม่มีส่วนขยาย tail call ก็ไม่รองรับการ optimize แบบ tail call ตั้งแต่พื้นฐาน
    • การที่กระแสเพิ่มฟีเจอร์ใหม่ให้ C กลับมาแรงขึ้นอีกครั้ง ทั้งน่าคาดหวังและค่อนข้างน่ากังวล
      น่าคาดหวังเพราะมีทั้งการเปลี่ยนแปลงและการเพิ่มเติมที่ควรต้องมีจริง ๆ แม้แต่ไอเดียบางอย่างที่ควรทำให้ชัดเจนขึ้น แต่รอบการอัปเดตที่ดุดันของ C++ สุดท้ายดูเหมือนกลายเป็นการ โปะปุ่มใหม่ทับปุ่มเดิม
      ปัญหาอยู่ตรงเวลาฟีเจอร์ต่าง ๆ โต้ตอบกันในทางที่ไม่ดีเร็วกว่าที่คาดไว้มาก หวังว่ากระบวนการมาตรฐานจะไม่พึ่งแต่เอกสารเหตุผลประกอบ แต่จะเลือกอย่างอนุรักษนิยมมาก ๆ พร้อมทดสอบฟีเจอร์ให้เพียงพอบน codebase ขนาดใหญ่และหลากหลาย

  • ถ้าสนใจฝั่ง Rust มี RFC เก่าเกี่ยวกับการเพิ่มคีย์เวิร์ด become เพื่อให้มีการ optimize แบบ tail call ที่รับประกันได้
    เดิมทีถูกเลื่อนออกไปเพื่อโฟกัสเป้าหมายของ edition 2018 ซึ่งเป็นการตัดสินใจที่ถูกแล้ว แต่ช่วงหลังแนวคิดนี้ถูกนำกลับมาพิจารณาอีก อาจกลับมาได้อีกครั้ง
    [0]: https://github.com/rust-lang/rfcs/pull/1888
    [1]: https://github.com/rust-lang/rfcs/pull/3407

  • วิธีที่ interpreter ใน C++ มักใช้เพื่อให้ได้ความเร็วเพิ่มแบบนี้คือใช้ computed goto แบบนั้นเส้นทางจาก opcode หนึ่งไปยัง opcode ถัดไปจะไม่มี noise ที่เกี่ยวกับ calling convention
    เหตุผลหลักที่วิธี computed goto หรือวิธี tail call เร็วกว่า loop switch แบบคลาสสิก คือช่วยลด ภาระของ branch predictor ลง เพราะในเชิงสถิติมี indirect branch หนึ่งตัวต่อ opcode และไม่ใช่โครงสร้างที่มี indirect branch เพียงตัวเดียวในเชิงสถิติ

    • อย่างที่บทความบอก แม้ใช้ computed goto กราฟ control flow graph ของฟังก์ชันก็ยังซับซ้อนเกินไป ทำให้การจัดสรร register ให้ตัวแปรที่ใช้บ่อยเปราะบาง
      ถ้าแต่ละฟังก์ชันมีขนาดเล็กและรับตัวแปรสำคัญเป็นอาร์กิวเมนต์ การจัดสรร register จะเปราะบางน้อยลงมาก
    • สงสัยคำว่า “ในเชิงสถิติมี indirect branch หนึ่งตัวต่อ opcode” หมายความว่าอย่างไรเมื่อเทียบกับ indirect branch เพียงตัวเดียว และทำได้อย่างไร อยากให้ช่วยอธิบายละเอียดขึ้นอีกหน่อย
    • เคยได้ยินว่าวิธีนี้ตกกระแสไปพักหนึ่งแล้ว เหตุผลคือ branch predictor ดีพอจนไม่จำเป็นอีกต่อไป
      แต่ก็สงสัยว่าเมื่อ interpreter มีขนาดใหญ่ขึ้น คำพูดนั้นยังจริงอยู่ไหม

  • ปัญหาที่ยังเหลือในการใช้ tail call เพื่อสลับ context คือมันใช้ฟังก์ชันที่ต้องใช้ calling convention น่าเสียดายที่ต้องเสีย register ไปเพื่อกู้คืนสถานะตอนจบฟังก์ชัน
    มีบทวิเคราะห์ละเอียดและทางเลือกที่ใช้คอมไพเลอร์ชั้นกลางในบล็อกรีเมค LuaJIT: https://sillycross.github.io/2022/11/22/2022-11-22/

    • ในช่วงไม่กี่ปีที่ผ่านมา เห็นบางภาษาถอดชั้น JIT ออกแล้วใส่กลับเข้าไปใหม่ บางส่วนเป็นเพราะความสามารถของโปรแกรมเมอร์และบทเรียนที่ได้เรียนรู้ แต่บางส่วนก็เป็นเพราะการเปลี่ยนไปของ รุ่น CPU ด้วย
      เหมือนทุกอย่างในวิทยาการคอมพิวเตอร์ เมื่อสมดุลของต้นทุนต่อชนิดของการคำนวณเปลี่ยนไป อัลกอริทึมที่ดีที่สุดอาจย้อนกลับไปเป็นวิธีที่เคยใช้เมื่อ 15 หรือ 20 ปีก่อน นั่นจึงทำให้การเขียนโปรแกรมดูมีด้านที่เหมือนแฟชั่น การรื้อฟื้นอะไรบางอย่างไม่ได้แปลว่าไม่มีเหตุผล แต่การลืมเหตุผลว่าทำไมครั้งก่อนมันถึงไม่ใช่ยาครอบจักรวาลก็ยังเป็นปัญหา
      ถ้า main JIT เร็วขึ้นหรือช้าลง ผลได้เมื่อเทียบกับต้นทุนการรันก็เปลี่ยน และ threshold ที่ trigger สิ่งนี้ก็ถูกปรับตาม จากนั้นปริมาณโค้ดที่รันในชั้นอื่นก็เปลี่ยน และต้นทุนแบบ amortized ของชั้นนั้นก็อาจแย่ลงด้วย เหมือนการปรับสมดุล ลูกตุ้มคู่
      ถ้าทำให้ชั้น JIT เร็วและหยาบพอได้ ก็อาจข้าม interpreter ไปเลยได้ มองจากภายนอก ภาระทางความคิดในการทำบัญชีให้สมดุลระหว่าง interpreter กับ JIT สักสองตัวดูหนัก จนบางภาษาดูเหมือนจะพัก interpreter ไว้ แล้วใช้ JIT ที่ optimize เพื่อเวลา compile มากกว่าความเร็ว output
      จำไม่ได้ว่าเป็นภาษาไหน แต่เท่าที่รู้ มีอย่างน้อยหนึ่งทีมที่สุดท้ายตัดคอมไพเลอร์ชั้นกลางออกไปด้วยเพราะปัญหาสมดุลนี้ โฟกัสกับสองอย่างดีกว่าต้องจัดการทั้งสามอย่าง
    • ช่วงหลัง Clang มี calling convention ใหม่ที่ทำให้ tail call แบบนี้ถูกลงมาก ลดความจำเป็นที่ caller ต้องเก็บรักษา register บางตัวไว้
      ชื่อทำให้สับสนทุกที แต่น่าจะเป็น preserve_all หรือ preserve_none ประเด็นคือมองการ preserve จากมุมของใคร

  • เท่าที่ทราบ แอตทริบิวต์ musttail กำลังอยู่ระหว่างการเพิ่มเข้าไปใน GCC แพตช์กำลังถูกรีวิวอยู่ และ semantics เข้ากันได้กับ Clang

    • สงสัยว่าแอตทริบิวต์ preserve_most จะเป็นอย่างไรต่อไป มีโอกาสไหมที่ของคล้าย ๆ กันจะเข้า GCC? ถ้าไม่มีสิ่งนี้ การเรียกที่ไม่ใช่ tail call จะทำให้อินเทอร์พรีเตอร์พัง
    • เป็นปัญหาที่ยาก ABI จำนวนมากไม่สามารถทำ tail call ได้แม้แต่ในกรณีพื้นฐานมาก ๆ อย่างการเรียกฟังก์ชันภายนอกที่อาร์กิวเมนต์และชนิดค่าที่ส่งคืนตรงกัน
      ดูเหมือนว่า Clang จะมี heuristic ที่เปลี่ยนลำดับการเรียกสำหรับการเรียก musttail เช่น บน i686 จะเปลี่ยนเป็นการเรียกแบบ noplt เรื่องแบบนี้ไม่มีอยู่ในเอกสารของ Clang: https://clang.llvm.org/docs/AttributeReference.html#musttail
      สิ่งที่ทำได้จริงในทางปฏิบัติคงเป็นแค่การออก ข้อความวินิจฉัย เมื่อคอมไพเลอร์ไม่สามารถสร้าง tail call ได้ สำหรับผู้ใช้จำนวนมาก แค่นั้นก็น่าจะเพียงพอแล้ว การรับประกัน tail call แบบ Scheme ดูไม่น่าจะเกิดขึ้นได้ง่าย
    • GNUC มีฟีเจอร์คล้าย Scheme อยู่พอสมควร จึงน่าแปลกใจที่ตามหลังในฟีเจอร์นี้

  • มีการพูดถึงการรองรับ C++ ด้วย แต่ใน C++ น่าจะมี tail call น้อยมาก
    เช่น foo() { auto a = SomeClassWithADestructor(); return bar(); } ไม่ใช่ tail call เพราะหลังจากเรียก bar() แล้วจะมีการทำลาย a

    • ถ้าคอมไพเลอร์พิสูจน์ได้ว่าไม่มีผลข้างเคียงระยะไกลระหว่างบรรทัดเหล่านั้น เป็นไปได้ไหมที่จะเรียก destructor ก่อนรัน bar?
      สงสัยว่ามาตรฐาน C++ บอกว่าต้องเรียก destructor ที่ท้ายบล็อกเสมอหรือไม่ หรือสามารถเรียกได้ทันทีเมื่อไม่ใช้ตัวแปรนั้นอีกแล้ว

  • ตัวอย่างอาจจะเรียบง่ายเกินไป แต่ดูเหมือนว่า __attribute__((musttail)) ไม่ได้จำเป็นเสมอไปสำหรับการสร้างโค้ดที่ดี
    ถ้าฟังก์ชันจัดการข้อผิดพลาดเป็นเส้นทางที่เกิดขึ้นไม่บ่อย ความเร็วของการเรียกก็คงไม่สำคัญมากนัก
    โครงสร้างแบบ if (unlikely(malformed)) return error(); switch (data_type) { case x: return handle_x(); case y: return handle_y(); } ดูเหมือนจะสร้าง jump table ที่ดีได้ค่อนข้างเสถียร

    • แน่นอนว่าคอมไพเลอร์ทำ tail call elimination มานานแล้ว แต่ในเทคนิคนี้ แค่ “สร้างได้ค่อนข้างเสถียร” ยังไม่พอ ต้องมีการ รับประกัน หรือไม่ก็ต้องคอมไพล์ล้มเหลว
      ไม่อย่างนั้นโครงสร้างนี้จะไม่ทำงาน และสแตกจะแตกทันที ประเด็นของ [[musttail]] คือการทำ tail call elimination เป็นสิ่งจำเป็น คอมไพเลอร์ไม่มีทางเลือกอื่น
    • อย่างที่ disassembly ในบทความแสดงให้เห็น เหตุผลที่เส้นทาง fallback เป็นปัญหาไม่ใช่ว่าการเรียกนั้นเร็วแค่ไหน แต่แค่การมีอยู่ของการเรียกนั้นก็อาจทำให้คอมไพเลอร์สร้าง stack frame ให้ทั้งฟังก์ชันและเทรีจิสเตอร์ลงไปในนั้น ซึ่งส่งผลกระทบรวมถึงเส้นทางเร็วด้วย
      แน่นอนว่าคำว่า “บังคับ” อาจไม่แม่นยำนัก ไม่มีข้อกำหนดว่าคอมไพเลอร์ต้องใช้โครงสร้าง stack frame เดียวกันในทุกเส้นทางการทำงานของฟังก์ชัน และก็ไม่ได้กำหนดว่าฟังก์ชันลิงก์ภายในหรือฟังก์ชันใน anonymous namespace ที่ไม่ได้ถูกนำ address ไปใช้ต้องใช้ ABI มาตรฐาน แต่คอมไพเลอร์ทุกตัวที่ผมเคยเห็น รวมถึง Clang ในทางปฏิบัติทำแบบนั้น ดังนั้นจึงต้องมีวิธีบอกคอมไพเลอร์ว่าอย่ากังวลเรื่อง ABI และอย่าเสียเวลากับการ preserve รีจิสเตอร์ระหว่างการเรียก
      jump table แน่นอนว่าสร้างได้ดี แต่ถ้านำผลลัพธ์นั้นไปรันด้วยเครื่องมืออย่าง perf report และไบต์โค้ดทดสอบไม่ได้แทนลูปสั้น ๆ คุณจะเห็นอย่างใดอย่างหนึ่งในสองอย่างนี้: มี branch prediction miss ทุกครั้งที่ dispatch หรือคอมไพเลอร์คิดว่า “เหมือนกำลังพยายามทำอินเทอร์พรีเตอร์อยู่นะ” แล้วเลื่อน indirect jump ไปไว้ท้ายแต่ละ case เคยเห็นสิ่งนี้ใน Clang ไม่ว่าจะทางไหน การจัดสรรรีจิสเตอร์ของโค้ดที่ได้ก็น่าจะค่อนข้างแย่โดยรวม

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

    • C มักถูกใช้เป็นภาษาเป้าหมายของคอมไพเลอร์ภาษาระดับสูง
      ภาษาโปรแกรม Scheme กำหนดว่า tail call ทั้งหมดต้องไม่ทำให้สแตกโตขึ้น ดังนั้นผู้พัฒนาระบบจึงสำรวจเทคนิคต่าง ๆ รวมถึง trampoline
      ไม่มีเอกสารให้อ้างอิง แต่คงหาคำตอบได้จากงานวิจัยที่คอมไพล์ Scheme เป็น C ถ้าภาษาเป้าหมายไม่มีการรับประกัน tail call optimization โปรแกรมที่สร้างออกมาก็จะช้าลง
      นอกจากนี้ นี่ก็เป็นเหตุผลที่โดยเฉพาะผู้พัฒนาภาษาระดับสูงไม่พอใจที่ tail call optimization ถูกนำออกจากสเปก JavaScript มีวิธีแก้ที่รักษาทั้ง tail call optimization และ stack inspection ไว้ได้
      https://github.com/schemedoc/bibliography/blob/master/page8....
    • ผมคิดว่าเหตุผลที่ tail call optimization เร็ว เป็นเพราะลูปที่ได้คาดเดาได้ ทำให้ instruction prefetch และ memory prefetch ของ CPU ทำงานได้ดี
      ถ้ากระโดดด้วย function pointer ก็น่าจะคาดเดาไม่ได้เท่านั้น และคงได้ประโยชน์แบบเดียวกันได้ยาก
      แน่นอนว่าต้องวัดจริง และผมเองก็ยังไม่ได้ลอง

  • ผมเคยเขียนตัวถอดรหัส/เข้ารหัส Protobuf, parser ของ IML และ Python binding ด้วย C มาแล้ว และมีเรื่องอยากพูดเกี่ยวกับการวัดความเร็วในการ parse
    ถ้าไลบรารีนี้มีให้ใช้เฉพาะในรูปแบบ binding สำหรับภาษา managed ก็จะมีตัวแปรเพิ่มเติมด้านประสิทธิภาพที่ทำให้มันเหนือกว่าทุกอย่างอื่นอย่างท่วมท้น ไม่แน่ใจสำหรับ Ruby หรือ PHP แต่ใน Python ผมเห็นความเร็วเพิ่มขึ้นอย่างมากเมื่อไม่ใช้ enumerator การแปลง Protobuf enumerator ให้เป็น Python enumerator ทำให้ประโยชน์ใดๆ ที่ได้จากโค้ด C ถูกเวลาในการสร้างอ็อบเจ็กต์ Python จำนวนมากกลบไปหมด ความต่างอยู่ในระดับหลายหลัก ยิ่งไปกว่านั้น ยังอาจ implement โครงสร้างข้อมูลช่วยทั้งหมดใน C แล้ว expose ให้ Python แค่ interface ขั้นต่ำก็ได้ เป็นเรื่องตอบยากว่าการเปรียบเทียบแบบนี้ยุติธรรมแค่ไหนเมื่อเทียบกับโค้ดที่ใช้โครงสร้าง built-in ของ Python
    parser Protobuf สำหรับ Python ของ Google อาจยัง “เร็ว” กว่า 2GB/s ได้ เหตุผลคือมันไม่ parse อะไรเลยนอกจาก message ระดับบนสุด โครงสร้างภายในของ message จะถูก parse เมื่อจำเป็น ถ้าโค้ดอ่านเนื้อหาที่ parse แล้วทั้งหมดทันที ก็มีแนวโน้มว่าจะช้ากว่า 2GB/s แต่ปัญหาคือจะเปรียบเทียบสองแนวทางนี้ในทางปฏิบัติได้อย่างไร ไม่มีคำตอบที่ชัดเจน เพราะผลจริงจะแตกต่างกันตามลักษณะของแอปพลิเคชัน
    ในกรณีทั่วไป การ parse Protobuf ไม่สามารถทำแบบ streaming ได้เพราะการจัดการค่าซ้ำ ในทางปฏิบัติ โค้ดที่ parse เนื้อหา Protobuf จะติดคอขวดที่ I/O เพราะต้องรอให้ถึงท้าย message ก่อนจึงจะเริ่ม parse ได้ แยกจากเรื่องนี้ ขึ้นอยู่กับ message Protobuf ทั่วไปของแอปพลิเคชัน อาจทำการ parse แบบขนานได้ และถ้าเป็นเช่นนั้นก็มีแนวโน้มสูงที่จะนำหน้า parser แบบ single-thread ส่วนใหญ่ แต่เช่นเดียวกับตัวอย่างก่อนหน้า ไม่สามารถบอกได้ว่านี่เป็นกลยุทธ์ที่ชนะโดยทั่วไป
    โดยปกติแล้ว การผสานการ parse กับ การสร้าง domain object มักมีประสิทธิภาพกว่ามาก แอปพลิเคชันแทบจะต้องผ่านขั้นตอนนี้เสมอ วิธีที่ parser เข้าถึงฟังก์ชันนี้ได้มักเป็นตัวตัดสินว่า parser ใดจะชนะ
    สรุปคือ Protobuf และบางที parser โดยทั่วไป ไม่ใช่สิ่งที่ดีสำหรับการวัดความเร็วและการเปรียบเทียบ มันอยู่ระดับต่ำเกินไปและการออกแบบก็ไม่ดีพอจนยากจะใช้เป็นเกณฑ์ของ benchmark ด้านประสิทธิภาพ

    • ผมไม่เข้าใจส่วนที่บอกว่า “ในกรณีทั่วไป การ parse Protobuf ไม่สามารถทำแบบ streaming ได้เพราะการจัดการค่าซ้ำ”
      อยากให้ช่วยอธิบายละเอียดหน่อยว่ากฎที่ให้ field สุดท้ายเป็นฝ่ายชนะนั้นขัดขวางการ parse แบบ streaming อย่างไร

  • GCC และ Clang มีออปชัน -foptimize-sibling-calls มานานแล้ว จึงสามารถได้ tail call แม้ใน debug build
    แน่นอนว่าการทำให้ฟีเจอร์นี้เป็นมาตรฐาน มีการรับประกัน และควบคุมได้ในระดับฟังก์ชัน ถือเป็นการปรับปรุงครั้งใหญ่
    [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
    [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#t...