Happy Fun branch predictor का मज़ाक मत उड़ाइए (2023)

(mattkeeter.com)

1 पॉइंट द्वारा GN⁺ 2024-07-05 | 1 टिप्पणियां | WhatsApp पर शेयर करें

AArch64 assembly में loop की एक branch कम करने की कोशिश वाली optimization उल्टा 4 गुना धीमी हो गई, और वजह यह थी कि bl/ret call-return pair को असममित तरीके से इस्तेमाल करने से branch predictor भ्रमित हो गया
मूल code में हर loop पर bl foo और b loop दो branch होती हैं, लेकिन बदले हुए code में एक बार bl loop से x30 को स्थिर कर दिया जाता है और कई ret को उसी address पर लौटने दिया जाता है, ताकि branch की संख्या घटाई जा सके
M1 Max पर 1024 float array को जोड़ने के परिणाम में, सामान्य bl/ret code 969ns था, लेकिन एक bl और कई ret वाला ढांचा 3.85µs तक धीमा हो गया; ret को br x30 में बदलने पर यह 913ns तक लौट आया
Instruments performance counters ने दिखाया कि 1 अरब elements के sum में असममित bl/ret संरचना में return branch prediction failure लगभग 93% तक पहुँची, और FETCH_RESTART, MAP_DISPATCH_BUBBLE, MAP_REWIND भी बहुत बढ़ गए
इससे भी तेज implementation foo inline करने, Rust iter().sum(), NEON SIMD और manual loop unrolling तक पहुँचा, और अंतिम SIMD version 94ns तक घट गया, लेकिन floating-point addition का क्रम बदलने से result अलग हो सकता है

AArch64 loop में उल्टा असर

उदाहरण function float array को traverse करता है, हर value को foo में देता है, और foo accumulated value g को update करता है
सरल AArch64 रूपांतरण में यह flow होता है
- loop की शुरुआत में n == 0 है या नहीं, यह जाँचा जाता है
- ldr s1, [x0], #4 से value पढ़ी जाती है
- bl foo से subroutine को call किया जाता है
- foo का ret, bl के बाद वाली अगली instruction पर लौटता है
- b loop से फिर loop की शुरुआत पर जाया जाता है
foo parent function के साथ वही stack frame और registers इस्तेमाल करने वाले naked function जैसे रूप के करीब है, और s1 पढ़कर s0 में accumulation करता है

`bl` और `ret` की भूमिका

bl एक branch and link instruction है, जो दिए गए label पर jump करते हुए अगली instruction का address link register lr या x30 में store करता है
ret link register में मौजूद address पर jump करता है
मूल संरचना में bl foo और ret एक-दूसरे के अनुरूप हैं, और ret हमेशा उसी bl के बाद वाली instruction पर लौटता है

असफल “एक branch कम करो” optimization

बदली हुई संरचना foo को बदले बिना loop के अंदर एक branch कम करना चाहती है
- function की शुरुआत में bl loop call करके x30 में loop की शुरुआत का address डाला जाता है
- loop exit condition जाँचने के बाद अलग branch के बिना foo code में गिरा जाता है
- foo का ret, x30 में मौजूद loop पर लौटता है
इस संरचना में loop body के भीतर x30 बदलता नहीं, इसलिए बार-बार होने वाले ret हमेशा उसी address पर लौटते हैं
सरल foo इस तरह एक पंक्ति का code है, जो float जोड़ता है

foo:
    fadd s0, s0, s1
    ret

इस स्थिति में पूरा function input float array का sum निकालता है

benchmark परिणाम और branch prediction समस्या

criterion से M1 Max CPU पर 1024 elements वाले array का benchmark किया गया
- सामान्य bl/ret: 969ns
- एक bl, कई ret: 3.85µs
एक branch कम करने वाला code, दो branch इस्तेमाल करने वाले मूल code से लगभग 4 गुना धीमा निकला
Cliff और Dan का मानना था कि bl/ret pair के मेल न खाने से branch predictor भ्रमित हो गया
ARM documentation के अनुसार RET processor को function return पहचानने देता है, जिससे branch prediction अधिक सटीक हो सकती है
- BR LR भी functional रूप से वही काम कर सकता है
- लेकिन RET एक अलग instruction है, जिसे processor function return के रूप में पहचान सकता है
- यदि branch prediction सही हो, तो pipeline में सही instructions पहुँचती हैं और memory से instructions का इंतज़ार करने का समय बचता है

return address stack और `br x30` प्रयोग

