Memoizing results of traversals

[kaushikcfd]

Not memoizing the results of the graph leads to unnecessary traversals. Some of the expression graphs I have consist of only 25% unique subexpressions i.e. paying unnecessarily for many traversals. I was hoping to implement a memorized version of the mappers (with the id as a default cheap cache-key). Some questions I had regarding this:

• Does something like this already exist? (git grep says no)
• Should this be implemented in the base mappers itself? (I'm leaning towards no as memorization wouldn't take into account global state, making it a non-trivial assumption.)

[inducer]

I'm supportive of that idea.

• Nothing of the sort exists.
• What's the lifetime of the caches you are thinking of? (just that of the mapper, or longer? Loopy could hold longer-lived mappers, for those that are used often, if any.)

[kaushikcfd]

Thanks!

What's the lifetime of the caches you are thinking of

I was shooting for id as the cache key, which limits our cache lifetime to the lifetime of the expression being traversed. We could look into WeakKeyDictionary but I think relying structural equality comparisons on pymbolic expression objects could be dubious given #73.

[inducer]

I think relying structural equality comparisons on pymbolic expression objects could be dubious given #73.

There exists #74, but I would tend to agree.

We could look into WeakKeyDictionary

My past experience with that has been that it's shockingly inefficient. That said, that experience comes from the ~Python 2.5 time frame, so a big grain of salt is advised :), although overall Python's refcounting scheme hasn't changed a great deal since then.