runarorama
commented
12 years ago That's no good. Any insight into why this might be happening?
Closed seanparsons closed 12 years ago
runarorama
commented
12 years ago That's no good. Any insight into why this might be happening?
seanparsons
commented
12 years ago Trying this on another machine I don't see the heap space issue (that puzzles me), it looks a bit like all the instances of Emit are held in memory until the computation completes. I'll hold my hands up to say I don't quite understand the underlying library enough to be able to diagnose why that should be.
ekmett
commented
12 years ago I would expect it to be the other way around. It should only demand its input when its needed by the downstream.
seanparsons
commented
12 years ago What I'm staring at at the moment is 10,499,976 instances of com.clarifi.machines.Emit and 10,499,975 instances of com.clarifi.machines.Emit$$anonfun$flatMap$1 in VisualVM from a heap dump I just took. Given the way it grows linearly in the number of both of those, that would imply they're being held in a massive chain until completion when the root becomes available for GC.
ekmett
commented
12 years ago Hrmm, then I think something was broken in the port from Haskell. =/
I wouldn't expect the Emits to backlog like that. If nothing else I'll take a look with @runarorama when we get into the office tomorrow!
seanparsons
commented
12 years ago Just confirmed it with the Eclipse Memory Analyzer, those two types end up with references to each other on the heap in a long chain that goes A -> B -> A -> B -> A -> B -> A -> B -> A...
runarorama
commented
12 years ago Looks like we need to hit this thing with some codensity (i.e. trampolining).
On Mon, Sep 3, 2012 at 7:45 PM, Sean Parsons notifications@github.comwrote:
Just confirmed it with the Eclipse Memory Analyzer, those two types end up with references to each other on the heap in a long chain that goes A -> B -> A -> B -> A -> B -> A -> B -> A...
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8249221.
ekmett
commented
12 years ago This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
runarorama
commented
12 years ago We'll have to either reify our flatMaps on the heap or compile plans to a tail-recursive Machine representation.
On Mon, Sep 3, 2012 at 9:00 PM, Edward A. Kmett notifications@github.comwrote:
This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8249950.
dolio
commented
12 years ago None of the pieces of the example appear to have large left-nested sequences of flatMaps, so blaming the lack of CPS doesn't make much sense to me.
It's probably just Scala using more stack than is necessary, which has no real analogue in a proper Haskell implementation. You could use algebraic Plans in Haskell and probably have no problem with this example.
On Mon, Sep 3, 2012 at 9:00 PM, Edward A. Kmett notifications@github.comwrote:
This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8249950.
runarorama
commented
12 years ago The machine is running out of heap, not stack.
On Mon, Sep 3, 2012 at 11:26 PM, dolio notifications@github.com wrote:
None of the pieces of the example appear to have large left-nested sequences of flatMaps, so blaming the lack of CPS doesn't make much sense to me.
It's probably just Scala using more stack than is necessary, which has no real analogue in a proper Haskell implementation. You could use algebraic Plans in Haskell and probably have no problem with this example.
On Mon, Sep 3, 2012 at 9:00 PM, Edward A. Kmett notifications@github.comwrote:
This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
— Reply to this email directly or view it on GitHub< https://github.com/runarorama/scala-machines/issues/2#issuecomment-8249950>.
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8251533.
dolio
commented
12 years ago Actually, is the problem the val in the procedure? It holds on to the root of the machine. And the combinators don't (can't easily) preserve a nice finite memory representation of the machines, so the machine we're storing probably just grows linearly. So we're forcing a huge structure into memory by running the machine, and it can't be collected until the procedure is, which won't happen until it's done executing (presumably).
You probably wouldn't have this problem in Haskell because an execute function wouldn't be a member of an object that keeps a pointer to the original machine, so it might be more nicely collectable (not that the machines package has an analogue to our procedures).
On Mon, Sep 3, 2012 at 11:28 PM, Rúnar notifications@github.com wrote:
The machine is running out of heap, not stack.
On Mon, Sep 3, 2012 at 11:26 PM, dolio notifications@github.com wrote:
None of the pieces of the example appear to have large left-nested sequences of flatMaps, so blaming the lack of CPS doesn't make much sense to me.
It's probably just Scala using more stack than is necessary, which has no real analogue in a proper Haskell implementation. You could use algebraic Plans in Haskell and probably have no problem with this example.
On Mon, Sep 3, 2012 at 9:00 PM, Edward A. Kmett < notifications@github.com>wrote:
This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
— Reply to this email directly or view it on GitHub<
https://github.com/runarorama/scala-machines/issues/2#issuecomment-8249950>.
— Reply to this email directly or view it on GitHub< https://github.com/runarorama/scala-machines/issues/2#issuecomment-8251533>.
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8251560.
runarorama
commented
12 years ago Hah! Isn't the solution just an aux function, then? Or not trying to memoize the value at all, I suppose.
On Tue, Sep 4, 2012 at 12:07 AM, dolio notifications@github.com wrote:
Actually, is the problem the val in the procedure? It holds on to the root of the machine. And the combinators don't (can't easily) preserve a nice finite memory representation of the machines, so the machine we're storing probably just grows linearly. So we're forcing a huge structure into memory by running the machine, and it can't be collected until the procedure is, which won't happen until it's done executing (presumably).
You probably wouldn't have this problem in Haskell because an execute function wouldn't be a member of an object that keeps a pointer to the original machine, so it might be more nicely collectable (not that the machines package has an analogue to our procedures).
On Mon, Sep 3, 2012 at 11:28 PM, Rúnar notifications@github.com wrote:
The machine is running out of heap, not stack.
On Mon, Sep 3, 2012 at 11:26 PM, dolio notifications@github.com wrote:
None of the pieces of the example appear to have large left-nested sequences of flatMaps, so blaming the lack of CPS doesn't make much sense to me.
It's probably just Scala using more stack than is necessary, which has no real analogue in a proper Haskell implementation. You could use algebraic Plans in Haskell and probably have no problem with this example.
On Mon, Sep 3, 2012 at 9:00 PM, Edward A. Kmett < notifications@github.com>wrote:
This would appear to be a consequence of the fact that the scala-machines code is uncps'ed, while the haskell code is. Codensity or trampolining it should fix it. It may introduce other overhead in the head pattern match though. This is one reason why the haskell version keeps plans and machines separate.
Plans being cps'd can flatMap quickly, while machines being direct can interpret quickly. CPSing will at least fix the flatMap issues, but i don't have a deep asymptotic insight into the impact on pattern matching here.
— Reply to this email directly or view it on GitHub<
https://github.com/runarorama/scala-machines/issues/2#issuecomment-8249950>.
— Reply to this email directly or view it on GitHub<
https://github.com/runarorama/scala-machines/issues/2#issuecomment-8251533>.
— Reply to this email directly or view it on GitHub< https://github.com/runarorama/scala-machines/issues/2#issuecomment-8251560>.
— Reply to this email directly or view it on GitHubhttps://github.com/runarorama/scala-machines/issues/2#issuecomment-8252018.
ekmett
commented
12 years ago That makes sense. You'll still have the asymptotic slowdown on flatmapping long plans, but it doesn't look like the problem is anything like what can happen in the Haskell version. ;)
dolio
commented
12 years ago I pushed some code that copies everything I thought was bad from Procedure, but uses an imperative loop to execute instead of using IO. It seems to work fine that way (it's also faster). So the bug has something to do with executing with IO (and maybe other monads), not anything to do with the machine implementation, it seems.
seanparsons
commented
12 years ago I just tried the latest cut and it works a treat, it was pretty snappy and doesn't eat memory.
runarorama
commented
12 years ago I have opened a "monadic" branch with monadic drivers that don't leak.
ekmett
commented
12 years ago Go Runar!
I've not had a chance to investigate in detail, but if I push (War and Peace)[http://www.gutenberg.org/cache/epub/2600/pg2600.txt] through Example.lineWordCount twice in succession I get the following occur: