Hi all,

I don't know if rtl-optimilisation patches have a large priority, but nevertheless this patch improves the speed of the sysutils.uppercase and lowercase functions.

I fail to see how changing a while loop to a for loop improves speed ? I could understand if you'd use a PChar and use pointer math, but not this ?

Michael

BTW, in the snippet below, Length(S) is called once or at each iteration?

for i := Length(S) downto 1 do

Luiz

Luiz Américo wrote

BTW, in the snippet below, Length(S) is called once or at each iteration? for i := Length(S) downto 1 do

Once. Since it is the start value, that is even quite logical. However, even if it appeared in the end condition it would also be only calculated once at the start of the loop. This is even required for correctness, because it's possible to do something like

i := 5
for i := 1 to array_var[i] do

Jonas

Joost van der Sluis wrote

Hi all, I don't know if rtl-optimilisation patches have a large priority,

It depends if someone does it ;)

but nevertheless this patch improves the speed of the sysutils.uppercase and lowercase functions.

What about creating a table which does direct mapping? It's a lot faster.

A more efficient optimization would use a forward for-loop. Modern processors are better suited for "normal" loops*, and the most compilers optimize them better.

* For instance, the P4 has "data stream detection", which means that it can pre-cache data used in a first-to-last-byte manner, but not last-to-first-byte.

I wasn't completely sure, so i made a test-prog which called the function 50.000 times, and measured the time it took to run a few times.

And then again with the other version. (approx 2.5 sec against 1.4)

And I think it's because the removal of the begin/end. And Peter always says that you can't change the running variable in a for-loop because of the optimilisations... So i suppose that a for-loop has several optimilisations which a while doesn't...

Joost.

begin/end doesn't change any code.

And Peter always says that you can't change the running variable in a for-loop because of the optimilisations... So i suppose that a for-loop has several optimilisations which a while doesn't...

Yes.

Can you test also with a forward loop?

While this is _potentially_ true of a for-loop, don't expect it to hold in every situation. (and trust me, it's _certainly_ not because of the begin-end removal)

Jonas Maebe wrote:
[..]

Thanks

Luiz

Op Sat, 11 Jun 2005, schreef Christian Iversen:

The compiler can take advantage of automatic zero comparison, i.e. if counting to zero one can simply say:

dec loopcounter
jnz @loop

If one counts upwards, the compiler needs to do an extra compare:

inc loopcounter
cmp loopcounter,endvalue
jne @loop

I guess the automatic prefetch of the CPU gets only activated for very large strings, while with a very small loop body the extra cmp might be noticeable, especially if the loop counter is not a register variable in which case it causes an extra memory look up.

Daniël

Op Fri, 10 Jun 2005, schreef Florian Klaempfl:

It would be faster, but it would require two 256-byte tables, which'll help make people complain about code size even more. I would do it in an inner loop, but upper/lower case conversions are seldomly called in an inner loop. It also does some cache trashing, which is an often ignored speed issue in programming.

Daniël

Well. Discussion is nice, but what does the real world show ?

To compare, I made 6 versions of Lowercase:
1 - Sysutils
2 - Sysutils with Joost's improvement.
3 - Sysutils with Joost's improvement, but forward loop. 4 - Using PChar.
5 - Using PChar with lookup table and if check
5 - Using Pchar with lookup table and no check.

Result on an AMD 64 3000:
Lowercase time to execute: 00:00:01.563
Lowercase2 Time to execute: 00:00:01.363
Lowercase3 Time to execute: 00:00:01.394
Lowercase4 Time to execute: 00:00:00.999
Lowercase5 Time to execute: 00:00:01.021
Lowercase6 Time to execute: 00:00:00.948

So, judge for yourself. I think this is worth the 256 byte lookup table.

Michael.

-----------------------------------------------------------------------
{$mode objfpc}
{$h+}
program testsp;
uses sysutils;
Function Lowercase2(Const S : String) : String;
Var
  i : Integer;
begin
  result := S;
  for i := Length(S) downto 1 do
    if (result[i] in ['A'..'Z']) then result[i] := char(byte(result[i]) + 32);
end;
Function Lowercase3(Const S : String) : String;
Var
  i : Integer;
begin
  result := S;
  for i := 1 to Length(S) do
    if (result[i] in ['A'..'Z']) then result[i] := char(byte(result[i]) + 32);
end;
Function Lowercase4(Const S : String) : String;
Var
  i : Integer;
  P : PChar;
begin
  result := S;
  UniqueString(Result);
  P:=Pchar(Result);
  for i := 1 to Length(Result) do
    begin
    if (P^ in ['A'..'Z']) then P^ := char(byte(p^) + 32);
    Inc(P);
    end;
end;
Var
  ConvertTable : Array[0..255] of char;
Function Lowercase5(Const S : String) : String;
Var
  i : Integer;
  P : PChar;
begin
  result := S;
  UniqueString(Result);
  P:=Pchar(Result);
  for i := 1 to Length(Result) do
    begin
    if (P^ in ['A'..'Z']) then P^ := ConvertTable[byte(p^)];
    Inc(P);
    end;
end;
Function Lowercase6(Const S : String) : String;
Var
  i : Integer;
  P : PChar;
begin
  result := S;
  UniqueString(Result); // Needed or S will be modified.
  P:=Pchar(Result);
  for i := 1 to Length(Result) do
    begin
    P^ := ConvertTable[byte(p^)];
    Inc(P);
    end;
end;
Const
  Count = 50000;
Var
  S,T : String;
  I : integer;
  Sa,Se : TDateTime;
begin
  For I:=0 to 256 do
    ConvertTable[i]:=LowerCase(Char(i));
  S:='Some Test string which I wouLD LiKE to Test With This RAther SpeedY routine';
  For I:=1 to 5 do
    S:=S+S;
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase(S);
  Se:=Now;
  Writeln('Lowercase time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase2(S);
  Se:=Now;
  Writeln('Lowercase2 Time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase3(S);
  Se:=Now;
  Writeln('Lowercase3 Time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase4(S);
  Se:=Now;
  Writeln('Lowercase4 Time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase5(S);
  Se:=Now;
  Writeln('Lowercase5 Time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
  Sa:=Now;
  For I:=0 to Count do
    T:=LowerCase6(S);
  Se:=Now;
  Writeln('Lowercase6 Time to execute: ',FormatDateTime('hh:nn:ss.zzz',Se-SA));
end.

Op Sat, 11 Jun 2005, schreef Michael Van Canneyt:

So, judge for yourself. I think this is worth the 256 byte lookup table.

?

0.948/0.999 = 95 %

So, we 5% speed improvement from using a table; this is much worse than I thought and can easily be undone in real world by the increased cache trashing. Of course any speed improvement is welcome, but IMHO this is not worth the size increase.

Remember, this just 1 procedure, and 256 byte extra is nothing compared to the whole unit.

But if we start doing this kind of optimization accross the entire unit, we'll get a horribly bloated unit.

Also, if speed is really important, nothing can beat a hand-optimized assembler routine that does the operation without jump and by means of 32-bit registers does 4 have hand optimized string routines in the rtl, I don't see why it cannot be done in sysutils.

Daniël

Op Sat, 11 Jun 2005, schreef Daniël Mantione:

For what it's worth, I found this on my harddrive. It uses shortstring, assumes oldfpccall and looking at the code it doesn't look that it's possible to process 4 bytes at once this way.

Daniël

function uppercase(const s:string):string;assembler;

asm
mov esi,s
mov edi,@result
lodsb
stosb
movzx ecx,al
jecxz @a2
@a1:
lodsb
cmp al,'a'
sbb bl,bl
cmp al,'z'+1
sbb bh,bh
not bh
or bl,bh
not bl
and bl,32
sub al,bl
stosb
dec cl
jnz @a1
@a2:
end;

function lowercase(const s:string):string;assembler;

asm
mov esi,s
mov edi,@result
lodsb
stosb
movzx ecx,al
jecxz @a2
@a1:
lodsb
cmp al,'A'
sbb bl,bl
cmp al,'Z'+1
sbb bh,bh
not bh
or bl,bh
not bl
and bl,32
add al,bl
stosb
dec cl
jnz @a1
@a2:
end;

If we're gonna hold a discussion like this for every optimilisation, it isn't worth the effort imho. But now we're busy with it:

You shoudn't use the sysutils's version. It's better to copy the source from sysutils to the testprogram.

I've added that (lowercase1) and i've added Daniel's asm-procedure...

Further I've used the more precise timer-utils from Tom. Most remarkably is that now my lowercase is actually _slower_ then the one in the RTL. Yesterday and in Michael's test it's the other way around?

Results: (compiled with -OG1)

lowercase execution time: 90619
lowercase 1 execution time: 94293
lowercase 2 execution time: 96657
lowercase 3 execution time: 95163
lowercase 4 execution time: 68910
lowercase 5 execution time: 68030
lowercase 6 execution time: 69403
lowercase 7 execution time: 51839

(notice the difference between the lowercase in the rtl, and the same code directly in the unit, caused by different compiler-directives?)

I aggree with Daniel that the use of a table isn't usefull. For that, also look at GenericAnsiUpperCase in sysstr.inc

Joost.

To reduce porting efforts, I would prefer to have sysutils clean of assembler code.

I've committed the PChar version without lookup table. It gives a nice speed gain (uses only 64% of the time), and doesn't increase the size of the executable.

Michael.

Timing for Daniel's procedure doesn't count, it's shortstrings. They are limited to 256 characters, obviously this will execute faster; The ansistring S used is 2400 characters (so a factor 10 longer).

Depends on the used optimizations, I suppose.

Michael.

Op Sat, 11 Jun 2005, schreef Michael Van Canneyt:

It is also a bad test, it should be converted to ansistring for proper comparison. The string s is declared in $H+ state, so the compiler has to convert an ansistring to shortstring, then do the lowercase and then convert the result back to ansistring to be able to assign to t. The fact that it is still faster shows what speed gains you can still get anno 2005.

The ansistring S used is 2400 characters (so a factor 10 longer).

No, Joost's test uses a much shorter string (which is also the most likely reason the benchmarks give contradictory results).

Daniël

I'm not contesting that; but here I think that the use of pascal is more important, for porting's sake.

To show that there is room for improvement in FPC, these are the Kylix timings:

Lowercase time to execute: 00:00:00.792
Lowercase2 Time to execute: 00:00:00.705
Lowercase3 Time to execute: 00:00:00.665
Lowercase4 Time to execute: 00:00:00.438
Lowercase5 Time to execute: 00:00:00.472
Lowercase6 Time to execute: 00:00:00.569

And their routine is pure pascal. (first, lowercase timing) They are, without exception, much faster than FPC.

What is more, if I compile my test program with Optimizations (-OG2), I get the following timings (times between brackets are without optimization):

Lowercase time to execute: 00:00:01.571
Lowercase2 Time to execute: 00:00:01.287 (00:00:01.362) Lowercase3 Time to execute: 00:00:01.280 (00:00:01.395) Lowercase4 Time to execute: 00:00:00.871 (00:00:00.996) Lowercase5 Time to execute: 00:00:00.921 (00:00:01.064) Lowercase6 Time to execute: 00:00:00.946 (00:00:00.953)

In which the version without lookup is actually faster than the one with lookup. If compared with the timings I posted originally, there is a 10% gain for Lowercase4, showing that optimizations are important :-)

Last, I inlined all functions (except the sysutils one):

Lowercase time to execute: 00:00:01.665
Lowercase2 Time to execute: 00:00:00.869
Lowercase3 Time to execute: 00:00:00.910
Lowercase4 Time to execute: 00:00:00.439
Lowercase5 Time to execute: 00:00:00.566
Lowercase6 Time to execute: 00:00:00.574

Now this is truly remarkable, because it comes closer to the Kylix timings. Any explanation from the compiler people ?

My apologies, I (wrongly) assumed he adapted the program I posted and left S as-is.

In my opinion, all this shows that one should be careful with how one designs tests :-)

Michael.

Op Sat, 11 Jun 2005, schreef Michael Van Canneyt:

I'm not contesting that; but here I think that the use of pascal is more important, for porting's sake.

As long as the Pascal version remains available (for exactly the those portability reasons), I am not against it. Instead, I hope someone will optimize some stuff as we cannot get competitive speed results with gcc and Delphi without optimized libraries.

Sysutils already consists of a lot of include files, one more won't hurt its portability and maintainability a lot.

However, I will not spend my time on it. I think spending to on improving FPC's code generation is a much better time investment for me.

Daniël

One of the major optimisations for the LowerCase function is actually for the case when the function does nothing!

The most expensive operation in the whole LowerCase function is the UniqueString allocation for when the string changes. For the case where the string is already in lower case it is important not call UniqueString. It makes a 600% difference is speed on Delphi for my test case (haven't tested on fpc yet).

This is why it is important to have this line in Lowercase2 for example:

    if (result[i] in ['A'..'Z']) then

It prevents the UniqueString call if nothing changes.

Just for comparison, here is the implementation in Fundamentals. The pure pascal version is like your lowercase2.

{$IFDEF USE_ASM386}
procedure ConvertLower(var S: AnsiString);
asm
OR EAX, EAX
JZ @Exit
PUSH EAX
MOV EAX, [EAX]
OR EAX, EAX
JZ @ExitP
MOV ECX, [EAX - 4]
OR ECX, ECX
JZ @ExitP
XOR DH, DH
@L2:
DEC ECX
MOV DL, [EAX + ECX]
CMP DL, 'A'
JB @L1
CMP DL, 'Z'
JA @L1
OR DH, DH
JZ @Uniq
@L3:
ADD DL, 'a' - 'A'
MOV [EAX + ECX], DL
@L1:
OR ECX, ECX
JNZ @L2
OR DH, DH
JNZ @Exit
@ExitP:
POP EAX
@Exit:
RET
@Uniq:
POP EAX
PUSH ECX
PUSH EDX
CALL UniqueString
POP EDX
POP ECX
MOV DH, 1
JMP @L3
end;
{$ELSE}
procedure ConvertLower(var S: AnsiString);
var F : Integer;
begin

  For F := 1 to Length(S) do
    if S[F] in ['A'..'Z'] then
      S[F] := AnsiChar(Ord(S[F]) + 32);

end;
{$ENDIF}

Regards
David

And in general for FPC :-)

Michael.

That is why I use pchar and one uniquestring;
It prevents all these automated uniquestring calls.

Just for comparison, here is the implementation in Fundamentals. The pure pascal version is like your lowercase2.

It's quite different; the use of a var changes it a lot;
An in-place replacement routine is of course faster...

Michael.

Op Sat, 11 Jun 2005, schreef Michael Van Canneyt:

That is why I use pchar and one uniquestring; It prevents all these automated uniquestring calls.

Isn't it a better idea to build a new string, i.e. we setlength result and copy characters either modified or unmodified? That'll save an unnecessary copy of the string.

Daniël

The Delphi routine does this, but when compiled with FPC, it runs slower.

Michael.

Some more test results with PII 350MHz and
two additional implementations with lookup table:

Kylix:
lowercase execution time: 336887
lowercase 1 execution time: 380923
lowercase 2 execution time: 375411
lowercase 3 execution time: 369814
lowercase 4 execution time: 320665
lowercase 5 execution time: 300580
lowercase 6 execution time: 219047
lowercase 7 execution time: 356606
lowercase 8 execution time: 249913
lowercase 9 execution time: 252431

FPC -OG1
lowercase execution time: 474871
lowercase 1 execution time: 497440
lowercase 2 execution time: 464547
lowercase 3 execution time: 488088
lowercase 4 execution time: 322630
lowercase 5 execution time: 321486
lowercase 6 execution time: 299599
lowercase 7 execution time: 279863
lowercase 8 execution time: 282185
lowercase 9 execution time: 181006

FPC -OG2
lowercase execution time: 475327
lowercase 1 execution time: 486661
lowercase 2 execution time: 449136
lowercase 3 execution time: 471541
lowercase 4 execution time: 282642
lowercase 5 execution time: 285662
lowercase 6 execution time: 260930
lowercase 7 execution time: 261744
lowercase 8 execution time: 268638
lowercase 9 execution time: 169120

FPC -Og1
lowercase execution time: 474512
lowercase 1 execution time: 504779
lowercase 2 execution time: 472132
lowercase 3 execution time: 491122
lowercase 4 execution time: 324513
lowercase 5 execution time: 424865
lowercase 6 execution time: 714593
lowercase 7 execution time: 277637
lowercase 8 execution time: 703568
lowercase 9 execution time: 177973

FPC -Og2
lowercase execution time: 474981
lowercase 1 execution time: 500521
lowercase 2 execution time: 472871
lowercase 3 execution time: 483081
lowercase 4 execution time: 301566
lowercase 5 execution time: 418570
lowercase 6 execution time: 707521
lowercase 7 execution time: 272874
lowercase 8 execution time: 694156
lowercase 9 execution time: 175725

Martin Schreiber wrote

Some more test results with PII 350MHz and two additional implementations with lookup table:

Try also with register variables on (-O???r), it will probably more closely match Kylix' results then in case of the loop versions.

Jonas

Where do I find the cpu/cpu-timer unit guys...
Directory? Download link?

Thank you.

|
| On 12 Jun 2005, at 00:12, Martin Schreiber wrote: |
| > Some more test results with PII 350MHz and
| > two additional implementations with lookup table: |
| Try also with register variables on (-O???r), it will probably more | closely match Kylix' results then in case of the loop versions. |
|
| Jonas
|
|
| _______________________________________________
| fpc-devel maillist -
| http://lists.freepascal.org/mailman/listinfo/fpc-devel

| Where do I find the cpu/cpu-timer unit guys...
| Directory? Download link?
|
| Thank you.
|

Is this the one? ;-)
http://members.yline.com/~tom_at_work/

|
| |
| | On 12 Jun 2005, at 00:12, Martin Schreiber wrote: | |
| | > Some more test results with PII 350MHz and
| | > two additional implementations with lookup table: | |
| | Try also with register variables on (-O???r), it will probably more | | closely match Kylix' results then in case of the loop versions. | |
| |
| | Jonas
| |
| |
| | _______________________________________________ | | fpc-devel maillist -
| | http://lists.freepascal.org/mailman/listinfo/fpc-devel |
| _______________________________________________
| fpc-devel maillist -
| http://lists.freepascal.org/mailman/listinfo/fpc-devel

Jonas Maebe wrote

Try also with register variables on (-O???r), it will probably more closely match Kylix' results then in case of the loop versions.

Kylix:
lowercase   execution time: 336887
lowercase 1 execution time: 380923
lowercase 2 execution time: 375411
lowercase 3 execution time: 369814
lowercase 4 execution time: 320665
lowercase 5 execution time: 300580
lowercase 6 execution time: 219047
lowercase 7 execution time: 356606
lowercase 8 execution time: 249913
lowercase 9 execution time: 252431

-OG1r
lowercase execution time: 465596
lowercase 1 execution time: 378780
lowercase 2 execution time: 389711
lowercase 3 execution time: 375878
lowercase 4 execution time: 225029
lowercase 5 execution time: 228708
lowercase 6 execution time: 158026
lowercase 7 execution time: 264930
lowercase 8 execution time: 182939
lowercase 9 execution time: 165446

-OG2r
lowercase execution time: 471705
lowercase 1 execution time: 378160
lowercase 2 execution time: 388112
lowercase 3 execution time: 395773
lowercase 4 execution time: 227191
lowercase 5 execution time: 227925
lowercase 6 execution time: 156750
lowercase 7 execution time: 258313
lowercase 8 execution time: 181842
lowercase 9 execution time: 165069

-Og1r
lowercase execution time: 464843
lowercase 1 execution time: 486571
lowercase 2 execution time: 463269
lowercase 3 execution time: 472342
lowercase 4 execution time: 247544
lowercase 5 execution time: 399030
lowercase 6 execution time: 646651
lowercase 7 execution time: 263588
lowercase 8 execution time: 636059
lowercase 9 execution time: 170660

-Og2r
lowercase execution time: 470038
lowercase 1 execution time: 487086
lowercase 2 execution time: 459035
lowercase 3 execution time: 476304
lowercase 4 execution time: 243678
lowercase 5 execution time: 399953
lowercase 6 execution time: 646284
lowercase 7 execution time: 265147
lowercase 8 execution time: 632796
lowercase 9 execution time: 169471

Martin

Some more experience:

7a: like 7 but ansi string
9a: like 9, without loop instruction
10: like 6, loop in assembler
10a like 10, without loop instruction

(PII, 350MHz)

Kilix:
lowercase execution time: 335536
lowercase 1 execution time: 369539
lowercase 2 execution time: 377384
lowercase 3 execution time: 367407
lowercase 4 execution time: 319018
lowercase 5 execution time: 317572
lowercase 6 execution time: 220341
lowercase 7 execution time: 343903
lowercase 7a execution time: 369064
lowercase 8 execution time: 259604
lowercase 9 execution time: 256799
lowercase 9a execution time: 201195
lowercase 10 execution time: 279708
lowercase 10a execution time: 223645

-OG2r
lowercase execution time: 467200
lowercase 1 execution time: 385648
lowercase 2 execution time: 395934
lowercase 3 execution time: 403329
lowercase 4 execution time: 231616
lowercase 5 execution time: 237851
lowercase 6 execution time: 160797
lowercase 7 execution time: 262418
lowercase 7a execution time: 285810
lowercase 8 execution time: 184037
lowercase 9 execution time: 171197
lowercase 9a execution time: 113786
lowercase 10 execution time: 197823
lowercase 10a execution time: 140806

-Og2r
lowercase execution time: 465173
lowercase 1 execution time: 490236
lowercase 2 execution time: 460353
lowercase 3 execution time: 478584
lowercase 4 execution time: 245922
lowercase 5 execution time: 401423
lowercase 6 execution time: 646020
lowercase 7 execution time: 265284
lowercase 7a execution time: 285793
lowercase 8 execution time: 632552
lowercase 9 execution time: 169229
lowercase 9a execution time: 114605
lowercase 10 execution time: 204204
lowercase 10a execution time: 143213

Op Sat, 11 Jun 2005, schreef L505:

Hmmm... They managed to do the 4 bytes in parallel. I can figure out how it works, but it is interresting and should be fast.

Replace the loop by:

  repeat
    if exitcondition then
      break;
  until false;

... this will generate exactly the same code, but is more according to the rules of art.

Next, make it 64-bit safe, i.e. change cardinal(p) to ptruint(p). There
are also potential speed improvements, i.e.: c2:=not(c1) and $80808080.

If this is done it can be included in the sysutils unit.

It should also be kept in mind that this code assumes 32-bit, even though it'll run on 64-bit, it won't be optimal on 64-bit (but this faster than byte per byte I guess).

If you want to submit assembler routines (I think that LowerCaseSha2 trick is a good basis to build one), take the following guidelines in mind:

* It should be worthwhile to use assembler, i.e. if you don't get more than 10% speed gain it isn't worth it; it's better to wait until the compiler generates better code.
* Don't use CPU-specific optimizations. I.e. code will have to run all kinds of machines, Pentium-4 or Athlon specific optimizations aren't a good idea.

Do it this way:

* At the top of the implementation section, add {$i i386.inc}.
* In i386.inc add the assembler version and do a {$define have_lowercase}
* Put the Pascal implementation between a {$ifndef have_lowercase} and

  {$endif}

This way the impact on the maintainability and portability is rather low.

Daniël

Op Sun, 12 Jun 2005, schreef Daniël Mantione:

I can figure out how it works, but it is interresting and should be fast.

I can't figure out...

Sorry.

Daniël

http://dennishomepage.gugs-cats.dk/LowerCaseChallenge.htm

LowerCaseShaPas2_c
This one here is in Pascal, using GOTO and LABEL which consistently work fast on both -Og and -OG
But no one wants to maintain a GOTO and a LABEL..

[LowerCaseShaPas2_c] was slightly slower than [lowercase 6 ] (second fastest) in -OG mode
[LowerCaseShaPas2_c] was slightly faster than [lowercase 9] (still second fastest) in -Og mode .. so it's more consistent across compiler options it seemed

So maybe [lowercase 6 ] result should be submitted to fastcode to be tested?

Also, if no one wants to use the assembly functions and GOTO/LABEL functions in the RTL due to code bloat/maintenance, we could always offer an optional unit where people could call the fast functions only if they needed them badly. Just like how fastcode does, external from the VCL.

Asm is ok as well as long as there is also a good pascal implementation.

and GOTO/LABEL functions in

I've no problem with goto/label as long as it affects only a litte part of the rtl.

I use fastcode stuff some times, I just never spend too much time figuring out how all the code works.

The way I do it is I create my software application first in Pascal.. Then if I find a huge bottleneck, I pull in a optimized function in place of the old one.. even if I dont' understand the optimized functions entirely.

I'm sure lot's of people know and do this, but I want to make a point that sometimes 90 percent of your common GUI app doesn't need to be optimized.. only certain concentrated sections of the app need to be optimized, like search and replace routines, or especially with a compiler who is running through text over and over again (patronizing the compiler team here).

With lowercase function I'm sure optimizations will help a lot if we are using it to do bulk translations of 1000's of MiXedCaSe text files from crackers/hackers whO wRiTe lIke tHiS. (ping Carl Eric ..j/k) More realistically, it could also help in a CGI app say if you were converting people's web posts to lower case (if hundreds of people posting at the same time for example).

Lars

Op Sun, 12 Jun 2005, schreef Daniël Mantione:

I can figure out how it works, but it is interresting and should be fast.

I can't figure out...

Sorry.

Daniël

Why call it when it might not be necessary??

My point is that you can make the function MUCH faster for the case where the function doesn't modify the string by not calling UniqueString at all.

with similar probability) is much more time-consuming that an unnecessary function call.

Bye Uberto

ps. is there a way to see the assembly producted by a FPC function?

Op Sun, 12 Jun 2005, schreef Uberto Barbini:

Yes, but the call needs to do memory allocation and a string copy, so it is not just the call.

ps. is there a way to see the assembly producted by a FPC function?

Sure. Depending on your prefered asm style:

fpc -Anasmelf -a -s filename.pas
fpc -Agas -a -s filename.pas

Daniël

From: Martin Schreiber
To: FPC developers' list <fpc-

Subject: Re: [fpc-devel] Patch to speed up Uppercase/Lowercase functions
Date sent: Sun, 12 Jun 2005 00:12:44 +0200

What's the intended purpose of jz in the following fragment from lowercase9:

mov ecx,[ebx-4] //length
jz @l1

As far as I know, mov instruction doesn't set zero flag. Zero length is checked earlier in the code, though, so it doesn't matter for that
- just the jz instruction seems to be useless there.

Tomas

I thought that UniqueString() goal was exactly to avoid the string copy...

Thanks!
I wonder if anyone has checked why Kylix version is faster comparing the assembler code.

I read the thread but I haven't studied well! ;)

Bye Uberto

Op Sun, 12 Jun 2005, schreef Uberto Barbini:

Of course, we know our strong and weak points very well.

Borland's compiler does register variables better than FPC and can do induction variables. This has a large impact on the code generation in general. FPC beats Delphi when you start to use int64 or the heap (like object oriented programming). It can also provide some kick ass FPU performance when using SSE2.

Daniël

Hello,

I was looking at this discussion and decided to put my 5 cents :)

