मैंने इसे जीथब पर पोस्ट किया नया प्रोजेक्ट एक सरल जीपीयू हैश टेबल.

यह एक साधारण जीपीयू हैश टेबल है जो प्रति सेकंड सैकड़ों लाखों इंसर्ट को प्रोसेस करने में सक्षम है। मेरे NVIDIA GTX 1060 लैपटॉप पर, कोड लगभग 64 एमएस में 210 मिलियन बेतरतीब ढंग से उत्पन्न कुंजी-मूल्य जोड़े डालता है और लगभग 32 एमएस में 64 मिलियन जोड़े हटा देता है।

यानी, लैपटॉप पर स्पीड लगभग 300 मिलियन इंसर्ट/सेकंड और 500 मिलियन डिलीट/सेकंड है।

तालिका CUDA में लिखी गई है, हालाँकि वही तकनीक HLSL या GLSL पर लागू की जा सकती है। वीडियो कार्ड पर उच्च प्रदर्शन सुनिश्चित करने के लिए कार्यान्वयन की कई सीमाएँ हैं:

• केवल 32-बिट कुंजियाँ और समान मान संसाधित होते हैं।
• हैश तालिका का एक निश्चित आकार होता है।
• और यह आकार दो घात के बराबर होना चाहिए।

कुंजियों और मानों के लिए, आपको एक साधारण सीमांकक मार्कर आरक्षित करना होगा (उपरोक्त कोड में यह 0xffffffff है)।

ताले के बिना हैश तालिका

हैश तालिका ओपन एड्रेसिंग का उपयोग करती है रैखिक जांच, यानी, यह केवल कुंजी-मूल्य जोड़े की एक सरणी है जो मेमोरी में संग्रहीत होती है और इसमें बेहतर कैश प्रदर्शन होता है। चेनिंग के लिए ऐसा नहीं कहा जा सकता है, जिसमें लिंक की गई सूची में पॉइंटर की खोज करना शामिल है। हैश तालिका तत्वों को संग्रहित करने वाली एक सरल सारणी है KeyValue:

struct KeyValue
{
    uint32_t key;
    uint32_t value;
};

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

तालिका केवल प्रत्येक तत्व के लिए कुंजी और मान संग्रहीत करती है, कुंजी का हैश नहीं। चूँकि तालिका केवल 32-बिट कुंजियाँ संग्रहीत करती है, इसलिए हैश की गणना बहुत जल्दी की जाती है। उपरोक्त कोड Murmur3 हैश का उपयोग करता है, जो केवल कुछ बदलाव, XOR और गुणन करता है।

हैश तालिका लॉकिंग सुरक्षा तकनीकों का उपयोग करती है जो मेमोरी ऑर्डर से स्वतंत्र होती हैं। भले ही कुछ लेखन ऑपरेशन ऐसे अन्य ऑपरेशनों के क्रम को बाधित करते हों, फिर भी हैश तालिका सही स्थिति बनाए रखेगी। हम इसके बारे में नीचे बात करेंगे. यह तकनीक उन वीडियो कार्डों के साथ बढ़िया काम करती है जो हजारों थ्रेड एक साथ चलाते हैं।

हैश तालिका में कुंजियाँ और मान खाली करने के लिए प्रारंभ किए जाते हैं।

कोड को 64-बिट कुंजियों और मानों को संभालने के लिए भी संशोधित किया जा सकता है। कुंजियों को परमाणु पढ़ने, लिखने और तुलना-और-स्वैप संचालन की आवश्यकता होती है। और मूल्यों के लिए परमाणु पढ़ने और लिखने के संचालन की आवश्यकता होती है। सौभाग्य से, CUDA में, 32- और 64-बिट मानों के लिए पढ़ने-लिखने के संचालन तब तक परमाणु होते हैं जब तक वे स्वाभाविक रूप से संरेखित होते हैं (नीचे देखें)। यहां), और आधुनिक वीडियो कार्ड 64-बिट परमाणु तुलना-और-विनिमय संचालन का समर्थन करते हैं। बेशक, 64 बिट्स पर जाने पर प्रदर्शन थोड़ा कम हो जाएगा।

