- การที่อันดับเบนช์มาร์ก related_post_gen ของ Neat สูงขึ้นไม่ได้มาจากการปรับแต่งระดับสูง แต่เกิดจากการเปลี่ยน ABI เล็ก ๆ โดยส่งอาร์เรย์เป็น อาร์กิวเมนต์พอยน์เตอร์ 3 ตัว แทน struct ขนาด 24 ไบต์
- อาร์เรย์ของ Neat ต้องมีพอยน์เตอร์ฐานของอ็อบเจ็กต์อาร์เรย์นอกเหนือจากพอยน์เตอร์เริ่มต้นและสิ้นสุด เพราะมีตัวนับอ้างอิง จึงต่างจากอาร์เรย์ของ D ที่มีขนาด 16 ไบต์ และไปใช้เส้นทางการส่งผ่านหน่วยความจำของ SystemV AMD64 ABI
- aggregate บางชนิดที่มีขนาดเกิน 16 ไบต์จะถูกคัดลอกค่าลงสแตกเมื่อเรียก แล้วส่งต่อเป็นพอยน์เตอร์ ทำให้เสียประโยชน์จากการส่งผ่านรีจิสเตอร์ และเพิ่มต้นทุนการสับเปลี่ยนสแตก
- ในตัวอย่างเบนช์มาร์ก หากส่ง
struct Vector { double x, y, z; } เป็น struct การรัน 1 พันล้านครั้งใช้เวลา 12.3 วินาที แต่หากส่งฟิลด์เป็นอาร์กิวเมนต์แยกกันจะลดเหลือ 5.3 วินาที
- C API ต้องทำตาม C ABI แต่สำหรับชนิดข้อมูลอย่างอาร์เรย์ ทูเพิล และ sumtype ภายใน runtime ของภาษาเอง เมื่อมีขนาดเกิน 16 ไบต์ ก็คุ้มค่าที่จะเบนช์มาร์กการ แยกฟิลด์เพื่อส่งต่อ
คอขวดที่ปรากฏใน Neat
- Neat ขยับอันดับขึ้นหลายขั้นในเบนช์มาร์ก related_post_gen
- ประสิทธิภาพที่ดีขึ้นไม่ได้มาจาก optimization pass ระดับสูงใหม่ แต่เป็นผลจากการเปลี่ยนวิธีส่งต่ออาร์เรย์
- เดิม: อาร์กิวเมนต์ struct ที่บรรจุพอยน์เตอร์ 3 ตัว
- เปลี่ยนเป็น: ส่ง พอยน์เตอร์ 3 ตัวแยกเป็นอาร์กิวเมนต์แต่ละตัว
- เมื่อเทียบกับ D แล้ว Neat ช้ากว่าที่คาด และ profiler แสดงพฤติกรรมการย้ายพื้นที่ขนาดใหญ่บนสแตกเพื่อเรียกฟังก์ชัน
- คอขวดจึงใกล้เคียงกับ ต้นทุนการจัดวางสแตกใหม่ ณ ตอนเรียก มากกว่าการคำนวณเอง
ทำไมอาร์เรย์ของ Neat จึงมีขนาด 24 ไบต์
- ต่างจากอาร์เรย์ของ D, Neat ใช้ ตัวนับอ้างอิง
- อาร์เรย์ของ Neat มีพอยน์เตอร์ 3 ตัวดังนี้
- พอยน์เตอร์เริ่มต้น
- พอยน์เตอร์สิ้นสุด
- พอยน์เตอร์ฐานของอ็อบเจ็กต์อาร์เรย์ที่เก็บ reference count
- พอยน์เตอร์ 3 ตัวมีขนาด 24 ไบต์ จึงไปคนละเส้นทางในกฎการส่งอาร์กิวเมนต์ของ AMD64 เมื่อเทียบกับอาร์เรย์ 16 ไบต์ที่มีพอยน์เตอร์ 2 ตัว
- เหตุผลที่อาร์เรย์ของ D เร็วและอาร์เรย์ของ Neat ช้า คือเมื่อมีขนาด 24 ไบต์ มันข้าม ขอบเขต 16 ไบต์
ขอบเขต 16 ไบต์ของ SystemV AMD64 ABI
- SystemV AMD64 ABI specification กำหนดว่า หาก aggregate บางชนิดมีขนาดเกิน two eightbytes จะส่งอาร์กิวเมนต์ทั้งหมดผ่านหน่วยความจำ
- การส่ง struct ผ่านหน่วยความจำ ฝั่ง caller ต้องทำงานต่อไปนี้
- จัดสรรพื้นที่บนสแตกเท่ากับขนาดของ struct
- เติมพื้นที่นั้นด้วยค่าที่จะส่งต่อ
- ส่งพอยน์เตอร์ของตำแหน่ง struct นั้นให้ฟังก์ชัน
- ในกรณีนี้ ค่า必须อยู่บน สแตก ทำให้ LLVM มีพื้นที่สำหรับ optimization น้อยลง
- ค่าต้องถูกคัดลอกจากรีจิสเตอร์ไปยังสแตก และยังต้องติดตามว่าส่วนใดของสแตกกำลังถูกใช้ และส่วนใดสามารถนำกลับมาใช้ซ้ำได้
- LLVM แสดงผลลัพธ์ไม่ดีนักในการติดตามการใช้สแตกซ้ำแบบนี้
เบนช์มาร์กเวกเตอร์ double 3 ตัว
- เบนช์มาร์กใช้เวกเตอร์ 3 ฟิลด์ในรูปแบบ
struct Vector { TYPE x, y, z; };
TYPE ถูกกำหนดเป็น double
- ฟังก์ชันทั้งสองทำการบวกแบบเดียวกัน แต่ต่างกันที่วิธีส่งอาร์กิวเมนต์
vector_add_struct(struct Vector left, struct Vector right) รับ struct ขนาดใหญ่เป็นอาร์กิวเมนต์
vector_add_fields(...) รับ left_x, left_y, left_z, right_x, right_y, right_z เป็นอาร์กิวเมนต์แยกกัน
mode และความยาวการรันถูกส่งเข้ามาเป็น command-line arguments เพื่อไม่ให้ optimizer ทำ constant folding กับการคำนวณทั้งหมดได้
impl.c ถูกคอมไพล์แยกต่างหากเพื่อหลีกเลี่ยง inlining
clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000
- ผลลัพธ์คือ 12.3 วินาที สำหรับการส่ง struct และ 5.3 วินาที สำหรับการส่งฟิลด์แยกกัน
ความแตกต่างที่เห็นใน assembly
- เวอร์ชันที่ส่ง struct ใช้คำสั่งจำนวนมากไปกับ การสับเปลี่ยนสแตก
- เวอร์ชันที่ส่งฟิลด์ได้เปรียบตรงที่พารามิเตอร์อยู่ใน รีจิสเตอร์ SSE อยู่แล้วเมื่อเข้าสู่ฟังก์ชัน
- เวอร์ชันที่ส่ง struct ต้องโหลดค่าจากสแตกทุกครั้ง
- SystemV ABI มีเป้าหมายจะส่งค่าให้ผ่านรีจิสเตอร์มากที่สุด แต่ในกรณีนี้ ประโยชน์นั้นหายไปเพราะ struct มีขนาดเกิน 16 ไบต์
- เมื่อพิจารณาจำนวนรีจิสเตอร์ที่ใช้ได้บน AMD64 ผู้เขียนมองว่าการส่งค่ากับชนิดที่เกิน 16 ไบต์ก็น่าจะยังมีประโยชน์
สถานการณ์ที่คล้ายกับ cdecl
- วิธีที่เขียนฟิลด์ลงสแตกแล้วส่งพอยน์เตอร์ สุดท้ายแล้วคล้ายกับ ABI
cdecl บน x86 รุ่นเก่าที่ส่งทุกอย่างผ่านสแตก
cdecl เป็นที่รู้กันว่าช้า และมี calling convention หลายแบบเกิดขึ้นเพื่อทำให้เร็วขึ้น
- ปัญหาคือ AMD64 System V ABI ในกรณีนี้ทำงานเหมือนวิธีส่งผ่านสแตกแบบเก่า เพราะขนาดของ struct
ข้อยกเว้นเรื่อง inlining และ LTO
- ในโค้ดจริง ฟังก์ชันแบบนี้อาจถูก inline ทั้งหมดได้
- เมื่อเปิด LTO ใน
gcc ความแตกต่างด้านประสิทธิภาพระหว่างสองเวอร์ชันจะหายไป
- ใน
clang ไม่ได้ผลลัพธ์แบบเดียวกัน
- ไม่ใช่ทุกฟังก์ชันที่จะ inline ได้ หรือควรถูก inline
คำแนะนำสำหรับผู้พัฒนาภาษาและการปรับแต่ง API
- เมื่อเรียก C API ต้องทำตาม C ABI
- อย่างไรก็ตาม ชนิดข้อมูลระดับสูงภายในภาษาที่ไม่ใช่ C แม้ backend จะมองเห็นเหมือน struct ก็ไม่จำเป็นต้องแทนเป็น struct เดียวเสมอไป
- ผู้พัฒนาภาษาสามารถกำหนดเองได้ว่าจะส่งอาร์เรย์ ทูเพิล sumtype ฯลฯ อย่างไร
- ใน Neat เลือกให้ส่งชนิดเหล่านี้ที่เกิน 16 ไบต์เป็นฟิลด์แยกกัน และเห็นข้อได้เปรียบในเบนช์มาร์ก
- หากกำลังทำ implementation ของภาษาบน AMD64 หรือปรับแต่ง API แบบละเอียด ควรเบนช์มาร์กว่าการแยก struct ที่เกิน 16 ไบต์ด้วยมือช่วยได้หรือไม่
- โดยเฉพาะใน inner loop ความต่างด้านประสิทธิภาพอาจมากกว่าที่คาด
เพิ่มเติม: struct ที่มี double และ SSE
- คำถามคือ
double อยู่ในคลาส SSE ตาม specification แล้วทำไม struct จึงไม่ถูกส่งผ่านรีจิสเตอร์ SSE
- คำตอบคือไม่ทราบเหตุผล แต่ในทางปฏิบัติมันไม่ได้ถูกส่งแบบนั้น
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ปัญหาตรงนี้คือ SysV amd64 ABI ไม่จำเป็นต้องใช้ SysV เป็น ABI ภายในภาษา ถ้าไม่ได้เปิดเผยให้ผู้เรียกแบบ SysV C ใช้ ก็สามารถใช้ calling convention แบบที่ต้องการได้
https://llvm.org/docs/LangRef.html#calling-conventions
สำหรับคนที่สงสัย การเปลี่ยนแปลงที่เกี่ยวข้องของ neatlang อยู่ที่นี่: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
ดูซับซ้อนกว่าการเปลี่ยนเอาต์พุต calling convention ของ LLVM อย่างมาก บางทีผู้เขียนอาจอยากเปิดเผย type เหล่านี้ให้โปรแกรม C ใช้ด้วย calling convention ที่แน่นอนตายตัว
ไม่ต้องทำตามธรรมเนียมแบบหลับหูหลับตา แค่เลือกวิธีที่สมเหตุสมผลที่สุดในสถานการณ์นั้น ๆ
โดยเฉพาะ ABI มักเอนเอียงไปทางความเข้ากันได้กับ CPU รุ่นเก่ากว่า และ CPU รุ่นใหม่กว่าอาจมีช่องให้ปรับปรุงได้โดยใช้ฟีเจอร์อย่างรีจิสเตอร์ขยาย โดยไม่ต้องลดขนาด struct ลง ซอฟต์แวร์ที่จูนให้ฮาร์ดแวร์หรือเจเนอเรชันเฉพาะจะใช้กับบางเครื่องไม่ได้ จึงอาจไม่ดึงดูดนัก แต่ถ้าอยากปรับโค้ดให้เหมาะกับฟีเจอร์ฮาร์ดแวร์ของระบบตัวเองแบบสุด ๆ การมีคอมไพเลอร์ที่สร้างเอาต์พุตแบบนั้นได้ก็คงยอดเยี่ยม
ต้นทุนการส่งอาร์กิวเมนต์ มักถูกทำความเข้าใจไม่ดี จึงดีใจที่ได้เห็นบทความแบบนี้ แม้แต่ที่อย่าง Google ก็ยังพบได้บ่อยกับการส่ง object ขนาด 24 ไบต์แบบ by value และต้นทุนของมันกระจายไปทั่วทุกฟังก์ชันจน profiler มองไม่ค่อยเห็น
แต่ก็มีข้อสะดุดแบบนี้โผล่มาให้เห็น: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
ข้อยกเว้นเดียวที่นึกออกคือประมาณ string_view
ถ้าโชคร้ายเกิด cache miss ก็อาจต้องรอราว 100 นาโนวินาทีเพื่อดึง object ขนาด 24 ไบต์จากหน่วยความจำหลัก แต่ถ้าส่ง object เดียวกันโดยตรง มันจะอยู่บน stack จึงมีโอกาสสูงว่าจะอยู่ใน cache
ตอนย้ายไป x64 ครั้งแรก ผมกังวลว่า vec3 object ในงานกราฟิกส์ (float 3 ตัว) จะขยายจาก sizeof()=12 เป็น 16 ไบต์ เลย benchmark graphics engine อย่างหนัก
ไม่น่าแปลกใจที่เพราะการจัดแนวการอ่าน 8 ไบต์ ขนาด 16 ไบต์จึงเร็วกว่า 12 ไบต์ ทั้งภายในและบน GPU ดังนั้น vec3 จึงกลายเป็น vec4 ไปเงียบ ๆ และยังมี vec4 แยกต่างหากอยู่เหมือนเดิม เช่นเคย ควร benchmark จาก มุมมองภาพรวมทั้งหมด ไม่ใช่ benchmark เฉพาะจุด
เข้าใจว่าถ้าเป็น 16 ไบต์ การเข้าถึงหลายแบบอาจกลายเป็น 2x8 ไบต์ที่จัดแนวแล้ว หรือ 1x16 ไบต์ แทนที่จะเป็น 3x4 ไบต์ แต่กับการเข้าถึงแบบอื่นอาจไม่เป็นแบบนั้นมากนัก และยังมีปัญหา แรงกดดันต่อ cache เพิ่มขึ้น ด้วย
ตามสามัญสำนึก ค่าที่ส่งผ่านรีจิสเตอร์สามารถถูกโหลดล่วงหน้าได้ด้วย speculative execution จึงเร็วกว่าการเขียนลง stack และการจัดการ stack ก็เร็วกว่า heap allocation
ดังนั้นโค้ด spaghetti เลอะเทอะที่มี global variable เต็มไปหมดจึงเร็วมาก ส่วนฟังก์ชัน recursive อันสง่างามหรืออาร์กิวเมนต์แบบ tuple/struct/list กลับช้าอย่างไม่น่าเชื่อ แบบแรก optimize ให้เป็น ลูปแอสเซมบลีที่แน่นหนา ได้ง่ายกว่ามาก
ถ้าโค้ดที่สง่างามเป็น O(n) แต่โค้ด spaghetti เป็น O(n^2) คุณอาจสัมผัสความต่างได้ ต้องพิจารณาการบำรุงรักษาด้วย ในแง่หนึ่ง คอมไพเลอร์มีอยู่เพื่อแปลงวิธีแก้ปัญหาที่สง่างามของเราให้กลายเป็นโค้ด spaghetti
global object ยังขัดขวางการ optimize ของคอมไพเลอร์ด้วย
สำหรับข้อมูลอ้างอิง ใน MSVC ขนาด cutoff ก่อนที่ struct จะถูกส่งผ่าน stack คือ 8 ไบต์ นี่เป็นรายละเอียดของ ABI จึงไม่ควรพึ่งพาในโค้ดที่ต้องการความสามารถในการพอร์ต
แต่ถ้าเป็นฟังก์ชันที่ไม่ได้ถูกเรียกบ่อย ก็ไม่จำเป็นต้องเครียดมากนัก ถ้าเป็นฟังก์ชันเล็ก ๆ ที่ถูกเรียกบ่อยเหมือนในตัวอย่าง ก็แค่ทำให้คอมไพเลอร์สามารถ inline โค้ดด้วยวิธีอย่าง LTO ได้ จากนั้นการ optimize ที่มีประโยชน์ยิ่งกว่าการส่งอาร์กิวเมนต์ผ่านรีจิสเตอร์ก็จะเปิดทางขึ้น
ผมจัดบทความแนวนี้ไว้ในหมวด “ความรู้ที่พอดีจะสร้างเรื่องปวดหัวได้” แม้จะทำตามคำแนะนำโดยคอมไพล์แยกต่างหากเพื่อบังคับให้คอมไพเลอร์สร้างฟังก์ชันที่เรียกผ่าน ABI ได้ แต่ LTO ก็อาจย้อนแก้ข้อผิดพลาดนี้กลับมาได้
ถ้าบิลด์โปรแกรมนี้ด้วย LTO ทั้งสองโหมดจะเร็วขึ้นอย่างมากกว่าโหมดใด ๆ ของโปรแกรมที่ไม่มี LTO หากเป็นโปรแกรมที่ไวต่อประสิทธิภาพ ควรทำ profiling แล้วปรับแต่งคอขวดให้ถึงที่สุดก่อนจึงค่อย commit วิธีทำอย่างการแยก struct ออกเป็นอาร์กิวเมนต์
เรื่องนี้เกิดกับโค้ดที่คอมไพเลอร์สร้างแทบทั้งหมด Valgrind น่าจะวัดได้ แต่ sampling profiler อาจทำไม่ได้ และไม่มีเครื่องมือที่ช่วยเน้น ปัญหาการสร้างโค้ด ที่กระจัดกระจายแบบนี้
ใน cdecl calling convention พื้นฐานของ Windows struct ที่ใหญ่กว่า 8 ไบต์จะไม่ถูกส่งผ่าน register [1]
[1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...
บน amd64 ถึงจะใช้ SysV amd64 ABI การส่งและคืนค่า struct ที่ใหญ่กว่า 16 ไบต์แบบ by value ก็ทำได้เต็มที่ แค่ช้าเท่านั้น
ถึงอย่างนั้นก็มีหลายกรณีที่การส่งค่า by value คุ้มค่าเพื่อให้โค้ดชัดเจนขึ้น แน่นอนว่าไม่ใช่กรณีนี้ แต่ตามที่ loeg ชี้ไว้ ภายในภาษาของตัวเองก็ใช้ ABI แบบกำหนดเอง ได้ เหมือนคอมไพเลอร์ C++, Go, OCaml, SBCL
ในตัวอย่างที่ให้มา สามารถแก้ได้โดยเปลี่ยนชนิดพารามิเตอร์จาก “struct Vector” เป็น “const struct Vector &” เพื่อ ส่งผ่านด้วย reference โดยไม่กระทบผู้เรียก
ผมเคยเห็นโค้ด C++ จำนวนมากที่มีบั๊กจาก pointer เพราะใช้ pointer ทั้งที่จริง ๆ แล้วส่งผ่านด้วย reference ก็พอ และใช้ง่ายกว่า ปลอดภัยกว่า
เพราะ ABI กำหนดให้ส่งค่าผ่าน pointer จึงต้องเก็บไว้ที่ไหนสักแห่งเพื่อให้ได้ pointer และสิ่งเดียวกับตอนระบุเป็น const-ref ก็เกิดขึ้น ถ้าเปลี่ยนค่า struct เป็นอาร์กิวเมนต์แยกกัน ก็จะส่งอาร์กิวเมนต์ผ่าน register ได้
ผมเคยค่อนข้างคิดมาตลอดว่า LLVM คงจัดการเรื่องแบบนี้ให้เรียบร้อยได้ดี แต่ปรากฏว่าไม่ใช่
ประโยชน์ที่อธิบายไว้คือการหลีกเลี่ยง serialization จาก register ลง stack ทั้งหมด ซึ่งดูเหมือนว่าการส่งผ่านด้วย reference จะหลีกเลี่ยงไม่ได้
ถ้าอนุญาตให้ใช้ C++ ก็จะมีทางเลือกมากขึ้น เช่น move argument เพื่อลดการคัดลอก
กฎจากประสบการณ์ที่ได้ยินมาตลอดใน C++ คือ อะไรก็ตามที่ไม่ใช่ primitive type ให้ส่งผ่าน reference เว้นแต่จะมีเหตุผลดีพอที่จะส่ง by value และถ้าจำเป็นจริง ๆ ค่อยส่งผ่าน pointer
ทั้งเพราะ ABI และเพื่อหลีกเลี่ยง copy constructor หรือ move constructor นี่เป็นรายละเอียดระดับต่ำที่น่าเบื่อ แต่ถ้าต้องการประสิทธิภาพสูงสุดใน C++ ก็เป็นสิ่งที่ต้องใส่ใจ พูดให้ชัด นี่เป็นแค่การ optimize ประสิทธิภาพเท่านั้น โค้ดที่ส่ง struct ยังทำงานถูกต้อง เพียงแต่ช้ากว่า