AMD64 पर 16 बाइट से बड़े struct पास न करें

• Neat की related_post_gen benchmark ranking में बढ़त किसी high-level optimization से नहीं, बल्कि array को 24-byte struct की जगह 3 pointer arguments के रूप में पास करने वाले एक छोटे ABI बदलाव से आई
• Reference counter की वजह से Neat array को start और end pointers के अलावा array object base pointer चाहिए होता है, इसलिए D array के 16 bytes के उलट यह SystemV AMD64 ABI के memory-passing path पर चला जाता है
• 16 bytes से बड़े कुछ aggregates call के समय value को stack पर copy करने के बाद pointer से पास किए जाते हैं, जिससे register passing का फायदा खत्म हो जाता है और stack shuffle की लागत बढ़ जाती है
• Example benchmark में struct Vector { double x, y, z; } को struct के रूप में पास करने पर 1 billion runs में 12.3 seconds लगे, जबकि fields को अलग-अलग arguments के रूप में पास करने पर यह घटकर 5.3 seconds हो गया
• C API को C ABI का पालन करना ही पड़ता है, लेकिन language runtime के अंदर arrays, tuples, sumtype जैसे types जब 16 bytes से बड़े हों, तो field-splitting passing benchmark करने लायक है

---

Neat में सामने आया bottleneck

• Neat related_post_gen benchmark में ranking में कई पायदान ऊपर गया
• Performance improvement किसी नए high-level optimization pass से नहीं, बल्कि array passing का तरीका बदलने से आया
  • पहले: 3 pointers वाला struct argument
  • बदलाव के बाद: 3 pointers को अलग-अलग arguments के रूप में पास करना
• D की तुलना में Neat उम्मीद से धीमा था, और profiler में function call के लिए stack का बड़ा हिस्सा move करने वाली activity दिखी
• Bottleneck calculation से ज्यादा call के समय होने वाली stack rearrangement cost जैसा था

Neat array 24 bytes का क्यों होता है

• D array के उलट Neat reference counter का इस्तेमाल करता है
• Neat array में ये 3 pointers शामिल होते हैं
  • Start pointer
  • End pointer
  • वह array object base pointer जिसमें reference count stored होता है
• 3 pointers 24 bytes होते हैं, इसलिए AMD64 argument passing rules में यह 2 pointers वाले 16-byte array से अलग path लेता है
• D array तेज और Neat array धीमा होने की वजह यह थी कि 24 bytes होने पर यह 16-byte boundary पार कर गया

SystemV AMD64 ABI की 16-byte boundary

• SystemV AMD64 ABI specification कहता है कि अगर किसी aggregate का size दो eightbytes से ज्यादा हो जाए, तो पूरे argument को memory के जरिए पास किया जाता है
• Struct को memory के जरिए पास करने के लिए caller side पर ये काम करने पड़ते हैं
  • Stack पर struct size जितनी जगह allocate करना
  • उस जगह को पास की जाने वाली value से भरना
  • Function को उस struct location का pointer पास करना
• इस case में value का stack पर होना जरूरी है, इसलिए LLVM के optimization की गुंजाइश कम हो जाती है
• Value को registers से stack पर copy करना पड़ता है, और यह भी track करना पड़ता है कि stack का कौन-सा हिस्सा use में है और कौन-सा हिस्सा reuse किया जा सकता है
• इस stack reuse tracking में LLVM का behavior अच्छा नहीं दिखा

3 double vector benchmark

• Benchmark में struct Vector { TYPE x, y, z; }; form का 3-field vector इस्तेमाल हुआ
• TYPE को double के रूप में define किया गया
• दोनों functions वही addition करते हैं, लेकिन argument passing का तरीका अलग है
  • vector_add_struct(struct Vector left, struct Vector right) बड़े struct को argument के रूप में लेता है
  • vector_add_fields(...) left_x, left_y, left_z, right_x, right_y, right_z को अलग-अलग arguments के रूप में लेता है
• mode और run length command-line arguments से लिए गए, ताकि optimizer पूरी calculation को constant folding न कर सके
• impl.c को inlining से बचाने के लिए अलग से compile किया गया

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Result struct passing में 12.3 seconds, और fields को अलग-अलग पास करने में 5.3 seconds रहा

Assembly में दिखने वाला अंतर

• Struct passing version कई instructions stack shuffle में इस्तेमाल करता है
• Field version को यह फायदा है कि parameters function में आते समय पहले से ही SSE registers में होते हैं
• Struct passing version को हर बार stack से values load करनी पड़ती हैं
• SystemV ABI का मकसद values को यथासंभव registers से पास करना है, लेकिन इस case में 16 bytes से बड़े struct की वजह से वह फायदा गायब हो जाता है
• AMD64 पर उपलब्ध registers की संख्या देखते हुए, 16 bytes से बड़े types के लिए भी value passing उपयोगी होती, ऐसा माना गया

