uv is fantastic. I would highly recommend it. I've used it in a quite complex environment, with no issues (quite an achievement!) and it's about 10x faster than pip.

I mean... I guess it's not surprising given uv is written in Rust and pip is written in Python, but even so given pip is surely IO bound I was expecting something like 4x improvement. 10x is impressive.

[–] [email protected] 9 points 4 months ago (4 children)

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

load more comments (3 replies)