Efficient subtype testing

Languages like Java, C#, Eiffel, and C++ have subtype hierarchies which are directed acyclic graphs, due to interfaces in Java and C# and multiple inheritance in Eiffel and C++. An obvious way to check whether type $A$ is a subtype of type $B$ is to traverse the graph of the subtype hierarchy starting at $A$ to see whether type $B$ appears 'above' it. This surely is not the most efficient way to implement subtype tests.


What techniques exist to efficiently implement subtype testing for modern OO languages?

I'm interested in efficiency both in terms of time and memory and any trade-offs between the two.

Yves Caseau gave a method for efficiently encoding type hierarchies as bit vectors. See Efficient handling of multiple inheritance hierarchies.

StackExchange Computer Science Q#2198, answer score: 2