this post was submitted on 20 Aug 2024
94 points (99.0% liked)

Python

6381 readers
57 users here now

Welcome to the Python community on the programming.dev Lemmy instance!

๐Ÿ“… Events

PastNovember 2023

October 2023

July 2023

August 2023

September 2023

๐Ÿ Python project:
๐Ÿ’“ Python Community:
โœจ Python Ecosystem:
๐ŸŒŒ Fediverse
Communities
Projects
Feeds

founded 1 year ago
MODERATORS
[email protected]
[email protected]
[email protected]
94
uv: Unified Python packaging (astral.sh)
submitted 3 months ago by [email protected] to c/[email protected]
38 comments fedilink hide all child comments
 

TL;DR: uv is an extremely fast Python package manager, written in Rust.

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 9 points 3 months ago (2 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.

[โ€“] [email protected] 8 points 3 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

[โ€“] [email protected] 3 points 3 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

[โ€“] [email protected] 7 points 3 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.

[โ€“] [email protected] 3 points 3 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.