FiniteMap performance WITHOUT any copying?

[Daan Leijen]

> Magnus wrote (snipped)
> > Now, Haskell has a garbage collector, so Haskell must know how many
> > pointers there are to all objects in the heap (or?). Then, if a finite map
> > for example only has one single pointer to it, then it ought to be all
> > right to modify the finite map (or whatever datastructure we are
> 
> 
> In fact I don't think GHC does know how many pointers there are to all objects in the
> heap.  That would only be useful if it did GC by reference-counting, which it doesn't.
> Reference counting is in fact rather expensive; 

A possible solution to this could be one-bit reference counting. With this technique,
every pointer to an item is marked as either a unique pointer or a shared pointer.
Normal GC techniques are used to garbage collect the heap but certain operations
can use the uniqueness information to update-in-place. This kind of reference counting
is cheaper since it involves bit-twiddling on the pointers directly instead of indirect fields.
However, I think that in the end the price may be too high for the benefits obtained.
It may be applicable however to interpreted systems where these register operations come
relatively cheap.

All the best,
    Daan.

ps. The remarkable PhD. thesis of William R. Stoye says more about one-bit reference
counts that he uses in his (hardware) SKI machine. Allthough fairly old (1984) it is still
a very interesting thesis to read. It is especially fun to read how he already describes
very clearly "why functional programming matters", even dwelling on the subject of
functional operating systems.
 _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
> 
>