Fix 3 space leaks and refactoring of PositionMapping #557

mpickering · 2020-05-09T14:12:09Z

Please review this commit by commit.

The first three commits are just about fixing space leaks.

The fourth commit is a comment warning about not unfixing the leak.

The fifth commit is a refactoring which makes the correctness of the first commit more obvious but seemed distracting to include in the same commit.

Eta-expanding the function means GHC no longer allocates a function closure every time `withProgress` is called (which is a lot). See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT

Ensure that PositionMappings are shared between versions There was a quadratic space leak as the tails of the position maps were not shared with each other. Now the space usage is linear which is produces more acceptable levels of residency after 3000 modifications.

See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT

pepeiborra

Nice work!

pepeiborra · 2020-05-09T14:17:27Z

src/Development/IDE/Core/PositionMapping.hs

+                (from1 >=> from2)
+
+idDelta :: PositionDelta
+idDelta = PositionDelta Just Just


Why not define Monoid and Semigroup instances for PositionDelta?

It didn't occur to me in particular. I'm a GHC developer so I prefer having explicitly named functions!

Lies. If you were a real GHC developer you'd have used ; { and your commit would have been rendered in comic sans.

pepeiborra · 2020-05-09T14:22:40Z

src/Development/IDE/Core/Shake.hs

 withProgress :: (Eq a, Hashable a) => Var (HMap.HashMap a Int) -> a -> Action b -> Action b
 withProgress var file = actionBracket (f succ) (const $ f pred) . const
-    where f shift = modifyVar_ var $ return . HMap.alter (Just . shift . fromMaybe 0) file
+    where f shift = modifyVar_ var $ \x -> return (HMap.alter (Just . shift . fromMaybe 0) file x)


The linked blog post by @nomeata explains why this can lead to performance gains, but it isn't clear that it fixes a space leak

I profiled a session where I repeatedly modified the file and could observe this function closure growing in the profile. I eta-expanded and the band was no longer present in the profile. So I agree it's not clear why this fixes the leak I don't think it should block merging.

