Hacker News Reader

Comment by zodiac | Hacker News Reader

It was making a lot of sense until the part about recursive dependencies. To my mind, once this happens it becomes a dependency graph instead of a tree, and instead of trying to satisfy dependencies "locally" I would work out all the constraints and then solve them. The "choose highest, check parent" algorithm seems to me like it would make results depend on which package in a cycle you tried to resolve first, and apparently with peerdependencies it sometimes is incorrect (https://github.com/yarnpkg/yarn/issues/422). Any insight as to why it was designed this way? Just the NP-completeness?

View on HN

I've made some early work on using constraints when I started working on Yarn, but it ended up unpractical because of the sheer execution time it required. A huge number of constraints were required to satisfy the requirements, which was made even worse when you consider that a dependency version might have different sub-dependencies than its other versions.

That being said, I'm not an expert in SAT logic, and it's quite possible a better solution is possible! Maybe some kind of hybrid algorithm, possibly? In fact, one thing I'd really like to do in medium term would be to externalize the resolver part of Yarn - this way, it would be much easier to experiment with it to try to find algorithms that fits various requirements. If you want correctness you would use a slow but comprehensive algorithm, if you want speed you would use a naive algorithm like the one in the article, etc.

Interesting, which packages did you try running it on for which it took too much execution time? Where was most of the time spent?

I unfortunately don't remember - possibly a combo of Babel + Webpack and their plugins, tho, they're usually my go-to choices to test install perfs.

Now that I think about it, it's quite possible that the process was apparently hanging on the same issue I describe in my article, where babel-core depends and babel-cli and vice versa. Maybe it would work better if I were to run the process a first time with a simple algorithm like the one exposed in the article, that would clear up any dependency loop, then a second more complex pass that wouldn't have to deal with this.

Reply on news.ycombinator.com