हैश तालिका स्थिति

हैश तालिका में प्रत्येक कुंजी-मूल्य जोड़ी में चार अवस्थाओं में से एक हो सकती है:

• कुंजी और मान रिक्त हैं. इस स्थिति में, हैश तालिका प्रारंभ की जाती है।
• कुंजी तो लिख दी गई है, परंतु मूल्य अभी तक नहीं लिखा गया है। यदि कोई अन्य थ्रेड वर्तमान में डेटा पढ़ रहा है, तो वह खाली लौटता है। यह सामान्य है, यदि निष्पादन का कोई अन्य थ्रेड थोड़ा पहले काम करता तो यही बात होती, और हम समवर्ती डेटा संरचना के बारे में बात कर रहे हैं।
• कुंजी और मान दोनों रिकॉर्ड किए जाते हैं.
• मान निष्पादन के अन्य थ्रेड्स के लिए उपलब्ध है, लेकिन कुंजी अभी तक उपलब्ध नहीं है। ऐसा इसलिए हो सकता है क्योंकि CUDA प्रोग्रामिंग मॉडल में शिथिल रूप से ऑर्डर किया गया मेमोरी मॉडल है। यह सामान्य है; किसी भी स्थिति में, कुंजी अभी भी खाली है, भले ही मान अब ऐसा न हो।

एक महत्वपूर्ण बारीकियां यह है कि एक बार कुंजी को स्लॉट में लिख दिया गया है, तो यह आगे नहीं बढ़ती है - भले ही कुंजी हटा दी गई हो, हम इसके बारे में नीचे बात करेंगे।

हैश टेबल कोड शिथिल क्रम वाले मेमोरी मॉडल के साथ भी काम करता है जिसमें मेमोरी को पढ़ने और लिखने का क्रम अज्ञात है। जैसा कि हम हैश तालिका में सम्मिलन, लुकअप और विलोपन को देखते हैं, याद रखें कि प्रत्येक कुंजी-मूल्य जोड़ी ऊपर वर्णित चार स्थितियों में से एक में है।

हैश तालिका में सम्मिलित करना

CUDA फ़ंक्शन जो कुंजी-मूल्य जोड़े को हैश तालिका में सम्मिलित करता है, इस तरह दिखता है:

void gpu_hashtable_insert(KeyValue* hashtable, uint32_t key, uint32_t value)
{
    uint32_t slot = hash(key);

    while (true)
    {
        uint32_t prev = atomicCAS(&hashtable[slot].key, kEmpty, key);
        if (prev == kEmpty || prev == key)
        {
            hashtable[slot].value = value;
            break;
        }
        slot = (slot + 1) & (kHashTableCapacity-1);
    }
}

एक कुंजी डालने के लिए, कोड सम्मिलित कुंजी के हैश से शुरू होकर हैश तालिका सरणी के माध्यम से पुनरावृत्त होता है। सरणी में प्रत्येक स्लॉट एक परमाणु तुलना-और-स्वैप ऑपरेशन करता है जो उस स्लॉट में कुंजी की तुलना खाली से करता है। यदि बेमेल का पता चलता है, तो स्लॉट में कुंजी को सम्मिलित कुंजी के साथ अद्यतन किया जाता है, और फिर मूल स्लॉट कुंजी वापस कर दी जाती है। यदि यह मूल कुंजी खाली थी या सम्मिलित कुंजी से मेल खाती थी, तो कोड को सम्मिलन के लिए एक उपयुक्त स्लॉट मिला और सम्मिलित मूल्य को स्लॉट में डाला गया।

यदि एक कर्नेल कॉल में gpu_hashtable_insert() एक ही कुंजी के साथ कई तत्व हैं, तो उनके किसी भी मान को कुंजी स्लॉट में लिखा जा सकता है। इसे सामान्य माना जाता है: कॉल के दौरान की-वैल्यू राइट्स में से एक सफल होगा, लेकिन चूंकि यह सब निष्पादन के कई थ्रेड्स के भीतर समानांतर में होता है, इसलिए हम यह अनुमान नहीं लगा सकते कि कौन सी मेमोरी राइटिंग आखिरी होगी।

