मी ते Github वर पोस्ट केले आहे नवीन प्रकल्प एक साधा GPU हॅश टेबल.

हे एक साधे GPU हॅश टेबल आहे जे प्रति सेकंद शेकडो लाखो इन्सर्टवर प्रक्रिया करण्यास सक्षम आहे. माझ्या NVIDIA GTX 1060 लॅपटॉपवर, कोड 64 दशलक्ष यादृच्छिकपणे व्युत्पन्न केलेल्या की-व्हॅल्यू जोड्या सुमारे 210 ms मध्ये घालतो आणि सुमारे 32 ms मध्ये 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() हॅश टेबलमधील जोड्यांच्या अॅरेसाठी साधा किंवा अस्थिर पॉइंटर वापरा. CUDA दस्तऐवजीकरण असे सांगते की:

कंपाइलर जागतिक किंवा सामायिक मेमरीमध्ये वाचन आणि लेखन ऑप्टिमाइझ करणे निवडू शकतो... हे ऑप्टिमायझेशन कीवर्ड वापरून अक्षम केले जाऊ शकतात volatile: ... या व्हेरिएबलचा कोणताही संदर्भ रिअल मेमरी रीड किंवा राइट इंस्ट्रक्शनमध्ये संकलित केला जातो.

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

उत्पादकता

64 दशलक्ष घटक घालण्यासाठी आणि त्यापैकी 32 दशलक्ष हटविण्याच्या चाचणीमध्ये, दरम्यान स्पर्धा std::unordered_map आणि GPU साठी अक्षरशः हॅश टेबल नाही:

std::unordered_map घटक घालण्यासाठी आणि काढून टाकण्यासाठी आणि नंतर त्यांना मुक्त करण्यासाठी 70 ms खर्च केले unordered_map (लाखो घटकांपासून मुक्त होण्यासाठी खूप वेळ लागतो, कारण आत unordered_map एकाधिक मेमरी वाटप केले जाते). प्रामाणिकपणे सांगायचे तर, std:unordered_map पूर्णपणे भिन्न निर्बंध. हा एकच CPU थ्रेड आहे, जो कोणत्याही आकाराच्या की-व्हॅल्यूला सपोर्ट करतो, उच्च वापर दरांवर चांगली कामगिरी करतो आणि एकाधिक हटवल्यानंतर स्थिर कामगिरी दाखवतो.

GPU आणि इंटर-प्रोग्राम कम्युनिकेशनसाठी हॅश टेबलचा कालावधी 984 ms होता. यात टेबल मेमरीमध्ये ठेवण्यात आणि हटवण्यात घालवलेला वेळ (एकदा 1 GB मेमरी वाटप करणे, ज्याला CUDA मध्ये थोडा वेळ लागतो), घटक घालणे आणि हटवणे आणि त्यावर पुनरावृत्ती करणे समाविष्ट आहे. व्हिडीओ कार्ड मेमरीमधील आणि त्यातील सर्व प्रती देखील विचारात घेतल्या जातात.

हॅश टेबलला पूर्ण होण्यासाठी 271 ms लागला. यामध्ये व्हिडिओ कार्डने घटक घालण्यात आणि हटवण्यात घालवलेला वेळ समाविष्ट आहे आणि मेमरीमध्ये कॉपी करण्यात आणि परिणामी टेबलवर पुनरावृत्ती करण्यात घालवलेला वेळ विचारात घेत नाही. जर GPU टेबल बराच काळ जगत असेल किंवा हॅश टेबल पूर्णपणे व्हिडिओ कार्डच्या मेमरीमध्ये समाविष्ट असेल (उदाहरणार्थ, हॅश टेबल तयार करण्यासाठी जे इतर GPU कोडद्वारे वापरले जाईल आणि सेंट्रल प्रोसेसरद्वारे नाही), तर चाचणी परिणाम संबंधित आहे.

व्हिडिओ कार्डसाठी हॅश टेबल उच्च थ्रूपुट आणि सक्रिय समांतरीकरणामुळे उच्च कार्यक्षमता दर्शवते.

उणीवा

हॅश टेबल आर्किटेक्चरमध्ये काही समस्या आहेत ज्यांची जाणीव असणे आवश्यक आहे:

