उद्देश्य-सी: ब्लॉक और एनएसईएन्यूमरेशन के साथ समस्याएंकंक्रंट

Question

मेरे पास एक शब्दकोश है जिसमें 1000 प्रविष्टियां हैं। प्रविष्टियां प्रकार कुंजी = key XXX के सभी एनएसएसटींग हैं, और मूल्य = element XXX जहां XXX 0 के बीच एक संख्या है - तत्वों की संख्या - 1. (कई दिन पहले, मैंने एक शब्दकोश युक्त उद्देश्य-सी शब्दकोशों के बारे में पूछा था। कृपया refer to that question आप उस कोड को चाहते हैं जो शब्दकोश बनाता है।)

उप शब्दकोश में सभी तारों की कुल लंबाई 28,670 वर्ण है। अर्थात्:

strlen("key 0")+strlen("element 0")+ 
//and so on up through 
strlen("key 999")+strlen("element 999") == 28670. 

इस एक संकेतक के रूप एक बहुत ही सरल हैश मान यदि एक विधि एक बार और केवल एक बार हर कुंजी + मान युग्म प्रगणित गया है पर विचार करें। अगर मैं (एक बहु प्रोसेसर मशीन पर) समवर्ती ब्लॉकों एक ही उपयोग करने का प्रयास

NSUInteger KVC_access3(NSMutableDictionary *dict){ 
    __block NSUInteger ll=0; 
    NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

    [subDict 
     enumerateKeysAndObjectsUsingBlock: 
      ^(id key, id object, BOOL *stop) { 
       ll+=[object length]; 
       ll+=[key length]; 
    }]; 
    return ll; 
} 
// will correctly return the expected length... 

, मैं एक मिल:

मैं एक सबरूटीन कि पूरी तरह से काम करता है (ब्लॉकों का उपयोग कर) अलग-अलग शब्दकोश कुंजी और मान का उपयोग करना संख्या करीब नहीं बल्कि वास्तव में उम्मीद 28670:

NSUInteger KVC_access4(NSMutableDictionary *dict){ 
    __block NSUInteger ll=0; 
    NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

    [subDict 
     enumerateKeysAndObjectsWithOptions: 
      NSEnumerationConcurrent 
     usingBlock: 
      ^(id key, id object, BOOL *stop) { 
       ll+=[object length]; 
       ll+=[key length]; 
    }]; 
    return ll; 
} 
// will return correct value sometimes; a shortfall value most of the time... 

NSEnumerationConcurrent राज्य के लिए एप्पल डॉक्स:

"the code of the Block must be safe against concurrent invocation." 

मुझे लगता है कि शायद यह मुद्दा है, लेकिन मेरे कोड या ब्लॉक के साथ समस्या क्या है KVC_access4 जो समवर्ती आमंत्रण के लिए सुरक्षित नहीं है?

संपादित & निष्कर्ष

बी.जे. होमर के excellent solution के लिए धन्यवाद, मैं NSEnumerationConcurrent काम कर गया। मैंने दोनों विधियों को बड़े पैमाने पर समय दिया। मेरे पास KVC_access3 में जो कोड है, वह छोटे और मध्यम आकार के शब्दकोशों के लिए तेज़ और आसान है। बहुत सारे शब्दकोशों पर यह बहुत तेज है। हालांकि, अगर आप तो इस कोड को एक मोंगो बड़ा शब्दकोश (दस लाख या कुंजी/मान जोड़े करोड़ों) है:

[subDict 
    enumerateKeysAndObjectsWithOptions: 
     NSEnumerationConcurrent 
    usingBlock: 
     ^(id key, id object, BOOL *stop) { 
     NSUInteger workingLength = [object length]; 
     workingLength += [key length]; 

     OSAtomicAdd64Barrier(workingLength, &ll); 
}]; 

तेजी 4x तक है। आकार के लिए पारदर्शी बिंदु मेरे परीक्षण तत्वों में से 100,000 का लगभग 1 शब्दकोश है। सेट-अप समय के कारण अधिक शब्दकोश और वह क्रॉसओवर पॉइंट संभवतः अधिक है।

Answer 1

समवर्ती गणना के साथ, आपके पास एकाधिक धागे पर एक साथ चलने वाला ब्लॉक होगा। इसका मतलब है कि एक ही समय में एकाधिक धागे ll तक पहुंच रहे हैं। चूंकि आपके पास सिंक्रनाइज़ेशन नहीं है, इसलिए आप दौड़ की स्थिति के लिए प्रवण हैं।

यह एक समस्या है क्योंकि += ऑपरेशन एक परमाणु संचालन नहीं है। याद रखें, ll += xll = ll + x जैसा ही है। इसमें ll पढ़ने, x को उस मान में जोड़ने और फिर ll में नया मान वापस संग्रहीत करना शामिल है। उस समय के बीच ll थ्रेड एक्स पर पढ़ा जाता है और जब इसे संग्रहीत किया जाता है, तो थ्रेड एक्स इसकी गणना को संग्रहीत करने के लिए वापस आने पर अन्य धागे के कारण होने वाले किसी भी परिवर्तन को खो दिया जाएगा।

आपको सिंक्रनाइज़ेशन जोड़ने की आवश्यकता है जैसे कि एकाधिक थ्रेड एक ही समय में मान को संशोधित नहीं कर सकते हैं।

__block NSUInteger ll=0; 
NSMutableDictionary *subDict=[dict objectForKey:@"dict_key"]; 

[subDict 
    enumerateKeysAndObjectsWithOptions:NSEnumerationConcurrent 
    usingBlock: 
     ^(id key, id object, BOOL *stop) { 
      @synchronized(subDict) { // <-- Only one thread can be in this block at a time. 
       ll+=[object length]; 
       ll+=[key length]; 
      } 
}]; 
return ll; 

बहरहाल, यह सभी लाभ आप, समवर्ती गणन से प्राप्त के बाद से ब्लॉक के पूरे शरीर को अब एक तुल्यकालन ब्लॉक में प्रभाव, केवल एक ही इस ब्लॉक के कहने में संलग्न है को छोड़ देता है: अनुभवहीन समाधान यह है वास्तव में एक समय में चल रहा होगा।

तो संगामिति वास्तव में एक महत्वपूर्ण प्रदर्शन आवश्यकता यहाँ है, मेरा सुझाव था निम्नलिखित: एक काफी कम स्तर समारोह है कि एक को बढ़ाने के लिए गारंटी है जो

__block uint64 ll = 0; // Note the change in type here; it needs to be a 64-bit type. 

^(id key, id object, BOOL *stop) { 
    NSUInteger workingLength = [object length]; 
    workingLength += [key length]; 

    OSAtomicAdd64Barrier(workingLength, &ll); 
} 

ध्यान दें कि मैं OSAtomicAdd64Barrier उपयोग कर रहा हूँ, परमाणु मूल्य। आप पहुंच को नियंत्रित करने के लिए @synchronized का भी उपयोग कर सकते हैं, लेकिन यदि यह ऑपरेशन वास्तव में एक महत्वपूर्ण प्रदर्शन बाधा है, तो संभवतः आप कुछ स्पष्टता की लागत पर भी सबसे अधिक प्रदर्शन विकल्प चाहते हैं। यदि यह ओवरकिल की तरह लगता है, तो मुझे संदेह है कि समवर्ती गणना सक्षम करने से वास्तव में आपके प्रदर्शन को प्रभावित नहीं किया जा रहा है।