میں نے اسے Github پر پوسٹ کیا۔ نیا پروجیکٹ ایک سادہ جی پی یو ہیش ٹیبل.

یہ ایک سادہ جی پی یو ہیش ٹیبل ہے جو فی سیکنڈ لاکھوں انسرٹس پر کارروائی کرنے کی صلاحیت رکھتا ہے۔ میرے NVIDIA GTX 1060 لیپ ٹاپ پر، کوڈ تقریباً 64 ms میں 210 ملین تصادفی طور پر تیار کردہ کلیدی قدر کے جوڑے داخل کرتا ہے اور تقریباً 32 ms میں 64 ملین جوڑوں کو ہٹا دیتا ہے۔

یعنی لیپ ٹاپ پر رفتار تقریباً 300 ملین انسرٹس/سیکنڈ اور 500 ملین ڈیلیٹ/سیکنڈ ہے۔

جدول CUDA میں لکھا گیا ہے، حالانکہ اسی تکنیک کو HLSL یا GLSL پر لاگو کیا جا سکتا ہے۔ ویڈیو کارڈ پر اعلی کارکردگی کو یقینی بنانے کے لیے عمل درآمد میں کئی حدود ہیں:

صرف 32 بٹ کیز اور اسی قدروں پر کارروائی کی جاتی ہے۔
ہیش ٹیبل کا ایک مقررہ سائز ہے۔
اور یہ سائز دو طاقت کے برابر ہونا چاہیے۔

کلیدوں اور اقدار کے لیے، آپ کو ایک سادہ ڈیلیمیٹر مارکر محفوظ کرنے کی ضرورت ہے (اوپر والے کوڈ میں یہ 0xffffffff ہے)۔

تالے کے بغیر ہیش ٹیبل

ہیش ٹیبل اوپن ایڈریسنگ کے ساتھ استعمال کرتا ہے۔ لکیری تحقیقات، یعنی، یہ صرف کلیدی قدر کے جوڑوں کی ایک صف ہے جو میموری میں محفوظ ہوتی ہے اور کیشے کی کارکردگی بہتر ہوتی ہے۔ زنجیر بندی کے لیے بھی ایسا نہیں کہا جا سکتا، جس میں منسلک فہرست میں پوائنٹر کی تلاش شامل ہے۔ ایک ہیش ٹیبل ایک سادہ صف ذخیرہ کرنے والے عناصر ہے۔ KeyValue:

struct KeyValue
{
    uint32_t key;
    uint32_t value;
};

ٹیبل کا سائز دو کی طاقت ہے، پرائم نمبر نہیں، کیونکہ pow2/AND ماسک لگانے کے لیے ایک تیز ہدایات کی ضرورت ہوتی ہے، لیکن ماڈیولس آپریٹر بہت سست ہے۔ یہ لکیری پروبنگ کے معاملے میں اہم ہے، کیونکہ لکیری ٹیبل تلاش میں سلاٹ انڈیکس کو ہر سلاٹ میں لپیٹنا ضروری ہے۔ اور اس کے نتیجے میں، آپریشن کی لاگت ہر سلاٹ میں ماڈیولو شامل کی جاتی ہے۔

ٹیبل ہر عنصر کے لیے صرف کلید اور قدر کو ذخیرہ کرتا ہے، کلید کا ہیش نہیں۔ چونکہ ٹیبل صرف 32 بٹ کیز کو اسٹور کرتا ہے، اس لیے ہیش کا حساب بہت جلد کیا جاتا ہے۔ اوپر کا کوڈ Murmur3 ہیش کا استعمال کرتا ہے، جو صرف چند شفٹوں، XORs اور ضربوں کو انجام دیتا ہے۔

ہیش ٹیبل لاکنگ پروٹیکشن تکنیک استعمال کرتا ہے جو میموری آرڈر سے آزاد ہیں۔ یہاں تک کہ اگر کچھ تحریری کارروائیاں اس طرح کی دیگر کارروائیوں کی ترتیب میں خلل ڈالتی ہیں، تب بھی ہیش ٹیبل صحیح حالت کو برقرار رکھے گا۔ ہم ذیل میں اس کے بارے میں بات کریں گے۔ یہ تکنیک ویڈیو کارڈز کے ساتھ بہترین کام کرتی ہے جو بیک وقت ہزاروں تھریڈز چلاتے ہیں۔

ہیش ٹیبل میں کیز اور ویلیوز کو خالی کرنے کے لیے شروع کیا جاتا ہے۔

کوڈ کو 64 بٹ کیز اور اقدار کو بھی سنبھالنے کے لیے تبدیل کیا جا سکتا ہے۔ کلیدوں کو ایٹم پڑھنے، لکھنے، اور موازنہ اور تبادلہ کی کارروائیوں کی ضرورت ہوتی ہے۔ اور اقدار کو ایٹم ریڈ اینڈ رائٹ آپریشنز کی ضرورت ہوتی ہے۔ خوش قسمتی سے، CUDA میں، 32- اور 64-bit اقدار کے لیے پڑھنے لکھنے کی کارروائیاں ایٹم ہیں جب تک کہ وہ قدرتی طور پر منسلک ہوں (نیچے دیکھیں)۔ یہاں)، اور جدید ویڈیو کارڈز 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 ملین حذف/sec سے کم ہو کر 450 ملین حذف/sec ہو گئی۔

کارکردگی

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 ایم ایس لگے۔ اس میں ویڈیو کارڈ کے عناصر کو داخل کرنے اور حذف کرنے میں صرف کیا گیا وقت شامل ہے، اور میموری میں کاپی کرنے اور نتیجے میں آنے والے ٹیبل پر تکرار کرنے میں صرف کیے گئے وقت کو مدنظر نہیں رکھا جاتا ہے۔ اگر 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 کے برابر ہے۔

حاصل يہ ہوا

اگر آپ کے سوالات یا تبصرے ہیں، تو براہ کرم مجھے ای میل کریں۔ ٹویٹر یا میں ایک نیا موضوع کھولیں۔ ذخیرے.

یہ کوڈ بہترین مضامین سے متاثر ہوکر لکھا گیا تھا:

مستقبل میں، میں ویڈیو کارڈز کے لیے ہیش ٹیبل کے نفاذ کے بارے میں لکھتا رہوں گا اور ان کی کارکردگی کا تجزیہ کروں گا۔ میرے منصوبوں میں چیننگ، رابن ہڈ ہیشنگ، اور ڈیٹا ڈھانچے میں جوہری آپریشنز کا استعمال کرتے ہوئے کوکو ہیشنگ شامل ہیں جو GPU دوستانہ ہیں۔

ماخذ: www.habr.com

GPU کے لیے سادہ ہیش ٹیبل