4 ms·

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 rough

by 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. :)
- dilap 9y ago
  The claim under consideration is whether the Go packaging proposal is novel, not any of the other things you've mentioned. :-)

by dilap 9y ago

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. :)

dilap 9y ago
The claim under consideration is whether the Go packaging proposal is novel, not any of the other things you've mentioned. :-)