DynamicArray kontra StaticArray

[w***@poczta.onet.pl]

dlaczeggo odwolania do tablic dynamicznej sa szybsze od odwolan do tablic
zdefiniowanych statycznie

var OpenArray:Array of Longint;
DefArray:Array[0..10] of Longint;

L2:=15;
SetLength(OpenArray,10);
StartTime:=Now;
OpenArray[0]:=0;
For L1:=1 to L2 do
For Loop:=1 to 1000000000 do OpenArray[0]:=OpenArray[0]+1;
EndTime:=Now;
Memo1.Lines.Add(' Tablica OpenArray '+ TimeToStr(EndTime-StartTime));

StartTime:=Now;
DefArray[0]:=0;
For L1:=1 to L2 do
For Loop:=1 to 1000000000 do DefArray[0]:=DefArray[0]+1;
EndTime:=Now;
Memo1.Lines.Add(' Tablica DefArray '+ TimeToStr(EndTime-StartTime));

kompilacja dla pentium4 , wylaczone sprawdzanie zakresow , optymalizacja 3
stopnia .

u mnie dodawanie dynamicznej tablicy dla 15 miliardow powtorzzen konczy sie o
25 % szybciej .
pentla dla openArray zajmuje 33 sek a dla defArray 44 sek .

[Łukasz 'Maly' Ostrowski]

<snip>
u mnie dodawanie dynamicznej tablicy dla 15 miliardow powtorzzen konczy sie o
25 % szybciej .
pentla dla openArray zajmuje 33 sek a dla defArray 44 sek .

Wklejaj kompletne fragmenty, najlepiej kompilowalne FPC,
a nie upośledzonym lazarusem, najlepiej na pastebin.com,
bo nie zawsze chce mi adaptować te snippetów, przez
3-5min żeby się tylko skompilowały. :-P

[Mirek]

Post by w***@poczta.onet.pl
kompilacja dla pentium4 , wylaczone sprawdzanie zakresow , optymalizacja 3
stopnia .
u mnie dodawanie dynamicznej tablicy dla 15 miliardow powtorzzen konczy sie o
25 % szybciej .
pentla dla openArray zajmuje 33 sek a dla defArray 44 sek .

SOA#1

DefArray real 35.84 user 35.61 sys 0.01
DefArray real 34.82 user 34.50 sys 0.00
DefArray real 34.75 user 34.49 sys 0.01
OpenArray real 34.20 user 34.00 sys 0.00
OpenArray real 37.50 user 37.36 sys 0.00
OpenArray real 34.75 user 34.75 sys 0.00

[Wiktor S.]

Post by w***@poczta.onet.pl
dlaczeggo odwolania do tablic dynamicznej sa szybsze od odwolan do
tablic zdefiniowanych statycznie
For Loop:=1 to 1000000000 do OpenArray[0]:=OpenArray[0]+1;

kiepski test, sprawdzasz tylko odwołanie do indeksu [0], a może jest ono
optymalizowane, bo nie trzeba wyliczać offsetu? odwołuj się do losowego
indeksu.

[Wiktor S.]

No i mamy, bardziej miarodajny test, z zapisem i odczytem, i nie tylko
[zera]

//---------
{$mode objfpc}

uses sysutils;

var OpenArray:Array of Longint;
DefArray:Array[0..10] of Longint;

L1,L2:integer;
StartTime,EndTime:TDateTime;
loop:integer;

begin
L2:=15;
SetLength(OpenArray,10);
StartTime:=Now;
OpenArray[4]:=1;
For L1:=1 to L2 do
For Loop:=1 to 1000000000 do OpenArray[7]:=OpenArray[7]+OpenArray[4];
EndTime:=Now;
writeln(' Tablica OpenArray '+ TimeToStr(EndTime-StartTime));

StartTime:=Now;
DefArray[4]:=1;
For L1:=1 to L2 do
For Loop:=1 to 1000000000 do DefArray[7]:=DefArray[7]+DefArray[4];
EndTime:=Now;
writeln(' Tablica DefArray '+ TimeToStr(EndTime-StartTime));
end.
//---------


i dostaję

Tablica OpenArray 00.00.46
Tablica DefArray 00.00.39

[Mirek]

Post by Wiktor S.
i dostaję
Tablica OpenArray 00.00.46
Tablica DefArray 00.00.39

I dostałeś wynik odwrotny niż w pierwszym poście ;)

U mnie dla pgm1 wyniki były równe, a dla pgm2 (niestety mam tylko fpc 2.2.0)
jest:

Tablica OpenArray 00:01:15
Tablica DefArray 00:00:34

Skompiluj z opcją -al i wyszukaj w pliku pgm.s wnętrza pętli, u mnie
wyglądają tak:

//-------------
movl U_P$PROGRAM_OPENARRAY,%eax
movl 28(%eax),%ecx
movl 16(%eax),%eax
addl %ecx,%eax
movl U_P$PROGRAM_OPENARRAY,%ecx
movl %eax,28(%ecx)

//--------------
movl U_P$PROGRAM_DEFARRAY+28,%edx
movl U_P$PROGRAM_DEFARRAY+16,%eax
addl %edx,%eax
movl %eax,U_P$PROGRAM_DEFARRAY+28

Czyli OPENARRAY ma więcej o dwa ładowania rejestru i trzy dodawania (przy
wyznaczaniu adresu).

[Łukasz 'Maly' Ostrowski]

Post by Mirek

Post by Wiktor S.
i dostaję
Tablica OpenArray 00.00.46
Tablica DefArray 00.00.39

E:\WorkShop\fpc>c:\dev\fpc\bin\i386-win32\fpc -O3 test
Free Pascal Compiler version 2.4.0 [2009/12/18] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
Compiling test.pas
Linking test.exe
27 lines compiled, 0.1 sec , 63296 bytes code, 11064 bytes data

E:\WorkShop\fpc>test
Tablica OpenArray 00:00:32
Tablica DefArray 00:00:32

E:\WorkShop\fpc>test
Tablica OpenArray 00:00:32
Tablica DefArray 00:00:32

Tak jakby, pomijalna różnica.

Post by Mirek
I dostałeś wynik odwrotny niż w pierwszym poście ;)
U mnie dla pgm1 wyniki były równe, a dla pgm2 (niestety mam tylko fpc 2.2.0)
Tablica OpenArray 00:01:15
Tablica DefArray 00:00:34
Skompiluj z opcją -al i wyszukaj w pliku pgm.s wnętrza pętli, u mnie
//-------------
movl U_P$PROGRAM_OPENARRAY,%eax
movl 28(%eax),%ecx
movl 16(%eax),%eax
addl %ecx,%eax
movl U_P$PROGRAM_OPENARRAY,%ecx
movl %eax,28(%ecx)
//--------------
movl U_P$PROGRAM_DEFARRAY+28,%edx
movl U_P$PROGRAM_DEFARRAY+16,%eax
addl %edx,%eax
movl %eax,U_P$PROGRAM_DEFARRAY+28
Czyli OPENARRAY ma więcej o dwa ładowania rejestru i trzy dodawania (przy
wyznaczaniu adresu).

Czego się spodziewamy ze względu na internalsy dynamicznego arraya.
Co do wygenerowanego asma mamy zgodę, z różnicą tyczącą sie
allokacji rejestrów, która to pewnie powoduje u mnie różnicę
w postaci braku różnicy ;-) :

.Lj31:
incl %edi
movl U_P$PROGRAM_OPENARRAY,%eax
movl U_P$PROGRAM_OPENARRAY,%ebx
movl 28(%eax),%ecx
movl 16(%ebx),%eax
addl %eax,%ecx
movl U_P$PROGRAM_OPENARRAY,%eax
movl %ecx,28(%eax)
cmpl $1000000000,%edi
jl .Lj31

.Lj65:
incl %edi
movl U_P$PROGRAM_DEFARRAY+28,%edx
movl U_P$PROGRAM_DEFARRAY+16,%ecx
addl %ecx,%edx
movl %edx,U_P$PROGRAM_DEFARRAY+28
cmpl $1000000000,%edi
jl .Lj65

Co nadal nie robi takiej różnicy żeby zwracać na to uwagę ;-).

[w***@poczta.onet.pl]

Post by Wiktor S.
No i mamy, bardziej miarodajny test, z zapisem i odczytem, i nie tylko
[zera]

{... ciach ...}

Post by Wiktor S.
i dostaję
Tablica OpenArray 00.00.46
Tablica DefArray 00.00.39

Rzeczywiscie mój test jest źle zaprojektowany . Teraz go porawiłem - żeby
wygladał tak jak mniej więcej w programie pracuje .

{$mode objfpc}

uses sysutils;

type
TDefNulArray = array[0..0] of longint;
TDefArray = array[0..1000] of longint;
TOpenArray = array of longint;
var
DefArray: array[0..1000] of longint;
DefArray2: array[0..1000] of longint;
OpenArray,OpenArray2: array of longint;
PDefArray,PDefArray2: ^TDefArray;
PNul: ^TDefNulArray;
POpenArray: ^TOpenArray;
L1, L2, Loop: Longint;
StartTime, EndTime: TDateTime;
begin
L2 := 10000000;

DefArray[0] := 0;
StartTime := Now;
for Loop := 1 to 1000 do
DefArray[Loop] := 0;
for Loop := 1 to 1000 do
DefArray2[Loop] := 1;

for L1 := 1 to L2 do
for Loop := 1 to 1000 do
DefArray[Loop] := DefArray[Loop] + DefArray2[Loop];
EndTime := Now;
WriteLn(' Plus DefArray ' + TimeToStr(EndTime - StartTime));

SetLength(OpenArray,1001);
SetLength(OpenArray2,1001);
StartTime := Now;
for Loop := 1 to 1000 do OpenArray[Loop] := 0;
for Loop := 1 to 1000 do OpenArray2[Loop] := 1;

for L1 := 1 to L2 do
for Loop := 1 to 1000 do OpenArray[Loop] := OpenArray[Loop]+ OpenArray2[Loop];
EndTime := Now;
Writeln(' Plus OpenArray ' + TimeToStr(EndTime - StartTime));

GetMem(PDefArray, SizeOf(TDefArray));
GetMem(PDefArray2, SizeOf(TDefArray));
for Loop := 1 to 1000 do PdefArray^[Loop] := 0;
for Loop := 1 to 1000 do PdefArray2^[Loop] := 1;

startTime := Now;
for L1 := 1 to L2 do
for Loop := 1 to 1000 do
begin
PDefArray^[Loop] := PDefArray^[Loop] + PDefArray2^[Loop];
end;
EndTime := Now;
WriteLn(' Plus Pointer DefArray ' +TimeToStr(EndTime - StartTime));

End.

dla FPC mam ( optymalizacja 3 stpnai , właczone mnie wazne optymalizacje )
Plus DefArray 00:00:42
Plus OpenArray 00:00:58
Plus Pointer DefArray 00:00:52

Dla Delphi7
Plus DefArray 00:00:17
Plus OpenArray 00:00:22
Plus Pointer DefArray 00:00:16

i tu pytanie dlaczego konstrukcja typu dynamiczna tablica jest o 20 %
wolniejsza ??
i dla czego FPC generuje tak wolny kod ( 3 razy wolniejszy ) ??

[Łukasz 'Maly' Ostrowski]

Post by w***@poczta.onet.pl
dla FPC mam ( optymalizacja 3 stpnai , właczone mnie wazne optymalizacje )
Plus DefArray 00:00:42
Plus OpenArray 00:00:58
Plus Pointer DefArray 00:00:52
Dla Delphi7
Plus DefArray 00:00:17
Plus OpenArray 00:00:22
Plus Pointer DefArray 00:00:16
i tu pytanie dlaczego konstrukcja typu dynamiczna tablica jest o 20 %
wolniejsza ??
i dla czego FPC generuje tak wolny kod ( 3 razy wolniejszy ) ??

Albo masz przedwojenny komputer, albo naprawdę nie wiesz
jak się kompiluje z optymalizacjami:

E:\WorkShop\fpc>c:\dev\fpc\bin\i386-win32\fpc -O3 test
Free Pascal Compiler version 2.4.0 [2009/12/18] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
Compiling test.pas
test.pas(14,3) Note: Local variable "PNul" not used
test.pas(15,3) Note: Local variable "POpenArray" not used
Linking test.exe
59 lines compiled, 0.4 sec , 63792 bytes code, 11112 bytes data
2 note(s) issued

