एक घड़ी चक्र

Question

में सी ++ स्ट्रिंग तुलना में यह एक एकल प्रोसेसर चक्र में पूरी स्मृति क्षेत्रों की तुलना करना संभव है? कुछ प्रकार के एमएमएक्स असेंबलर निर्देश का उपयोग कर एक प्रोसेसर चक्र में दो तारों की तुलना करना अधिक सटीक है? या strcmp है - पहले से ही उस अनुकूलन के आधार पर पूरक?

संपादित करें: या स्ट्रिंग डुप्लिकेट को हटाने के लिए सी ++ कंपाइलर को निर्देश देना संभव है, ताकि तारों को उनकी स्मृति स्थान से आसानी से तुलना की जा सके? memcmp(a,b) के बजाय a==b की तुलना में (यह मानते हुए कि a और b दोनों देशी const char* तार हैं)।

Answer 1

वास्तव में नहीं। आपका ठेठ 1-बाइट तुलना निर्देश 1 चक्र लेता है। आपकी सर्वश्रेष्ठ शर्त एमएमएक्स 64-बिट तुलना निर्देशों का उपयोग करना होगा (this page for an example) देखें। हालांकि, वे रजिस्टरों पर काम करते हैं, जिन्हें स्मृति से लोड किया जाना चाहिए। मेमोरी लोड आपके समय को काफी नुकसान पहुंचाएंगे, क्योंकि आप बाहर जायेंगे एल 1 कैश में सबसे अच्छा, जो कुछ 10x समय की मंदी को जोड़ता है *। यदि आप कुछ भारी स्ट्रिंग प्रोसेसिंग कर रहे हैं, तो आप शायद कुछ निफ्टी स्पीडअप प्राप्त कर सकते हैं, लेकिन फिर, यह चोट पहुंचाने जा रहा है।

अन्य लोग प्री-कंप्यूटिंग का सुझाव देते हैं तार। हो सकता है कि अपने विशेष अनुप्रयोग के लिए काम करेंगे, शायद यह नहीं होगा। आप तार की तुलना करने के है? आप संख्याओं की तुलना कर सकते हैं?

आपका संपादन संकेत की तुलना पता चलता है। वह एक खतरनाक situa है टियन जब तक आप विशेष रूप से गारंटी नहीं दे सकते कि आप सबस्ट्रिंग तुलना नहीं कर पाएंगे (यानी, आप कुछ दो बाइट तारों की तुलना कर रहे हैं: [0x40, 0x50] [0x40, 0x42] के साथ। वे "बराबर" नहीं हैं, लेकिन एक सूचक तुलना वे कहेंगे)।

क्या आपने gcc strcmp() स्रोत देखा है? मैं सुझाव दूंगा कि ऐसा करना आदर्श प्रारंभिक स्थान होगा।

* यदि कोई चक्र 1 यूनिट लेता है, तो एल 1 हिट 10 इकाइयां लेता है, एक वास्तविक रैम हिट वास्तव में लंबे समय तक लेता है।

Answer 2

यह आप कितना preprocessing कर पर निर्भर करता है। सी # और जावा दोनों में इंटर्निंग स्ट्रिंग नामक एक प्रक्रिया होती है जो प्रत्येक स्ट्रिंग मैप को उसी पते पर बनाती है यदि उनके पास समान सामग्री हो। इस तरह की प्रक्रिया मानते हुए, आप एक तुलना निर्देश के साथ एक स्ट्रिंग समानता तुलना कर सकते हैं।

आदेश थोड़ा मुश्किल है।

संपादित करें: स्पष्ट रूप से यह उत्तर एक चक्र के भीतर एक स्ट्रिंग तुलना करने के प्रयास के वास्तविक मुद्दे को दूर कर रहा है। लेकिन यह तब तक करने का एकमात्र तरीका है जब तक कि आपके पास निर्देशों का अनुक्रम न हो जो स्ट्रैम्प के समतुल्य निर्धारित करने के लिए निरंतर समय में स्मृति की असंबद्ध मात्रा को देख सके। जो असंभव है, क्योंकि यदि आपके पास ऐसा आर्किटेक्चर था तो वह व्यक्ति जिसने इसे बेच दिया था, "अरे, यह एक अद्भुत निर्देश है जो एक चक्र में एक स्ट्रिंग की तुलना कर सकता है! वह कितना भयानक है?" और आपको स्टैक ओवरफ्लो पर कोई प्रश्न पोस्ट करने की आवश्यकता नहीं होगी।

लेकिन वह बस अपना तर्क राय है।

Answer 3

भले ही दोनों तारों को कैश किया गया हो, फिर भी एक प्रोसेसर चक्र में तुलनात्मक रूप से लंबी (मनमाने ढंग से लंबी) तारों की तुलना करना संभव नहीं होगा। एक आधुनिक कंपाइलर पर्यावरण में strcmp के कार्यान्वयन को काफी अनुकूलित किया जाना चाहिए, इसलिए आपको बहुत अधिक अनुकूलित करने के लिए परेशान नहीं होना चाहिए।

