Re: [Boost-users] performance of dijkstra_shortest_paths

Subject: Re: [Boost-users] performance of dijkstra_shortest_paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-05-01 14:58:59

On Fri, 1 May 2009, Thomas Klimpel wrote:

> Another question for Andrew: Why was the relaxed heap replaced with a 
> 4-ary heap? In my experience, a normal array based binary heap is a 
> nightmare for the cache, and I wonder whether the 4-ary heap will be 
> much better in this respect. However, I don't know whether the cache 
> behavior of a relaxed heap is much better.

I was the one who changed the default heap type.  The d-ary heap (with d = 
4) was approximately 23% faster on the Dijkstra benchmark (in 
lists/graph/test) on x86.  The d-ary heap does have largely random cache 
behavior (although it only has half the number of levels of a binary 
heap), but it does do some small scans that are contiguous.  Other studies 
(I don't have them off-hand) have also found d-ary heaps to be good for 
Dijkstra's algorithm.  Relaxed heaps are likely to also be bad for the 
cache, as you suggested, because they involve many pointer dereferences; 
they do have asymptotically better behavior than traditional heaps, but 
this benefit seems to be limited by large constants, even on large data 
sets.

-- Jeremiah Willcock