I have been playing around with this definition of fib with a colleague: fib n = fibs !! n where fibs = 0 : 1 : zipWith (+) fibs (tail fibs) My initial expectation was that this should take linear time and constant space, but this proved not to be the case: it leaks (a linear amount of) space. We fixed this by replacing (!!) with a version that is strict in the head of its first argument, effectively forcing the list to be strict as far as is needed. With that fix we could quite happily do { print $ fib 1000000 } and all was well, so I tried to write a Criterion benchmark to show that the time taken was linear in n. And the space leak reappeared! Looking at the core, I think what had happened was that GHC had spotted that the inner definition of fibs didn't depend on n and floated it out to the top level so it could be shared between calls. Normally a good move, but in this case it's a disaster as it's much quicker to recalculate the list as needed than to keep it around for next time, for sufficiently large values of n. Now I'm a bit stuck: how do you prevent this from happening? Obviously here we could just implement fibs differently, but as a more general question, how would you prevent unwanted sharing from taking place? Cheers, David
Hi, Am Freitag, den 18.12.2015, 09:40 +0000 schrieb David Turner:
Now I'm a bit stuck: how do you prevent this from happening? Obviously here we could just implement fibs differently, but as a more general question, how would you prevent unwanted sharing from taking place?
floating out (and, relatedly, CSE) is tricky to get a good grip on, and I wish there were good and easy solutions. This also comes up with things like "zip xs [0..]" and gets in the way of applying rules. Note that in your example, depending on the use case, maybe the programmer did want to share the fibs list. So it is not clear that the compiler can always do the right thing. You can pass -fno-full-laziness to GHC (and you can do that with a per- module pragma), this might work in your case, but you better check. Another trick is to add an argument to fibs, e.g. the initial starting values fib n = fibs 0 1 !! n where fibs a b = go where go = a : b : zipWith (+) go (tail go) {-# NOINLINE fibs #-} The noinline pragma might be required as otherwise GHC will simplify the code again to your origin form, and then share the go with a and be specialized to 0 and 1. Again, check the core if it indeed does what you want. Both approaches are unsatisfying. Greetings, Joachim -- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
Hi,
Well at least I hadn't overlooked something obvious!
Some combination of dummy arguments, NOINLINE and -fno-full-laziness did
indeed prevent it from sharing but this definitely seemed unsatisfactory.
Particularly that -fno-full-laziness applies to the whole module which
feels a bit heavyweight.
How feasible would it be to add another pragma like NOINLINE that prevented
exactly this? Is it actually important? This is a toy example of course and
I've not come across this kind of problem in any real code - has anyone
else?
Cheers,
David
On 18 December 2015 at 14:36, Joachim Breitner
Hi,
Am Freitag, den 18.12.2015, 09:40 +0000 schrieb David Turner:
Now I'm a bit stuck: how do you prevent this from happening? Obviously here we could just implement fibs differently, but as a more general question, how would you prevent unwanted sharing from taking place?
floating out (and, relatedly, CSE) is tricky to get a good grip on, and I wish there were good and easy solutions. This also comes up with things like "zip xs [0..]" and gets in the way of applying rules.
Note that in your example, depending on the use case, maybe the programmer did want to share the fibs list. So it is not clear that the compiler can always do the right thing.
You can pass -fno-full-laziness to GHC (and you can do that with a per- module pragma), this might work in your case, but you better check.
Another trick is to add an argument to fibs, e.g. the initial starting values
fib n = fibs 0 1 !! n where fibs a b = go where go = a : b : zipWith (+) go (tail go) {-# NOINLINE fibs #-}
The noinline pragma might be required as otherwise GHC will simplify the code again to your origin form, and then share the go with a and be specialized to 0 and 1. Again, check the core if it indeed does what you want.
Both approaches are unsatisfying.
Greetings, Joachim
-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
On Fri, Dec 18, 2015 at 06:43:10PM +0000, David Turner wrote:
Some combination of dummy arguments, NOINLINE and -fno-full-laziness did indeed prevent it from sharing but this definitely seemed unsatisfactory. Particularly that -fno-full-laziness applies to the whole module which feels a bit heavyweight.
I would be very surprised if -fno-full-laziness did not fix the issue on its own. Do you have a simple example which I can reproduce myself that shows that it doesn't? Tom
You're right, I think. I wasn't being very scientific with my investigation. Though as mentioned, -fno-full-laziness seems like a bit of a sledgehammer. On 18 Dec 2015 18:54, "Tom Ellis" < tom-lists-haskell-cafe-2013@jaguarpaw.co.uk> wrote:
On Fri, Dec 18, 2015 at 06:43:10PM +0000, David Turner wrote:
Some combination of dummy arguments, NOINLINE and -fno-full-laziness did indeed prevent it from sharing but this definitely seemed unsatisfactory. Particularly that -fno-full-laziness applies to the whole module which feels a bit heavyweight.
I would be very surprised if -fno-full-laziness did not fix the issue on its own. Do you have a simple example which I can reproduce myself that shows that it doesn't?
Tom _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
participants (3)
-
David Turner -
Joachim Breitner -
Tom Ellis