*/div and shr/shl lazarus / 64-FPC development ---------------------------------------------------------------------- Okoba · 2022-03-16 11:28 Hello, Are these two codes equivalent all the time? If so, why not FPC optimize it, as shr appears to be 2x faster than div in microbenchmarks? If not, a sample would be appreciated. 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 V := I div 2; 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 V := I shr 1; Although these two take the same time: 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 V := I shl 1; 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 V := I * 2; Tested on Trunk, Win64. ---------------------------------------------------------------------- MathMan · 2022-03-16 11:49 Hello Okoba, To answer your first question - no they are not egivalent all the time! If I, V are signed integers then "div" <> "shr". On some processors there exist assembler instructions which are eqivalent - e.g. on x86 this is "sar" (shift arithmetic right). But I don't know offhand if this is available as an intrinsic in Free Pascal. Cheers, MathMan PS - removed a wrong "=" sign which had slipped in ---------------------------------------------------------------------- Okoba · 2022-03-16 12:04 Can you give me a sample? I saw many uses cases that shl 1 is used instead of * 2 or shr 1 instead of div 2 for performance needs. And I like to be more aware of pitfalls. ---------------------------------------------------------------------- ccrause · 2022-03-16 12:12 Quote from: MathMan on March 16, 2022, 12:49:23 pmIf I, V are signed integers then "div" <> "shr". On some processors there exist assembler instructions which are eqivalent - e.g. on x86 this is "sar" (shift arithmetic right). But I don't know offhand if this is available as an intrinsic in Free Pascal. Note that shift arithmetic right is available in FPC, but this is not a direct equivalent to divide by two of a negative number. ---------------------------------------------------------------------- Kays · 2022-03-16 12:13 Write what you mean. The compiler will optimize multiplying/dividing by a constant factor 2ⁿ accordingly. Quote from: Okoba on March 16, 2022, 12:28:41 pmAre these two codes equivalent all the time?No. For instance, a recently discussed issue … shl 64. ---------------------------------------------------------------------- ccrause · 2022-03-16 12:21 Quote from: Okoba on March 16, 2022, 01:04:24 pmCan you give me a sample? I saw many uses cases that shl 1 is used instead of * 2 or shr 1 instead of div 2 for performance needs. And I like to be more aware of pitfalls. A rather trivial example: 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; var  i, j: longint; begin  j := -1;  i := j shr 1;  writeln('j shr 1 = ', i);  i := j div 2;  writeln('j div 2 = ', i);  i := SarLongint(j, 1);  writeln('SarLongint(j, 1) = ', i);  readln;end. Generated output: 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 j shr 1 = 2147483647j div 2 = 0SarLongint(j, 1) = -1 ---------------------------------------------------------------------- Okoba · 2022-03-16 13:06 @ccrause Thank you for the sample. So it only matters when the value is negative. Is it true that positive values are always equivalent? @Kays, FPC only optimizes them when it is set to -O4, not -O3. I hope one of the compiler devs like @PascalDragon, can clarify why it is not happening in the normally default -O3 (at least in Lazarus), and only happens in -O4 (with the beware! note). Is there something else that may be dangerous? Is it best to always write shl/shr when you know the number is not negative, or should you write */div and set the compiler on -O4? I would like to know what the best approach is. ---------------------------------------------------------------------- MathMan · 2022-03-16 13:56 Quote from: ccrause on March 16, 2022, 01:12:06 pmQuote from: MathMan on March 16, 2022, 12:49:23 pmIf I, V are signed integers then "div" <> "shr". On some processors there exist assembler instructions which are eqivalent - e.g. on x86 this is "sar" (shift arithmetic right). But I don't know offhand if this is available as an intrinsic in Free Pascal. Note that shift arithmetic right is available in FPC, but this is not a direct equivalent to divide by two of a negative number. Thanks for reminding me - I forgot the exceptional case of -1 and the trickery with rounding. Cheers, MathMan ---------------------------------------------------------------------- ccrause · 2022-03-16 14:08 Quote from: Okoba on March 16, 2022, 02:06:11 pm@ccrause Thank you for the sample. So it only matters when the value is negative. Is it true that positive values are always equivalent? The one exception I can think of for positive or unsigned numbers is that shl does not check for overflow, while the multiplication will (if overflow checking is enabled): 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 i, j: longint;   j := MaxInt;  i := j shl 1;  // i = -2  i := j * 2;    // This results in an arithmetic overflow exception if overflow check is enabled, else result is also -2In all other cases (I think) for a positive or unsigned number x: x * n = x shl ln(n) and x div n = x shr ln(n), with n an integer power of 2. ---------------------------------------------------------------------- Okoba · 2022-03-16 14:19 Thank you very much @ccrause. ---------------------------------------------------------------------- Kays · 2022-03-16 14:23 Quote from: Okoba on March 16, 2022, 02:06:11 pm@Kays, FPC only optimizes them when it is set to -O4, not -O3.On an x86 Linux target I could not see idiv/imul in the assembly output, regardless of the optimization level. Maybe it depends on {$optimization fastMath} on Win64 targets. ---------------------------------------------------------------------- Okoba · 2022-03-16 15:32 That is interesting. Maybe some of the FPC team members can explain the behavior better. ---------------------------------------------------------------------- PascalDragon · 2022-03-17 11:53 I can not reproduce. FPC 3.2.2 converts the following example to code without any div instructions on x86_64 and i386 without any optimizations enabled: 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 ttest; var  i: LongInt;  u: LongWord;begin  i := i div 2;  i := i div -2;  u := u div 2;  u := u div -2;end. Generated assembly: 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 # [7] i := i div 2;        movslq  U_$P$TTEST_$$_I(%rip),%rax        movq    %rax,%rdx        shrq    $63,%rdx        addq    %rdx,%rax        sarq    $1,%rax        movl    %eax,U_$P$TTEST_$$_I(%rip)# [8] i := i div -2;        movslq  U_$P$TTEST_$$_I(%rip),%rax        movq    %rax,%rdx        shrq    $63,%rdx        addq    %rdx,%rax        sarq    $1,%rax        negq    %rax        movl    %eax,U_$P$TTEST_$$_I(%rip)# [9] u := u div 2;        movl    U_$P$TTEST_$$_U(%rip),%eax        shrl    $1,%eax        movl    %eax,U_$P$TTEST_$$_U(%rip)# [10] u := u div -2;        movl    U_$P$TTEST_$$_U(%rip),%eax        movq    %rax,%rdx        shrq    $63,%rdx        addq    %rdx,%rax        sarq    $1,%rax        negq  %rax        movl    %eax,U_$P$TTEST_$$_U(%rip)  If you have another experience then please state your FPC version and platform and provide a full, compilable, self contained example that shows the problem. ---------------------------------------------------------------------- Okoba · 2022-03-17 12:22 Result in: Lazarus 2.3.0 (rev main-2_3-1428-g9f142eef14) FPC 3.3.1 x86_64-win64-win32/win64 without optimization 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;var  I, V: Cardinal;begin  I := 0;  V := I shr 1;  V := I div 2;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 # [7] V := I shr 1;        shrl    $1,%eax        movl    %eax,U_$P$PROJECT1_$$_V(%rip).Ll4:# [8] V := I div 2;        movl    U_$P$PROJECT1_$$_I(%rip),%eax        shrl    $1,%eax        movl    %eax,U_$P$PROJECT1_$$_V(%rip) Same instruction. Changing the type to Integer: 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; var  I, V: Integer;begin  I := 0;  V := I shr 1;  V := I div 2;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 # [7] V := I shr 1;        shrl    $1,%eax        movl    %eax,U_$P$PROJECT1_$$_V(%rip).Ll4:# [8] V := I div 2;        movslq  U_$P$PROJECT1_$$_I(%rip),%rax        movq    %rax,%rdx        shrq    $63,%rdx        addq    %rdx,%rax        sarq    $1,%rax        movl  %eax,U_$P$PROJECT1_$$_V(%rip)  I can understand this, compiler thinks that as the value is integer, it may be negative so it does not use the same simple shr. Now for this code and even with -O4 the results will be: 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; uses  SysUtils;   procedure TestDiv;  var    I, V: Integer;  begin    for I := 1 to 1000 * 1000 * 1000 do      V := I div 2;    WriteLn(V);  end;   procedure TestSHR;  var    I, V: Integer;  begin  for I := 1 to 1000 * 1000 * 1000 do      V := I shr 1;    WriteLn(V);  end; var  T: QWord;begin  T := GetTickCount64;  TestDiv;  WriteLn('div: ', GetTickCount64 - T);   T := GetTickCount64;  TestSHR;  WriteLn('shr: ', GetTickCount64 - T);  ReadLn;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 # [11] V := I div 2;        movslq  %eax,%rdx        movq    %rdx,%rcx        shrq    $63,%rcx        addq    %rcx,%rdx        sarq    $1,%rdx      movl    %edx,%ebx        addl    $1,%eax        cmpl    $1000000000,%eax        jng     .Lj5 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 # [20] V := I shr 1;        movl    %eax,%ebx        shrl    $1,%ebx        addl  $1,%eax        cmpl    $1000000000,%eax        jng     .Lj10  and the times are: Quotediv: 469 shr: 218 and if I change integer to cardinal: 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 # [11] V := I div 2;        movl    %eax,%ebx        shrl    $1,%ebx        addl  $1,%eax        cmpl    $1000000000,%eax        jna     .Lj5 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 # [20] V := I shr 1;        movl    %eax,%ebx        shrl    $1,%ebx        addl  $1,%eax        cmpl    $1000000000,%eax        jna     .Lj10  And the times: Quotediv: 219 shr: 219 As in the integer sample, the loop is clearly in positive values, why compiler does not optimize it? Is it to be safe or something else? ---------------------------------------------------------------------- PascalDragon · 2022-03-18 15:34 Quote from: Okoba on March 17, 2022, 01:22:31 pmAs in the integer sample, the loop is clearly in positive values, why compiler does not optimize it? Is it to be safe or something else? The compiler only considers the type of the left side of the div (which is signed) and not what range it might have. Feel free to file a feature request to improve the data flow analysis so that it might take into account this as well. ---------------------------------------------------------------------- Okoba · 2022-03-18 20:02 Done. https://gitlab.com/freepascal.org/fpc/source/-/issues/39626