(अपने संपादित करने के लिए उत्तर में) संपादित करें:

1. आप संकलक सभी डुप्लिकेट तार को एकजुट करने के निर्देश दे सकते हैं नहीं - सबसे compilers कुछ इस तरह कर सकते हैं, लेकिन यह केवल सबसे अच्छा प्रयास है (और मैं किसी भी कंपाइलर को नहीं जानते जहां यह संकलन इकाइयों में काम करता है)।

2. आप उस के बाद iterators एक नक्शा करने के लिए तार जोड़ने और तुलना द्वारा बेहतर प्रदर्शन प्राप्त हो सकता है ... तुलना ही एक चक्र (या नहीं भी बहुत कुछ) तो

3. तो हो सकता है करने के लिए तार के सेट उपयोग तय किया गया है, गणना का उपयोग करें - यही वह है जो वे वहां हैं।

Answer 4

मान लिया जाये कि क्या आपका मतलब x86 ... Here इंटेल प्रलेखन है।

लेकिन मेरे सिर के ऊपर से, नहीं, मुझे नहीं लगता कि आप एक समय में एक रजिस्टर के आकार से अधिक तुलना कर सकते हैं।

जिज्ञासा से बाहर

, आप क्यों पूछते हैं? मैं आखिरी बार Knuth का आह्वान करने के लिए आखिरी हूँ, लेकिन ... strcmp आमतौर पर एक बहुत अच्छा काम करता है।

संपादित: लिंक अब आधुनिक प्रलेखन के लिए अंक।

Answer 5

या यह ++ सी निर्देश देने संकलक स्ट्रिंग डुप्लिकेट निकालने के लिए संभव है, तो तार बस उनकी स्मृति स्थान के आधार पर तुलना की जा सकती है?

सं संकलक डुप्लिकेट आंतरिक रूप से निकाल सकते हैं, लेकिन मैं नहीं संकलक की गारंटी देता है या इस तरह के एक अनुकूलन (संभवतः छोड़कर इसे बंद करने) तक पहुँचने के लिए सुविधाएं प्रदान करता है इस बात का पता है। निश्चित रूप से सी ++ मानक के पास इस क्षेत्र में कुछ भी कहना नहीं है।

Answer 6

एक चक्र में सामान्य उद्देश्य स्ट्रिंग ऑपरेशंस करना संभव नहीं है, लेकिन कई ऑप्टिमाइज़ेशन हैं जो आप अतिरिक्त जानकारी के साथ आवेदन कर सकते हैं।

• आपकी समस्या डोमेन है कि एक मशीन रजिस्टर में फिट बैठता है तार के लिए एक गठबंधन, निश्चित-आकार बफर के उपयोग की अनुमति देता है, तो आप एकल चक्र तुलना (लोड निर्देश गिनती नहीं) प्रदर्शन कर सकते हैं।
• यदि आप हमेशा अपने तारों की लंबाई का ट्रैक रखते हैं, तो आप लंबाई की तुलना कर सकते हैं और memcmp का उपयोग कर सकते हैं, जो strcmp से तेज़ है। यदि आपका आवेदन बहु-सांस्कृतिक है, तो ध्यान रखें कि यह केवल ordinal string comparison के लिए काम करता है।
• ऐसा प्रतीत होता है कि आप सी ++ का उपयोग कर रहे हैं। यदि आपको केवल अपरिवर्तनीय तारों के साथ समानता तुलना की आवश्यकता है, तो आप एक स्ट्रिंग इंटर्निंग समाधान (प्रतिलिपि/पेस्ट लिंक का उपयोग कर सकते हैं क्योंकि मैं एक नया उपयोगकर्ता हूं) गारंटी देता हूं कि बराबर तार उसी स्मृति स्थान पर संग्रहीत होते हैं, जिस बिंदु पर आप बस तुलना कर सकते हैं संकेत दिए गए। en.wikipedia.org/wiki/String_interning
• इसके अलावा, टेक्स्ट प्रोसेसिंग के लिए एसएसई 4.2 के निर्देशों के विवरण के लिए इंटेल ऑप्टिमाइज़ेशन रेफरेंस मैनुअल, अध्याय 10 पर एक नज़र डालें। www.intel.com/products/processor/manuals/

संपादित करें: आपकी समस्या डोमेन एक गणन के उपयोग की अनुमति देता है, तो उस है अपने एकल चक्र तुलना समाधान। इसे मत लड़ो।

Answer 7

यदि आप स्ट्रिंग तुलना के लिए अनुकूलित कर रहे हैं, तो आप एक स्ट्रिंग टेबल को नियोजित करना चाहते हैं (फिर आपको केवल दो स्ट्रिंग्स के इंडेक्स की तुलना करने की आवश्यकता है, जो एक मशीन निर्देश में किया जा सकता है)।

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

Answer 8