branch predictor आंतरिक रूप से function return address stack बनाए रखता होगा
- bl चलने पर return address stack में push होता है
- ret दिखने पर यह मान लिया जाता है कि control सबसे हाल के bl के return address पर जाएगा
- उसी address के आधार पर prefetch और speculative execution शुरू होती है, फिर stack से pop किया जाता है
यह तरीका तब अच्छा काम करता है जब bl/ret सही जोड़ी में हों
जब कई ret बार-बार एक ही address का उपयोग करते हैं, तो prediction fail हो सकती है, बेकार prefetch हो सकती है, गलत speculative execution हो सकती है, और pipeline stall या flush हो सकता है
Dan के सुझाव पर ret को br x30 में बदलने से performance गिरावट गायब हो गई
- सामान्य bl/ret: 969ns
- एक bl, कई ret: 3.85µs
- एक bl, कई br x30: 913ns
br x30 version हर loop में सिर्फ एक branch करता है, इसलिए यह मूल code से थोड़ा तेज है

Instruments performance counters

Instruments से पहले दो programs के performance counters देखे गए
माप 1 अरब elements वाले array का sum निकालते समय किया गया
असममित bl/ret में return branch prediction failure लगभग 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 ने इन counters को पूरी तरह document नहीं किया है
दूसरे counters को खराब branch prediction के downstream effects के रूप में माना गया
- FETCH_RESTART: संभवतः गलत prefetch
- MAP_DISPATCH_BUBBLE: संभवतः pipeline stall से संबंधित
- MAP_REWIND: संभवतः गलत speculative execution जिसे rewind करना पड़ा

और तेज कैसे बनाया जाए

उदाहरण एक educational code है, और foo के subroutine होने की वजह भी “अधिकतम तेज code” के बजाय समझाने वाली संरचना के करीब है
अगर foo की content build time पर पता हो और jump distance की सीमा के भीतर हो, तो bl और ret को पूरी तरह हटाकर inline किया जा सकता है
- 969ns से 911ns तक, लगभग 6% तेज
Rust में सिर्फ f.iter().sum() लिखने से यह 833ns तक आ जाता है

pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

generated assembly loop unrolling करती है
-C target-cpu=native के साथ compile करने पर भी NEON SIMD instructions generate नहीं होतीं

SIMD और manual loop unrolling

manual AArch64 SIMD implementation तीन loop से बनी है
- loop: जब तक बाकी values की संख्या 4 के multiple न हो जाए, अलग-अलग values को s0 में जोड़ा जाता है
- simd: एक बार में 4 values को vector register v1 में जोड़ा जाता है, और यह तब तक दोहरता है जब तक बाकी values की संख्या 8 के multiple न हो जाए
- simd2: simd को 2 गुना unroll करके हर iteration में 8 values process की जाती हैं और v1 तथा v2 में accumulate किया जाता है
function के अंत में v1 और v2 की values को s0 में जोड़कर return किया जाता है
type punning में float* वाले x0 को double* की तरह लेकर 128-bit, यानी 4 float, को d3 और d4 में पढ़ा जाता है
- mov v3.d[1], v4.d[0] से d4 के 64-bit को v3 के ऊपरी 64-bit में ले जाया जाता है
- fadd v1.4s, v1.4s, v3.4s में .4s suffix के कारण इसे चार float की तरह treat किया जाता है
यह SIMD implementation 94ns में चलती है, जो पिछले सर्वश्रेष्ठ Rust version 833ns से लगभग 8.8 गुना तेज है

कुल performance सारांश और सावधानियाँ

implementation	समय
सामान्य `bl`/`ret`	969ns
एक `bl`, कई `ret`	3.85µs
एक `bl`, कई `br x30`	913ns
`b` इस्तेमाल करने वाला साधारण loop	911ns
Rust में rewrite	833ns
SIMD + manual loop unrolling	94ns

SIMD code floating-point addition का क्रम बदल देता है
floating-point addition associative नहीं होती, इसलिए SIMD version straight-line code जैसा ठीक वही result नहीं दे सकता
संभव है कि compiler ने sum के लिए SIMD instructions इसलिए generate नहीं की हों
सारा code GitHub पर सार्वजनिक है
ARM64 machine पर cargo bench चलाकर benchmark को reproduce किया जा सकता है

1 टिप्पणियां

GN⁺ 2024-07-05

Hacker News की रायें

