Take the 2-minute tour ×

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
    float Value;

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

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

DictionaryT dictionary;

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;
            /// add a new value
            data = &dictionary.insert(dataIter, DictionaryT::value_type(key, SomeData()))->second;

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

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


Time: 636 ms
Lookup count: 854750

F# code

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

type SomeData =
        val mutable Value : float

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

        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


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


Time: 245 ms
Lookup count: 854750

share|improve this question
Perhaps using the unordered_map end iterator as the next element hint is hindering performance? –  GWW Dec 4 '11 at 1:44
Are both runs from cold caches or both from hot caches? –  sarnold Dec 4 '11 at 1:45
No removing next element hint does not help :( Both functions run with cold caches. –  evgenyp Dec 4 '11 at 2:28
Have you tried with a memory pool of SomeData? Every insert into a std::map (c++) calls the allocator. I imagine .NET, being garbage collected, simply does pointer arithmetic on the GC heap. –  Ian Thompson Dec 4 '11 at 5:42
add comment

3 Answers

up vote 37 down vote accepted

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 first
  • size() >= 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.

share|improve this answer
Wow, that's a great observation. Thanks! –  karunski Dec 4 '11 at 2:22
Thank you!!! I am embarrassed that I haven't tried it before posting this question. Yeas it worked. With custom hash function C++ perf is about 180ms. Which is ~50 ms faster than .NET. –  evgenyp Dec 4 '11 at 2:33
Interesting if I make a key a little bit longer then performance of both C++ and .NET implementation will be almost the same (~ 260ms on my machine). If I use integer keys than C++ will run in ~35 ms and .NET in ~40 ms. Maybe I will create a .NET implementation of the whole function from the real app where I run this loop (it does some data massaging and computes dot product of multiple vectors) to see how its performance is comparable to the native implementation. –  evgenyp Dec 5 '11 at 7:21
add comment

We can only speculate why one version is faster than the other. You could definitely use a profiler here to tell you where the hot spot is. So don't take any of this as a definitive answer.

Your note about the c++ version being faster with a shorter key length is illuminating because it could point to a couple of things:

  • Maybe the hash function for std::string is really optimized for small strings rather than long strings.
  • Maybe the longer string takes longer to copy into the unordered_set because it disables a small string optimization in VS 2010 c++ library. Thus the copy into the map requires an allocation.

Off the cuff, here's some wild observations based on my experience with unordered_map (though I'm more familiar with the boost implementation that Microsoft's).

  • In this example there's no reason to use a std::string as the key type, just use the integer value. This would presumably make both c++ and F# versions faster.

  • When you insert values into the map, it's probably not faster to do a find followed by an insert since both will require re-hashing the key string. Just used the [] operator, which does a find-or-insert operation on it's own. I guess this would depend on how often you find a hit in the map versus add a new value.

  • If allocation is the bottleneck and you must use a string key type you might get better performance out of storing a shared ptr to the string rather than copying the string when you insert it into the map.

  • Try providing your own hash function for the key type that ignores the "key_prefix_" part of the string

  • Try boost's implementation; maybe it's faster.

Again, a profile run would quickly tell you where to look for this kind of problem. Specifically, it will tell you if there's a bottleneck in hashing vs. a bottleneck in allocation.

share|improve this answer
Thank you. I've already tried some of your suggestions. I will try to run it under profiler. I was frustrated because I wrote that method in C++ naively expecting that C++ implementation will beat .NET one out of the box and then I will tune it make it run even faster. –  evgenyp Dec 4 '11 at 2:25
On the small-string optimization: Rather than degrade, it should improve performance, since the small-string optimization needs to copy all characters. If it is no small string, it can just swap pointers, or move the string (VS2010 is already move aware). –  Xeo Dec 4 '11 at 2:29
Yes integer keys work much much faster. I used strings because this is what I have in my real app. I wish I could use integers there, but right now it is not possible. –  evgenyp Dec 4 '11 at 2:35
@Xeo Ah I wasn't taking move semantics into account. –  karunski Dec 4 '11 at 2:41
add comment

When you're dealing with pure data-structure code, a speed ratio of 2.6 is not that strange. Take a look at the slides on this project to see what I mean.

share|improve this answer
add comment

Your Answer


