Re: Canonical type nodes, or, comptypes considered harmful

[Joe Buck <Joe dot Buck at synopsys dot COM>]

On Thu, Nov 09, 2006 at 04:54:23PM -0800, Mike Stump wrote:
> Once not equal addresses might mean equal types, you have to do a  
> structure walk to compare types, and you're right back were we  
> started.

Not quite.  A structure walk is required to be certain of equality,
but if inequality is the more common case, some kind of hash to speed
up that case could speed things up.  For example, in

> 	********************A
> 	********************B

if each node in the type tree contains some kind of hash code,
which is built as a function of the leaves when the tree is constructed,
then you avoid the tree walk.  However, for

> 	********************A
> 	********************A

at different addresses, you still have to do it.  Someone said earlier
in this thread that inequality was 34x as common as equality, so ...