อย่าล้อเลียนตัวทำนายสาขาที่แสนสุขและน่าสนุก (2023)

 (mattkeeter.com)
1 คะแนน โดย GN⁺ 2024-07-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

อย่าล้อเลียนตัวทำนายสาขาที่แสนสุข

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

ตัวอย่างโค้ด

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

แปลเป็นแอสเซมบลี AArch64

// x0: const float* data
// x1: size_t n
// s0: 반환할 float
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // s1에서 읽고 s0에 누적
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

ความพยายามในการปรับแต่ง

  • พยายามลดคำสั่ง bl เพื่อเพิ่มประสิทธิภาพ
  • แต่กลับทำให้ประสิทธิภาพแย่ลงแทน

เปรียบเทียบประสิทธิภาพ

  • โค้ดต้นฉบับ: 969 ns
  • โค้ดที่ปรับแต่ง: 3.85 µs

วิเคราะห์สาเหตุ

  • ตัวทำนายสาขาสับสนเพราะคู่ bl และ ret ไม่ตรงกัน
  • ตามเอกสารของ ARM คำสั่ง ret ช่วยให้คาดเดาการคืนค่าจากฟังก์ชันได้ดีขึ้น

วิธีแก้

  • ใช้ br x30 แทน ret
  • ประสิทธิภาพกลับมา: 913 ns

การปรับแต่งเพิ่มเติม

  • อินไลน์ foo เพื่อเพิ่มประสิทธิภาพ
  • ใช้การ unroll ลูปและคำสั่ง SIMD

ประสิทธิภาพสุดท้าย

  • SIMD + unroll ลูปด้วยมือ: 94 ns

บทสรุป

  • อย่าทำให้ตัวทำนายสาขาสับสน
  • โค้ด SIMD เร็วกว่า แต่ผลลัพธ์อาจต่างกันได้เพราะการบวกเลขทศนิยมไม่เป็นไปตามสมบัติการเปลี่ยนหมู่

ความเห็นของ GN⁺

  • บทความนี้แสดงให้เห็นความสำคัญของการปรับแต่งแอสเซมบลี AArch64 ได้อย่างดี
  • การเข้าใจหลักการทำงานของตัวทำนายสาขาเป็นสิ่งจำเป็นต่อการปรับแต่งประสิทธิภาพ
  • การปรับแต่งด้วยคำสั่ง SIMD มีประสิทธิภาพมาก แต่ต้องคำนึงถึงปัญหาเรื่องความแม่นยำ
  • หากใช้ภาษาในระดับสูงอย่าง Rust ก็สามารถเพิ่มประสิทธิภาพได้ง่ายผ่านการปรับแต่งของคอมไพเลอร์
  • โปรเจ็กต์ที่มีลักษณะใกล้เคียงกัน ได้แก่ คู่มือการปรับแต่งแอสเซมบลีของ Agner Fog

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

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

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

  • มีการสรุปบทความร่วมกับเพื่อน ๆ จากยุค Apple II

    • โค้ดที่ปรับแต่งแล้วใช้เวลา 94 นาโนวินาทีในการบวกเลขทศนิยมลอยตัว 32 บิตจำนวน 1024 ค่า
    • 6502 ที่ 1 MHz จะยังคงพยายามดึงไบต์แรกของคำสั่งแรกจากหน่วยความจำอยู่ในช่วง 94 นาโนวินาทีนั้น
    • โค้ดนี้ทำงานได้เต็มประสิทธิภาพที่ปรับแต่งไว้ก็ต่อเมื่อรันจากแคชเท่านั้น DRAM ช้า

  • Raymond Chen เคยพูดถึงหัวข้อเดียวกันนี้เมื่อเกือบ 20 ปีก่อน

    • หลังจากตรวจสอบการจบลูปแล้ว ก็ข้ามไปยังฟังก์ชัน foo โดยไม่มีการแตกแขนง
    • นั่นเป็นการขัดกับฮิวริสติกการทำนายพื้นฐาน
    • การที่ตัวทำนายการแตกแขนงเก็บ shadow stack ของที่อยู่สำหรับ return นั้นมีมานานหลายสิบปีแล้ว

  • ในโค้ด SIMD สามารถบวกผลรวมในลำดับที่ต่างออกไปได้ เพราะการบวกเลขทศนิยมลอยตัวไม่เป็นไปตามสมบัติการเปลี่ยนหมู่

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

  • ตั้งแต่ Rust 1.78 เป็นต้นมา คอมไพเลอร์ใช้การ unroll ลูปที่ดุดันขึ้นและมี SIMD อยู่บ้าง

    • การ unroll ลูปเริ่มมาตั้งแต่ Rust 1.59
    • ในโค้ดบน Github ใช้ Rust เวอร์ชัน 1.67.0-nightly อยู่

  • มีความสับสนว่า x0 เพิ่มค่าอย่างไรในแอสเซมบลี ARM/ARM64

    • คำสั่ง ldr s1, [x0], #4 จะโหลดข้อมูลพร้อมเพิ่มค่า x0 ขึ้น 4
    • x86_64 ไม่มีคำสั่งเดี่ยวที่ทั้งโหลดและเพิ่มค่าได้ในครั้งเดียว

  • น่าแปลกใจที่ไม่ได้ลองวิธีที่ซับซ้อนน้อยกว่านี้เพื่อปรับแต่งโค้ดแอสเซมบลี

    • สามารถเขียนโค้ดแอสเซมบลีใหม่ให้ต้องใช้การแตกแขนงเพียงครั้งเดียวที่ด้านล่างของลูปได้
    • สามารถ inline foo และตัดคำสั่ง RET ออกได้

  • มีความเห็นว่าอยากให้ผู้เขียนเลิกเปลี่ยนหน่วยไปมาอยู่ตลอด