joelberkeley/spidr

Efficient graph caching

Closed this issue · 2 comments

joelberkeley commented

SortedMap has O(log n) insertion, and who knows what mergeLeft has. Find something suitable. We may need to rethink the algo for building the graph.

Also consider ST for escapable in-place updates

joelberkeley commented

mergeLeft has been removed in #369, so it uses SortedMap about as efficiently as it can. Moving to a linear mutable array may be fairly trivial

joelberkeley commented

note List will do fine for building the graph. We can just reverse once in eval/run. List won't be good for the XlaOp cache though due to O(n) indexing