खुशमिज़ाज, मज़ेदार branch predictor का मज़ाक न उड़ाएँ (2023)

खुशमिज़ाज branch predictor का मज़ाक न उड़ाएँ

• हाल ही में AArch64 assembly काफ़ी लिख रहा हूँ
• लूप में एक jump हटाने का एक "चतुर" आइडिया performance को घटा देता है
• इस गलती को समझाया गया है ताकि दूसरे लोग वही गलती न करें

कोड उदाहरण

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 assembly में अनुवाद

// 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

optimization की कोशिश

• bl instruction को कम करके performance बेहतर करना चाहा गया
• लेकिन performance उल्टा गिर गई

performance तुलना

• मूल कोड: 969 ns
• optimized कोड: 3.85 µs

कारण का विश्लेषण

• branch predictor bl और ret की जोड़ी मेल न खाने से उलझ जाता है
• ARM दस्तावेज़ के अनुसार, ret instruction function return का अनुमान लगाने में मदद करता है

समाधान

• ret की जगह br x30 का उपयोग
• performance की वापसी: 913 ns

अतिरिक्त optimization

• foo को inline करके performance बढ़ाई गई
• loop unrolling और SIMD instructions का उपयोग

अंतिम performance

• SIMD + manual loop unrolling: 94 ns

निष्कर्ष

• branch predictor को भ्रमित नहीं करना चाहिए
• SIMD कोड तेज़ है, लेकिन floating-point addition associative law का पालन नहीं करती, इसलिए परिणाम अलग हो सकते हैं

GN⁺ की राय

• यह लेख AArch64 assembly optimization के महत्व को अच्छी तरह दिखाता है
• performance optimization के लिए branch predictor के काम करने के सिद्धांत को समझना ज़रूरी है
• SIMD instructions का उपयोग करके optimization बहुत प्रभावी है, लेकिन accuracy की समस्या पर विचार करना चाहिए
• Rust जैसी high-level language का उपयोग करने पर compiler optimization के ज़रिए performance को आसानी से बेहतर किया जा सकता है
• समान प्रकृति वाले प्रोजेक्ट्स में Agner Fog की assembly optimization guide शामिल है

[GN⁺]

Hacker News राय

• Apple II दौर के दोस्तों के साथ मिलकर लेख का सार निकाला गया

  • optimized code को 1024 32-bit floating point numbers का योग करने में 94 nanoseconds लगते हैं
  • 1 MHz 6502 उन 94 nanoseconds के दौरान मेमोरी से पहले instruction का पहला byte लाने की कोशिश कर रहा होगा
  • यह code केवल cache में चलने पर optimized performance दिखाता है। DRAM धीमा है

• Raymond Chen ने लगभग 20 साल पहले इसी विषय को कवर किया था

  • loop के अंत की जांच करने के बाद branch के बिना foo function में चला जाता है
  • यह बुनियादी prediction heuristics का उल्लंघन था
  • branch predictor द्वारा return addresses की shadow stack बनाए रखना कई दशकों से मौजूद है

• SIMD code में floating point addition associative नहीं होती, इसलिए योग अलग क्रम में किया जा सकता है

  • शायद यही वजह है कि compiler SIMD instructions generate नहीं करता
  • floating point summation में स्वाभाविक रूप से error bounds होते हैं, और उस सीमा के भीतर कोई भी उत्तर वैध है
  • अगर special floating point inputs हों, तो language को उन्हें explicitly encode करने का साधन देना चाहिए

• Rust 1.78 के बाद compiler अधिक aggressive loop unrolling और थोड़ा SIMD इस्तेमाल करता है

  • loop unrolling की शुरुआत Rust 1.59 में हुई थी
  • Github code में Rust 1.67.0-nightly version इस्तेमाल हो रहा था

• ARM/ARM64 assembly में x0 कैसे बढ़ता है, इसे लेकर भ्रम था

  • ldr s1, [x0], #4 instruction load करते समय x0 को 4 से बढ़ा देता है
  • x86_64 में load और increment को एक साथ करने वाला एकल instruction नहीं है

• assembly code को optimize करने के लिए कम जटिल तरीका न आज़माना हैरानी की बात थी

  • assembly code को फिर से इस तरह लिखा जा सकता है कि loop के सबसे नीचे सिर्फ एक branch की जरूरत पड़े
  • foo को inline किया जा सकता है और RET instruction हटाया जा सकता है

• एक राय यह भी थी कि लेखक बार-बार units न बदलता तो बेहतर होता