आखिरी optimized code 32-bit floating-point के 1024 elements वाले array का sum 94ns में पूरा कर देता है
उन 94ns के दौरान पुराना दोस्त 1MHz 6502 तो शायद program के पहले instruction का पहला byte fetch करने के लिए memory chip को signal भेजे या नहीं, यही सोचना शुरू कर रहा होता
हालांकि यह code पूरी तरह इस premise पर निर्भर है कि वह cache के अंदर execute हो रहा है। नहीं तो लेख में आया ताकतवर M1 Max भी पहले memory fetch का इंतजार करते हुए रुका होता। DRAM धीमा है
- अब यह हमारा सौभाग्य है कि पूरी L1 cache size उतनी बड़ी हो गई है जितनी 6502 कुल memory address कर सकता था। हम सचमुच अद्भुत दौर में जी रहे हैं
Raymond Chen ने करीब 20 साल पहले यही बात कवर की थी: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...
- Intel के x86/64 architecture instruction reference की printed book, यानी मोटी नीली किताब, मेरे पास है, और datasheets व documents ध्यान से पढ़ने वाले व्यक्ति के तौर पर जब भी सुनता हूं कि “intuition से X लगेगा, लेकिन Y होता है”, तो हमेशा सतर्क हो जाता हूं
  silicon की semiconductor प्रकृति और doping की बुनियादी समझ को छोड़ दें, तो इसमें intuitive बहुत कम है। अगर आपने die circuit diagram और wiring, paths नहीं देखे हैं, तो जब तक engineers और datasheets स्पष्ट रूप से न कहें, A के B से तेज होने की उम्मीद करने की बहुत कम वजह है। खासकर ARM में तो मुझे ऐसा और भी लगता है
- Raymond Chen का लेख शानदार है, और इस लेख को समझने के लिए अच्छा context देता है
  इस बार के लेख ने जो जोड़ा है, वह ret को एक और br instruction से बदलने वाला साधारण correction है। इसलिए pair फिर से “symmetric” हो जाता है, और branch predictor को बिगाड़े बिना थोड़ा तेज code मिल सकता है
- Raymond Chen सचमुच खजाने जैसे इंसान हैं। Microsoft उन्हें blog लिखते रहने की छूट देता है, इसके लिए आभारी हूं, और वहां से मैंने सचमुच बहुत कुछ सीखा है
- हाल के x86 processors में लगता है यह अब सच नहीं है: https://news.ycombinator.com/item?id=40767676
बेशक कुछ भी संभव है, और array sum निकालने वाला सामान्य loop सच में computer को elements एक-एक करके accumulate करने का निर्देश देने के रूप में होता है
लेकिन, उदाहरण के लिए, SIMD से चार accumulators parallel में बनाकर आखिर में जोड़ना, elements को एक-एक करके जोड़ने से ज्यादा गलत है—ऐसा कहना कठिन है
floating-point summation को मूल रूप से error bounds वाला मानना चाहिए, और उस range के भीतर का answer valid होना चाहिए। अगर input floating-point के बारे में कुछ खास पता है, तो language को वह intention explicitly express करने का तरीका देना चाहिए। सबसे basic loop ही default है, इसलिए default तौर पर best performance देना बेहतर लगता है
- numbers की list जोड़ने जैसे simple काम में भी हैरानी की बात है कि कई summation algorithms हैं
  loop में एक-एक करके जोड़ने का naive तरीका obvious है, लेकिन accumulated error के total पर बेहतर bounds देने वाली ज्यादा sophisticated methods भी हैं, और Kahan summation एक जाना-पहचाना example है: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
  streaming data हो तो शायद एक-एक करके जोड़ने के अलावा कुछ न कर सकें, लेकिन fixed-size buffer के N slots इस्तेमाल कर सकते हों, तो नए number के आने पर किस subset को partial sum बनाया जाए, उसे accumulated sum में कैसे जोड़ा जाए, और क्या उस choice से provable error improvement मिलता है—ऐसे सवाल उठते हैं
- floating-point values की magnitude difference बड़ी हो तो यह गंभीर समस्या बन जाती है
  उदाहरण के लिए [1e50, -1e50, 1e3, 1e3] को (((1e50 + -1e50) + 1e3) + 1e3) की तरह calculate करें तो 2e3 आता है, लेकिन ((1e50 + 1e3) + (-1e50 + 1e3)) की तरह calculate करें तो 0 आता है
  छोटे values को किसी एक बहुत बड़े value में बहुत बार जोड़ने पर भी ऐसा ही है, इसलिए (((1e3 + 1e3) + 1e3) ... + 1e50) और (((1e50 + 1e3) + 1e3) ... + 1e3) काफी अलग हैं