• क्लस्टरिंगमुळे लीनियर प्रोबिंगला अडथळा येतो, ज्यामुळे टेबलमधील कळा अगदी कमी ठेवल्या जातात.
• फंक्शन वापरून की काढल्या जात नाहीत delete आणि कालांतराने ते टेबल गोंधळतात.

परिणामी, हॅश टेबलचे कार्यप्रदर्शन हळूहळू खराब होऊ शकते, विशेषत: जर ते बर्याच काळापासून अस्तित्वात असेल आणि त्यात असंख्य इन्सर्ट आणि डिलीट असतील. हे तोटे कमी करण्याचा एक मार्ग म्हणजे बर्‍यापैकी कमी वापर दरासह नवीन टेबलमध्ये पुन्हा हॅश करणे आणि रीहॅशिंग दरम्यान काढलेल्या की फिल्टर करणे.

वर्णन केलेल्या समस्यांचे वर्णन करण्यासाठी, मी 128 दशलक्ष घटकांसह एक टेबल तयार करण्यासाठी वरील कोड वापरेन आणि मी 4 दशलक्ष स्लॉट भरेपर्यंत 124 दशलक्ष घटकांमधून लूप करेन (सुमारे 0,96 चा वापर दर). येथे निकाल सारणी आहे, प्रत्येक पंक्ती एका हॅश टेबलमध्ये 4 दशलक्ष नवीन घटक घालण्यासाठी CUDA कर्नल कॉल आहे:

वापर दर
अंतर्भूत कालावधी 4 घटक

0,00
11,608448 ms (361,314798 दशलक्ष की/से.)

0,03
11,751424 ms (356,918799 दशलक्ष की/से.)

0,06
11,942592 ms (351,205515 दशलक्ष की/से.)

0,09
12,081120 ms (347,178429 दशलक्ष की/से.)

0,12
12,242560 ms (342,600233 दशलक्ष की/से.)

0,16
12,396448 ms (338,347235 दशलक्ष की/से.)

0,19
12,533024 ms (334,660176 दशलक्ष की/से.)

0,22
12,703328 ms (330,173626 दशलक्ष की/से.)

0,25
12,884512 ms (325,530693 दशलक्ष की/से.)

0,28
13,033472 ms (321,810182 दशलक्ष की/से.)

0,31
13,239296 ms (316,807174 दशलक्ष की/से.)

0,34
13,392448 ms (313,184256 दशलक्ष की/से.)

0,37
13,624000 ms (307,861434 दशलक्ष की/से.)

0,41
13,875520 ms (302,280855 दशलक्ष की/से.)

0,44
14,126528 ms (296,909756 दशलक्ष की/से.)

0,47
14,399328 ms (291,284699 दशलक्ष की/से.)

0,50
14,690304 ms (285,515123 दशलक्ष की/से.)

0,53
15,039136 ms (278,892623 दशलक्ष की/से.)

0,56
15,478656 ms (270,973402 दशलक्ष की/से.)

0,59
15,985664 ms (262,379092 दशलक्ष की/से.)

0,62
16,668673 ms (251,627968 दशलक्ष की/से.)

0,66
17,587200 ms (238,486174 दशलक्ष की/से.)

0,69
18,690048 ms (224,413765 दशलक्ष की/से.)

0,72
20,278816 ms (206,831789 दशलक्ष की/से.)

0,75
22,545408 ms (186,038058 दशलक्ष की/से.)

0,78
26,053312 ms (160,989275 दशलक्ष की/से.)

0,81
31,895008 ms (131,503463 दशलक्ष की/से.)

0,84
42,103294 ms (99,619378 दशलक्ष की/से.)

0,87
61,849056 ms (67,815164 दशलक्ष की/से.)

0,90
105,695999 ms (39,682713 दशलक्ष की/से.)

0,94
240,204636 ms (17,461378 दशलक्ष की/से.)

जसजसा वापर वाढतो तसतसे कार्यक्षमतेत घट होते. बहुतेक प्रकरणांमध्ये हे वांछनीय नाही. जर एखादा अनुप्रयोग टेबलमध्ये घटक समाविष्ट करतो आणि नंतर त्यांना टाकून देतो (उदाहरणार्थ, पुस्तकातील शब्द मोजताना), तर ही समस्या नाही. परंतु जर अनुप्रयोग दीर्घकाळ टिकणारे हॅश टेबल वापरत असेल (उदाहरणार्थ, चित्रांचे रिक्त नसलेले भाग संग्रहित करण्यासाठी ग्राफिक्स एडिटरमध्ये जेथे वापरकर्ता वारंवार माहिती घालतो आणि हटवतो), तर हे वर्तन समस्याप्रधान असू शकते.

