सी # से सी ++ शब्दकोश unordered_map परिणामों के लिए

Question

मैंने कुछ वर्षों के सी # अब किया है, और मैं कुछ नई चीजें सीखने की कोशिश कर रहा हूं। तो मैंने प्रोग्रामिंग को एक अलग तरीके से जानने के लिए, सी ++ पर एक नज़र डालने का फैसला किया।

मैं पढ़ने के भार कर रहा हूं, लेकिन मैंने आज कुछ कोड लिखना शुरू कर दिया है।

मेरी विंडोज 7/64 बिट मशीन पर, वीएस -2010 चल रहा है, मैंने दो परियोजनाएं बनाई: 1) एक सी # प्रोजेक्ट जो मुझे चीजों को लिखने की अनुमति देता है। 2) एक सी ++ "मेकफ़ाइल" प्रोजेक्ट जो मुझे एक ही चीज़ को लागू करने की कोशिश कर रहा है। जो मैं समझता हूं उससे, यह एक .NET प्रोजेक्ट नहीं है।

मुझे 10K मानों के साथ एक शब्दकोश को पॉप्युलेट करने का प्रयास करना पड़ा। किसी कारण से, सी ++ तीव्रता के आदेश धीमा है।

यहां नीचे सी # है। नोट मैं समय माप के बाद एक समारोह में डाल सुनिश्चित करने के लिए यह "अनुकूलित" नहीं कर रहा था दूर संकलक द्वारा:

var freq = System.Diagnostics.Stopwatch.Frequency; 

int i; 
Dictionary<int, int> dict = new Dictionary<int, int>(); 
var clock = System.Diagnostics.Stopwatch.StartNew(); 

for (i = 0; i < 10000; i++) 
    dict[i] = i; 
clock.Stop(); 

Console.WriteLine(clock.ElapsedTicks/(decimal)freq * 1000M); 
Console.WriteLine(dict.Average(x=>x.Value)); 
Console.ReadKey(); //Don't want results to vanish off screen 

यहाँ C++, बहुत ज्यादा नहीं सोचा था कि इसे में चला गया है है (जानने की कोशिश कर, सही?) int इनपुट;

LARGE_INTEGER frequency;  // ticks per second 
LARGE_INTEGER t1, t2;   // ticks 
double elapsedTime; 

// get ticks per second 
QueryPerformanceFrequency(&frequency); 

int i; 
boost::unordered_map<int, int> dict; 
// start timer 
QueryPerformanceCounter(&t1); 

for (i=0;i<10000;i++) 
    dict[i]=i; 

// stop timer 
QueryPerformanceCounter(&t2); 

// compute and print the elapsed time in millisec 
elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0/frequency.QuadPart; 
cout << elapsedTime << " ms insert time\n"; 
int input; 
cin >> input; //don't want console to disappear 

अब, कुछ चेतावनी। I managed to find this related SO question. लोगों में से एक ने परिणामों का स्काईइंग WOW64 का उल्लेख करते हुए एक लंबा जवाब लिखा। मैंने प्रोजेक्ट को रिलीज़ करने के लिए सेट किया है और सी ++ प्रोजेक्ट के "गुण" टैब के माध्यम से चला गया है, जिससे सबकुछ ऐसा लगता है जो इसे तेज कर देगा। प्लेटफॉर्म को x64 में बदल दिया, हालांकि मुझे यकीन नहीं है कि वह उसके वाह 64 मुद्दे को संबोधित करता है या नहीं। मैं संकलक विकल्पों के साथ अनुभव नहीं कर रहा हूं, शायद आप लोगों के पास एक सुराग है?

ओह, और परिणाम: सी #: 0.32ms सी ++: 8.26ms। यह थोड़ा अजीब है। क्या मैंने कुछ के बारे में गलत व्याख्या की है। क्वाड का मतलब है? मैंने वेब पर किसी स्थान से सी ++ टाइमर कोड की प्रतिलिपि बनाई, सभी बूस्ट इंस्टॉलेशन के माध्यम से जाकर/libfile rigmarole शामिल किया। या शायद मैं वास्तव में अनजाने में विभिन्न उपकरणों का उपयोग कर रहा हूँ? या कुछ महत्वपूर्ण संकलन विकल्प है जिसका मैंने उपयोग नहीं किया है? या शायद सी # कोड अनुकूलित किया गया है क्योंकि औसत स्थिर है?

