Поиск C ++ ~ 1M в unordered_map со строковым ключом работает намного медленнее, чем код .NET

Question

У меня есть реализации .NET и C ++ функции теста perf, которая выполняет 854 750 запросов в словаре, используя строковые ключи из пула из 6838 ключей.Я написал эти функции для исследования узких мест в реальных приложениях.

.NET-реализация написана на F #, использует словарь и скомпилирована для .NET 4.0

C ++-реализация использует std :: unordered_map и создается с VS2010 в режиме Release.

На моей машине .NET-код выполняется в среднем за 240 мс, а код C ++ - за 630 мс.Не могли бы вы помочь мне понять, в чем причина такой огромной разницы в скорости?

Если я уменьшу длину ключа в реализации C ++ и использую префикс "key_" вместо "key_prefix_", он будет работать в 140ms.

Еще одна хитрость, которую я попробовал, - заменить 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

Answer 1

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 ++.

Answer 2

Мы можем только догадываться, почему одна версия быстрее другой.Вы можете определенно использовать профилировщик здесь, чтобы сказать вам, где находится горячая точка.Так что не принимайте это как окончательный ответ.

Ваше замечание о том, что версия c ++ быстрее с более короткой длиной ключа, освещает, потому что это может указывать на несколько вещей:

• Может быть, хеш-функция для std :: string действительно оптимизирована для небольших строк, а не для длинных строк.
• Возможно, более длинная строка занимает больше времени для копирования в unordered_set, потому что отключает оптимизацию небольшой строки в VS 2010библиотека с ++.Таким образом, для копирования в карту требуется выделение.

Вне всяких сомнений, вот некоторые дикие наблюдения, основанные на моем опыте с unordered_map (хотя я больше знаком с реализацией надстройки, чем в Microsoft).

• В этом примере нет причин использовать std :: string в качестве типа ключа, просто используйте целочисленное значение.Это, по-видимому, ускорило бы и версии c ++, и F #.

• Когда вы вставляете значения в карту, вероятно, поиск выполняется с последующей вставкой не быстрее, так как обе требуют повторного хэширования.ключевая строка.Просто использовал оператор [], который самостоятельно выполняет операцию поиска или вставки.Я думаю, это будет зависеть от того, как часто вы находите попадание на карте, а не добавляете новое значение.

• Если распределение является узким местом, и вы должны использовать тип строкового ключа, вы могли бы стать лучшепроизводительность из-за сохранения общего ptr в строку вместо копирования строки при вставке ее в карту.

• Попробуйте предоставить собственную хэш-функцию для типа ключа, который игнорирует "key_prefix_"часть строки

• Попробуйте реализацию boost;может быть, это быстрее.

Опять же, запуск профиля быстро подскажет, где искать подобные проблемы.В частности, он скажет вам, есть ли узкое место в хешировании против узкого места в распределении.

Answer 3

Когда вы имеете дело с чистым кодом структуры данных, соотношение скоростей 2,6 не так уж странно.Взгляните на слайды этого проекта , чтобы понять, что я имею в виду.