Словарь на C++ как (Dictionary) на C#

На C# имеется удивительно быстрый словарь (Dictionary), хотелось бы узнать, а имеетс
ли такой же производительный только на C++ ? Пробовал unordered_map, hash_map, map, но производительность в разы ниже чем у Dictionary сишарповского...
P.S: Пара имеет вид 
    

Ответы

Ответ 1

На самом деле, сравнение языков -- штука неблагодарная. Всегда найдутся тесты, н
которых один из языков выиграет по сравнению с другим, и всегда найдутся люди, считающие, что данный тест не релевантен и подобный код никогда не будет встречаться в реальности.
Тем не менее, я бы не сказал, что результаты ТС очень уж неожиданны: в .NET действительн
выделение памяти обычно происходит быстрее, чем в нативных языках без кастомного аллокатора. А небольшие тесты обычно гораздо больше нагружают аллокатор чем, скажем, механизмы вызова функций.
Причиной такой разницы в производительности аллокатора является то, что объекты C+
невозможно перемещать в памяти, а значит, привычный алгоритм выделения памяти (который
как известно, поддерживает список свободных блоков, и ищет подходящий при аллокации
работает довольно медленно, и, хуже того, требует глобальной блокировки памяти (что ещё более ухудшает ситуацию в многопоточном сценарии). Кроме того, объекты в C++ имеют тенденцию освобождаться быстро как только можно, что приводит к дополнительной нагрузке на освобождение памяти, которое тоже требует глобальную блокировку.
В среде .NET же всё происходит по-другому. Объекты всегда выделяются на вершине heap-памяти
а значит, выделение не медленнее, чем InterlockedIncrement. .NET'у не нужно поддерживать список свободных блоков потому, что при сборке мусора происходит компактификация heap-памяти: объекты перемещаются, заполняя "дыры".

Кроме того, известия о том, что код на C++ вполне может быть медленнее аналогичног
кода на C#, давно не новость. Вот, например, замечательная серия статей о простом приложении от мастеров нативного программирования, и резюме Джефа Этвуда:

Чтобы обойти по производительности версию на C#, Реймонду пришлось написать собственны
процедуры ввода-вывода, переписать класс string, воспользоваться кастомным аллокатором, а также собственной процедурой отображения кодовых страниц.

Это подтверждается и бенчмарком, который приведён ниже: нативные контейнеры "из коробки" существенно проигрывают дотнетовским, (некоторые) самописные контейнеры выигрывают.

Теперь самое интересное: измерения.
C#:
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Sharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var dict = new Dictionary();
            int seed = 1;

            var timer = new Stopwatch();
            timer.Start();

            for (int i = 0; i < 10000000; i++)
            {
                seed = 1664525 * seed + 1013904223;
                dict.Add(seed, i);
            }

            timer.Stop();
            Console.WriteLine(
                "elapsed time = {0} ms, dictionary entries count = {1}",
                timer.ElapsedMilliseconds,
                dict.Count);
        }
    }
}

C++:
#include "stdafx.h"
#include 
#include