5 ms·

See, that's the reason why calling it a SAT solver makes the problem sound scarier than it is. Using Z3--or even MiniSAT--is massive overkill. The naive exponen

See, that's the reason why calling it a SAT solver makes the problem sound scarier than it is. Using Z3--or even MiniSAT--is massive overkill. The naive exponential algorithm is fine, and it leads to more maintainable and understandable code. Rust's build performance has nothing to do with dependency solving. I've never heard of a package manager in which core dependency solving was a speed problem; dep was slow because of I/O, not SAT solving.

Groxx 7y ago
I/O + the absurd lengths you need to go to to (mostly) safely use Git as an external binary + no package repository to globally cache things like package names and versions. yea. "SAT solving" was an incredibly tiny amount of the runtime, like you'd expect for a CPU-bound algorithm. It's a straw man that keeps getting dragged out, but anyone who has used and understood this kind of dependency manager knows it's meaningless. You can definitely argue about its impact on community behavior, but it functions just fine, handles a ton of real-world issues reasonably, and it's nowhere near slow enough to care about.
sansnomme 7y ago
Ask the Python pipenv people. Take a look at their GitHub issues. https://github.com/pypa/pipenv/issues https://github.com/pypa/pipenv/issues Perhaps they need to "rewrite it in Rust" /s Their competitor's isn't much better either when it comes to dependency resolution related bugs. https://github.com/sdispater/poetry/issues https://github.com/sdispater/poetry/issues
- steveklabnik 7y ago
  https://poetry.eustace.io/docs/faq/#why-is-the-dependency-resolution-process-slow https://poetry.eustace.io/docs/faq/#why-is-the-dependency-re... This is due to the fact that not all libraries on PyPI have properly declared their metadata and, as such, they are not available via the PyPI JSON API. At this point, Poetry has no choice but downloading the packages and inspect them to get the necessary information. This is an expensive operation, both in bandwidth and time, which is why it seems this is a long process. https://github.com/pypa/pipenv/issues/2284#issuecomment-395294319 https://github.com/pypa/pipenv/issues/2284#issuecomment-3952... (from 2018, may be outdated) we compute a resolution graph that attempts to satisfy all of the dependencies you specify, before we build your environment. That means we have to start downloading, comparing, and often times even building packages to determine what your environment should ultimately look like, all before we've even begun the actual process of installing it (there are a lot of blog posts on why this is the case in python so I won't go into it more here). ------------------ As I stated in another comment on this thread, Cargo has to do none of this. This stuff is the source of things being slow, not the actual "Okay I have all the versions and constraints, what's the answer" bit.
  - sansnomme 7y ago
    Are there any plans to increase the amount of metadata on e.g PyPy?
    - steveklabnik 7y ago
      I have no idea, I'm not involved in Python in any way.
ainar-g 7y ago
> The naive exponential algorithm is fine (…) Define “fine”. In my experience, Go with modules[1] solves a project's dependencies exponentially more quickly than dep. And that is especially noticeable on big projects with three or more dozens of dependencies. I don't mean any disrespect to the people behind dep, and the whole debacle was a massive miscommunication disaster, but go mod is just quicker. [1] While we're at it, I'm still low-key mad that the Go authors called modules packages and packages modules. Gah!
- pcwalton 7y ago
  Again, that's because of I/O. The CPU bound part of the algorithm is very fast, as Cargo demonstrates.
  - ainar-g 7y ago
    I don't get it. The number of dependencies is constant. Which means that both of them need to make approximately the same amount of network requests. Where does the I/O difference come from then? Also, since you've mentioned Cargo. Its slowness actually used to be one of the main pain points about which the Rust people at one of the companies I've worked for in the past complained a lot during the water cooler discussions. Granted, that was a couple of years ago, and Cargo has probably made progress since then.
    - pcwalton 7y ago
      As I recall, dep had to parse Go code over and over during the dependency resolution process instead of caching it. And any cargo slowness is likely the fault of rustc or I/O. It's received a lot of profiling work and the core dependency solver has never been a performance issue to my knowledge.
      - steveklabnik 7y ago
        It would seem this is correct. From the docs: https://github.com/golang/dep/blob/master/docs/FAQ.md#why-is-dep-slow https://github.com/golang/dep/blob/master/docs/FAQ.md#why-is... There are two things that really slow dep down. One is unavoidable; for the other, we have a plan. The unavoidable part is the initial clone. ... Fortunately, this is just an initial clone - pay it once, and you're done. The other part is the work of retrieving information about dependencies. There are three parts to this: * Getting an up-to-date list of versions from the upstream source * Reading the Gopkg.toml for a particular version out of the local cache * Parsing the tree of packages for import statements at a particular version The first requires one or more network calls; the second two usually mean something like a git checkout, and the third is a filesystem walk, plus loading and parsing .go files. All of these are expensive operations. ---------------- For context, in comparison, Cargo has the same #1 problem. But for #2, the information on all dependencies is stored in the index itself; this means that Cargo can figure out what dependencies you need without any network calls at all, let alone downloading, git checkout, and filesystem walk. I do not know how go mod compares, off the top of my head.
