Feedback sur l'implémentation d'une map?

[LoshkinOleg]

Séb et moi avons fait un premier jet d'une implémentation d'une hash map. Pourrait-on avoir du feedback svp?

#pragma once

#include <engine/custom_allocator.h>
#include <vector> // TODO: replace this with neko's own container.
#include <xxhash.hpp>

namespace neko
{

template<typename Key, typename Value>
class Map
{
public:
    // Constructor / destructor.
    Map(Allocator* allocator, const size_t sizeInBytes)
    {
        allocator = nullptr; // TODO: Pass this allocator to neko's container.

        pairs_.resize(sizeInBytes / sizeof(Value));
        for (auto& pair : pairs_)
        {
            pair = std::pair<xxh::hash_t<64>, Value>(0, Value());
        }
    }

    // Overloads.
    inline Map<Key, Value>& operator=(Map<Key, Value>&& other) noexcept
    {
        return *this;
    }

    inline bool IsEmpty()
    {
        return count_ == 0;
    }

    inline size_t Count()
    {
        return count_;
    }

    inline size_t Capacity()
    {
        return pairs_.capacity();
    }

    bool Add(const Key key, const Value value) const
    {
        // TODO@Seb: matchCount that key doesn't exist already in the map! Otherwise 1 key may have multiple values!

        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = pairs_.capacity();
        for (size_t i = 0; i < len; i++)
        {
            if (pairs_[i].first == 0)
            {
                pairs_[i].first = hash;
                pairs_[i].second = value;
                return true;
            }
        }
        return false;
    }

    bool Remove(const Key key) const
    {
        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = pairs_.capacity();
        for (int i = 0; i < len; i++)
        {
            if (pairs_[i].first == hash)
            {
                pairs_[i].first = 0;
                pairs_[i].second = Value();
                return true;
            }
        }
        return false;
    }

    void Clear() const
    {
        for (auto& pair : pairs_)
        {
            pair = std::pair<xxh::hash_t<64>, Value>(0, Value());
        }
    }

    bool Swap(const Key a, const Key b) const
    {
        if (a == b) return true;

        const xxh::hash_t<64> hash0 = xxh::xxhash<64>(&a, sizeof(Key));
        const xxh::hash_t<64> hash1 = xxh::xxhash<64>(&b, sizeof(Key));
        const size_t len = count_;

        size_t index0 = 0;
        size_t index1 = 0;
        size_t i = 0;
        bool firstMatch = false;

        while (i++ < len)
        {
            auto hash = pairs_[i].first;
            if (hash == hash0 || hash == hash1)
            {
                if (!firstMatch)
                {
                    index0 = i;
                    firstMatch = true;
                }
                else
                {
                    index1 = i;
                    goto RETURN;
                }
            }
        }
        return false; // Traversed whole map without finding both keys.

        RETURN:
        const auto temp = pairs_[index0].second;
        pairs_[index0].second = pairs_[index1].second;
        pairs_[index1].second = temp;
        return true;
    }

    Value& FindValue(const Key key) const
    {
        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = count_;

        for (size_t i = 0; i < len; i++)
        {
            if (pairs_[i].first == hash)
            {
                return pairs_[i].second;
            }
        }
        return Value();
    }

private:
    std::vector<std::pair<xxh::hash_t<64>, Value>> pairs_; // TODO: Replace this with neko's container when it's ready.
    size_t count_ = 0;
};

}// !neko

Merci!

[LoshkinOleg]

J'ai debuggé le code entre temps:

#pragma once

#include <engine/custom_allocator.h>
#include <vector> // TODO: replace this with neko's own container.
#include <xxhash.hpp>

namespace neko
{

template<typename Key, typename Value>
class Map
{
public:
    // Constructor / destructor.
    Map(Allocator* allocator, const size_t sizeInBytes)
    {
        allocator = nullptr; // TODO: Pass this allocator to neko's container.

        pairs_.resize(sizeInBytes / sizeof(Value));
        for (auto& pair : pairs_)
        {
            pair = std::pair<xxh::hash_t<64>, Value>(0, Value());
        }
    }