यहाँ C++ कमांड लाइन, संपत्ति से है पृष्ठ-> C/C++ -> कमांड लाइन: /मैं "C: \ Users \ कार्लोस \ डेस्कटॉप \ boost_1_47_0"/जि/Nologo/डब्ल्यू 3/WX-/एमपी/ऑक्स/ओई/ओटी/जीएल/डी "_एमबीसीएस"/जीएम-/ईएचएससी/जीएस-/जीई// आर्क: एसएसई 2/एफपी: फास्ट/जेडसी: wchar_t/जेडसी :स्कोप/एफपी "x64 \ रिलीज \ मेकटेस्ट .pch "/ Fa" x64 \ release \ "/ fo" x64 \ release \ "/Fd"x64\Release\vc100.pdb"/जीडी/त्रुटि रिपोर्ट: कतार

किसी भी मदद की सराहना की जाएगी, धन्यवाद।

Answer 1

एक साधारण आवंटक परिवर्तन उस समय बहुत कम हो जाएगा।

boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>, boost::fast_pool_allocator<std::pair<const int, int>>> dict; 

मेरे सिस्टम पर 0.9ms (10ms से पहले)। यह मुझे बताता है कि असल में, आपके समय का विशाल, विशाल बहुमत हैश टेबल में बिल्कुल नहीं बिताया जाता है, लेकिन आवंटक में। इसका कारण यह है कि यह एक अनुचित तुलना है क्योंकि आपका जीसी इस तरह के एक छोटे से कार्यक्रम में कभी भी एकत्र नहीं करेगा, इसे एक अनुचित प्रदर्शन लाभ प्रदान करेगा, और मूल आवंटकों को मुफ्त मेमोरी का महत्वपूर्ण कैशिंग करना होगा- लेकिन यह कभी भी इस तरह के तुच्छ में नहीं खेलेंगे उदाहरण के लिए, क्योंकि आपने कभी भी आवंटित या अस्वीकार नहीं किया है और इसलिए कैश करने के लिए कुछ भी नहीं है।

अंत में, बूस्ट पूल कार्यान्वयन थ्रेड-सुरक्षित है, जबकि आप धागे के साथ कभी नहीं खेलते हैं, इसलिए जीसी सिर्फ एक-थ्रेडेड कार्यान्वयन पर वापस आ सकता है, जो बहुत तेज होगा।

मैंने हाथ से लुढ़का हुआ, गैर-मुक्त गैर-थ्रेड-सुरक्षित पूल आवंटक का सहारा लिया और सी # + के लिए 0.45ms तक मेरी मशीन पर 0.55ms तक पहुंच गया। निष्कर्ष: दो मूल भाषाओं की विभिन्न स्मृति आवंटन योजनाओं के कारण आपके मूल परिणाम बहुत कम किए गए थे, और एक बार यह हल हो जाने के बाद, अंतर अपेक्षाकृत कम हो जाता है।

एक कस्टम हैशर (जैसा कि अलेक्जेंड्रे के उत्तर में वर्णित है) ने मेरे सी ++ समय को 0.34ms तक गिरा दिया, जो अब सी # से तेज है।

static const int MaxMemorySize = 800000; 
static int FreedMemory = 0; 
static int AllocatorCalls = 0; 
static int DeallocatorCalls = 0; 
template <typename T> 
class LocalAllocator 
{ 
    public: 
     std::vector<char>* memory; 
     int* CurrentUsed; 
     typedef T value_type; 
     typedef value_type * pointer; 
     typedef const value_type * const_pointer; 
     typedef value_type & reference; 
     typedef const value_type & const_reference; 
     typedef std::size_t size_type; 
     typedef std::size_t difference_type; 

    template <typename U> struct rebind { typedef LocalAllocator<U> other; }; 

