Хэш-таблица быстрее на С#, чем на С++?

Вот любопытство, которое я исследовал. Класс .NET Dictionary работает смехотворно быстро по сравнению с unordered_map STL в тесте, который я продолжаю выполнять, и я не могу понять, почему.

(0,5 секунды против 4 секунд на моей машине) (.NET 3.5 SP1 по сравнению с Visual Studio 2008 Express SP1 STL)

С другой стороны, если я реализую свою собственную хэш-таблицу на C# и C++, версия C++ примерно в два раза быстрее, чем версия C#, и это нормально, потому что это подкрепляет мой здравый смысл в том, что собственный машинный код иногда быстрее. (Видите. Я сказал «иногда».) Поскольку я один и тот же человек, говорящий на обоих языках, мне интересно, какие уловки мог проделать кодировщик C# из Microsoft, чего не смог программист C++ из Microsoft? Мне трудно представить, как компилятор может проделывать такие трюки сам по себе, преодолевая трудности с оптимизацией того, что должно выглядеть как произвольные вызовы функций.

Это простой тест, сохраняющий и извлекающий целые числа.

C#:

const int total = (1 << 20);
int sum = 0;
Dictionary<int, int> dict = new Dictionary<int, int>();
for(int i = 0; i < total; i++)
{
    dict.Add(i, i * 7);
}

for(int j = 0; j < (1 << 3); j++)
{
    int i = total;
    while(i > 0)
    {
        i--;
        sum += dict[i];
    }
}
Console.WriteLine(sum);

C++:

const int total = (1 << 20);
int sum = 0;
std::tr1::unordered_map<int, int> dict;
for(int i = 0; i < total; i++)
{
    dict.insert(pair<int, int>(i, i * 7));
}

for(int j = 0; j < (1 << 3); j++)
{
    int i = total;
    while(i > 0)
    {
        i--;
        std::tr1::unordered_map<int, int>::const_iterator found =
            dict.find(i);
        sum += found->second;
    }
}
cout << sum << endl;

person Matthew    schedule 13.12.2009    source источник
comment
Является ли версия C++ типизированной как Dictionary‹T›?   -  person Cory Charlton    schedule 14.12.2009
comment
Родной машинный код быстрее чего? Как вы думаете, как работает C#?   -  person David M    schedule 14.12.2009
comment
как вы измеряете производительность?   -  person stefanB    schedule 14.12.2009
comment
Любопытно, запускаете ли вы код в сборке релиза. Реализация MS STL общеизвестно медленна в отладочных сборках из-за большого количества дополнительных проверок.   -  person imaginaryboy    schedule 14.12.2009
comment
@imaginaryboy, MS не единственный, кто страдает от этого. Переключение с отладки на выпуск с использованием XCode почти удваивает производительность приведенного выше кода C++.   -  person Glen    schedule 14.12.2009
comment
Вау, это сверхъестественно, как я только что столкнулся с таким же наблюдением. Хотел написать вопрос, но так как вы написали то же самое, я просто скажу спасибо!   -  person Carlos    schedule 07.08.2011


Ответы (3)


две версии не эквивалентны, вы создаете итератор в каждом проходе вашего цикла C++ while. это занимает процессорное время и выдает ваши результаты.

person Alon    schedule 13.12.2009
comment
Согласен - попробуйте заменить dict.insert(pair‹int, int›(i, i * 7)); с dict[i] = i * 7; Одним уровнем гука меньше. - person Chris Tonkinson; 14.12.2009
comment
Это, и они используют оператор массива в версии C# и метод find() в версии C++. - person Glen; 14.12.2009
comment
@Glen: оператор массива представляет собой синтаксическое удобство, которое вызывает метод FindEntry. У него нет преимущества в скорости. - person Ben M; 14.12.2009
comment
@ Бен, нигде в моей версии STL нет метода FindEntry. Кроме того, реализации оператора индекса и метода поиска сильно различаются, что заставляет меня поверить, что один из них может работать совершенно иначе, чем другой. Я не уверен, что предполагается, но надлежащий тест производительности должен показать это довольно легко. - person Glen; 14.12.2009
comment
@ Бен, если вы имели в виду оператор нижнего индекса C #, извините, я неправильно его понял. Однако ОП должен пытаться писать правильный код в обеих реализациях, а не сравнивать хороший код С# со средней реализацией С++. - person Glen; 14.12.2009

Вы измеряете стоимость явного управления памятью. Дополнительные статистические данные доступны здесь. Это тоже актуально и Попытка Криса Селлса добавить детерминированную финализацию в среду CLR заслуживает внимания.

person Hans Passant    schedule 13.12.2009

Будут некоторые отличия на уровне кода: тот факт, что неупорядоченная карта принимает пару, вынуждает создавать такой объект, в то время как C# может быть быстрее с передачей двух параметров в Add.

Другим моментом является реализация самих хеш-таблиц: реализация функции хеширования или способ обработки коллизий вызовет разные модели производительности.

Добавьте к этому выравнивание и кэширование, JIT-совместимость некоторых алгоритмов, и сравнение двух разных реализаций на двух разных языках становится очень сложным, и единственное, что вы можете сравнить, это конкретная задача. Попробуйте с меньшим или большим количеством элементов или попробуйте получить доступ к элементам случайным образом, а не последовательно, и вы можете увидеть совсем другие результаты.

person small_duck    schedule 13.12.2009