हैश टेबल लुकअप

कुंजी खोजने के लिए कोड:

uint32_t gpu_hashtable_lookup(KeyValue* hashtable, uint32_t key)
{
        uint32_t slot = hash(key);

        while (true)
        {
            if (hashtable[slot].key == key)
            {
                return hashtable[slot].value;
            }
            if (hashtable[slot].key == kEmpty)
            {
                return kEmpty;
            }
            slot = (slot + 1) & (kHashTableCapacity - 1);
        }
}

किसी तालिका में संग्रहीत कुंजी का मान ज्ञात करने के लिए, हम जिस कुंजी की तलाश कर रहे हैं उसके हैश से शुरू करके सरणी के माध्यम से पुनरावृति करते हैं। प्रत्येक स्लॉट में, हम जांचते हैं कि क्या कुंजी वह है जिसे हम ढूंढ रहे हैं, और यदि हां, तो हम उसका मान लौटाते हैं। हम यह भी जांचते हैं कि कुंजी खाली है या नहीं, और यदि हां, तो हम खोज को रोक देते हैं।

यदि हमें कुंजी नहीं मिल पाती है, तो कोड एक खाली मान लौटाता है।

इन सभी खोज कार्यों को सम्मिलन और विलोपन के माध्यम से एक साथ निष्पादित किया जा सकता है। तालिका में प्रत्येक जोड़ी में प्रवाह के लिए ऊपर वर्णित चार स्थितियों में से एक होगी।

हैश तालिका में हटाना

कुंजियाँ हटाने के लिए कोड:

void gpu_hashtable_delete(KeyValue* hashtable, uint32_t key, uint32_t value)
{
    uint32_t slot = hash(key);

    while (true)
    {
        if (hashtable[slot].key == key)
        {
            hashtable[slot].value = kEmpty;
            return;
        }
        if (hashtable[slot].key == kEmpty)
        {
            return;
        }
        slot = (slot + 1) & (kHashTableCapacity - 1);
    }
}

किसी कुंजी को हटाना एक असामान्य तरीके से किया जाता है: हम कुंजी को तालिका में छोड़ देते हैं और उसके मान (कुंजी को नहीं) को खाली के रूप में चिह्नित करते हैं। यह कोड काफी हद तक मिलता जुलता है lookup(), सिवाय इसके कि जब किसी कुंजी पर मिलान पाया जाता है, तो यह उसका मान रिक्त कर देता है।

जैसा कि ऊपर उल्लेख किया गया है, एक बार एक स्लॉट में कुंजी लिखी जाने के बाद, इसे स्थानांतरित नहीं किया जाता है। यहां तक ​​कि जब कोई तत्व तालिका से हटा दिया जाता है, तब भी कुंजी यथावत रहती है, उसका मान बस खाली हो जाता है। इसका मतलब यह है कि हमें स्लॉट मान के लिए परमाणु लेखन ऑपरेशन का उपयोग करने की आवश्यकता नहीं है, क्योंकि इससे कोई फर्क नहीं पड़ता कि वर्तमान मान खाली है या नहीं - यह अभी भी खाली हो जाएगा।

हैश तालिका का आकार बदलना

आप एक बड़ी तालिका बनाकर और उसमें पुरानी तालिका से गैर-रिक्त तत्वों को सम्मिलित करके हैश तालिका का आकार बदल सकते हैं। मैंने इस कार्यक्षमता को लागू नहीं किया क्योंकि मैं नमूना कोड को सरल रखना चाहता था। इसके अलावा, CUDA प्रोग्रामों में, मेमोरी आवंटन अक्सर CUDA कर्नेल के बजाय होस्ट कोड में किया जाता है।

लेख एक लॉक-मुक्त प्रतीक्षा-मुक्त हैश टेबल वर्णन करता है कि ऐसी लॉक-संरक्षित डेटा संरचना को कैसे संशोधित किया जाए।

प्रतिस्पर्धा