    template <typename U> 
    LocalAllocator(const LocalAllocator<U>& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    LocalAllocator(std::vector<char>* ptr, int* used) { 
     CurrentUsed = used; 
     memory = ptr; 
    } 
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    pointer address(reference r) { return &r; } 
    const_pointer address(const_reference s) { return &r; } 
    size_type max_size() const { return MaxMemorySize; } 
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); } 
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); } 
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); } 

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; } 
    bool operator!=(const LocalAllocator&) const { return false; } 

    pointer allocate(size_type count) { 
     AllocatorCalls++; 
     if (*CurrentUsed + (count * sizeof(T)) > MaxMemorySize) 
      throw std::bad_alloc(); 
     if (*CurrentUsed % std::alignment_of<T>::value) { 
      *CurrentUsed += (std::alignment_of<T>::value - *CurrentUsed % std::alignment_of<T>::value); 
     } 
     auto val = &((*memory)[*CurrentUsed]); 
     *CurrentUsed += (count * sizeof(T)); 
     return reinterpret_cast<pointer>(val); 
    } 
    void deallocate(pointer ptr, size_type n) { 
     DeallocatorCalls++; 
     FreedMemory += (n * sizeof(T)); 
    } 

    pointer allocate() { 
     return allocate(sizeof(T)); 
    } 
    void deallocate(pointer ptr) { 
     return deallocate(ptr, 1); 
    } 
}; 
int main() { 
    LARGE_INTEGER frequency;  // ticks per second 
    LARGE_INTEGER t1, t2;   // ticks 
    double elapsedTime; 

    // get ticks per second 
    QueryPerformanceFrequency(&frequency); 
    std::vector<char> memory; 
    int CurrentUsed = 0; 
    memory.resize(MaxMemorySize); 

    struct custom_hash { 
     size_t operator()(int x) const { return x; } 
    }; 
    boost::unordered_map<int, int, custom_hash, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
     std::unordered_map<int, int>().bucket_count(), 
     custom_hash(), 
     std::equal_to<int>(), 
     LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed) 
    ); 

    // start timer 
    std::string str; 
    QueryPerformanceCounter(&t1); 

    for (int i=0;i<10000;i++) 
     dict[i]=i; 

    // stop timer 
    QueryPerformanceCounter(&t2); 

    // compute and print the elapsed time in millisec 
    elapsedTime = ((t2.QuadPart - t1.QuadPart) * 1000.0)/frequency.QuadPart; 
    std::cout << elapsedTime << " ms insert time\n"; 
    int input; 
    std::cin >> input; //don't want console to disappear 
} 

Answer 2

आरोही क्रम में जोड़े गए अंकीय अभिन्न कुंजी के लगातार अनुक्रम को संग्रहीत करना निश्चित रूप से हैश टेबल को अनुकूलित करने के लिए अनुकूलित नहीं किया गया है।

एक सरणी का उपयोग करें, या फिर यादृच्छिक मान उत्पन्न करें।

और कुछ पुनर्प्राप्ति करें। हैश टेबल पुनर्प्राप्ति के लिए अत्यधिक अनुकूलित हैं।

Answer 3

दृश्य स्टूडियो TR1 unordered_map stdext :: hash_map रूप में ही है:

एक और धागा पूछ कारण है कि यह धीमी गति से करता है, दूसरों के लिए लिंक है कि एक ही मुद्दे की खोज की है के साथ मेरा उत्तर देखें।

Alternative to stdext::hash_map for performance reasons

Btw: निष्कर्ष +++ सी में जब एक और hash_map कार्यान्वयन उपयोग करने के लिए है। याद रखें जब सी ++ में सी # की तुलना में अनुकूलित रिलीज-बिल्ड और गैर-अनुकूलित डीबग-बिल्ड के बीच बड़ा अंतर होता है।

Answer 4

तत्वों को डालने से पहले n के विभिन्न (बड़े) मानों के साथ dict.rehash(n) को आजमाएं, और देखें कि यह प्रदर्शन को कैसे प्रभावित करता है। मेमोरी आवंटन (वे कंटेनर बाल्टी भरने पर होते हैं) आमतौर पर सी # की तुलना में सी ++ में अधिक महंगा होते हैं, और रीहैशिंग भी भारी होती है। std::vector और std::deque के लिए, एनालॉग सदस्य फ़ंक्शन reserve है।

विभिन्न रीहैश नीतियां और लोड फैक्टर थ्रेसहोल्ड (max_load_factor सदस्य फ़ंक्शन पर नज़र डालें) unordered_map के प्रदर्शन पर भी बहुत प्रभाव डालेगा।

अगला, चूंकि आप वीएस -2010 का उपयोग कर रहे हैं, तो मेरा सुझाव है कि आप <unordered_map> शीर्षलेख से std::unordered_map का उपयोग करें। जब आप मानक पुस्तकालय का उपयोग कर सकते हैं तो boost का उपयोग न करें।

वास्तविक हैश फ़ंक्शन का उपयोग प्रदर्शन पर बहुत अधिक प्रभाव डाल सकता है। आप निम्नलिखित के साथ प्रयास कर सकते हैं:

struct custom_hash { size_t operator()(int x) const { return x; } }; 

और std::unordered_map<int, int, custom_hash> का उपयोग करें।

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