Small speedup for FExpand function lazarus / 62-General ---------------------------------------------------------------------- AlexTP · 2020-09-29 21:20 fpcsrc/rtl/inc/fexpand.inc Block Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$IFNDEF FPC_FEXPAND_DIRSEP_IS_CURDIR} {$IFNDEF FPC_FEXPAND_DIRSEP_IS_UPDIR}  {Before anything else, remove doubled DirectorySeparator characters   - technically invalid or at least useless, but ignored by most operating     systems except for plain DOS.}    I := Pos (DirectorySeparator + DirectorySeparator, Dirs);    while I <> 0 do      begin            J := Succ (I);            while (Length (Dirs) > J) and (Dirs [Succ (J)] = DirectorySeparator) do                Inc (J);            Delete (Dirs, Succ (I), J - I);            I := Pos (DirectorySeparator + DirectorySeparator, Dirs);        end; {$ENDIF FPC_FEXPAND_DIRSEP_IS_UPDIR}{$ENDIF FPC_FEXPAND_DIRSEP_IS_CURDIR}  Here we can use PosEx(.., I) in 'while' to find next DirectorySeparator pair from previous one. And 4+ similar blocks below that one. ---------------------------------------------------------------------- jamie · 2020-09-30 01:01 if you are looking for a speed up in execution then I would use the source string and simply have two indexes, one the trailing index and the second the head index reading the remainder of the line..  When complete, you reset the line length using the Trailing index..  the idea is to find a separator and just keep incrementing both indexes until you find one, then if you find another index after that you only increment the HEAD index until you find no more..  In the process of doing all of this you will be replacing the Trailing characters with the characters the HEAD index finds.  I can provide an example if you wish. ---------------------------------------------------------------------- PascalDragon · 2020-09-30 07:56 Quote from: Alextp on September 29, 2020, 11:20:24 pmHere we can use PosEx(.., I) in 'while' to find next DirectorySeparator pair from previous one. No, we can't, because PosEx is part of the unit StrUtils while the code of fexpand.inc is used in both the Dos and SysUtils unit and StrUtils uses the later in its interface section. ---------------------------------------------------------------------- marcov · 2020-09-30 08:23 Quote from: PascalDragon on September 30, 2020, 09:56:40 amQuote from: Alextp on September 29, 2020, 11:20:24 pmHere we can use PosEx(.., I) in 'while' to find next DirectorySeparator pair from previous one. No, we can't, because PosEx is part of the unit StrUtils while the code of fexpand.inc is used in both the Dos and SysUtils unit and StrUtils uses the later in its interface section. True, but pos with offset is part of system since 3.2.  As soon as 3.0.4 bootstrapping is no longer supported, this can be switched (or needs an ifdef). ---------------------------------------------------------------------- PascalDragon · 2020-09-30 08:36 Quote from: marcov on September 30, 2020, 10:23:50 amTrue, but pos with offset is part of system since 3.2.  As soon as 3.0.4 bootstrapping is no longer supported, this can be switched (or needs an ifdef). Better wait until we've dropped 3.0.4 support, less code clutter that way as fexpand.inc is already full of it. ---------------------------------------------------------------------- jamie · 2020-09-30 23:41 here's a base Idea.. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i  Procedure RepeatCharToSingleChar(Var AStr:String; aRp:Char);Var T,H,L:Integer;begin T:=1;H:=1; L:= Length(AStr); While H<=L do  Begin    AStr[T]:=AStr[H];    Inc(T);    IF AStr[H]=aRp Then    Repeat     Inc(H);    until (H>L)or(AStr[H]<>aRp) else inc(H);  end;SetLength(AStr, T-1);end; procedure TForm1.Button1Click(Sender: TObject);var  Dirs:String = '\\1\\2\\3\\4\5\6';begin RepeatCharToSingl eChar(Dirs,DirectorySeparator); Caption := Dirs;end;                                            That will remove all repeating chars indicated in the call. and its done very effectively without using inner functions, deletes etc.. of course this can be enhanced but I think the idea is conveyed ---------------------------------------------------------------------- PascalDragon · 2020-10-01 07:08 Quote from: jamie on October 01, 2020, 01:41:27 amhere's a base Idea.. Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i  Procedure RepeatCharToSingleChar(Var AStr:String; aRp:Char);Var T,H,L:Integer;begin T:=1;H:=1; L:= Length(AStr); While H<=L do  Begin    AStr[T]:=AStr[H];    Inc(T);    IF AStr[H]=aRp Then    Repeat     Inc(H);    until (H>L)or(AStr[H]<>aRp) else inc(H);  end;SetLength(AStr, T-1);end; procedure TForm1.Button1Click(Sender: TObject);var  Dirs:String = '\\1\\2\\3\\4\5\6';begin RepeatCharToSingl eChar(Dirs,DirectorySeparator); Caption := Dirs;end;                                            That will remove all repeating chars indicated in the call. and its done very effectively without using inner functions, deletes etc.. You should probably check whether T <> H before doing the assignment, as in most cases this will be False and thus the assignment might be more expensive than the check. ---------------------------------------------------------------------- jamie · 2020-10-01 21:25 You are talking about resetting the length of the string ? if T <> H then SetLength(…) ? ---------------------------------------------------------------------- Martin_fr · 2020-10-01 21:43 Quote from: PascalDragon on October 01, 2020, 09:08:33 amYou should probably check whether T <> H before doing the assignment, as in most cases this will be False and thus the assignment might be more expensive than the check. Or start by finding the first occurrence "pos()" and then go from there. Also assigning chars to a string, I assume that the code will check for copy-on-write (refcount>1) all the time, despite it is only needed once? (Or does the compiler optimize that?) So then, if (and only if) you got the first occurrence of the duplicated char, make the string unique, then use pchar. ---------------------------------------------------------------------- jamie · 2020-10-02 00:09 It was a base idea which I use many times to delete specific items in a string without using Delete, POS which just piles up the code and CPU time.  When performing such operations like this, there is no need to call functions or create another string if all you want to do is remove something in multiple places..  Using a 2 PChars and incrementing the pointer would also be a speed increase for sure.  The function isn't needed, I just did that to separate it from the code, it could also be marked "inline" to save on the stack operations.  Since we are dealing with both Single and Wide chars, I guess an overload version would also need to be made. ---------------------------------------------------------------------- jamie · 2020-10-02 00:38 Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Procedure RepeatToSingleChar(Var Str:String; aRp:Char);  Inline;var  T,H,L:Pchar;Begin  T := Pchar(Str);  H := T;  IF H <> Nil Then  While (H^<>#0) do   Begin     T^ := H^;     Inc(T);     If H^=aRp THen     Repeat      Inc(H);     Until (H^=#0)or(H^<>aRp) else Inc(H);   end; IF T<>H then  SetLength(Str,Length(Str)-(H-T));end;                               This looks good with the 3.0.4 fpc, didn't try it with 3.2 and up but it actually "Inlines" the code so this can actually be used to remove the call to the procedure ---------------------------------------------------------------------- Martin_fr · 2020-10-02 02:11 When you find the first duplicate char, you need to call UniqueString. Access via pchar, does not trigger copy-on-write. So if Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var a,b: String;begin  a := GetValue;  b := a; // reference to same memory  RepeatToSingleChar(a, '/');  will modify a and b. (Except the SetLength applies only to a.) ---------------------------------------------------------------------- Martin_fr · 2020-10-02 02:33 Something roughly like this Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i     Procedure RepeatToSingleChar(Var Str:String; aRp:Char);  Inline;    var      T,H,L:Pchar;      i: integer;    Begin      T := Pchar(Str);      if T = nil then        exit;       while (T^ <> #0) do        if (T^ <> aRp) then begin          inc(T);        end else begin        inc(T);          if (T^ = aRp) then break        end;      if T^ = #0 then        exit;       i := T - Pchar(Str);      UniqueString(Str);    T := i + Pchar(Str);      H := T;       Repeat       Inc(H);      Until (H^=#0)or(H^<>aRp);       While (H^<>#0) do       Begin         T^ := H^;         Inc(T);         If H^=aRp THen           Repeat          Inc(H);           Until (H^=#0)or(H^<>aRp)         else         Inc(H);       end;      SetLength(Str,Length(Str)-(H-T));    end; ---------------------------------------------------------------------- jamie · 2020-10-02 11:28 It looks like u didn't even run my code? U are making a mountain out of a mole hill. If u pull a string from a constant then u simply use uniquestring once on the string before entering the code. There is no issue changing contents of a string like I did. I actually tested the code before posting it. ---------------------------------------------------------------------- Martin_fr · 2020-10-02 12:11 Quote from: jamie on October 02, 2020, 01:28:55 pmI actually tested the code before posting it. So did I: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var      Dirs:String = 'b\a\\1\\2\\3\\4\5\6789';      Dirs2:String; begin    dirs := copy(dirs,1,111);     Dirs2:=dirs;     RepeatToSingleChar(Dirs,DirectorySeparator);     writeln( Dirs);     writeln( Dirs2);     readln;end.prints Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i b\a\1\2\3\4\5\6789b\a\1\2\3\4\5\67896789 But "b" should still have the "\\" in it. (fpc 3.0.4 / but that should not matter) QuoteIf u pull a string from a constant then u simply use uniquestring once on the string before entering the code.Well, that is what I wrote. => Only that needs to be in the subroutine. Because then, this needs only happen, if there needs to be any modification at all. So if the string has no dups, you save the time of copying it around in memory (in case it had more than one ref) As for mountain vs "mole hill" => I did not classify it. I simply stated what happens I posted my own suggestion, independent on it (and yes, it is based on your code.) ---------------------------------------------------------------------- Bart · 2020-10-02 12:22 How relevant is this discussion about speeding up FExpand? Since this code is primarily used in preparation of some disk IO, which is orders of magnitude slower than string handling. So it is very unlikely that FExpand will ever be the bottleneck in your program. IMO it is better to have good readable code then pre-mature optimized code that is harder to follow (and potentially therefore more prone to new bugs). Bart ---------------------------------------------------------------------- Martin_fr · 2020-10-02 12:31 Quote from: Bart on October 02, 2020, 02:22:06 pmHow relevant is this discussion about speeding up FExpand? Since this code is primarily used in preparation of some disk IO, which is orders of magnitude slower than string handling. So it is very unlikely that FExpand will ever be the bottleneck in your program. IMO it is better to have good readable code then pre-mature optimized code that is harder to follow (and potentially therefore more prone to new bugs). I don't really know. But I dont think code like my example is really needed. I only meant it as proof of concept. I can see it getting used heavily, if file locations are compared (if you have a list of pathes). But: pathes are usually short. I do not even know, how long a path would be acceptable by most OS. On a string of 1000 chars the speed diff will probably be negligible. ---------------------------------------------------------------------- PascalDragon · 2020-10-02 12:35 Quote from: Bart on October 02, 2020, 02:22:06 pmHow relevant is this discussion about speeding up FExpand? Since this code is primarily used in preparation of some disk IO, which is orders of magnitude slower than string handling. So it is very unlikely that FExpand will ever be the bottleneck in your program. IMO it is better to have good readable code then pre-mature optimized code that is harder to follow (and potentially therefore more prone to new bugs). No one can say in what situation the code of fexpand.inc is used, because e.g. ExpandFileName does not do disk I/O by itself (aside from what the code in fexpand.inc itself might do). So while optimizing fexpand.inc might not help everyone, due to a potentially following disk I/O being more expensive, there are definitely cases where it does. If it should for example result in smaller/faster code for embedded platforms that would be a plus, and memory allocations (the Delete in the current code) is definitely more expensive than simply adjusting pointers. ---------------------------------------------------------------------- ASerge · 2020-10-02 19:28 Sometimes there is no need to look for a solution like the C language, we can use regular Pascal, without any #0: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure CompressDuplicatesToOne(var InStr: string; Sample: Char);var  SLength: SizeInt;  WritePos: SizeInt;  ReadPos: SizeInt;begin  SLength := Length(InStr);  ReadPos := 1;  WritePos := 1;  while ReadPos <= SLength do  begin    InStr[WritePos] := InStr[ReadPos];    Inc(WritePos);    if InStr[ReadPos] <> Sample then      Inc(ReadPos)  else      repeat        Inc(ReadPos);      until (ReadPos > SLength) or (InStr[ReadPos] <> Sample);  end;  if WritePos < ReadPos then    SetLength(InStr, WritePos - 1);end;In line 12, the compiler implicitly calls the UniqueString function. We can optimize this by reducing the readability of the code. We will also replace the value of the WritePos variable, since we now need to use it for PChar: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var  SLength: SizeInt;  WritePosZeroBase: SizeInt; // Zero index  ReadPos: SizeInt;begin  UniqueString(InStr); // Call only once  SLength := Length(InStr);  ReadPos := 1;  WritePosZeroBase := 0;  while ReadPos <= SLength do  begin    // Cast to PChar to eliminate implicit UniqueString call for InStr[i]:=    (PChar(Pointer(InStr)) + WritePosZeroBase)^ := InStr[ReadPos];    Inc(WritePosZeroBase);    if InStr[ReadPos] <> Sample then      Inc(ReadPos)    else      repeat      Inc(ReadPos);      until (ReadPos > SLength) or (InStr[ReadPos] <> Sample);  end;  if (WritePosZeroBase + 1) < ReadPos then    SetLength(InStr, WritePosZeroBase);end;Given the fact that modern processors work equally fast with or without index addressing, this code, I think, will be no worse in speed than the code with bringing everything to PChar. It also works for strings containing the #0 character. At least the assembler text on x64 looks optimal: Code: ASM  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i # [57] UniqueString(InStr);        movq    %rbx,%rcx        call    FPC_ANSISTR_UNIQUE.Ll19:# [58] SLength := Length(InStr);        movq  (%rbx),%rax        testq   %rax,%rax        je      .Lj22        movq    -8(%rax),%rax.Lj22:# Var SLength located in register rax# Var ReadPos located in register r9.Ll20:# [59] ReadPos := 1;        movl  $1,%r9d# Var WritePosZeroBase located in register rdx.Ll21:# [60] WritePosZeroBase := 0;        xorl    %edx,%edx.Ll22:# [61] while ReadPos <= SLength do        jmp     .Lj24        .balign 8,0x90.Lj23:.Ll23:        movq    (%rbx),%rcx.Ll24:# [64] (PChar(Pointer(InStr)) + WritePosZeroBase)^ := InStr[ReadPos];        leaq    (%rcx,%rdx),%r8        movb    -1(%rcx,%r9,1),%cl        movb    %cl,(%r8).Ll25:# [65] Inc(WritePosZeroBase);        addq    $1,%rdx.Ll26:# [66] if InStr[ReadPos] <> Sample then        movq    (%rbx),%rcx        cmpb    -1(%rcx,%r9,1),%sil        je      .Lj27.Ll27:# [67] Inc(ReadPos)        addq    $1,%r9        jmp     .Lj28.Lj27:        .balign 8,0x90.Lj29:.Ll28:# [70] Inc(ReadPos);      addq    $1,%r9.Ll29:# [71] until (ReadPos > SLength) or (InStr[ReadPos] <> Sample);        cmpq    %r9,%rax        jl      .Lj31        movq    (%rbx),%rcx        cmpb    -1(%rcx,%r9,1),%sil      je      .Lj29.Lj31:.Lj28:.Lj24:.Ll30:        cmpq    %r9,%rax      jge     .Lj23.Ll31:# [73] if (WritePosZeroBase + 1) < ReadPos then      leaq    1(%rdx),%rax        cmpq    %r9,%rax        jnl     .Lj36.Ll32:# [74] SetLength(InStr, WritePosZeroBase);        movq    %rbx,%rcx        xorl    %r8d,%r8d        call    fpc_ansistr_setlength        .balign 4,0x90.Lj36:.Ll33:# [75] end; ---------------------------------------------------------------------- marcov · 2020-10-02 19:37 Quote from: ASerge on October 02, 2020, 09:28:36 pmGiven the fact that modern processors work equally fast with or without index addressing, this code, I think, will be no worse in speed than the code with bringing everything to PChar. It also works for strings containing the #0 Recent processors re-valuate string functions. Modern processors can process up to 100 bytes per tick (!). While even with uopcache, 6 uops per tick is the maximum Maybe we need an IndexNByte for this code: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i  repeat      Inc(ReadPos);      until (ReadPos > SLength) or (InStr[ReadPos] <> Sample); ---------------------------------------------------------------------- ASerge · 2020-10-03 08:17 Quote from: marcov on October 02, 2020, 09:37:46 pmMaybe we need an IndexNByte for this code: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i  repeat      Inc(ReadPos);      until (ReadPos > SLength) or (InStr[ReadPos] <> Sample);Thinking is not necessary, in practice there are not many identical consecutive characters, but the IndexByte function is very long compared to the code: Code: ASM  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i .Lj29:.Ll28:# [70] Inc(ReadPos);        addq    $1,%r9.Ll29:# [71] until (ReadPos > SLength) or (InStr[ReadPos] <> Sample);        cmpq  %r9,%rax        jl      .Lj31        movq    (%rbx),%rcx        cmpb  -1(%rcx,%r9,1),%sil        je      .Lj29.Lj31: ---------------------------------------------------------------------- marcov · 2020-10-03 13:32 Yeah, and then you get to the topic what CPU such routines should optimize for. Which is not easy.