An example of substituability test that is recursive

John Rose john.r.rose at
Thu Jan 31 19:43:33 UTC 2019

On Jan 31, 2019, at 10:41 AM, 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

More information about the valhalla-spec-observers mailing list