મેં તેને ગીથબ પર પોસ્ટ કર્યું નવો પ્રોજેક્ટ એક સરળ GPU હેશ ટેબલ.

તે એક સરળ GPU હેશ ટેબલ છે જે સેંકડો લાખો ઇન્સર્ટ્સ પ્રતિ સેકન્ડ પર પ્રક્રિયા કરવામાં સક્ષમ છે. મારા 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-બીટ મૂલ્યો માટે રીડ-રાઇટ ઑપરેશન્સ પરમાણુ હોય છે જ્યાં સુધી તેઓ કુદરતી રીતે સંરેખિત હોય (નીચે જુઓ). અહીં), અને આધુનિક વિડીયો કાર્ડ 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 એમએસનો સમય લાગ્યો. આમાં વિડિયો કાર્ડ દ્વારા ઘટકોને દાખલ કરવામાં અને કાઢી નાખવામાં વિતાવેલો સમય શામેલ છે, અને મેમરીમાં કૉપિ કરવામાં અને પરિણામી કોષ્ટક પર પુનરાવર્તિત કરવામાં વિતાવેલ સમયને ધ્યાનમાં લેતો નથી. જો 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