उपरोक्त फ़ंक्शन कोड स्निपेट्स में gpu_hashtable_insert(), _lookup() и _delete() एक समय में एक कुंजी-मूल्य जोड़ी को संसाधित करें। और निचला gpu_hashtable_insert(), _lookup() и _delete() जोड़ों की एक सरणी को समानांतर में संसाधित करें, प्रत्येक जोड़ी को एक अलग GPU निष्पादन थ्रेड में:

// CPU code to invoke the CUDA kernel on the GPU
uint32_t threadblocksize = 1024;
uint32_t gridsize = (numkvs + threadblocksize - 1) / threadblocksize;
gpu_hashtable_insert_kernel<<<gridsize, threadblocksize>>>(hashtable, kvs, numkvs);

// GPU code to process numkvs key/values in parallel
void gpu_hashtable_insert_kernel(KeyValue* hashtable, const KeyValue* kvs, unsigned int numkvs)
{
    unsigned int threadid = blockIdx.x*blockDim.x + threadIdx.x;
    if (threadid < numkvs)
    {
        gpu_hashtable_insert(hashtable, kvs[threadid].key, kvs[threadid].value);
    }
}

लॉक-प्रतिरोधी हैश तालिका समवर्ती प्रविष्टियों, लुकअप और विलोपन का समर्थन करती है। चूँकि कुंजी-मूल्य जोड़े हमेशा चार अवस्थाओं में से एक में होते हैं और कुंजियाँ हिलती नहीं हैं, तालिका तब भी शुद्धता की गारंटी देती है जब विभिन्न प्रकार के संचालन एक साथ उपयोग किए जाते हैं।

हालाँकि, यदि हम सम्मिलन और विलोपन के एक बैच को समानांतर में संसाधित करते हैं, और यदि जोड़े के इनपुट सरणी में डुप्लिकेट कुंजियाँ हैं, तो हम यह अनुमान नहीं लगा पाएंगे कि कौन सी जोड़ी "जीतेगी" - जो कि हैश तालिका में सबसे अंत में लिखी जाएगी। मान लीजिए कि हमने जोड़े के इनपुट ऐरे के साथ इंसर्शन कोड को कॉल किया है A/0 B/1 A/2 C/3 A/4. जब कोड पूरा हो जाए, जोड़े B/1 и C/3 तालिका में मौजूद होने की गारंटी है, लेकिन साथ ही कोई भी जोड़ा इसमें दिखाई देगा A/0, A/2 या A/4. यह कोई समस्या हो भी सकती है और नहीं भी - यह सब एप्लिकेशन पर निर्भर करता है। आप पहले से जान सकते हैं कि इनपुट ऐरे में कोई डुप्लिकेट कुंजियाँ नहीं हैं, या आपको इस बात की परवाह नहीं होगी कि अंतिम बार कौन सा मान लिखा गया था।

यदि यह आपके लिए एक समस्या है, तो आपको डुप्लिकेट जोड़ियों को अलग-अलग CUDA सिस्टम कॉल में अलग करना होगा। CUDA में, कर्नेल को कॉल करने वाला कोई भी ऑपरेशन हमेशा अगले कर्नेल कॉल से पहले पूरा होता है (कम से कम एक थ्रेड के भीतर। विभिन्न थ्रेड में, कर्नेल को समानांतर में निष्पादित किया जाता है)। उपरोक्त उदाहरण में, यदि आप एक कर्नेल को कॉल करते हैं A/0 B/1 A/2 C/3, और दूसरे के साथ A/4, फिर कुंजी A मूल्य मिलेगा 4.

अब बात करते हैं कि क्या कार्यों को करना चाहिए lookup() и delete() हैश तालिका में जोड़े की एक सरणी के लिए एक सादे या अस्थिर सूचक का उपयोग करें। सीयूडीए दस्तावेज़ीकरण बताता है:

कंपाइलर पढ़ने और लिखने को वैश्विक या साझा मेमोरी में अनुकूलित करना चुन सकता है... इन अनुकूलन को कीवर्ड का उपयोग करके अक्षम किया जा सकता है volatile: ...इस चर का कोई भी संदर्भ वास्तविक मेमोरी में पढ़ने या लिखने के निर्देश में संकलित किया जाता है।