I made 2 fastest modifications based on Lowercase4.

Lowercase41 is optimized for input which is already lowercased. Lowercase42 slower if input is already lowercased and a bit faster for mixed case input.

The best results are acheived with -OG3r optimizations.

Here are results at my system (mixed case input):

Lowercase2 Time to execute: 00:00:00.828
Lowercase3 Time to execute: 00:00:00.860
Lowercase4 Time to execute: 00:00:00.609
Lowercase41 Time to execute: 00:00:00.547
Lowercase42 Time to execute: 00:00:00.546
Lowercase5 Time to execute: 00:00:00.625
Lowercase6 Time to execute: 00:00:00.641

Here are results at my system (lowered case input):

Lowercase2 Time to execute: 00:00:00.344
Lowercase3 Time to execute: 00:00:00.329
Lowercase4 Time to execute: 00:00:00.437
Lowercase41 Time to execute: 00:00:00.281
Lowercase42 Time to execute: 00:00:00.359
Lowercase5 Time to execute: 00:00:00.437
Lowercase6 Time to execute: 00:00:00.642

--------

Function Lowercase41(Const S : String) : String;
var
  i: Integer;
  P: PChar;
  Changed: boolean;
begin
  Changed:=False;
  P := PChar(S);
  for i := 1 to Length(S) do begin
    if P^ in ['A'..'Z'] then begin
      if not Changed then begin
        Changed := True;
        Result := S;
        UniqueString(Result);
        P := PChar(Result) + i - 1;
      end;
      Inc(byte(P^));
    end;
    Inc(P);
  end;
  if not Changed then
    Result := S;
