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/oopindelp...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

[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/1...his-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.