Boost logo

Boost Users :

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

-- Jeremiah Willcock

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at