लॉक्स बनाम तुलना-और-स्वैप

Question

मैं लॉक-फ्री तकनीकों के बारे में पढ़ रहा हूं, जैसे तुलना-और-स्वैप और लॉकिंग के बिना थ्रेड सिंक्रनाइज़ेशन प्राप्त करने के लिए इंटरलाक्ड और स्पिनवाइट कक्षाओं का लाभ उठाना।

मैंने अपने स्वयं के कुछ परीक्षण चलाए हैं, जहां मेरे पास बस एक स्ट्रिंग में एक चरित्र को जोड़ने की कोशिश कर रहे कई धागे हैं। मैंने नियमित lock एस और तुलना-और-स्वैप का उपयोग करने का प्रयास किया। आश्चर्य की बात है (कम से कम मेरे लिए), ताले सीएएस का उपयोग करने से बेहतर परिणाम दिखाते हैं।

यहां मेरे कोड का सीएएस संस्करण है (this पर आधारित)।

private string _str = ""; 
    public void Append(char value) 
    { 
     var spin = new SpinWait(); 
     while (true) 
     { 
      var original = Interlocked.CompareExchange(ref _str, null, null); 

      var newString = original + value;     
      if (Interlocked.CompareExchange(ref _str, newString, original) == original) 
       break; 
      spin.SpinOnce(); 
     } 
    } 

और सरल (और अधिक कुशल) ताला संस्करण:

private object lk = new object(); 
    public void AppendLock(char value) 
    { 
     lock (lk) 
     { 
      _str += value; 
     } 
    } 

तो मैं 50.000 वर्णों को जोड़ने का प्रयास करते हैं, कैस संस्करण 1.2 सेकंड लेता है यह एक copy-> संशोधित> स्वैप पद्धति का अनुसरण और लॉक संस्करण 700ms (औसत)। 100k वर्णों के लिए, क्रमश: 7 सेकंड और 3.8 सेकंड लेते हैं। यह क्वाड-कोर (i5 2500k) पर चलाया गया था।

मुझे संदेह है कि क्यों सीएएस इन परिणामों को प्रदर्शित कर रहा था क्योंकि यह आखिरी "स्वैप" कदम को विफल कर रहा था। मैं सही था। जब मैं 50k वर्ण (50k सफल स्वैप) जोड़ने का प्रयास करता हूं, तो मैं 70k (सर्वोत्तम केस परिदृश्य) और लगभग 200k (सबसे खराब केस परिदृश्य) विफल प्रयासों के बीच गिनने में सक्षम था। सबसे खराब स्थिति परिदृश्य, हर 5 प्रयासों में से 4 विफल रहा।

तो मेरी प्रश्न हैं:

1. मैं क्या याद आ रही है? सीएएस बेहतर परिणाम नहीं देना चाहिए? लाभ कहां है?
2. सीएएस एक बेहतर विकल्प क्यों और कब है? (मुझे पता है कि यह पूछा गया है, लेकिन मुझे कोई संतोषजनक उत्तर नहीं मिल रहा है जो मेरे विशिष्ट परिदृश्य को भी समझाता है)।

यह मेरी समझ है कि रोजगार समाधान कैस है, हालांकि कोड के लिए कड़ी मेहनत, ज्यादा बेहतर पैमाने पर और विवाद बढ़ने के साथ ताले की तुलना में बेहतर प्रदर्शन करते हैं। मेरे उदाहरण में, ऑपरेशन बहुत छोटे और लगातार होते हैं, जिसका अर्थ है उच्च विवाद और उच्च आवृत्ति। तो मेरे परीक्षण अन्यथा क्यों दिखाते हैं?

मुझे लगता है कि लंबे परिचालन मामले को और भी बदतर बना देंगे -> "स्वैप" असफल दर और भी बढ़ेगी।

पुनश्च:

Stopwatch watch = Stopwatch.StartNew(); 
var cl = new Class1(); 
Parallel.For(0, 50000, i => cl.Append('a')); 

var time = watch.Elapsed; 
Debug.WriteLine(time.TotalMilliseconds); 

Answer 1

समस्या पाश पर असफलता की दर और तथ्य यह है कि तार अपरिवर्तनीय हैं का एक संयोजन है: इस कोड मैं परीक्षण चलाने के लिए प्रयोग किया जाता है। मैंने निम्नलिखित पैरामीटर का उपयोग करके अपने आप पर कुछ परीक्षण किए।

• रण 8 अलग-अलग धागे (मेरे पास 8 कोर मशीन है)।
• प्रत्येक धागा Append 10,000 बार कहा जाता है।