munificent 7y ago
> I've never heard of a package manager in which core dependency solving was a speed problem Natalie Weizenbaum and I wrote the package manager for Dart. My naïve backtracking version solver was fine ~98% of the time. 2% of the time it was catastrophically, exponentially slow. Natalie wrote a much better one to solve exactly that: https://medium.com/@nex3/pubgrub-2fb6470504f https://medium.com/@nex3/pubgrub-2fb6470504f
- pcwalton 7y ago
  That hasn't been our experience with Cargo. It's always been fast. As a colleague of mine pointed out, the lockfile makes the solving a non-issue in practice anyway.
  - steveklabnik 7y ago
    To be clear, Cargo doesn't actually use a SAT solver, it's depth-first search with some heuristics. Without knowing more about how Dart's solver worked, it's hard to directly compare. https://github.com/rust-lang/cargo/blob/368333c20702793477236e393d9e2cfa0de9cd8a/src/cargo/core/resolver/mod.rs https://github.com/rust-lang/cargo/blob/368333c2070279347723...
- littlestymaar 7y ago
  If I correctly understood the post you linked, it looks like there is a big difference between Rust and Dart when it comes to dependency management: Rust allows for different major version of a crate to appear in the dependency tree, while it seems (from the first example given by the post) that Dart doesn't. That difference would dramatically change the difficulty of dependency resolution between the two languages, because there will be many more unsatisfiable cases in Dart than in Rust, leading to much more work to find a working set. (In the given example, cargo would just pick icon:1.0.0 and menu:1.5.0-> dropdown:2.3.0->icon:2.0.0, and call it a day). The exponential search issue could arise if people used explicit upper bound on crate minor of patch versions, but since the number of crate doing that is few far between, there's little change to encounter such a degenerated exponential case in practice.
sacado2 7y ago
> dep was slow because of I/O, not SAT solving. Actually dep tended to produce suboptimal solutions, meaning in some cases it downloaded too many packages to solve dependencies. And that meant more I/O operations than needed. Plugging a full-blown SAT solver would have solved this issue.

Groxx 7y ago

I/O + the absurd lengths you need to go to to (mostly) safely use Git as an external binary + no package repository to globally cache things like package names and versions. yea. "SAT solving" was an incredibly tiny amount of the runtime, like you'd expect for a CPU-bound algorithm. It's a straw man that keeps getting dragged out, but anyone who has used and understood this kind of dependency manager knows it's meaningless. You can definitely argue about its impact on community behavior, but it functions just fine, handles a ton of real-world issues reasonably, and it's nowhere near slow enough to care about.

sansnomme 7y ago

Ask the Python pipenv people. Take a look at their GitHub issues. https://github.com/pypa/pipenv/issues https://github.com/pypa/pipenv/issues Perhaps they need to "rewrite it in Rust" /s Their competitor's isn't much better either when it comes to dependency resolution related bugs. https://github.com/sdispater/poetry/issues https://github.com/sdispater/poetry/issues

steveklabnik 7y ago
https://poetry.eustace.io/docs/faq/#why-is-the-dependency-resolution-process-slow https://poetry.eustace.io/docs/faq/#why-is-the-dependency-re... This is due to the fact that not all libraries on PyPI have properly declared their metadata and, as such, they are not available via the PyPI JSON API. At this point, Poetry has no choice but downloading the packages and inspect them to get the necessary information. This is an expensive operation, both in bandwidth and time, which is why it seems this is a long process. https://github.com/pypa/pipenv/issues/2284#issuecomment-395294319 https://github.com/pypa/pipenv/issues/2284#issuecomment-3952... (from 2018, may be outdated) we compute a resolution graph that attempts to satisfy all of the dependencies you specify, before we build your environment. That means we have to start downloading, comparing, and often times even building packages to determine what your environment should ultimately look like, all before we've even begun the actual process of installing it (there are a lot of blog posts on why this is the case in python so I won't go into it more here). ------------------ As I stated in another comment on this thread, Cargo has to do none of this. This stuff is the source of things being slow, not the actual "Okay I have all the versions and constraints, what's the answer" bit.
- sansnomme 7y ago
  Are there any plans to increase the amount of metadata on e.g PyPy?
  - steveklabnik 7y ago
    I have no idea, I'm not involved in Python in any way.

