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-10 16:19:59

On 06/05/09 11:05, Larry Evans wrote:
 > 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.

[snip]

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

Actually, the 2 BOOST_PP_REPEAT invocations in iter_fold_if_impl do
essentially the same as 2 while loops mentioned above. The 1st
BOOST_PP_REPEAT invocation creates the "explicit" stack and the 2nd
BOOST_PP_REPEAT goes down this explicit stack (or up the "implicit"
recursion stack), while invoking BackwardOp.

Well, that's not entirely true.  The explicit stack is created by
recursive calls of iter_fold_if_impl *and* the 1st BOOST_PP_REPEAT
call. If the I-th recursive call of iter_fold_if_impl is denoted by:

   iter_fold_if_impl@[I]

and the typedef target (e.g. forward_step4) produced by the J-th call
of the 1st BOOST_PP_REPEAT is denoted by:

   forward_step#[J]

then the explicit stack can be denoted by:

   iter_fold_if_impl@[0]::forward_step#[0]
   iter_fold_if_impl@[0]::forward_step#[1]
   iter_fold_if_impl@[0]::forward_step#[2]
    .
    .
    .
   iter_fold_if_impl@[0]::forward_step#[M]

     iter_fold_if_impl@[1]::forward_step#[0]
     iter_fold_if_impl@[1]::forward_step#[1]
     iter_fold_if_impl@[1]::forward_step#[2]
      .
      .
      .
     iter_fold_if_impl@[1]::forward_step#[M]

       ...

         iter_fold_if_impl@[N]::forward_step#[0]
         iter_fold_if_impl@[N]::forward_step#[1]
         iter_fold_if_impl@[N]::forward_step#[2]
          .
          .
          .
         iter_fold_if_impl@[N]::forward_step#[M+1]

where:
   horizontal indentation is a visual que (in addition to the @[.]
     notation ) to the recursion depth.
   M+1 == BOOST_MPL_LIMIT_UNROLLING.
   N is the number of recursive calls to iter_fold_if_impl.

As mentioned, the 2nd BOOST_PP_REPEAT goes up the recursion stack.
Instead of creating forward_stepJ typedefs, it creates backward_stepJ
typedefs. These will be denoted:

   backward_step#[J]<Iterator,State>

where:

   Iterator and State are some previous typedef targets.

The reason for the <,> suffix is to indicate the dependency on
previous typedefs. The actual dependency is, roughly, on the stack's
forwardstep's iterator and the immediately previous backstep's state.

Thus, going up the recursion stack results in typedefs denoted by:

         iter_fold_if_impl@[N]::backward_step#[M]
           < iter_fold_if_impl@[N]::forward_step#[M]::iterator
           , iter_fold_if_impl@[N]::forward_step#[M]::state
           >
          .
          .
          .
         iter_fold_if_impl@[N]::backward_step#[2]
           < iter_fold_if_impl@[N]::forward_step#[2]::iterator
           , iter_fold_if_impl@[N]::backward_step#[3]::state
           >
         iter_fold_if_impl@[N]::backward_step#[1]
           < iter_fold_if_impl@[N]::forward_step#[1]::iterator
           , iter_fold_if_impl@[N]::backward_step#[2]::state
           >
         iter_fold_if_impl@[N]::backward_step#[0]
           < iter_fold_if_impl@[N]::forward_step#[0]::iterator
           , iter_fold_if_impl@[N]::backward_step#[1]::state
           >

       ...

     iter_fold_if_impl@[1]::backward_step#[M]
       < iter_fold_if_impl@[1]::forward_step#[M]::iterator
       , iter_fold_if_impl@[2]::backward_step#[0]::state
       >
      .
      .
      .
     iter_fold_if_impl@[1]::backward_step#[2]
       < iter_fold_if_impl@[1]::forward_step#[2]::iterator
       , iter_fold_if_impl@[1]::backward_step#[3]::state
       >
     iter_fold_if_impl@[1]::backward_step#[1]
       < iter_fold_if_impl@[1]::forward_step#[1]::iterator
       , iter_fold_if_impl@[1]::backward_step#[2]::state
       >
     iter_fold_if_impl@[1]::backward_step#[0]
       < iter_fold_if_impl@[1]::forward_step#[0]::iterator
       , iter_fold_if_impl@[1]::backward_step#[1]::state
       >

   iter_fold_if_impl@[0]::backward_step#[M]
     < iter_fold_if_impl@[0]::forward_step#[M]::iterator
     , iter_fold_if_impl@[1]::backward_step#[0]::state
     >
    .
    .
    .
   iter_fold_if_impl@[0]::backward_step#[2]
     < iter_fold_if_impl@[0]::forward_step#[2]::iterator
     , iter_fold_if_impl@[0]::backward_step#[3]::state
     >
   iter_fold_if_impl@[0]::backward_step#[1]
     < iter_fold_if_impl@[0]::forward_step#[1]::iterator
     , iter_fold_if_impl@[0]::backward_step#[2]::state
     >
   iter_fold_if_impl@[0]::backward_step#[0]
     < iter_fold_if_impl@[0]::forward_step#[0]::iterator
     , iter_fold_if_impl@[0]::backward_step#[1]::state
     >

One bad consequence of using BOOST_PP_REPEAT this way is that the
iterator argument to the topmost backward_step:

         iter_fold_if_impl@[N]::backward_step#[M]
           < iter_fold_if_impl@[N]::forward_step#[M]::iterator
           , iter_fold_if_impl@[N]::forward_step#[M]::state
           >

may be the the end iterator, mpl::end<Sequence>::type, where Sequence
is the 1st argument to iter_fold_if. The solution proposed here:

 
https://svn.boost.org/trac/boost/attachment/ticket/3044/iter_fold_if.patch 

is to simply replace the BackwardPred with a test on whether the
iterator is the end iterator.  Of course this lessens the ease of use
because now the user, if he desires something like reverse_find, will
have to modify BackwardOp to incorporate some sort of BackwardPred and
to do nothing if this BackwardPred is false.  This solution was
proposed here:

   http://article.gmane.org/gmane.comp.lib.boost.devel/189764

A second bad consequence of using BOOST_PP_REPEAT is that no
"short-circuiting" (i.e. BackwardPred returns false part-way up the
recursion stack) is possible.  This is because each
backward_step#[J]'s depends on either backward_step#[J+1] in the
current recursive call or the backward_step#[0] in the previous
recursive call to iter_fold_if_impl.  Thus all the bacward_step#[J]'s
instantiated even if they're no-ops.

In contrast, the 2 while loop solution, implemented using the
while_recur template here:

   https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp

suffers neither of these bad consequences because the explicit
recursion stack is implemented with a mpl::list.  While creating the
explicit stack, the end iterator is not pushed onto the explicit stack
because template metaprogramming (in contrast to preprocessor
metaprogramming) can detect the end iterator.  Going up the recursion
stack can be short-circuited because, again, template metaprogramming
can detect when an element in the explicit stack fails the
BackwardPred and can exit the while_recur loop early.

The only advantage that the 2 BOOST_PP_REPEAT loop solution has over
the 2 while_recur solution is that it may create fewer template
instantions, especially when BackwardPred is always<true_>.  That's
because with such a BacwardPred, no short-ciruiting is possible and
the mpl::list used to implement the explicit stack has some
instantiation overhead.  However, that's only a guess.  To really
tell, some tests with Steven's template profiler are needed.

-regards,
Larry