purescript / registry-dev

Development work related to the PureScript Registry
https://github.com/purescript/registry
95 stars 80 forks source link

Fix performance issue in 'allDependencies' #668

Closed thomashoneyman closed 9 months ago

thomashoneyman commented 9 months ago

In #667 I added an implementation to prune unused dependencies from legacy packages. Unfortunately, while the implementation was tested in the small, it was never tested on a package with a sizable graph. On larger packages the inefficiencies in the implementation would cause the process to run out of memory.

This implementation fixes the issue. We switch to ST so we can keep a mutable map around to track modules we've already visited and push all unvisited dependencies to an array for later processing. Once we go through the full pending array without refilling it we're done and can exit.

thomashoneyman commented 9 months ago

Tested on this package run in the API: https://github.com/purescript/registry/issues/410#issuecomment-1802255081

thomashoneyman commented 9 months ago

The major difference is that Spago's implementation is all folds, but I was using bind via the call to traverse. I think this is a reasonable place to use ST — at least the way it's used in the registry, which is a bit different from what Spago is doing — but I can explore a different approach if you aren't happy with the use of ST.

thomashoneyman commented 9 months ago

@f-f could you take another look at this? it's still blocking publishing.

f-f commented 9 months ago

Ah yes sorry I had the tab open and got distracted with other things - my preference is that we keep the lib portable if we can. We explicitely depend on some node libs though, so I guess this is alright as well?

thomashoneyman commented 9 months ago

Yeah, we already explicitly depend on some NPM libraries (ssh2), and Node builtins (the crypto module), so if we were to make the library portable we'd need to move that stuff out altogether and at that time could also replace the ST code. But we'd only need to do any of that if someone came along wanting to use the registry-lib with an alternate backend.

f-f commented 9 months ago

I assume we'll want to use the Scheme backend with Spago (which depends on the registry-lib) once that takes off, but we'll sorry about it then