logo标签列表

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

c++perlgohashtable
7

对哈希表进行了简单的性能测试，结果显示C++版本比Perl版本和Golang版本更慢。

  • Perl版本大约需要200毫秒，
  • C++版本需要280毫秒，
  • Golang版本只需要56毫秒。

这是在我的电脑上，使用Core(TM) i7-2670QM CPU @ 2.20GHz, Ubuntu 14.04.3LTS操作系统进行测试的。

有什么想法吗？

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;
}

Go语言版本

package main

import "fmt"
import "time"

func main() {
    var x string
    mymap := make(map[string]string)
    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";
    t0 := time.Now()
    sum := 1
    for sum < 1000000 {
        x = mymap["China"]
        sum += 1
    }
    t1 := time.Now()
    fmt.Printf("The call took %v to run.\n", t1.Sub(t0))
    fmt.Println(x)
}

更新1

为了改进C++版本，将x = mymap["China"]; 更改为 mymap["China"];，但在性能上几乎没有什么区别。

更新2

当没有任何优化编译时，我得到了原始结果：g++ -std=c++11 unorderedMap.cc。使用“-O2”优化后，时间只需要一半（150毫秒）。

更新3

为了避免可能出现的char*转换成string构造函数调用，我创建了一个字符串常量。时间降至约220毫秒（未进行编译优化）。感谢@neil-kirk的建议，使用优化（-O2标志），时间约为80毫秒。

  double start = getTS();
  string x = "China";
  for (int i=0; i<1000000; i++) {
      mymap[x];
  }

更新4

感谢@steffen-ullrich指出perl版本存在语法错误。我进行了更改。性能数字约为150毫秒。

更新5

看来执行的指令数很重要。使用命令valgrind --tool=cachegrind <cmd>

对于Go版本

$ valgrind --tool=cachegrind  ./te1
==2103== Cachegrind, a cache and branch-prediction profiler
==2103== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2103== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2103== Command: ./te1
==2103== 
--2103-- warning: L3 cache found, using its data for the LL simulation.
The call took 1.647099s to run.
Beijing
==2103== 
==2103== I   refs:      255,763,381
==2103== I1  misses:          3,709
==2103== LLi misses:          2,743
==2103== I1  miss rate:        0.00%
==2103== LLi miss rate:        0.00%
==2103== 
==2103== D   refs:      109,437,132  (77,838,331 rd   + 31,598,801 wr)
==2103== D1  misses:        352,474  (   254,714 rd   +     97,760 wr)
==2103== LLd misses:        149,260  (    96,250 rd   +     53,010 wr)
==2103== D1  miss rate:         0.3% (       0.3%     +        0.3%  )
==2103== LLd miss rate:         0.1% (       0.1%     +        0.1%  )
==2103== 
==2103== LL refs:           356,183  (   258,423 rd   +     97,760 wr)
==2103== LL misses:         152,003  (    98,993 rd   +     53,010 wr)
==2103== LL miss rate:          0.0% (       0.0%     +        0.1%  )

对于 C++ 优化版本（无优化标志）

$ valgrind --tool=cachegrind ./a.out
==2180== Cachegrind, a cache and branch-prediction profiler
==2180== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2180== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2180== Command: ./a.out
==2180== 
--2180-- warning: L3 cache found, using its data for the LL simulation.
took 64.657681 sec
==2180== 
==2180== I   refs:      5,281,474,482
==2180== I1  misses:            1,710
==2180== LLi misses:            1,651
==2180== I1  miss rate:          0.00%
==2180== LLi miss rate:          0.00%
==2180== 
==2180== D   refs:      3,170,495,683  (1,840,363,429 rd   + 1,330,132,254 wr)
==2180== D1  misses:           12,055  (       10,374 rd   +         1,681 wr)
==2180== LLd misses:            7,383  (        6,132 rd   +         1,251 wr)
==2180== D1  miss rate:           0.0% (          0.0%     +           0.0%  )
==2180== LLd miss rate:           0.0% (          0.0%     +           0.0%  )
==2180== 
==2180== LL refs:              13,765  (       12,084 rd   +         1,681 wr)
==2180== LL misses:             9,034  (        7,783 rd   +         1,251 wr)
==2180== LL miss rate:            0.0% (          0.0%     +           0.0%  )

对于C++优化版本

$ valgrind --tool=cachegrind ./a.out
==2157== Cachegrind, a cache and branch-prediction profiler
==2157== Copyright (C) 2002-2013, and GNU GPL'd, by Nicholas Nethercote et al.
==2157== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2157== Command: ./a.out
==2157== 
--2157-- warning: L3 cache found, using its data for the LL simulation.
took 9.419447 sec
==2157== 
==2157== I   refs:      1,451,459,660
==2157== I1  misses:            1,599
==2157== LLi misses:            1,549
==2157== I1  miss rate:          0.00%
==2157== LLi miss rate:          0.00%
==2157== 
==2157== D   refs:        430,486,197  (340,358,108 rd   + 90,128,089 wr)
==2157== D1  misses:           12,008  (     10,337 rd   +      1,671 wr)
==2157== LLd misses:            7,372  (      6,120 rd   +      1,252 wr)
==2157== D1  miss rate:           0.0% (        0.0%     +        0.0%  )
==2157== LLd miss rate:           0.0% (        0.0%     +        0.0%  )
==2157== 
==2157== LL refs:              13,607  (     11,936 rd   +      1,671 wr)
==2157== LL misses:             8,921  (      7,669 rd   +      1,252 wr)
==2157== LL miss rate:            0.0% (        0.0%     +        0.0%  )
1
在 for 循环之外，将键缓存到本地字符串变量中。 - Neil Kirk
3
你是否开启了优化？ - Galik
@codingFun，关于mymap.at(key)怎么样？ - cezheng
2
我其实并不关心这些基准测试，因为至少目前为止，即使经过“修复”，Perl 代码仍未能完成其应有的功能。我不知道其他代码是否也存在问题，或者编译器是否已经优化了某些内容。这些基准测试绝对不可靠。 - Steffen Ullrich
3
除此之外，使用不到一秒钟的基准测试是无意义的，因为处理器当前所处的功耗模式以及可能正在并行运行并占用CPU时间的进程都纯属运气。真正的基准测试会持续数小时，以确保基准测试不受这些问题的影响。 - Steffen Ullrich
显示剩余19条评论
4个回答
16

