c # to c ++ словарь для результатов unordered_map

Question

Я уже несколько лет занимаюсь c # и пытаюсь выучить что-то новое. Поэтому я решил взглянуть на c ++, чтобы познакомиться с программированием по-другому.

Я много читал, но сегодня начал писать код.

На моем компьютере с Windows 7/64, работающем под VS2010, я создал два проекта: 1) C # проект, который позволяет мне писать вещи, как я привык. 2) c ++ "makefile" проект, который позволяет мне поиграть, пытаясь реализовать то же самое. Насколько я понимаю, это не проект .NET.

Я пытался заполнить словарь значениями 10К. По какой-то причине c ++ работает на несколько порядков медленнее.

Вот c # ниже. Примечание Я добавил функцию после измерения времени, чтобы компилятор не «оптимизировал» его:

var freq = System.Diagnostics.Stopwatch.Frequency;

int i;
Dictionary<int, int> dict = new Dictionary<int, int>();
var clock = System.Diagnostics.Stopwatch.StartNew();

for (i = 0; i < 10000; i++)
     dict[i] = i;
clock.Stop();

Console.WriteLine(clock.ElapsedTicks / (decimal)freq * 1000M);
Console.WriteLine(dict.Average(x=>x.Value));
Console.ReadKey(); //Don't want results to vanish off screen

Вот с ++ , в него не особо задумывались (пытаясь учиться, верно?) int input;

LARGE_INTEGER frequency;        // ticks per second
LARGE_INTEGER t1, t2;           // ticks
double elapsedTime;

// get ticks per second
QueryPerformanceFrequency(&frequency);

int i;
boost::unordered_map<int, int> dict;
// start timer
QueryPerformanceCounter(&t1);

for (i=0;i<10000;i++)
    dict[i]=i;

// stop timer
QueryPerformanceCounter(&t2);

// compute and print the elapsed time in millisec
elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;
cout << elapsedTime << " ms insert time\n";
int input;
cin >> input; //don't want console to disappear

Теперь несколько предостережений. Мне удалось найти связанный с этим вопрос. Один из парней написал длинный ответ, упомянув, что WOW64 искажает результаты. Я настроил проект на выпуск и прошел через вкладку «свойства» проекта c ++, включив все, что звучало так, как это, сделает его быстрым. Изменил платформу на x64, хотя я не уверен, решает ли это его проблему с wow64. Я не настолько опытен с опциями компилятора, может, вы, ребята, больше разбираетесь в этом?

Да, и результаты: c #: 0,32 мс C ++: 8,26 мс. Это немного странно. Я что-то неправильно истолковал о том, что означает .Quad? Я скопировал код таймера c ++ из какого-то места в сети, прошел все установки boost и включил / libfile rigmarole. Или, может быть, я невольно использую разные инструменты? Или есть какой-то критический вариант компиляции, который я не использовал? Или, может быть, код C # оптимизирован, потому что среднее значение является константой?

Вот командная строка c ++, со страницы свойств-> C / C ++ -> Командная строка: / I "C: \ Users \ Carlos \ Desktop \ boost_1_47_0" / Zi / nologo / W3 / WX- / MP / Ox / Oi / Ot / GL / D "_MBCS" / Gm- / EHsc / GS- / Gy- / arch: SSE2 / fp: fast / Zc: wchar_t / Zc: forScope /Fp"x64\Release\MakeTest.pch "/ Fa" x64 \ Release \ "/ Fo" x64 \ Release \ "/ Fd" x64 \ Release \ vc100 .pdb "/ Gd / errorReport: очередь

Любая помощь будет оценена, спасибо.

Answer 1

Простое изменение распределителя значительно сократит это время.

boost::unordered_map<int, int, boost::hash<int>, std::equal_to<int>, boost::fast_pool_allocator<std::pair<const int, int>>> dict;

0,9 мс в моей системе (с 10 мс до).Это наводит меня на мысль о том, что на самом деле подавляющее большинство вашего времени вообще не проводится в хеш-таблице, а в распределителе.Причина, по которой это несправедливое сравнение, заключается в том, что ваш сборщик мусора никогда не соберется в такой тривиальной программе, что дает ему неоправданное преимущество в производительности, а встроенные распределители выполняют значительное кеширование свободной памяти, но это никогда не вступит в игру в такой тривиальной ситуации.Например, потому что вы никогда ничего не выделяли и не освобождали и поэтому кешировать нечего.

Наконец, реализация пула Boost является поточно-ориентированной, тогда как вы никогда не играете с потоками, поэтому GC может просто вернуться коднопотоковая реализация, которая будет намного быстрее.

Я прибег к ручному, не освобождающему, не поточно-ориентированному распределителю пула и опустился до 0,525 мс для C ++ до 0,45 мс для C # (включенмоя машина).Вывод: Ваши исходные результаты были очень искажены из-за различий в схемах распределения памяти двух языков, и после их устранения разница становится относительно минимальной.

Пользовательский хеш (как описано в ответе Александра) упалмое C ++ время до 0,34 мс, что теперь быстрее, чем C #.

static const int MaxMemorySize = 800000;
static int FreedMemory = 0;
static int AllocatorCalls = 0;
static int DeallocatorCalls = 0;
template <typename T>
class LocalAllocator
{
  public:
      std::vector<char>* memory;
      int* CurrentUsed;
      typedef T value_type;
      typedef value_type * pointer;
      typedef const value_type * const_pointer;
      typedef value_type & reference;
      typedef const value_type & const_reference;
      typedef std::size_t size_type;
      typedef std::size_t difference_type;

    template <typename U> struct rebind { typedef LocalAllocator<U> other; };

    template <typename U>
    LocalAllocator(const LocalAllocator<U>& other) {
        CurrentUsed = other.CurrentUsed;
        memory = other.memory;
    }
    LocalAllocator(std::vector<char>* ptr, int* used) {
        CurrentUsed = used;
        memory = ptr;
    }
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) {
        CurrentUsed = other.CurrentUsed;
        memory = other.memory;
    }
    pointer address(reference r) { return &r; }
    const_pointer address(const_reference s) { return &r; }
    size_type max_size() const { return MaxMemorySize; }
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); }
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); }
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); }

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; }
    bool operator!=(const LocalAllocator&) const { return false; }

    pointer allocate(size_type count) {
        AllocatorCalls++;
        if (*CurrentUsed + (count * sizeof(T)) > MaxMemorySize)
            throw std::bad_alloc();
        if (*CurrentUsed % std::alignment_of<T>::value) {
            *CurrentUsed += (std::alignment_of<T>::value - *CurrentUsed % std::alignment_of<T>::value);
        }
        auto val = &((*memory)[*CurrentUsed]);
        *CurrentUsed += (count * sizeof(T));
        return reinterpret_cast<pointer>(val);
    }
    void deallocate(pointer ptr, size_type n) {
        DeallocatorCalls++;
        FreedMemory += (n * sizeof(T));
    }

    pointer allocate() {
        return allocate(sizeof(T));
    }
    void deallocate(pointer ptr) {
        return deallocate(ptr, 1);
    }
};
int main() {
    LARGE_INTEGER frequency;        // ticks per second
    LARGE_INTEGER t1, t2;           // ticks
    double elapsedTime;

    // get ticks per second
    QueryPerformanceFrequency(&frequency);
    std::vector<char> memory;
    int CurrentUsed = 0;
    memory.resize(MaxMemorySize);

    struct custom_hash {
        size_t operator()(int x) const { return x; }
    };
    boost::unordered_map<int, int, custom_hash, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
        std::unordered_map<int, int>().bucket_count(),
        custom_hash(),
        std::equal_to<int>(),
        LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed)
    );

    // start timer
    std::string str;
    QueryPerformanceCounter(&t1);

    for (int i=0;i<10000;i++)
        dict[i]=i;

    // stop timer
    QueryPerformanceCounter(&t2);

    // compute and print the elapsed time in millisec
    elapsedTime = ((t2.QuadPart - t1.QuadPart) * 1000.0) / frequency.QuadPart;
    std::cout << elapsedTime << " ms insert time\n";
    int input;
    std::cin >> input; //don't want console to disappear
}

Answer 2

Вы можете попробовать dict.rehash(n) с различными (большими) значениями n перед вставкой элементов и посмотреть, как это влияет на производительность.Выделение памяти (оно происходит, когда контейнер заполняет сегменты), как правило, дороже в C ++, чем в C #, и перефразировка также тяжелая.Для std::vector и std::deque аналоговая функция-член reserve.

Различные политики перефразирования и пороговое значение коэффициента загрузки (взгляните на max_load_factor функцию-члена) также окажут значительное влияние на unordered_mapпроизводительность.

Далее, поскольку вы используете VS2010, я предлагаю вам использовать std::unordered_map из заголовка <unordered_map>.Не используйте boost, когда вы можете использовать стандартную библиотеку.

Реальная используемая хеш-функция может сильно повлиять на производительность.Вы можете попробовать следующее:

struct custom_hash { size_t operator()(int x) const { return x; } };

и использовать std::unordered_map<int, int, custom_hash>.

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

Answer 3

Хранение последовательной последовательности числовых целых ключей, добавленных в порядке возрастания, определенно НЕ является тем, для чего оптимизированы хеш-таблицы.

Использовать массив или генерировать случайные значения.

И сделать несколько поисков. Хеш-таблицы высоко оптимизированы для поиска.

Answer 4

Visual Studio TR1 unordered_map совпадает с stdext :: hash_map:

Другой поток, спрашивающий, почему он работает медленно, смотрите мой ответ со ссылками на других, которые обнаружили ту же проблему.Вывод заключается в использовании другой реализации hash_map в C +++:

Альтернатива stdext :: hash_map по соображениям производительности

Кстати.помните, что в C ++ существует большая разница между оптимизированной версией сборки и неоптимизированной версией сборки отладки по сравнению с C #.