哈希表的性能，为什么C++最慢？

Question

对 hash 进行了一个简单的性能测试，看起来 C++ 版本比 perl 版本和 golang 版本都慢。perl 版本用了大约 200 毫秒，C++ 版本用了 280 毫秒。golang 版本用了 56 毫秒。在我的带有 Core(TM) i7-2670QM CPU @ 2.20GHz、Ubuntu 14.04.3LTS 的 PC 上，有任何想法吗？perl 版本use Time::HiRes qw( usleep ualarm gettimeofday tv_interval nanosleep                      clock_gettime clock_getres clock_nanosleep clock                      stat );sub getTS {    my ($seconds, $microseconds) = gettimeofday;    return $seconds + (0.0+ $microseconds)/1000000.0;}my %mymap;$mymap{"U.S."} = "Washington";$mymap{"U.K."} = "London";$mymap{"France"} = "Paris";$mymap{"Russia"} = "Moscow";$mymap{"China"} = "Beijing";$mymap{"Germany"} = "Berlin";$mymap{"Japan"} = "Tokyo";$mymap{"China"} = "Beijing";$mymap{"Italy"} = "Rome";$mymap{"Spain"} = "Madrad";$x = "";$start = getTS();for ($i=0; $i<1000000; $i++) {    $x = $mymap{"China"};}printf "took %f sec\n", getTS() - $start;C++版本#include <iostream>#include <string>#include <unordered_map>#include <sys/time.h>double getTS() {    struct timeval tv;    gettimeofday(&tv, NULL);    return tv.tv_sec + tv.tv_usec/1000000.0;}using namespace std;int main () {  std::unordered_map<std::string,std::string> mymap;  // populating container:    mymap["U.S."] = "Washington";    mymap["U.K."] = "London";    mymap["France"] = "Paris";    mymap["Russia"] = "Moscow";    mymap["China"] = "Beijing";    mymap["Germany"] = "Berlin";    mymap["Japan"] = "Tokyo";    mymap["China"] = "Beijing";    mymap["Italy"] = "Rome";    mymap["Spain"] = "Madrad";    double start = getTS();  string x;  for (int i=0; i<1000000; i++) {      mymap["China"];  }  printf("took %f sec\n", getTS() - start);  return 0;}

Answer 1

从您的 Perl 代码（在您尝试修复它之前）：

@mymap = ();

$mymap["U.S."] = "Washington";

$mymap["U.K."] = "London";

这不是地图而是数组。哈希映射的语法是：

  %mymap;

  $mymap{"U.S."} = ....

因此，您有效地做的是创建一个数组而不是哈希映射并始终访问元素 0。请使用use strict;和use warnings;所有用Perl的时候，甚至有警告简单的语法检查会显示你的问题：

perl -cw x.pl

Argument "U.S." isn't numeric in array element at x.pl line 9.

Argument "U.K." isn't numeric in array element at x.pl line 10.

除此之外，基准测试的主要部分实际上没有任何用处（分配一个变量并且从不使用它）并且一些编译器可以检测到它并简单地将其优化掉。

如果您检查 Perl 程序生成的代码，您会看到：

$ perl -MO=Deparse x.pl

@mymap = ();

$mymap[0] = 'Washington';

$mymap[0] = 'London';

...

for ($i = 0; $i < 1000000; ++$i) {

    $x = $mymap[0];

}

也就是说，它在编译时检测到问题，并用对数组索引 0 的访问来替换它。

因此，无论何时进行基准测试，您都需要：

• 检查您的程序是否确实执行了它应该执行的操作。

• 检查编译器是否不优化，也不在编译时执行其他语言将在运行时执行的内容。任何没有结果或可预测结果的语句都易于进行这种优化。

• 验证您实际测量的是您打算测量的内容，而不是其他内容。即使对程序进行很小的更改也会影响运行时间，因为需要分配内存，而这些更改可能与您打算测量的内容无关。在您的基准测试中，您一次又一次地测量对同一哈希元素的访问，而没有对其他元素的访问。这是一项可以很好地与处理器缓存配合使用的活动，但可能无法反映现实世界的使用情况。

而且，使用简单的计时器并不是一个现实的基准。系统上还有其他进程，有调度程序，有缓存垃圾......而对于今天的 CPU，它高度依赖于系统上的负载，因为也许 CPU 会以比其他基准测试更低的功耗模式运行一个基准测试，即使用不同的 CPU 时钟。例如，同一“基准”的多次运行在我的系统上的测量时间在 100 毫秒到 150 毫秒之间变化。

基准是谎言，而像您这样的微观基准则是双重的。

Answer 2

