Сопряжения Heap против станда :: priority_queue

Question

Я Трингом реализации в C++ из спаривания 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 против станда :: priority_queue и эти результаты:

НКУ 4,7 -O3, ядро ​​i7 2.4Ghz инструкция 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 может в значительной степени быстрее, чем он?

Я просто не считал, что реализация кучи спаривания, которую я использовал, просто дерьмо, , но, похоже, это не так, потому что другие реализации, которые я пробовал, еще хуже! Мысли?

Answer 1

Итак, мой вопрос: могут ли асимптотически лучшие структуры данных быть (в основном) избиты худшими, просто потому, что они гораздо более удобны для кеширования?

Да, это происходит постоянно. Существуют и другие причины (постоянные факторы) помимо удобства кэш-памяти.Как и в других применениях одного и того же слова, асимптотический здесь относится к чему-то (обычно, размер проблемы), идущему в infinity. А асимптотически лучше, чем B, только говорит, что будет в конечном итоге быть лучше, не то, чтобы он был лучше (или даже равен) для некоторого заданного значения. Обратите внимание, что соотношение действительно улучшает бит для больших наборов данных, этого недостаточно.

Обратите внимание, что даже двоичная куча не слишком кэширована для нескольких больших наборов данных (таких как ваши). . У детей и родителей узла, вероятно, будет совершенно другая страница, поэтому вы действительно получите что-то из кеша на последних нескольких уровнях (или если вы обращаетесь к элементам, которые имеют похожий путь, но это указано в почти любая структура данных). Существует вариант, названный B-heap, который улучшает это, но я не смог найти много подробностей (просто две реализации и раздумья о том, как модель RAM вычислений вводит в заблуждение).

У вас должен быть профиль, чтобы быть уверенным, но вполне возможно, что повторное выделение и освобождение занимает значительную часть времени. Распределитель пула (boost или hand-rollted one atop of std :: vector), который позволяет заменять указатели целыми числами, что может сэкономить некоторое пространство), может значительно снизить эту стоимость. Реализация также, по-видимому, использует связанные списки для списка детей, что, вероятно, еще больше вредит кешу. Массив требует некоторых дополнительных копий, но может быть улучшением на практике.

Действительно ли стоит потратить много времени на более сложную структуру данных, такую ​​как куча спаривания, когда по умолчанию std :: priority_queue может в значительной степени быть быстрее, чем он?

Возможно, что достаточно большой набор данных в сочетании с некоторыми оптимизациями (например, специализированным распределителем и умным расположением узлов) подскажет баланс в его пользу. В любом случае это утверждение немного самонадеянно: если куча спаривания была быстрее, чем двоичная куча для ожидаемых вариантов использования, скорее всего, стандартная библиотека будет использовать кучу спаривания!

Кроме того, по крайней мере, на чисто функциональных языках куча сопряжения довольно проста для реализации (хотя она не будет очень эффективной). Это может быть мало пользы для вас и C++, но это что-то и бросает вызов «более сложной» части.

Answer 2

Основная проблема заключается в распределении памяти и эффективности кэша.

Что вы могли бы попробовать это реализовать аллокатор фиксированного размера с обычаем operator new + operator delete для PairNode класса для уменьшения выделения накладных расходов (аналогично тому, в «более эффективных C++», пункт 10). Кроме того, этот подход может оказаться более дружественным к кеш, поскольку элементы с большей вероятностью будут иметь локальность ссылки.

Я сделал это с помощью структуры QuadEdge (которая испытывает аналогичные проблемы) для триангуляции Delaunay раньше и увеличение скорости превышало 10-20x IIRC. Если вам нужно сделать потокобезопасный распределитель, тогда вы заплатите за это высокую стоимость за производительность.

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