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

[Mike Parker]

On Tuesday, 13 August 2019 at 22:12:23 UTC, Mirjam Akkersdijk 
wrote:

> Though, it left me with some semi-offtopic questions unanswered:
>
> (1) Ali, do you mean that from an optimization viewpoint, it's 
> better to keep appending like `nodes ~= ...` instead of setting 
> the length first? I would like to have some more background on 
> that claim.

He's not saying it will be better, but that the cost will be 
negligible. On every append, the GC allocates new memory only if 
the current capacity == 0. When it does allocate, it allocates 
more space than it actually needs based on the current length of 
the array, so you don't actually have an allocation on every 
append. Also, when the adjacent memory block is free and can hold 
the additional elements, the allocation consists of extending the 
array's memory block and no copying is performed, making the cost 
of the allocation even cheaper than it could be.

Anyway, you can use `reserve` when appending rather than setting 
the length. This will allocate enough memory without 
default-initializing anything and you don't have to worry about 
bounds checking.

int[] ints;
ints.reserve(100);
foreach(i; 0..100) {
     ints ~= i;
}


See Steve Schveighoffer's array article for details:

https://dlang.org/articles/d-array-article.html