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. _______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-devel
