c++ - 为什么迭代器调试在调试版本中会减慢 std::unordered_map 200x？

Question

我知道代码会变慢，但为什么这么慢？我该如何编码才能避免这种减速？

std::unordered_map 在内部使用其他容器，而这些容器使用迭代器。构建调试时，默认_ITERATOR_DEBUG_LEVEL=2。这会打开 iterator debugging .有时我的代码没有受到太大影响，有时运行起来非常慢。

我可以通过在我的项目属性 >> C++ >> 预处理器 >> 预处理器定义中设置 _ITERATOR_DEBUG_LEVEL=0 来加速我的示例。但是作为this link建议，我不能在我的真实项目中这样做。就我而言，我与 MSVCMRTD.lib 发生冲突，其中包含使用 _ITERATOR_DEBUG_LEVEL=2 构建的 std::basic_string。我知道我可以通过静态链接到 CRT 来解决这个问题。但如果我可以修复代码，我宁愿不这样做，这样问题就不会出现。

我可以做出改变来改善这种情况。但我只是在不理解它们为什么起作用的情况下尝试。例如，前 1000 个插入以全速运行。但是，如果我将 O_BYTE_SIZE 更改为 1，则第一个插入与其他所有内容一样慢。这看起来像是一个小的改变(不一定是好的改变。)

This , this , 和 this也阐明了一些问题，但不要回答我的问题。

我使用的是 Visual Studio 2010(这是遗留代码。)我创建了一个 Win32 控制台应用程序并添加了这段代码。

main.cpp

#include "stdafx.h"


#include "OString.h"
#include "OTHashMap.h"

#include <cstdio>
#include <ctime>
#include <iostream>

// Hash and equal operators for map
class CRhashKey {
public:
   inline unsigned long operator() (const OString* a) const { return a->hash(); }
};

class CReqKey {
public:
    inline bool operator() (const OString& x, const OString& y) const { return strcmp(x.data(),y.data()) != 0; }
    inline bool operator() (const OString* x, const OString& y) const { return operator()(*x,y); }
    inline bool operator() (const OString& x, const OString* y) const { return operator()(x,*y); }
    inline bool operator() (const OString* x, const OString* y) const { return operator()(*x,*y); }
};


int _tmain(int argc, _TCHAR* argv[])
{
    const int CR_SIZE = 1020007;

    CRhashKey h;
    OTPtrHashMap2<OString, int, CRhashKey, CReqKey> *code_map = 
        new OTPtrHashMap2 <OString, int, CRhashKey, CReqKey>(h, CR_SIZE);

    const clock_t begin_time = clock();

    for (int i=1; i<=1000000; ++i)
    {
        char key[10];
        sprintf(key, "%d", i);

        code_map->insert(new OString(key), new int(i));

        //// Check hash values
        //OString key2(key);
        //std::cout << i << "\t" << key2.hash() << std::endl;

        // Check timing
        if ((i % 100) == 0)
        {
            std::cout << i << "\t" << float(clock() - begin_time) / CLOCKS_PER_SEC << std::endl;
        }
    }

    std::cout << "Press enter to exit" << std::endl;
    char buf[256];
    std::cin.getline(buf, 256);

    return 0;
}

OTHashMap.h

#pragma once

#include <fstream>
#include <unordered_map>    

template <class K, class T, class H, class EQ>
class OTPtrHashMap2
{
    typedef typename std::unordered_map<K*,T*,H,EQ>                     OTPTRHASHMAP_INTERNAL_CONTAINER;
    typedef typename OTPTRHASHMAP_INTERNAL_CONTAINER::iterator          OTPTRHASHMAP_INTERNAL_ITERATOR;

public:
    OTPtrHashMap2(const H& h, size_t defaultCapacity) : _hashMap(defaultCapacity, h) {}

    bool insert(K* key, T* val)
    {
        std::pair<OTPTRHASHMAP_INTERNAL_ITERATOR,T> retVal = _hashMap.insert(std::make_pair<K*,T*>(key, val));
        return retVal.second != NULL;
    }

    OTPTRHASHMAP_INTERNAL_CONTAINER _hashMap;

private:
};

OString.h

#pragma once

#include <string>

class OString
{
public:
    OString(const std::string& s) : _string (s) { } 
    ~OString(void) {}

    static unsigned hash(const OString& s) { return unsigned (s.hash()); }
    unsigned long hash() const
    {
        unsigned hv = static_cast<unsigned>(length());
        size_t i = length() * sizeof(char) / sizeof(unsigned);
        const char * p = data();
        while (i--) {
            unsigned tmp;
            memcpy(&tmp, p, sizeof(unsigned));
            hashmash(hv, tmp);
            p = p + sizeof(unsigned);
        } 
        if ((i = length() * sizeof(char) % sizeof(unsigned)) != 0)  {
            unsigned h = 0;
            const char* c = reinterpret_cast<const char*>(p);
            while (i--)
            {
                h = ((h << O_BYTE_SIZE*sizeof(char)) | *c++);
            }
            hashmash(hv, h);
        }
        return hv; 
    }

