Подтвердить что ты не робот

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

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

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

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

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

С#:

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);

С++:

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;
4b9b3361

Ответ 1

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

Ответ 2

Вы измеряете стоимость явного управления памятью. Дополнительные статистические данные здесь. Это также . И попытка Chris Sells добавить детерминированную доработку в CLR.

Ответ 3

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

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

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