อย่าล้อเล่นกับ Happy Fun Branch Predictor (2023)

 (mattkeeter.com)
1 คะแนน โดย GN⁺ 2024-07-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • การปรับแต่งที่พยายามลด branch หนึ่งตัวในลูปบน AArch64 assembly กลับทำให้ ช้าลง 4 เท่า โดยสาเหตุคือการใช้คู่เรียก-คืนค่า bl/ret แบบไม่สมมาตรจนทำให้ branch predictor สับสน
  • โค้ดเดิมมีการ branch สองครั้งต่อรอบลูปคือ bl foo และ b loop แต่โค้ดที่แก้ไขพยายาม ลดจำนวน branch โดยใช้ bl loop เพียงครั้งเดียวเพื่อกำหนด x30 ให้คงที่ แล้วให้ ret หลายครั้งกลับไปยังที่อยู่เดียวกัน
  • จากผลการบวกอาร์เรย์ float 1024 ตัวบน M1 Max โค้ด bl/ret ปกติใช้เวลา 969ns แต่โครงสร้างแบบ bl หนึ่งครั้งกับ ret หลายครั้ง ช้าลงเป็น 3.85µs และเมื่อเปลี่ยน ret เป็น br x30 เวลากลับมาที่ 913ns
  • ตัวนับประสิทธิภาพของ Instruments แสดงว่าในการรวมค่า 1 พันล้าน element โครงสร้าง bl/ret แบบไม่สมมาตรมีการทำนาย branch สำหรับ return ผิดพลาดราว 93% และ FETCH_RESTART, MAP_DISPATCH_BUBBLE, MAP_REWIND ก็เพิ่มขึ้นมากเช่นกัน
  • การทำให้เร็วขึ้นต่อยอดไปจากการ inline foo, ใช้ Rust iter().sum(), NEON SIMD และการ unroll ลูปด้วยมือ โดยเวอร์ชัน SIMD สุดท้ายลดลงเหลือ 94ns แต่ลำดับการบวก floating-point เปลี่ยนไป จึง อาจได้ผลลัพธ์ต่างกัน

ผลย้อนกลับในลูป AArch64

  • ฟังก์ชันตัวอย่างมีโครงสร้างที่วนผ่านอาร์เรย์ float แล้วส่งค่าแต่ละตัวให้ foo โดย foo จะอัปเดตค่ารวมสะสม g
  • การแปลงเป็น AArch64 แบบตรงไปตรงมามี flow ดังนี้
    • ตรวจสอบที่จุดเริ่มลูปว่า n == 0 หรือไม่
    • อ่านค่าด้วย ldr s1, [x0], #4
    • เรียก subroutine ด้วย bl foo
    • ret ของ foo กลับมายังคำสั่งถัดจาก bl
    • ใช้ b loop เพื่อย้ายกลับไปยังจุดเริ่มลูป
  • foo มีรูปแบบใกล้เคียงกับ naked function ที่ใช้ stack frame และ register เดียวกับฟังก์ชันแม่ โดยอ่าน s1 แล้วสะสมใน s0

บทบาทของ bl และ ret

  • bl คือคำสั่ง branch and link ซึ่งกระโดดไปยัง label ที่กำหนด พร้อมบันทึกที่อยู่ของคำสั่งถัดไปไว้ใน link register lr หรือ x30
  • ret จะกระโดดไปยังที่อยู่ที่อยู่ใน link register
  • ในโครงสร้างเดิม bl foo กับ ret จะจับคู่กัน และ ret จะกลับไปยังคำสั่งถัดจาก bl นั้นเสมอ

การปรับแต่ง “ลด branch หนึ่งตัว” ที่ล้มเหลว

  • โครงสร้างที่แก้ไขพยายามลด branch หนึ่งตัวในลูปโดยไม่เปลี่ยน foo
    • เรียก bl loop ตอนเริ่มฟังก์ชันเพื่อใส่ที่อยู่เริ่มต้นของ loop ลงใน x30
    • หลังตรวจสอบเงื่อนไขจบลูปแล้ว ปล่อยให้ไหลต่อเข้าโค้ด foo โดยไม่มี branch แยก
    • ret ของ foo จะกลับไปยัง loop ที่อยู่ใน x30
  • ในโครงสร้างนี้ x30 จะไม่เปลี่ยนใน body ของลูป ดังนั้น ret ที่เกิดซ้ำจะกลับไปยังที่อยู่เดียวกันเสมอ
  • foo แบบง่ายคือโค้ดบรรทัดเดียวที่บวก float ดังนี้
