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

H. S. Teoh hsteoh at quickfur.ath.cx
Tue Aug 13 18:54:58 UTC 2019


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

-- 
"If you're arguing, you're losing." -- Mike Thomas


More information about the Digitalmars-d-learn mailing list