Ngiyithumele ku-Github .
Ithebula le-GPU elilula elikwazi ukucubungula amakhulu ezigidi zokufakwa ngomzuzwana. Kukhompyutha yami ephathekayo ye-NVIDIA GTX 1060, ikhodi ifaka amapheya enani angukhiye akhiqizwa ngokungahleliwe ayizigidi ezingu-64 cishe ngo-210 ms futhi ikhipha amapheya ayizigidi ezingu-32 cishe ngama-64 ms.
Okusho ukuthi, ijubane kukhompuyutha ephathekayo lilinganiselwa ezigidini ezingu-300 zokufakwa/ngesekhondi kanye nezigidi ezingu-500 zokususwa/ngesekhondi.
Ithebula libhalwe nge-CUDA, nakuba indlela efanayo ingasetshenziswa ku-HLSL noma i-GLSL. Ukuqaliswa kunemikhawulo eminingana yokuqinisekisa ukusebenza okuphezulu ekhadini levidiyo:
- Okhiye abangu-32-bit kuphela namanani afanayo ayacutshungulwa.
- Ithebula le-hashi linosayizi ongashintshi.
- Futhi lobu bukhulu kufanele bulingane nokubili kwamandla.
Ukuze uthole okhiye namanani, udinga ukubekisa umaka we-delimiter olula (kukhodi engenhla lokhu ngu-0xffffffff).
Itafula le-Hash elingenazo izingidi
Ithebula le-hashi lisebenzisa ikheli elivuliwe nge , okusho ukuthi, imane nje iwuxhaxha lwamapheya enani elingukhiye agcinwa kumemori futhi anokusebenza kwenqolobane okuphezulu. Okufanayo akunakushiwo ngokubopha ngamaketango, okubandakanya ukucinga i-pointer ohlwini oluxhunyiwe. Ithebula le-hashi liwuhlelo olulula lokugcina izakhi KeyValue:
struct KeyValue
{
uint32_t key;
uint32_t value;
};
Usayizi wethebula ungamandla amabili, hhayi inombolo eyinhloko, ngoba umyalelo owodwa osheshayo wanele ukusebenzisa imaski ye-pow2/AND, kodwa u-opharetha we-modulus uhamba kancane kakhulu. Lokhu kubalulekile esimweni sokuphenya ngomugqa, njengoba ekubhekeni kwetafula ngomugqa inkomba yesikhala kufanele isongwe endaweni ngayinye. Futhi ngenxa yalokho, izindleko zokusebenza zengezwa i-modulo ku-slot ngayinye.
Ithebula ligcina kuphela ukhiye kanye nenani le-elementi ngayinye, hhayi i-hashi yokhiye. Njengoba ithebula ligcina okhiye abangu-32-bit kuphela, i-hashi ibalwa ngokushesha okukhulu. Ikhodi engenhla isebenzisa i-Murmur3 hash, eyenza amashifu ambalwa kuphela, ama-XOR kanye nokuphindaphinda.
Ithebula le-hashi lisebenzisa izindlela zokuvikela ukukhiya ezizimele ohlelweni lwememori. Ngisho noma eminye imisebenzi yokubhala iphazamisa ukuhleleka kweminye imisebenzi enjalo, ithebula le-hashi lisazogcina isimo esilungile. Sizokhuluma ngalokhu ngezansi. Indlela yokusebenza isebenza kahle ngamakhadi evidiyo asebenzisa izinkulungwane zemicu kanye kanye.
Okhiye namanani kuthebula le-hashi aqalwa ukuze angabi nalutho.
Ikhodi ingashintshwa ukuze isingathe okhiye be-64-bit kanye namanani. Okhiye badinga ukufunda, ukubhala, nokuqhathanisa nokushintshanisa imisebenzi ye-athomu. Futhi amanani adinga imisebenzi yokufunda nokubhala ye-athomu. Ngenhlanhla, ku-CUDA, imisebenzi yokufunda-bhala yamanani angama-32- kanye nama-64-bit i-athomu inqobo nje uma iqondaniswe ngokwemvelo (bona ngezansi). ), namakhadi evidiyo esimanje asekela ukusebenza kokuqhathanisa nokushintshana kwe-athomu engu-64-bit. Yiqiniso, lapho uthuthela kumabhithi angu-64, ukusebenza kuzokwehla kancane.
Isimo sethebula le-hash
Ipheya ngalinye lenani elingukhiye kuthebula le-hashi lingaba nesifunda esisodwa kwezine:
- Ukhiye nevelu akunalutho. Kulesi simo, ithebula le-hashi liyaqaliswa.
- Ukhiye ubhaliwe phansi, kodwa inani alikakabhalwa phansi. Uma olunye uchungechunge lufunda idatha okwamanje, lubuya lungenalutho. Lokhu kuvamile, bekuzokwenzeka into efanayo ukube olunye uchungechunge lokubulawa belusebenze ngaphambidlana, futhi sikhuluma ngesakhiwo sedatha ngesikhathi esisodwa.
- Kokubili ukhiye kanye nenani kuyarekhodwa.
- Inani liyatholakala kolunye uchungechunge lokusetshenziswa, kodwa ukhiye awukakafiki. Lokhu kungenzeka ngoba imodeli yokuhlela ye-CUDA inemodeli yenkumbulo ehlelwe ngokukhululekile. Lokhu kuvamile; kunoma yikuphi, ukhiye awusenalutho, ngisho noma inani lingasekho.
I-nuance ebalulekile ukuthi uma ukhiye usubhaliwe ku-slot, awusanyakazi - ngisho noma ukhiye ususiwe, sizokhuluma ngalokhu ngezansi.
Ikhodi yethebula le-hashi isebenza ngisho namamodeli enkumbulo ahlelwe ngokukhululekile lapho inkumbulo efundwa futhi ibhalwe ngayo ingaziwa. Njengoba sibheka ukufakwa, ukubheka, kanye nokususwa kuthebula le-hashi, khumbula ukuthi ipheya ngayinye yenani lokhiye ikwesinye sezimo ezine ezichazwe ngenhla.
Ukufaka kuthebula le-hashi
Umsebenzi we-CUDA ofaka amapheya enani elingukhiye kuthebula le-hashi ubukeka kanje:
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);
}
}
Ukuze ufake ukhiye, ikhodi iphindaphinda kuhlu lwethebula le-hashi eqala ngo-hashi wokhiye ofakiwe. Imbobo ngayinye ohlwini yenza umsebenzi wokuqhathanisa nokushintshanisa kwe-athomu oqhathanisa ukhiye kuleso sikhala nokungenalutho. Uma kutholwa ukungafani, ukhiye esikhaleni uyabuyekezwa ngokhiye ofakiwe, bese kubuyiselwa ukhiye we-slot wasekuqaleni. Uma lo khiye wangempela ubungenalutho noma ufane nokhiye ofakiwe, ikhodi izobe ithola indawo efanelekile ukuze ishutheke bese ifaka inani elifakiwe esikhaleni.
Uma ku-kernel eyodwa ikholi gpu_hashtable_insert() kunezinto eziningi ezinokhiye ofanayo, khona-ke noma imaphi amanani azo angabhalwa ku-slot yokhiye. Lokhu kuthathwa njengokujwayelekile: enye ye-key-value ebhala ngesikhathi socingo izophumelela, kodwa njengoba konke lokhu kwenzeka ngokufana phakathi kwemicu eminingana yokubulawa, asikwazi ukubikezela ukuthi iyiphi inkumbulo ebhalayo ezoba ngeyokugcina.
Ukubheka ithebula le-hash
Ikhodi yokhiye bokusesha:
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);
}
}
Ukuthola inani lokhiye ogcinwe kuthebula, siphindaphinda kuhlu oluqala nge-hashi yokhiye esiwufunayo. Esikhaleni ngasinye, sibheka ukuthi ukhiye yiwona yini esiwufunayo, futhi uma kunjalo, sibuyisela inani lawo. Siphinde sihlole ukuthi ukhiye awunalutho yini, futhi uma kunjalo, sihoxisa ukusesha.
Uma singakwazi ukuthola ukhiye, ikhodi ibuyisela inani elingenalutho.
Yonke le misebenzi yosesho ingenziwa kanyekanye ngokufaka nokususa. Ipheya ngalinye etafuleni lizoba nesinye sezimo ezine ezichazwe ngenhla ngokugeleza.
Isusa kuthebula le-hashi
Ikhodi yokususa okhiye:
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);
}
}
Ukususa ukhiye kwenziwa ngendlela engavamile: sishiya ukhiye etafuleni bese simaka inani laso (hhayi ukhiye ngokwalo) njengento engenalutho. Le khodi ifana kakhulu ne lookup(), ngaphandle kokuthi uma okufanayo kutholakala kukhiye, kwenza inani lakhona lingabi nalutho.
Njengoba kushiwo ngenhla, uma ukhiye usubhalwe endaweni, awusanyakazi. Ngisho noma i-elementi isusiwe etafuleni, ukhiye uhlala usendaweni, inani layo livele lingabi nalutho. Lokhu kusho ukuthi asikho isidingo sokusebenzisa umsebenzi wokubhala kwe-athomu yenani lesikhala, ngoba akunandaba ukuthi inani lamanje alinalutho noma cha - lisazophela.
Ishintsha usayizi wethebula le-hash
Ungashintsha usayizi wethebula le-hashi ngokwakha ithebula elikhudlwana futhi ufake izinto ezingenalutho kusuka kuthebula elidala kulo. Angizange ngisebenzise lokhu kusebenza ngoba bengifuna ukugcina ikhodi yesampula ilula. Ngaphezu kwalokho, ezinhlelweni ze-CUDA, ukwabiwa kwenkumbulo kuvame ukwenziwa kukhodi yokusingatha esikhundleni se-CUDA kernel.
Esihlokweni ichaza ukuthi ungashintsha kanjani uhlaka lwedatha oluvikelwe.
Ukuncintisana
Kumazwibela ekhodi yokusebenza angenhla gpu_hashtable_insert(), _lookup() ΠΈ _delete() cubungula ipheya yenani elingukhiye elilodwa ngesikhathi. Futhi ngaphansi gpu_hashtable_insert(), _lookup() ΠΈ _delete() cubungula uhlu lwamapheya ngokuhambisana, ipheya ngalinye kuchungechunge oluhlukile lokuqalisa lwe-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);
}
}
Ithebula le-hashi elingavimbeki ukukhiya lisekela ukufaka kanyekanye, ukubheka, nokususwa. Ngenxa yokuthi amapheya enani elingukhiye ahlala esendaweni eyodwa kwezine futhi okhiye abanyakazi, ithebula liqinisekisa ukunemba ngisho noma izinhlobo ezahlukene zokusebenza zisetshenziswa ngesikhathi esisodwa.
Nokho, uma sicubungula iqoqo lokufaka nokususa ngokuhambisanayo, futhi uma uhlu lokokufaka lokupheya luqukethe okhiye abayizimpinda, lapho-ke ngeke sikwazi ukubikezela ukuthi yimaphi amapheya βazowinaββazobhalwa kuthebula le-hashi ekugcineni. Ake sithi sibize ikhodi yokufaka ngohlu lokufaka lwamapheya A/0 B/1 A/2 C/3 A/4. Uma ikhodi iqeda, amabhangqa B/1 ΠΈ C/3 aqinisekisiwe ukuthi azoba khona etafuleni, kodwa ngesikhathi esifanayo noma yimaphi amapheya azovela kulo A/0, A/2 noma A/4. Lokhu kungase kube inkinga noma kungabi yinkinga - konke kuncike kuhlelo lokusebenza. Ungase wazi kusengaphambili ukuthi abekho okhiye abayizimpinda ohlwini lokokufaka, noma ungase ungabi nandaba ukuthi yiliphi inani eligcine ukubhalwa.
Uma lokhu kuyinkinga kuwe, kuzomele uhlukanise amapheya ayimpinda ube amakholi wesistimu we-CUDA ahlukene. Ku-CUDA, noma yikuphi ukusebenza okubiza i-kernel kuhlala kuqeda ngaphambi kocingo olulandelayo lwe-kernel (okungenani phakathi kwentambo eyodwa. Emicu ehlukene, ama-kernel asetshenziswa ngokuhambisana). Esibonelweni esingenhla, uma ubiza i-kernel eyodwa nge A/0 B/1 A/2 C/3, nomunye nge A/4, bese kuba ukhiye A uzothola inani 4.
Manje ake sikhulume ngokuthi kufanele yini imisebenzi lookup() ΠΈ delete() sebenzisa isikhombi esingenalutho noma esiguquguqukayo kuhlu lwamapheya kuthebula le-hashi. Isho ukuthi:
Umhlanganisi angase akhethe ukuthuthukisa ukufundwa nokubhala kumemori yomhlaba wonke noma eyabiwe... Lokhu kulungiselelwa kungakhutshazwa kusetshenziswa igama elingukhiye.
volatile: ... noma iyiphi ireferensi yalokhu okuguquguqukayo ihlanganiswa ibe yinkumbulo yangempela efundwayo noma ebhaliwe.
Ukucatshangelwa kokulunga akudingi isicelo volatile. Uma uchungechunge lokusayinda lusebenzisa inani elifakwe kunqolobane kusukela ekusebenzeni okufundwe ngaphambilini, kuzobe kusetshenziswa ulwazi oluphelelwe isikhathi kancane. Kodwa noma kunjalo, lolu ulwazi oluvela esimweni esifanele setafula le-hashi ngesikhathi esithile socingo lwe-kernel. Uma udinga ukusebenzisa ukwaziswa kwamuva, ungasebenzisa inkomba volatile, kodwa ukusebenza kuzokwehla kancane: ngokuvumelana nokuhlolwa kwami, lapho kususwa izici eziyizigidi ezingu-32, isivinini sehle sisuka ku-500 million ukususwa/isekhondi kuya ku-450 million ukususwa/isekhondi.
Ukukhiqiza
Esivivinyweni sokufaka ama-elementi ayizigidi ezingu-64 nokususa izigidi ezingu-32 zazo, ukuncintisana phakathi std::unordered_map futhi cishe alikho ithebula le-hash le-GPU:
std::unordered_map ichithe u-70 ms ifaka futhi ikhipha izinto bese iyazikhulula unordered_map (ukususa izigidi zezinto kuthatha isikhathi esiningi, ngoba ngaphakathi unordered_map kwenziwa ukwabiwa kwememori eminingi). Uma sikhuluma iqiniso, std:unordered_map imikhawulo ehluke ngokuphelele. Iwuchungechunge olulodwa lwe-CPU, isekela amanani abalulekile anoma yimuphi usayizi, isebenza kahle ngamazinga aphezulu okusetshenziswa, futhi ikhombisa ukusebenza okuzinzile ngemuva kokususwa okuningi.
Ubude besikhathi sethebula le-hashi le-GPU nokuxhumana phakathi kwezinhlelo bekungu-984 ms. Lokhu kufaka phakathi isikhathi esichithwe kubekwa ithebula enkumbulweni nokuyisusa (ukwaba inkumbulo engu-1 GB ngesikhathi esisodwa, okuthatha isikhathi ku-CUDA), ukufaka nokususa izakhi, nokuphindaphinda phezu kwazo. Wonke amakhophi aya noma asuka kwimemori yekhadi levidiyo nawo ayacatshangelwa.
Ithebula le-hashi ngokwalo lithathe 271 ms ukuqeda. Lokhu kufaka phakathi isikhathi esichithwa ikhadi levidiyo lifaka futhi lisusa izinto, futhi akunaki isikhathi esichithwe ukukopisha kumemori nokuphindaphinda phezu kwethebula eliwumphumela. Uma ithebula le-GPU liphila isikhathi eside, noma uma ithebula le-hashi liqukethwe ngokuphelele kumemori yekhadi levidiyo (isibonelo, ukwakha ithebula le-hashi elizosetshenziswa enye ikhodi ye-GPU hhayi iphrosesa emaphakathi), khona-ke umphumela wokuhlolwa ufanelekile.
Ithebula le-hashi lekhadi levidiyo libonisa ukusebenza okuphezulu ngenxa yokuphuma okuphezulu nokuhambisana okusebenzayo.
amaphutha
Ukwakhiwa kwetafula le-hash kunezinkinga ezimbalwa okufanele wazi:
- Ukuhlola ngomugqa kuthikazwa ukuhlanganisa, okwenza okhiye kuthebula babekwe ngaphansi kokuphelele.
- Okhiye abasuswa kusetshenziswa umsebenzi
deletefuthi ngokuhamba kwesikhathi bahlanganisa itafula.
Ngenxa yalokho, ukusebenza kwethebula le-hashi kungalulaza kancane kancane, ikakhulukazi uma likhona isikhathi eside futhi linokufaka nokususa okuningi. Enye indlela yokunciphisa lobu bubi iwukuba kabusha kuthebula elisha elinenani eliphansi lokusetshenziswa nokuhlunga okhiye abakhishiwe phakathi nokushintsha kabusha.
Ukukhombisa izinkinga ezichaziwe, ngizosebenzisa ikhodi engenhla ukuze ngidale ithebula elinezinto eziyizigidi ezingu-128 futhi ngivule ama-elementi ayizigidi ezingu-4 ngize ngigcwalise izikhala eziyizigidi ezingu-124 (izinga lokusetshenziswa cishe elingu-0,96). Nali ithebula lemiphumela, umugqa ngamunye wucingo lwe-CUDA ukuze kufakwe izinto ezintsha eziyizigidi ezi-4 etafuleni elilodwa le-hashi:
Izinga lokusebenzisa
Ubude besikhathi sokufakwa 4 izici
0,00
11,608448 ms (361,314798 million okhiye/isekhondi.)
0,03
11,751424 ms (356,918799 million okhiye/isekhondi.)
0,06
11,942592 ms (351,205515 million okhiye/isekhondi.)
0,09
12,081120 ms (347,178429 million okhiye/isekhondi.)
0,12
12,242560 ms (342,600233 million okhiye/isekhondi.)
0,16
12,396448 ms (338,347235 million okhiye/isekhondi.)
0,19
12,533024 ms (334,660176 million okhiye/isekhondi.)
0,22
12,703328 ms (330,173626 million okhiye/isekhondi.)
0,25
12,884512 ms (325,530693 million okhiye/isekhondi.)
0,28
13,033472 ms (321,810182 million okhiye/isekhondi.)
0,31
13,239296 ms (316,807174 million okhiye/isekhondi.)
0,34
13,392448 ms (313,184256 million okhiye/isekhondi.)
0,37
13,624000 ms (307,861434 million okhiye/isekhondi.)
0,41
13,875520 ms (302,280855 million okhiye/isekhondi.)
0,44
14,126528 ms (296,909756 million okhiye/isekhondi.)
0,47
14,399328 ms (291,284699 million okhiye/isekhondi.)
0,50
14,690304 ms (285,515123 million okhiye/isekhondi.)
0,53
15,039136 ms (278,892623 million okhiye/isekhondi.)
0,56
15,478656 ms (270,973402 million okhiye/isekhondi.)
0,59
15,985664 ms (262,379092 million okhiye/isekhondi.)
0,62
16,668673 ms (251,627968 million okhiye/isekhondi.)
0,66
17,587200 ms (238,486174 million okhiye/isekhondi.)
0,69
18,690048 ms (224,413765 million okhiye/isekhondi.)
0,72
20,278816 ms (206,831789 million okhiye/isekhondi.)
0,75
22,545408 ms (186,038058 million okhiye/isekhondi.)
0,78
26,053312 ms (160,989275 million okhiye/isekhondi.)
0,81
31,895008 ms (131,503463 million okhiye/isekhondi.)
0,84
42,103294 ms (99,619378 million okhiye/isekhondi.)
0,87
61,849056 ms (67,815164 million okhiye/isekhondi.)
0,90
105,695999 ms (39,682713 million okhiye/isekhondi.)
0,94
240,204636 ms (17,461378 million okhiye/isekhondi.)
Njengoba ukusetshenziswa kwanda, ukusebenza kuyehla. Lokhu akufiseleki ezimweni eziningi. Uma uhlelo lokusebenza lufaka izakhi etafuleni bese luzilahla (isibonelo, lapho ubala amagama encwadini), lokhu akuyona inkinga. Kodwa uma uhlelo lokusebenza lusebenzisa ithebula le-hashi lesikhathi eside (isibonelo, kusihleli sezithombe ukuze sigcine izingxenye ezingenalutho zezithombe lapho umsebenzisi evamise ukufaka nokususa ulwazi), lokhu kuziphatha kungaba yinkinga.
Futhi kukalwe ithebula le-hashi lokuhlola ukujula ngemva kokufaka okuyizigidi ezingu-64 (isici sokusetshenziswa esingu-0,5). Ukujula okumaphakathi kwakungu-0,4774, ngakho-ke okhiye abaningi bebesendaweni engcono kakhulu noma indawo eyodwa kude nendawo engcono kakhulu. Ukujula komsindo omkhulu bekungama-60.
Ngabe sengikala ukujula kokuhlola etafuleni elinokufakwa okuyizigidi ezingu-124 (isici sokusetshenziswa esingu-0,97). Ukujula okumaphakathi kwase kuvele ku-10,1757, futhi okuphezulu - 6474 (!!). Ukusebenza kwezinzwa zolayini kwehla kakhulu ngamanani aphezulu okusetshenziswa.
Kungcono kakhulu ukugcina izinga lokusebenzisa leli thebula le-hashi liphansi. Kodwa-ke sikhulisa ukusebenza ngezindleko zokusebenzisa inkumbulo. Ngenhlanhla, esimweni sokhiye namanani angu-32-bit, lokhu kungathethelelwa. Uma kulesi sibonelo esingenhla, etafuleni elinezinto eziyizigidi eziyi-128, sigcina isici sokusetshenziswa esingu-0,25, lapho-ke asikwazi ukubeka izinto ezingaphezu kwezigidi ezingama-32 kulo, futhi izikhala ezisele eziyizigidi ezingama-96 zizolahleka - amabhayithi ayi-8 kubhangqa ngalinye. , 768 MB yenkumbulo elahlekile.
Sicela uqaphele ukuthi sikhuluma ngokulahleka kwememori yekhadi levidiyo, okuwumthombo obaluleke kakhulu kunememori yohlelo. Nakuba amakhadi amaningi ezithombe zedeskithophu yesimanje asekela i-CUDA anenkumbulo okungenani engu-4 GB (ngesikhathi sokubhala, i-NVIDIA 2080 Ti ine-11 GB), bekungeke kube yisinqumo esihlakaniphe kakhulu ukulahlekelwa amanani anjalo.
Kamuva ngizobhala okwengeziwe mayelana nokudala amathebula e-hashi amakhadi wevidiyo angenazo izinkinga ngokujula kokuhlola, kanye nezindlela zokusebenzisa kabusha izikhala ezisusiwe.
Ukulinganisa ukujula komsindo
Ukuze sinqume ukujula kokuhlola kokhiye, singakhipha i-hashi yokhiye (inkomba yayo yethebula efanelekile) kunkomba yayo yethebula langempela:
// get_key_index() -> index of key in hash table
uint32_t probelength = (get_key_index(key) - hash(key)) & (hashtablecapacity-1);
Ngenxa yomlingo wezinombolo ezimbili ezihambisanayo ezimbili kanye neqiniso lokuthi umthamo wethebula le-hashi ukabili emandleni amabili, le ndlela izosebenza ngisho nalapho inkomba yokhiye ihanjiswa ekuqaleni kwetafula. Ake sithathe ukhiye osheshi ukuya ku-1, kodwa ufakwe ku-slot 3. Bese sithola itafula elinomthamo 4 (3 β 1) & 3, okulingana no-2.
isiphetho
Uma unemibuzo noma imibono, ngicela ungithumele i-imeyili ku noma uvule isihloko esisha ku.
Le khodi yabhalwa ngaphansi kokukhuthazwa okuvela ezihlokweni ezinhle kakhulu:
Ngokuzayo, ngizoqhubeka nokubhala mayelana nokusetshenziswa kwetafula le-hash lamakhadi wevidiyo futhi ngihlaziye ukusebenza kwawo. Izinhlelo zami zibandakanya i-chaining, i-Robin Hood hashing, kanye ne-cuckoo hashing usebenzisa ukusebenza kwe-athomu ezakhiweni zedatha ezinobungani be-GPU.
Source: www.habr.com