[Haskell-cafe] Can't Haskell catch up with Clean's uniqueness typing?

[Jan-Willem Maessen]

On Dec 6, 2005, at 9:17 AM, haskell-cafe.mail.zooloo at xoxy.net wrote:

> Hi all,
>
> being occupied with learning both languages, I'm getting curious if  
> Haskell couldn't achieve most of the performance gains
> resulting from uniqueness typing in Clean by *automatically*  
> determining the reference count of arguments wherever
> possible and subsequently allowing them to be physically replaced  
> immediately by (the corresponding part of) the
> function's result. Are there any principal obstacles, or *could*  
> this be done, or *is* this even done already, e. g. in
> ghc?

Yes, this could be done.  The principle obstacles are the same as for  
any reference counting scheme: It imposes more run-time overhead than  
GC does, unless the data structures involved are large.  Let me  
repeat that: accurate up-to-the-moment reference counting is  
dramatically slower than GC.  Techniques exist to make ref counting  
fast, but they all require the equivalent of a full stack walk in  
order to get an accurate count.

That said, clever techniques (like 1-bit ref counting) are available  
that will get 80% of what is desired.  1-bit reference counting keeps  
a single bit which says either "this is certainly the only reference"  
or "other references may exist".  The bit can be kept in the pointer  
itself.  There's still run-time overhead, though---the bit must be  
masked on each pointer dereference.

Wearing my "Fortress language designer" hat, we've given serious  
thought to these techniques for very large arrays.  Copying such  
structures is terribly expensive, or even impossible (imagine copying  
a 1PB array).  I'd think hard before I used them for, say, cons cells.

Shae: All this is very, very different from eager / optimistic  
evaluation.

-Jan-Willem Maessen