ਮੈਂ ਇਸਨੂੰ Github 'ਤੇ ਪੋਸਟ ਕੀਤਾ ਹੈ ਨਵਾਂ ਪ੍ਰੋਜੈਕਟ ਇੱਕ ਸਧਾਰਨ 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 ms ਦਾ ਸਮਾਂ ਲਿਆ। ਇਸ ਵਿੱਚ ਵੀਡੀਓ ਕਾਰਡ ਦੁਆਰਾ ਤੱਤ ਪਾਉਣ ਅਤੇ ਮਿਟਾਉਣ ਵਿੱਚ ਬਿਤਾਇਆ ਗਿਆ ਸਮਾਂ ਸ਼ਾਮਲ ਹੈ, ਅਤੇ ਮੈਮੋਰੀ ਵਿੱਚ ਨਕਲ ਕਰਨ ਅਤੇ ਨਤੀਜੇ ਸਾਰਣੀ ਉੱਤੇ ਦੁਹਰਾਉਣ ਵਿੱਚ ਬਿਤਾਏ ਗਏ ਸਮੇਂ ਨੂੰ ਧਿਆਨ ਵਿੱਚ ਨਹੀਂ ਰੱਖਦਾ। ਜੇ GPU ਟੇਬਲ ਲੰਬੇ ਸਮੇਂ ਲਈ ਰਹਿੰਦਾ ਹੈ, ਜਾਂ ਜੇਕਰ ਹੈਸ਼ ਟੇਬਲ ਪੂਰੀ ਤਰ੍ਹਾਂ ਵੀਡੀਓ ਕਾਰਡ ਦੀ ਮੈਮੋਰੀ ਵਿੱਚ ਸ਼ਾਮਲ ਹੈ (ਉਦਾਹਰਣ ਵਜੋਂ, ਇੱਕ ਹੈਸ਼ ਟੇਬਲ ਬਣਾਉਣ ਲਈ ਜੋ ਦੂਜੇ GPU ਕੋਡ ਦੁਆਰਾ ਵਰਤਿਆ ਜਾਵੇਗਾ ਨਾ ਕਿ ਕੇਂਦਰੀ ਪ੍ਰੋਸੈਸਰ ਦੁਆਰਾ), ਤਾਂ ਟੈਸਟ ਦਾ ਨਤੀਜਾ ਢੁਕਵਾਂ ਹੈ।

ਵੀਡੀਓ ਕਾਰਡ ਲਈ ਹੈਸ਼ ਟੇਬਲ ਉੱਚ ਥ੍ਰਰੂਪੁਟ ਅਤੇ ਕਿਰਿਆਸ਼ੀਲ ਸਮਾਨਤਾ ਦੇ ਕਾਰਨ ਉੱਚ ਪ੍ਰਦਰਸ਼ਨ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ।

shortcomings

ਹੈਸ਼ ਟੇਬਲ ਆਰਕੀਟੈਕਚਰ ਵਿੱਚ ਸੁਚੇਤ ਹੋਣ ਲਈ ਕੁਝ ਮੁੱਦੇ ਹਨ:

• ਲੀਨੀਅਰ ਪ੍ਰੋਬਿੰਗ ਨੂੰ ਕਲੱਸਟਰਿੰਗ ਦੁਆਰਾ ਅੜਿੱਕਾ ਬਣਾਇਆ ਜਾਂਦਾ ਹੈ, ਜਿਸ ਕਾਰਨ ਸਾਰਣੀ ਵਿੱਚ ਕੁੰਜੀਆਂ ਪੂਰੀ ਤਰ੍ਹਾਂ ਘੱਟ ਰੱਖੀਆਂ ਜਾਂਦੀਆਂ ਹਨ।
• ਫੰਕਸ਼ਨ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਕੁੰਜੀਆਂ ਨੂੰ ਨਹੀਂ ਹਟਾਇਆ ਜਾਂਦਾ ਹੈ 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