iterator for array structure

[laggyluk]

So I have this 'world' class with a lot of iterating over world data in different methods and I wonder if it's possible to wrap this around in such manner:


for block in wordData do begin

instead of:


for z:=0 to world_depth-1 do begin
for x:=0 to world_width-1 do
for y:=0 to chunk_height-1 do begin
chx:=x div chunk_width;
chy:=z div chunk_width;
xx:=x mod chunk_width;
yy:=y;
zz:=z mod chunk_width;
pBlok:=@chunksPointer^[chx,chy].blocks[xx,yy,zz];
...
end;
end;

in each method.

I suppose that it would be more obvious if 'wordData' was a list but I'm storing data in an array of 'chunk' class and each chunk stores blocks in 3d array.
is there a way to do that?

[SilverWarior]

You have to use enumrerators. I haven't use them yet in any of my classes so I can't provide you with an example of my own.
But I can provide you with links to a few articles on this topic:
http://delphi.about.com/od/oopindelphi/a/enumerators-in-delphi-creating-custom-for-in-iterations.htm

[User137]

For-in adds extra bloat, and for sure is not designed for operations that need performance.

That would go much faster if you iterate xx, zz for 1 full chunk at the time. You would get something like:

for chy:=0 to chunk_rows-1 do
for chx:=0 to chunk_cols-1 do begin
pChunk:=@chunksPointer^[chx, chy];
for z:=0 to chunk_depth-1 do
for x:=0 to chunk_width-1 do
for y:=0 to chunk_height-1 do begin
pBlok:=@pChunk^.blocks[x, y, z];
...
end;
end;

Edit: On other note, i don't use 2- or 3-dimensional arrays myself, for numbers bigger than 10 usually. I prefer 1-dimensional and setlength(block, blocksize*count); type of approach. Then everything is tidy continuous data.

[laggyluk]

in methods used 'in game' i usually operate on chunks not on whole world but for some editor operations it would be handy to have the iterator.
btw I was thinking about keeping data in a flat array but it seemed to be more messy with index calculation. maybe next time :P

[imcold]

1. depending on how do you allocate it, you can cast the multidimensional array to a pointer to blocks and iterate over it with single index. Also, this is most likely the fastest way, if the compiler cannot optimize away the nested loops
2. if you can't use for-in directly and you don't want to bloat your code with nested loops or pointer casts, you can hide the loops iterating over blocks in a procedure. Pass it the operation that should be executed on each block as a parameter.
3. you can repeat this trick with chunks, too. It adds to readability of the code and makes maintaining easier.
4. if the iteration order doesn't matter, always iterate with the first index changing the slowest and the last index the fastest. This way the CPU accesses the array items continuously, which is more efficient than random jumping through memory. And the difference can be in orders of magnitude.
5. don't do div and mod in the innermost loop, if you can avoid it (or at all, as USer137 showed), those operations are amongst the slowest math ops on all cpus.

Sample for Freepascal, the data types are just wild speculations, since you didn't provide any :)
http://satd.sk/public/multiarray.pas.html

[User137]

(Sorry, answered same time.)

Well, the compiler will add the same mess and maybe more internally ;) (N-dimensional dynamic array is actually array of arrays, each prime index having different allocation) You would just be in control over it. But sure it may need a little "thinking with indexes" sometimes.

Also it's possible to simplify the indexing with inline functions:

function TChunk.GetIndex(const x, y, z: integer): integer; inline;
begin
result:=x + (z + y * ChunkDepth) * ChunkWidth; // Hope it went right ...
end;

pBlok:=@pChunk^.blocks[GetIndex(x, y, z)];
Inlining places the code directly to where it's used, so there shouldn't be any parameter "overhead" or what it's called.

[imcold]

Array of array of array of something can make one's eyes bleed :) You could take over the allocation and use pointer arrays to store all blocks sequentially in one pool, if you wanted to use single index to iterate over them, but this can quickly get ugly. It's better not to expose stuff like that outside of a class and an extra reason to make some iterator method - if you ever decide to optimize, there's just one class to change ;)

[laggyluk]

there is a LOT to optimize in this game ;) thanks for the suggestions

[SilverWarior]

I just made test project in which I implemented Enumeration for 3D array. Implementing Enumeration wasn't hard. But I'm disapointed that I'm geting poorer performance when using enumeration and for in loop in comparison to nested foor loops. This slowdown might be result of my poor implementation.

Anywhay here is code with some comments for you guys to studdy and use if it comes usefull to you.

unit Unit2;
interface

uses
Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, System.Diagnostics, System.TimeSpan, System.Math;

type
T3DPosition = record
X,Y,Z: Integer;
end;

TWorldDataEnumerator = class
private
FOwner: TObject;
FXPos: Integer;
FYPos: Integer;
FZPos: Integer;
protected
function GetCurrent: T3DPosition;
function GetWidth: Integer;
function GetHeight: Integer;
function GetDepth: Integer;
public
constructor Create(AOwner: TObject);
function MoveNext: Boolean; virtual;
property Current: T3DPosition read GetCurrent;
property Width: Integer read GetWidth;
property Height: Integer read GetHeight;
property Depth: Integer read GetDepth;
end;

