Equality comparison of DAGs can have exponential complexity

[inducer]

Every time expressions are reused, they are re-traversed, since __eq__ has no mechanism/means to memoize that expressions previously compared equal. (And we probably wouldn't want such a cache on the instance. Or maybe we do? Not sure.) I'm thinking we could introduce an EqualityComparisonMapper that would facilitate such memoization. To avoid having the cat biting its tail, it obviously couldn't use the arrays themselves as hash keys (since that would require equality comparison). But id() is available, and we could back that up with a is b as a check. An (IMO manageably) unfortunate consequence of this would be that we'd have to reimplement equality comparison of all types that can contain Array types, notably dict.

@MTCam is hitting this with cache retrievals upon freeze when exercising lazy evaluation for chemistry in https://github.com/illinois-ceesd/mirgecom.

cc @kaushikcfd

[kaushikcfd]

(And we probably wouldn't want such a cache on the instance.

It's better to not memoize such instances as there will be an equality comparison in accessing the cache dict itself.

I'm taking on implementing the EqualityComparisonMapper, if anyone else is already on it please let me know.

The demand for #160 seems to be growing :).

[inducer]

I'm taking on implementing the EqualityComparisonMapper, if anyone else is already on it please let me know.

Sounds good. (And thanks!) I meant to do it yesterday, but I only got as far as typing up all these issues. I haven't yet started.

[kaushikcfd]

Here's an example for which we can observe the exponential complexity:

def construct_intestine_graph(depth=20, seed=0):
    from numpy.random import default_rng

    rng = default_rng(seed)

    x = pt.make_placeholder("x", shape=(10,), dtype=float)

    for i in range(depth):
        coeff1, coeff2 = rng.integers(0, 10, 2)
        x = coeff1 * x + coeff2 * x

    return x

graph1 = construct_intestine_graph()
graph2 = construct_intestine_graph()

assert graph1 == graph2

The comparison operation is exponential in depth.