Can we make it evaluate (HMap.alter - I suspect the space leak is removed because GHC manages to optimise a little bit more in some place. The evaluate would mean the operation guarantees to run in the IO monad and not stack up.

pepeiborra · 2020-05-09T14:37:16Z

src/Development/IDE/Core/Shake.hs

-    ,positionMapping :: Var (HMap.HashMap NormalizedUri (Map TextDocumentVersion PositionMapping))
+    ,positionMapping :: Var (HMap.HashMap NormalizedUri (Map TextDocumentVersion (PositionMapping, PositionMapping)))
    -- ^ Map from a text document version to a PositionMapping that describes how to map
    -- positions in a version of that document to positions in the latest version


Unrelated to this change, but is positionMapping ever flushed? It's a space leak that grows with every edit, isn't it?

Yes it grows every edit, I have some thoughts about doing some garbage collection but now the growth is only linear it is not as serious a problem. We don't end up with 1gb of residency just from the position map.

For example, we could remove the whole position map from removing a file from FOI as well as flush out part of the Values map.

Note that we do have some code for this in DAML https://github.com/digital-asset/daml/blob/master/compiler/damlc/daml-ide-core/src/Development/IDE/Core/Rules/Daml.hs#L946

ndmitchell · 2020-05-10T11:40:50Z

src/Development/IDE/Core/Shake.hs

 withProgress :: (Eq a, Hashable a) => Var (HMap.HashMap a Int) -> a -> Action b -> Action b
 withProgress var file = actionBracket (f succ) (const $ f pred) . const
-    where f shift = modifyVar_ var $ \x -> return (HMap.alter (Just . shift . fromMaybe 0) file x)
+    where f shift = modifyVar_ var $ \x -> return (HMap.alter (\x -> Just (shift (fromMaybe 0 x))) file x)


Can we make this Just $! (shift ...). I suspect this does fix the space leak, but by luck rather than guarantee. A $! would be a guarantee.

ndmitchell

Awesome work!

ndmitchell · 2020-05-10T11:42:01Z

src/Development/IDE/Core/Shake.hs

 withProgress var file = actionBracket (f succ) (const $ f pred) . const
+    -- This functions are deliberately eta-expanded to avoid space leaks.
+    -- Do not remove the eta-expansion without profiling a session with at
+    -- least 1000 modifications.


Once we are using $! and evaluate we can hang these comments off more solid guarantees.

ndmitchell · 2020-05-10T11:43:36Z

Could we get a ticket for the "we reduce the space leak from quadratic to linear", since presumably eventually that linear will need fixing too.

cocreature

Looks great! I agree with @ndmitchell that some of the changes would benefit from a bit of evaluate or $!.

cocreature · 2020-05-11T14:21:51Z

src/Development/IDE/Core/Shake.hs

-    ,positionMapping :: Var (HMap.HashMap NormalizedUri (Map TextDocumentVersion PositionMapping))
+    ,positionMapping :: Var (HMap.HashMap NormalizedUri (Map TextDocumentVersion (PositionMapping, PositionMapping)))
    -- ^ Map from a text document version to a PositionMapping that describes how to map
    -- positions in a version of that document to positions in the latest version


Note that we do have some code for this in DAML https://github.com/digital-asset/daml/blob/master/compiler/damlc/daml-ide-core/src/Development/IDE/Core/Rules/Daml.hs#L946

cocreature · 2020-05-11T14:23:49Z

src/Development/IDE/Core/Shake.hs

 withProgress :: (Eq a, Hashable a) => Var (HMap.HashMap a Int) -> a -> Action b -> Action b
 withProgress var file = actionBracket (f succ) (const $ f pred) . const
-    where f shift = modifyVar_ var $ return . HMap.alter (Just . shift . fromMaybe 0) file
+    where f shift = modifyVar_ var $ \x -> return (HMap.alter (Just . shift . fromMaybe 0) file x)


cocreature · 2020-05-11T14:29:09Z

src/Development/IDE/Core/Shake.hs

 withProgress :: (Eq a, Hashable a) => Var (HMap.HashMap a Int) -> a -> Action b -> Action b
 withProgress var file = actionBracket (f succ) (const $ f pred) . const
-    where f shift = modifyVar_ var $ \x -> return (HMap.alter (Just . shift . fromMaybe 0) file x)
+    where f shift = modifyVar_ var $ \x -> return (HMap.alter (\x -> Just (shift (fromMaybe 0 x))) file x)


mpickering · 2020-05-16T10:08:18Z

It may take me a while to get around to making these changes as I will have to profile ghcide again in order to verify the suggestions work correctly.

mpickering · 2020-05-18T09:50:19Z

We are somewhat blocked here because I don't want to spend any more time profiling, when I know these changes fix the leaks, but you don't want to merge because there is a suggestion other ways to fix them would be preferable.

My preference is to merge the patch as-is and make tickets for the other suggested changes which can be picked up by other people. It is unfortunate to just leave these leaks unfixed whilst we are in this impasse. The script I used to profile is in my repo - https://github.com/mpickering/ghcide/blob/hls/test-leak

cocreature · 2020-05-18T10:01:42Z

Sounds sensible, still need to fix the CI errors though before we can merge it.

ndmitchell · 2020-05-18T11:01:03Z

The fixes as written are inherently fragile, relying on subtle compiler invariants, so I suspect they don't fix it on all versions and won't fix it if we breathe on the code funny. However, the points you've identified are clearly space leaks, and based on my history of hunting space leaks I can understand exactly why they are space leaks, and what the robust fix is - which I put in the comment.

My recommendation would be to switch to the robust versions, which I'd give a 90%+ probability of fixing now and continuing to fix in the future. If you're not happy with doing that in this patch I suggest I follow up with the changes I identified, but non-space-leak tested, and we merge that. I agree that retesting would be ideal, but without a CI infrastructure that spots these leaks robustly, we're somewhat flying blind and hopeful anyway, so I think anything we do is not ideal.

A Delta is a change between two versions A Mapping is a change from the current version to a specific older version. Fix hlint Fix hlint

cocreature · 2020-05-22T09:02:22Z

Happy to merge the more robust fixes separately.

Follow up from haskell#557. We definitely want the progress state to be fully evaluated, so demand that with evaluating functions like evaluate and $!, rather than relying on the compiler to get it right. My guess is the `$!` is unnecessary now we have `evaluate`, but it's also not harmful, so belt and braces approach.

Follow up from #557. We definitely want the progress state to be fully evaluated, so demand that with evaluating functions like evaluate and $!, rather than relying on the compiler to get it right. My guess is the `$!` is unnecessary now we have `evaluate`, but it's also not harmful, so belt and braces approach.

) * Rats: Fix space leak in withProgress Eta-expanding the function means GHC no longer allocates a function closure every time `withProgress` is called (which is a lot). See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Rats: Share computation of position mapping Ensure that PositionMappings are shared between versions There was a quadratic space leak as the tails of the position maps were not shared with each other. Now the space usage is linear which is produces more acceptable levels of residency after 3000 modifications. * Rats: Eta-expand modification function See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Add a comment warning about eta-reducing * Distinguish between a Delta and a Mapping in PositionMapping A Delta is a change between two versions A Mapping is a change from the current version to a specific older version. Fix hlint Fix hlint

