How should I sort a doubly linked list the D way?

[Max Haughton]

On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote:
> On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via 
> Digitalmars-d-learn wrote: [...]
>> Summary: Ditch the linked list and put the elements into an 
>> array. :)
> [...]
>
> +1.  The linked list may have been faster 20 years ago, before 
> the advent of modern CPUs with caching hierarchies and memory 
> access predictors.
>
> These days, with CPU multi-level caches and memory access 
> predictors, in-place arrays are often the best option for 
> performance, up to a certain size.  In general, avoid 
> indirection where possible, in order to avoid defeating the 
> memory access predictor and reduce the number of cache misses.
>
>
> T

I saw a Bjarne Stroustrup talk where he benchmarked that the for 
n > 1, std::vector was a lot faster than a linked list for all 
supported operations. I don't know how clever the caching 
strategies are on a modern processor (Pointer chasing), but to my 
knowledge the only way of getting a cache efficient linked list 
would be to effectively have a very contiguous allocator (Which 
obviously defeats the purpose of using a list in the first place)

Found it: https://www.youtube.com/watch?v=YQs6IC-vgmo