आणि 64 दशलक्ष इन्सर्ट्स (उपयोग घटक 0,5) नंतर हॅश टेबल प्रोबिंग डेप्थ मोजली. सरासरी खोली 0,4774 होती, त्यामुळे बहुतेक की एकतर शक्य तितक्या सर्वोत्तम स्लॉटमध्ये होत्या किंवा सर्वोत्तम स्थानापासून एक स्लॉट दूर होत्या. कमाल आवाजाची खोली 60 होती.

मी नंतर 124 दशलक्ष इन्सर्ट्स (उपयोग घटक 0,97) असलेल्या टेबलवर प्रोबिंगची खोली मोजली. सरासरी खोली आधीच 10,1757 होती, आणि कमाल - 6474 (!!). उच्च वापर दरांवर लिनियर सेन्सिंग कार्यप्रदर्शन लक्षणीयरीत्या कमी होते.

या हॅश टेबलचा वापर दर कमी ठेवणे चांगले. परंतु नंतर आम्ही मेमरी वापराच्या खर्चावर कार्यप्रदर्शन वाढवतो. सुदैवाने, 32-बिट की आणि मूल्यांच्या बाबतीत, हे न्याय्य असू शकते. जर वरील उदाहरणामध्ये, 128 दशलक्ष घटक असलेल्या टेबलमध्ये, आपण 0,25 चा उपयोग घटक ठेवला, तर आपण त्यात 32 दशलक्ष घटकांपेक्षा जास्त ठेवू शकत नाही आणि उर्वरित 96 दशलक्ष स्लॉट गमावले जातील - प्रत्येक जोडीसाठी 8 बाइट्स , 768 MB गमावलेली मेमरी.

कृपया लक्षात घ्या की आम्ही व्हिडिओ कार्ड मेमरी गमावण्याबद्दल बोलत आहोत, जे सिस्टम मेमरीपेक्षा अधिक मौल्यवान संसाधन आहे. जरी CUDA चे समर्थन करणार्‍या बहुतेक आधुनिक डेस्कटॉप ग्राफिक्स कार्ड्समध्ये किमान 4 GB मेमरी असते (लेखनाच्या वेळी, NVIDIA 2080 Ti मध्ये 11 GB असते), तरीही अशा प्रमाणात गमावणे हा सर्वात शहाणा निर्णय ठरणार नाही.

नंतर मी व्हिडिओ कार्ड्ससाठी हॅश टेबल्स तयार करण्याबद्दल अधिक लिहीन ज्यांना प्रोबिंग डेप्थमध्ये समस्या येत नाहीत, तसेच हटविलेले स्लॉट पुन्हा वापरण्याचे मार्ग.

ध्वनी खोली मोजमाप

कीची प्रोबिंग डेप्थ निश्चित करण्यासाठी, आम्ही त्याच्या वास्तविक टेबल इंडेक्समधून कीचा हॅश (त्याचा आदर्श टेबल इंडेक्स) काढू शकतो:

// 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 च्या समतुल्य आहे.

निष्कर्ष

आपल्याकडे प्रश्न किंवा टिप्पण्या असल्यास, कृपया मला येथे ईमेल करा Twitter किंवा मध्ये एक नवीन विषय उघडा भांडार.

हा कोड उत्कृष्ट लेखांच्या प्रेरणेने लिहिलेला आहे:

• जगातील सर्वात सोपी लॉक-फ्री हॅश टेबल
• लॉक-मुक्त प्रतीक्षा-मुक्त हॅश टेबल

भविष्यात, मी व्हिडिओ कार्डसाठी हॅश टेबल अंमलबजावणीबद्दल लिहित राहीन आणि त्यांच्या कार्यप्रदर्शनाचे विश्लेषण करेन. माझ्या योजनांमध्ये GPU अनुकूल असलेल्या डेटा स्ट्रक्चर्समध्ये अणू ऑपरेशन्स वापरून चेनिंग, रॉबिन हूड हॅशिंग आणि कुकू हॅशिंग यांचा समावेश आहे.

स्त्रोत: www.habr.com