[fpc-pascal] code optimization

[stefan077 at web.de]

<karl-michael.schindler at web.de> wrote:

>My 2 cents: 
>looking at the code, i would assume that you can gain by using linked lists with pointers instead of arrays and working with the index. This would reduce the number of offset calculations. However, it means quite a rewrite. So, do you really need more speed?

My experience is that linked lists with pointers are much slower than linked lists realized by arrays. Allocating and dellocating memory is very time consuming. Even if you allocate all memory in advance using pointers easily results in cache misses. The additional offset calculation should not take any additional clock cycles on modern CPUs.
And yes, I need more speed, because the program I wrote is going to run several CPU-years. It will run in the end on several Intel Xeons in parallel, but still it means that the runtime is a few months. So even 10% speedup can save me a week or more.
 
>
>Even the following primitive replace, which is not yet a conversion to a linked list already saved about 10% on Mac OS X:
>
>      while CurrentRectangle <> 0 do
>      begin
>        i := CurrentRectangle;
>        if (UnsortedRectangle[i].Width <= MinValleyWidth) then
>          inc (TotalAreaOfFittingRectangles, UnsortedRectangle[i].Area);
>        CurrentRectangle := UnsortedRectangle[CurrentRectangle].NextUnusedRectangle
>      end;
>
>-----
>
>var
>  ThisUnsortedRectangle: ^TRectangle;
>...
>      while CurrentRectangle <> 0 do
>      begin
>        ThisUnsortedRectangle := @UnsortedRectangle[CurrentRectangle];
>	if (ThisUnsortedRectangle^.Width <= MinValleyWidth) then
>          inc (TotalAreaOfFittingRectangles, ThisUnsortedRectangle^.Area);
>        CurrentRectangle := ThisUnsortedRectangle^.NextUnusedRectangle
>      end;

I see almost no difference if I compile with Delphi 7 under Windows XP. But actually you hit the point because for these few lines FPC-pascal seems to have great problems with optimization. 

>
>Btw. profiling indicates that this loop takes over 30% of cpu time. Skipping the initial assignment (i := CurrentRectangle;) made up for about 5%.

Not for Delphi 7. So Delphi 7 seems to eliminate the first assignment while FPC-pascal seems not to do so. 

BTW, the code that I sent was not intended to be a speed optimized code. It was just some code that shows that FPC-pascal can generate code that is more than 50% slower than Delphi 7 code. 

Stefan