我稍微修改了您的示例以获取有关哈希表结构的一些详细信息：

#include <iostream>

#include <string>

#include <unordered_map>

#include <sys/time.h>

#include <chrono>

using namespace std;

int main()

{

    std::unordered_map<std::string, std::string> mymap;

    // populating container:

    mymap["U.S."] = "Washington";

    mymap["U.K."] = "London";

    mymap["France"] = "Paris";

    mymap["Russia"] = "Moscow";

    mymap["China"] = "Beijing";

    mymap["Germany"] = "Berlin";

    mymap["Japan"] = "Tokyo";

    mymap["China"] = "Beijing";

    mymap["Italy"] = "Rome";

    mymap["Spain"] = "Madrad";

    std::hash<std::string> h;

    for ( auto const& i : mymap )

    {

        printf( "hash(%s) = %ud\n", i.first.c_str(), h( i.first ) );

    }

    for ( int i = 0; i != mymap.bucket_count(); ++i )

    {

        auto const bucketsize = mymap.bucket_size( i );

        if ( 0 != bucketsize )

        {

            printf( "size of bucket %d = %d\n", i, bucketsize );

        }

    }

    auto const start = std::chrono::steady_clock::now();

    string const x = "China";

    std::string res;

    for ( int i = 0; i < 1000000; i++ )

    {

        mymap.find( x );

    }

    auto const elapsed = std::chrono::steady_clock::now() - start;

    printf( "%s\n", res );

    printf( "took %d ms\n",

            std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );

    return 0;

}

在我的系统上运行它，我得到了 ~68ms 的运行时间，输出如下：

hash(Japan) = 3611029618d

hash(Spain) = 749986602d

hash(China) = 3154384700d

hash(U.S.) = 2546447179d

hash(Italy) = 2246786301d

hash(Germany) = 2319993784d

hash(U.K.) = 2699630607d

hash(France) = 3266727934d

hash(Russia) = 3992029278d

size of bucket 0 = 0

size of bucket 1 = 0

size of bucket 2 = 1

size of bucket 3 = 1

size of bucket 4 = 1

size of bucket 5 = 0

size of bucket 6 = 1

size of bucket 7 = 0

size of bucket 8 = 0

size of bucket 9 = 2

size of bucket 10 = 3

事实证明，哈希表没有得到很好的优化，并且包含一些冲突。进一步打印bucket中的元素显示西班牙和中国在bucket 9。bucket可能是一个链表，节点分布在内存中，解释了性能下降。

如果您选择另一个哈希表大小，这样就不会发生冲突，您可以获得加速。我通过添加对其进行了测试，mymap.rehash(1001)并在 44-52 毫秒之间将速度提高了 20-30%。

现在，另一点是计算“中国”的哈希值。该函数在每次迭代中执行。当我们切换到常量纯 C 字符串时，我们可以消除这种情况：

#include <iostream>

#include <string>

#include <unordered_map>

#include <sys/time.h>

#include <chrono>

static auto constexpr us = "U.S.";

static auto constexpr uk = "U.K.";

static auto constexpr fr = "France";

static auto constexpr ru = "Russia";

static auto constexpr cn = "China";

static auto constexpr ge = "Germany";

static auto constexpr jp = "Japan";

static auto constexpr it = "Italy";

static auto constexpr sp = "Spain";

using namespace std;

int main()

{

    std::unordered_map<const char*, std::string> mymap;

    // populating container:

    mymap[us] = "Washington";

    mymap[uk] = "London";

    mymap[fr] = "Paris";

    mymap[ru] = "Moscow";

    mymap[cn] = "Beijing";

    mymap[ge] = "Berlin";

    mymap[jp] = "Tokyo";

    mymap[it] = "Rome";

    mymap[sp] = "Madrad";

    string const x = "China";

    char const* res = nullptr;

    auto const start = std::chrono::steady_clock::now();

    for ( int i = 0; i < 1000000; i++ )

    {

        res = mymap[cn].c_str();

    }

    auto const elapsed = std::chrono::steady_clock::now() - start;

    printf( "%s\n", res );

    printf( "took %d ms\n",

            std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );

    return 0;

}

在我的机器上，这将运行时间减少了 50% 到大约 20 毫秒。不同之处在于，它不是从字符串内容计算散列值，而是将地址转换为散列值，这要快得多，因为它只是将地址值作为 size_t 返回。我们也不需要重新散列，因为与cn.

Answer 3

这只是表明对于这个特定用例，Go 哈希映射实现优化得非常好。

mymap["China"]调用专门针对字符串键优化的mapaccess1_faststr。特别是对于小型单桶映射，甚至不为短（小于 32 字节）字符串计算哈希码。