end;
Function Lowercase42(Const S : String) : String;
var
  i: Integer;
  P: PChar;
begin
  Result := S;
  UniqueString(Result);
  P := PChar(Result);
  i := Length(Result);
  while i > 0 do begin
    if P^ in ['A'..'Z'] then
      Inc(byte(P^));
    Inc(P);
    Dec(i);
  end;
end;

--------
Yury Sidorov,

Daniël Mantione wrote

Borland's compiler does register variables better than FPC and can do induction variables. This has a large impact on the code generation in general.

I thought I saw that FPC beat Kylix in several cases in the timings that were posted.

Jonas

Oh,

I found the bug.
There should be:

Inc(byte(P^), 32);

instead of previously posted:

Inc(byte(P^));

Here is correct implementation:

----

Function Lowercase41(Const S : String) : String;
var
  i: Integer;
  P: PChar;
  Changed: boolean;
begin
  Changed:=False;
  P := PChar(S);
  for i := 1 to Length(S) do begin
    if P^ in ['A'..'Z'] then begin
      if not Changed then begin
        Changed := True;
        Result := S;
        UniqueString(Result);
        P := PChar(Result) + i - 1;
      end;
      Inc(byte(P^), 32);
    end;
    Inc(P);
  end;
  if not Changed then
    Result := S;
