Почему std :: tr1 :: unordered_map медленнее, чем доморощенная хеш-карта?

Question

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

Я использую std :: tr1 :: unordered_map для хранилища, созданного для пользовательской хеш-функции и пользовательской функции равенства. Тип ключа на самом деле char*, а не слишком медленный std::string.

Затем я изменил тот же код, чтобы использовать очень и очень простую хеш-таблицу (на самом деле массив структур {ключ, значение}, проиндексированных хешем) с размером степени два и линейным зондированием для столкновений. Программа стала на 33% быстрее.

Учитывая, что когда я использовал tr1 :: unordered_map, я нажимал на хеш-таблицу, чтобы она никогда не увеличивалась, и что я использовал точно такие же хеш-функции и процедуры сравнения, что делает tr1 :: unordered_map, который замедляет ее на 50% по сравнению с самой простой картой хешей?

Код для типа карты хеша, о котором я говорю как «простой»:

typedef struct dataitem {
    char* item;
    size_t count;
} dataitem_t;

dataitem_t hashtable[HASHTABLE_SIZE] = {{NULL,0}}; // Start off with empty table

void insert(char* item) {
    size_t hash = generate_hash(item);
    size_t firsthash = hash;
    while (true) {
        hash &= HASHTABLE_SIZE_MASK; // Bitmasking effect is hash %= HASHTABLE_SIZE
        if (hashtable[hash].item == NULL) { // Free bucket
            hashtable[hash].item = item;
            hashtable[hash].count = 1;
            break;
        }
        if (strcmp(hashtable[hash].item, item) == 0) { // Not hash collision; same item
            hashtable[hash].count += 1;
            break;
        }
        hash++; // Hash collision.  Move to next bucket (linear probing)
        if (hash == firsthash) {
            // Table is full.  This does not happen because the presizing is correct.
            exit(1);
        }
    }
}

Answer 1

Я хочу расширить ответ @AProgrammer.

Ваша хеш-карта проста, потому что она настраивается в соответствии с вашими потребностями. С другой стороны, std::tr1::unordered_map должен выполнить ряд различных задач, и преуспеть во всех случаях. Это требует подхода средней производительности во всех случаях, поэтому он никогда не будет превосходным в любой конкретной области.

Хэш-контейнеры очень специфичны тем, что есть много способов их реализации, вы выбрали Open-Addressing, в то время как стандарт навязывает подходы для разработчиков. Оба имеют разные компромиссы, и это одна из причин, по которой стандарт на этот раз фактически обеспечил реализацию конкретной реализации: чтобы производительность не сильно изменилась при переключении с одной библиотеки на другую. Простого указания сложности / амортизации Big-O здесь было бы недостаточно.

Вы говорите, что указали unordered_map относительно количества элементов финала, но изменили ли вы коэффициент загрузки? Цепочка, как известно, «плохая» (из-за нехватки памяти) в случае коллизий, и использование меньшего коэффициента загрузки будет способствовать распространению ваших элементов.

В заключение отметим одно отличие: что происходит, когда вы изменяете размер своей хэш-карты? Используя цепочку, unordered_map не перемещает элементы в памяти:

• ссылки на них все еще действительны (даже если итераторы могут быть недействительными)
• в случае больших или сложных объектов вызов конструкторов копирования не производится

Это в отличие от вашей простой реализации , которая может принести O(N) копий (если вы не используете линейную перефразировку для распространения работы, но это определенно не просто).

Следовательно, кажется, что для unordered_map было выбрано сглаживание шипов за счет более медленной средней вставки.

Есть кое-что, что вы можете сделать, хотя бы: предоставить пользовательский распределитель . Записав определенный распределитель для вашего сценария использования, и выделите всю его память за один раз (поскольку вы знаете, сколько объектов будет вставлено, и можете иметь распределитель, сообщающий, сколько памяти является узлом). Затем выделите узлы в виде стека (простое увеличение указателя). Это должно улучшить (несколько) производительность.

Answer 2

Ваша "доморощенная хеш-карта" - это вовсе не хеш-карта, это навязчивый хеш-набор.И это причина того, что это быстрее.Все просто.

Ну, на самом деле навязчивый набор хешей тоже не точен, но это самое близкое совпадение.

Answer 3

В общем, сравнение скорости компонентов, не собранных с одной и той же спецификацией, не справедливо.

Не зная точно, что вы измерили - какой набор операций, какой коэффициент нагрузки, какой набор присутствующих / отсутствующихданные - трудно объяснить, откуда взялась эта разница.

TR1 в g ++ решает коллизию путем цепочки.Это подразумевает динамическое распределение.Но это также дает лучшую производительность при высоком уровне нагрузки.

Answer 4

Ваша "доморощенная" хеш-карта быстрее ¹ , чем std::tr1::unordered_map, потому что, как вы сами сказали, ваша доморощенная хеш-карта "простая" и она неt не проверяет, заполнена ли хеш-таблица .И, возможно, многие вещи, которые вы не проверяете перед операцией.Это может быть причиной того, что ваша хэш-карта быстрее, чем std::tr1::unordered_map.

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

^{1.Я просто предположил, что ваша претензия верна, и, основываясь на ней, я сказал вышеупомянутое.}