E:\WorkShop\fpc>test
Plus DefArray 00:00:11
Plus OpenArray 00:00:18
Plus Pointer DefArray 00:00:18

Wynik w pełni powtarzalny.

A wynik dla dynamic arraya i pointera na arraya jest taki sam,
jednocześnie gorszy, ponieważ masz jeden więcej poziom pointer
indirection. Bo generalnie dynamiczny array to po prostu
pointer na tablicę.

[w***@poczta.onet.pl]

Post by Łukasz 'Maly' Ostrowski
Albo masz przedwojenny komputer, albo naprawdę nie wiesz

Komputer wspólczesny 3 GHz .
Jak optymalizacja to coś więcej niż ustawienie w opcjiach kompilatora
odpowiedniego pola lub wywlołanie fpc z opcja -O3 to możesz mnie nauczyć tej
sztuki .

Chyba rozgryzłęm problem -- winy jest FPC -- a właściwie jego wersje .
Przetestowałęm szybkośc programu dla FPC 2.4.1 , FPC 2.5.1 z czerwca (tej
używałęm ) i FPC 2.5.1 z lipca .

fpc test.pas
2.4.1\bin\i386-win32>test
Plus DefArray 00:00:46
Plus OpenArray 00:00:51
Plus Pointer DefArray 00:00:51

fpc -O3 test.pas
2.4.1\bin\i386-win32>test
Plus DefArray 00:00:15
Plus OpenArray 00:00:32
Plus Pointer DefArray 00:00:34

pp\bin\i386-win32>fpc test.pas
Free Pascal Compiler version 2.5.1 [2010/06/21] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
pp\bin\i386-win32>test
Plus DefArray 00:00:46
Plus OpenArray 00:00:54
Plus Pointer DefArray 00:00:54

pp\bin\i386-win32>fpc -O3 test.pas
Free Pascal Compiler version 2.5.1 [2010/06/21] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
pp\bin\i386-win32>test
Plus DefArray 00:00:43
Plus OpenArray 00:00:51
Plus Pointer DefArray 00:00:45

pp1\bin\i386-win32>fpc test.pas
Free Pascal Compiler version 2.5.1 [2010/07/04] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
pp1\bin\i386-win32>test
Plus DefArray 00:00:46
Plus OpenArray 00:00:53
Plus Pointer DefArray 00:00:51

pp1\bin\i386-win32>fpc -O3 test.pas
Free Pascal Compiler version 2.5.1 [2010/07/04] for i386
Copyright (c) 1993-2009 by Florian Klaempfl
Target OS: Win32 for i386
pp1\bin\i386-win32>test
Plus DefArray 00:00:43
Plus OpenArray 00:00:48
Plus Pointer DefArray 00:00:46

fpc 2.4.1 najlepiej optymalizuje --dla statycznych tablic tak samo jak delphi a
dla dynamicznych jest tylko 2 razy gorszy od delphi -- późniejsze wersje są już
dla dynamicznych i statycznych równo 3 razy wolniejsze .
Pozniejsze wersje niż 2.4.1 nie potrfią zoptymalizować kodu .

Post by Łukasz 'Maly' Ostrowski
A wynik dla dynamic arraya i pointera na arraya jest taki sam,
jednocześnie gorszy, ponieważ masz jeden więcej poziom pointer
indirection. Bo generalnie dynamiczny array to po prostu
pointer na tablicę.

pytałęm się o te tablice dlatego ze FPC dawał ( daje ) różne wyniki dla
tablicy różnie zdefiniowanych a spełniające te same zadania ( i teoretycznie
powinny być równie szybkie ) np:
type TArray=Array[0..0] of Longint;
tab1:array of longint;
tab2:^TArray;
i dostęp do tab2 był znacznie szybszy .

[Łukasz 'Maly' Ostrowski]

Post by w***@poczta.onet.pl

Post by Łukasz 'Maly' Ostrowski
Albo masz przedwojenny komputer, albo naprawdę nie wiesz

Komputer wspólczesny 3 GHz .
Jak optymalizacja to coś więcej niż ustawienie w opcjiach kompilatora
odpowiedniego pola lub wywlołanie fpc z opcja -O3 to możesz mnie nauczyć tej
sztuki .