शुद्धता संबंधी विचारों के लिए आवेदन की आवश्यकता नहीं होती है volatile. यदि निष्पादन थ्रेड पहले पढ़े गए ऑपरेशन से कैश्ड मान का उपयोग करता है, तो यह थोड़ी पुरानी जानकारी का उपयोग करेगा। लेकिन फिर भी, यह कर्नेल कॉल के एक निश्चित क्षण में हैश तालिका की सही स्थिति की जानकारी है। यदि आपको नवीनतम जानकारी का उपयोग करने की आवश्यकता है, तो आप सूचकांक का उपयोग कर सकते हैं volatile, लेकिन तब प्रदर्शन थोड़ा कम हो जाएगा: मेरे परीक्षणों के अनुसार, 32 मिलियन तत्वों को हटाने पर, गति 500 ​​मिलियन विलोपन/सेकंड से घटकर 450 मिलियन विलोपन/सेकंड हो गई।

निष्पादन

64 मिलियन तत्वों को सम्मिलित करने और उनमें से 32 मिलियन को हटाने के परीक्षण में, के बीच प्रतिस्पर्धा std::unordered_map और GPU के लिए वस्तुतः कोई हैश तालिका नहीं है:

std::unordered_map तत्वों को डालने और हटाने और फिर उन्हें मुक्त करने में 70 एमएस खर्च हुए unordered_map (लाखों तत्वों से छुटकारा पाने में बहुत समय लगता है, क्योंकि अंदर unordered_map एकाधिक मेमोरी आवंटन किए जाते हैं)। सच बोलू तो, std:unordered_map पूरी तरह से अलग प्रतिबंध. यह निष्पादन का एक एकल सीपीयू थ्रेड है, किसी भी आकार के कुंजी-मानों का समर्थन करता है, उच्च उपयोग दर पर अच्छा प्रदर्शन करता है, और कई विलोपन के बाद स्थिर प्रदर्शन दिखाता है।

GPU और अंतर-प्रोग्राम संचार के लिए हैश तालिका की अवधि 984 एमएस थी। इसमें तालिका को मेमोरी में रखने और उसे हटाने (एक बार में 1 जीबी मेमोरी आवंटित करना, जिसमें CUDA में कुछ समय लगता है), तत्वों को सम्मिलित करना और हटाना, और उन पर पुनरावृत्ति करने में लगने वाला समय शामिल है। वीडियो कार्ड मेमोरी से आने और जाने वाली सभी प्रतियों को भी ध्यान में रखा जाता है।

हैश तालिका को पूरा होने में 271 एमएस लगे। इसमें वीडियो कार्ड द्वारा तत्वों को डालने और हटाने में बिताया गया समय शामिल है, और मेमोरी में कॉपी करने और परिणामी तालिका पर पुनरावृत्त करने में लगने वाले समय को ध्यान में नहीं रखा जाता है। यदि GPU तालिका लंबे समय तक रहती है, या यदि हैश तालिका पूरी तरह से वीडियो कार्ड की मेमोरी में समाहित है (उदाहरण के लिए, एक हैश तालिका बनाने के लिए जिसका उपयोग अन्य GPU कोड द्वारा किया जाएगा, न कि केंद्रीय प्रोसेसर द्वारा), तो परीक्षा परिणाम प्रासंगिक है.

वीडियो कार्ड के लिए हैश तालिका उच्च थ्रूपुट और सक्रिय समानांतरीकरण के कारण उच्च प्रदर्शन प्रदर्शित करती है।

सीमाएं

हैश टेबल आर्किटेक्चर में कुछ मुद्दों के बारे में पता होना चाहिए:

• क्लस्टरिंग के कारण रैखिक जांच में बाधा आती है, जिसके कारण तालिका में कुंजियाँ पूरी तरह से कम रखी जाती हैं।
• फ़ंक्शन का उपयोग करके कुंजियाँ नहीं हटाई जाती हैं delete और समय के साथ वे मेज़ को अव्यवस्थित कर देते हैं।

