Conversions between classes related by inheritance

[David Abrahams]

Hi Ulli (and anyone else who cares!),

I'm getting ready to implement implicit upcasting/downcasting and (yes!)
cross-casting of class instances that are related by inheritance for the
Boost.Python rewrite.

Ullrich has suggested that it would be good to optimize these conversions,
especially in order to speed overload resolution in the cases where some
attempts will fail. When attempting to unwrap a class X, the current
approach performs a depth-first traversal of the inheritance DAG in which X
participates, starting at X and performing conversions at each step, and
revisiting nodes in cases of diamond inheritance. Especially in the case of
down-cast attempts, this can be slow due to the need for many
dynamic_cast<>s.

The most obvious optimization to do at first would be to quickly check
whether the target class is part of a common inheritance hierarchy with the
class of the object held in the Python object being unwrapped before doing
any dynamic_cast<>s. We can make that an O(N) operation where N is the
number of classes in the hierarchy, for example, by doing a breadth-first
search. We could make it an O(1) operation by maintaining a unique
identifier for each set of related classes.

The above optimization helps us quickly rule out some conversions that won't
work, but if we get past that test, we still need to find a path through the
inheritance hierarchy that connects the source and target classes... and in
the case of downcasts or cross-casts, the conversion /still/ might not
succeed.

The only obvious way to optimize further, AFAICT, would be to cache a record
of the path from source to target. This might be extremely useful for
efficiently implementing CLOS-style (multimethod) overload resolution, but
it could also be expensive in large class hierarchies (O(N^2) in space).

I'd like to hear from people about how important they consider this to be,
and what trade-offs their applications demand. Also, if there are other
ideas about ways to improve this mechanism, I'd love to hear those as well.

Thanks,
Dave

===================================================
  David Abrahams, C++ library designer for hire
 resume: http://users.rcn.com/abrahams/resume.html

        C++ Booster (http://www.boost.org)
          email: david.abrahams at rcn.com
===================================================