end;
Function Lowercase42(Const S : String) : String;
var
  i: Integer;
  P: PChar;
begin
  Result := S;
  UniqueString(Result);
  P := PChar(Result);
  i := Length(Result);
  while i > 0 do begin
    if P^ in ['A'..'Z'] then
      Inc(byte(P^), 32);
    Inc(P);
    Dec(i);
  end;
end;

Hello,

It seem my original post was lost, so I repost it...

---

I was looking at this discussion and decided to put my 5 cents :)

I made 2 fastest modifications based on Lowercase4.

Lowercase41 is optimized for input which is already lowercased. Lowercase42 slower if input is already lowercased and a bit faster for mixed case input.

The best results are acheived with -OG3r optimizations.

Here are results at my system (mixed case input):

Lowercase2 Time to execute: 00:00:00.828
Lowercase3 Time to execute: 00:00:00.860
Lowercase4 Time to execute: 00:00:00.609
Lowercase41 Time to execute: 00:00:00.547
Lowercase42 Time to execute: 00:00:00.546
Lowercase5 Time to execute: 00:00:00.625
Lowercase6 Time to execute: 00:00:00.641

Here are results at my system (lowered case input):

Lowercase2 Time to execute: 00:00:00.344
Lowercase3 Time to execute: 00:00:00.329
Lowercase4 Time to execute: 00:00:00.437
Lowercase41 Time to execute: 00:00:00.281
Lowercase42 Time to execute: 00:00:00.359
Lowercase5 Time to execute: 00:00:00.437
Lowercase6 Time to execute: 00:00:00.642

--------

Function Lowercase41(Const S : String) : String;
var
  i: Integer;
  P: PChar;
  Changed: boolean;
begin
  Changed:=False;
  P := PChar(S);
  for i := 1 to Length(S) do begin
    if P^ in ['A'..'Z'] then begin
      if not Changed then begin
        Changed := True;
        Result := S;
        UniqueString(Result);
        P := PChar(Result) + i - 1;
      end;
      Inc(byte(P^), 32);
    end;
    Inc(P);
  end;
  if not Changed then
    Result := S;
end;
Function Lowercase42(Const S : String) : String;
var
  i: Integer;
  P: PChar;
begin
  Result := S;
  UniqueString(Result);
  P := PChar(Result);
  i := Length(Result);
  while i > 0 do begin
    if P^ in ['A'..'Z'] then
      Inc(byte(P^), 32);
    Inc(P);
    Dec(i);
  end;
end;

--------
Yury Sidorov,

Tomas Hajny wrote

As far as I know, mov instruction doesn't set zero flag. Zero length is checked earlier in the code, though, so it doesn't matter for that - just the jz instruction seems to be useless there.

You are right of course, i am not very familiar with IA-32. There was a test ecx,ecx some times ago...

Do you see more errors?

Martin

Borland's compiler does register variables better than FPC and can do induction variables. This has a large impact on the code generation in general.

