Re: Canonical type nodes, or, comptypes considered harmful

[Mike Stump <mrs at apple dot com>]

On Nov 8, 2006, at 7:14 AM, Ian Lance Taylor wrote:
> The way to canonicalize them is to have all equivalent types point to
> a single canonical type for the equivalence set.  The comparison is
> one memory dereference and one pointer comparison, not the current
> procedure of checking for structural equivalence.

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.  The only way to save yourself, is to be able to say,  
different addresses, _must_ be different types.

An example, are these two types the same:

	********************A
	********************B

given that A and B are the same type.  Your way, you need to walk two  
trees, hitting memory 40 times.  The cost is 40 cache misses, each  
one takes 100 ns, so we're up to 2000 ns to compare them.  In my  
scheme, the addresses are the same, so for codegen you get:

	cmp p1, p2

which is 1 machine instruction, and no memory hits, and this runs in  
around 0.2 ns, a 10000x speedup.  Now, imagine real live template  
code.  20 deep is nothing, and the branching is worse than one I  
suspect.