आप निश्चित रूप से एक चक्र में एक से अधिक बाइट की तुलना कर सकते हैं। यदि हम x86-64 का उदाहरण लेते हैं, तो आप एक ही निर्देश (cmps) में 64-बिट्स (8 बाइट्स) की तुलना कर सकते हैं, यह आवश्यक रूप से एक चक्र नहीं है लेकिन आमतौर पर कम एकल अंकों में होगा (सटीक गति विशिष्ट प्रोसेसर संस्करण पर निर्भर करता है)।

हालांकि, इसका मतलब यह नहीं कि आप स्मृति strcmp तुलना में बहुत तेज में दो सरणियों की तुलना में सब काम करने में सक्षम हो जाएगा: -

1. नहीं है बस की तुलना में अधिक तुलना करें - आप की तुलना करने की जरूरत है दो मान, जांचें कि वे एक जैसे हैं, और यदि ऐसा है तो अगले खंड में जाएं।
2. अधिकतर strcmp कार्यान्वयन पहले से ही अत्यधिक अनुकूलित किए जाएंगे, जिसमें यह जांच भी शामिल है कि एक और बी को उसी पते पर इंगित किया गया है, और कोई उपयुक्त निर्देश-स्तर अनुकूलन।

जब तक आप strcmp में बिताए समय की बहुत देख रहे हैं, मैं इसके बारे में चिंता नहीं करता है - आप एक विशिष्ट समस्या/उपयोग के मामले आप में सुधार की कोशिश कर रहे है?

Answer 9

आप अपने अपरिवर्तनीय तारों को प्रशिक्षित करने के लिए Boost Flyweight लाइब्रेरी का उपयोग कर सकते हैं। स्ट्रिंग समानता/असमानता परीक्षण तब बहुत तेज हो जाते हैं क्योंकि उस बिंदु पर इसे करने के लिए सभी बिंदुओं की तुलना करना है (पन इरादा नहीं है)।

Answer 10

अपनी स्ट्रिंग तुलना के लिए मानक सी strcmp() या सी ++ std::string::operator==() का उपयोग करें।

उनके कार्यान्वयन उचित रूप से अच्छे हैं और शायद एक बहुत ही अनुकूलित अनुकूलित असेंबली के लिए संकलित किए गए हैं, यहां तक ​​कि प्रतिभावान असेंबली प्रोग्रामर भी मैच के लिए चुनौतीपूर्ण पाएंगे।

तो छोटी चीजें पसीना न करें। मैं आपके कोड के अन्य हिस्सों को अनुकूलित करने के लिए सुझाव देना चाहता हूं।

Answer 11

यहां एक समाधान है जो तारों की बजाय enum-like मानों का उपयोग करता है। यह एनम-वैल्यू-विरासत का समर्थन करता है और इस प्रकार सबस्ट्रिंग तुलना के समान तुलना का समर्थन करता है। यह नाम टकराव से बचने के लिए नामकरण के लिए विशेष चरित्र "¤" का भी उपयोग करता है। आप किसी भी वर्ग, फ़ंक्शन या परिवर्तनीय नाम को ले सकते हैं और इसे enum-value में बना सकते हैं (SomeClassA ¤SomeClassA बन जाएगा)।

struct MultiEnum 
{ 
    vector<MultiEnum*> enumList; 
    MultiEnum() 
    { 
     enumList.push_back(this); 
    } 
    MultiEnum(MultiEnum& base) 
    { 
     enumList.assign(base.enumList.begin(),base.enumList.end()); 
     enumList.push_back(this); 
    } 
    MultiEnum(const MultiEnum* base1,const MultiEnum* base2) 
    { 
     enumList.assign(base1->enumList.begin(),base1->enumList.end()); 
     enumList.assign(base2->enumList.begin(),base2->enumList.end()); 
    } 
    bool operator !=(const MultiEnum& other) 
    { 
     return find(enumList.begin(),enumList.end(),&other)==enumList.end(); 
    } 
    bool operator ==(const MultiEnum& other) 
    { 
     return find(enumList.begin(),enumList.end(),&other)!=enumList.end(); 
    } 
    bool operator &(const MultiEnum& other) 
    { 
     return find(enumList.begin(),enumList.end(),&other)!=enumList.end(); 
    } 
    MultiEnum operator|(const MultiEnum& other) 
    { 
     return MultiEnum(this,&other); 
    } 
    MultiEnum operator+(const MultiEnum& other) 
    { 
     return MultiEnum(this,&other); 
    } 
}; 

MultiEnum 
    ¤someString, 
    ¤someString1(¤someString), // link to "someString" because it is a substring of "someString1" 
    ¤someString2(¤someString); 


void Test() 
{ 
    MultiEnum a = ¤someString1|¤someString2; 
    MultiEnum b = ¤someString1; 

    if(a!=¤someString2){} 
    if(b==¤someString2){} 
    if(b&¤someString2){} 
    if(b&¤someString){} // will result in true, because someString is substring of someString1 
} 

पीएस। मेरे पास आज सुबह मेरे हाथों पर बहुत अधिक खाली समय था, लेकिन पहिया को फिर से शुरू करना कभी-कभी बहुत मजेदार होता है ... :)