मैंने जो देखा वह था कि स्ट्रिंग की अंतिम लंबाई 80,000 (8 x 10,000) थी जो कि सही थी। मेरे लिए औसत 300,000 औसत प्रयासों की संख्या। तो यह ~ 73% की विफलता दर है। सीपीयू समय के केवल 27% के परिणामस्वरूप उपयोगी काम हुआ। अब क्योंकि स्ट्रिंग्स अपरिवर्तनीय हैं जिसका मतलब है कि स्ट्रिंग का एक नया उदाहरण ढेर और मूल सामग्री पर बनाया गया है और इसमें एक अतिरिक्त चरित्र की प्रतिलिपि बनाई गई है।वैसे, यह प्रतिलिपि ऑपरेशन ओ (एन) है इसलिए स्ट्रिंग की लंबाई बढ़ने के साथ यह लंबा और लंबा हो जाता है। कॉपी ऑपरेशन की वजह से मेरी परिकल्पना यह थी कि स्ट्रिंग की लंबाई बढ़ने के साथ विफलता दर में वृद्धि होगी। इसका कारण यह है कि कॉपी ऑपरेशन में अधिक से अधिक समय लगता है, टकराव की उच्च संभावना होती है क्योंकि थ्रेड आईसीएक्स को अंतिम रूप देने के लिए प्रतिस्पर्धा करने में अधिक समय व्यतीत करते हैं। मेरे परीक्षणों ने इसकी पुष्टि की। आपको खुद को एक ही परीक्षण का प्रयास करना चाहिए।

यहां सबसे बड़ी समस्या यह है कि अनुक्रमिक स्ट्रिंग concatenations खुद को समांतरता के लिए बहुत अच्छी तरह से उधार नहीं देते हैं। चूंकि ऑपरेशन एक्स _n एक्स _{एन -पर निर्भर करता है, इसलिए यह पूर्ण लॉक लेने के लिए तेज़ होगा, खासकर अगर इसका मतलब है कि आप सभी विफलताओं और रिट्री से बचें। एक निराशावादी रणनीति इस मामले में एक आशावादी के खिलाफ लड़ाई जीतती है। कम तकनीक बेहतर काम करती है जब आप समस्या को स्वतंत्र चक्स में विभाजित कर सकते हैं जो वास्तव में समानांतर में बिना किसी रन में चलाया जा सकता है।}

एक पक्ष नोट के रूप में Interlocked.CompareExchange का उपयोग _str के प्रारंभिक पढ़ने के लिए अनावश्यक है। इसका कारण यह है कि इस मामले में पढ़ने के लिए एक स्मृति बाधा की आवश्यकता नहीं है। ऐसा इसलिए है क्योंकि Interlocked.CompareExchange कॉल जो वास्तव में काम करता है (आपके कोड में दूसरा वाला) एक पूर्ण बाधा उत्पन्न करेगा। तो सबसे खराब मामला यह है कि पहला पठन "पुराना" है, आईसीएक्स ऑपरेशन परीक्षण में विफल रहता है, और लूप फिर से प्रयास करने के लिए चारों ओर स्पिन करता है। इस बार, हालांकि, पिछले आईसीएक्स ने एक "ताजा" पढ़ाया।

निम्न कोड यह है कि मैं कम लॉक तंत्र का उपयोग करके एक जटिल संचालन को कैसे सामान्यीकृत करता हूं। वास्तव में, नीचे दिया गया कोड आपको ऑपरेशन का प्रतिनिधित्व करने वाले प्रतिनिधि को पास करने की अनुमति देता है, इसलिए यह बहुत सामान्यीकृत है। क्या आप इसे उत्पादन में उपयोग करना चाहते हैं? शायद इसलिए नहीं क्योंकि प्रतिनिधि का आह्वान धीमा है, लेकिन कम से कम आपको यह विचार मिलता है। आप ऑपरेशन को हमेशा कठिन कोड बना सकते हैं।

public static class InterlockedEx 
{ 
    public static T Change<T>(ref T destination, Func<T, T> operation) where T : class 
    { 
    T original, value; 
    do 
    { 
     original = destination; 
     value = operation(original); 
    } 
    while (Interlocked.CompareExchange(ref destination, value, original) != original); 
    return original; 
    } 
} 

---

मैं वास्तव में मामले नापसंद "बासी" और "ताजा" जब स्मृति बाधाओं पर चर्चा, क्योंकि वह नहीं है कि वे क्या बारे में वास्तव में कर रहे हैं। वास्तविक गारंटी के विपरीत यह एक दुष्प्रभाव का अधिक है। लेकिन, इस मामले में यह मेरे बिंदु को बेहतर दिखाता है।