5 ms·

Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency

Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency hell because someone thought it would be a good idea to use a full-blown SAT solver for package management. Grr.

ignoramous 7y ago
> ...someone thought it would be a good idea to use a full-blown SAT solver for package management Relevant: https://research.swtch.com/version-sat https://research.swtch.com/version-sat
- jjoonathan 7y ago
  Right. SAT solvers are an excellent theoretical fit and a terrible practical fit, at least at the current state of tooling. Their runtime _does_ explode and the tooling _is not_ any good at hinting as to why even when the explanation turns out to be very simple. "lol install takes an hour now" makes for a very poor error message, and debugging a black box that takes an hour to evaluate each input is just.... ugggggghh, and I can only thank my lucky stars that it did finish after an hour rather than taking an indefinite amount of time. In contrast, the "danger" of heuristics is that they fail to dig up an exceedingly clever combination of archaic package versions that technically fit the user's specified requirements. It's such a small problem that it might even be considered a feature, since said exceedingly clever combinations are likely to be the result of poor version definitions and unlikely to be what the user actually wants. Of course, if the only people who can be persuaded to write package managers are people doing research in the subject, then I suppose letting them inflict their pet projects on us is one way to compensate them for an otherwise thankless task, and perhaps in that sense it's fair.
  - cwzwarich 7y ago
    Do you have an example of a real-world package dependency situation that generates a truly difficult SAT instance?
hinkley 7y ago
Sometimes I have lamented the fact that 80% of everything we're ever going to properly discover in Computer Science has already been discovered forty years ago. What hasn't been explored very well is how to formulate these solutions so mere mortals can comprehend how they work. Algorithms accessibility is, I believe, the limiting factor on building systems any bigger than the ones we have now. When there is one tricky bit in the code, you can get away with asking people to dive in and learn it. When there are 50? 100? Just figuring out the consequences of how those systems interact is a full time job, let alone how they function internally. Give me a SAT solver, or a parser, or half a dozen other things, that decomposes a problem the way a human would do it, just faster and with far more accuracy, and I could learn it in a week. Take all my Paxoses and replace them with Raft, then swing by and make a second pass on a few.
- jeffdavis 7y ago
  It's hard to optimize algorithms while also making them general and composable. We are forever reimplementing good ideas in different combinations of systems.
- imtringued 7y ago
  The real problems are conventions and ease of use. You're not going to solve these problems by pointing at a paper from the 80s and shouting "We did this 40 years ago! Why is everyone so dumb nowadays?". Lets take WebAssembly as an example. It's only reason for existence is convention. You need everyone to agree on an IR that is not only cross platform and stable but also low level and allows execution of untrusted code within a sandbox. If you look at competitors then it becomes obvious that they are not following these core principles. LLVM IR just isn't meant to be used in a browser. JVM bytecode just wasn't meant to be used in a browser. So what are we going to do? Use them anyway? That's how you get situations like the horribly insecure JVM plugin. You can restrict the JVM plugin to a subset that is secure enough for browsers and add additional opcodes for low level behaviors but then you are no longer using JVM bytecode. It's a completely new invention at that point but Oracle will still hunt you down.
  - hyperman1 7y ago
woadwarrior01 7y ago
That’s because package version selection is a SAT problem. https://research.swtch.com/version-sat https://research.swtch.com/version-sat

ignoramous 7y ago

> ...someone thought it would be a good idea to use a full-blown SAT solver for package management Relevant: https://research.swtch.com/version-sat https://research.swtch.com/version-sat

jjoonathan 7y ago
Right. SAT solvers are an excellent theoretical fit and a terrible practical fit, at least at the current state of tooling. Their runtime _does_ explode and the tooling _is not_ any good at hinting as to why even when the explanation turns out to be very simple. "lol install takes an hour now" makes for a very poor error message, and debugging a black box that takes an hour to evaluate each input is just.... ugggggghh, and I can only thank my lucky stars that it did finish after an hour rather than taking an indefinite amount of time. In contrast, the "danger" of heuristics is that they fail to dig up an exceedingly clever combination of archaic package versions that technically fit the user's specified requirements. It's such a small problem that it might even be considered a feature, since said exceedingly clever combinations are likely to be the result of poor version definitions and unlikely to be what the user actually wants. Of course, if the only people who can be persuaded to write package managers are people doing research in the subject, then I suppose letting them inflict their pet projects on us is one way to compensate them for an otherwise thankless task, and perhaps in that sense it's fair.
- cwzwarich 7y ago
  Do you have an example of a real-world package dependency situation that generates a truly difficult SAT instance?

hinkley 7y ago

Sometimes I have lamented the fact that 80% of everything we're ever going to properly discover in Computer Science has already been discovered forty years ago. What hasn't been explored very well is how to formulate these solutions so mere mortals can comprehend how they work. Algorithms accessibility is, I believe, the limiting factor on building systems any bigger than the ones we have now. When there is one tricky bit in the code, you can get away with asking people to dive in and learn it. When there are 50? 100? Just figuring out the consequences of how those systems interact is a full time job, let alone how they function internally. Give me a SAT solver, or a parser, or half a dozen other things, that decomposes a problem the way a human would do it, just faster and with far more accuracy, and I could learn it in a week. Take all my Paxoses and replace them with Raft, then swing by and make a second pass on a few.

jeffdavis 7y ago
It's hard to optimize algorithms while also making them general and composable. We are forever reimplementing good ideas in different combinations of systems.
imtringued 7y ago
The real problems are conventions and ease of use. You're not going to solve these problems by pointing at a paper from the 80s and shouting "We did this 40 years ago! Why is everyone so dumb nowadays?". Lets take WebAssembly as an example. It's only reason for existence is convention. You need everyone to agree on an IR that is not only cross platform and stable but also low level and allows execution of untrusted code within a sandbox. If you look at competitors then it becomes obvious that they are not following these core principles. LLVM IR just isn't meant to be used in a browser. JVM bytecode just wasn't meant to be used in a browser. So what are we going to do? Use them anyway? That's how you get situations like the horribly insecure JVM plugin. You can restrict the JVM plugin to a subset that is secure enough for browsers and add additional opcodes for low level behaviors but then you are no longer using JVM bytecode. It's a completely new invention at that point but Oracle will still hunt you down.
- hyperman1 7y ago

woadwarrior01 7y ago

That’s because package version selection is a SAT problem. https://research.swtch.com/version-sat https://research.swtch.com/version-sat