ما دا په ګیتوب کې پوسټ کړ نوې پروژه یو ساده GPU هش میز.

دا یو ساده GPU هش میز دی چې په هره ثانیه کې د سلګونو ملیون داخلونو پروسس کولو توان لري. زما په NVIDIA GTX 1060 لپ ټاپ کې، کوډ په 64 ms کې په تصادفي ډول د 210 ملیون تصادفي تولید شوي کلیدي ارزښت جوړه داخلوي او شاوخوا 32 ms کې 64 ملیون جوړه لرې کوي.

دا دی، په لپ ټاپ کې سرعت نږدې 300 ملیون داخلونه / ثانیه او 500 ملیون حذف / ثانیه ده.

جدول په CUDA کې لیکل شوی، که څه هم ورته تخنیک په HLSL یا GLSL کې پلي کیدی شي. په ویډیو کارت کې د لوړ فعالیت ډاډ ترلاسه کولو لپاره پلي کول ډیری محدودیتونه لري:

یوازې 32-bit کیلي او ورته ارزښتونه پروسس کیږي.
د هش میز یو ثابت اندازه لري.
او دا اندازه باید د بریښنا دوه سره مساوي وي.

د کلیدونو او ارزښتونو لپاره، تاسو اړتیا لرئ یو ساده ډیلیمیټر مارکر وساتئ (په پورتني کوډ کې دا 0xffffffff دی).

د هش میز پرته له تالاشۍ

د هش جدول د خلاص پتې سره کاروي خطي پلټنه، دا په ساده ډول د کلیدي ارزښت جوړو لړۍ ده چې په حافظه کې زیرمه شوې او د کیچ غوره فعالیت لري. ورته د زنځیر کولو لپاره نشي ویل کیدی ، کوم چې په لینک شوي لیست کې د پوائنټر لټون کول شامل دي. د هش میز د عناصرو ذخیره کولو ساده صف دی KeyValue:

struct KeyValue
{
    uint32_t key;
    uint32_t value;
};

د میز اندازه د دوه ځواک څخه ده، نه د اصلي شمیره، ځکه چې یو ګړندی لارښوونه د pow2/AND ماسک پلي کولو لپاره کافي ده، مګر د موډول آپریټر خورا ورو دی. دا د خطي تحقیقاتو په حالت کې مهم دی، ځکه چې د لینر جدول په لټه کې د سلاټ شاخص باید په هر سلاټ کې وتړل شي. او د پایلې په توګه، د عملیاتو لګښت په هر سلاټ کې ماډلو اضافه کیږي.

جدول یوازې د هر عنصر لپاره کیلي او ارزښت ذخیره کوي ، نه د کیلي هش. څرنګه چې میز یوازې 32-bit کیلي ذخیره کوي، هش په چټکۍ سره محاسبه کیږي. پورته کوډ د Murmur3 هش کاروي، کوم چې یوازې یو څو بدلونونه، XORs او ضربونه ترسره کوي.

د هش میز د تالاشۍ محافظت تخنیکونه کاروي چې د حافظې له ترتیب څخه خپلواک دي. حتی که د لیکلو ځینې عملیات د نورو ورته عملیاتو ترتیب ګډوډ کړي ، د هش میز به لاهم سم حالت وساتي. موږ به لاندې په دې اړه خبرې وکړو. تخنیک د ویډیو کارتونو سره عالي کار کوي چې په ورته وخت کې زرګونه تارونه چلوي.

په هش جدول کې کیلي او ارزښتونه د خالي کولو لپاره پیل شوي.

کوډ د 64-bit کلیدونو او ارزښتونو هم سمبالولو لپاره تعدیل کیدی شي. کیلي د اټومي لوستلو، لیکلو، او پرتله کولو او بدلولو عملیاتو ته اړتیا لري. او ارزښتونه د اټومي لوستلو او لیکلو عملیاتو ته اړتیا لري. په خوشبختۍ سره، په CUDA کې، د 32- او 64-bit ارزښتونو لپاره د لوستلو لیکلو عملیات اټومي دي تر هغه چې دوی په طبیعي توګه سره سمون ولري (لاندې وګورئ). دلته)، او عصري ویډیو کارتونه د 64-bit اټومي پرتله کولو او تبادلې عملیاتو ملاتړ کوي. البته، کله چې 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 په اړه د کارولو کچه). دلته د پایلې جدول دی، هر قطار د CUDA کرنل کال دی چې په یوه هش میز کې 4 ملیون نوي عناصر داخلوي:

