Memoizing results of traversals

inducer / pymbolic

A simple package to do symbolic math (focus on code gen and DSLs)

http://mathema.tician.de/software/pymbolic

Other

106 stars 25 forks source link

Memoizing results of traversals #89

Closed kaushikcfd closed 2 years ago

kaushikcfd commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

I think relying structural equality comparisons on pymbolic expression objects could be dubious given https://github.com/inducer/pymbolic/issues/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.