Nie, w uproszczeniu nie ;-). Mamy za mało opcji optymalizacji w fpc ;-).

Post by w***@poczta.onet.pl
Chyba rozgryzłęm problem -- winy jest FPC -- a właściwie jego wersje .
Przetestowałęm szybkośc programu dla FPC 2.4.1 , FPC 2.5.1 z czerwca (tej
używałęm ) i FPC 2.5.1 z lipca .

Czyli pewnie masz jakąś wersję rozwojową, i o problemy sam
się prosisz...

Post by w***@poczta.onet.pl
fpc 2.4.1 najlepiej optymalizuje --dla statycznych tablic tak samo jak delphi a
dla dynamicznych jest tylko 2 razy gorszy od delphi -- późniejsze wersje są już
dla dynamicznych i statycznych równo 3 razy wolniejsze .
Pozniejsze wersje niż 2.4.1 nie potrfią zoptymalizować kodu .

... co by było wytłumaczeniem, zgłoś developerom,
niech się wytłumaczą co zepsuli, bądź co Ty zepsułeś.

Post by w***@poczta.onet.pl

Post by Łukasz 'Maly' Ostrowski
A wynik dla dynamic arraya i pointera na arraya jest taki sam,
jednocześnie gorszy, ponieważ masz jeden więcej poziom pointer
indirection. Bo generalnie dynamiczny array to po prostu
pointer na tablicę.

pytałęm się o te tablice dlatego ze FPC dawał ( daje ) różne wyniki dla
tablicy różnie zdefiniowanych a spełniające te same zadania ( i teoretycznie
type TArray=Array[0..0] of Longint;
tab1:array of longint;
tab2:^TArray;
i dostęp do tab2 był znacznie szybszy .

Nie powinno tak być, tab1 i tab2 powinny być tak samo szybkie
z minimalnym marginesem różnicy potencjalnym. Chyba że range
check był włączony.

[Wiktor S.]

Post by w***@poczta.onet.pl
Przetestowałęm szybkośc programu dla FPC 2.4.1 , FPC 2.5.1 z czerwca
(tej używałęm ) i FPC 2.5.1 z lipca .

Bieżąca wersja Free Pascala to 2.4.0

To czego używasz to jakieś bety, wersje rozwojowe, czy coś takiego. Mają
prawo źle działać.

[w***@poczta.onet.pl]

Post by Wiktor S.
Bieżąca wersja Free Pascala to 2.4.0
To czego używasz to jakieś bety, wersje rozwojowe, czy coś takiego. Mają
prawo źle działać.

teraz to wiem -- chociaż zeby były aż takie róznice w wydajności !!

sprawdzilem jaki kod asemblera generuja te 3 wersje i kazda generuje ten sam
kod . Optymalizuja kod też w ten sam sposób . a jednak wynikowy program binarny
ma już inną wydajność .

[Łukasz 'Maly' Ostrowski]

Post by w***@poczta.onet.pl
teraz to wiem -- chociaż zeby były aż takie róznice w wydajności !!

Wersja rozwojowa może równie dobrze resetować Ci komputer, zepsuć
kran w kuchni i zgwałcić kota ;-).

Post by w***@poczta.onet.pl
sprawdzilem jaki kod asemblera generuja te 3 wersje i kazda generuje ten sam
kod . Optymalizuja kod też w ten sam sposób . a jednak wynikowy program binarny
ma już inną wydajność .

To co widzisz "w asemblerze" to już jest zoptymalizowana forma ;-).
Potencjalnie, jeżeli asm jest taki sam, , to wydajność powinna być
analogiczna/identyczna.

Zwróć uwage na ew różnice w allokacji rejestrów i innych
potencjalnie mało znaczących detali, które mogą wpływać na
out-of-order execution, cashe-trashing, etc etc.

[Wiktor S.]

Post by w***@poczta.onet.pl
i dla czego FPC generuje tak wolny kod ( 3 razy wolniejszy ) ??

dlaczego, dlaczego... FPC jest open source, więc go przyspiesz ;-)
robiłem kiedyś testy, i przegrywa z C# - a ten przecież kompiluje pod VM...