C ++〜1M查找在unordered_map与字符串键的工作比.NET代码慢得多 [英] C++ ~ 1M look-ups in unordered_map with string key works much slower than .NET code
问题描述
我有一个perf和c ++ perf测试函数的实现，使用6838键池中的字符串键在字典中执行854,750次查找。我写了这些函数来调查真正的应用程序中的perf瓶颈。
.NET实现是用F＃编写的，使用Dictionary并为.NET 4.0编译。
在我的机器上.NET代码平均运行240 ms，C ++代码运行在630 ms。
如果我在C ++实现中使密钥长度更短，并使用key_前缀代替key_prefix_将在140 ms内运行。
我尝试的另一个技巧是用一个自定义的不可变字符串实现替换std :: string，到源和一次计算散列。使用此字符串允许C ++实现的性能下降到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.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
for（int keyId = 0; keyId< MaxNumberOfKeys; keyId ++）
{
///从MaxNumberOfKeys键池中获取一个新键
int randomKeySuffix =（std :: rand（）％MaxNumberOfKeys）;
:: itoa（randomKeySuffix，keyBuffer + keyPrefixLen，10）;
KeyString key = keyBuffer;
///字典中的查找键
auto dataIter = dictionary.find（key）;
SomeData * data;
if（dataIter！= dictionary.end（））
{
///获取现有值
data =& dataIter-&
}
else
{
///添加一个新值
data =& dictionary.insert（dataIter，DictionaryT :: value_type（key，SomeData ））→第二;
}
///更新字典中的对应值
data->值+ = keyId * runId;
lookupCount ++;
}
}
timer.Stop（）;
std :: cout<< 时间：< timer.GetElapsedMilleseconds（）< ms< std :: endl;
std :: cout<< 查找计数：< lookupCount<< std :: endl;
列印：
时间：636 ms
查找次数：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
$ b let MaxNumberOfRuns = 125
let MaxNumberOfKeys = 6838
let timer = Stopwatch.StartNew（）
让mutable lookupCount = 0
/// run MaxNumberOfRuns * MaxNumberOfKeys迭代
在1中的runId。MaxNumberOfRuns do
for keyId in 1 .. MaxNumberOfKeys do
/// get a来自MaxNumberOfKeys键池的新键
let randomKeySuffix = randomGen.Next（0，MaxNumberOfKeys）.ToString（）
let key =key_prefix_+ randomKeySuffix
///查找键字典
让mutable找到，someData = dictionary.TryGetValue（key）
如果没有找到，则
///添加一个新值
someData< new SomeData（）
dictionary。[key]< - someData
///更新字典中的对应值
someData.Value< - someData.Value + float keyId）* float（runId）
lookupCount < - lookupCount + 1
timer.Stop（）
printfn时间：％d ms timer.ElapsedMilliseconds
printfn查找计数：％dlookupCount
打印： p>
时间：245 ms
查找次数：854750
Visual Studio 2010对 std :: string 使用了一个高效的哈希函数，而不是一个精确的哈希函数。基本上，如果键字符串大于10个字符，散列函数停止使用每个字符作为散列，并且大于 1 。
size_t operator（）（const _Kty& _Keyval）const
{//散列_Keyval到size_t值通过伪随机变换
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- p>感谢这样，碰撞发生更频繁，这当然会减慢代码。尝试使用C ++版本的自定义哈希函数。
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 implementation is written in F#, uses Dictionary and is compiled for .NET 4.0
C++ implementation uses std::unordered_map and is built with VS2010 in Release mode.
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?
If I make key length in C++ implementation shorter and use "key_" prefix instead of "key_prefix_" it will run in 140 ms.
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++ code:
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;
Prints:
Time: 636 ms
Lookup count: 854750
F# code
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
Prints:
Time: 245 ms
Lookup count: 854750
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- use every second character after the firstsize() >= 20- use every third character after the first- ...
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屋！
