You could use a tree for that, but my understanding is that a heap is
much
more efficient?
Yes. I have a feeling dcollections will use heap from phobos (to avoid
duplication) for a full priority queue.
-Steve
I tried a Fibonacci tree. It didn't beat the good old array based priority
queue. And the more I read about garbage collection and CPU L1/L2 caches,
my understanding is that packed arrays and indexes are the best choice if
the amount of data is not too much.
I did a test with a circular linked list. As long as it is correctly
ordered in memory, the CPU is able to prefetch everything into L1 by the
time the next pointer is read, independent of the byte count. It could be
a few KB up to a GB.
But when I randomly reordered the locations of the list nodes in memory it
was up to 80x slower for the cases from several MB on. It only stayed fast
as long as the complete data fit into the L1 cache. So what I learned from
that is to avoid pointers to memory outside the current allocation block
and to use a ushort now and then where appropriate ^^. I hope these didn't
get slower on amd64.