- “ऐसा होना चाहिए” बहुत है, लेकिन व्यवहार में लगभग कभी ऐसा नहीं होता। original expression जो information देता है, वह सिर्फ arithmetic operation order है
  अगर builds के बीच arithmetic results stable न हों, तो यह पूरा nightmare बन जाता है। same input के साथ software को फिर से build करके run करने पर अलग result नहीं आना चाहिए
  बहुत पहले Intel-specific case भी झेला था: FPU internally 80-bit registers इस्तेमाल करता था और memory में 64-bit, इसलिए registers fill/empty होने का timing बदलता तो rounding का timing भी बदलता और result भी बदल जाता। program start पर global FPU flag set करके हर operation पर rounding force की जा सकती है
- floating-point values को sort करने से error घटता है। इसलिए कई accumulators इस्तेमाल करने से accuracy कम हो सकती है, ऐसा मुझे लगता है। sorted data भी uncommon नहीं है
  हमेशा सही answer मौजूद होता है, और compiler को कम से कम default में गलत change नहीं करना चाहिए, ऐसा मैं सोचता हूं। हालांकि programmer को अपना intention और साफ तौर पर express करने का तरीका मिलना हमेशा welcome है
- बहुत सा code किसी खास instruction set architecture के भीतर floating-point operations deterministic होने पर निर्भर करता है
  floating-point loop पर SIMD लगाना default बन सकता था, लेकिन यह बहुत सारे existing code को तोड़ देता और output अक्सर non-deterministically बदल जाता, इसलिए यह ऐसी feature बन गई जिसे programmer को explicitly चुनना पड़ता है
  ऊपर से कई programmers को यह बात पता नहीं हो सकती, इसलिए अगर float Sum(float[] values) अलग value return करना शुरू करे, तो उन्हें यह जानने का तरीका नहीं होगा कि वजह vectorization है। इसलिए, उदाहरण के लिए, .NET standard library integers.Sum() में SIMD इस्तेमाल करती है, लेकिन floats.Sum() में नहीं
सिर्फ “लूप खत्म होने की जांच करने के बाद, बिना किसी branch के सीधे foo function के अंदर गिर जाता है” वाली लाइन पढ़कर ही लगा, “अच्छा, यही समस्या है।”
लगा था कि यह चमकदार branch predictor heuristics पर कोई गहरी चर्चा होगी, लेकिन आखिर में यह basic heuristic का उल्लंघन ही निकला।
यह नहीं सोचना चाहिए कि mismatched call/ret instructions इस्तेमाल करके जबरदस्त speedup मिल सकता है। branch predictor द्वारा return address का shadow stack बनाए रखना दशकों से चली आ रही तकनीक है
- branch predictor कैसे काम करता है, यह जानना अच्छी बात है, लेकिन बहुत लोगों को यह नहीं पता होता; उनके लिए यह नई और शायद उपयोगी जानकारी हो सकती है। बस यह लेख आपके लिए नहीं था, और यह भी ठीक है
- जिन systems में security feature के रूप में architecture-level shadow call stack होता है, वहाँ यह program execution को और मूल रूप से बिगाड़ सकता है, यानी crash करा सकता है
- एक तरफ, RISC का design goal बाकी अधिकतर चीज़ों की कीमत पर compiled code की performance बढ़ाना है
  इसलिए ऐसे risks document किए जाने चाहिए, लेकिन designer यह मानकर चल सकते हैं कि हाथ से assembly लिखने वाला व्यक्ति documentation पढ़ चुका है
  दूसरी तरफ, Sophie Wilson ने मूल रूप से ARM के लिए BBC BASIC implementation लिखा था, लेकिन उस समय branch predictor नहीं था। भले ही 32-bit होने से rules अलग हों, यह जानना दिलचस्प है कि architectural assumptions बदलने पर AArch64 code को कैसे धीमा बनाता है
