Tree Borrows: Rust unsafe कोड के aliasing नियमों का मॉडल
(plf.inf.ethz.ch)- Rust compiler pointer aliasing guarantees का उपयोग optimization के लिए कर सके, इसके लिए यह स्पष्ट रूप से परिभाषित होना चाहिए कि unsafe कोड कहाँ नियम तोड़ता है
- मौजूदा Stacked Borrows ने इसका एक मानदंड दिया, लेकिन यह वास्तविक unsafe Rust कोड के आम patterns और borrow checker की नई सुविधाओं को पर्याप्त रूप से स्वीकार नहीं कर पाया
- Tree Borrows, Stacked Borrows की मुख्य संरचना को stack से tree में बदलकर अधिक वैध patterns को व्यक्त करने योग्य बनाता है
- सबसे अधिक इस्तेमाल होने वाले 30,000 Rust crates के मूल्यांकन में, इसने Stacked Borrows की तुलना में अस्वीकृत test cases 54% कम किए
- Rocq proof के जरिए यह पुष्टि हुई कि मौजूदा optimization का अधिकांश भाग बरकरार रखा जा सकता है, और read-read reordering जैसे नए optimization भी संभव हैं
unsafe Rust में आवश्यक aliasing नियम
- Rust ownership-आधारित type system के जरिए memory safety और data race prevention जैसी मजबूत guarantees देता है
- लेकिन unsafe कोड में safety अपने-आप सुनिश्चित नहीं होती, और ऐसे में programmer के लिए अलग नियमों का पालन करना जरूरी होता है
- Compiler, type system की guarantees—खासकर pointer aliasing से जुड़ी जानकारी—का उपयोग करके function के अंदर optimization को और मजबूत करना चाहता है
- गलत तरीके से लिखा गया unsafe कोड ऐसे optimization को तोड़ सकता है, इसलिए किस कोड को “badly behaved” माना जाए इसका स्पष्ट मानदंड महत्वपूर्ण है
- पहले के शोध Stacked Borrows ने यह मानदंड परिभाषित किया था, लेकिन इसकी सीमाएँ हैं
- यह वास्तविक unsafe Rust कोड में आम कई patterns को अस्वीकार करता है
- यह हाल में जोड़ी गई Rust borrow checker की उन्नत सुविधाओं को प्रतिबिंबित नहीं करता
Tree Borrows का दृष्टिकोण और मूल्यांकन परिणाम
- Tree Borrows को Stacked Borrows की केंद्रीय stack संरचना को tree से बदलकर परिभाषित किया गया है
- इस संरचनात्मक बदलाव से पुराने मॉडल की सीमाएँ कम होती हैं
- सबसे अधिक इस्तेमाल होने वाले 30,000 Rust crates के मूल्यांकन में Stacked Borrows की तुलना में अस्वीकृत test cases 54% कम हुए
- Rocq proof के जरिए optimization से जुड़ी विशेषताओं की भी पुष्टि हुई
- Stacked Borrows जिन optimization की अनुमति देता था, उनमें से अधिकांश को यह बनाए रखता है
- महत्वपूर्ण नए optimization read-read reorderings को भी यह संभव बनाता है
- Tree Borrows को PLDI'25 Distinguished Paper Award मिला है
- संबंधित सामग्री
1 टिप्पणियां
Hacker News टिप्पणियाँ
बोनस के तौर पर, Ralf Jung समूह की हाल की एक प्रस्तुति भी है, जिसमें Rust dialect में Rust की execution semantics को executable रूप में सटीक रूप से specified करने की कोशिश की गई है: https://youtube.com/watch?v=yoeuW_dSe0o
Torvalds लंबे समय से कहते आए हैं कि C के strict aliasing rules से फ़ायदे से ज़्यादा नुकसान होता है, और यह काफ़ी convincing लगता है। उदाहरण यहाँ है: https://lore.kernel.org/all/CAHk-=wgq1DvgNVoodk7JKc6BuU1m9Un... अगर इस विषय में रुचि हो तो पूरा thread भी पढ़ने लायक है
सीमित अनुभव के आधार पर, Rust मूल रूप से अलग है ऐसा नहीं लगता। कम से कम जहाँ unsafe शामिल हो, वहाँ तो बिल्कुल नहीं
मेरे हिसाब से वे compiler के लिए ज़्यादा उपयोगी हैं और programmer पर कम बोझ डालते हैं। साथ ही, language के भीतर इससे बाहर निकलने का रास्ता भी वास्तव में है: raw pointers का इस्तेमाल करें। और code को जाँचने के tools भी मौजूद हैं
अंततः, language design की हर चीज़ की तरह यह भी एक trade-off है, और Rust ने शायद ऐसे optimizations के लिए कोई नया sweet spot ढूँढ लिया है। यह सही है या नहीं, यह समय बताएगा
C में
restrictजैसा एक nuclear option है, और मेरे अनुभव में clang और gcc में इसका कुछ असर तभी दिखा जब इसे function arguments पर लगाया गया। Type-based alias analysis को सामान्य रूप से इस्तेमाल करना मुश्किल है, औरint64_ttype की अनंत copies बनाना न संभव है, न शायद कोई ऐसा करना चाहेगा। दूसरे type के रूप में reinterpret करने के लिएmemcpyको मजबूर किया जाना भी परेशान करने वाला हैदूसरी ओर, Rust references को lifetime, scope, और mutability के हिसाब से बारीकी से सीमित किया जाता है, और “physical” type ख़ुद उतना महत्वपूर्ण नहीं होता। इसलिए उसी memory को
&mut i32/&i32और&mut i64/&i64के रूप में reinterpret करके switch करना भी संभव है। जब तक unsafe abstraction एक ही समय पर overlap करने वाले&mutreferences न दे, या एक&mutको कई non-overlapping&mutमें बाँटे, तब तक सामान्य safe Rust reads/writes से half values या कई values को पढ़ना-लिखना संभव हैआजकल अच्छी performance पाने में alias analysis बहुत महत्वपूर्ण है। लेकिन यह भी याद रखना चाहिए कि सबसे बड़ा लाभ अक्सर सबसे सरल heuristics से आता है। उदाहरण के लिए, अगर दो loads pointers के रूप में एक ही SSA value का उपयोग करते हैं, तो वे अनिवार्य रूप से एक-दूसरे के alias हैं
LLVM के नज़रिए से, BasicAA यही काम करता है। यह लगभग simple heuristics का एक सेट है: “अगर object के allocation point को track किया जा सकता है, तो alias query को निर्णायक रूप से हल करो, वरना पता नहीं”
असली सवाल है कि basic और obvious checks से आगे बढ़ने वाली alias analysis की क्या कीमत है। जब alias queries इतनी trivial न रहें, तब उनके नतीजों से आम तौर पर किया भी बहुत कम जा सकता है, और अधिकतर केवल code motion hazards ही मिलते हैं। उससे लाभ काफ़ी कम होता है
जिन experiments को मैं देखना चाहूँगा, उनमें से एक यह है कि सैद्धांतिक रूप से perfect alias analysis कुल कितना speedup देगी। मेरा अंदाज़ा है कि Linux kernel जैसे non-HPC code में भी यह लगभग 20% होगा
[1] इसमें data layout transformation जैसे heroic optimizations शामिल नहीं हैं, जिन्हें high-quality alias analysis के बिना आज़माया ही नहीं जाएगा। चूँकि हमें पहले से पता है कि ऐसी alias analysis वास्तव में मौजूद नहीं है, इसलिए ऐसे optimizations की कोशिश भी नहीं की जाएगी, और उन्हें अपेक्षित speedup में शामिल करना भी उचित नहीं लगता
C में aliasing केवल types पर आधारित है, इसलिए इसका दूसरा नाम type-based alias analysis या TBAA है
मुझे यह दावा मिला कि
noaliasexecution time के हिसाब से लगभग 5% performance improvement देता है, लेकिन यह साफ़ है कि यह सामग्री काफ़ी पुरानी हैhttps://github.com/rust-lang/rust/issues/54878#issuecomment-...
https://news.ycombinator.com/item?id=22281205
https://news.ycombinator.com/item?id=17715399
&mutसे*mut i32बनाया जाए, औरwrite(x)की जगह*x = 10किया जाए, तो क्योंकि implicit two-phase borrow इस्तेमाल नहीं होता, compiler को इसे reject करना चाहिए—ऐसा वर्णन से लगा, लेकिन वास्तव में यह pass हो जाता है*x = 10;वाले version में error report होती है, जबकिwrite(x);वाले version में नहींerror कुछ इस तरह है: “Undefined Behavior: attempting a write access using [...] but that tag does not exist in the borrow stack for this location”
rustc के पास अपने-आप में इन दोनों में से किसी को भी reject करने का कोई कारण नहीं है।
yएक*mutहै, और compile-time type system के नज़रिये से इसकाxवाले&mutके साथ कोई borrow या lifetime संबंध नहीं हैमौजूदा borrow checker अधिक restrictive analysis इस्तेमाल करता है, इसलिए वह raw pointer और mutable reference के बीच इस खास टकराव को detect नहीं कर पाता
व्यावहारिक अनुभव में [1] [2] पर भी इसने ऐसे reasonable code को अनुमति दी, जो Stacked Borrows में illegal था
[1] https://github.com/Voultapher/sort-research-rs/blob/main/wri... Miri column
[2] https://github.com/rust-lang/rust/blob/6b3ae3f6e45a33c2d95fa...
यह scope-based borrow checker से non-lexical lifetime borrow checker पर आ चुका है, और अगला experimental Polonius implementation भी एक option के रूप में मौजूद है। लेकिन जब नया implementation production-ready हो जाता है, तो पुराना implementation हटा दिया जाता है। क्योंकि उसे चुनने की कोई वजह नहीं रहती
borrow checking तेज़ है, और नया implementation सख़्ती से अधिक सही programs को accept करता है
साथ ही
RcऔरRefCelltypes भी हैं, जिनसे runtime checking की लागत देकर अधिक flexibility पाई जा सकती हैimplementation, performance, और developer experience के लिहाज़ से इन सबकी लागत और क्षमता अलग-अलग है
और Rust के बाहर ज़्यादातर systems का वास्तविक लक्ष्य automatic resource management की productivity है। तरीका कोई भी हो, automatic resource management का उपयोग किया जाता है, और performance-critical paths पर ही ऊपर के type systems में से किसी एक को जोड़ा जाता है
इस संदर्भ में “Rust” को सिर्फ़ “वे invariants जो लोग आम तौर पर चाहते हैं” और “उन सामान्य invariants को मानकर, न उससे ज़्यादा न कम, की गई optimizations का एक set” माना जा सकता है
compile time का ज़्यादातर हिस्सा trait resolution, monomorphization, LLVM optimization passes, और linking में जाता है
शायद यह बेवकूफ़ी भरा सवाल हो, लेकिन क्या कई implementations को parallel threads में चलाकर, जो पहले positive result दे वह जीत जाए, ऐसा नहीं किया जा सकता?
pointers का इस्तेमाल करके एक ही variable के लिए कई mutable references को एक साथ मौजूद रखना undefined behavior है। अगर मैंने पेपर का इरादा गलत नहीं समझा, तो यही बात लगती है
ऊपर वाला code Rust compiler accept कर लेता है, लेकिन यह rules तोड़ता है। सवाल यह है कि कौन-से rules तोड़ता है
मूल रूप से borrow checker जो accept करता है वह legal है; unsafe ऐसा code भी व्यक्त कर सकता है जो illegal हो या undefined behavior हो; और rules का एक ऐसा set भी मौजूद है जो borrow checker की जाँच-क्षमता से व्यापक है, लेकिन फिर भी legal और well-defined behavior है
इस research का लक्ष्य उसी ruleset को सटीक रूप से specify करना है। मोटे तौर पर यह “writable pointers alias नहीं होने चाहिए” के करीब है, लेकिन internal pointers, iterator invalidation, और बुरा pointer बनाना समस्या है या उसका इस्तेमाल करना, जैसे details बहुत कठिन हैं
पहले का Stacked Borrows पेपर अधिक simple था, लेकिन अधिक restrictive भी, इसलिए वास्तविक unsafe code अक्सर उसके rules से बाहर रह जाता था। Tree Borrows अधिक व्यापक है, अधिक code को अनुमति देता है, और फिर भी साबित करने योग्य रूप से safe है
Tree Borrows ठीक ऐसी ही definition प्रस्तावित करता है
यहाँ “code ऐसा कर सकता है” का मतलब है “आप यह code लिख, compile, और run कर सकते हैं, और Tree Borrows जैसी किसी चीज़ के बिना यह दावा करने का आधार नहीं है कि इस code में समस्या है”
आप यह बात पहले ही मान चुके हैं कि ऐसे code को undefined behavior कहा जाना चाहिए—यानी Tree Borrows जैसी किसी चीज़ की ज़रूरत है। पेपर का यह हिस्सा इसी बात की दलील देता है कि ऐसी चीज़ की ज़रूरत क्यों है
https://play.rust-lang.org/?version=stable&mode=debug&editio...
बात यह है कि Rust compiler developers aliasing optimizations को support करना चाहते हैं, इसलिए ऊपर जैसे counterexamples को विचार के दायरे से “बाहर” करने का कोई तरीका चाहिए
unsafeका उद्देश्य उन मामलों के लिए है जहाँ Rust की lifetime analysis से कोड की वैधता साबित करना मुश्किल होता है, लेकिन इसका दुरुपयोग इससे कहीं ज़्यादा काम करने के लिए किया जा सकता है