An example of substituability test that is recursive

[forax at univ-mlv.fr]

> De: "John Rose" <john.r.rose at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "Karen Kinnear" <karen.kinnear at oracle.com>, "valhalla-spec-experts"
> <valhalla-spec-experts at openjdk.java.net>
> Envoyé: Jeudi 31 Janvier 2019 20:43:33
> Objet: Re: An example of substituability test that is recursive

> On Jan 31, 2019, at 10:41 AM, [ mailto:forax at univ-mlv.fr | forax at univ-mlv.fr ]
> wrote:

>> yes, i creates a DAG that will be too long to traverse :(
>> you basically, DDOS yourself if you do a ==.

> The complexity is exponential in depth, and
> can be more than linear in heap allocation,
> because of the risk of repeat traversals.

> A worklist algorithm could make use of the
> secret implementation identity of heap nodes
> to push the complexity back down to heap
> allocation size. A portable algorithm could
> not. This is one more bit of evidence it should
> be a system intrinsic rather than a vanilla library
> function.

yes, 
i buy that ! 
it will be always more expensive in Java, 

Rémi