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:
OOPS, I deleted it from the vault for some reason; however,
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:
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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk