[Solved] What is optimal code for this char-testing? lazarus / 61-Beginners ---------------------------------------------------------------------- AlexTP · 2022-02-25 14:30 Code from CudaText project (it runs millions times on long files) 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 function IsSpaceOrBreakChar(c: WideChar): Boolean; inline;begin  case c of    #9,    ' ',    #10,    #13:      Result := True;    else      Result := False;  end;end; Is it better to rewrite this as 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   Result:= (C=#9) or (C=' ') or (C=#10) or (C=#13);  on modern CPUs? Note: this is WideChar, not char! ---------------------------------------------------------------------- wildfire · 2022-02-25 14:47 Serious question, don't mock I'm still in the old ASCII days. Is there any particular reason that IsWhiteSpace not suitable? ---------------------------------------------------------------------- Warfley · 2022-02-25 14:55 Looking at the Assembly: Link 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 function IsSpaceOrBreakCharCase(c: WideChar): Boolean; inline;begin    case c of    #9,    ' ',    #10,    #13:        Result := True;    else      Result := False;    end;end; function IsSpaceOrBreakCharIf(c: WideChar): Boolean; inline;begin    Result:= (C=#9) or (C=' ') or (C=#10) or (C=#13);end; function IsSpaceOrBreakCharSet(c: WideChar): Boolean; inline;begin    Result:= c in [#9, ' ', #10, #13];end; 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 isspaceorbreakcharcase(widechar):        cmpw    $9,%di        jb      .Lj6        subw    $10,%di        jbe     .Lj7        subw    $3,%di        je      .Lj7        subw    $19,%di        jne     .Lj6.Lj7:        movb    $1,%al        ret.Lj6:        xorb    %al,%al        ret isspaceorbreakcharif(widechar):        cmpw    $9,%di        je      .Lj10        cmpw    $32,%di        je      .Lj10        cmpw    $10,%di        je      .Lj10        cmpw    $13,%di        jne     .Lj14.Lj10:        movb    $1,%al        ret.Lj14:        xorb    %al,%al        ret isspaceorbreakcharset(widechar):        leaq    -8(%rsp),%rsp      andl    $65535,%edi        call    fpc_uchar_to_char        andl    $255,%eax        subl    $9,%eax        cmpl    $2,%eax        jb    .Lj18        cmpl    $4,%eax        stc        je      .Lj18        cmpl    $23,%eax        stc        je      .Lj18        clc.Lj18:      setcb   %al        leaq    8(%rsp),%rsp        retIf and Case are pretty similar, basically just a series of conditional jumps. The set solution on the other hand is a bit different, as this results in bit- operations, which potentially could be faster. Personally I also find the set notation the cleanest ---------------------------------------------------------------------- AlexTP · 2022-02-25 15:36 The 'set' variant has the 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 call    fpc_uchar_to_char which is some internal FPC call. seems it will be slower. Thanks! ---------------------------------------------------------------------- Ally · 2022-02-25 15:42 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 TForm1.Button1Click(Sender: TObject);var  i: Integer;  c: WideChar;  r: Boolean;  Start, Stopp: Integer;begin  Start := GetTickCount64;   c := #13;   for i := 1 to 100000000 do  begin    // fast    //-----------------------------------------------    case c of      #9,      ' ',      #10,      #13:      r := True;    else      r := False;    end;    //-----------------------------------------------      // slow    //-----------------------------------------------    //r:= (C=#9) or (C=' ') or (C=#10) or (C=#13);    //-----------------------------------------------      // very slow  //-----------------------------------------------    //r:= c in [#9, ' ', #10, #13];    //-----------------------------------------------  end;   Stopp := GetTickCount64;   if r then    i := 0;   ShowMessage(IntToStr(Stopp - Start) + ' milliseconds ');end; ---------------------------------------------------------------------- AlexTP · 2022-02-25 16:03 Haha, 'set' variant is very very slow. ---------------------------------------------------------------------- Martin_fr · 2022-02-25 16:18 The question is wrong, so technically it can't be answered. You ask how to write the Pascal code, but you want to know what performs better on a modern CPU. Only that is the machine code... And there is no one-to-one relation between the Pascal and the machine code (at least in principal). Such a relation only exists if you specify - the exact compiler (release version, or git revision) - the exact arguments for the compilation - the surrounding code, in case of inlining. - .... And even for asm the question is not easy to answer, not even if you benchmark But lets assume, that for the particular bits of "to be compared" pascal code, the translation will not significantly change. (Which might be a broken assumption, given there is currently active work on optimization in the fpc main branch). At first sight the below code sample might be promising (compiled with a recent 3.2.3 / using -O2 ). 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 function IsSpaceOrBreakChar(c: WideChar): Boolean; inline;var  r1: Boolean;begin    result := (C=#9);    r1:= (C=' ');    Result := Result or r1;    r1:= (C=#10);    Result := Result or r1;    r1:= (C=#13);    Result := Result or r1;end; 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 P$PROJECT1_$$_ISSPACEORBREAKCHAR$WIDECHAR$$BOOLEAN:.Lc1:        cmpw  $9,%cx        seteb   %dl        cmpw    $32,%cx        seteb   %al      orb     %dl,%al        cmpw    $10,%cx        seteb   %dl        orb     %al,%dl        cmpw    $13,%cx        seteb   %al        orb   %dl,%al        ret  As you can see, it eliminates any conditional jumps. That is one (of many) ways to help the CPU with faster execution. I don't know though, if - the registers usage is good with regards to thinks like "pipeline stalls" (which to be honest, I do know very little about). - using only byte registers has any impact - the final size of the machine code in bytes has any impact (actually it most likely will have, and smaller is not always better) The next bit of getting it to run fast is the surrounding code. And this is also why a benchmark may not get you really helpful values. Consider that the function is inlined, and you have the following 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 procedure Foo;var   p: pwidechar;  i := integere;  t: qword;begin  //Bar();   // Optional call to Bar   t := getTickCount64;  p := @SomeText[1];    while p^ <> 0 do begin    if IsSpaceOrBreakChar(p^) then      inc(i);    inc(p);  end;  writeln(getTickcount64 - t);end;  Commenting in/out the call to Bar => will the code in the loop be faster or slower? Well it could go either way. In fact even unrelated changes in other functions, could speed up or slow down the code. Yes, indeed they can. (and significantly, I had cases where IIRC this was an over 25% diff) Why? Well modern (Intel) CPU optimize code that is within ONE 32 byte long, 32 byte aligned memory segment. If the code splits over 2 such segments, it could run a lot slower. If the code is larger than 32 byte, the exact location where it is split between blocks can matter a lot. FPC aligns procedures to 16 bytes. So a procedure can either start at an exact 32 byte boundary, or at 16 bytes into a 32 byte boundary. For the above "procedure Foo" this will depend on any code of any function that is located before "Foo". And so that can shift the loop, and affect the speed. And there may (very likely "definitely will") be more stuff about modern CPU, affecting those speeds. So, if you have more conditions, and the asm code gets rather big, it could be faster to start with "if ord(c) > 32" then exit(false);". That would be very short (likely in a single 32 byte block / though if inlined, depending on the loop statement, the conditional jump might still leave that boundary), cover a high percentage of the iterations, and the branch prediction would likely do a fine job on it. --- EDIT: FPC git main will generate branch-less asm for the one line assignment. (my 2 week old fpc 3.2.3 doesn't) 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         Result:= (C=#9) or (C=' ') or (C=#10) or (C=#13); ---------------------------------------------------------------------- Warfley · 2022-02-25 16:58 Quote from: Alextp on February 25, 2022, 04:36:25 pmThe 'set' variant has the 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 call    fpc_uchar_to_char which is some internal FPC call. seems it will be slower. Thanks! Ah you are right, the conversion is really slow, just tested it with regular chars, there it is actually faster than the other two options, where case is the worst: 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 program Project1; {$mode objfpc}{$H+} uses  SysUtils; function IsSpaceOrBreakCharCase(c: Char): Boolean; inline;begin    case c of  #9,    ' ',    #10,    #13:        Result := True;    else        Result := False;    end;end; function IsSpaceOrBreakCharIf(c: Char): Boolean; inline;begin    Result:= (C=#9) or (C=' ') or (C=#10) or (C=#13);end; function IsSpaceOrBreakCharSet(c: Char): Boolean; inline;const  CompareSet: Set of Char = [#9, ' ', #10, #13];begin    Result:= c in CompareSet;end; var  c: Char;  i: Integer;  Start: QWord; const  ITERS = 1000000000;begin  Start := GetTickCount64;  for i:=1 to ITERS do  begin    c := Char(Random(1 shl SizeOf(Char)));    IsSpaceOrBreakCharCase(c);  end;  WriteLn('Case: ', GetTickCount64-Start);  Start := GetTickCount64;  for i:=1 to ITERS do  begin    c := Char(Random(1 shl SizeOf(Char)));    IsSpaceOrBreakCharIf(c);  end;  WriteLn('If: ', GetTickCount64-Start);  Start := GetTickCount64;  for i:=1 to ITERS do  begin    c := Char(Random(1 shl SizeOf(Char)));    IsSpaceOrBreakCharSet(c);  end;  WriteLn('Set: ', GetTickCount64-Start);  ReadLn;end.Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Case: 6094If: 5640Set: 5578 But with a little trick, you can make the conversion much faster: 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 function IsSpaceOrBreakCharSet(c: WideChar): Boolean; inline;const  CompareSet: Set of Char = [#9, ' ', #10, #13];begin    Result:= PChar(@c)^ in CompareSet;end;And with everything changed to WideChars 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 Case: 5921If: 6344Set: 6063It low sits between the case and the if. It's interesting that the conversion functions, which should be the fastest functions possible, as they are used so often and transparently in the background, are actually really slow ---------------------------------------------------------------------- 440bx · 2022-02-25 17:21 Maybe I'm missing something but.... the set of characters to compare against is the lowest part of the Ascii character set.  Those characters will be preceded by a zero which can be safely ignored.  IOW, the "conversion" is simply to skip that null in front of the character and, if sets are slow because of library calls, define your own array of bits (boolean) and index directly into it using the character's ordinals.  HTH. ---------------------------------------------------------------------- Warfley · 2022-02-25 20:13 Quote from: 440bx on February 25, 2022, 06:21:10 pmMaybe I'm missing something but.... the set of characters to compare against is the lowest part of the Ascii character set.  Those characters will be preceded by a zero which can be safely ignored.  IOW, the "conversion" is simply to skip that null in front of the character and, if sets are slow because of library calls, define your own array of bits (boolean) and index directly into it using the character's ordinals.  HTH. The sets aren't slow, it is simply the internal conversion function: 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 Function fpc_UChar_To_Char(const c : UnicodeChar): Char; compilerproc;{  Converts a UnicodeChar to a Char;}var  s: ansistring;begin  widestringmanager.Unicode2AnsiMoveProc(@c, s, DefaultSystemCodePage, 1);  if length(s)=1 then    fpc_UChar_To_Char:= s[1]  else    fpc_UChar_To_Char:='?';end; Of course this will be hellish slow, but also it kinda needs to be so complex to be portable. Honestly, I think that this is called implicetly, and the function itself is not documented (as it isn't even a real function but more a compiler internal the programmer should not know about), is kinda bad, and breaking with strict typing. So yeah, you can create your own function, but the main Problem I see here is that, that fpc does a lot of code implicitly code, that you only know about when looking into the compiler source, that you just need to know about or wonder why your code is slower by a factor of 20 than you might expect. In such a situation the much better alternative would be to say: Incompatible type, expected Char but got WideChar and let the user call the conversion routine manually. Also, that aside, I don't know why anyone wants to use widechars in the first place. Even Microsoft got the memo by now and switched all the APIs to UTF-8. It is simply the better unicode format, exactly because the backwardscompatibility to ANSI strings. ---------------------------------------------------------------------- AlexTP · 2022-02-25 20:47 I gave small suggestion here https://gitlab.com/freepascal.org/fpc/source/-/issues/39601 ---------------------------------------------------------------------- engkin · 2022-02-26 03:21 I think it is faster if you test for exclusion first.