د کارونې کچه
د ننوتلو موده 4 عناصر

0,00
11,608448 ms (361,314798 ملیون کیلي/sec.)

0,03
11,751424 ms (356,918799 ملیون کیلي/sec.)

0,06
11,942592 ms (351,205515 ملیون کیلي/sec.)

0,09
12,081120 ms (347,178429 ملیون کیلي/sec.)

0,12
12,242560 ms (342,600233 ملیون کیلي/sec.)

0,16
12,396448 ms (338,347235 ملیون کیلي/sec.)

0,19
12,533024 ms (334,660176 ملیون کیلي/sec.)

0,22
12,703328 ms (330,173626 ملیون کیلي/sec.)

0,25
12,884512 ms (325,530693 ملیون کیلي/sec.)

0,28
13,033472 ms (321,810182 ملیون کیلي/sec.)

0,31
13,239296 ms (316,807174 ملیون کیلي/sec.)

0,34
13,392448 ms (313,184256 ملیون کیلي/sec.)

0,37
13,624000 ms (307,861434 ملیون کیلي/sec.)

0,41
13,875520 ms (302,280855 ملیون کیلي/sec.)

0,44
14,126528 ms (296,909756 ملیون کیلي/sec.)

0,47
14,399328 ms (291,284699 ملیون کیلي/sec.)

0,50
14,690304 ms (285,515123 ملیون کیلي/sec.)

0,53
15,039136 ms (278,892623 ملیون کیلي/sec.)

0,56
15,478656 ms (270,973402 ملیون کیلي/sec.)

0,59
15,985664 ms (262,379092 ملیون کیلي/sec.)

0,62
16,668673 ms (251,627968 ملیون کیلي/sec.)

0,66
17,587200 ms (238,486174 ملیون کیلي/sec.)

0,69
18,690048 ms (224,413765 ملیون کیلي/sec.)

0,72
20,278816 ms (206,831789 ملیون کیلي/sec.)

0,75
22,545408 ms (186,038058 ملیون کیلي/sec.)

0,78
26,053312 ms (160,989275 ملیون کیلي/sec.)

0,81
31,895008 ms (131,503463 ملیون کیلي/sec.)

0,84
42,103294 ms (99,619378 ملیون کیلي/sec.)

0,87
61,849056 ms (67,815164 ملیون کیلي/sec.)

0,90
105,695999 ms (39,682713 ملیون کیلي/sec.)

0,94
240,204636 ms (17,461378 ملیون کیلي/sec.)

لکه څنګه چې کارول زیاتیږي، فعالیت کمیږي. دا په ډیرو مواردو کې د منلو وړ نه ده. که یو غوښتنلیک په میز کې عناصر داخل کړي او بیا یې رد کړي (د مثال په توګه، کله چې په کتاب کې ټکي شمیرل کیږي)، نو دا کومه ستونزه نده. مګر که غوښتنلیک د اوږد مهاله هش میز کاروي (د مثال په توګه، د ګرافیک مدیر کې د انځورونو غیر خالي برخې ذخیره کولو لپاره چیرې چې کاروونکي په مکرر ډول معلومات داخلوي او حذف کوي)، نو دا چلند ستونزمن کیدی شي.

او د 64 ملیون داخلونو وروسته د هش میز د تحقیقاتو ژوروالی اندازه کړ (د کارونې فکتور 0,5). منځنۍ ژوره 0,4774 وه، نو ډیری کیلي یا په غوره ممکنه سلاټ کې وې یا د غوره موقعیت څخه یو سلاټ لرې. د لوړ غږ ژوره 60 وه.

بیا ما په میز کې د 124 ملیون داخلونو سره د تحقیقاتو ژوروالی اندازه کړ (د کارولو فکتور 0,97). منځنۍ ژوره لا دمخه 10,1757 وه، او اعظمي - 6474 (!!). د لینر سینس کولو فعالیت د لوړې کارولو نرخونو کې د پام وړ راټیټیږي.

دا غوره ده چې د دې هش میز د کارولو کچه ټیټ وساتئ. مګر بیا موږ د حافظې مصرف په لګښت فعالیت ډیروو. خوشبختانه ، د 32-bit کلیدونو او ارزښتونو په حالت کې ، دا توجیه کیدی شي. که په پورتنۍ بېلګه کې، د 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 لپاره ساده هش میز