Follow up from haskell/ghcide#557. We definitely want the progress state to be fully evaluated, so demand that with evaluating functions like evaluate and $!, rather than relying on the compiler to get it right. My guess is the `$!` is unnecessary now we have `evaluate`, but it's also not harmful, so belt and braces approach.

) * Rats: Fix space leak in withProgress Eta-expanding the function means GHC no longer allocates a function closure every time `withProgress` is called (which is a lot). See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Rats: Share computation of position mapping Ensure that PositionMappings are shared between versions There was a quadratic space leak as the tails of the position maps were not shared with each other. Now the space usage is linear which is produces more acceptable levels of residency after 3000 modifications. * Rats: Eta-expand modification function See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Add a comment warning about eta-reducing * Distinguish between a Delta and a Mapping in PositionMapping A Delta is a change between two versions A Mapping is a change from the current version to a specific older version. Fix hlint Fix hlint

Follow up from haskell/ghcide#557. We definitely want the progress state to be fully evaluated, so demand that with evaluating functions like evaluate and $!, rather than relying on the compiler to get it right. My guess is the `$!` is unnecessary now we have `evaluate`, but it's also not harmful, so belt and braces approach.

) * Rats: Fix space leak in withProgress Eta-expanding the function means GHC no longer allocates a function closure every time `withProgress` is called (which is a lot). See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Rats: Share computation of position mapping Ensure that PositionMappings are shared between versions There was a quadratic space leak as the tails of the position maps were not shared with each other. Now the space usage is linear which is produces more acceptable levels of residency after 3000 modifications. * Rats: Eta-expand modification function See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT * Add a comment warning about eta-reducing * Distinguish between a Delta and a Mapping in PositionMapping A Delta is a change between two versions A Mapping is a change from the current version to a specific older version. Fix hlint Fix hlint

Follow up from haskell/ghcide#557. We definitely want the progress state to be fully evaluated, so demand that with evaluating functions like evaluate and $!, rather than relying on the compiler to get it right. My guess is the `$!` is unnecessary now we have `evaluate`, but it's also not harmful, so belt and braces approach.

mpickering added 4 commits May 9, 2020 15:03

Rats: Fix space leak in withProgress

4a24c38

Eta-expanding the function means GHC no longer allocates a function closure every time `withProgress` is called (which is a lot). See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT

Rats: Eta-expand modification function

cdcbba1

See: https://www.joachim-breitner.de/blog/763-Faster_Winter_5__Eta-Expanding_ReaderT

Add a comment warning about eta-reducing

9cbd9c0

pepeiborra approved these changes May 9, 2020

View reviewed changes

ndmitchell reviewed May 10, 2020

View reviewed changes

cocreature approved these changes May 11, 2020

View reviewed changes

Distinguish between a Delta and a Mapping in PositionMapping

36a5940

A Delta is a change between two versions A Mapping is a change from the current version to a specific older version. Fix hlint Fix hlint

mpickering force-pushed the wip/space-leaks branch from b09b620 to 36a5940 Compare May 20, 2020 07:54

cocreature merged commit 126e398 into haskell:master May 22, 2020

ndmitchell mentioned this pull request May 22, 2020

Remove space leaks in a more robust way #578

Merged

Fix 3 space leaks and refactoring of PositionMapping #557

Fix 3 space leaks and refactoring of PositionMapping #557

Uh oh!

Conversation

mpickering commented May 9, 2020

Uh oh!

pepeiborra left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ndmitchell left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ndmitchell commented May 10, 2020

Uh oh!

cocreature left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mpickering commented May 16, 2020

Uh oh!

mpickering commented May 18, 2020

Uh oh!

cocreature commented May 18, 2020

Uh oh!

ndmitchell commented May 18, 2020

Uh oh!

cocreature commented May 22, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants