Board index » delphi » Fast Array Access

Fast Array Access

Quote
John Brydon wrote:

> I want to maximise the speed of a signal processing loop of the form:

>   for i := 1 to 50 do
>   {
>     AccumulatedSum := coefficient[i]*data[i};
>   }

> In 'C' I would use autoincrementing pointers in place of the array
> indices. What form generates the fastest code in Delphi Pascal ?

        Hmm - it seems _possible_ that the optimizer will change the
above to

AccumulatedSum := coefficient[50]*data[50};

, in which case it will execute very fast<g>...

        I would guess that

   for i := 50 downto 0 do
   {
     AccumulatedSum := AccumulatedSum + coefficient[i]*data[i};
   }

is going to be about as fast as it gets - this is certainly a very
common construct, so it would be a surprise if the compiler didn't
come up with a fairly fast version. If you want to try doing it
yourself there are no "autoincrementing" pointers in Delphi, but
you could say

i:= 50;
while i > 0 do
begin
   stuff(i);
   dec(i);
end;

or if you really want to get down,

type

        PDataType = ^TDataType;
        TDataType = whatever;
        PCoeffType = ^TCoeffType;
        TCoeffType = whatever;

var PD: PDataType; PC: PCoefftype; i: integer;
begin
  PD:= whatever;
  PC:= whatever;
  Sum:= 0;
  for i:= 50 downto 0 do
  begin
    Sum:= Sum + PD^ * PC^;
    inc(PC);
    inc(PD);
  end;

I don't think it's documented yet, but inc(ATypedPointer) increments
the pointer by the right amount.

        Again, I'd be surprised if the "manual" versions came out
significantly faster than the simple loop, simply because I don't
see why they wouldn't compile the loop to something fairly
optimal in the first place. (Um - for example my impression is
that the optimizer does sequential ("for") access to arrays by
incrementing pointers instead of by doing a multiplication each time.
It's become _illegal_ to modify the value of the loop counter, and
the fact that this is illegal would make that optimization possible.)

--
David Ullrich

sig.txt not found

 

Re:Fast Array Access


Quote
John Brydon <jbry...@ozemail.com.au> wrote:
>I want to maximise the speed of a signal processing loop of the form:
>  for i := 1 to 50 do
>  {
>    AccumulatedSum := coefficient[i]*data[i};
>  }
>In 'C' I would use autoincrementing pointers in place of the array
>indices. What form generates the fastest code in Delphi Pascal ?

You can use pointers in Pascal too.  I assume the above is

AccumulatedSum := AccumulatedSum + coff[i]*data[i]

assuming that coff and data are integer arrays then

type
   pInt = ^integer;
var
   x, y : pInt;

begin
   x := @coff[1];
   y := @data[1];

   while (cardinal(x) <= cardinal(@coff[50]) do begin
      accumsum := accumsum + (x^ * y^);
      x := pInt(cardinal(x) + SizeOf(coff[1]));
      y := pInt(cardinal(y) + SizeOf(coff[1]));
   end;
end;

I think that the Delphi optimizer might turn your loop above into
pointer arithmetic instead of array index calculation.  It has those
types of optimizations.  But, the pointer arithmetic above combined
with delphi's smart register reuse and allocation would yeild code
very close to the best c compilers autoincrementing pointer code.

Jay Cole
My real address is @bgn.mindspring.com to prevent spam.

Re:Fast Array Access


On Wed, 27 Aug 1997 18:11:09 +0200, Rudi Ziegaus <"Rudi.Ziegaus[No

Quote
Spam please]"@bingo.baynet.de> wrote:
>John Brydon wrote:

>> I want to maximise the speed of a signal processing loop of the form:

>>   for i := 1 to 50 do
>>   {
>>     AccumulatedSum := coefficient[i]*data[i};
>>   }

>> In 'C' I would use autoincrementing pointers in place of the array
>> indices. What form generates the fastest code in Delphi Pascal ?

>> John Brydon
>Don't overestimate the autoincrementing in C. The speed depends largely
>on the implementation. AFAIK, there are many implementations where the
>speed gain is none or insignificant.

Also, if you examine the object code, you will find that the
optimization in Delphi 2 does a great job of generating optimal code
for this, as good as any C compiler using autoincrementing!

=======================================================
Chris Williams               chris.willi...@pixie.co.za
Tel: +27 331 961066 (local 0331 961066) 07:00-19:00 GMT
Fax: +27 331 961066 (local 0331 961066) 22:00-04:00 GMT
-------------------------------------------------------

