C++ ~ 1M 在 unordered_map 中使用字符串键查找的工作比 .NET 代码慢得多 [英] C++ ~ 1M look-ups in unordered_map with string key works much slower than .NET code

问题描述

我有一个性能测试函数的 .NET 和 C++ 实现，它使用 6838 个键池中的字符串键在字典中进行 854,750 次查找.我编写了这些函数来调查真实应用程序中的性能瓶颈.

I have .NET and C++ implementations of a perf test function that does 854,750 lookups in a dictionary using string keys from a pool of 6838 keys. I wrote these functions to investigate a perf bottleneck in a real app.

.NET 实现是用 F# 编写的，使用 Dictionary 并为 .NET 4.0 编译

.NET implementation is written in F#, uses Dictionary and is compiled for .NET 4.0

C++ 实现使用 std::unordered_map 并在发布模式下使用 VS2010 构建.

C++ implementation uses std::unordered_map and is built with VS2010 in Release mode.

在我的机器上，.NET 代码平均运行时间为 240 毫秒，而 C++ 代码运行时间为 630 毫秒.能否请您帮我了解一下造成这种巨大速度差异的原因是什么?

On my machine .NET code runs in 240 ms on average and C++ code runs in 630 ms. Could you please help me to understand what can be the reason for this huge difference in speed?

如果我在 C++ 实现中缩短密钥长度并使用key_"前缀而不是key_prefix_"，它将在 140 毫秒内运行.

If I make key length in C++ implementation shorter and use "key_" prefix instead of "key_prefix_" it will run in 140 ms.

我尝试的另一个技巧是将 std::string 替换为自定义的不可变字符串实现，该实现具有指向源的 const char* 指针和一次性计算的散列.使用此字符串可以将 C++ 实现的性能降低到 190 毫秒.

Another trick I tried is to replace std::string with a custom immutable string implementation that has a const char* pointer to the source and a one-time computed hash. Using this string allowed to get performance of C++ implementation down to 190 ms.

C++ 代码:

struct SomeData
{
public:
    float Value;
};

typedef std::string KeyString;
typedef std::unordered_map<KeyString, SomeData> DictionaryT;

const int MaxNumberOfRuns = 125;
const int MaxNumberOfKeys = 6838;

DictionaryT dictionary;
dictionary.rehash(MaxNumberOfKeys);

auto timer = Stopwatch::StartNew();

int lookupCount = 0;

char keyBuffer[100] = "key_prefix_";
size_t keyPrefixLen = std::strlen(keyBuffer);

/// run MaxNumberOfRuns * MaxNumberOfKeys iterations
for(int runId = 0; runId < MaxNumberOfRuns; runId++)
{
    for(int keyId = 0; keyId < MaxNumberOfKeys; keyId++)
    {
        /// get a new key from the pool of MaxNumberOfKeys keys           
        int randomKeySuffix = (std::rand() % MaxNumberOfKeys);
        ::itoa(randomKeySuffix, keyBuffer + keyPrefixLen, 10);

        KeyString key = keyBuffer;

        /// lookup key in the dictionary         
        auto dataIter = dictionary.find(key);
        SomeData* data;

        if(dataIter != dictionary.end())
        {
            /// get existing value           
            data = &dataIter->second;
        }
        else
        {
            /// add a new value
            data = &dictionary.insert(dataIter, DictionaryT::value_type(key, SomeData()))->second;
        }

        /// update corresponding value in the dictionary
        data->Value += keyId * runId;
        lookupCount++;
    }
}

timer.Stop();
std::cout << "Time: " << timer.GetElapsedMilleseconds() << " ms" << std::endl;
std::cout << "Lookup count: " << lookupCount << std::endl;

打印:

时间:636 毫秒
查找次数:854750

Time: 636 ms
Lookup count: 854750

F# 代码

open System
open System.Diagnostics
open System.Collections.Generic

type SomeData =
    struct
        val mutable Value : float
    end

let dictionary = new Dictionary<string, SomeData>()
let randomGen = new Random()

let MaxNumberOfRuns = 125
let MaxNumberOfKeys = 6838

let timer = Stopwatch.StartNew()

let mutable lookupCount = 0

/// run MaxNumberOfRuns * MaxNumberOfKeys iterations
for runId in 1 .. MaxNumberOfRuns do
    for keyId in 1 .. MaxNumberOfKeys do

        /// get a new key from the pool of MaxNumberOfKeys keys
        let randomKeySuffix = randomGen.Next(0, MaxNumberOfKeys).ToString()        
        let key = "key_prefix_" + randomKeySuffix

        /// lookup key in the dictionary
        let mutable found, someData = dictionary.TryGetValue (key)
        if not(found) then
            /// add a new value
            someData <- new SomeData()
            dictionary.[key] <- someData

        /// update corresponding value in the dictionary
        someData.Value <- someData.Value + float(keyId) * float(runId)

        lookupCount <- lookupCount + 1

timer.Stop()

printfn "Time: %d ms" timer.ElapsedMilliseconds
printfn "Lookup count: %d" lookupCount

打印:

时间:245 毫秒
查找次数:854750

Time: 245 ms
Lookup count: 854750

推荐答案

Visual Studio 2010 对 std::string 使用高性能哈希函数，而不是准确的哈希函数.基本上，如果键字符串大于 10 个字符，哈希函数将停止使用每个字符进行哈希，并且步长大于 1.

Visual Studio 2010 uses a performant hash function for std::string, rather than an accurate one. Basically, if the key string is larger than 10 characters, the hash function stops using every character for the hash, and has a stride greater than 1.

size_t operator()(const _Kty& _Keyval) const
    {   // hash _Keyval to size_t value by pseudorandomizing transform
    size_t _Val = 2166136261U;
    size_t _First = 0;
    size_t _Last = _Keyval.size();
    size_t _Stride = 1 + _Last / 10;

    for(; _First < _Last; _First += _Stride)
        _Val = 16777619U * _Val ^ (size_t)_Keyval[_First];
    return (_Val);
    }

• size() >= 10 - 在第一个
之后每隔一个字符使用一次
• size() >= 20 - 使用第一个
之后的每三个字符
• ...
• size() >= 10 - use every second character after the first
• size() >= 20 - use every third character after the first
• ...

多亏了这一点，冲突发生得更频繁，这当然会减慢代码速度.尝试使用 C++ 版本的自定义哈希函数.

Thanks to this, collisions happen more frequently, which slows the code down of course. Try a custom hash function for the C++ version.

这篇关于C++ ~ 1M 在 unordered_map 中使用字符串键查找的工作比 .NET 代码慢得多的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！