Re: [fpc-pascal] Recursion optimization by compiler
Am 04.09.2010 15:08, schrieb Sven Barth: > On 28.08.2010 11:57, Florian Klämpfl wrote: >> Am 03.09.2010 21:31, schrieb Sven Barth: >>> On 03.09.2010 18:02, Marco van de Voort wrote: > Second, does FPC understand "tail recursion"? Depends on version, do fpc -i |grep -i tailrec to find out more. >>> >>> O.o >>> >>> Ok... now I'm officially impressed. >> >> Well, simple to implement and useless optimization :) > > But it's nice to have. > > In the lecture "Introduction of Computer Science 2" we had to learn > functional programming with the programming language OCaml. There we > used tail recursion a lot (and I always tried to write my functions in a > tail recursive form) and it's nice to see/know that FPC can do that as > well. :) IIRC in the whole FPC source tree are two cases where this optimization is applied :) > > Btw: is this a CPU dependent optimization? > No. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re[2]: [fpc-pascal] Recursion optimization by compiler
Hello FPC-Pascal, Saturday, September 4, 2010, 9:07:57 AM, you wrote: RB> This a misunderstanding of way recursion can be flattened RB> into a loop. It's especially not useful because the transformed RB> version still uses a stack, so it doesn't execute in constant RB> space. I know, but as far as I know it is the only way to get exactly the same functionality whichever the recursion function works (using a stack different than the default stack). If the recursion function is not the last function it can not be "optimized" in such way, moreover most of that "tail recursive" functions are easy to be rewritten as a while end loop. Anyway I do not have any kind of degree in computer science or alike so I could be completly wrong :) -- Best regards, José ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
On 28.08.2010 11:57, Florian Klämpfl wrote: Am 03.09.2010 21:31, schrieb Sven Barth: On 03.09.2010 18:02, Marco van de Voort wrote: Second, does FPC understand "tail recursion"? Depends on version, do fpc -i |grep -i tailrec to find out more. O.o Ok... now I'm officially impressed. Well, simple to implement and useless optimization :) But it's nice to have. In the lecture "Introduction of Computer Science 2" we had to learn functional programming with the programming language OCaml. There we used tail recursion a lot (and I always tried to write my functions in a tail recursive form) and it's nice to see/know that FPC can do that as well. :) Btw: is this a CPU dependent optimization? Regards, Sven ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
Am 03.09.2010 21:31, schrieb Sven Barth: > On 03.09.2010 18:02, Marco van de Voort wrote: >> >>> Second, does FPC understand "tail recursion"? >> >> Depends on version, do >> >> fpc -i |grep -i tailrec >> >> to find out more. > > O.o > > Ok... now I'm officially impressed. Well, simple to implement and useless optimization :) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
On Sep 2010, at 20:32, José Mejuto wrote: [ some stuff about recursion - at the bottom if you want to read it ] This a misunderstanding of way recursion can be flattened into a loop. It's especially not useful because the transformed version still uses a stack, so it doesn't execute in constant space. Consider the classic factorial function: function fact ( i : integer ) : integer ; begin if i := 0 then fact := 1 else fact := i * fact ( i - 1 ) end ; with initial call "fact ( )" For an actual parameter value "i" this requires O (i) space, because you need to create stack frame to hold the current value of "i" for use after calculating the value "factorial ( i - 1 )" and the return address of the calling routine, (which is actually the same in every stack frame except in the one created by the top-level call). You can see this by writing a top-level-call and plugging in the definition until you hit the base-case: fact ( 4 ) -> 4 * fact ( 3 ) -> 4 * ( 3 * fact ( 2 ) ) -> 4 * ( 3 * ( 2 * fact ( 1 ) ) ) -> 4 * ( 3 * ( 2 * ( 1 * fact ( 0 ) ) ) ) -> 4 * ( 3 * ( 2 * ( 1 * 1 ) ) ) None of the multiplications can be done until the final call of "fact", so all the values must be preserved until then. Now consider this version: function accfact ( f , i : integer ) ; begin if i = 0 then accfact := f else accfact := accfact ( f * i , i - 1 ) end ; with an initial call of "accfact ( 1 , )" This is the standard "accumulating parameter" technique. All the calculation is performed on the descent, no local variables need to be kept, and the return address can simply be the point following the top-level call. The new stackframe can overwrite the old one (or rather the new values for the actual parameters "f" and "i" can simply overwrite the old ones). If you the previous trick of plugging the definition into a top-level call you immediately get: accfact ( 1 , 4 ) -> accfact ( 1 * 4 , 3 ) and we can do the multiplication before making the recursive call. This is "tail recursion". For trees it's a lot trickier to write the processing routines in this kind of tail-recursive form. Suppose we have a data type "tree" that can be empty or hold a value (say an integer) plus two subtrees, either of which may of course be empty at any level. Without getting into the minutiae of data representation and pointer-twiddling, assume functions "value", "left" and "right" to return the value and the two subtrees respectively, and "isempty" to check if a tree is empty. The obvious way to process all the integers in such a tree (perhaps by forming their sum) is: function sum ( t : tree ) : integer ; begin if isempty ( t ) then sum := 0 else sum := value ( t ) + sum ( left ( t ) ) + sum ( right ( t ) ) end ; For a tree with "n" nodes this executes in O (n) space. The accumulating parameter version is a bit less intuitive than "accfact": function accsum ( s : integer ; t : tree ) : integer ; begin if isempty ( t ) then accsum : = s else accsum := accsum ( accsum ( s + value ( t ) , left ( t ) ) , right ( t ) ) end ; with top-level call "accsum ( 0 , )" Here we have double recursion, which for a tree of maximum depth "d" it can be executed in O (d) space. For a balanced tree of "n" nodes, this means O(log(n)) space, which is still a huge improvement on the original version. The key to making this work invisibly is provide higher-order functions to hide the recursion. If necessary they can be hand-coded in assembler and the compiler need never do any optimisation. i.e given a type "munge = function ( a , b : ) : " we define: function mungetree ( b : ; m : munge ; t : -values> ) : ; begin if isempty ( t ) then mungetree : = b else mungetree := mungetree ( mungetree ( munge ( s , value ( t ) ) , left ( t ) ) , right ( t ) ) end ; and depending on what is, and the actual function we supply for "m" (with of course an appropriate base-case value for "b") we can traverse any tree in O(log(n)) space, irrespective of the type of values in the tree or the type of operation performed on them. Or we could if Pascal had a proper polymorphic type system. But it ain't, it's too old-fashioned. On 3 Sep 2010, at 20:32, fpc-pascal-requ...@lists.freepascal.org wrote: > From: Jos? Mejuto > Subject: Re: [fpc-pascal] Recursion optimization by compiler > To: FPC-Pascal users discussions > Message-ID: <166212194.20100903141...@gmail.com> > Content-Type: text/plain; charset=ISO-8859-15 > > Hello FPC-Pascal, > > Friday, September 3, 2010, 1:12:31 PM, you wrote: > > BA> After my previous post, "TreeView and Nonrecursion", I'd tried to ask the
Re: [fpc-pascal] Recursion optimization by compiler
On 03.09.2010 18:02, Marco van de Voort wrote: Second, does FPC understand "tail recursion"? Depends on version, do fpc -i |grep -i tailrec to find out more. O.o Ok... now I'm officially impressed. Maybe it's time to reuse some of my OCaml knowledge from the 3rd term of my study :D Regards, Sven ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
In our previous episode, Bihar Anwar said: > O Marco, I love you :-) Better love Florian :-) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
O Marco, I love you :-) - Original Message From: Marco van de Voort To: FPC-Pascal users discussions Sent: Fri, September 3, 2010 11:02:52 PM Subject: Re: [fpc-pascal] Recursion optimization by compiler > Second, does FPC understand "tail recursion"? Depends on version, do fpc -i |grep -i tailrec to find out more. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
> Second, does FPC understand "tail recursion"? Depends on version, do fpc -i |grep -i tailrec to find out more. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re[2]: [fpc-pascal] Recursion optimization by compiler
Hello FPC-Pascal, Friday, September 3, 2010, 3:06:30 PM, you wrote: BA> First, just curious, have somebody here ever benchmark performance between BA> native stack and regular RAM as a stack? Stack is RAM, so the only difference is in the algorithm used. -- Best regards, José ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
September 3, 2010 7:17:57 PM, José Mejuto wrote: > That kind of "optimization" to me only seems interesting in > two possible situations, when calling functions is high > costly or when there is a very limited stack amount (really, > really small). From my point of view if you need more that > 1MB of stack size I'm quite sure that you are doing > something wrong, because around 65000 recursion levels > looks not very good. > > The recursion "optimization" is being done using regular RAM > as a stack. Thanks Jose, I agree with you. Since in my case I need less than 1MB of stack size, so there is no reason to use nonrecursive/iterative approach. Furthermore, recursion is more readable. Thanks Jose for the code snippets. You introduce TStack that I'm not aware of. First, just curious, have somebody here ever benchmark performance between native stack and regular RAM as a stack? Second, does FPC understand "tail recursion"? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Recursion optimization by compiler
Hello FPC-Pascal, Friday, September 3, 2010, 1:12:31 PM, you wrote: BA> After my previous post, "TreeView and Nonrecursion", I'd tried to ask the same BA> topics in stackoverflow.com BA> (http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion) BA> and I got something new. BA> It is possible to recurse without using up the stack space. Optimizing BA> compilers are able to accomplish certain types of recursion into efficient BA> non-recursive loops, but the code has to be written into a tail recursion form. BA> Is there such a recursion optimization in FPC? If it is not enabled by default, BA> how to enable it? That kind of "optimization" to me only seems interesting in two possible situations, when calling functions is high costly or when there is a very limited stack amount (really, really small). From my point of view if you need more that 1MB of stack size I'm quite sure that you are doing something wrong, because around 65000 recursion levels looks not very good. The recursion "optimization" is being done using regular RAM as a stack: function Recursive(var a: integer): boolean; begin if a=1000 then begin Result:=false; exit; end else begin inc(a); Result:=Recursive(a); end; end; Function Iterative(var a: integer): boolean; var Stack: TStack; v: integer; begin stack.Push(a); while true do begin v:=stack.pop; if v=1000 then begin Result:=true; a:=v; break; end else begin inc(v); Stack.push(v); end; end; stack.free; end; To me the first one looks more clear... -- Best regards, José ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Recursion optimization by compiler
After my previous post, "TreeView and Nonrecursion", I'd tried to ask the same topics in stackoverflow.com (http://stackoverflow.com/questions/3630047/treeview-control-and-nonrecursion) and I got something new. It is possible to recurse without using up the stack space. Optimizing compilers are able to accomplish certain types of recursion into efficient non-recursive loops, but the code has to be written into a tail recursion form. Is there such a recursion optimization in FPC? If it is not enabled by default, how to enable it? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
