Словарь на C++ как (Dictionary) на C#
1,00
р.
На 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
Ответ
На самом деле, сравнение языков — штука неблагодарная. Всегда найдутся тесты, на которых один из языков выиграет по сравнению с другим, и всегда найдутся люди, считающие, что данный тест не релевантен и подобный код никогда не будет встречаться в реальности.
Тем не менее, я бы не сказал, что результаты ТС очень уж неожиданны: в .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)
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)