foo:
    fadd s0, s0, s1
    ret
  • ในกรณีนี้ ฟังก์ชันทั้งหมดจะคำนวณผลรวมของอาร์เรย์ float ที่รับเข้ามา

ผล benchmark และปัญหา branch prediction

  • ใช้ criterion benchmark อาร์เรย์ 1024 element บน CPU M1 Max
    • bl/ret ปกติ: 969ns
    • bl หนึ่งครั้ง, ret หลายครั้ง: 3.85µs
  • โค้ดที่ลด branch หนึ่งตัวกลับช้ากว่าโค้ดเดิมที่ใช้สอง branch ราว 4 เท่า
  • Cliff และ Dan มองว่าเพราะคู่ bl/ret ไม่ตรงกัน จึงทำให้ branch predictor สับสน
  • ตาม เอกสารของ ARM RET ทำให้โปรเซสเซอร์รับรู้ว่าเป็นการ return จากฟังก์ชัน จึงช่วยให้ทำนาย branch ได้แม่นยำขึ้น
    • BR LR ก็ทำงานแบบเดียวกันได้ในเชิงฟังก์ชัน
    • แต่ RET เป็นคำสั่งแยกที่โปรเซสเซอร์รับรู้ได้ว่าเป็นการ return จากฟังก์ชัน
    • หากทำนาย branch ถูกต้อง pipeline จะได้รับคำสั่งที่ถูกต้อง และหลีกเลี่ยงเวลาที่ต้องรอคำสั่งจากหน่วยความจำได้

Return address stack และการทดลอง br x30

  • branch predictor มีความเป็นไปได้ว่าจะดูแล stack ของที่อยู่ return ภายใน
    • เมื่อรัน bl จะ push ที่อยู่ return ลง stack
    • เมื่อเห็น ret จะสมมติว่าจะกลับไปยังที่อยู่ return ของ bl ล่าสุด
    • เริ่ม prefetch และ speculative execution ตามที่อยู่นั้น แล้ว pop ออกจาก stack
  • วิธีนี้ทำงานได้ดีเมื่อ bl/ret เป็นคู่ที่ตรงกัน
  • หาก ret หลายครั้งใช้ที่อยู่เดียวกันซ้ำ ๆ การทำนายจะล้มเหลว และอาจเกิด prefetch ที่ไร้ประโยชน์, speculative execution ที่ผิดพลาด, pipeline stall หรือ flush
  • เมื่อเปลี่ยน ret เป็น br x30 ตามข้อเสนอของ Dan ปัญหาประสิทธิภาพตกก็หายไป
    • bl/ret ปกติ: 969ns
    • bl หนึ่งครั้ง, ret หลายครั้ง: 3.85µs
    • bl หนึ่งครั้ง, br x30 หลายครั้ง: 913ns
  • เวอร์ชัน br x30 ทำ branch เพียงหนึ่งครั้งต่อรอบลูป จึงเร็วกว่าโค้ดเดิมเล็กน้อย

ตัวนับประสิทธิภาพของ Instruments

  • ตรวจสอบตัวนับประสิทธิภาพของสองโปรแกรมแรกด้วย Instruments
  • การวัดทำระหว่างรวมค่าอาร์เรย์ 1 พันล้าน element
  • ใน bl/ret แบบไม่สมมาตร มีการทำนาย branch สำหรับ return ผิดพลาดราว 93%
