Куча сопряжения против std :: priority_queue
Я использую реализацию C ++ Pairing Heap, которую я взял отсюда:
http://home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.h
http://home.fnal.gov/~stoughto/build/graphviz-2.22.2/lib/vpsc/pairingheap/PairingHeap.cpp
Я сравнил это PairingHeap с std :: priority_queue
и вот результаты:
gcc 4.7 -O3, ядро i7 2,4 ГГц
Инструкция rdstc для измерения циклов
-------------------------------------------------------------------------------
for 100.000 elements:
o std::priority_queue<int>
- insert: 9,800,415 cycles
- extract: 29,712,818 cycles
- total: 39,513,233 cycles [0.031secs]
o PairingHeap<int>
- insert: 34,381,467 cycles
- extract: 259,986,113 cycles
- total: 294,367,580 cycles [0.125secs]-------------------------------------------------------------------------------for 1.000.000 elements:
o std::priority_queue<int>
- insert: 95,954,533 cycles
- extract: 518,546,747 cycles
- total: 614,501,280 cycles [0.296secs]
o PairingHeap<int>
- insert: 344,453,782 cycles
- extract: 3,856,344,199 cycles
- total: 4,200,797,981 cycles [1.593secs]
-------------------------------------------------------------------------------for 10.000.000 elements:
o std::priority_queue<int>
- insert: 999,836,450 cycles
- extract: 10,634,407,049 cycles
- total: 11,634,243,499 cycles [4.390secs]
o PairingHeap<int>
- insert: 3,441,903,781 cycles
- extract: 61,166,421,272 cycles
- total: 64,608,325,053 cycles [24.187secs]
Куча сопряжения должна быть быстрее, чем std :: priority_queue, потому что она должна быть асимптотически быстрее
операции, но вместо этого здесь кучи сопряжения очень помедленнее.
Я думаю, что это потому, что std :: priority_queue использует вектор под капотами, и это гораздо больше
дружественный к кэшу, чем выделение узлов для каждого целого числа, как это делает куча сопряжения.
Итак, мой вопрос: могут ли асимптотически лучшие структуры данных (в значительной степени) быть побеждены худшими,
только потому, что они гораздо более дружественны к кешу?
Стоит ли тратить много времени на более сложную структуру данных, такую как куча сопряжения, когда
стандартный std :: priority_queue может быть намного быстрее, чем он?
Я просто не учел, что реализация кучи сопряжения, которую я использовал, просто дерьмо,
но, похоже, это не так, потому что другие реализации, которые я пробовал, еще хуже!
Мысли?
Решение
Итак, мой вопрос: могут ли асимптотически лучшие структуры данных (в значительной степени) быть побеждены худшими, только потому, что они гораздо более дружественны к кешу?
Да, это происходит постоянно. Есть и другие причины (постоянные факторы), кроме кеша. Как и другие варианты использования того же слова, асимптотический здесь относится к чему-то (как правило, размер проблемы) собирается бесконечность. Существо, асимптотически лучше, чем B, говорит только, что оно в конце концов лучше, а не то, что это будет лучше (или даже равно) для некоторого заданного значения. Обратите внимание, что для больших наборов данных это соотношение немного улучшается, но этого недостаточно.
Обратите внимание, что даже двоичная куча не слишком удобна для кеша для некоторых больших наборов данных (таких как ваш).
Дочерние и родительские узлы, скорее всего, находятся на совершенно другой странице, так что вы действительно получаете что-то из кеша только для последних нескольких уровней (или если вы получаете доступ к элементам, у которых, похоже, есть похожий путь, но это дано почти любая структура данных).
Существует вариант, называемый B-heap, который улучшает это, но я не смог найти в нем подробностей (только две реализации и рассуждения о том, как модель вычислений в ОЗУ вводит в заблуждение).
Вы должны были бы составить профиль, чтобы быть уверенным, но возможно, что повторное распределение и освобождение занимают значительную часть времени. Распределитель пула (повышение или свернутый вручную поверх std :: vector — который позволяет заменять указатели на целые числа, что может сэкономить некоторое пространство) может значительно снизить эту стоимость.
Реализация также, кажется, использует связанные списки для списка детей, что, вероятно, повреждает кеш еще больше. Массив требует некоторых дополнительных копий, но может быть улучшением на практике.
Стоит ли тратить много времени на более сложную структуру данных, такую как куча сопряжения, когда стандартное std :: priority_queue может быть значительно быстрее, чем оно?
Возможно, что достаточно большой набор данных в сочетании с некоторыми оптимизациями (например, специализированным распределителем и продуманным расположением узлов) перевесит баланс в свою пользу.
В любом случае, это утверждение немного пагубно: если куча сопряжения была быстрее двоичной кучи для ожидаемых сценариев использования, скорее всего, стандартная библиотека будет использовать кучу сопряжения!
Кроме того, по крайней мере на чисто функциональных языках, куча сопряжения довольно проста в реализации (хотя она не будет очень эффективной). Это может быть мало полезно для вас и C ++, но это что-то и бросает вызов «более сложной» части.
Другие решения
Основная проблема здесь — это выделение памяти и да, эффективность кеша.
То, что вы можете попробовать, это реализовать распределитель фиксированного размера с пользовательским operator new + operator delete для PairNode класс для уменьшения накладных расходов (аналогично классу «Более эффективный C ++», пункт 10). Кроме того, этот подход может в конечном итоге стать более дружественным к кешу, так как элементы с большей вероятностью будут иметь локальную ссылку.
Я сделал это с QuadEdge структура (которая страдает от подобных проблем) для триангуляции Делоне и раньше, и увеличение скорости превышало 10-20x IIRC. Если вам нужно сделать распределитель потокобезопасным, тогда вы заплатите за это высокую цену с точки зрения производительности.
Что касается фактического ответа на вопрос о том, является ли производительность лучше в 1 случае или в другом, то вряд ли она будет универсальной, а профилирование на индивидуальной основе — самый простой способ узнать (любой другой метод будет сложным, так как Вы не можете предсказать качество реализации без ее реализации). Мало того, но разные процессоры будут отличаться, и результаты могут зависеть от данных, которые вы стремитесь получить.