[boost] Re: overloads: request for discussion

From: Alexander Nasonov (alnsn_at_[hidden])
Date: 2005-01-25 17:48:32

Aleksey Gurtovoy wrote:
> Alexander Nasonov writes:
> > 3. Performance. When number of functions is high everything is
> > important. For example, if all functions have same arity it decrease
> > compilation time significantly. I have to pass a strategy to algorithms.
> >
> > Currently, this example looks like:
> >
> >      overloads::find_if<
> >          overload_set<has_intersection, mpl::range_c<int,1,5> >
> >        , is_same<first_arg<_>, Circle&>
> >        >
> >
> > Close to your code but it's not mpl::find_if.
> 
> Hmm, what _is_ the strategy here? 'overload_set'?

Oops, there is no explicit strategy in my example.
The strategy is optimization for sets of fixed arity. Signature
deduction on a huge set is not as fast as on small sets especially if
repeated many times. Deduction of 4 signatures at once speeds things
up. You can think of it as different unrolling strategy. Unrolling used
in mpl is getting 4 iterators and then apllying deref to each while
unrolling of fixed arity overlod set is vectorized deref that returns 4
types.

I think I can use strategy only in overlod_set specific algorithms (It
would be interesting to see it in mpl algorithms but it's a lot work
only for one not so widely used sequence).

> > What if you have 400? Can mpl::vector or mpl::set contain 400 elements?
> 
> 'mpl::set' definitely can. Structurally, it's not very different from an
> "overload set".

I wonder how to create such a huge set. By inserting elements 400 times?
How much compilation time would it take then?

> > I'm afraid not. Some overloads library work even on higher numbers
> > (up to 700 on my laptop).
> 
> Interesting. How do you generate these in the first place?

typedef overload_set<overloads, range_c<int,1,701> > huge_set;
struct overloads contains 700 call operators.

You can't do much with it. Only special algorithms that is designed with
this number in mind and which are supposed to return a moderate amount
of element. For example, typical FSM may have 20 states and 30 events,
that is, up to 600 transitions. First algorithm to apply to an overload
set of transitions is searching for unique states. It should return an
overload set with size 20 where each signature contains unique state.
20 is moderate number and can be represented by vector20.

This is how this algorithm can transform transitions into overloads
with unique states inside:

in : overload_set<overloads, range_c<int,1,601> >
out: overload_set<overloads, vector20< /*...*/> >

Something similar to has_key would be nice too. I have one idea how to
imlement fast detection of a given signature but I have to check it.

> 
> > 400 is not a random number. Imagine, you have 20 classes in Shape
> > hierarchy. Intersestion of all of them requires 20x20=400
> > has_intersection functions.
> >
> > BTW, I remember Dave mentioned that you generate FSM using mpl::vectorN,
> > with N higher then default 50. How high is N?
> 
> ~70, IIRC.

Is it a number of transitions?

> > > I think Fusion is already capable of building tuples based on the MPL
> > > sequences.
> >
> > 1. It's different. In mpl case you use a sequence to generate tuple *type*.
> 
> I'd expect that you can generate a tuple type populated with some
> corresponding values (?).

I don't know much about fusion, I can only guess. 
I know for sure that I need for_each and few other algorithms.
The fact that fusion has more than for_each and that it is designed for
things having both run- and compile- time sequence properties lead me to
conclusion that it might be useful.

Overloads have both. Set of signatures is compile-time set while each call
operator is run-time thing (it can be called at runtime either directly or
indirectly).

-- 
Alexander Nasonov