[fpc-devel] Dynamic indexing (multi-dimensional-indexing) (probably my most important/valuable posting up to this date)

[Skybuck Flying]

This is probably the most important test/demonstration program I ever wrote 
and published/released onto the internet (up to this date (7 juli 2011)).

I hope compiler writers/programming language designers will study it 
carefully and integrate it into their language.
(It's a bit long/lengthy read by well worth it ! Also casual programmers can 
benefit from it as well !)

See comments for more details about the usefullness and the value of it for 
present day and the future.

Also see test program way down below for usage example and verification 
program.

Especially the formula's are very important.

For more information how this program came to be see the other thread called 
"dynamic pointer indexing"

Which takes this step a bit further to provide direct memory access 
(concept/thread which is still under development).

This posting takes a step back to evaluate and verify the formula's to be 
used in "dynamic pointer indexing".

For now this example/concept can be thought of as "dynamic indexing".

Which can also be thought of as "multi-dimensional indexing".

A future which is currently missing in C/C++/CUDA C/C++ and in a way also 
Delphi since Delphi requires a pointer array per additional dimension.

The technique illustrated below needs none of that Delphi overhead and 
introduces it's own much smaller overhead, memory-wise, it does introduce a 
somewhat more computation-overhead.

There is also a hidden potential problem if parenthesis would be used.

A small explanation for the people that did not follow the other thread 
mentioned:

The multiply operator is used as a passing mechanism to calculate a linear 
index for the multi dimension indexes.

// *** Begin of Program ***

program TestProgram;

{$APPTYPE CONSOLE}

{

Test dynamic multi dimensional index calculations

version 0.01 created on 1 juli 2011 by Skybuck Flying

To illustrate the theory behind dynamic multi dimension index calculations I 
shall now
create a little test/demonstration program to show you how to write this 
code and what
formula's to use.

The example deviates from the written theory so far in regard to the order, 
the order
in the theory was assumed to be z, y, x however delphi's order appears to be 
x, y, z.

Therefore the formula's will be adepted to Delphi's order.

For completeness sakes I shall mention the formula's in this comments one 
more time.

How these formula's where derived I will not explain here because it was a 
bit vague and messy but all in all not to bad.
But you don't need to know that... all that matters are the formula's you 
can probably derive/come to the conclusion
how these were formed yourself and if not consider these a gift to you from 
me ! ;) :)

Formula for index calculation in abstract form:

result.index =
(lower dimension parameter.index * lower dimension parameter.stride) +
(higher dimension parameter.index * lower dimension parameter.volume);

the resulting stride should be 1 until further notice
result.stride = 1;

Valueable notes for you to understand:

Strides always have a minimum of 1.
Volumes always have a minimum of 1.
DimensionCounts always have a minimum of 1.

These ones assure that none of the multiplications are zero-ed out, that 
would lead to wrong results.
This is why these general formula's work. No matter if the stride is 1 and 
the volume is 1 it will still work.
So some unnecessary multiplications with 1 might be done but so be it for 
generalities sake.

The last formula you will need is the volume calculation in abstract form 
which is actually quite simply:

result.volume = (lower dimension parameter.volume * higher dimension 
parameter.volume);

It should be apperent to you now why this will work, but I shall explain it 
anyway.

Since the order is from left to right which means low to high this will 
work.

The lowest dimension is multiplied with the higher dimension giving a new 
volume, in the first two dimension case
this would be the area (a volume with a depth of 1) the next dimension it is 
multiplied with would give a new volume.
(a real 3d volume with a depth of depth). The next dimension it is 
multiplied against gives a 4D volume. I use
the term "volume" for a lack of a better term for a 4D quanitity. So think 
of a volume is that which describes
the entire (coordinate) space (or index space if you will).

I shall also give these two formula's in a somewhat more concrete and short 
hand form for direct/easy/correct implementation purposes:

result.stride := 1;
result.index := (ParaA.Index * ParaA.Stride) + (ParaB.Index * ParaA.Volume);
result.volume := (ParaA.Volume * ParaB.Volume);

Now it's time for a test/demonstration program to proof to you that this is 
not bullshit, to prove to you that is is valuable
and that this works and to show the power/flexibility of it so you will 
hopefully see how usefull this would become
if this became a primary language feature with further support behind it ! 
;) =D

However the current code which shall be provided can already be of high 
value for current day usasage ! ;) =D

To show the usefullness of it a type will be introduced which shall 
encompass this theory and these formula's.

This type shall be called "TDynamicIndex" it's purposes is many-fold:

To construct "dynamic" multi dimensional array indexing automatically.

So that the user programmer can easily adjust it's code to support all kinds 
of 1D, 2D, 3D and xD dimensions.

Possibly layed out over a single dimension.

So this type calculates a linear index (which is the final/result index) 
which can then be used to access for example
the memory system (which is a 1D entity).

Also to simply the design, the indexed property will be replaced with a 
procedure, this illustrates
that the method is applieable to other languages which do not have 
properties like c/c++, so this also illustrates
that the method works not because of properties but thanks to operator 
overloading.

However I have no way of setting the index value with indexed properties (a 
procedure call would look ugly so I am going
to leave it in ! ;):)) but rename it also a little bit to show what it does.

This test/demonstration program will also function as a verifier to verify 
that the calculations are indeed correct.


Conclusion:

It works flawlessly so far.

This is probably one of the, if not the, most important test program and 
theory I have ever published.

I hope compiler writers will study it carefully and will hopefully be able 
to integrate this "technology" into
their programming languages so that we programmers can finally use "dynamic 
pointers" and "dynamic indexes".. so
that we programmers can finally program easily in multiple dimensions which 
translate to a linear/1d dimension for memory access.