ตัวนับ bl/ret ปกติ bl หนึ่งครั้ง, ret หลายครั้ง
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928,644,975
FETCH_RESTART 61,121 987,765,276
MAP_DISPATCH_BUBBLE 1,155,632 7,350,085,139
MAP_REWIND 6,412,734 2,789,499,545
  • Apple ไม่ได้จัดทำเอกสารตัวนับเหล่านี้ไว้อย่างครบถ้วน
  • ตัวนับอื่น ๆ คาดว่าเป็นผล downstream ของ branch prediction ที่แย่
    • FETCH_RESTART: อาจเป็น prefetch ที่ผิดพลาด
    • MAP_DISPATCH_BUBBLE: อาจเกี่ยวข้องกับ pipeline stall
    • MAP_REWIND: อาจเป็น speculative execution ที่ผิดพลาดและต้องย้อนกลับ

วิธีทำให้เร็วขึ้น

  • ตัวอย่างนี้เป็นโค้ดเพื่อการศึกษา และเหตุผลที่ foo เป็น subroutine ก็ใกล้เคียงกับโครงสร้างเพื่ออธิบายมากกว่า “โค้ดที่เร็วที่สุดเท่าที่เป็นไปได้”
  • หากรู้เนื้อหาของ foo ตอน build และสั้นกว่าระยะกระโดดสูงสุด ก็สามารถลบ bl กับ ret ออกทั้งหมดแล้วทำ inline ได้
    • เร็วขึ้นจาก 969ns เป็น 911ns หรือประมาณ 6%
  • ถ้าใช้ Rust แบบง่าย ๆ ด้วย f.iter().sum() จะลงไปได้ถึง 833ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD และการ unroll ลูปด้วยมือ

  • การใช้งาน AArch64 SIMD ด้วยมือประกอบด้วยสามลูป
    • loop: บวกค่าแต่ละตัวเข้า s0 จนกว่าจำนวนค่าที่เหลือจะเป็นพหุคูณของ 4
    • simd: บวกค่า 4 ตัวในครั้งเดียวเข้า vector register v1 และวนซ้ำจนกว่าจำนวนค่าที่เหลือจะเป็นพหุคูณของ 8
    • simd2: unroll simd เป็น 2 เท่า โดยประมวลผล 8 ค่าในแต่ละรอบ และรวมสะสมใน v1 กับ v2
  • เมื่อจบฟังก์ชัน จะสะสมค่าจาก v1 และ v2 ลงใน s0 แล้ว return
  • type punning เป็นวิธีที่ปฏิบัติต่อ x0 ซึ่งเป็น float* ราวกับเป็น double* เพื่ออ่าน 128 บิต หรือ float 4 ตัว เป็น d3 และ d4
    • ใช้ mov v3.d[1], v4.d[0] เพื่อย้าย 64 บิตของ d4 ไปยัง 64 บิตบนของ v3
    • ใน fadd v1.4s, v1.4s, v3.4s ใช้ suffix .4s เพื่อประมวลผลเหมือน float สี่ตัว
  • การใช้งาน SIMD นี้รันใน 94ns เร็วกว่าเวอร์ชัน Rust ที่ดีที่สุดก่อนหน้า 833ns ราว 8.8 เท่า

สรุปประสิทธิภาพทั้งหมดและข้อควรระวัง

