An example of substituability test that is recursive

forax at forax at
Thu Jan 31 20:12:07 UTC 2019

> De: "John Rose" <john.r.rose at>
> À: "Remi Forax" <forax at>
> Cc: "Karen Kinnear" <karen.kinnear at>, "valhalla-spec-experts"
> <valhalla-spec-experts at>
> 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 | forax at ]
> 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.

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


More information about the valhalla-spec-observers mailing list