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

[H. S. Teoh]

On Tue, Aug 13, 2019 at 12:12:28PM -0600, Jonathan M Davis via Digitalmars-d-learn wrote:
> On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via 
> Digitalmars-d-learn wrote:
[...]
> > Thank you, this is what I eventually chose to do. It's also fairly
> > fast, though doesn't the nature of the dynamic array slow it down a
> > bit? Since I already know the size of the array (but just not at
> > compile time), can't I define an array of fixed size, which is
> > dependent on the input of the function?
> 
> In D, static arrays must know their length at compile time. Dynamic
> arrays can have their length determined at runtime. I don't know why a
> dynamic array would slow anything down here though - especially if you
> just allocate it with the correct length.
[...]

When it comes down to fine points concerning performance like here, my
default response is: are you sure this is an *actual* performance hit?
Did you run a profiler to measure the actual runtimes?

Static arrays have the advantage that the size is known at compile-time,
so the compiler can generate better code (by hard-coding the length,
optimizing the memory layout, etc.).  But when you pass static arrays
around, you have to either slice them, in which case they become
identical to dynamic arrays anyway, or pass them on the stack, which in
some cases can actually slow things down (you have to copy a potentially
large amount of data to/from the stack when passing arguments to a
function). Passing a dynamic array (or a slice of a static array) is
very fast: it's just a pointer + size pair.

Dynamic arrays could potentially incur performance hits if you're
appending to them (may need a GC allocation).  Static arrays don't have
this problem -- but then you can't append to a static array at all. :-P

Anyway, splitting hairs over whether to use static arrays or dynamic
arrays sounds like premature optimization to me.  Before worrying about
potential performance problems with using dynamic arrays, always use a
profiler to see if the bottleneck is actually in that part of the code.
Otherwise it's just a waste of time and energy to "optimize" the code
when it isn't even anywhere near the real bottleneck(s) in the program.

Profile, profile, profile. Until then, don't sweat it over optimization.


T

-- 
Mediocrity has been pushed to extremes.