การใช้งาน เวลา
bl/ret ปกติ 969ns
bl หนึ่งครั้ง, ret หลายครั้ง 3.85µs
bl หนึ่งครั้ง, br x30 หลายครั้ง 913ns
ลูปธรรมดาที่ใช้ b 911ns
เขียนใหม่ด้วย Rust 833ns
SIMD + unroll ลูปด้วยมือ 94ns
  • โค้ด SIMD เปลี่ยนลำดับการบวก floating-point
  • การบวก floating-point ไม่มีสมบัติการเปลี่ยนกลุ่ม ดังนั้นเวอร์ชัน SIMD อาจไม่ได้ผลลัพธ์เดียวกัน กับโค้ดเส้นตรง
  • นี่อาจเป็นเหตุผลที่ compiler ไม่สร้างคำสั่ง SIMD สำหรับการรวมค่า
  • โค้ดทั้งหมดเผยแพร่บน GitHub
  • สามารถรัน cargo bench บนเครื่อง ARM64 เพื่อทำซ้ำ benchmark ได้

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

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

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

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

    • โชคดีที่ตอนนี้ ขนาด L1 cache ทั้งหมดใหญ่พอ ๆ กับหน่วยความจำทั้งหมดที่ 6502 เคย address ได้แล้ว เราอยู่ในยุคที่น่าทึ่งจริง ๆ

  • Raymond Chen เคยพูดถึงเรื่องเดียวกันนี้มาเกือบ 20 ปีก่อน: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • ในฐานะคนที่มีคู่มืออ้างอิงชุดคำสั่งสถาปัตยกรรม x86/64 ของ Intel แบบหนังสือกระดาษ หรือที่เรียกกันว่าหนังสือสีน้ำเงินเล่มหนา และอ่าน datasheet กับเอกสารอย่างละเอียด ผมจึงระวังเสมอเวลามีคนบอกว่า “โดยสัญชาตญาณน่าจะเป็น X แต่กลับเกิด Y”
      นอกจากความเข้าใจพื้นฐานเรื่องคุณสมบัติเซมิคอนดักเตอร์ของซิลิคอนและการโดปแล้ว แทบไม่มีอะไรในนี้ที่เป็นไปตามสัญชาตญาณเลย ถ้าไม่ได้เห็นแผนผังวงจรของได เส้นทางเดินสาย และ path ต่าง ๆ ก็แทบไม่มีเหตุผลที่จะคาดว่า A จะเร็วกว่า B เว้นแต่วิศวกรและ datasheet จะระบุไว้อย่างชัดเจน โดยเฉพาะใน ARM ผมยิ่งคิดว่าเป็นแบบนั้น
    • บทความของ Raymond Chen ยอดเยี่ยม และให้บริบทที่ดีในการตีความบทความนี้
      สิ่งที่บทความนี้เพิ่มเติมคือการแก้ง่าย ๆ โดยเปลี่ยน ret ให้เป็นคำสั่ง br อีกคำสั่งหนึ่ง ดังนั้นคู่คำสั่งจึงกลับมา “สมมาตร” อีกครั้ง และได้โค้ดที่เร็วขึ้นเล็กน้อยโดยไม่ทำให้ branch predictor พัง
    • Raymond Chen เป็นคนล้ำค่าจริง ๆ ผมขอบคุณที่ Microsoft ให้อิสระเขาในการเขียนบล็อกต่อไป และผมได้เรียนรู้จากที่นั่นเยอะมาก
    • ดูเหมือนว่าจะไม่เป็นจริงอีกต่อไปใน โปรเซสเซอร์ x86 รุ่นใหม่ ๆ: https://news.ycombinator.com/item?id=40767676

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

    • แม้แต่งานง่าย ๆ อย่างการบวกรายการตัวเลข ก็มี อัลกอริทึมการหาผลรวม หลายแบบอย่างคาดไม่ถึง
      วิธีแบบซื่อ ๆ ที่บวกทีละตัวในลูปนั้น obvious แต่มีวิธีที่ซับซ้อนกว่าซึ่งให้ขอบเขตที่ดีกว่าสำหรับผลรวมของความคลาดเคลื่อนสะสม และ Kahan summation เป็นตัวอย่างที่รู้จักกันดี: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      ถ้าเป็นข้อมูลแบบสตรีมมิง คุณอาจทำได้แค่บวกทีละตัว แต่ถ้าใช้บัฟเฟอร์ขนาดคงที่ N ชุดได้ ก็จะเกิดประเด็นว่าเมื่อมีตัวเลขใหม่เข้ามา จะเลือก subset ใดมาทำ partial sum จะนำไปบวกกับผลรวมสะสมอย่างไร และตัวเลือกนั้นมีการปรับปรุงความคลาดเคลื่อนที่พิสูจน์ได้หรือไม่
    • หาก ความต่างของขนาด ของค่าเลขทศนิยมมาก จะกลายเป็นปัญหาร้ายแรง
      ตัวอย่างเช่น ถ้าคำนวณ [1e50, -1e50, 1e3, 1e3] เป็น (((1e50 + -1e50) + 1e3) + 1e3) จะได้ 2e3 แต่ถ้าคำนวณเป็น ((1e50 + 1e3) + (-1e50 + 1e3)) จะได้ 0
      กรณีคล้ายกันเกิดขึ้นเมื่อบวกค่าขนาดเล็กจำนวนมากเข้ากับค่าขนาดใหญ่หนึ่งค่า โดย (((1e3 + 1e3) + 1e3) ... + 1e50) กับ (((1e50 + 1e3) + 1e3) ... + 1e3) ต่างกันพอสมควร
    • มีคำว่า “ควรจะ” เยอะมาก แต่ในความเป็นจริงแทบไม่เป็นแบบนั้นเลย ข้อมูลที่นิพจน์ดั้งเดิมให้มีเพียง ลำดับการคำนวณทางคณิตศาสตร์ เท่านั้น
      ถ้าผลลัพธ์ทางคณิตศาสตร์ไม่เสถียรระหว่างการ build แต่ละครั้ง มันจะกลายเป็นฝันร้ายโดยสิ้นเชิง เมื่อ build ซอฟต์แวร์ใหม่แล้วรันด้วย input เดิม ไม่ควรได้ผลลัพธ์ที่ต่างกัน
      ผมเคยเจอกรณีเฉพาะของ Intel เมื่อนานมาแล้วด้วย โดย FPU ใช้รีจิสเตอร์ 80 บิตภายใน แต่ใช้ 64 บิตในหน่วยความจำ ดังนั้นเมื่อจังหวะการเติม/ล้างรีจิสเตอร์เปลี่ยนไป จังหวะการปัดเศษก็เปลี่ยนและผลลัพธ์ก็เปลี่ยนด้วย สามารถตั้งค่าแฟล็ก FPU แบบ global ตอนเริ่มโปรแกรมเพื่อบังคับให้ปัดเศษทุกการดำเนินการได้
    • หากจัดเรียงค่าเลขทศนิยม ความคลาดเคลื่อนจะลดลง ดังนั้นผมคิดว่าการใช้ตัวสะสมหลายตัวอาจทำให้ความแม่นยำต่ำลงได้ ข้อมูลที่จัดเรียงแล้วก็ไม่ใช่เรื่องหายาก
      มีคำตอบที่ถูกต้องอยู่เสมอ และผมคิดว่า compiler ไม่ควรทำการเปลี่ยนแปลงที่ผิด อย่างน้อยก็ในค่าเริ่มต้น อย่างไรก็ดี วิธีให้โปรแกรมเมอร์แสดงเจตนาได้ชัดขึ้นย่อมเป็นสิ่งที่น่ายินดีเสมอ
    • โค้ดจำนวนมากพึ่งพาข้อเท็จจริงที่ว่า การคำนวณเลขทศนิยมเป็น deterministic ภายใน สถาปัตยกรรมชุดคำสั่ง หนึ่ง ๆ
      การใช้ SIMD กับลูปเลขทศนิยมอาจกลายเป็นค่าเริ่มต้นได้ แต่เพราะมันจะทำให้โค้ดเดิมจำนวนมากพัง และทำให้ output เปลี่ยนแบบไม่ deterministic บ่อยครั้ง จึงกลายเป็นฟีเจอร์ที่โปรแกรมเมอร์ต้องเลือกใช้อย่างชัดเจน
      ยิ่งไปกว่านั้น โปรแกรมเมอร์จำนวนมากอาจไม่รู้เรื่องนี้ ดังนั้นแม้ float Sum(float[] values) จะเริ่มคืนค่าที่ต่างออกไป ก็อาจไม่มีทางรู้ว่าสาเหตุคือการ vectorize นั่นเอง ด้วยเหตุนี้ เช่น ไลบรารีมาตรฐานของ .NET จึงใช้ SIMD กับ integers.Sum() แต่ไม่ใช้กับ floats.Sum()

  • แค่อ่านบรรทัดที่ว่า “หลังจากตรวจสอบการจบลูปแล้ว ก็ไหลเข้าไปในฟังก์ชัน foo โดยตรงโดยไม่มี branch” ก็คิดว่า “อ๋อ นั่นแหละปัญหา”
    ตอนแรกนึกว่าจะเป็นเรื่องเชิงลึกเกี่ยวกับ heuristic ของ branch predictor ที่หวือหวา แต่สุดท้ายกลับเป็นการละเมิด heuristic พื้นฐาน
    ไม่ควรคิดว่าจะได้ความเร็วเพิ่มขึ้นมหาศาลจากการใช้คำสั่ง call/ret ที่ไม่เข้าคู่กัน การที่ branch predictor รักษา shadow stack ของ return address นั้นเป็นวิธีที่มีมาหลายสิบปีแล้ว

    • การรู้ดีว่า branch predictor ทำงานอย่างไรเป็นเรื่องดี แต่คนจำนวนมากไม่ได้รู้ และสำหรับพวกเขามันอาจเป็นข้อมูลใหม่และอาจมีประโยชน์ก็ได้ แค่บทความนี้ไม่ได้เขียนมาเพื่อคุณเท่านั้นเอง และนั่นก็ไม่เป็นไร
    • ในระบบที่มี shadow call stack ระดับสถาปัตยกรรม เป็นฟีเจอร์ด้านความปลอดภัย มันอาจทำให้การรันโปรแกรมพังในระดับพื้นฐานกว่าเดิม กล่าวคือทำให้แครชได้
    • อีกด้านหนึ่ง เป้าหมายการออกแบบของ RISC คือเพิ่มประสิทธิภาพของโค้ดที่คอมไพล์แล้ว โดยแลกกับองค์ประกอบอื่น ๆ ส่วนใหญ่
      ดังนั้นความเสี่ยงแบบนี้ควรถูกบันทึกไว้ในเอกสาร แต่ผู้ออกแบบก็ควรสมมติได้ว่าคนที่เขียน assembly เองได้อ่านเอกสารแล้ว
      อีกด้านหนึ่ง Sophie Wilson เคยเขียนการใช้งาน BBC BASIC สำหรับ ARM รุ่นแรก แต่ตอนนั้นยังไม่มี branch predictor แม้จะเป็น 32 บิตและกฎจะแตกต่างกัน แต่ก็ชวนสงสัยว่าเมื่อสมมติฐานเชิงสถาปัตยกรรมเปลี่ยนไป AArch64 ทำให้โค้ดช้าลงอย่างไร
    • ถึงอย่างนั้น บทความก็ยังมีประโยชน์ เพราะแสดงให้เห็นจริง ๆ ว่าทำ optimization แบบนี้และแบบอื่น ๆ ได้อย่างไร

  • เป็นการอ้างอิง SNL คลาสสิก “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • ถ้า happy fun branch predictor เริ่มมีควันออกมา ควรอพยพทันที
    • พอเห็นประโยคว่า “Happy Fun Ball ถูกส่งไปให้ทหารของเราในซาอุดีอาระเบีย และยังถูกทิ้งจากเครื่องบินรบเหนืออิรักด้วย” ก็ให้ความรู้สึกว่า “นี่มันปีอะไรกันแน่!?”
    • ยังถูกกฎหมายอยู่ใน 16 รัฐ: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • อย่าพลาดประเด็นว่านี่เป็นบทความปี 2023 ตอนนี้มันเริ่มเก่าไปนิดแล้ว และตั้งแต่ Rust 1.78 เป็นต้นมา คอมไพเลอร์ใช้การคลี่ลูปที่ aggressive กว่าเดิมและมี SIMD เล็กน้อย: https://godbolt.org/z/zhbobW7rr
    บทความต้นฉบับบอกว่า “ดู assembly แล้วเห็นว่ามีการคลี่ลูป” พร้อมลิงก์ https://godbolt.org/z/Kv77abW6c ซึ่งใช้ “Rust Nightly” ที่เปลี่ยนแปลงอยู่ตลอด ตอนนี้มีการคลี่ลูปมากขึ้นแล้ว
    การคลี่ลูปเริ่มตั้งแต่ Rust 1.59: https://godbolt.org/z/5PTnWrWf7
    จากโค้ดบน GitHub ใช้ Rust 1.67.0-nightly เวอร์ชัน 2022-11-27

    • อัปเดตลิงก์ให้เลือก Rust 1.67 อย่างชัดเจนแล้ว
    • Rust 1.67.0 ที่ดูเหมือนบทความต้นฉบับจะเห็น ให้ผลลัพธ์แบบนี้: https://godbolt.org/z/4Y61d9seh
      ผมลองรัน benchmark เองบนฮาร์ดแวร์เดียวกันด้วย nightly Rust 1.81 ล่าสุดที่คลี่ลูปแบบ aggressive แต่ก็ไม่ต่างกัน และเร็วเท่าเดิมกับเมื่อ 1.5 ปีก่อน

  • เป็นบทความปี 2023 การสนทนาในตอนนั้น: https://news.ycombinator.com/item?id=34520498

    • ขยายความคือเป็นการสนทนาเมื่อมกราคม 2023 ของ “Do not taunt happy fun branch predictor” และมีคอมเมนต์ 171 รายการ: https://news.ycombinator.com/item?id=34520498
      การถูกโพสต์ซ้ำหลังผ่านไปประมาณหนึ่งปีก็ไม่เป็นไร และลิงก์เธรดเก่าไว้สำหรับผู้อ่านที่อยากรู้เพิ่มเติม

  • ผมไม่ได้คุ้นกับ assembly ของ ARM/ARM64 มากนัก เลยสับสนว่า x0 เพิ่มค่าได้อย่างไร
    const float f = *data++; กลายเป็น ldr s1, [x0], #4 ซึ่งดูเหมือนว่าคำสั่งนี้จะอ่านค่าไปพร้อมกับเพิ่ม x0 ขึ้น 4
    น่าจะใช้ค่าติดลบได้ด้วย จึงน่าจะวนย้อนกลับได้ด้วย เจ๋งทีเดียว ดูเหมือนว่า x86_64 จะไม่มีคำสั่งเดี่ยวที่อ่านและเพิ่มค่าไปพร้อมกัน

    • lods และ stos ทำการอ่าน/เขียนพร้อมเพิ่มค่าให้ rsi หรือ rdi ตามลำดับ และยังมี movs ที่คัดลอกระหว่างที่อยู่หน่วยความจำสองแห่งพร้อมเพิ่มค่าไปด้วย
      ปกติมักใช้ร่วมกับ rep เพื่อทำซ้ำ rcx ครั้ง เช่น memset ขนาด 10 ไบต์อาจเขียนเป็น mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb ได้
      ถ้าใช้ suffix w, d, q จะเดินหน้า 2, 4, 8 ไบต์ตามลำดับ

  • บทความดี แต่เสียดายที่สลับใช้หน่วย µs กับ ns ไปมาตลอด ทำให้กวาดตาดูตารางเพื่อเปรียบเทียบได้ยาก

    • การที่กลางบทความเปลี่ยนจาก C ไปเป็น Rust ก็ทำให้งงเล็กน้อยเหมือนกัน

  • น่าแปลกใจที่ไม่ได้ลองวิธีที่ฉลาดน้อยกว่านี้ก่อนจะ optimize โค้ด
    ถ้าเขียน assembly ใหม่ จะต้องมี branch แค่ตัวเดียวที่ท้ายลูป และสำหรับ X1 ก็สามารถจัดการด้วย ALU operation ครั้งเดียว แทนที่จะแยกการลบเพื่อเปรียบเทียบกับการลดค่าออกจากกัน
    ถ้าไปต่ออีก ก็ inline foo ไปเลย และตัดคำสั่ง RET ออกได้โดยไม่ต้องใช้ทริก BL/RET ที่ไม่เข้าคู่กัน ผมไม่ได้ benchmark เอง จึงไม่รู้ว่าจริง ๆ จะเร็วขึ้นแค่ไหน

    • มีพิมพ์ผิด บรรทัดที่เขียนว่า cbnz ควรเป็น cbz CBZ จะ branch ไปยัง label ถ้ารีจิสเตอร์เป็น 0 ส่วน CBNZ จะ branch ถ้าไม่เป็น 0