ainar-g 7y ago

> The naive exponential algorithm is fine (…) Define “fine”. In my experience, Go with modules[1] solves a project's dependencies exponentially more quickly than dep. And that is especially noticeable on big projects with three or more dozens of dependencies. I don't mean any disrespect to the people behind dep, and the whole debacle was a massive miscommunication disaster, but go mod is just quicker. [1] While we're at it, I'm still low-key mad that the Go authors called modules packages and packages modules. Gah!

pcwalton 7y ago
Again, that's because of I/O. The CPU bound part of the algorithm is very fast, as Cargo demonstrates.
- ainar-g 7y ago
  I don't get it. The number of dependencies is constant. Which means that both of them need to make approximately the same amount of network requests. Where does the I/O difference come from then? Also, since you've mentioned Cargo. Its slowness actually used to be one of the main pain points about which the Rust people at one of the companies I've worked for in the past complained a lot during the water cooler discussions. Granted, that was a couple of years ago, and Cargo has probably made progress since then.
  - pcwalton 7y ago
    As I recall, dep had to parse Go code over and over during the dependency resolution process instead of caching it. And any cargo slowness is likely the fault of rustc or I/O. It's received a lot of profiling work and the core dependency solver has never been a performance issue to my knowledge.
    - steveklabnik 7y ago
      It would seem this is correct. From the docs: https://github.com/golang/dep/blob/master/docs/FAQ.md#why-is-dep-slow https://github.com/golang/dep/blob/master/docs/FAQ.md#why-is... There are two things that really slow dep down. One is unavoidable; for the other, we have a plan. The unavoidable part is the initial clone. ... Fortunately, this is just an initial clone - pay it once, and you're done. The other part is the work of retrieving information about dependencies. There are three parts to this: * Getting an up-to-date list of versions from the upstream source * Reading the Gopkg.toml for a particular version out of the local cache * Parsing the tree of packages for import statements at a particular version The first requires one or more network calls; the second two usually mean something like a git checkout, and the third is a filesystem walk, plus loading and parsing .go files. All of these are expensive operations. ---------------- For context, in comparison, Cargo has the same #1 problem. But for #2, the information on all dependencies is stored in the index itself; this means that Cargo can figure out what dependencies you need without any network calls at all, let alone downloading, git checkout, and filesystem walk. I do not know how go mod compares, off the top of my head.

munificent 7y ago

> I've never heard of a package manager in which core dependency solving was a speed problem Natalie Weizenbaum and I wrote the package manager for Dart. My naïve backtracking version solver was fine ~98% of the time. 2% of the time it was catastrophically, exponentially slow. Natalie wrote a much better one to solve exactly that: https://medium.com/@nex3/pubgrub-2fb6470504f https://medium.com/@nex3/pubgrub-2fb6470504f

pcwalton 7y ago
That hasn't been our experience with Cargo. It's always been fast. As a colleague of mine pointed out, the lockfile makes the solving a non-issue in practice anyway.
- steveklabnik 7y ago
  To be clear, Cargo doesn't actually use a SAT solver, it's depth-first search with some heuristics. Without knowing more about how Dart's solver worked, it's hard to directly compare. https://github.com/rust-lang/cargo/blob/368333c20702793477236e393d9e2cfa0de9cd8a/src/cargo/core/resolver/mod.rs https://github.com/rust-lang/cargo/blob/368333c2070279347723...
littlestymaar 7y ago
If I correctly understood the post you linked, it looks like there is a big difference between Rust and Dart when it comes to dependency management: Rust allows for different major version of a crate to appear in the dependency tree, while it seems (from the first example given by the post) that Dart doesn't. That difference would dramatically change the difficulty of dependency resolution between the two languages, because there will be many more unsatisfiable cases in Dart than in Rust, leading to much more work to find a working set. (In the given example, cargo would just pick icon:1.0.0 and menu:1.5.0-> dropdown:2.3.0->icon:2.0.0, and call it a day). The exponential search issue could arise if people used explicit upper bound on crate minor of patch versions, but since the number of crate doing that is few far between, there's little change to encounter such a degenerated exponential case in practice.

sacado2 7y ago

> dep was slow because of I/O, not SAT solving. Actually dep tended to produce suboptimal solutions, meaning in some cases it downloaded too many packages to solve dependencies. And that meant more I/O operations than needed. Plugging a full-blown SAT solver would have solved this issue.