Memory leak with dynamic array

[bearophile]

Steven Schveighoffer:

Thank you for your answers Steven, I always appreciate your efforts in both trying to improve D runtime and in teaching me :-)

The new dynamic array regime has the main advantage of avoiding some stomping-related bugs (a secondary advantage is a little higher append speed). One its disadvantage is its increased complexity, that makes it harder for the programmer to understand what dynamic arrays are actually doing under the cover. Sometimes you don't need to know what's happening under the cover, but in this case arrays are so basic and common data structures, and their abstraction is leaking so much, that I think a D programmer must know what's happening inside them to use them at their best.


> >   C++ v1: 0.67
> >   C++ v1: 0.72

That the 0.72 timing was from the second C++ program, sorry.


> That is to be expected.  The append function is not the most efficient  
> thing.  It still must do a lot of work just to look up the valid length  
> and verify appending can be done, whereas the v2 "append" is a single  
> instruction!

The v2 "append" seems two instructions:
arr[arr_len] = j;
arr_len++;

And the C++ v1 too has to verify if the appending can be done, comparing the size with the capacity and if so assigning the item and increasing the size.
I understand that the D code has to work more here, and I presume your code can't be improved. But those timings are a little sad anyway :-|


> A better method is to set the length, and then write the data.

What I have done in the D v2 example.


>0 means if you append to the array, it will reallocate.  It will return 0  
for stack-allocated arrays also.  This makes sense since the slice has  
taken over the "allocated" length of the block.  Essentially, capacity  
indicates how many elements can be appended.  The function gives up and  
returns 0 if it determines the array does not end at the allocated part of  
a block.<
>For fun, add one more element to slice, and the arr will now have a valid capacity :)<

I will have to read this some more times, and probably I will have to read the source code of the append implementation :-)


>Technically, I could return the length of the array, but I'm not sure whether that is as useful.<

I like this.


>FYI, using arr after assuming safe append on the slice is undefined.<

/me nods.

Can you please write a short page, to be added to the D site (for example in the "Articles" section) that explains the data structures used under the cover by the dynamic arrays and how such data structures work (and maybe why this is the chosen design of arrays instead of other possible designs, how it iteracts with the current GC)? The purpose of this short text is to help D programmers understand what and why dynamic arrays work this way in their programs. Dynamic arrays are among the most common data structure in D programs, so they are pretty important and basic.

If you are willing to write a first draft of this small document I can offer you any kind of help you want, for example I can read and comment your text, fix typos, convert it to html, I can even draw for you small data structures with their little pointers, I can beg Walter to add the resulting html page to his site, and so on :-) It's not a big work, despite all it can't be a very complex data structure.

Bye and thank you,
bearophile