Boost logo

Boost :

From: Hamish Mackenzie (hamish_at_[hidden])
Date: 2002-04-15 07:35:49


On Mon, 2002-04-15 at 05:20, David Abrahams wrote:
>
> ----- Original Message -----
> From: "Hamish Mackenzie" <hamish_at_[hidden]>
>
> > Something else that occurs to me is that I can see no reason not have
> > both implementations of the algorithms in the same namespace. The
> loki
> > style implementation being specialisation for type_list_node and
> > type_list_nil. This may be desirable as I expect sometimes recursive
> > approach may use fewer compiler resources.
>
> I know it may be hard to believe, especially after I've repeated it
> several times ;-), but **the MPL implementation is recursive**!

I never doubted it for a second :-). I was speaking in terms of the
implementation of count_if. One implementation calls itself recursively
the other does not.

Is there a better term I can use to make this clear?

Direct/indirect recursion is out as it implies the existence or not of
intermediate functions in the recursion.

Shallow/deep recursion may be confused with the number of times
something recurses rather than the level at which the recursion takes
place.

How about top-level/nontop-level recursion?
 
> Furthermore, why speculate?

True, empirical evidence would be the best way to to decide.

> While the simple-looking implementation may
> use less compile-resources for short lists, it will always use more
> template nesting for long lists and preliminary tests show that it also
> compiles more slowly.

I don't know which the "simple-looking implementation" is? I thought
the general consensus was that simplicity was largely in the eye of the
beholder.

As I understand it, both result in nesting, ether of N * count_if or N *
(for_loop + for_loop_iteration). (I don't seem to have source for
mpl::fold so I am basing this on the next_if implementation).

> In order to optimize for short lists you'd need to
> make specializations for, say, all lengths up to 10. If performing
> matches on those partial specialization doesn't tax the compiler, it
> might be a win. However, that's a big if.

If it did work though, you could do it for the recursive part as well,
which might improve performance for long lists. But I am speculating
again.

What are your thoughts on the other issues involved with including two
implementations?

Pros
* Improved self documentation
* Testability (ie. you can check one implementation against the other)
* Possible compile time performance improvement
* Possibly shorter error messages
Cons
* More code to maintain
* More variation in error messages

Hamish


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk