How much is and should be speed difference between static and dynamic arrays?

I wrote simple program (source at the end of the message), which compared speed of the same operations (I know there are many more operations, this was just a little sample test). Under WinXPsp2 with enough memory and celeron 2.4 GHz processor with array length 1000000 it took about 3910 ms for static and 4220 ms for dynamic array.

I didn't dig sources, but is it really hard to make them equally fast? (By the way, the speed difference was less, than I expected.)

{$mode objfpc}{$h+}
program testdynstat;
  uses sysutils;
var i,j,k : longint;
    a: array [0..999999] of byte;
    b: array of byte;
    c,c1,c2: Int64;
begin
write('Enter dyn array len (1-1000000):');readln(k);
if (k<1)or(k>1000000) then begin writeln('Be responsive!'); halt; end;
setlength(b,k);
{****************************************************************}
c1:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
for i:=1 to 1000 do
  for j:=0 to (k-1) do
    a[j]:=a[999999-j];
c2:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
{******************************************************************}
c:=c2-c1;
writeln('Total:',c,'ms');
{****************************************************************}
c1:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
for i:=1 to 1000 do
  for j:=0 to (k-1) do
    b[j]:=b[999999-j];
c2:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
{******************************************************************}
c:=c2-c1;
writeln('Total:',c,'ms');
end.

Пётр Косаревский wrote

I didn't dig sources, but is it really hard to make them equally fast? (By the way, the speed difference was less, than I expected.)

They are equally fast if you turn on register variables and if enough free registers are available (e.g. on a PPC; possibly also on an x86 if you have a very simple loop and little or no variables used both before and after the loop).

Jonas

It's wrong.

About the number of variables: you saw the whole source of the sample program.

About register variables: I compiled it with -O3rp4 options.

bigmac:~/fpc/test jonas$ ppcppc69 -O3 tarr
Target OS: Darwin for PowerPC
Compiling tarr.pp
Assembling testdynstat
Linking tarr
43 Lines compiled, 0.3 sec
bigmac:~/fpc/test jonas$ ./tarr
Enter dyn array len (1-1000000):1000000
Total:4789ms
Total:4809ms
bigmac:~/fpc/test jonas$ ./tarr
Enter dyn array len (1-1000000):1000000
Total:4897ms
Total:4787ms

About the number of variables: you saw the whole source of the sample program. About register variables: I compiled it with -O3rp4 options.

2.0.2 has less efficient register variable allocation. And your program requires 9 permanently free registers to be able to make optimal use of regvars. That is impossible to achieve on an x86, since in the best case you only have 7 (and usually less, since you need some scratch registers as well and ebp is occupied most of the time).

Jonas

Something new at the end of message.

Wow!
I'm glad for PowerPC, but anyhow: (formatted)
3954 4234
4000 4266
3938 4234
3890 4281
3907 4218
I repeat, celeron 2.4 GHz, winxpsp2.

In real program registers should be used more efficiently, especially when dealing with SEVERAL arrays, than for support of ONE dynamical array. So, the circumstances described by you can only be reached in special cases.

I don't mean to blame/flame or something, I just ask (in developers' mail list):

What can I do to speed up dynamical arrays?

What can I do to speed up static arrays?

NOW: the argument contra static arrays --- almost the same program, but "a[j]:=1" and "b[j]:=1" inside cycles, formatted output: 6641 3952
6655 3970
6610 3938
(I have already roughly specified my system, "fpc -O3rp4 222.pp")

Пётр Косаревский wrote

In real program registers should be used more efficiently, especially when dealing with SEVERAL arrays, than for support of ONE dynamical array.

We don't do anything special to use register not as efficiently as possible, and on the other hand making the register allocator more efficient is difficult (especially for a braindead architecture like x86).

So, the circumstances described by you can only be reached in special cases.

No, it's a very common cases on all cpus which have a reasonable amount of available registers.

What can I do to speed up dynamical arrays? What can I do to speed up static arrays?

Unless you can implement static single assignment in the compiler, probably nothing.

Jonas

If you really want to speed up both cases you need to use pointers and increase the pointer value in each iteration. This saves the indexing in every iteration.

