On 06/05/09 10:00, David Abrahams wrote:
on Wed Jun 03 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it. Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack?
How can you possibly "avoid going back up the recursion stack?"
By making the stack explicit and using 2 while loops. The first while loop goes down the recursion stack, while storing the values in an mpl::list, the 2nd while then goes up the stack but terminates when the BackPred is reached. Shouldn't that work? It does work for the tests shown in the code. I thought the test cases accompanying the while.cpp in the previous post I mentioned showed that. OOPS, I didn't put that code in the post, but did put it in the vault and announced it earlier in this thread: http://article.gmane.org/gmane.comp.lib.boost.devel/188775 OOPS, I deleted it from the vault for some reason; however, it's here: https://svn.boost.org/trac/boost/attachment/ticket/3044/while.cpp However, there's also a version, while_unroll_recur, which does loop unrolling. I've just added while_unroll.cpp to the ticket. https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp while_recur.cpp has a 2 functionally equivalent while templates: - while_recur (no unrolling, just like the earlier attachment) - while_unroll_recur (does unrolling) The macro, USE_WHILE_UNROLL, governs which is used. A comparision of what the min value of NN in the compiler option, -ftemplate-depth-NN needed to compile the code is: For while_unroll_recur: depth compiled? ----- --------- 32 yes 31 no For while_recur: depth compiled? ----- --------- 38 yes 37 no I would have guessed maybe a factor of 4 improvement; however, it just appears only a difference of 6. I've no idea why.
That's like asking the recursive metafunction invocations not to "return." I suppose we could cause a compiler error, but I doubt that's what you had in mind!