On Tue, 16 May 2000, Frank Atanassow wrote:
> Markus Mottl writes:

>  > But if you use exceptions, you can "jump back" and can thus prevent the
>  > spine from being copied. This normally reduces the load of the garbage
>  > collector and yields some percent more performance.
> 
> I don't see how this would improve performance. If the element is in the tree,
> you will be copying the spine until you descend to a point where you discover
> the node exists. 

Usually, that is, in the most straightforward implementation, you rebuild
the path on the way up.  By throwing the exception, you don't cons any new
node.

> If you then escape via an exception, the copied nodes will be
> collected. Otherwise (but it depends on your specification, I suppose) the
> functional way would be to just return the subtree(s) intact, so there would
> be no need to copy their spines. Either way, you're generating the same amount
> of garbage.

For this to work, you should either have a low-level pointer equality
operator (present in OCaml, but not in other func. languages), or you
must return a flag to signal whether the returned tree is unchanged.
Both variants are ugly and cumbersome, IMO.


Gxis,
  Pierpaolo