Lazarus

Free Pascal => FPC development => Topic started by: lagprogramming on March 23, 2023, 09:53:06 am

Title: [SOLVED]Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: lagprogramming on March 23, 2023, 09:53:06 am

packages/fcl-image/src/fpcanvas.inc contains the following procedure:

Code: Pascal  [Select][+][-]

1. procedure TFPCustomCanvas.Erase;
2. var
3.   x,y:Integer;
4. begin
5.   for x:=0 to Width-1 do
6.     for y:=0 to Height-1 do
7.       Colors[x,y]:=colTransparent;
8. end;
9.  

The following procedure should be faster. I've switched the for loops.

Code: Pascal  [Select][+][-]

1. procedure TFPCustomCanvas.Erase;
2. var
3.   x,y:Integer;
4. begin
5.   for y:=0 to Height-1 do
6.     for x:=0 to Width-1 do
7.       Colors[x,y]:=colTransparent;
8. end;

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: Чебурашка on March 23, 2023, 10:47:35 am

Quote from: lagprogramming on March 23, 2023, 09:53:06 am

packages/fcl-image/src/fpcanvas.inc contains the following procedure:

Code: Pascal  [Select][+][-]

1. procedure TFPCustomCanvas.Erase;
2. var
3.   x,y:Integer;
4. begin
5.   for x:=0 to Width-1 do
6.     for y:=0 to Height-1 do
7.       Colors[x,y]:=colTransparent;
8. end;
9.  

The following procedure should be faster. I've switched the for loops.

Code: Pascal  [Select][+][-]

1. procedure TFPCustomCanvas.Erase;
2. var
3.   x,y:Integer;
4. begin
5.   for y:=0 to Height-1 do
6.     for x:=0 to Width-1 do
7.       Colors[x,y]:=colTransparent;
8. end;

I am curious to know what is the difference in terms of execution time, could you please explain/demonstrate?

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: lagprogramming on March 23, 2023, 03:12:57 pm

Quote from: Чебурашка on March 23, 2023, 10:47:35 am

I am curious to know what is the difference in terms of execution time, could you please explain/demonstrate?

It's a matter of CPU cache usage.
Original code "erases"(which in fact consists in writing data) all the lines(rows) of the canvas simultaneously. This means that the CPU will try to simultaneously cache writes for many lines, no more than the height of the canvas.
New CPUs have huge caches and good mechanisms of managing it, but old CPUs are not that good. Those old CPUs will run the proposed code faster than the original code because the data writes are leaner, more fluent.
Also, there are CPUs that write data forward significantly faster than writing it backward. This is another example of CPU cache usage.

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: Чебурашка on March 24, 2023, 10:13:06 am

Quote from: lagprogramming on March 23, 2023, 03:12:57 pm

Quote from: Чебурашка on March 23, 2023, 10:47:35 am

I am curious to know what is the difference in terms of execution time, could you please explain/demonstrate?

It's a matter of CPU cache usage.
Original code "erases"(which in fact consists in writing data) all the lines(rows) of the canvas simultaneously. This means that the CPU will try to simultaneously cache writes for many lines, no more than the height of the canvas.
New CPUs have huge caches and good mechanisms of managing it, but old CPUs are not that good. Those old CPUs will run the proposed code faster than the original code because the data writes are leaner, more fluent.
Also, there are CPUs that write data forward significantly faster than writing it backward. This is another example of CPU cache usage.

Very interesting, thank you.

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: wp on March 24, 2023, 10:38:25 am

Here's a test project which measures the execution time for both methods. There's a 40% speed gain when y is in the outer loop (taking the case of x in the outer loop as a reference). Tested on a 10,000 x 10,000 pixel image.

Code: Pascal  [Select][+][-]

1. program project1;
2.  
3. uses
4.   SysUtils, fpImage, fpCanvas, fpImgCanv;
5.  
6. const
7.   WIDTH = 10*1000;
8.   HEIGHT = 10*1000;
9. var
10.   t: TDateTime;
11.   img: TFPCustomImage;
12.   cnv: TFPCustomCanvas;
13.   i, x, y: Integer;
14. begin
15.   for i := 1 to 5 do
16.   begin
17.     WriteLn('Run #', i);
18.     img := TFPMemoryImage.Create(WIDTH, HEIGHT);
19.     try
20.       cnv := TFPImageCanvas.Create(img);
21.       try
22.         Write('  outer loop x...: ');
23.         t := Now;
24.         for x:=0 to img.Width-1 do
25.           for y:=0 to img.Height-1 do
26.             cnv.Colors[x,y] := colTransparent;
27.         t := Now-t;
28.         WriteLn(FormatDateTime('s.zzz" seconds"', t));
29.  
30.         Write('  outer loop y...: ');
31.         t := Now;
32.         for y:=0 to img.Height-1 do
33.           for x:=0 to img.Width-1 do
34.             cnv.Colors[x,y] := colTransparent;
35.         t := Now-t;
36.         WriteLn(FormatDateTime('s.zzz" seconds"', t));
37.       finally
38.         cnv.Free;
39.       end;
40.     finally
41.       img.Free;
42.     end;
43.     WriteLn;
44.   end;
45.  
46.   Write('Done. Press ENTER to quit...');
47.   ReadLn;
48. end.

Post a patch to the FPC bug tracker, I doubt whether the developers taking care of graphics read this here.

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: AlexTP on April 11, 2023, 09:31:30 am

Posted bugreport to https://gitlab.com/freepascal.org/fpc/source/-/issues/40236

Title: Re: Improvement of packages/fcl-image/src/fpcanvas.inc TFPCustomCanvas.Erase
Post by: marcov on April 11, 2023, 11:20:38 am

Quote from: wp on March 24, 2023, 10:38:25 am

Post a patch to the FPC bug tracker, I doubt whether the developers taking care of graphics read this here.

I work with image formats in my daily job, but I don't use fcl-image.

Anyway, committed. I'm somewhat surprised it still has effect, since afaik the fcl-image colors[] is quite slow with a lot of shifting for various formats.