परिणामस्वरूप, हैश तालिका का प्रदर्शन धीरे-धीरे ख़राब हो सकता है, खासकर यदि यह लंबे समय से मौजूद है और इसमें कई प्रविष्टियाँ और विलोपन हैं। इन नुकसानों को कम करने का एक तरीका यह है कि काफी कम उपयोग दर के साथ एक नई तालिका में दोबारा बदलाव किया जाए और दोबारा इस्तेमाल के दौरान हटाई गई कुंजियों को फ़िल्टर कर दिया जाए।

वर्णित मुद्दों को स्पष्ट करने के लिए, मैं उपरोक्त कोड का उपयोग 128 मिलियन तत्वों के साथ एक तालिका बनाने और 4 मिलियन तत्वों के माध्यम से लूप करने के लिए करूंगा जब तक कि मैं 124 मिलियन स्लॉट (लगभग 0,96 की उपयोग दर) नहीं भर लेता। यहां परिणाम तालिका है, प्रत्येक पंक्ति एक हैश तालिका में 4 मिलियन नए तत्व डालने के लिए एक CUDA कर्नेल कॉल है:

उपयोग दर
सम्मिलन अवधि 4 तत्व

0,00
11,608448 एमएस (361,314798 मिलियन कुंजी/सेकंड)

0,03
11,751424 एमएस (356,918799 मिलियन कुंजी/सेकंड)

0,06
11,942592 एमएस (351,205515 मिलियन कुंजी/सेकंड)

0,09
12,081120 एमएस (347,178429 मिलियन कुंजी/सेकंड)

0,12
12,242560 एमएस (342,600233 मिलियन कुंजी/सेकंड)

0,16
12,396448 एमएस (338,347235 मिलियन कुंजी/सेकंड)

0,19
12,533024 एमएस (334,660176 मिलियन कुंजी/सेकंड)

0,22
12,703328 एमएस (330,173626 मिलियन कुंजी/सेकंड)

0,25
12,884512 एमएस (325,530693 मिलियन कुंजी/सेकंड)

0,28
13,033472 एमएस (321,810182 मिलियन कुंजी/सेकंड)

0,31
13,239296 एमएस (316,807174 मिलियन कुंजी/सेकंड)

0,34
13,392448 एमएस (313,184256 मिलियन कुंजी/सेकंड)

0,37
13,624000 एमएस (307,861434 मिलियन कुंजी/सेकंड)

0,41
13,875520 एमएस (302,280855 मिलियन कुंजी/सेकंड)

0,44
14,126528 एमएस (296,909756 मिलियन कुंजी/सेकंड)

0,47
14,399328 एमएस (291,284699 मिलियन कुंजी/सेकंड)

0,50
14,690304 एमएस (285,515123 मिलियन कुंजी/सेकंड)

0,53
15,039136 एमएस (278,892623 मिलियन कुंजी/सेकंड)

0,56
15,478656 एमएस (270,973402 मिलियन कुंजी/सेकंड)

0,59
15,985664 एमएस (262,379092 मिलियन कुंजी/सेकंड)

0,62
16,668673 एमएस (251,627968 मिलियन कुंजी/सेकंड)

0,66
17,587200 एमएस (238,486174 मिलियन कुंजी/सेकंड)

0,69
18,690048 एमएस (224,413765 मिलियन कुंजी/सेकंड)

0,72
20,278816 एमएस (206,831789 मिलियन कुंजी/सेकंड)

0,75
22,545408 एमएस (186,038058 मिलियन कुंजी/सेकंड)

0,78
26,053312 एमएस (160,989275 मिलियन कुंजी/सेकंड)

0,81
31,895008 एमएस (131,503463 मिलियन कुंजी/सेकंड)

0,84
42,103294 एमएस (99,619378 मिलियन कुंजी/सेकंड)

0,87
61,849056 एमएस (67,815164 मिलियन कुंजी/सेकंड)

0,90
105,695999 एमएस (39,682713 मिलियन कुंजी/सेकंड)

0,94
240,204636 एमएस (17,461378 मिलियन कुंजी/सेकंड)

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

और 64 मिलियन इंसर्ट (उपयोग कारक 0,5) के बाद गहराई की जांच करने वाली हैश तालिका को मापा। औसत गहराई 0,4774 थी, इसलिए अधिकांश चाबियाँ या तो सर्वोत्तम संभव स्लॉट में थीं या सर्वोत्तम स्थिति से एक स्लॉट दूर थीं। अधिकतम ध्वनि गहराई 60 थी.