cdecl जैसी स्थिति

• Fields को stack पर लिखकर pointer पास करने का तरीका आखिरकार पुराने x86 cdecl ABI जैसा हो जाता है, जिसमें सब कुछ stack से पास किया जाता था
• cdecl को slow माना जाता था, और इसे तेज बनाने के लिए कई calling conventions बने
• समस्या यह है कि struct size की वजह से AMD64 System V ABI इस case में पुराने stack-passing तरीके की तरह behave करता है

Inlining और LTO के exceptions

• Real code में ऐसे functions सभी inline हो सकते हैं
• gcc में LTO enable करने पर दोनों versions के बीच performance difference खत्म हो जाता है
• clang में वही result नहीं आता
• सभी functions inline हो सकते हैं या inline होने चाहिए, ऐसा नहीं है

Language implementers और API optimization के लिए सलाह

• C API call करते समय C ABI का पालन करना होगा
• लेकिन non-C languages के अंदर high-level types backend को struct जैसे दिखें, तो भी उन्हें अनिवार्य रूप से एक ही struct के रूप में represent करना जरूरी नहीं है
• Language implementers खुद तय कर सकते हैं कि arrays, tuples, sumtype आदि को कैसे pass किया जाए
• Neat में 16 bytes से बड़े ऐसे types को अलग-अलग fields के रूप में पास करने का चुनाव किया गया, और benchmark में इसका फायदा दिखा
• AMD64 पर language implementation कर रहे हों या API को micro-optimize कर रहे हों, तो 16 bytes से बड़े structs को manually split करने से मदद मिलती है या नहीं, इसे benchmark करना जरूरी है
• खासकर inner loops में performance difference उम्मीद से बड़ा हो सकता है

जोड़: double struct और SSE

• सवाल यह है कि double specification के अनुसार SSE class में है, तो struct को SSE registers से pass क्यों नहीं किया जाता
• जवाब यह है कि कारण नहीं पता, लेकिन असल में ऐसा pass नहीं किया जाता

[GN⁺]

Hacker News की टिप्पणियां

• यहां समस्या SysV amd64 ABI है। भाषा के अंदरूनी ABI को SysV के तौर पर इस्तेमाल करना जरूरी नहीं है। अगर आप उसे SysV C caller के सामने expose नहीं कर रहे हैं, तो अपनी पसंद की calling convention इस्तेमाल कर सकते हैं
  https://llvm.org/docs/LangRef.html#calling-conventions
  जिन लोगों को जिज्ञासा हो, उनके लिए neatlang में संबंधित बदलाव यहां है: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  यह सिर्फ LLVM calling convention output बदलने से कहीं ज्यादा जटिल दिखता है। शायद लेखक इन types को C programs के सामने deterministic calling convention के साथ expose करना चाहते थे

  • दरअसल, पूरे ABI के बारे में भी यही कहा जा सकता है। अगर आप assembly programmer हैं तो जानते होंगे कि यह उन low-hanging fruits में से एक है जहां compiler को आसानी से मात दी जा सकती है
    conventions को आंख मूंदकर न मानें; किसी खास स्थिति में जो तरीका सबसे ज्यादा समझ में आए, वही चुनें
  • मेरे मन में सबसे पहले आया सवाल पहले ही जवाब पा चुका था। यह दिलचस्प है कि बहुत-सी चीजें बहुत पहले बनाए गए ABI जैसी चीजों का पालन करती हैं
    खासकर ABI अक्सर पुराने CPU के साथ compatibility की तरफ झुके होते हैं, और नए CPU में extended registers जैसी सुविधाओं का इस्तेमाल करके struct size घटाए बिना भी सुधार की गुंजाइश हो सकती है। किसी खास hardware या generation के लिए tune किया गया software कुछ machines पर unusable हो जाएगा, इसलिए यह बहुत आकर्षक नहीं होगा; लेकिन जब आप अपने system की hardware capabilities के हिसाब से code को बेहद optimize करना चाहें, तब ऐसा output दे सकने वाला compiler होना शानदार होगा

