На C# имеется удивительно быстрый словарь (Dictionary), хотелось бы узнать, а имеется ли такой же производительный только на C++ ? Пробовал unordered_map, hash_map, map, но производительность в разы ниже чем у Dictionary сишарповского... P.S: Пара имеет вид
Ответ На самом деле, сравнение языков — штука неблагодарная. Всегда найдутся тесты, на которых один из языков выиграет по сравнению с другим, и всегда найдутся люди, считающие, что данный тест не релевантен и подобный код никогда не будет встречаться в реальности. Тем не менее, я бы не сказал, что результаты ТС очень уж неожиданны: в .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
#include using namespace std int main(int argc, char* argv[]) { map dict int seed = 1 auto begin = clock() for (int i = 0 i < 10000000 i++) { seed = 1664525 * seed + 1013904223 dict.insert(make_pair(seed, i)) } auto end = clock() double elapsedMs = double(end - begin) * 1000.0 / CLOCKS_PER_SEC cout << "elapsed time = " << elapsedMs << " ms, dictionary entries count = " << dict.size() << endl <br> return 0 } Результаты измерений (release mode, 5 запусков подряд без отладчика): C# elapsed time = 1138 ms, dictionary entries count = 10000000 elapsed time = 1127 ms, dictionary entries count = 10000000 elapsed time = 1133 ms, dictionary entries count = 10000000 elapsed time = 1134 ms, dictionary entries count = 10000000 elapsed time = 1129 ms, dictionary entries count = 10000000 C++ elapsed time = 8377 ms, dictionary entries count = 10000000 elapsed time = 8408 ms, dictionary entries count = 10000000 elapsed time = 8377 ms, dictionary entries count = 10000000 elapsed time = 8377 ms, dictionary entries count = 10000000 elapsed time = 8361 ms, dictionary entries count = 10000000 Среднее время: C# = 1132 мс, C++ = 8379 мс. Я не утверждаю, что мои тесты идеальны. Кроме того, они релевантны лишь на моём компьютере. Если кто-то предложит лучшую методику измерения, я с удовольствием применю её тоже. Тем не менее, в моих условиях производительность System.Collections.Generic.Dictionary на добавление элементов существенно превосходит производительность std::map.
Обратите внимание, что Dictionary использует хэш-таблицы, в то время как std::map в моей имплементации использует красно-чёрное дерево в качестве несущей структуры данных. Хэш-таблицы обычно сами по себе быстрее, так что скорость аллокации — не единственная причина лучшей скорости у Dictionary.
Замена в C++ make_pair(seed, i) на pair(seed, i) по совету @igumnov не привела к большому отличию: 8361/8392/8361/8408/8361/8345.
Замена в C++ std::map на std::unordered_map по совету @Котик привела к значительному ускорению: 2230/2230/2230/2230/2246 (среднее 2233). Тем не менее, C++ всё ещё почти вдвое медленнее.
Заменил в C++ std::unordered_map на uthash по совету @igumnov. Результат немного хуже, чем std::unordered_map: 2963/2932/2948/2948/2932. Код: void testUhash() { struct myint { int key int value UT_hash_handle hh } struct myint* dict = NULL int seed = 1 auto begin = clock() for (int i = 0 i < 10000000 i++) { seed = 1664525 * seed + 1013904223 struct myint* ps = (struct myint*)malloc(sizeof(struct myint)) ps->key = seed ps->value = i HASH_ADD_INT(dict, key, ps) } auto end = clock() double elapsedMs = double(end - begin) * 1000.0 / CLOCKS_PER_SEC cout << "elapsed time = " << elapsedMs << " ms, dictionary entries count = " << HASH_COUNT(dict) << endl } <br> Добавил capacity = 10000000 в C++ и для честного сравнения в C# тоже. Изменения: C++: unordered_map dict(10000000) C#: var dict = new Dictionary(10000000) Действительно, стало скорее: C++: 1826/1856/1857/1841/1825, среднее 1841 C#: 790/786/801/790/791, среднее 792 По-прежнему C# более чем вдвое впереди.
По совету @KoVadim убрал вычисление seed (capacity оставил), теперь рабочий цикл таков: C++: for (int i = 0 i < 10000000 i++) { /eed = 1664525 * seed + 1013904223 dict.insert(pair(i, i)) } C#: for (int i = 0 i < 10000000 i++) { /eed = 1664525 * seed + 1013904223 dict.Add(i, i) } Результаты: C++: 1498/1514/1498/1498/1498, среднее 1501 C#: 129/129/135/133/132, среднее 132
По совету @igumnov добавил в бенчмарк khash. Код: KHASH_MAP_INIT_INT(32, int) void testKhash() { int seed = 1 khiter_t iter khash_t(32)* dict = kh_init(32) int dummy auto begin = clock() for (int i = 0 i < 10000000 i++) { seed = 1664525 * seed + 1013904223 iter = kh_put(32, dict, seed, &dummy) kh_value(dict, iter) = i } auto end = clock() double elapsedMs = double(end - begin) * 1000.0 / CLOCKS_PER_SEC cout << "elapsed time = " << elapsedMs << " ms, dictionary entries count = " << kh_size(dict) << endl } <br>Результат: 577/577/608/577/577, среднее 583, массивный вин для нативного кода. Напомню, что лучший результат стандартного .NET-контейнера — 792 мс. Кто предложит кастомный контейнер под .NET?
Попробовал имплементацию для .NET FastDictionary (проект MapReduce.NET). Получилось немного медленнее, чем встроенный Dictionary: 853/865/842/841/842, среднее 849.
Попробовал скорость чистой аллокации для проверки гипотезы @Dith: 10 миллионов раз запускается конструктор пустого класса. Код: C#: static class Allocation { class Foo { } static public void Test() { const int size = 10000000 var timer = new Stopwatch() timer.Start() for (int i = 0 i < size i++) { new Foo() } timer.Stop() Console.WriteLine("elapsed time = {0} ms", timer.ElapsedMilliseconds) } } C++: void testAlloc() { const int size = 10000000 LARGE_INTEGER li if (!QueryPerformanceFrequency(&li)) exit(1) double freq = double(li.QuadPart)/1000.0 QueryPerformanceCounter(&li) auto begin = li.QuadPart for (int i = 0 i < size i++) new Foo() QueryPerformanceCounter(&li) auto end = li.QuadPart double elapsedMs = double(end - begin) / freq cout << "elapsed time = " << elapsedMs << " ms" << endl } <br>Результаты: C#: 58/54/28/55/55 (среднее 50) C++: 407.719/400.693/401.674/401.926/399.976 (среднее 402.4)