    // Overloads.
    inline Map<Key, Value>& operator=(Map<Key, Value>&& other) noexcept
    {
        return *this;
    }

    inline bool IsEmpty()
    {
        return count_ == 0;
    }

    inline size_t Count()
    {
        return count_;
    }

    inline size_t Capacity()
    {
        return pairs_.capacity();
    }

    bool Add(const Key key, const Value value)
    {
        // TODO@Seb: check that key doesn't exist already in the map! Otherwise 1 key may have multiple values!

        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = pairs_.capacity();
        for (size_t i = 0; i < len; i++)
        {
            if (pairs_[i].first == 0)
            {
                pairs_[i].first = hash;
                pairs_[i].second = value;
                count_++;
                return true;
            }
        }
        return false;
    }

    bool Remove(const Key key)
    {
        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = pairs_.capacity();
        for (int i = 0; i < len; i++)
        {
            if (pairs_[i].first == hash)
            {
                pairs_[i].first = 0;
                pairs_[i].second = Value();
                count_--;
                return true;
            }
        }
        return false;
    }

    void Clear()
    {
        for (auto& pair : pairs_)
        {
            pair = std::pair<xxh::hash_t<64>, Value>(0, Value());
        }
        count_ = 0;
    }

    bool Swap(const Key a, const Key b)
    {
        if (a == b || count_ < 2) return false;

        const xxh::hash_t<64> hash0 = xxh::xxhash<64>(&a, sizeof(Key));
        const xxh::hash_t<64> hash1 = xxh::xxhash<64>(&b, sizeof(Key));
        const size_t len = count_;

        size_t index0 = 0;
        size_t index1 = 0;
        size_t i = 0;
        bool firstMatch = false;

        do
        {
            auto hash = pairs_[i].first;
            if (hash == hash0 || hash == hash1)
            {
                if (!firstMatch)
                {
                    index0 = i;
                    firstMatch = true;
                }
                else
                {
                    index1 = i;
                    goto RETURN;
                }
            }
        } while (i++ < len);
        return false; // Traversed whole map without finding both keys.

        RETURN:
        const auto temp = pairs_[index0].second;
        pairs_[index0].second = pairs_[index1].second;
        pairs_[index1].second = temp;
        return true;
    }

    Value FindValue(const Key key) const
    {
        // TODO@Seb: Have to traverse whole vector regardless of count_ if there are holes in the memory layout!

        const xxh::hash_t<64> hash = xxh::xxhash<64>(&key, sizeof(Key));
        const size_t len = pairs_.size(); // TODO@Seb: this...

        for (size_t i = 0; i < len; i++)
        {
            if (pairs_[i].first == hash)
            {
                return pairs_[i].second;
            }
        }
        return 0;
    }

private:
    std::vector<std::pair<xxh::hash_t<64>, Value>> pairs_; // TODO: Replace this with neko's container when it's ready.
    size_t count_ = 0;
};

}// !neko

[EliasFarhan]

Okay, c'est un VectorMap votre classe hein! Vous pouvez utiliser using KeyValuePair = std::pair<..., ...> aussi pour cleaner un peu.

Et il faut tester tout ça si c'est pas fait. Benchmarker les fonctions usuelles (insert, get_value, ...) par rapport à std::map aussi.

[LoshkinOleg]

T'avais bien dit de commençer par une VectorMap non? Quelles autres implémentations est-ce qu'on doit faire? C'est quoi la différence entre une vector map et une hash map?

Et on a un test pour s'assurer que tout fonctionne, mais je rajoute un benchmark pour comparer notre map avec celle du std alors.

[LoshkinOleg]

Benchmark de FindValue():

---

Benchmark Time CPU Iterations

BM_StdMap/2 214 ns BM_StdMap/8 1295 ns BM_StdMap/64 14494 ns BM_StdMap/512 144762 ns BM_NekoMap/2 292 ns BM_NekoMap/8 1320 ns BM_NekoMap/64 26889 ns BM_NekoMap/512 1227872 ns

.....ouch

[EliasFarhan]

Pour les benchmarks, il faut désactiver les assert (dans cmake Neko_Assert)