• argument passing cost अक्सर ठीक से समझी नहीं जाती, इसलिए ऐसे लेख देखकर अच्छा लगता है। Google जैसी जगहों पर भी 24-byte objects को value के रूप में pass करना आम है, और इसकी लागत सभी functions में इतनी व्यापक रूप से फैली होती है कि profiler में ठीक से नजर नहीं आती

  • value से pass करना और reference से pass करना असल में ABI/API को प्रभावित करता है, इसलिए यह काफी बड़ा cognitive burden बन जाता है। Zig इसे enforce नहीं करना चाहता, इसलिए “value से pass” करने पर भी compiler यह तय कर सकता है कि असल में उसे reference से pass किया जाए
    हालांकि ऐसी अड़चन भी सामने आती है: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Google जैसी जगहों” से आपका मतलब अपने अनुभव से है? एक ex-Googler के तौर पर मैं साफ कह सकता हूं कि non-primitive types को pointer या reference से pass करने की guideline है
    जो एकमात्र exception याद आती है वह string_view है
  • यह बात अच्छी तरह उठाई गई है कि calling convention में built-in जैसी, व्यापक रूप से फैली overhead को profiling से ढूंढना लगभग असंभव है
  • 24-byte object को pointer से pass करने में tradeoff यह है कि जब वास्तव में उस object को इस्तेमाल करना हो, तो pointer को dereference करना पड़ेगा। और इस बात की कोई guarantee नहीं कि वह object पास में ही होगा
    अगर किस्मत खराब हुई, तो cache miss हो सकता है और main memory से 24-byte object लाने में करीब 100 nanoseconds इंतजार करना पड़ सकता है। वही object direct pass किया जाए तो वह stack पर होगा, इसलिए cache में होने की संभावना ज्यादा है
  • जिज्ञासा है कि क्या C++ ABI भी हर call पर 24-byte object को stack पर spill करता है। std::string या std::function parameters के तेज होने की उम्मीद तो नहीं है, फिर भी यह चौंकाने वाला है

• x64 पर पहली बार जाते समय, मुझे graphics में vec3 object (3 floats) के sizeof()=12 के बजाय 16 bytes हो जाने की चिंता थी, इसलिए मैंने graphics engine पर बहुत benchmarks चलाए
  हैरानी की बात नहीं कि 8-byte read alignment की वजह से 16 bytes, 12 bytes से तेज निकला। अंदरूनी तौर पर भी और GPU पर भी। इसलिए vec3 चुपचाप vec4 बन गया, और अलग से vec4 अब भी मौजूद है। हमेशा की तरह, local benchmarks नहीं बल्कि पूरे परिप्रेक्ष्य वाले benchmarks करने चाहिए

  • इसका SSE size के साथ अच्छी तरह फिट होना एक बहुत अच्छा side effect है। इसलिए _mm_load_ps को सीधे इस्तेमाल किया जा सकता है, code ज्यादा साफ होता है और vectorization भी बेहद आसान हो जाती है
  • शायद यह बहुत ज्यादा तेज नहीं होगा। और यह CPU पर भी काफी निर्भर नहीं करता क्या, इस data के साथ आप क्या करते हैं उससे अलग?
    16 bytes होने पर कई accesses 3x4 bytes के बजाय aligned 2x8 bytes या 1x16 bytes हो सकते हैं, यह समझ आता है। लेकिन दूसरे accesses में ऐसा कम हो सकता है, और cache pressure बढ़ने की समस्या भी है
  • x64 ABI, x86 ABI से भी काफी बेहतर है

• common sense के हिसाब से, registers में pass की गई values speculative execution की वजह से पहले से load हो सकती हैं, इसलिए वे stack writes से तेज होती हैं, और stack manipulation heap allocation से तेज होता है
  इसलिए बहुत सारे global variables वाला गंदा spaghetti code बेहद तेज होता है, और elegant recursive functions या tuple/struct/list arguments अविश्वसनीय रूप से धीमे। पहले वाले को tight assembly loop में optimize करना कहीं ज्यादा आसान है

  • बेशक, यह मानना होगा कि वह spaghetti code elegant code जैसा ही algorithm implement करता है
    अगर elegant code O(n) है और spaghetti code O(n^2), तो आपको फर्क महसूस हो सकता है। maintainability पर भी विचार करना चाहिए। एक मायने में compilers हमारी elegant solutions को spaghetti code में बदलने के लिए ही मौजूद हैं
  • “parameters को stack नहीं, registers से pass करो” लगभग common sense है, लेकिन “16 bytes से बड़े parameters हमेशा stack से pass होते हैं” उतना स्पष्ट नहीं है
  • आजकल कुछ CPU memory renaming कर सकते हैं, इसलिए stack पर spill करने की cost सस्ती हो सकती है
    global objects compiler optimization में भी बाधा डालते हैं

• संदर्भ के लिए, MSVC में structs को stack पर pass किए जाने से पहले cutoff size 8 bytes है। यह ABI detail है, इसलिए portable code में इस पर निर्भर नहीं करना चाहिए
  लेकिन अगर function अक्सर call नहीं होता, तो बहुत stress लेने की जरूरत नहीं है। उदाहरण की तरह अगर यह अक्सर call होने वाला छोटा function है, तो LTO जैसे तरीकों से compiler को code inline करने दें। तब arguments को registers से pass करने की तुलना में कहीं ज्यादा उपयोगी optimizations खुल जाती हैं

