"Andrei Alexandrescu" <andrewalex@hotmail.com> wrote:
> Hi,
>
> I just ran into an extremely interesting problem. (Well, your
> enthusiasm may vary.)
>
> I implement Scott Meyers' double dispatch engine. Of course, with
> my little list of improvements.
>
> One of this improvement relates to performance. Let's set the
> stage with some code:
>
> void Collide(Spaceship&, Asteroid&);
> ...
> DoubleDispatcher dd;
> dd.Add<Spaceship, Asteroid>(&Collide);
> ...
> GameObject *p1 = ...;
> GameObject *p2 = ...;
> dd.Go(*p1, *p2); // invokes Collide if types match
>
> The DoubleDispatcher object adds the address of Collide to the
> now legendary map with type_infos and functions, ordered by
> type_info::before.
> Okaaaaaaaay.
>
> Unlike Scott's engine, DoubleDispatcher does the casts by
> itself (Scott's engine requires you to register functions
> that accept GameObject& only, so you have to do the cast).
> Here's where the question comes.
>
> Should DoubleDispatcher do a dynamic_cast or a static_cast?

I think it should *always* do a dynamic_cast.

> As Scott says, "you're better off safe than sorry" (I know
> this by heart now :o)),

Exactly.

> but static_cast can be considerably faster

That's irrelevant if the answer is sometimes wrong.

(Presumably the registration would happen once, during
program initialization. Is the speed of the dynamic_cast
critical here?)

> and applies most of the cases.

But you don't know which cases in advance. And the thing that
you're missing is that it can be safe sometimes, and unsafe
other times in the same program run.

> Plus, because now it's hidden in DoubleDispatcher (not in
> client code), the cast is safer.

True.

> It all boils down to this: you have two types, Base and Derived.
> How can you determine, at compile-time or at runtime, whether
> static_cast<Derived*>(p) works instead of
> dynamic_cast<Derived*>(p), where p points to a Base?

I think you're oversimplifying.

> If Derived inherits Base more than once and/or through virtual
> inheritance, that won't work so I'll have to dynamic_cast.
> However, this case is fairly rare and I don't want to always
> hurt the performance "just in case".

That's the easy part of the problem. The subtle case happens
when Derived inherits Base only once. You still can't assume
that static_cast is safe unless you are certain that you're
dealing with a Derived object (and not a MoreDerived object).

Consider this:
    struct Base { int b; };
    struct Derived : public Base { int d; };
    Base*BaseFromDerived(Derived*d) {
        return static_cast<Base*>(d);
    }
    int foo() {
        Derived d;
        Base *b = BaseFromDerived(&d); // No problem
    }

    struct Sister : public Base { int s; };
    struct Muckup : public Sister, public Derived { int m; }
    int bar() {
        Muckup m;
        Base *b = BaseFromDerived(&m); // Big problem!
    }

So even if you know that Derived has the correct semantics to
make static_cast safe, you can't know that there's nothing
derived from it that makes this dangerous.

> What tantalizes me is that the information is embedded in the
> program and is available at compile-time. I wonder how I
> could reach it.

If the information was available at compile-time, then this
would be a QOS issue, because most or all compilers would
optimize away the difference.

On the other hand, at link time we could identify the common
"special case" where nothing derived from Derived has MI or
virtual inheritance. Systems that do not have separate phases
for "compile" and "link" might be able to optimize this case.

Another way to handle this is to let the programmer specify
what type of cast is done, using something similar to traits.

    // The trait class
    template<class F,class T>class game_cast {
        static class T* cast(class F*f) {
            return dynamic_cast<class T*>(f);
        }
    };

    // Your program uses
    GameObject * g = game_cast<Spaceship,GameObject>(s);

    // By default, that uses dynamic_cast. If the programmer
    // wishes to assert that static_cast is safe, she writes:
    template<>class game_cast<Spaceship,GameObject> {
        static GameObject*cast(Spaceship*f) {
            return static_cast<GameObject*>(f);
        }
    }

--
Allan_W@my-deja.com is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.


