小编egu*_*gur的帖子

基于散列表的容器是非常快速的关联数组(例如unordered_map,unordered_set).

它们的性能高度依赖于用于为每个条目创建索引的哈希函数.随着哈希表的增长,元素会一次又一次地重新出现.

指针是简单类型,基本上是唯一标识对象的4/8字节值.问题在于,由于多个LSB为零,因此使用地址作为散列函数的结果是无效的.

例:

struct MyVoidPointerHash {
    size_t operator()(const void* val) const {
        return (size_t)val;
    }
};

更快的实现是丢失一些位:

struct MyVoidPointerHash2 {
    size_t operator()(const void* val) const {
        return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
    }
};

后者在大型应用程序上产生了10-20%的性能提升,该应用程序使用散列集和映射以及经常构建和清除的数万个元素.

有人可以为散列指针提供更好的方案吗？

功能需要是:

1. 快速!并且必须很好地内联.
2. 提供合理的分配,允许罕见的碰撞.

更新 - 基准测试结果

我运行了两组测试,一组用于int*和一个大小为4KB的类指针.结果非常有趣.

我用于std::unordered_set所有测试,数据大小为16MB,在一次new调用中分配.第一个算法运行了两次,以确保缓存尽可能热,并且CPU正在全速运行.

设置:VS2013(x64),i7-2600,Windows 8.1 x64.

• VS2013默认哈希函数
• HASH1: return (size_t)(val);
• HASH2: return '(size_t)(val) >> 3;
• Hash3(@BasileStarynkevitch): uintptr_t ad = (uintptr_t)val; return …

对于我的用例,我必须非常快速地从列表中插入和删除数据包.

在我看来,有两种常见的解决方法:

• 插入/删除指向这些数据包的指针
• 使用移动语义插入/删除副本

无论如何,我认为使用指针的解决方案应该是最有效的,即使你自己的垃圾收集的缺点.

为了更好的比较,我实现了3个测试用例:

• 使用副本
• 使用移动语义
• 使用指针

为了测量每个测试用例的时间,我还实现了一个计时器类:

class HighPerformanceTimer {

public:
    enum TimerResolution {
        SECONDS      = 1,
        MILLISECONDS = SECONDS * 1000,
        MICROSECONDS = MILLISECONDS * 1000,
        NANOSECONDS  = MICROSECONDS * 1000
    };


    explicit HighPerformanceTimer(const TimerResolution resolution = NANOSECONDS)
        : m_resolution(resolution)
        , m_frequency(0.0)
        , m_startTime({0})
        , m_stopTime({0}) {}
    ~HighPerformanceTimer(void) {}


    bool Init(void) {
        LARGE_INTEGER frequency;
        if(0 == ::QueryPerformanceFrequency(&frequency)) {
            return false;
        }

        /* Check for zero divisor. */
        if(0 == frequency.QuadPart) {
            return false;
        }

        /* Change …

我有一个像这样的非常简单的程序

int main()
{
    int opt;
    int n;
    int flag = 1;
    while(flag)
    {
        printf("m inside while.Press c to continue\n");
        if((opt = getchar())== 'c')
        {
            printf("choose a number\n");
            scanf(" %d",&n);
            switch(n)
            {
            case 0:
                printf("m zero\n");
                break;
            case 1:
               printf("entered one\n");
               break;
            case 3:
               printf("m exit\n");
               flag = 0;
               break;
            }
            printf("m broke\n");
        }
    }
    printf("m out\n");
    return 0;
}

我得到这样的输出：

m inside while.Press c to continue
c
choose a number
1
entered one
m broke
m inside while.Press c …

我正在尝试使用 MSBuild 在 Windows Server 2008 上使用 Boost 和 Cinder 构建 C++ 项目，但没有成功。我已经在我的 Windows 7 机器上使用 VS2013 和 MSBuild 构建了相同的项目，但是在服务器上它说它无法打开名为“threadsafestatics.lib”的库

我从未听说过 threadsafestatics.lib，而且我的 Google-foo 也没有给我带来任何运气，无法在网上找到任何有关它的信息。

有没有办法找出我的项目的哪一部分依赖于这个库？