DivMod optimization
lazarus / 64-FPC development

----------------------------------------------------------------------
gidesa · 2025-01-04 11:26

Hello,
seems that DivMod is not optimized against a constant divisor, on
contrary separate Div and Mod are optimized.
See the following code (from this interesting site:
https://github.com/jabbalaci/SpeedTests).
Using DivMod on my machine performance is around 3 times slower than
using separate Div and Mod (around 6 sec).

EDIT: indeed the difference is on FPC 3.2.2 and 3.3.1 using UInt32;
using Integer there is no difference
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
testMunchausen;uses math; procedure CalcCache(var cache: array of
Uint32);var  i: Uint32;begin  cache[0] := 0;  for i := 1 to 9 do 
begin    cache[i] := i**i;  end; end; function IsMunchausen(constref
cache: array of Uint32; constref num: Uint32): Boolean;var  n, total,
digit: Uint32;begin  n := num;  total := 0;  while n > 0 do    begin 
   //DivMod(n, 10, n, digit);      // splitted in 2 separate
operations      digit := n MOD 10;      n:= n DIV 10;      total +=
cache[digit];      if total > num then        break;    end; 
IsMunchausen := num = total;end; var  cache: array[0..9] of Uint32; 
i: Uint32;const  MAX = 440000000;begin  CalcCache(cache);  for i := 0
to MAX do    if IsMunchausen(cache, i) then      WriteLn(i);end.

----------------------------------------------------------------------
ALLIGATOR · 2025-01-04 13:22

Try this, it's how I was able to maximize 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 function
IsMunchausen(const cache: array of LongInt; num: UInt32):
Boolean;{$CODEALIGN JUMP=128}var  n, tn, total, digit: UInt32;begin  n
:= num;  total := 0;   while n > 0 do    begin      tn:=n div 10;    
digit:=n-tn*10;      n:=tn;       total += cache[digit];      if total
> num then        break;    end;  IsMunchausen := num = total;end;

----------------------------------------------------------------------
gidesa · 2025-01-04 13:45

Thank you. With your function the program is slightly faster, around
5,5 sec (Win 11, AMD Ryzen 7 2700).
I use your suggestion to modify  original program.
Now all variables are type Integer, and in function I don't use MOD:
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
IsMunchausen(constref cache: array of integer; constref num: integer):
Boolean;var  n, total, digit: integer;  tn: integer;begin  n := num; 
total := 0;  while n > 0 do    begin//      DivMod(n, 10, n, digit);
 //      digit := n MOD 10;      tn:= n DIV 10;      digit:=n-tn*10; 
   n:=tn;      total += cache[digit];      if total > num then       
break;//      n:= n DIV 10;    end;  IsMunchausen := num = total;end;
                               
Now time is 6,5 -7 sec, much better than original version with Integer
(17 sec), although a bit worst that UInt32 version.
So seems that DivMod and Mod are not always optimized.

----------------------------------------------------------------------
ALLIGATOR · 2025-01-05 07:23

Note the results for the Go language - there are two variants shown
there with Int32 and UInt32

----------------------------------------------------------------------
gidesa · 2025-01-05 13:27

I think the initial idea for that benchmark is to compare languages
using the most simple and straightforward implementation, with no
special tricks, using the C source as reference. And using different
compilers, if avalaible.
But you are right, for Go, Haskell, and others, there are multiple
source version.
I have open an issue, asking to update the Freepascal original source.
Or add a second version.
Your suggestions are very useful, the new source is more than 3 times
faster.
Sadly remains the fact that DivMod and Mod are not very optimized.
Here others compilers do a better work.

----------------------------------------------------------------------
ALLIGATOR · 2025-01-05 13:39

You are not quite right - div and mod are optimized, but separately,
and DivMod is a normal function, it is optimized compared to two
separate actions of dividing and finding the remainder from dividing
by a value in a variable (not a constant)

Also you can always do it 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 program
test;{$mode objfpc} uses math; procedure DivMod_(Dividend: LongInt;
Divisor: LongInt; var Result, Remainder: LongInt); inline;begin  if
IsConstValue(Divisor) then  begin    Result:=Dividend div Divisor;   
Remainder:=Dividend mod Divisor;  end else  begin    DivMod(Dividend,
Divisor, Result, Remainder);  end;end; var  a,b,c: LongInt; begin 
a:=333+Random(0);  DivMod_(a, 33, b, c);  WriteLn(a,',',b); 
ReadLn;end.

----------------------------------------------------------------------
Laksen · 2025-01-05 14:03

As a microoptimization you can remove constref from num

----------------------------------------------------------------------
gidesa · 2025-01-05 14:26

Quote from: ALLIGATOR on January 05, 2025, 02:39:27 pmYou are not
quite right - div and mod are optimized, but separately, and DivMod is
a normal function, it is optimized compared to two separate actions of
dividing and finding the remainder from dividing by a value in a
variable (not a constant)

Indeed if we simply don't use DivMod and Mod, as in my IsMunchausen()
last version, performance are 3 times better!  So Mod seems not
optimized in respect of dividing for a constant, where Div is
optimized. For DivMod really I don't know was the developers target.
In my opinion, in this simple test, we are only comparing "native"
language/compiler optimization performances.
Of course it's always possible to rewrite functions, add tricks
specific of a language, etc., for every compared language/compiler.

----------------------------------------------------------------------
gidesa · 2025-01-05 14:39

Quote from: Laksen on January 05, 2025, 03:03:11 pmAs a
microoptimization you can remove constref from num

Thank you, there is another significative improvement.