Sent via Deja.com http://www.deja.com/
Before you buy.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AllanW <allan_w@my-deja.com> wrote in message
news:8dqk69$9he$1@nnrp1.deja.com...
> > Should DoubleDispatcher do a dynamic_cast or a static_cast?
>
> I think it should *always* do a dynamic_cast.

I disagree. In the meantime I kept thinking and I reached the following rule
of thumb: if you use single inheritance, you can use static_cast. If you use
multipl inheritance (be it virtual or not), static_cast can fail so you
should use dynamic_cast.

Because an important precentage of architectures use single inheritance, I
decided to make the decision on what cast to use, a policy, I migrated the
policy as a template parameter, documented the requirements, defaulted to
dynamic_cast, and left the user decide.

> > but static_cast can be considerably faster
>
> That's irrelevant if the answer is sometimes wrong.

That's irrelevant if I hardcode dynamic_cast and someone who wants an
efficient dispatcher with a single inheritance hierarchy cannot use mine.

> (Presumably the registration would happen once, during
> program initialization. Is the speed of the dynamic_cast
> critical here?)

It's not about registration, it's about each call.

> > and applies most of the cases.
>
> But you don't know which cases in advance. And the thing that
> you're missing is that it can be safe sometimes, and unsafe
> other times in the same program run.

I think I found a good solution, as shown above.

> > It all boils down to this: you have two types, Base and Derived.
> > How can you determine, at compile-time or at runtime, whether
> > static_cast<Derived*>(p) works instead of
> > dynamic_cast<Derived*>(p), where p points to a Base?
>
> I think you're oversimplifying.

I'm not. I think I got the right guideline.

> Another way to handle this is to let the programmer specify
> what type of cast is done, using something similar to traits.

Ah, now I see we're into the same solution. Great.



Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Once again, with the help of a meta-if template going somewhere in the
following direction:

template< bool static, class T, class U >
struct Caster
{
    static U cast( T Arg )
        { return static_cast<U>( Arg ); }
};

// Partial specilization
template< class T, class U >
struct Caster< false, T, U >
{
    static U cast( T Arg )
        { return dynamic_cast<U>( Arg ); }
}

Now the problem is to determine the inheritance status. Let's use the usual
trick to do this:

template< class Base, class Candidate >
struct CheckerHelper
{
 typedef char (&no)[1];
 typedef char (&yes)[2];

static yes Test( Base* );

static no Test( ... );
};

template< class Candidate, class Base >
class InheritsFrom
{
public:
 enum { IsTrue =
   sizeof( CheckerHelper< Base, Candidate >::Test( static_cast< Candidate*
>( 0 ) ) ) ==
   sizeof( CheckerHelper< Base, Candidate >::yes ) };
};

Now you can just use it to select the right caster at compile-time:

void Dispatch()
{
        X x;
        Y y = Caster< InheritsFrom< X, Y>::IsTrue >::cast( x );
}

    J.-D. Nicolet
    Software Consultant
    Geneva
    Switzerland