    const char* data() const { return _string.c_str(); }
    size_t length() const    { return _string.length(); }


private:
    std::string _string;

    //static const unsigned O_BYTE_SIZE = 1;
    static const unsigned O_BYTE_SIZE = 8;
    static const unsigned O_CHASH_SHIFT = 5;

    inline void hashmash(unsigned& hash, unsigned chars) const
    {
        hash = (chars ^
                ((hash << O_CHASH_SHIFT) |
                 (hash >> (O_BYTE_SIZE*sizeof(unsigned) - O_CHASH_SHIFT))));
    }
};

Answer 1

我找到了足够多的答案。碰撞是减速的根源。

编辑 2:-- 另一个修复是在 main.cpp 中的 #include 周围添加它 --

// Iterator debug checking makes the Microsoft implementation of std containers 
// *very* slow in debug builds for large containers. It must only be undefed around 
// STL includes. Otherwise we get linker errors from the debug C runtime library, 
// which was built with _ITERATOR_DEBUG_LEVEL set to 2. 
#ifdef _DEBUG
#undef _ITERATOR_DEBUG_LEVEL
#endif

#include <unordered_map>

#ifdef _DEBUG
#define _ITERATOR_DEBUG_LEVEL 2
#endif

编辑:——修复是切换到 boost::unordered_map。 --

std::unordered_map 在 中定义。它继承自_Hash，定义在 中。

_Hash 包含这个(高度缩写)

template<...> 
class _Hash
{
    typedef list<typename _Traits::value_type, ...> _Mylist;
    typedef vector<iterator, ... > _Myvec;

    _Mylist _List;  // list of elements, must initialize before _Vec
    _Myvec _Vec;    // vector of list iterators, begin() then end()-1
};

所有值都存储在_List 中。

_Vec 是指向 _List 的迭代器 vector 。它将 _List 分成桶。 _Vec 有一个指向每个桶的开头和结尾的迭代器。因此，如果映射有 1M 个桶(不同的键哈希)，_Vec 有 2M 个迭代器。

当一个键/值对被插入映射时，通常会创建一个新的桶。该值被推到列表的开头。键的散列是 _Vec 中放置两个新迭代器的位置。这很快，因为它们指向列表的开头。

如果桶已经存在，则必须将新值插入到 _List 中现有值的旁边。这需要在列表中间插入一个项目。必须更新现有的迭代器。显然，当启用迭代器调试时，这需要大量工作。代码在 里，我没有单步执行。

---

为了了解工作量，我使用了一些无意义的散列函数，这些函数使用起来很糟糕，但在插入时会产生很多冲突或很少的冲突。

添加到 OString.h

static unsigned hv2;

// Never collides. Always uses the next int as the hash
unsigned long hash2() const
{
    return ++hv2;
}

// Almost never collides. Almost always gets the next int. 
// Gets the same int 1 in 200 times. 
unsigned long hash3() const
{
    ++hv2;
    unsigned long lv = (hv2*200UL)/201UL;
    return (unsigned)lv;
}

// A best practice hash
unsigned long hash4() const
{
    std::hash<std::string> hasher;
    return hasher(_string);
}

// Always collides. Everything into bucket 0. 
unsigned long hash5() const
{
    return 0;
}

添加到 main.cpp

// Hash and equal operators for map
class CRhashKey {
public:
   //inline unsigned long operator() (const OString* a) const { return a->hash(); }
   //inline unsigned long operator() (const OString* a) const { return a->hash2(); }
   //inline unsigned long operator() (const OString* a) const { return a->hash3(); }
   //inline unsigned long operator() (const OString* a) const { return a->hash4(); }
   inline unsigned long operator() (const OString* a) const { return a->hash5(); }
};

unsigned OString::hv2 = 0;

结果是戏剧性的。没有现实的哈希会起作用。

• hash2 - 永不冲突 - 在 15.3 秒内插入 1M
• hash3 - 几乎从不 - 在 206 秒内插入 1M
• hash4 - 最佳实践 - 在 132 秒内插入 100k，并且随着冲突变得更加频繁而变慢。 1M 插入需要 > 1 小时
• hash5 - 始终碰撞 - 48 秒内插入 1k，或 13 小时内插入 1M

我的选择是

• 按照 Retired Ninja 的建议发布构建、调试符号和优化
• 静态链接到 MSVCMRTD，这样我就可以关闭 _ITERATOR_DEBUG_LEVEL。还解决了其他一些类似的问题。
• 从 unordered_map 更改为排序 vector 。
• 其他。欢迎提出建议。