memchr() हुड के नीचे कैसे काम करता है?

Question

पृष्ठभूमि: मैं कार्यक्षमता का एक शुद्ध डी भाषा कार्यान्वयन बनाने की कोशिश कर रहा हूं जो लगभग C's memchr के बराबर है लेकिन पॉइंटर्स के बजाय सरणी और सूचकांक का उपयोग करता है। कारण यह है कि std.string संकलन समय समारोह मूल्यांकन के साथ काम करेगा। आप में से अपरिचित डब्ल्यू/डी के लिए, कुछ प्रतिबंधों को पूरा होने पर संकलन समय पर कार्यों का मूल्यांकन किया जा सकता है। एक प्रतिबंध यह है कि वे पॉइंटर्स का उपयोग नहीं कर सकते हैं। दूसरा यह है कि वे सी कार्यों को कॉल नहीं कर सकते हैं या इनलाइन असेंबली भाषा का उपयोग नहीं कर सकते हैं। संकलन समय पर स्ट्रिंग लाइब्रेरी कार्य करने के बाद कुछ संकलन समय कोड जेन हैक के लिए उपयोगी है।

प्रश्न: मेमचर हुड के तहत काम करता है जितना तेज़ करता है? Win32 पर, कुछ भी जो मैं सरल लूप का उपयोग कर शुद्ध डी में बनाने में सक्षम हूं, कम से कम 2x धीमी है, यहां तक ​​कि w/स्पष्ट ऑप्टिमाइज़ेशन तकनीकों जैसे कि सीमा जांच, लूप अनोलिंग आदि अक्षम करना आदि। किस प्रकार की गैर-स्पष्ट चाल उपलब्ध हैं एक स्ट्रिंग में एक चरित्र खोजने के रूप में सरल कुछ?

Answer 1

मैं GNU libc के स्रोत पर एक नज़र डालने का सुझाव दूंगा। अधिकांश कार्यों के लिए, इसमें फंक्शन के सामान्य अनुकूलित सी संस्करण दोनों शामिल होंगे, और मशीन विशिष्ट चाल का लाभ उठाकर, जितना संभव हो उतने समर्थित आर्किटेक्चर के लिए अनुकूलित असेंबली भाषा संस्करण होंगे।

x86-64 SSE2 version जल्दी बाहर निकलने के pmovmskb/test/jcc की भूमि के ऊपर amortize करने के लिए एक पूरे एक बार (चार 16B वैक्टर) में डेटा का कैश-लाइन पर pcmpeqb से परिणाम को जोड़ती है,।

जीसीसी और क्लैंग वर्तमान में if() break प्रारंभिक निकास स्थितियों के साथ ऑटो-वेक्टरिंग लूपों में असमर्थ हैं, इसलिए वे स्पष्ट सी कार्यान्वयन से बेवकूफ बाइट-एट-ए-टाइम एएसएम बनाते हैं।

Answer 2

This implementation of memchr from newlib किसी का एक उदाहरण memchr के अनुकूलन है: इसे पढ़ने और एक समय में 4 बाइट का परीक्षण कर रहा है (अलग memchr से, newlib पुस्तकालय में अन्य कार्यों here हैं)।

संयोग से, एमएसवीसी रन-टाइम लाइब्रेरी के लिए स्रोत स्रोत अधिकांश एमएसवीसी स्थापना के वैकल्पिक भाग के रूप में उपलब्ध है (इसलिए, आप इसे देख सकते हैं)।

Answer 3

यहां memchr.c से फ्रीबीएसडी (बीएसडी-लाइसेंस प्राप्त) memchr() है। फ्रीबीएसडी का ऑनलाइन स्रोत कोड ब्राउज़र समय-परीक्षण, बीएसडी-लाइसेंसीकृत कोड उदाहरणों के लिए एक अच्छा संदर्भ है।

void * 
memchr(s, c, n) 
    const void *s; 
    unsigned char c; 
    size_t n; 
{ 
    if (n != 0) { 
     const unsigned char *p = s; 

     do { 
      if (*p++ == c) 
       return ((void *)(p - 1)); 
     } while (--n != 0); 
    } 
    return (NULL); 
} 

Answer 4

memchr जैसे memset और memcpy आमतौर पर मशीन कोड की काफी छोटी मात्रा को कम करता है। आप inlining similar assembly code के बिना उस तरह की गति को पुन: पेश करने में सक्षम होने की संभावना नहीं है। कार्यान्वयन में विचार करने के लिए एक प्रमुख मुद्दा data alignment है।

एक generic technique you may be able to use स्ट्रिंग की खोज के अंत में sentinel डालने के लिए है, जो गारंटी देता है कि आपको यह मिल जाएगा। यह आपको लूप के अंदर, लूप के अंदर से स्ट्रिंग के अंत के लिए परीक्षण को स्थानांतरित करने की अनुमति देता है।