tmcdonell
commented
9 years ago I've been working on the simplifier recently, where similar problems happened at the scalar level. That looks to be working pretty well now though, so the ideas should (probably) transfer to the array level (although note that the simplifier is allowed to iterate, whereas the array level is single pass; this might be an issue).
I know what you are trying to do, but it is not a great idea. Consider:
let t = let expensive
in (a, b ..)
in .. (#0 t) .. (#1 t) ..Straightforwardly doing what you proposed above is going to duplicate the expensive part:
let t0 = let expensive in a
t1 = let expensive in b
in .. t0 .. t1 ..You can fix this by lifting out the expensive bit and sharing it, but note now the intermediate program is huge. BOOM. Anyway, eventually you could reduce down to a single spine of lets:
(By the way check the simplifier tick counts and iteration steps, which have increased drastically since the 0.15 branch. I am guessing it is because your changes to the substitution module prevented the rewrite rules, although that is admittedly fragile and shouldn't have been relied upon. Anyway, that's a different ticket on something else we should look at.)
let x = expensive
t0 = a
t1 = bHowever, this is bad because it has implications for memory management. Previously, anything required by the expensive block to compute a and b was only alive in that small scope, but because we pulled it to the top level it is now alive forever. BOOM.
Anyway, yes, this is something that we should look at, but we have to be careful. Your proposed solution technically works, but is bad for various reasons.
The current fusion system doesn't always work very well in the presence of array level tuples. For example:
We have two needlessly manifest arrays here. The current fusion system is not able to see that while
ais referenced twice, each of its components are really only used once, so are able to be embedded and fused.I think the simplest way to solve this, in a lot of cases anyway, is to have a pass before fusion that turns terms of the form
into
i.e.Let bound tuples are expanded into multiple bindings. I'm pretty certain this normal form has a name, but I can't think what it is (anyone know?).
This problem is of particular pain with the vectoriser, where we represent nested arrays as a tuple of segment descriptors and a vector of elements, so lots of stuff that could easily be fused isn't. For this reason, I was going to go ahead and implement this in the streaming branch, but I thought I should check with you @tmcdonell first because you might have had thoughts on this before?
(ping @fmma)