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

[Ali Çehreli]

On 08/13/2019 03:12 PM, Mirjam Akkersdijk wrote:

 > For the application I am writing, it makes very much sense to use a DLL.

Yes, Dynamically Linked Libraries can be useful. Oh wait... You mean 
Doubly-Linked List. :o)

 > I tried setting the length first and iterating through it with `nodes[i]
 > = ...`

As Mike Parker said, it should be .reserve.

 > and the implementation did not run noticeably faster (10 trials),

That's the most important part: You profiled and it was the same. 
(Although, profiling is tricky business as well; it can be difficult to 
measure the operation that you are interested in.)

The performance will depend on many factors:

* First, if there aren't many number of nodes it shouldn't matter. 
(That's why I would choose the simpler arrays.)

* Doubly-linked list nodes will have two extra pointers per element. As 
a general rule, larger the data slower the data structure.

* Pointer chasing through 'next' pointers will make the program jump 
around in memory. This will be slower compared to consecutive elements 
that arrays provide. But if processing the elements cause pointer 
chasing anyway, then it shouldn't matter much. Another topic to read and 
watch is "data oriented programming". This talk by Mike Acton is eye 
opening:

   https://www.youtube.com/watch?v=rX0ItVEVjHc

* Is data appended and removed throughout the life of the program or are 
the nodes set once in the beginning and then only used?

* Are elements accessed randomly or always in sequence. (If the latter, 
modern CPUs promise that arrays will be better.)

* etc.

Ali