以下是您的Perl代码（在尝试修复之前）：

@mymap = ();
$mymap["U.S."] = "Washington";
$mymap["U.K."] = "London";
这不是一个地图，而是一个数组。哈希映射的语法如下：
  %mymap;
  $mymap{"U.S."} = ....

因此，您实际上创建的是一个数组而不是哈希映射，并且始终访问元素0。请在使用Perl时始终使用use strict;和use warnings;，即使只进行简单的语法检查也会显示出问题：
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时钟下以较低的功率模式运行一个基准测试而不是其他基准测试。例如，在我的系统上，同一“基准测试”的多次运行在测量时间上的变化在100ms和150ms之间变化。
基准测试是谎言，而像您这样的微基准测试更是如此。
感谢@steffen-ullrich指出语法问题。现在已经修复，但性能数字并没有提高。 - packetie
1
@codingFun：不要期望数字会上升，因为在代码修复后它实际上会执行更复杂的操作。而且就像我说的：基准测试是谎言，而像你这样的微基准测试更是如此。阅读有关CPU、电源模式、调度程序的部分...并根据生成的代码而不是您的输入验证其他代码的功能。就像我说的，聪明的编译器可能会意识到它没有做任何有用的事情，并将其优化掉。 - Steffen Ullrich
@codingFun：除此之外，你的代码仍然有误，如果你真的像我建议的那样使用警告，你就会看到它。 - Steffen Ullrich
你是正确的。微基准测试只能提供一个大致的想法。需要更多的研究来选择项目所需的语言。顺便说一下，当我编辑时，$x = $mymap["China"]; 中有个打字错误。现在已经更新了。性能约为180毫秒。 - packetie
2
@codingFun：正如你所见，当进行微小的更改时，性能会有很大的变化。仅仅从 $x = $mymap{..} 更改为 my $x = $mymap{...} 就会显著影响性能。而在我的系统上，程序多次运行之间存在 50% 的差异。 - Steffen Ullrich
你又是对的，我尝试了 my $x = $mymap{...}，速度确实提高了大约25%。由于200毫秒很短，每次运行之间有很大的差异（正如你所指出的），我通过运行30M的循环（而不是1M），并将时间规范化为1M循环来稳定它。 - packetie
4

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

#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;
}

在我的系统上运行此代码，我得到了大约68毫秒的运行时间，以下是输出结果：

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

原来哈希表没有很好地优化，存在一些冲突。进一步打印桶中的元素显示，西班牙和中国在第9个桶中。该桶可能是一个链接列表，节点分布在内存中，解释了性能下降。
如果选择另一个哈希表大小使得没有冲突，您可以获得加速。我测试了添加"mymap.rehash(1001)"，并且获得了20-30%的加速，时间介于44-52毫秒之间。
现在，另一个问题是计算"China"的哈希值。这个函数在每个迭代中都会执行。当我们切换到常量普通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 桶中没有冲突，我们也不需要重新哈希。

转换为 char* 意味着您使用引用相等性，因此如果您传递来自不同源的字符串，则代码将无法正常工作。 - CodesInChaos
@CodesInChaos 你是对的，但我认为这不是那个微基准测试的重点。 - Jens
感谢@Jens的详细解释。碰撞确实是一个大问题。使用不同的键，“France”，可以提高约25%的性能。比较指针确实可以极大地提高性能，但这不是我们在这里需要的。我相信性能与执行的指令数量有很大关系，正如james-picone在生成的汇编中指出的那样。在问题上创建了更新5。谢谢。 - packetie
@codingFun 使用指针的示例表明，运行时的很大一部分时间都花费在计算哈希值上，因为这是随类型而变化的。我猜测 Go 版本要么有更好的字符串哈希函数，可能缓存哈希值，从而只计算一次，要么使用其他策略来实现小字符串的映射。 - Jens
@jens，我也是。只希望C++的实现能够赶上Go的实现。 - packetie
3

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

mymap["China"] 调用mapaccess1_faststr，该函数专门针对字符串键进行优化。特别是对于仅有一个桶的小型映射，对于长度小于32字节的字符串甚至不需要计算哈希值。

2

这只是猜测：

unordered_map::operator[]需要一个字符串参数。您提供了一个char*。如果没有优化，C++版本很可能会调用std::string(char*)构造函数一百万次，将“China”转换为std::string。 Go的语言规范可能会将“字符串字面量”视为与字符串相同的类型，因此不需要调用构造函数。

开启优化后，字符串构造函数将被提升出循环，您将看不到相同的问题。或者可能根本不会生成任何代码，除了获取时间和打印差异的两个系统调用，因为最终它都没有影响。

要确认这一点，您必须实际查看正在生成的汇编代码。这将是编译器选项。请参见此问题以获取GCC所需的标志。

去掉额外的构造函数调用有所帮助，但是C++版本仍然相当慢。谢谢！ - packetie
我仍然非常好奇Go汇编和C++汇编之间的区别是什么。 - James Picone
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接