फिर मैंने 124 मिलियन इंसर्ट (उपयोग कारक 0,97) के साथ एक मेज पर जांच की गहराई को मापा। औसत गहराई पहले से ही 10,1757 थी, और अधिकतम - 6474 (!!). उच्च उपयोग दर पर रैखिक संवेदन प्रदर्शन में काफी गिरावट आती है।

इस हैश तालिका की उपयोग दर को कम रखना सबसे अच्छा है। लेकिन फिर हम मेमोरी खपत की कीमत पर प्रदर्शन बढ़ाते हैं। सौभाग्य से, 32-बिट कुंजियों और मानों के मामले में, इसे उचित ठहराया जा सकता है। यदि उपरोक्त उदाहरण में, 128 मिलियन तत्वों वाली तालिका में, हम उपयोग कारक 0,25 रखते हैं, तो हम इसमें 32 मिलियन से अधिक तत्व नहीं रख सकते हैं, और शेष 96 मिलियन स्लॉट खो जाएंगे - प्रत्येक जोड़ी के लिए 8 बाइट्स , 768 एमबी की खोई हुई मेमोरी।

कृपया ध्यान दें कि हम वीडियो कार्ड मेमोरी के नुकसान के बारे में बात कर रहे हैं, जो सिस्टम मेमोरी से अधिक मूल्यवान संसाधन है। हालाँकि CUDA का समर्थन करने वाले अधिकांश आधुनिक डेस्कटॉप ग्राफ़िक्स कार्ड में कम से कम 4 जीबी मेमोरी होती है (लेखन के समय, NVIDIA 2080 Ti में 11 जीबी है), फिर भी इतनी मात्रा खोना सबसे बुद्धिमानी भरा निर्णय नहीं होगा।

बाद में मैं उन वीडियो कार्डों के लिए हैश टेबल बनाने के बारे में और अधिक लिखूंगा जिनमें जांच की गहराई की समस्या नहीं है, साथ ही हटाए गए स्लॉट का पुन: उपयोग करने के तरीकों के बारे में भी लिखूंगा।

ध्वनि गहराई माप

किसी कुंजी की जांच गहराई निर्धारित करने के लिए, हम कुंजी के हैश (इसका आदर्श तालिका सूचकांक) को उसके वास्तविक तालिका सूचकांक से निकाल सकते हैं:

// get_key_index() -> index of key in hash table
uint32_t probelength = (get_key_index(key) - hash(key)) & (hashtablecapacity-1);

दो के दो के पूरक बाइनरी संख्याओं के जादू और इस तथ्य के कारण कि हैश तालिका की क्षमता दो की शक्ति दो है, यह दृष्टिकोण तब भी काम करेगा जब कुंजी सूचकांक को तालिका की शुरुआत में ले जाया जाएगा। आइए एक कुंजी लें जो 1 पर हैश की गई है, लेकिन स्लॉट 3 में डाली गई है। फिर क्षमता 4 वाली एक टेबल के लिए हमें मिलता है (3 — 1) & 3, जो 2 के बराबर है।

निष्कर्ष

यदि आपके कोई प्रश्न या टिप्पणियाँ हैं, तो कृपया मुझे ईमेल करें ट्विटर या कोई नया विषय खोलें खजाने.

यह कोड उत्कृष्ट लेखों से प्रेरणा लेकर लिखा गया था:

• दुनिया की सबसे सरल लॉक-फ्री हैश टेबल
• एक लॉक-मुक्त प्रतीक्षा-मुक्त हैश टेबल

भविष्य में, मैं वीडियो कार्ड के लिए हैश टेबल कार्यान्वयन के बारे में लिखना और उनके प्रदर्शन का विश्लेषण करना जारी रखूंगा। मेरी योजनाओं में डेटा संरचनाओं में परमाणु संचालन का उपयोग करके चेनिंग, रॉबिन हुड हैशिंग और कुक्कू हैशिंग शामिल है जो जीपीयू के अनुकूल हैं।

स्रोत: www.habr.com