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