Thank you, that's a very interesting read.
TLDR: If I understood everything, NP-complete != DLL hell, but anyway, go
is vulnerable to DLL hell, so we're screwed.
I'm not sure I understand everything, though. Both your article and Russ
Cox' you mention seem to confuse NP-completeness and the concept of DLL
hell. I thought DLL hell was the inability, plain and simple, to install
two versions of the same DLL (and, AFAIK, two different versions of a go
package). The problem of whether you need two incompatible versions or not
happens to be NP-complete, but that's not the problem per se, is it ?
If I understood correctly your article and Russ Cox', the proposed solution
is either to offer, in each subsequent version of a package / shared
library / DLL, both the old and the new API, or to allow the installation
of several packages. However this leads to problems, as you now tend to
have bloated binaries that contain old compatibility code you don't
necessarily need. If version 1 and 2 of package C are incompatible, I'm
expecting the latest binary version of package C to contain both version 1
and version 2.
However that's good for DLLs and other shared objects, but that seems
overkill in the case of go, since each executable includes all the library
code it uses. If I need package A and package B, and both those packages
only use the version 2 of C, I don't wan't to include the version 1 of C,
too, in my executable: it is already big enough. If you want to avoid it,
you need to be able to specify specific versions of packages, and you're
almost back to square one, with an NP-hard problem.
But this is not DLL hell anymore: first, you know your program can be
installed, not matter what. You might need to duplicate lots of code, have
several different versions of your packages, but at least there's a
possible solution. Secondly, this is no more a decision problem (is there a
solution at all), but an optimization problem (what is the best possible
solution): the initial, suboptimal solution (just install the last version
of each package, recursively) is found in linear time and the optimization
process can be interrupted at any moment if it takes too long, leaving you
with a suboptimal but workable solution.
So, for instance :
let's say I want to install package p, that requires both packages a and b.
Here are package a's versions, and their dependencies :
a:
v1: c >=1
v2: c = 2
And package b:
b:
v1: c >= 2, d >= 1
v2: c >= 3, d >= 1
There are two more dependencies, c and d, here are their own versions and
dependencies:
c:
v1: nothing
v2: nothing
v3: nothing
d:
v1: c = 1
If I can't have two versions of the same package installed, I have to go
through a NP-complete problem (and use a SAT solver or equivalent) to find
I'm actually out of luck: there is now way to install p while having at
most one version of each package. That is DLL hell.
But if I can have several versions installed, a first reasonable option is
to propose to install the latest version of a and b, and then the latest
versions of each of their dependencies, recursively. If incompatible
versions are needed, duplicate them. So, here, that initial solution would
be a2, b2, c1, c2, c3, d1. Good, and found in linear time, but not perfect,
since there are duplicate packages. I can now try to find an optimal
solution, optimal being defined as "the newer versions the better, the
least installed packages the better". Here, the optimal solution is a1, b2,
c1, c3, d1 which is only 4 packages, the trick being to downgrade to
version 1 of package a. Still NP-complete (NP hard, actually), but no DLL
hell, and I already had a workable solution in linear time.
Now, am I wrong to think that go, in its current state, is still vulnerable
to DLL hell, even with the vendoring mechanism?
Le dimanche 24 décembre 2017 00:44:32 UTC+1, David Collier-Brown a écrit :
>
>
>> A bit of an unresolved problem in several universes, one of which
> contains Go (;-))
>
> I have some definite opinions: I grew up in a universe where it was
> resoilved in Multics, rediscoverd in Solaris and independantly rediscovered
> in Linux glibc. Way more information that you want in
> https://leaflessca.wordpress.com/2017/02/12/dll-hell-and-avoiding-an-np-complete-problem/
>
> <https://www.google.com/url?q=https%3A%2F%2Fleaflessca.wordpress.com%2F2017%2F02%2F12%2Fdll-hell-and-avoiding-an-np-complete-problem%2F&sa=D&sntz=1&usg=AFQjCNHbJ3pVxytKQ7X1cDO6yiijFPp-dw>
>
> The best advice I can give in the current context is to chose an A-B pair
> with a common C, even if it causes you to go back to an undesirably early
> release of either A or B.
>
> It is, after all, an NP-complete problem: there is no guarantee that there
> is a good answer, save to *not have* the problem, as the Multicians found.
>
> --dave
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
