www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Array List object?

reply "Gan" <avisaria me.com> writes:
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?
Jan 26 2015
next sibling parent reply "Gan" <avisaria me.com> writes:
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.
Jan 26 2015
parent reply "Gan" <avisaria me.com> writes:
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.
Jan 26 2015
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
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
Jan 26 2015
parent reply "Gan" <avisaria me.com> writes:
On Tuesday, 27 January 2015 at 06:16:03 UTC, H. S. Teoh wrote:

 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


Thanks! My project use to hover at 80mb ram usage, now it hovers 
at 35mb ram usage. Nevermind. It just climbed up to 65mb

Okay now I'm very confused. When I have my program fully hidden 
behind another window, my ram usage goes up without going down. 
Which my program is partly visible it goes up a few mb then 
returns to the past amount of mb.

Is this a bug?
Jan 26 2015
parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Tue, Jan 27, 2015 at 07:18:22AM +0000, Gan via Digitalmars-d-learn wrote:
[...]

 Okay now I'm very confused. When I have my program fully hidden behind
 another window, my ram usage goes up without going down. Which my
 program is partly visible it goes up a few mb then returns to the past
 amount of mb.
 
 Is this a bug?


It's hard to say without more information. One possibility is that when
the program is partly visible the GC gets triggered more often, so more
memory gets returned to the OS, whereas when it's not, the GC may be
triggering less often so memory usage increases. But that's just my
guess, it's hard to say unless we know more about what your program
does.


T

-- 
People say I'm indecisive, but I'm not sure about that. -- YHL, CONLANG
Jan 27 2015
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Gan:


 //Initializing the array
 tiles = new SBTile[](0);


This is often useless.



 //Clearing the array
 tiles = [];


This doesn't "clear" the array, it rebinds it to a null pointer.

Bye,
bearophile
Jan 27 2015
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
And it's named "dynamic array", instead of "Array List object", 
it's not a class instance.

Bye,
bearophile
Jan 27 2015