Phobos 'collections' question

[Marco Leise]

>> 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.