On Tuesday, 13 August 2019 at 21:11:41 UTC, H. S. Teoh wrote:
A contiguous allocator doesn't help after the list has
undergone a large number of insertions/deletions, because of
fragmentation.
Fragmentation should not be an issue, I insist on keep using a
DLL for the base structure in my application and create an array
just for sorting operations. No new nodes are added and no nodes
are permanently removed.
You can still get a cache-efficient linked list by chunking.
[...]
I very much appreciate this thought, as I was thinking of adding
such kind of cache to my implementation. It's still in the early
stages and I have yet to see when this would make a considerable
impact. I will remember this.
