horde-ad icon indicating copy to clipboard operation
horde-ad copied to clipboard

Add a sharing mechanism to Ast terms

Open Mikolaj opened this issue 1 year ago • 33 comments

I'm now leaning towards replicating the trick we have in Delta terms (Tom's Tree0 method --- a stamp per each term node). Then we could add the same stamp to the Delta expressions created from Ast terms.

There are benefits. The user doesn't have to worry and let from Haskell implies this permanent sharing (not only temporary sharing in memory). We get stamps in fewer Delta terms, which does not incur a risk of sharing violation as long as interpretation of Ast terms don't duplicate newly created Delta terms (but it can duplicate delta terms that will be received from interpreted Ast subterms).

There are some drawbacks . We get many stamps in Ast terms: one stamp per Ast node. The implementation of interpretation of Ast in Tensor can't just have one extra case for AstLet, but instead needs to keep a table of interpreted subterms. Moreover, interpretation in an ADVal instance of Tensor has to pass on the stamps, so maybe this interpretation can't share code with all the others. I haven't thought through Vectorization nor Simplification, but given that they can incur duplication, we can't introduce sharing after they are complete. So they probably need to keep tables as well. I'm not sure if we can get away with stamps only in tensor terms, given that integer terms suffer from blowup when gathers are fused and consequently large terms are substituted for integer variables.

Mikolaj avatar Mar 27 '23 20:03 Mikolaj