C++ ~ 1M 在 unordered_map 中使用字元串鍵查找比 .NET 程式碼慢得多

我有一個性能測試函式的 .NET 和 C++ 實現，該函式使用來自 6838 個鍵的池中的字元串鍵在字典中進行 854,750 次查找。我編寫了這些函式來調查實際應用程序中的性能瓶頸。

.NET 實現是用 F# 編寫的，使用 Dictionary 並針對 .NET 4.0 編譯

C++ 實現使用 std::unordered_map 並在發布模式下使用 VS2010 建構。

在我的機器上，.NET 程式碼平均執行 240 毫秒，C++ 程式碼執行 630 毫秒。您能否幫助我了解造成這種速度巨大差異的原因是什麼？

如果我在 C++ 實現中縮短密鑰長度並使用“key_”前綴而不是“key_prefix_”，它將在 140 毫秒內執行。

我嘗試的另一個技巧是將 std::string 替換為自定義的不可變字元串實現，該實現具有指向源的 const char* 指針和一次性計算的雜湊值。使用此字元串可以將 C++ 實現的性能降低到 190 毫秒。

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

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

Visual Studio 2010 對 使用高性能散列函式std::string，而不是準確的散列函式。基本上，如果鍵字元串大於 10 個字元，散列函式將停止使用每個字元進行散列，並且步幅大於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- 在第一個字元之後使用每三個字元
• …

由於這一點，衝突發生得更頻繁，這當然會減慢程式碼速度。嘗試 C++ 版本的自定義雜湊函式。

引用自：https://stackoverflow.com/questions/8372579