The actual dependency resolution part, so where you figure out which versions of the dependencies can be used together, is actually notoriously CPU-bound.

At least as far as I'm aware, you generally use a SAT solver for dependency resolution (unless you don't care for correctness), and as Wikipedia puts it:

Boolean satisfiability is an NP-complete problem in general. As a result, only algorithms with exponential worst-case complexity are known.

There are quite sophisticated algorithms at this point, making use of heuristics and whatnot, but they're still just backtracking algorithms at their core. And as Wikipedia puts it so fittingly again:

backtracking is often much faster than brute-force enumeration

You know shit's inefficient, when the best thing to compare it to, is just randomly trying solutions.

[–] burntsushi 8 points 4 months ago

Interestingly, dependency resolution is not the only NP hard problem uv tries to solve. During development, it also became clear that we needed some way to simplify PEP 508 marker expressions and ask questions like, "are these marker expressions disjoint?"

See: https://github.com/astral-sh/uv/blob/72bd12716225ae48d1e46ec6254d7daf134bdc94/crates/pep508-rs/src/marker/algebra.rs

[–] FizzyOrange 3 points 4 months ago (1 children)

you generally use a SAT solver for dependency resolution (unless you don’t care for correctness)

Actually Go's dependency system is specifically designed to avoid the need for global constraint solvers. Go has the most modern and elegant dependency versioning system that I'm aware of. Python was designed before people realised that it's dependency style was a mistake.

https://research.swtch.com/vgo-principles

[–] burntsushi 7 points 4 months ago (1 children)

I'm on the uv team. I am quite partial to this approach as well. Alas, it's difficult culturally to pull this off in a pre-existing ecosystem. And in the case of Python at least, it's not totally clear to me that it would avoid the need for solving NP hard problems. See my other comment in this thread about simplifying PEP 508 marker expressions.

Other than avoiding needing a SAT solver to resolve dependencies, the other thing I like about Go's approach is that it makes it very difficult to "lie" about the dependencies you support. In a maximal environment, it's very easy to "depend" on foo 1.0 but where you actually need foo 1.1 without issues appearing immediately.

[–] FizzyOrange 3 points 4 months ago

Oo hello. Didn't know that's what you were doing these days! Hope it goes well, though I'd be nervous about a realistic business plan.

Anyway, yeah bit too late for Python.