2

に使用できるように、6バイトのフィールドをハッシュする効率的な方法を探していますstd::unordered_map。

これは、ハッシュを作成する従来の方法だと思います。

struct Hash {
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
        std::size_t key = 0;
        boost::hash_combine(key, mac[0]);
        boost::hash_combine(key, mac[1]);
        boost::hash_combine(key, mac[2]);
        boost::hash_combine(key, mac[3]);
        boost::hash_combine(key, mac[4]);
        boost::hash_combine(key, mac[5]);
        return key;
    }
};

しかし、私はこのトリックを使用してそれを少し速く（〜20％）することができることに気づきました：

struct Hash {
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
        std::size_t key = 0;

        // Possibly UB?
        boost::hash_combine(key, reinterpret_cast<const uint32_t&>(mac[0]));
        boost::hash_combine(key, reinterpret_cast<const uint16_t&>(mac[4]));
        return key;
    }
};

そして、これはさらに高速でした：

struct Hash {
    std::size_t operator()(const std::array<uint8_t, 6> & mac) const {
        // Requires size_t to be 64-bit.
        static_assert(sizeof(std::size_t) >= 6, "MAC address doesn't fit in std::size_t!");

        std::size_t key = 0;

        // Likely UB?
        boost::hash_combine(key, 0x0000FFFFFFFFFFFF & reinterpret_cast<const uint64_t&>(mac[0]));
        return key;
    }
};

私の質問は2つあります。

  1. これらの最適化はUBになりますか？
  2. 私の最初の解決策は進むべき道ですか？それとももっと良い方法はありますか？
4

1 に答える 1

3

最適化により、厳密なエイリアシングルールが破られ、（標準的には）未定義の動作が発生します。

最後の最適化は、あなたが本質的にあなたがすべきではないメモリを読んでいるので私を最も心配します。それはこのメモリがたまたま保護された場合にトラップを引き起こすかもしれません。

使用していない理由はboost::hash_range何ですか？

必要な速度ではないことがわかったのでboost::hash_range、エイリアシングに基づいた別のソリューションを提案します。というか、1つに2つのソリューション。

最初のアイデアは、エイリアシングをchar*一時的なタイプとして使用して抑制できるということです。

size_t key = 0;
char* k = &reinterpret_cast<char*>(&key);

std::copy(mac.begin(), mac.end(), k);

return key;

したがって、はハッシュの有効な実装です。

ただし、さらに一歩進むことができます。位置合わせとパディングのため、とを格納するchar[6]とchar[8]、マップノード内で同じ量のメモリを使用する可能性があります。したがって、次を使用してタイプを充実unionさせることができます。

union MacType {
    unsigned char value[8];
    size_t hash;
};

これで、これをクラス内に適切にカプセル化して（そして、常にバイト7と8toを初期化するようにしてください）、実際に必要な0インターフェースを実装できます。std::array<unsigned char, 6>

ハッシュと高速（アルファベット以外）の比較のために、小さな文字列（8文字未満）にも同様のトリックを使用しましたが、これは非常に便利です。

于 2012-05-12T14:08:11.423 に答える