|>I thought I saw that FPC beat Kylix in several cases in the timings |>that were posted.

I saw this too, so what do you mean Daniël .. in the -Og cases?

FPC is beating Delphi 5 in my tests:

FPC with -OG3r:

Lowercase2 Time to execute: 00:00:00.828
Lowercase3 Time to execute: 00:00:00.876
Lowercase4 Time to execute: 00:00:00.593
Lowercase41 Time to execute: 00:00:00.547
Lowercase42 Time to execute: 00:00:00.548
Lowercase5 Time to execute: 00:00:00.625
Lowercase6 Time to execute: 00:00:00.641

Delphi 5 with full optimization:

Lowercase2 Time to execute: 00:00:00.859
Lowercase3 Time to execute: 00:00:00.953
Lowercase4 Time to execute: 00:00:00.735
Lowercase41 Time to execute: 00:00:00.671
Lowercase42 Time to execute: 00:00:00.469
Lowercase5 Time to execute: 00:00:00.516
Lowercase6 Time to execute: 00:00:00.640

---
Yury Sidorov,

Daniël Mantione wrote

I can't figure out...

loop:

   //flags for chars $80..$ff are removed later so we have
   // only to care about chars $00..$7f
    ch1:=pinteger(p)^;    //original char
    ch3:=$7F7F7F7F;       //msb remove mask
    ch2:=ch1;             //copy of original
    ch3:=ch3 and ch1;     //originalchars with msb 0 -> <= $7f
    ch2:=ch2 xor (-1);    //complement
    ch3:=ch3 + $25252525; //msb 1 for all chars > $7f - $25 = $5a -> >'Z'
            //$00..$5a -> $25..$7f
            //$5b..$7f -> $80..$a4
    ch2:=ch2 and $80808080; //msb 1 for all chars < $80
                            //to remove flags of chars > $7f
    ch3:=ch3 and $7F7F7F7F; //(chars mod $80 + $25) mod $80
            //$00..$5a -> $25..$7f
            //$5b..$7f -> $80..$a4 -> $00..$24
    ch3:=ch3 + $1A1A1A1A;   //original + $25 + $1a = original + $3f
                 //-> msb 1 for all chars > $7f - $3f = $40 -> >='A'
            //$00..$5a -> $25..$7f -> $3f..$99
            //     '@'
            //$00..$40 -> $25..$65 -> $3f..$7f             msb 0
            //'A'  'Z'
            //$41..$5a -> $66..$7f -> $80..$99             msb 1
            //'['
            //$5b..$7f -> $80..$a4 -> $00..$24 ->$1a..$3e  msb 0
    inc(p,4);
    ch3:=ch3 and ch2;
        //remove flags for chars > $7f, remove bit 0..6
    if cardinal(p)>=cardinal(term) then goto last;
    ch3:=ch3 shr 2;        //$80 -> $20 -> shift 'A' to 'a'
    ch1:=ch1 + ch3;        //'A'..'Z' -> 'a'..'z'
    pinteger(p+dist)^:=ch1;
    goto loop;

