Array List object?

[H. S. Teoh via Digitalmars-d-learn]

On Tue, Jan 27, 2015 at 06:02:38AM +0000, Gan via Digitalmars-d-learn wrote:
> On Tuesday, 27 January 2015 at 06:00:50 UTC, Gan wrote:
> >On Tuesday, 27 January 2015 at 05:32:09 UTC, Gan wrote:
> >>Hey I'm using normal arrays for my project:
> >>//Declaring the array
> >>SBTile[] tiles;
> >>
> >>//Initializing the array
> >>tiles = new SBTile[](0);
> >>
> >>//Clearing the array
> >>tiles = [];
> >>
> >>//Removing a tile at index i from the array
> >>tiles.remove(i);
> >>
> >>//Adding a tile to the array
> >>tiles ~= tile;
> >>
> >>But I think I'm doing something very wrong because my list of tiles
> >>is growing larger and larger. Am I misusing the array or is there a
> >>better way of doing those array list functions?
> >
> >Found my problem. When you call remove, you need to set it.
> >
> >tiles = tiles.remove(i);
> >
> >Though isn't it incredibly inefficient to continually have it
> >re-create the arrays for adding and removing? I'm asking cause I'm
> >not very knowledgable on this subject.
> 
> On a side note, my program's ram usage is increasing very rapidly. All
> I'm doing to adding and removing objects from an array.

The answers to your question can be found here:

	http://dlang.org/d-array-article.html

In short, D "arrays" are actually not arrays directly, but slices of
arrays (i.e., pointer and length pairs to a segment of memory managed by
the GC).  Therefore, assigning the return value of .remove back to tiles
is extremely efficient, because all you're doing is updating the .ptr
and .length fields of tiles. There is no copying of array elements at
all (except what's already being done in .remove).

However, the problem comes when you call .remove immediately followed by
~=. Because the runtime doesn't know whether you have made other slices
of the same array in the meantime, it doesn't know whether you wish to
retain the original array elements, so to be safe, whenever the array
length shrinks it assumes that the next time you append something new,
it should reallocate. Thus, every time ~= follows .remove, the array
will be reallocated, which is extremely slow. The solution is to tell
the runtime that yes, you do wish to overwrite whatever may have been
there in GC memory before when you append:

	tiles = tiles.remove(i);
	assumeSafeAppend(tiles); // <--- this is the secret
	tiles ~= tile;		// now this won't reallocate everytime

Note that append to the array will still reallocate occasionally (e.g.,
when there is no more space in the currently allocated GC block, and the
array needs to be moved to a new memory location where a bigger block
can be allocated). But it should perform a lot better than reallocating
every single time you append.


T

-- 
Life would be easier if I had the source code. -- YHL