Quote
>>>>>>>>  See "The Number Crunching Page" at:  <<<<<<<<
>>> http://www.geocities.com/SiliconValley/Bay/9187 <<<

Lots of interesting facts & figures ... Free software!!
=======================================================

Re:Fast Array Access


Yes, I've just started examining the object code and it's pretty well
optimised, i:= i+1 coding to assembly code INC, for example. Another
discovery was how much faster "single" type multiplications run than
"real"s.

Don't overestimate the autoincrementing in C. The speed depends largely

Quote
> >on the implementation. AFAIK, there are many implementations where the
> >speed gain is none or insignificant.

> Also, if you examine the object code, you will find that the
> optimization in Delphi 2 does a great job of generating optimal code
> for this, as good as any C compiler using autoincrementing!

Re:Fast Array Access


Quote
John Brydon wrote:

> I want to maximise the speed of a signal processing loop of the form:

>   for i := 1 to 50 do
>   {
>     AccumulatedSum := coefficient[i]*data[i};
>   }

> In 'C' I would use autoincrementing pointers in place of the array
> indices. What form generates the fastest code in Delphi Pascal ?

You know, there are only four real alternatives here (array of records
vs pair of arrays / array indexing vs pointer incrementing) - you could
generate, time, and inspect the generated code for all four a lot faster
than you can get an answer of the Net. You'd learn more, too.

In any case, in D2/D3 at least, the array indexing form is significantly
faster than the pointer incrementing form, at least for element sizes =
1, 2, 4 or 8 - the compiler generates code that uses CPU level indexing
and scaling, so the loop requires fewer instructions than
the pointer increment version.

--

Personal Pages              http://www.midnightbeach.com/jon
Programming Publications    http://www.midnightbeach.com/jon/pubs
Homeschool Resource Page    http://www.midnightbeach.com/hs

Re:Fast Array Access


Generally:

Minimise the size of the index variable.
Turn off all compiler runtime debugging/error checking around the check.
Make sure that the elements of the array are minimum size.
If either array is sparse add a check for either element being 0.

I think that if you really wanted to you could point to coefficient or
data and get dirty.

declare

VAR
     coPtr : ^ coefficientArrayElement;
     datPtr : ^ coefficientArrayElement;

then you can do things like this:

   coPtr := addr(coefficient)
   datPtr := addr(data);

    coPtr := CoPtr + SIZEOF(coefficientArrayElement);  
   {this line SUCCs)

    datPtr := datPtr + SIZEOF(coefficientArrayElement);
   {this line SUCCs)

But! The compiler is probably clever enough to do this for you
(hopefully).

Re:Fast Array Access


In article <3405416...@hawk.pix.za>, <chris.willi...@pixie.co.za> writes

Quote
>Also, if you examine the object code, you will find that the
>optimization in Delphi 2 does a great job of generating optimal code
>for this, as good as any C compiler using autoincrementing!

I would like to look at the code Delphi generates too. Do I need a
disassembler to examine the object file? Is there one hidden in
DOS/Win95 somewhere? Does Delphi (1/2/3) have one?
--
Chris Randle (ch...@amlog.demon.co.uk)

Re:Fast Array Access


Quote
Chris Randle <Ch...@amlog.demon.co.uk> wrote:
>In article <3405416...@hawk.pix.za>, <chris.willi...@pixie.co.za> writes
>>Also, if you examine the object code, you will find that the
>>optimization in Delphi 2 does a great job of generating optimal code
>>for this, as good as any C compiler using autoincrementing!
>I would like to look at the code Delphi generates too. Do I need a
>disassembler to examine the object file? Is there one hidden in
>DOS/Win95 somewhere? Does Delphi (1/2/3) have one?
>--
>Chris Randle (ch...@amlog.demon.co.uk)

You can modify the registry to allow you to see the code, and debug it
instruction by insturction in Delphi 2.0

The change you need to make is in the registry folder:

HKEY_CURRENT_USER\Software\Borland\Delphi\2.0\Debugging

and you need to add "Enable CPU" and set the data to "1"

you will then be able to select View | CPU.

hope this helps.

Martin Harvey.
***********************************************
Martin Harvey
By popular request, email addresses are now in plain text.
Uni email: mc...@hermes.cam.ac.uk
Home email: mc...@harvey27.demon.co.uk
Uni web pages: http://www-stu.pem.cam.ac.uk/~mch24/
***********************************************

Other Threads