[fpc-devel] Compile time functions

J. Gareth Moreton gareth at moreton-family.com
Sun Jul 22 06:56:45 CEST 2018


 To follow up on this, even if you rewrote the function to use a
multiplicative formula (faster to compute overall):

 function Binomial(n, r: Cardinal): Cardinal; pure;var  c: Cardinal;
 begin
   for (r > n) then
     Result := 0
   else
     begin
       Result := 1;
       if n  r then
         begin
           Inc(n); { Only "n + 1" appears in the formula }
           for c := 1 to r do            
             Result := (Result * (n - c)) div c; { Make sure the
multiplication is evaluated first }

         end;
     end;
 end;

 I'm not saying it's impossible, but that's certainly slightly harder to
propagate a constant through that, even with manual programmer
optimisations like with Inc(n).

 Gareth aka. Kit

 On Sun 22/07/18 05:15 , "J. Gareth Moreton" gareth at moreton-family.com
sent:
  Sorry for that mess of a formatting on the code sample, Here is a much
nicer version!
 function Binomial(n, r: Cardinal): Cardinal; pure;begin
   if (r > n) then
     Result := 0
   else if (r = n) then
     Result := 1 { Faster than calculating the factorials }
   else
     Result := Factorial(n) div (Factorial(r) * Factorial(n - r));
 end;

 Gareth aka. Kit

 On Sun 22/07/18 05:03 , "J. Gareth Moreton" gareth at moreton-family.com
sent:
 An interesting read. If you can collapse an inline function into a single 
 assignment in most situations, then brilliant! Definitely keep that
optimisation in. 

 While there are many similarities and prerequisites between an inline
function 
 and a pure function, and many simple mathematical functions could easily
carry 
 both modifiers, they are not exactly the same. Pure functions cannot be 
 evaluated at compile time if one of the arguments is a variable (or at the
very 
 least, not deterministic), but it might be inlined, while a function with 
 recursion can't be reliably inlined, but might still be pure (e.g.
factorial, 
 assuming you don't rewrite it to use a for-loop), and not all recursive
functions 
 can be rewritten to use simpler loops (e.g. the infamous Ackermann
function). It 
 is true though... proper constant propagation would cover most situations,
even 
 when an inline function calls another inline function such as Max,
although there 
 might still be issues in exceptional conditions (e.g. division by zero or
trying 
 to calculate tan(pi/2), for example). 

 The other point with a "pure" modifier is that, assuming the compiler
determines 
 that the function is indeed pure, it would permit their assignment to a
constant. 
 True, you could replace the constant with the function call whenever it
appears, 
 but that's not exactly good coding practice. And that's sort of the other
reason 
 for the "pure" modifier. If you release a library of functions that a 
 third-party then looks at, with no background knowledge of its inner
workings, 
 the appearance of the "pure" modifier would quickly clue them in in
regards to 
 the functions' intent. 

 The final issue is that while a function might be pure, you might not want
to 
 inline it because of its complexity, especially if it's called multiple
times 
 with variable arguments. The simplest example I can think of is the
two-argument 
 binomial coefficient: 

 function Binomial(n, r: Cardinal): Cardinal; pure; 
 begin 
 if (r > n) then 
 Result := 0 
 else if (r = n) then 
 Result := 1 { Faster than calculating the factorials } 
 else 
 Result := Factorial(n) div (Factorial(r) * Factorial(n - r)); 
 end; 

 The alternative versions either require recursion, or for exceptionally
large 
 values of n and r, calculating the integral that defines the gamma
function. 

 Gareth aka. Kit 

 On Sat 21/07/18 18:51 , Sven Barth via fpc-devel
fpc-devel at lists.freepascal.org [1] sent: 
 > Martok schrieb am Sa., 21. Juli 2018, 17:12: 
 > Am 21.07.2018 um 02:08 schrieb Sven Barth via fpc-devel: 
 > > The main problem is that not all functions that would be eligible for 
 > your 
 > > approach are also declared as inline thus their node trees would not
be 
 > stored 
 > > inside the PPU and thus you could not work with them. 
 > I'm not sure I understand. Isn't the same true, with a new feature? The 
 > full 
 > node tree must be available, which basically means "has inlineinfo". 
 > Doesn't it? 
 > 
 > Correct.  
 > 
 > > Additional benefit of the "pure" modifier: the compiler can check once

 > the 
 > > method has been parsed whether it's pure or not and can thus error out

 > in the 
 > > latter case. 
 > That is true, it is a more explicit declaration of intent. 
 > Maybe the codegen of pure can simply be implemented as generating inline

 > info, 
 > but always replacing the calls with the simplified version. If it is 
 > already 
 > known that a function is pure, what I did with constexpr() would
basically 
 > be 
 > guaranteed to work. 
 > 
 > Pure functions would still have an ordinary generated body as there is
no 
 > reason that their address shouldn't be able to be taken (otherwise one 
 > needs to declare wrappers for them). Other than that I personally favor
the 
 > explicit declaration of intent for such functions without the need for a

 > ConstExpr intrinsic.  
 > Regards, Sven  _______________________________________________ 
 > fpc-devel maillist - fpc-devel at lists.freepascal.org [2] 
 > http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[3]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel [1] 
 > 
 > 
 > 
 > Links: 
 > ------ 
 > [1] 
 >
http://secureweb.fast.net.uk/parse.php?redirect=http://lists.freepascal.org
[5] 
 > /cgi-bin/mailman/listinfo/fpc-devel 
 > 

 _______________________________________________ 
 fpc-devel maillist - fpc-devel at lists.freepascal.org [6] 
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[7]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel 

  _______________________________________________
 fpc-devel maillist - fpc-devel at lists.freepascal.org [8]
 http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
[9]">http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

 

Links:
------
[1] mailto:fpc-devel at lists.freepascal.org
[2] mailto:fpc-devel at lists.freepascal.org
[3] http://secureweb.fast.net.uk/ http:=
[4] http://lists.freepascal.org
[5] http://lists.freepascal.org
[6] mailto:fpc-devel at lists.freepascal.org
[7] http://secureweb.fast.net.uk/ http:=
[8] mailto:fpc-devel at lists.freepascal.org
[9] http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20180722/5aa1f280/attachment.html>


More information about the fpc-devel mailing list