Andrei Alexandrescu wrote in message ...
>Hi,
>
>
>I just ran into an extremely interesting problem. (Well, your enthusiasm
>may vary.)
>
>I implement Scott Meyers' double dispatch engine. Of course, with my little
>list of improvements.
>
>One of this improvement relates to performance. Let's set the stage with
>some code:
>
>void Collide(Spaceship&, Asteroid&);
>...
>DoubleDispatcher dd;
>dd.Add<Spaceship, Asteroid>(&Collide);
>...
>GameObject *p1 = ...;
>GameObject *p2 = ...;
>dd.Go(*p1, *p2); // invokes Collide if types match
>
>The DoubleDispatcher object adds the address of Collide to the now
legendary
>map with type_infos and functions, ordered by type_info::before.
>Okaaaaaaaay.
>
>Unlike Scott's engine, DoubleDispatcher does the casts by itself (Scott's
>engine requires you to register functions that accept GameObject& only, so
>you have to do the cast). Here's where the question comes.
>
>Should DoubleDispatcher do a dynamic_cast or a static_cast? As Scott says,
>"you're better off safe than sorry" (I know this by heart now :o)), but
>static_cast can be considerably faster and applies most of the cases. Plus,
>because now it's hidden in DoubleDispatcher (not in client code), the cast
>is safer.
>
>It all boils down to this: you have two types, Base and Derived. How can
you
>determine, at compile-time or at runtime, whether static_cast<Derived*>(p)
>works instead of dynamic_cast<Derived*>(p), where p points to a Base?
>
>If Derived inherits Base more than once and/or through virtual inheritance,
>that won't work so I'll have to dynamic_cast. However, this case is fairly
>rare and I don't want to always hurt the performance "just in case".
>
>What tantalizes me is that the information is embedded in the program and
is
>available at compile-time. I wonder how I could reach it.
>
>
>Andrei
>
>
>
>
>---
>[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
>[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
>[              --- Please see the FAQ before posting. ---               ]
>[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Jean-Daniel Nicolet" <jdn@llinkvest.ch> wrote in message
news:8d7elb$o28$1@pollux.ip-plus.net...
> Once again, with the help of a meta-if template going somewhere in the
> following direction:
>
> template< bool static, class T, class U >
> struct Caster
> {
....
> };
>
> Now the problem is to determine the inheritance status. Let's use the
usual
> trick to do this:

This is really cool, but I don't think it helps Andre's problem because
the answer (in his case) to InheritsFrom is always 'true'.  Andre needs
to find out if

    dynamic_cast<D*>(b) == static_cast<D*>(b)

(where b is a pointer to a base type and D is the derived type)
at compile time.

Hey, I just had a thought.  We can thing of generic programming as
using 'compile time polymorphism' right?  What about carrying over
a concept of 'compile time exception handling'

try<> {
    /* stuff which may not compile */
}
catch<> ( type_conversion_exception ) {
}
catch<> ( syntax_error_exception ) {
}

etc?


marco



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

>>>>>>>>>>>>>>>>>> Urspr   ngliche Nachricht <<<<<<<<<<<<<<<<<<

Am 15.04.00, 04:41:44, schrieb "Jean-Daniel Nicolet" <jdn@llinkvest.ch> zum
Thema Re: A very very VERY interesting problem:


> Once again, with the help of a meta-if template going somewhere in the
> following direction:

SNIP

> Now the problem is to determine the inheritance status. Let's use the
usual
> trick to do this:

SNIP

> template< class Candidate, class Base >
> class InheritsFrom
> {
> public:
>  enum { IsTrue =
>    sizeof( CheckerHelper< Base, Candidate >::Test( static_cast<
Candidate*
> >( 0 ) ) ) ==
>    sizeof( CheckerHelper< Base, Candidate >::yes ) };
> };

> Now you can just use it to select the right caster at compile-time:

> void Dispatch()
> {
>         X x;
>         Y y = Caster< InheritsFrom< X, Y>::IsTrue >::cast( x );
NIT: seems you have to specify Y once more in caster.
> }

But Andrei wants to cast Pointers or References AND he wants to cast from
Base to Derived. So you should consider:

void Dispatch(X* p, void (Y::*f)())
{
 Y* y = Caster< StaticCastOk<X,Y>::IsTrue, Y*>(p);
 assert(y);
 (y->*f)();
}

But the real trouble is ...

> Andrei Alexandrescu wrote in message ...

> >I just ran into an extremely interesting problem. (Well, your enthusiasm
> >may vary.)

SNIP

> >It all boils down to this: you have two types, Base and Derived. How can
> you
> >determine, at compile-time or at runtime, whether
static_cast<Derived*>(p)
> >works instead of dynamic_cast<Derived*>(p), where p points to a Base?
> >
> >If Derived inherits Base more than once and/or through virtual
inheritance,
> >that won't work so I'll have to dynamic_cast. However, this case is
fairly
> >rare and I don't want to always hurt the performance "just in case".

... when Derived inherits Base through virtual inheritance, then
InheritsFrom<Derived,Base>::IsTrue == true, but static_cast wont work.

Otherwise if Derived inherits Base multiply (iow if Derived has multiple
'Base' base class subobjects) then static_cast will work, but
InheritsFrom<Derived,Base> cant be instantiated.
The call to CheckerHelper::Test will be rejected because the conversion
from Derived* to Base* is possible but ambiguous.

I'm sure Andrei has attempted your solution (I first saw this idiom in
one of his posts).

The real problem is to find a replacement for InheritsFrom that handles
these cases.

It should be: InheritsFromNonVirtuallyAndUnambiguously.

AFAICS you can determine that this is indeed the case only by having some
template instantion fail because something would be ill-formed. But then
compilation will stop right there :-(

Another problem is how to handle the case where a static_cast is legal,
but only dynamic_cast is guaranteed to be correct (see below) or the case
where static_cast is OK but dynamic_cast will fail (I don't remember now
how to produce that one).

struct B { virtual ~B(); };
struct D1 : B {};
struct D2 : B {};
struct E : D1,D2 {}

D2* pd2 = new E;
B* pb = pd2;
D1* pd1 = dynamic_cast<D1*>(pb); // OK
pd1 = static_cast<D1*>(pb); // Well-formed but erroneous


-- J   rg



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jean-Daniel Nicolet <jdn@llinkvest.ch> wrote in message
news:8d7elb$o28$1@pollux.ip-plus.net...
> Once again, with the help of a meta-if template going somewhere in the
> following direction:

Thanks for the answer.

Unfortunately, that won't work.

When you'll try to apply InheritsFrom on a type that inherits its base, you
won't get a boolean answer, you'll get a compile-time error (ambiguity). For
instance:

class GameObject { ... };
class SpaceShip : public GameObject { ... };
class Asteroid : public GameObject { ... };
class Borg : public SpaceShip, public Asteroid {};

With the tool you use, you cannot detect the relationship between Borg and
GameObject.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

J   rg Barfurth <joerg.barfurth@germany.sun.com> wrote in message
news:20000414.17570383@jb-11116.stardiv.de...
[snip]

A possible crippled solution is to make the code that uses static_cast but
it shouldn't, uncompilable. Then I provide two sets of functions: some that
use static_cast, and some that use dynamic_cast. The user calls whichever
finds fit. Then I provide the user with documentation like: "Try to use
StaticAdd, and when it doesn't compile, replace it with DynamicAdd." What an
embarrassment.

Seems, however, that this is the best solution. I repeat, I don't want to
force using dynamic_cast when there's no need for it.

In this case I will have to add a compile-time assert that Derived* converts
automatically to Base*. This eliminates the case of multiple non-virtual
bases. The case of virtual bases is eliminated from start because you cannot
do static_cast<Derived*>(Base*) if Derived has Base as a virtual base class.

Is my reasoning correct?


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

(This is a copy of an email I sent directly to Mr.
Alexandrescu.  He suggested I post it and also said
that he knew of a situation where it wouldn't
work. I'm awaiting the answer to his puzzle).

Andre,

After reading your 'traits' article in C++ Report (nicely
done, by the way) I came up with this possible solution
which has some implementation defined behavior, but may
be portable enough to be useful.

The idea is this:

template<typename To, typename From>
class cast_traits {
private:
    enum CastType { unknown, use_dynamic, use_static };
    static CastType how_to_cast;
public:
    To* cast( From* from ) {
        if ( from == 0 ) return 0;
        if ( how_to_cast == unknown ) {
            To* to1 = dynamic_cast<To*>(from);
            To* to2 = (To*) from;
            how_to_cast = ( to1 == to2 ) ?
                use_static :
                use_dynamic;
        }
        return ( m_how_to_cast == use_static ) ?
                    (To*) from :
                    dynamic_cast<To*>(from);
    }
}

In words, use the C-style cast operator to perform
the static cast.  But, the first time a cast is
attempted, check to see if a static_cast results
in the same pointer value as a dynamic_cast.  If it
does, perform a static cast on all subsequent casts
between From to To.

You still pay for one dynamic cast (and 3 tests on
all casts) but I think you're still better off in
the long run.

cheers,
marco



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Marco Dalla Gasperina wrote:
>
> (This is a copy of an email I sent directly to Mr.
> Alexandrescu.  He suggested I post it and also said
> that he knew of a situation where it wouldn't
> work. I'm awaiting the answer to his puzzle).
>
> Andre,
>
> After reading your 'traits' article in C++ Report (nicely
> done, by the way) I came up with this possible solution
> which has some implementation defined behavior, but may
> be portable enough to be useful.
>
> The idea is this:
>
> template<typename To, typename From>
> class cast_traits {
> private:
>     enum CastType { unknown, use_dynamic, use_static };
>     static CastType how_to_cast;
> public:
>     To* cast( From* from ) {
>         if ( from == 0 ) return 0;
>         if ( how_to_cast == unknown ) {
>             To* to1 = dynamic_cast<To*>(from);
>             To* to2 = (To*) from;
>             how_to_cast = ( to1 == to2 ) ?
>                 use_static :
>                 use_dynamic;
>         }
>         return ( m_how_to_cast == use_static ) ?
>                     (To*) from :
>                     dynamic_cast<To*>(from);
>     }
> }
>
> In words, use the C-style cast operator to perform
> the static cast.  But, the first time a cast is
> attempted, check to see if a static_cast results
> in the same pointer value as a dynamic_cast.  If it
> does, perform a static cast on all subsequent casts
> between From to To.
>
> You still pay for one dynamic cast (and 3 tests on
> all casts) but I think you're still better off in
> the long run.

I think this can be simplified:

template<class To, class From>
 inline To optimal_cast(From* p)
{
  if (!p) return NULL;

  static bool static_cast_works = (To(p) == dynamic_cast<To>(p));

  if (static_cast_works)
    return To(p);
  else
    return dynamic_cast<To>(p);
}

This function can be used with usual cast syntax:

To* ToPointeroptmal_cast<To*>(FromPointer);

However, both versions fail in the following situation:

class Base { virtual ~Base(); };
class Derived: public virtual Base {};

Base* pB = new Derived;
Derived* pD = optimal_cast<Derived*>(pB); // Error

The point is that casting from virtual base to derived is
_only_ allowed with dynamic_cast - even old-style casts
are not allowed here.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi,


I just ran into an extremely interesting problem. (Well, your enthusiasm
may vary.)

I implement Scott Meyers' double dispatch engine. Of course, with my little
list of improvements.

One of this improvement relates to performance. Let's set the stage with
some code:

void Collide(Spaceship&, Asteroid&);
...
DoubleDispatcher dd;
dd.Add<Spaceship, Asteroid>(&Collide);
...
GameObject *p1 = ...;
GameObject *p2 = ...;
dd.Go(*p1, *p2); // invokes Collide if types match

The DoubleDispatcher object adds the address of Collide to the now legendary
map with type_infos and functions, ordered by type_info::before.
Okaaaaaaaay.

Unlike Scott's engine, DoubleDispatcher does the casts by itself (Scott's
engine requires you to register functions that accept GameObject& only, so
you have to do the cast). Here's where the question comes.

Should DoubleDispatcher do a dynamic_cast or a static_cast? As Scott says,
"you're better off safe than sorry" (I know this by heart now :o)), but
static_cast can be considerably faster and applies most of the cases. Plus,
because now it's hidden in DoubleDispatcher (not in client code), the cast
is safer.

It all boils down to this: you have two types, Base and Derived. How can you
determine, at compile-time or at runtime, whether static_cast<Derived*>(p)
works instead of dynamic_cast<Derived*>(p), where p points to a Base?

If Derived inherits Base more than once and/or through virtual inheritance,
that won't work so I'll have to dynamic_cast. However, this case is fairly
rare and I don't want to always hurt the performance "just in case".

What tantalizes me is that the information is embedded in the program and is
available at compile-time. I wonder how I could reach it.


Andrei




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]