12 ms·

Nah, it's totally novel -- it's a viable packaging system that isn't NP-hard. Is there any precedent for that? It's also likely, in practical terms, to feel ve

by dilap 9y ago

Nah, it's totally novel -- it's a viable packaging system that isn't NP-hard. Is there any precedent for that? It's also likely, in practical terms, to feel very different to work with than any existing packaging system. My money is on it becoming quite popular. It just feels like it's been sprinkled w/ the Go magic -- deceptively simple ideas that end up working really well.

kibwen 9y ago
> it's a viable packaging system that isn't NP-hard. Is there any precedent for that? Yes, Rust's Cargo: see https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/core/resolver/mod.rs#L9-L36 https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/cor... For demonstration, on my low-end VPS Cargo takes less than a quarter second to select the versions of the 289 transitive dependencies used by Servo (could be much less, but I don't have a precise measurement; `time cargo update` takes 1.22 seconds but this is dominated by the network calls checking for a new version of the crates.io index and checking for new versions of Servo's custom deps on Github). The fact that the algorithm in the OP isn't NP-hard isn't anything worth getting excited about. The only advantage I can see is that it gives a measure of reproducibility without the need for lockfiles--though builds will still be less reproducible than they'd be with lockfiles.
- bradfitz 9y ago
  > > it's a viable packaging system that isn't NP-hard. Is there any precedent for that? > Yes, Rust's Cargo: https://github.com/rust-lang/cargo/blob/master/src/cargo/cor.. https://github.com/rust-lang/cargo/blob/master/src/cargo/cor.... For comparison, on my low-end VPS Cargo takes less than a quarter second to select the versions of the 289 transitive dependencies used by Servo That's kinda an answer to a different question. The question you replied to was asking about other non-NP-hard systems and you replied with how much time your system took.
  - kibwen 9y ago
    If you take a moment to read the linked comment, you will see that it describes how Cargo's selection algorithm is a simple heuristic that avoids NP-hardness. The subsequent timing example exists to demonstrate that the heuristic actually succeeds at avoiding pathological performance; Servo has more transitive dependencies than any known Rust project, and your development box is certainly more powerful than my $5 VPS.
    - bradfitz 9y ago
      Ah, sorry, I didn't realize you were linking to a comment. I read that was a link to Cargo itself.
- TheDong 9y ago
  Please link to a tag of the repository, not master, or else the docs may shift out from under you. https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/core/resolver/mod.rs#L9-L36 https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/cor...
  - kibwen 9y ago
    Yes, I always forget to do this. :)
- dilap 9y ago
  Sorry, nope. For your link: > Actually solving a constraint graph is an NP-hard problem. This algorithm is basically a nice heuristic to make sure we get roughly the best answer most of the time. That's miles away from the simple, linear time algorithm proposed here. Maybe it doesn't matter (though I suspect we'll discover it does), but that's not what you were arguing.
  - pcwalton 9y ago
    Why do you suspect it does? Cargo has gotten tons of use and the speed of the dependency resolution process has, to my knowledge, never been a problem. Besides, I suspect that if you restrict your Cargo graphs to use only the features that this Go proposal supports (minimal version pinning, in particular), then the algorithm is no longer NP-hard. There's no "Go magic" here: it's that just Go chooses not to implement features that could theoretically be slow (but aren't slow in practice).
    - dilap 9y ago
      No good reason, really :-) -- just a gut feeling/bias that when problems move from "tricky" to "easy", people end up creating new/unexpected tooling as a result, just because it's easier. Might well be totally irrelevant here. Sadly I don't know Rust (yet!), but Cargo certainly seems widely loved and admired. Perusing the resolver code was pleasant, and impressive. We've come a long way from when you'd pull back the covers on a C++ std library or (god help you) boost, and run away screaming in terror. The future is bright!
  - kibwen 9y ago
    Your condescension here is amusing. My good friend, please feel free to explain in more detail how the algorithm described in the aforementioned link is miles away from the algorithm in the OP. Feel free to also explain your fascination with linear time algorithms, considering that the nonlinear algorithm in question is demonstrably instantaneous for extreme real-world workloads (Go is supposed to be about pragmatism, I hear?). Lastly, feel free to lecture me further on how a you suspect that an algorithm that has been deployed and used, to overwhelming acclaim, by tens of thousands of programmers over the past three years will be found wanting in comparison to an algorithm that has existed on paper for two days, with no ecosystem or real-world experience to its name. :)
sagichmal 9y ago
The lack of a solver is predicated on the minimal version decision as well as insisting that breaking changes are reflected in dependency identifiers. These decisions are points on their respective spectrums that other package managers have considered and rejected, because they impose (optimistically) novel or (pessimisticly) burdensome requirements on package authors and consumers. Namely, that we bias toward stable (unchanging) builds, even when security or bugfix releases may be safely applied; and that we force authors toward uncommon and arguably awkward naming decisions when making breaking changes, essentially shifting work from computers to humans. Again, these things aren’t novel; in isolation, they’ve been considered (and rejected) by other package managers. Maybe they compose to something greater than the sum of their parts. At the moment, it’s unclear, and it mostly looks messy.
- ngrilly 9y ago
  What makes you think this design was considered by other package managers (npm, yarn, pip, bundler, cargo, etc.) in the past? Is it documented somewhere?
  - sagichmal 9y ago
    I'm basing this on documented albeit informal conversations with other package manager builders and maintainers.

by dilap 9y ago

kibwen 9y ago

> it's a viable packaging system that isn't NP-hard. Is there any precedent for that? Yes, Rust's Cargo: see https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/core/resolver/mod.rs#L9-L36 https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/cor... For demonstration, on my low-end VPS Cargo takes less than a quarter second to select the versions of the 289 transitive dependencies used by Servo (could be much less, but I don't have a precise measurement; `time cargo update` takes 1.22 seconds but this is dominated by the network calls checking for a new version of the crates.io index and checking for new versions of Servo's custom deps on Github). The fact that the algorithm in the OP isn't NP-hard isn't anything worth getting excited about. The only advantage I can see is that it gives a measure of reproducibility without the need for lockfiles--though builds will still be less reproducible than they'd be with lockfiles.

bradfitz 9y ago
> > it's a viable packaging system that isn't NP-hard. Is there any precedent for that? > Yes, Rust's Cargo: https://github.com/rust-lang/cargo/blob/master/src/cargo/cor.. https://github.com/rust-lang/cargo/blob/master/src/cargo/cor.... For comparison, on my low-end VPS Cargo takes less than a quarter second to select the versions of the 289 transitive dependencies used by Servo That's kinda an answer to a different question. The question you replied to was asking about other non-NP-hard systems and you replied with how much time your system took.
- kibwen 9y ago
  If you take a moment to read the linked comment, you will see that it describes how Cargo's selection algorithm is a simple heuristic that avoids NP-hardness. The subsequent timing example exists to demonstrate that the heuristic actually succeeds at avoiding pathological performance; Servo has more transitive dependencies than any known Rust project, and your development box is certainly more powerful than my $5 VPS.
  - bradfitz 9y ago
    Ah, sorry, I didn't realize you were linking to a comment. I read that was a link to Cargo itself.
TheDong 9y ago
Please link to a tag of the repository, not master, or else the docs may shift out from under you. https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/core/resolver/mod.rs#L9-L36 https://github.com/rust-lang/cargo/blob/0.25.0/src/cargo/cor...
- kibwen 9y ago
  Yes, I always forget to do this. :)
dilap 9y ago
Sorry, nope. For your link: > Actually solving a constraint graph is an NP-hard problem. This algorithm is basically a nice heuristic to make sure we get roughly the best answer most of the time. That's miles away from the simple, linear time algorithm proposed here. Maybe it doesn't matter (though I suspect we'll discover it does), but that's not what you were arguing.
- pcwalton 9y ago
  Why do you suspect it does? Cargo has gotten tons of use and the speed of the dependency resolution process has, to my knowledge, never been a problem. Besides, I suspect that if you restrict your Cargo graphs to use only the features that this Go proposal supports (minimal version pinning, in particular), then the algorithm is no longer NP-hard. There's no "Go magic" here: it's that just Go chooses not to implement features that could theoretically be slow (but aren't slow in practice).
  - dilap 9y ago
    No good reason, really :-) -- just a gut feeling/bias that when problems move from "tricky" to "easy", people end up creating new/unexpected tooling as a result, just because it's easier. Might well be totally irrelevant here. Sadly I don't know Rust (yet!), but Cargo certainly seems widely loved and admired. Perusing the resolver code was pleasant, and impressive. We've come a long way from when you'd pull back the covers on a C++ std library or (god help you) boost, and run away screaming in terror. The future is bright!
- kibwen 9y ago
  Your condescension here is amusing. My good friend, please feel free to explain in more detail how the algorithm described in the aforementioned link is miles away from the algorithm in the OP. Feel free to also explain your fascination with linear time algorithms, considering that the nonlinear algorithm in question is demonstrably instantaneous for extreme real-world workloads (Go is supposed to be about pragmatism, I hear?). Lastly, feel free to lecture me further on how a you suspect that an algorithm that has been deployed and used, to overwhelming acclaim, by tens of thousands of programmers over the past three years will be found wanting in comparison to an algorithm that has existed on paper for two days, with no ecosystem or real-world experience to its name. :)

sagichmal 9y ago

The lack of a solver is predicated on the minimal version decision as well as insisting that breaking changes are reflected in dependency identifiers. These decisions are points on their respective spectrums that other package managers have considered and rejected, because they impose (optimistically) novel or (pessimisticly) burdensome requirements on package authors and consumers. Namely, that we bias toward stable (unchanging) builds, even when security or bugfix releases may be safely applied; and that we force authors toward uncommon and arguably awkward naming decisions when making breaking changes, essentially shifting work from computers to humans. Again, these things aren’t novel; in isolation, they’ve been considered (and rejected) by other package managers. Maybe they compose to something greater than the sum of their parts. At the moment, it’s unclear, and it mostly looks messy.

ngrilly 9y ago
What makes you think this design was considered by other package managers (npm, yarn, pip, bundler, cargo, etc.) in the past? Is it documented somewhere?
- sagichmal 9y ago
  I'm basing this on documented albeit informal conversations with other package manager builders and maintainers.