Hacker News Reader

Comment by formerly_proven | Hacker News Reader

> Something else that I think about a lot: the industry spends a lot of CPU cycles to compute the suitable dependencies, but there are several alternative ways to solve dependencies. But those alternatives don't generate interest because the StopAlop lineage is so built in to how we work on software it almost goes unnoticed as a natural law of the world like gravity, so there's no prompt to directly challenge it.

If I recall correctly, Composer uses a SAT solver to do this, resulting in absurd amounts of CPU and memory time needed to create lockfiles in some situations. Dunno if they still do that.

View on HN

What are "absurd" amounts of CPU and memory? Calculating and pinning dependencies is just a very difficult problem which happens to be reducible to SAT. If you think a SAT solver takes a lot of time and memory, then all alternatives would probably be even slower.

Dependency solvers that obey semver are a really hard problem that have very unintuitive challenges. I think a very large number of people who use them will not have spent a lot of time to think about the issues in detail, just their experiences as a user of them. NPM has less complaints than composer for example, but node_modules has an interesting way out of the problem by making dependencies into a hierarchy but this brings a new bunch of challenges elsewhere (in the runtime, any object transiting between a mutual package which has two different package versions of the same package name in the lineage will be have "weird" behaviour).

  Your Project --depends-on-> Foo@1.2.3 --depends-on-> SomeLib@1.2.3
  Your Project --depends-on-> Bar@4.0.1 --depends-on-> SomeLib@4.5.6

If Your Project touches SomeLib from Bar and passes it into Foo things go sideways. It's easy to state that this violates best practices but it is a reality of how the runtime works. This category of issue is removed in PHP/Python by the package manager (not the language). The trade-off is the large computation that checks for conflicts in SomeLib.

> Dependency solvers that obey semver are a really hard problem that have very unintuitive challenges

throw in platform specific binary packages for which platform triplets can be wildcarded plus dependencies that may vary across these platforms plus specifying package sources for which dependencies may be on another source and you're in for a crazy world of hurt (well, at least I am, given I found some issues in bundler+rubygems and have been trying to solve them upstream for a couple of years)

Anything over "basically none" is absurd, but in this case the worst case really is very bad.

How would you solve it with very little computing resources? I've yet to see any reasonable solution.

There's a few novel techniques such as minimal version selection: https://research.swtch.com/vgo-mvs. I know I've seen a few others in the past years but I'm struggling to remember which ones are non-SAT solving approaches.

They recently updated the algo to handle better performance but I don't know what it is now. Top-of-mind I think it was a 30% wall-time improvement.

I wish those people would work on emerge.

Reply on news.ycombinator.com