D array expansion and non-deterministic re-allocation

[Andrei Alexandrescu]

Denis Koroskin wrote:
> On Fri, 20 Nov 2009 04:13:42 +0300, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> Leandro Lucarella wrote:
>>> dsimcha, el 19 de noviembre a las 23:21 me escribiste:
>>>> Face it, D is a close to the metal language.  Any attempt to define 
>>>> the spec at a
>>>> purely abstract level without reference to any implementation 
>>>> details, and without
>>>> leaving certain details implementation defined is absurd.  I think 
>>>> people need to
>>>> face the fact that you can't have close-to-the-metal flexibility and 
>>>> performance
>>>> and at the same time far-from-the-metal strict separation of 
>>>> specification from
>>>> implementation details.
>>>  Yes, but I think this is a place where you are doing early 
>>> optimization at
>>> the expense of usability. You can always do the slice-thinguie 
>>> yourself if
>>> you are that needed for speed that you can't afford an extra indirection
>>> when using an array (which will be the only overhead if T[new] were
>>> implemented as a pure reference type).
>>>  I think the cost here in terms of usability if far higher than the 
>>> little
>>> performance you loose, specially when you can overcome the issue for 
>>> those
>>> weird cases where you need it.
>>
>> I think one aspect that tends to be forgotten is that built-in arrays 
>> are the lowest abstraction - really just one small step above 
>> pointers. Efficiency lost there is lost forever. That's why I consider 
>> the current design adequate and the proposed designs less so.
>>
>> In other words: you can build a more convenient facility on top of 
>> T[], but you couldn't build a more efficient facility on top of a 
>> convenient one. I think D made the right choice with built-in arrays.
>>
>>
>> Andrei
> 
> Not so true. T[] appends are slow, *very* slow. Whenever I need anything 
> efficient, I always use an additional "size" field (and arr.length is 
> used as capacity). This is tricky, error-prone and not too intuitive to 
> newcomers. As such, it contradicts with all your statements above.

I was speaking somewhat anticipatively; the MRU is slated to accelerate 
append speed while also improving its safety. I have tried in vain to 
convince someone to look into implementing it.

> And there is also a hack to make it work a bit faster:
> 
> T[] arr;
> arr.length = capacity
> arr.length = 0;
> 
> Much to my disgust, having no higher-level abstraction in language core 
> only encourages writing code like this.

I hope that idiom will be put to rest soon.

> TBH, I used to write code like above before, too, but not now. I slowly 
> eliminate everything like this (as well as all the ~= operations) from 
> the code I wrote. It's unpredictable, slow, and leads to hard-to-fix bugs.
> 
> In other words, I disagree with your opinion that D made a right choice 
> with built-in pseudo-arrays.

I really meant to say "will have made".


Andrei