So that we can finally have multi dimensional array indexing with paying 
penalties like additional pointers or difficult data
structure construction involving multiple array creations and such.

This demonstration and code will become more valuable as CUDA/OpenCL becomes 
more valuable and widely used.

CUDA C/C++ is a perfect example of the
"multi dimensional indexing hell/linear index calculation hell, problem 
distribution hell" that CUDA C/C++ programmers are now facing.

This code demonstration demonstrates how to solve it in a flexible way.

The usage example is hard coded to use the dimensions of x: 320 y: 200 z: 60 
which represents the classic ms-dos vga
screen and a refresh rate of 60, (which was actually 70 at the time but ok), 
so some programmers might be used to these dimensions
and might recgonize some of it.

Hopefully needless to say, this example is not limited to these dimensions, 
and any dimension can be used.

A word of caution: integer has been used for volume. It's pretty easy to see 
how the volume calculation might overflow
for large dimensions so keep an eye out of that. For now I shall let it be 
an integer for speed's sake.

If an overflow occurs for your usage consider using an int64 for larger 
dimension support.

This demonstration code has limited itself to indexes to keep things simple.

Strides have also been set to 1.

This represent a byte.

Changing the stride to 4 would represent an integer.

Only the first stride for the X dimension would need to be set to 4.

The other strides should be left alone and be set to 1.

Changing the stride would invalidate the verification program ofcourse.

Changing the code to automatically adept to changes should be obvious, but 
for clearities sake
will not be done in version 0.01.

Perhaps version 0.02 might do this, but for now I see little value in it ! 
;) :)

I shall now continue working on my TDynamicPointer concept which uses
the concepts presented here in TDynamicIndex and expands on it to support
direct access to the memory.

}

uses
SysUtils;

type
TDynamicIndex = record
private
  mIndex : integer;
  mStride : integer;
  mDimensionCount : integer;
  mVolume : integer;

  function StoreIndex( ParaIndex : integer ) : TDynamicIndex;
public
  constructor Create( ParaDimensionCount : integer; ParaStride : integer );

  property IndexOperator[ ParaIndex : integer ] : TDynamicIndex read 
StoreIndex; default;

  class operator Multiply( ParaA, ParaB : TDynamicIndex ) : TDynamicIndex;
end;

constructor TDynamicIndex.Create( ParaDimensionCount : integer; ParaStride : 
integer );
begin
mIndex := 0;
mStride := 1;
mDimensionCount := 1;
mVolume := 1;

if ParaDimensionCount > 1 then
begin
  mDimensionCount := ParaDimensionCount;
end;

if ParaStride > 1 then
begin
  mStride := ParaStride;
end;

mVolume := mDimensionCount * mStride;
end;

// store index, and return a copy, not because we want to, but because we 
must :(
// I would much rather return a pointer, but unfortunately calling multiple 
operator on pointer derefence won't work well ?!)
// perhaps it should be retried sometime...
function TDynamicIndex.StoreIndex( ParaIndex : integer ) : TDynamicIndex;
begin
mIndex := ParaIndex;
result.mIndex := mIndex;
result.mStride := mStride;
result.mDimensionCount := mDimensionCount;
result.mVolume := mVolume;
end;

class operator TDynamicIndex.Multiply( ParaA, ParaB : TDynamicIndex ) : 
TDynamicIndex;
begin
result.mStride := 1;
result.mIndex := (ParaA.mIndex * ParaA.mStride) + (ParaB.mIndex * 
ParaA.mVolume);
result.mVolume := (ParaA.mVolume * ParaB.mVolume);
end;

procedure Main;
var
X : TDynamicIndex;
Y : TDynamicIndex;
Z : TDynamicIndex;
Result : TDynamicIndex;
vErrorDetected : boolean;

vX : integer;
vY : integer;
vZ : integer;

vCheck : integer;
begin
X := TDynamicIndex.Create( 320, 1 );
Y := TDynamicIndex.Create( 200, 1 );
Z := TDynamicIndex.Create(  60, 1 );

// first a few single tests to see/show how it works.
Result := X[ 0 ] * Y[ 0  ] * Z[ 1 ]; // should display 320*200*1*1=64000
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 0  ] * Z[ 0 ]; // should display 319*1*1*1=319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100  ] * Z[ 0 ]; // should display 319*1 + 
(100*320)*1*1 = 32319
writeln( Result.mIndex );

Result := X[ 319 ] * Y[ 100  ] * Z[ 5 ]; // should display 319*1 + 
(100*320)*1 + (5*200*320)*1 = 32319 + 320000 = 352319
writeln( Result.mIndex );

// so far so could so now let's do some exhaustive/full verifications.
writeln('Verification started.');

vErrorDetected := false;
for vZ := 0 to 59 do
begin
  for vY := 0 to 199 do
  begin
   for vX := 0 to 319 do
   begin
    Result := X[ vX ] * Y[ vY ] * Z[ vZ ];

    vCheck := (vZ * 200 * 320) + (vY * 320) + vX;

    if Result.mIndex <> vCheck then
    begin
     writeln('Index calculation error detected at (vX, vY, vZ): ' + '(' + 
IntToStr(vX) + ',' + IntToStr(vY) + ',' + IntToStr(vZ) + ')' );
     vErrorDetected := true;
    end;
   end;
  end;
end;

writeln('Verification done.');

if vErrorDetected then
begin
  writeln('Verification result: errors detected !');
end else
begin
  writeln('Verification result: no errors detected.');
end;
end;


begin
try
  Main;
except
  on E: Exception do
   Writeln(E.ClassName, ': ', E.Message);
end;
ReadLn;
end.

// *** End of Program ***

Bye,
  Skybuck. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20110701/858c7d5f/attachment.html>