JuliaLang/julia — pull request #1909 by carlobaldassi (2013-01-07 16:42:28+00:00)
Title: WIP/RFC: Alternative max-sum-based approach to package resolution

As briefly mentioned on the dev list, I wrote a pure-Julia package resolution algorithm based on the max-sum algorithm, as a substitute for the linear programming approach. This would allow to remove the dependency on GLPK/LinProg modules.

Unfortunately, this is going to need some detailed discussion...

With the current situation in the official METADATA, it works the same as the linear-programming-based one, with similar timings (slightly faster, but the times are dominated by the data fetching anyway). However, the current METADATA is not particularly interesting, since all packages are at version 0.0.0 and the dependency graph is very simple.

In order to stress-test the system, I used a generator for synthetic data, hijacked the functions `packages()`, `versions()` etc. from Matadata and I ran both the old and new systems. I'll publish it somewhere, but the point is that what would really be needed is to test both realistic settings with lots of packages and corner cases, while my randomized tests were not particularly realistic, and I tested just a few corner cases where I knew max-sum could have had some problems. In other words, a more controlled testing environment would be needed. So this is an area where I'll ask for help.

The results so far are as follow: with the synthetic randomized data, as soon as the number of packages (and versions allowed for each package) go up (on the order of 30 or so) and the dependency graph gets sufficiently complex, what happens is that

1) mixed integer progamming chokes, in that it takes ages (never seen it complete)
2) simplex-based method can happily return invalid solutions
3) max-sum works just fine (see below for more details)
4) in any case, when linear programming works fine, the results are the same as max-sum

I went up to 1000 packages and found that the linear programming approach fails due to excessive memory consumption (I have 8 Gb of RAM), while the max-sum one does not have a noticeable memory footprint, since it uses custom-made sparse structures everywhere. BTW, it took on the order of 40 seconds to produce a solution with 1000 packages on my machine.

Unfortunately, this means that it's very hard to assess if the solution is a global optimum. However, I implemented a test to check if the solution returned by max-sum is at least a local optimum, at I've never seen it fail with the current code (it's in the `verify_optimality` function).

About the corner cases, I created some small graphs by hand and introduced some very sick (totally unrealistic) cyclic dependencies in order to screw with the message-passing approach, and I've always seen it do what it's supposed to. Again, it's hard to derive a general principle from this, but the outlook is good at least. More tests are required.

There is also something to say about the rules I've chosen: the way it works now is as follows: requirements and dependencies are considered as hard constraints, which shall never be violated. Then, for all explicitly required packages, the highest versions are favoured. Then, for all other packages, it favours non-installation, followed by the highest versions (but with a lower precedence w.r.t. explicitely installed packages). Then, in case of a tie, dependants are favoured over dependencies. Lastly, if there is still a tie, random noise is used to drive the system to one single solution. I can expand on this if needed.

In any case, the cost of choosing a lower version of a package is a constant; this does not make any difference between major, minor and micro versions; this could be changed, I think.

Finally, the presence of random functions (though unlikely to be relevant in practical cases) is worrying from the point of view of reproducibility, so one thing to do would be at the very least use a fixed seed.

I'll cut it short here and let the discussion start; I'm of course available for any explanation about the graphical model and the code (which I tried to make readable by segregating structures and adding a lot of comments, but is still confusing probably).

One last remark: in order to define precedence rules, I defined my own numeric type `FieldValue`. This was a late addition, I've been using just Float64 previously. In order to do the change, I just had to add a bunch of definitions and everything was working like a charm. I was AMAZED, Julia is truly great for this kind of stuff!