TWorldData = class(TObject)
private
FWidth: Integer;
FHeight: Integer;
FDepth: Integer;
FData: Array of array of array of T3DPosition;
protected
function GetData(X,Y,Z: Integer): T3DPosition;
procedure SetData(X,Y,Z: Integer; Position: T3Dposition);
public
constructor Create(Width, Height, Depth: Integer);
function GetEnumerator: TWorldDataEnumerator;
property Data[X, Y, Z: Integer]: T3DPosition read GetData write SetData;
property Width: Integer read FWidth;
property Height: Integer read FHeight;
property Depth: Integer read FDepth;
end;

TForm2 = class(TForm)
Button1: TButton;
Memo1: TMemo;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure FormDestroy(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form2: TForm2;
WorldData: TWorldData;

implementation

{$R *.dfm}

{ TWorldDataEnumerator }

constructor TWorldDataEnumerator.Create(AOwner: TObject);
begin
inherited Create;
//Here we set the owner of this enumerator so we know hose data we itearate though
FOwner := AOwner;
//Needs alsways to be one before first item since MoveNext always moves to next item
FXpos := -1;
//FYpos and FZpos are not -1 since MoveNext primarly moves only on X axis
FYpos := 0;
FZpos := 0;
end;

function TWorldDataEnumerator.GetCurrent: T3DPosition;
begin
result := TWorldData(FOwner).Data[FXpos,FYpos,FZpos];
end;

function TWorldDataEnumerator.GetDepth: Integer;
begin
result := TWorldData(FOwner).Depth;
end;

function TWorldDataEnumerator.GetHeight: Integer;
begin
result := TWorldData(FOwner).Height;
end;

function TWorldDataEnumerator.GetWidth: Integer;
begin
result := TWorldData(FOwner).Width;
end;

function TWorldDataEnumerator.MoveNext: Boolean;
begin
//We set default result of our function to true
result := True;
FXpos := FXpos + 1;
//If FXpos is larger than the width of our data cluster we move to the start
//of next line
if FXpos > Width-1 then
begin
FXpos := 0;
FYpos := FYpos + 1;
//If YPos is larger than height of our data cluster we move to the start
//of next level
if FYpos > Height-1 then
begin
FYpos := 0;
FZpos := FZpos + 1;
//If FZpos is larger than the depth of our data cluster we are already
//out of bouds of our data cluster so we set result to false so the
//iterator know it came to the end
if FZpos > Depth-1 then result := False;
end;
end;
end;

{ TWorldData }

constructor TWorldData.Create(Width, Height, Depth: Integer);
begin
inherited Create;
FWidth := Width;
FHeight := Height;
FDepth := Depth;
//Set size of test data
SetLength(FData,Width,Height,Depth);
end;

function TWorldData.GetData(X, Y, Z: Integer): T3DPosition;
begin
//Get data at certain position
result := FData[X,Y,Z];
end;

function TWorldData.GetEnumerator: TWorldDataEnumerator;
begin
//We create TWorldDataEnumerator object and pass it as result
result := TWorldDataEnumerator.Create(self);
end;

procedure TWorldData.SetData(X, Y, Z: Integer; Position: T3Dposition);
begin
//Set data at certain positon
FData[X,Y,Z] := Position;
end;

{ TForm2 }

procedure TForm2.FormCreate(Sender: TObject);
var X,Y,Z: Integer;
Position: T3DPosition;
begin
//Create test data
WorldData := TWorldData.Create(200,200,200);
for Z := 0 to WorldData.Depth-1 do
begin
for Y := 0 to WorldData.Height-1 do
begin
for X := 0 to WorldData.Width-1 do
begin
Position.X := X;
Position.Y := Y;
Position.Z := Z;
WorldData.Data[X,Y,Z] := Position;
end;
end;
end;
end;

procedure TForm2.FormDestroy(Sender: TObject);
begin
WorldData.Free;
end;

procedure TForm2.Button1Click(Sender: TObject);
var Position: T3DPosition;
Pos: T3DPosition;
StopWatch: TStopWatch;
ElapsedTime: TTimeSpan;
I,G: Integer;
X,Y,Z: Integer;
begin
G := 10;
for I := 0 to G do
begin
StopWatch := TStopWatch.StartNew;
for Position in WorldData do
begin
Pos := Position;
end;
StopWatch.Stop;
ElapsedTime := StopWatch.Elapsed;
Memo1.Lines.Add('for in enumeration:'+IntToStr(ElapsedTime.Milliseconds));
end;
for I := 0 to g do
begin
StopWatch := TStopWatch.StartNew;
for Z := 0 to WorldData.Depth-1 do
begin
for Y := 0 to WorldData.Height-1 do
begin
for X := 0 to WorldData.Width-1 do
begin
Pos := WorldData.Data[X,Y,Z];
end;
end;
end;
StopWatch.Stop;
ElapsedTime := StopWatch.Elapsed;
Memo1.Lines.Add('regular nested for loops:'+IntToStr(ElapsedTime.Milliseconds));
end;
end;

end.


EDIT1: Code is written in Delphi XE3.
As you can see I relly on TStopWatch for time profiling. As far as I know TStopWatch is Delphi specific so you will unfortunately have to find your own way of time-prifiling the code in FPC.
EDIT2: After a quick search on the web I found that it seems to be similar implementation of TStopWatch made for FPC
http://stackoverflow.com/questions/13927317/what-is-free-pascals-equivalent-of-delphis-tstopwatch

[User137]

You create TStopWatch 22 times, but never free it. It is memory leak. Also i guess more interesting numbers come if StopWatch was used outside the "for I" loop. What kind of numbers do you get?

Also because of the caused function parameter load, compiler optimization might do things. Optimization might "inline" automatic if constants were used

procedure TWorldData.SetData(const X, Y, Z: Integer; const Position: T3Dposition); //inline; ?
Even the GetData allocates and sets 12 bytes for 3 integers for each pos, while nested for-loops do not.

[laggyluk]

actually I think that migrating iteration to one place in my code would allow me to switch to a flat array world representation at some point.
but maybe later as half a year passed since project start and still no gameplay..

[Darkhog]

@SilverWarrior: IMO, unless you need some record (as in Pascal record type) for each world "tile", enumeration is over engineering it. If nested loops are faster and still do the job, I'd say go for it. Just comment them well so you'll be sure what they do at a later date.

You create TStopWatch 22 times, but never free it. It is memory leak. Also i guess more interesting numbers come if StopWatch was used outside the "for I" loop. What kind of numbers do you get?

Also because of the caused function parameter load, compiler optimization might do things. Optimization might "inline" automatic if constants were used

That brings me to my game and similar issue. I've noticed slight memory leak (which doesn''t have much effect on gameplay, but I'm OCD and don't want it). I have proper destructors for all my classes and at the end of program I .Destroy() them, but do I also have to execute .Free() afterwards?

[laggyluk]

if in lazarus then project options>linking> check 'use heaptrc', usefull for tracking memory leaks

[User137]

I have proper destructors for all my classes and at the end of program I .Destroy() them, but do I also have to execute .Free() afterwards?
Free is simply a safe way to call Destroy (it checks first if it exists). So no, don't call both. In the implementation:

procedure TObject.Free;
begin
// the call via self avoids a warning
if self<>nil then
self.destroy;
end;

[Darkhog]

Ah, okay. Thanks for clarification.

[SilverWarior]

You create TStopWatch 22 times, but never free it. It is memory leak. Also i guess more interesting numbers come if StopWatch was used outside the "for I" loop. What kind of numbers do you get?

Since TStopWatch isn't a class but is actually a record with lots of class helper methods I'm not creating a memory leak.
Becouse TStopwatch is record the memory for it gets reserved when entering Mutton1OnClick method. You need to call Stopwatch.StartNow so that initial parameters of StopWatch are being set (automatic chosing of best way for time profiling based on hardware and OS capablitity, resetting timer, etc.).

Using the StopWatch outside "for I loop" still shows same difference in performance. Now I did find an error in my usage of StopWatch. I was retrieving Milliseconds with ElapsedTime.Milliseconds which returns only milliseconds part but I should have been using ElapsedTime.TotalMilliseconds to retrieve whole elapsed time in Milliseconds.



Also because of the caused function parameter load, compiler optimization might do things. Optimization might "inline" automatic if constants were used

procedure TWorldData.SetData(const X, Y, Z: Integer; const Position: T3Dposition); //inline; ?

You can't use that in Getter or Setter property methods.



Even the GetData allocates and sets 12 bytes for 3 integers for each pos, while nested for-loops do not.

Booth enumerator and nested for loops aproach retrieve data through the use of property so in both cases GetData is being called. I have written my code specifically to do so in order for me to have realistic comparison.


Anywhay I managed to improve the overal performance a bit by removing direct typecasting like:

result := TWorldData(FOwner).Data(FXPos,FYPos,FZPos)


I gues that lower performance I get with my Enumerator implementation is due to using another class which acts as annother abstract layer. Unfortunately you can't do without this aditional abstract level.

[SilverWarior]

@SilverWarrior: IMO, unless you need some record (as in Pascal record type) for each world "tile", enumeration is over engineering it. If nested loops are faster and still do the job, I'd say go for it. Just comment them well so you'll be sure what they do at a later date.

Don't worry I'll probably still be using nested loops as they also alow you to quickly iterate only through portion of your while data.

Since the threads question was "How to implement such feature" I went and do a litle research (I have nevere used Enumerations before) and build myself a litle demo to see how hard it is to implement Enumerators and what performance I can get out of them.
And of course I shared my findings with you guys so you won't have to do all this by yourselves.

[laggyluk]

I managed to convert my world data to flat array :D was easier than I thought -thanks to this thread too. can't really tell if it's faster than before, didn't benchmark :P