Improve Performance of graph_applyo

[brandonwillard]

Our fixed-point computing relation graph_applyo could be slower than necessary for a subset of problems that don't use its full relational capabilities (e.g. simply finding the unique fixed-point reduction/normal form of a ground term graph).

We could update the relevant relations (or make complementary ones) that take into account the groundedness of their terms and confluence of the rewrite rules. For instance, if the term to be reduced is completely grounded, the reduced term is simply a logic variable (i.e. we're simply asking for the reduction of a ground term graph), and the rules are confluent (or we're willing to assume they are), then we can use a short-circuited cond* and avoid evaluating unnecessary goals—all without necessarily violating relation-ality. Since this is easily our primary use case, it's probably worth the effort.

The first roadblock I see in the approach above involves checking for groundedness. We can always create a relation that assumes as much, but we could also start tracking the logic variables in a meta graph/etuple (and potentially use that info for other things, as well).

Broadly, we could address some more basic performance concerns with tabling and/or memoization, too.

Originally posted by @brandonwillard in #13 (comment)

[brandonwillard]

Looking at the situation in #67, we really do need to memoize/cache subgraph evaluations in graph_applyo—at least for meta graphs, which are necessarily hashable.

The question is: where and what exactly do we cache? My first thought is that we should simply cache miniKanren states (i.e. the logic variable maps), s, in the graph_applyo goal keyed on the tuple (relation, in_graph, out_graph). In general, the relation parameter might not be hashable, but we can probably work around that.
Perhaps the only substantial change (besides a dict lookup and insert) would involve changing the current yield from ... to s_new = yield from ... and a cache[key] = s_new.

With this sort of caching alone (i.e. tabling of some sort), we could dramatically improve the performance of the computations in #67 (e.g. see here) after running grappler's CSE.

[twiecki]

I don't think speed is that important right now as long as the running time is not prohibitive (couple of minutes are fine).

[brandonwillard]

It looks like the changes introduced in #70, #71, and #72 have improved the situation quite a lot, so I'm not as concerned anymore. Nevertheless, I've noticed a few more easy improvements that might speed things up even more.

The most obvious change involves reducing the size of the state dictionary that accumulates due to all the conso "deconstructions" between graph_applyo and its calls to seq_apply_anyo. The result is essentially a dict containing logic variable assignments for every element in a list/graph. In the cases where one of the reified arguments is a ground sequence (i.e. not a logic variable), we can largely bypass all the consos and yield a result immediately. This could also reduce the number of sub-goals that need to be evaluated.

Other, more efficient versions of these goals could also be implemented by actually leveraging the statefulness of their generators. For instance, we could reduce some goal creation overhead that way.

[brandonwillard]

Closing; this situation has been improved by changes in the underlying kanren package. Plus, any additional work in this direction should be directed toward https://github.com/pythological/kanren (unless it involves the meta graph objects explicitly).