- फिर भी, लेख उपयोगी है क्योंकि इसमें यह भी दिखाया गया कि असल में इस optimization और अन्य optimizations को कैसे हासिल किया गया
यह classic SNL reference “Do not taunt happy fun ball” है: https://www.youtube.com/watch?v=GmqeZl8OI2M
- अगर happy fun branch predictor से धुआँ निकलना शुरू हो जाए, तो तुरंत बाहर निकल जाना चाहिए
- “Happy Fun Ball सऊदी अरब में हमारे सैनिकों को भेजा गया है, और इराक के ऊपर लड़ाकू विमानों से भी गिराया जा रहा है” वाली line देखकर “अरे, अभी आखिर कौन-सा साल चल रहा है!?” जैसा एहसास होता है
- यह अभी भी 16 राज्यों में legal है: https://www.youtube.com/watch?v=2AzAFqrxfeY
यह नहीं भूलना चाहिए कि यह 2023 का लेख है। अब यह थोड़ा पुराना हो चुका है, और Rust 1.78 से compiler ज्यादा aggressive loop unrolling और थोड़ा SIMD इस्तेमाल करता है: https://godbolt.org/z/zhbobW7rr
मूल लेख में कहा गया था “assembly देखने पर loop unrolling हो रही है” और https://godbolt.org/z/Kv77abW6c link किया था, लेकिन वह लगातार बदलने वाला “Rust Nightly” इस्तेमाल कर रहा था। अब loop unrolling और ज्यादा हो गई है
loop unrolling Rust 1.59 से शुरू हुई थी: https://godbolt.org/z/5PTnWrWf7
GitHub code के हिसाब से Rust 1.67.0-nightly, 2022-11-27 version इस्तेमाल किया जा रहा था
- link को Rust 1.67 explicit रूप से चुनने के लिए update किया गया
- मूल लेख ने शायद जो Rust 1.67.0 देखा था, वह ऐसा result देता है: https://godbolt.org/z/4Y61d9seh
  उसी hardware पर latest nightly Rust 1.81 की aggressive loop unrolling के साथ खुद benchmark चलाया, लेकिन कोई फर्क नहीं था; speed 1.5 साल पहले जैसी ही थी
यह 2023 का लेख है। उस समय की discussion: https://news.ycombinator.com/item?id=34520498
- विस्तार से कहें तो यह “Do not taunt happy fun branch predictor” पर जनवरी 2023 की discussion थी, और इसमें 171 comments थे: https://news.ycombinator.com/item?id=34520498
  करीब 1 साल बाद repost होना ठीक है, और पुरानी thread का link उन readers के लिए है जो और जानना चाहते हैं
ARM/ARM64 assembly से बहुत परिचित नहीं था, इसलिए x0 कैसे increment होता है, इस पर confusion हुआ
const float f = *data++; ldr s1, [x0], #4 बनता है, और यह instruction value पढ़ते हुए साथ-साथ x0 को 4 से increment करता दिखता है
negative value भी इस्तेमाल की जा सकती है, इसलिए reverse traversal भी संभव लगता है। काफी अच्छा है। x86_64 में read और increment को एक साथ करने वाला single instruction शायद नहीं है
- lods और stos क्रमशः rsi या rdi पर read/write और increment को साथ करते हैं। दो memory addresses के बीच copy करते हुए increment करने वाला movs भी है
  आम तौर पर इसे rep के साथ इस्तेमाल किया जाता है, जो rcx बार repeat करता है। उदाहरण के लिए 10-byte memset mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb के रूप में किया जा सकता है
  w, d, q suffix लगाने पर यह क्रमशः 2, 4, 8 bytes आगे बढ़ता है
लेख अच्छा था, लेकिन tables देखते समय comparison मुश्किल हो गया क्योंकि µs और ns units के बीच बार-बार switch किया गया
- लेख के बीच में C से Rust पर switch होना भी थोड़ा confusing था
code optimize करने से पहले कम smart तरीका न आजमाया जाना हैरान करता है
assembly को दोबारा लिखने पर loop के bottom में केवल एक branch की जरूरत होगी, और X1 के लिए भी comparison subtraction और decrement अलग-अलग करने के बजाय एक ही ALU operation से निपटाया जा सकता है
आगे बढ़ें तो foo को बस inline किया जा सकता है, और mismatched BL/RET trick के बिना RET instruction भी हटाया जा सकता है। खुद benchmark नहीं किया है, इसलिए असल में कितना तेज होगा, पता नहीं
- एक typo है। जहाँ cbnz लिखा है, वह cbz होना चाहिए। CBZ register 0 होने पर label पर branch करता है, और CBNZ 0 न होने पर branch करता है

Happy Fun branch predictor का मज़ाक मत उड़ाइए (2023)

AArch64 loop में उल्टा असर

bl और ret की भूमिका

असफल “एक branch कम करो” optimization

benchmark परिणाम और branch prediction समस्या

return address stack और br x30 प्रयोग

Instruments performance counters

और तेज कैसे बनाया जाए

SIMD और manual loop unrolling

कुल performance सारांश और सावधानियाँ

संबंधित पढ़ाई

1 टिप्पणियां

Hacker News की रायें

`bl` और `ret` की भूमिका

return address stack और `br x30` प्रयोग