Re: [boost] [mpl]iter_fold_if Forward Backward rationale?

Subject: Re: [boost] [mpl]iter_fold_if Forward Backward rationale?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-06-05 12:05:20

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!
>