Ingeniously!

Martin

Borland's compiler does register variables better than FPC and can do induction variables. This has a large impact on the code generation in general.

|>I thought I saw that FPC beat Kylix in several cases in the timings |>that were posted.

I saw this too, so what do you mean Daniël .. in the -Og cases?

Op Sun, 12 Jun 2005, schreef L505:

In had Michael's initial results in my head, But, in general this are things were FPC isn't up to competing compilers yet. But FPC isn't slow at all, as the other results slow :)

And... it promises a lot for the future...

Daniël

Err, sorry for a stupid question, but what would the above code do?

There also is jecx, (jeecx ? :-), but I don't know if it is faster than writing it out.

Marco van de Voort wrote

There also is jecx, (jeecx ? :-),

jecxz

but I don't know if it is faster than writing it out.

Pretty much all of those old complex instructions (enter, loop, jecxz, xlatb, ...) are slower than the alternatives.

Jonas

I was thinking about this before I relpied, and knew this was the case for P5-P6 core. However is this verified/documented for generation 7 CPU's ? (Athlon/Netburst ?)

Why would they suddenly start spending silicon on making instructions faster which no modern compiler generates anymore?

Jonas

Because the decoder units are now more advanced, and (given the total transistor count) it is not that expensive, relatively.

However I partially agree that I think it is not likely. However I went over this a lot of times, and nobody ever came up with a test or reference to back it up. That's unscientific.

Maybe I should ask on nasm's forum or some other handcoders place.

22:55:42,18 >del withstat.exe

22:55:42,19 >ppc386 -Op1 -al -gl withstat
Free Pascal Compiler version 2.1.1 [2005/05/25] for i386 Copyright (c) 1993-2005 by Florian Klaempfl
Target OS: Win32 for i386
Compiling withstat.pas
withstat.pas(20,50) Warning: Comment level 2 found Assembling withstat
Linking withstat.exe
42 Lines compiled, 1.6 sec
withstat.pas(19,12) Error: Compilation aborted
An unhandled exception occurred at $00000000 :
EAccessViolation : Access violation
$00000000
$004C96DD TWITHNODE__DESTROY, line 851 of nmem.pas $00546AF9
$0045CF4E TUNARYNODE__DESTROY, line 848 of node.pas $0045D4BF TBINARYNODE__DESTROY, line 962 of node.pas $00546AF9
$004C63FF TBLOCKNODE__DESTROY, line 374 of nbas.pas $00546AF9
$0044643F TPROCDEF__DESTROY, line 3886 of symdef.pas $00546AF9
$0040C51E TINDEXARRAY__CLEAR, line 1974 of cclasses.pas $0040C3F4 TINDEXARRAY__DESTROY, line 1951 of cclasses.pas $0043247D TSYMTABLE__DESTROY, line 192 of symbase.pas $00546AF9
$0041AE22 TMODULE__DESTROY, line 526 of fmodule.pas $0047C520 TPPUMODULE__DESTROY, line 136 of fppu.pas $00546AF9

The program:

{$define withWITH}
{$define some_inlines}
{$r+,q+}
{$define integ64}
PROGRAM WithStat ;
  CONST
    MaxFmtBCDFractionSize = 64 ;
  TYPE
    myIntType = {$ifdef integ32} LongInt {$endif} {$ifdef integ64} int64
{$endif} ;
  TYPE
    pBCD = ^ tBCD ;
    tBCD = PACKED RECORD
      Precision : 0..maxfmtbcdfractionsize ;  { 1{joke?}..64 }
      SignSpecialPlaces : Byte ;      { Sign:1, Special:1, Places:6 }
      Fraction : PACKED ARRAY [ 0..( MaxFmtBCDFractionSize DIV 2 ) - 1 ] OF
Byte ;
     END;
  CONST
    NegBit = $80 ;
  PROCEDURE BCDNegate ( VAR BCD : tBCD ) ; {$ifdef some_inlines} INLINE ;
{$endif}
    BEGIN
{$ifdef withWITH}
      WITH BCD DO
       IF Precision  0
        THEN SignSpecialPlaces := SignSpecialPlaces XOR NegBit ;
{$else}
      IF BCD.Precision  0
       THEN BCD.SignSpecialPlaces := BCD.SignSpecialPlaces XOR NegBit ;
{$endif}
     END ;
  BEGIN
   END.

The error does not occur if either the "withWITH" or the "some_inlines" stays undefined.

With other words, the combination of WITH-statement and INLINE is unhealthy.

Gerhard

With other words, the combination of WITH-statement and INLINE is unhealthy.

Correct. It is a known issue and there is already a bug report about it

Anybody followed the discussion, e.g. which version should be included :)?