haskell / haskell-language-server

Official haskell ide support via language server (LSP). Successor of ghcide & haskell-ide-engine.
Apache License 2.0
2.61k stars 351 forks source link

Fix quadratic memory usage in GetLocatedImports #4318

Closed mpickering closed 1 week ago

mpickering commented 1 week ago

At startup GetLocatedImports is called on all known files. Say you have 10000 modules in your project then this leads to 10000 calls to GetLocatedImports running concurrently.

In GetLocatedImports the known targets are consulted and the targetsMap is created by mapping the known targets. This map is used for introducing sharing amongst filepaths. This operation copies a local copy of the target map which is local to the rule.

let targetsMap = HMap.mapWithKey const targets

So now each rule has a hashmap of size 10000 held locally to it and depending on how the threads are scheduled there will be 10000^2 elements in total allocated in hashmaps. This used a lot of memory.

Solution: Return the normalising map in the result of the GetKnownTargets rule so it is shared across threads.

Fixes #4317

michaelpj commented 1 week ago

Please write down this subtle reasoning in the code! Otherwise we will be unlikely to retain this property over time.

fendor commented 1 week ago

I added the comment to the documentation of 'normalisingMap'.