Boost logo

Boost :

From: Eric Friedman (ebf_at_[hidden])
Date: 2003-08-13 16:57:29


Brian Simpson wrote:
> Eric,
>
[snip]
> Heavily qualified explanation to follow... :)
>
> [snip]
> Oops! I saw the typedef'd names, observed their similarity to the names
of
> the template parameters, and immediately assumed that the switch was based
> on those parameters. Therefore, the value I _thought_ I was adding was in
> the basing of the switch statement on an mpl::Sequence rather than on the
> template parameters. I took a closer look at the current implementation
and
> observed that it is, indeed, based on the Sequence rather than the
template
> parameters--and I feel a little stupid for not noticing it before :).

No need to apologize! I'm just sorry you spent time reimplementing the
feature.

> >Thus, if we are to assume O(1) complexity for a switch, then the
complexity
> >of the visitation mechanism becomes O( N / unrolling-size ), where
> >unrolling-size is exposed as
>
> It sounds like you've become convinced that the switch is, indeed, worth
the
> effort? (I infer from the previous statement that you consider the 'if'
to
> be O(N), as opposed to a O(1) for the switch.)

Well not really...

In theory, both recursively-inline ifs and switches could be optimized to
O(1) via a jump table. It's a question, then, of whether the optimization
happens in practice with none, one, or both of them. Personally, I've done
no research to determine the answer (and would welcome any information on
the matter).

That said, I switched the implementation to use switch for the following
reasons: 1) despite my lack of any information one way or the other, I am
somewhat convinced by the argument that compilers would be more likely to
implement the optimization on switch statements than with if statements; and
2) I had some extra time on my hands and wanted to see how difficult/complex
the implementation would be.

[snip]
> My implementation is not achieving a better result :). It's achieving the
> same result as yours; I mentioned above the proposed extra value--which,
> unfortunately for my credibility, was based on a faulty reading.

I don't know if you need to worry about credibility. The variant
implementation is complex and -- except for occasional, short comments --
largely undocumented.

> Still, I would like to put forward a couple of considerations. These are
> comparatively subjective:
> 1) The "runtime_type_selected_invoker" component is implemented
independent
> of variant. Two benefits deriving from this approach are:
> a) "variant" becomes a client rather than a collaborator in the usage of
> the functionality. The practical differences? A three-argument function
> call rather than a six-argument call dependent on two supporting typedefs.

Generally I might agree with this argument, but I disagree in this instance
because of the the heavy use of templates invovled. Thus, even if the
visitation mechanism were in a separate header, any changes will require any
code dependent on variant.hpp to be recompiled. So with that given, I'm not
sure what other advantages there would be (apart from perhaps a
slightly-simplified invocation in variant's raw_apply_visitor
implementation).

> b) Distribution decisions can be made separately for the two. One that
I
> thought of was preprocessing. If someone wants to distribute preprocessed
> versions of code, he can make one decision for variant and another for
> "rtts".

I actually do agree with this. Accordingly, I've factored apply_visitor_impl
into a separate detail header. And I do plan to look into preprocessing at
some point...

> 2) An interesting characteristic of your approach is that it results in
the
> generation of "extra" cases which should never be executed. There seems
to
> be some extra complexity involved in implementing these extra cases. The
> implementation I propose does not suffer this problem. (Don't these extra
> cases seem like constructing a foundation with the cracks "built-in"? I
> know that the correctness of the class should make it impossible to ever
> fall in, but it still makes me nervous.)
> If you don't have to worry about how to implement "extra" cases, you can
> spend more time implementing more visible stuff!

Hmm... If the variant class is not correct then a more reliable visitation
mechanism isn't going to help anything (and may potentially mask any
problems). Furthermore, there have been assertions in forced_return (and now
apply_visitor_impl itself) to catch obviously broken implementations.

So I guess this point could work either way, but I don't know if its worth
changing anything now as a result. (Please reply if you disagree.)

[snip]
> Again, thanks for your work. I couldn't have even made this proposal (and
> had a little fun) had so much legwork not been done already. And I
> apologize for saying that you hadn't implemented such a solution when you
> actually had.

I appreciate the compliment. And don't worry about the oversight -- I know
I've had similar misunderstandings before.

Thanks,
Eric


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