Author: Vincent Diepeveen
Date: 10:54:14 04/12/04
Go up one level in this thread
On April 11, 2004 at 14:41:20, Dan Andersson wrote: >On April 11, 2004 at 14:06:03, Vincent Diepeveen wrote: > >>On April 10, 2004 at 10:29:51, Dan Andersson wrote: >> >>> There are reasons for using recursion. One of them is that the generated code >>>tends to be smaller. And that could trumph any gains made from reducing the >> >>I disagree with the first point with regards to the data used by the processor >>on the stack. In my function ABISMP() which is a non recursive search using >>principal variation search, i never call the function ABISMP() again. I just >>call it 1 time. That reduces data overhead considerable. It's faster too. >> >>That it is a bit more work to get it to work than recursive search i agree with. >>Complex code can be very tiny though. >> > It could be. But in practice compilers have a hard time reducing code while >keeping enough information to do high level optimizations. So it is a YMMV >issue. Average compiler AFAIK cannot register optimize more than 2 arguments. So i'm very sure that it is not YMMV. for alfabeta, recursion is slower in theory. in practice, non recursive is more work to make. But i really do not see major differences in it, except when you use too many local variables for a position. then for parallel search non-recursive is way easier. > >>>data. >>> Another one is decreasing complexity. And the ability to use induction to prove >>>an algorithm. >> >>Search algorithms are so complex that it is very hard to proof anything >>theoretically. I'm using extensions (singular also) which are of course in fact >>related to the complex evaluation function and nullmove with a quiescencesearch >>which also is unlimited in fact for checks (stack limits it to 32 ply). >> >>In short try to proof something about that. In general your proof has nothing to >>do with whether it is recursive or non-recursive. >> > > Wile it is true in theory it is in most cases significantly easier to reason >and perform proofing on sane recursive code. You talk about 10 lines programs here, like what is in for some books for students trying to see the difference between sorting in O(n*n*n) versus O(n log n). I'm considering 200k lines programs where the choice is to search recursive or non recursive with a complex search. >>> I often use tail recursion as a goto with values. It usually doesn't incur any >>>overhead. And increases branch prediction for some types of code like parsers, >> >>Calling functions is very expensive. I do not know how low level you program but >>a function call a few years ago for commercial chessprograms was too expensive. >> > > Funny how you should group that comment close to my mention of tail recursion. >Because you should know that tail recursion has nothing to do with function >calls at low level code. >>Ask whether one of the commercial programs at the time used recursion. The >>answer is NO. >> >>>regexp and interpreters. >> >>It's all high level stuff used to learn students how things work. Not how >>reality works. >> > Also a funny commentary. Recursion and self similarity is in fact a natural >occurrence. So it is very real. You are playing word games too much. Fact is that recursion is simpler to make and that non recursion is not so simple but faster. >>Recursion is a good tool to teach students how to do bugfree programming. >> >>Saying it is faster than other methods is however not true. The call + ret in >>assembly is very expensive. >> > Recursion could very well be faster. The issues of code complexity and the >interaction with a Harvard architecture split data/code cache makes it a case of >testing to see what works best for you. YMMV as it is. 'could' Give an example where it is faster. with disassembly code please I am sure it is slower than non recursive behaviour. Let's say the 8 queen problem? You solve it recursive, i solve it non recursive, ok? What is faster if we run the problem 1 million times? >>>MvH Dan Andersson
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.