Boost logo

Boost :

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

OOPS, I deleted it from the vault for some reason; however,
it's here:

However, there's also a version, while_unroll_recur, which does loop
unrolling. I've just added while_unroll.cpp to the ticket.

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!

Boost list run by bdawes at, gregod at, cpdaniel at, john at