search

joelberkeley / spidr

Accelerated machine learning with dependent types
Apache License 2.0
73 stars 4 forks source link

Efficient graph caching #367

Closed joelberkeley closed 4 months ago

joelberkeley commented 11 months ago

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 9 months ago

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 9 months ago

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