Also place the code in small procedures so the register allocator has less conflicts for assigning registers to variables.

No, it's a very common cases on all cpus which have a reasonable amount of available registers.

With 3-4 dynamical arrays and several parameters?

> What can I do to speed up dynamical arrays? > > What can I do to speed up static arrays?

I mean: what is the shortest way to estimate speed?

I don't know, why with "a[j]:=a[999999-j]"
(yes, entering something other than 1000000 is likely to generate one exception or another, I did so to avoid processing array size as constant)
static is faster and with "a[j]:=1" and "a[j]:=a[0] xor a[j]" dynamic is faster (this one is about 7719 vs 4405, dynamic wins!).

Passages in answer to "braindead architecture":
I don't like x86 too, I hate windows, but it's what we have to deal with in our country: majority uses mainly pirated microsoft software and cheap x86 computers with large percent of buggy components (and those with money mainly use pirated software too, but buy expensive x86 computers with large percent of buggy expensive components). Linux is THE (because almost only) alternative solution (in my ), but I have not encountered seamlessly working X-window system (with language support at the microsoft level). The problem is: using GPL software may improve situation, but it's very slow process. I don't expect my brother (only music-movies-games-internet interests on computer) to choose non-microsoft something soon: he wanted to try, but it was major pain in the behind to make everything work, so he reverted to microsoft. So, I ask about things real for me. Sorry.
(And, if you, Jonas, have read down to this, and don't mind: how much does your PowerPC+monitor cost? What about software? [New sold computers in Russia in my city are supplied with obtruded licensed copy of Windows XP. You have to debate some time to buy "clean" PC. I have seen Macs only few times in my life, and these times were not in computer shops.])

Use 2.1.1. Compile with "-O2 -al" and check the assembler output. It depends on the application which variables are placed in a regiter and which don't. This has been said already a couple of times. The register allocator works already very efficient for common pratice so don't expect any changes from the compiler itself. First do more expiriments and research yourself, we've given you enough information do to.

Пётр Косаревский wrote

> No, it's a very common cases on all cpus which have a reasonable > amount of available registers. With 3-4 dynamical arrays and several parameters?

It all depends on how many parameters, how many other variables and how they are used. But a PPC has on average about 27 or so registers available for register variables (19 if the procedure makes any calls), and

>> What can I do to speed up dynamical arrays? >> >> What can I do to speed up static arrays? I mean: what is the shortest way to estimate speed?

The only way is profiling your complete program and looking where the bottlenecks are. Performance estimation is very complex and depends on a lot of factors. In most cases it is impossible to say in advance "X will will always be faster than Y".

I don't know either. Have a look at the generated assembler. Maybe in one case the optimizer misses something which it catches in the other case.

Passages in answer to "braindead architecture":

All your explanations do not change anything about the fact that it is a braindead architecture which is very hard to work with from a compiler point of view, and that we often only have 5 or so registers to work with (with only 3 available for regvars if there are any calls during the lifetime of the variable).

We are not on purpose generating suboptimal code for the x86. In fact, the x86 is the only target cpu for which we have a fairly complicated optimizer and for which the code generator uses a lot of tricks to get as much performance as possible. It is also the only one that really needs that, most others already get close to fairly optimal performance by just enabling register variables.

Jonas

If you really want to speed up both cases you need to use pointers and increase the pointer value in each iteration. This saves the indexing in every iteration.

Thank you, that was informative. Here are the results (one program at the end for completeness):

            ap^:=app^; inc(ap); dec(bp);

4780 4845

            ap^:=1; inc(ap);

3703 3703

            ap^:=a[0] xor ap^; inc(ap);

3813 4203

Now the question rises again in the original form (not very correct, see previous messages): WHY DYNAMICS ARE SLOWER?

1st program (slightly corrected silly input):

{$mode objfpc}{$h+}
program testdynstat;
  uses sysutils;
var i,j,k : longint;
    a: array [0..999999] of byte;
    b: array of byte;
    ap,bp:  ^byte;
    app,bpp: ^byte;
    c,c1,c2: Int64;
begin
write('Enter dyn array len (1000000):');readln(k);
if (k1000000) then begin writeln('Be responsive!'); halt; end;
setlength(b,k);
{****************************************************************}
c1:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
for i:=1 to 1000 do
  begin
  ;
  ;
  for j:=0 to (k-1) do
    begin
    ap^:=app^;
    inc(ap);
    dec(app);
    end;
  end;
c2:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
{******************************************************************}
c:=c2-c1;
writeln('Total:',c,'ms');
{****************************************************************}
c1:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
for i:=1 to 1000 do
  begin
  ;
  ;
  for j:=0 to (k-1) do
    begin
    bp^:=bpp^;
    inc(bp);
    dec(bpp);
    end;
  end;
c2:=Int64(TimeStampToMSecs(DateTimeToTimeStamp(Time)));
{******************************************************************}
c:=c2-c1;
writeln('Total:',c,'ms');
end.

"fpc -O3rp4 a111.pp", celeron 2.4 GHz, enough memory, winxpsp2.

Because of the copy-on-write mechanism. The reference count must be checked each time you do a write. This is normal. It's the same in Delphi, and a good reason for avoiding dynamic arrays.

You can use pointer arithmetics in FPC, it works as a dynamic array, but without the overhead.

i.e.

MyArray : PInteger;
begin
   // Equivalent to setlength(MyArray,ArraySize);
   GetMem(MyArray,SizeOf(Integer)*ArraySize);
   Try
     For I:=0 to ArraySize-1 do
       MyArray[i]:=SomeThing;
   Finally
     // Equivalent to setlength(MyArray,0);
     FreeMem(MyArray);
   end;
end;

Michael.

This topic (when trying to read it from the beginning to this point) is informative about its subject, but very confusing.

I have already been confused with blockread() and dynamic arrays. (It's about "formal const" parameter and ability to pass one kind of array as parameter and inability to pass the other.)

Also I constantly fear array assignments.

Probably I will use something similar to your example ("manual" dynamic array?).

Could anyone state the reason of the way dynamic arrays are implemented? Can I "disable" reference counting for some types or something?

Delphi compatibility. It's a Delphi construct.

Can I "disable" reference counting for some types or something?

No.

Ansistrings, WideStrings and Dynamic arrays are always reference counted.

Michael.

No, that is not true. He's now using plain pointers. The compiler does not keep track of the fact that a particular pointer points to a reference-counted type. Both loops are now equally fast in principle (and they are in practice on e.g. ppc).

The only "problem" is that c and c1 are also assigned registers, and become in use after the first loop. Because of this, bp and bpp can't be assigned a register anymore on x86 and are kept in memory instead of in a register. The register allocator puts registers with most conflicts in memory first, and these variables apparently have more conflicts than c/c1.

The used register allocation algorithm is not optimal (there are no known optimal algorithms, except for exhaustive ones), but it performs well in general. Everyone is free to attempt to optimize it further, as long as it doesn't break (i.e., it must give a valid result in all cases, and not spend an hour on compiling the compiler).

Jonas

Oh, and this particular case would in fact be avoided with static single assignment, which is not yet implemented in the compiler.

Jonas

if I read this:

Now the question rises again in the original form (not very correct, see previous messages): WHY DYNAMICS ARE SLOWER?

Then I understand this question as "about dynamics in the original form", hence my answer.

Michael.

If he understands right: if he reverted the order of the "loops" (big loops, each between time measurings) or separated "loops", splitting program, he'd get different results. However, splitting tests or reverting order doesn't seem to change timings.

It does (tests on linux/x86):

Original order:
Total:8199ms
Total:12038ms

Reversed order:
Total:9526ms
Total:13332ms

I.e., whichever comes first gets the most regvars and is the fastest. Timings are not identical because that machine is currently fully loaded.

Jonas

And on my machine it doesn't matter, whether I reverse them or even split.

When it will be more urgent (it will) I will:
1. Create pseudo dynamical arrays with GetMem() or something
2. Compare all three kinds in tests
3. Look at asm source with "-al" with disabled register variables Probably it would be more fruitful, but it is matter of week or two.

I think, that this discussion is somewhat pointless, because I neither by my skills nor by machines available can research this thing on different systems.

by the way I go home, Good luck!

Probably you are not using the latest 2.1.1 compiler.

Jonas