Re: Canonical type nodes, or, comptypes considered harmful

[Mike Stump <mrs at apple dot com>]

On Nov 9, 2006, at 1:06 PM, Joern RENNECKE wrote:
> I think in order to handle the C type system with the non-transitive
> type compatibility effectively, for each type we have to pre-compute
> the most general variant, even if that has no direct representative in
> the current program.

The scheme you describe is logically the same as mine, where the  
things I was calling variants are present in the non-most general  
variants bit but not in the most general variant bits.  I think the  
data layout of your scheme is better as then you don't have to do log  
n map lookups to find data, the data are right there and for  
comparison, instead of address equality of the main node, you do  
address equality of the `most general variant'.  In my scheme, I was  
calling that field just the type.

I'm sorry if the others where thinking of that type of scheme, I  
though they weren't.

Now, what are the benefits and weaknesses between mine and your, you  
don't have to carry around type_context the way mine would, that's a  
big win.  You don't have to do anything special move a reference to a  
type around, that's a big win.  You have to do a structural walk if  
there are any bits that are used for type equality.  In my scheme, I  
don't have to.  I just have a vector of items, they are right next to  
each other, in the same cache line.  In your scheme, you have to walk  
all of memory to find them, which is slow.

So, if you want speed, I have a feeling mine is still faster.  If you  
want ease of implementation or conversion yours may be better.