• ऐसे लेखों को मैं “मुसीबत खड़ी करने लायक बस पर्याप्त ज्ञान” की श्रेणी में रखता हूँ। निर्देश के मुताबिक अलग से compile करके compiler को ABI से callable function बनाने के लिए मजबूर कर दें, तब भी LTO इस गलती को पलट सकता है
  अगर इस program को LTO के साथ build करें, तो यह बिना LTO वाले program के किसी भी mode की तुलना में दोनों modes में नाटकीय रूप से तेज हो जाता है। अगर program performance-sensitive है, तो profiling करें, bottleneck को चरम तक optimize करें, और उसके बाद ही struct को arguments में खोलकर पास करने जैसी चीज commit करनी चाहिए

  • सलाह अच्छी है, लेकिन मैंने अभी तक ऐसा compiler नहीं देखा जो इस तरह की चीज़ों को दिखा दे। पहले तो ये पूरे codebase में फैली होती हैं, और जब तक किस्मत से hotspot न बन जाएँ, मैंने ऐसा profiler भी नहीं देखा जो उनका असर दिखाए
    यह लगभग हर compiler-generated code पर लागू होता है। Valgrind माप सकता है, लेकिन sampling profiler शायद नहीं कर पाएगा, और बिखरी हुई code generation problem को highlight करने वाला कोई tool नहीं है
  • ऊपर से performance की पूर्ण अहमियत की बात करते हुए reference counting इस्तेमाल कर रहे हैं

• Windows के default cdecl calling convention में 8 bytes से बड़े struct registers के जरिए pass नहीं होते [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• amd64 पर SysV amd64 ABI इस्तेमाल करते हुए भी 16 bytes से बड़े struct को value के रूप में pass और return करना पूरी तरह संभव है। बस यह धीमा होता है
  फिर भी code को ज्यादा स्पष्ट बनाने के लिए अक्सर pass-by-value की कीमत वाजिब होती है। बेशक इस मामले में नहीं, लेकिन जैसा loeg ने बताया, अपनी भाषा के अंदर C++ compilers, Go, OCaml, SBCL की तरह custom ABI इस्तेमाल किया जा सकता है

• दिए गए example में caller को प्रभावित किए बिना parameter type को “struct Vector” से “const struct Vector &” में बदलकर pass by reference करने से इसे ठीक किया जा सकता है
  मैंने बहुत सारा C++ code देखा है जिसमें pointer bugs थे और जहाँ बिना वजह pointer इस्तेमाल किए गए थे, जबकि pass by reference काफी था और उसे ज्यादा आसान व सुरक्षित तरीके से इस्तेमाल किया जा सकता था

  • नहीं। दरअसल यहाँ की मुख्य समस्या यही है। ABI की वजह से compiler मूल रूप से ठीक वही काम करता है
    ABI कहता है कि value को pointer से pass करो, इसलिए pointer पाने के लिए उसे कहीं store करना पड़ता है, और वही होता है जो const-ref साफ तौर पर लिखने पर होता। struct value को अलग-अलग arguments में बदलने पर arguments को registers में pass किया जा सकता है
  • जब मैंने यह समस्या पकड़ी, तो code में byval के लिए pointer pass करने हेतु बीस-तीस alloca थे। हर function, call में pass होने वाले हर parameter के लिए अलग alloca से शुरू हो रहा था
    मैंने हमेशा कुछ हद तक मान लिया था कि LLVM ऐसी चीज़ों को अच्छी तरह साफ कर देगा, लेकिन पता चला कि ऐसा नहीं था
  • फिर भी struct pointer को callee को pass करने के लिए compiler को तीन registers को stack पर serialize करना पड़ेगा
    बताया गया फायदा registers से stack में serialization को पूरी तरह avoid करने का है, और pass by reference से यह avoid होता नहीं दिखता
  • यह C++ example नहीं बल्कि C99 example था। कई environments में न्यूनतम inertia के कारण tools को मनमर्जी से बदला नहीं जा सकता
    अगर C++ allow हो, तो copies घटाने के लिए move arguments जैसे और भी विकल्प मिल जाते हैं

• C++ में हमेशा सुना हुआ rule of thumb यह है कि primitive types के अलावा बाकी चीज़ों को value से pass करने की कोई अच्छी वजह न हो तो reference से pass करें, और सचमुच जरूरत हो तो pointer से pass करें
  इसकी वजह ABI भी है और copy constructor या move constructor से बचना भी। यह उबाऊ low-level detail है, लेकिन C++ में maximum performance चाहिए तो इसका ध्यान रखना पड़ता है। साफ कहूँ तो यह सिर्फ performance optimization है; struct-passing code ठीक से काम करता है, बस कम तेज होता है