Test solver against random graphs

[sdboyer]

Almost all of the tests I've written for gps' solver thus far are geared towards checking some aspect of correctness of the solver. Testing its performance has not been a priority. But the solver is tasked with constraint solving - an NP-hard search problem. Its performance (against real graphs) is something we have to care very much about.

Of course, there's a chicken-or-egg problem there - getting real graphs is difficult when the ecosystem doesn't exist yet for us to test against. Even when it does, though, the shape of the ecosystem is bound to change over time. It would be ideal if we had a way to get out ahead of solver performance issues, rather than having to wait for them to arise.

It seems to me that a potentially good approach to "getting ahead" in this way is to invest in a system for testing the solver against random dependency graphs. It's not trivial to do so - the generator would need to work across several dimensions of variables - but it shouldn't be crazy hard to do, either. The crucial bit will be exporting the generated graphs into valid Go code, probably in the same form used to declare the handcrafted correctness-checking fixtures that exist today.

The basic loop would be something like this:

1. Generate random graph
2. Dispatch a solve using the random graph
3. If solve time exceeds , dump the graph
   • Support for timing out a solve run would need to be added to the solver. Not hard, and no need to expose that control yet
4. Repeat 1-3 until we find a graph that causes solving to run for more than X (maybe start with 5) seconds, then dump the templated declaration of it to stdout

This would be a great tool in our arsenal, though I'm not sure when I'd have time to get to it myself. Help would be awesome. I'm happy to add more info here, and generally provide guidance as needed to anyone interested.

[timtadh]

One way to construct "worst case DAGs" for version control operations is to generate a graph in the form of a N-dimensional grid or lattice structure. This effectively makes every "non-edge" commit in the DAG a merge commit. Here is a simple example:

The numbers are the commits, edges indicate parent-commit --> child-commit or previous-version --> next-version

1 --> 2 --> 3 --> 4
|     |     |     |
v     v     v     v
5 --> 8 --> 9 -->10
|     |     |     |
v     v     v     v
6 -->11 -->12 -->13
|     |     |     |
v     v     v     v
7 -->14 -->15 -->16

VCS systems often have problems involving selecting ranges of commits and constructing these "worst-case" lattices can be used to test the performance of the operations.

For the dependency resolution problem a similar structure could be used. However, there are some wrinkles.

1. VCS DAGs are different than the dependency resolution problem. So a different random structure will be needed. This type of structure may be useful to think about when constructing the random graphs.

2. For 3SAT (and by extension all NP-Complete problems) there is currently no know way to reliably and randomly select a "hard-instance" of a problem. If we could randomly generate hard instances of NP-Complete problems we could construct simple and secure cryptographic systems. However, at present we cannot do this.

However, we do not need to necessarily generate only hard instances. It may be reasonable to simply generate large instances.

From reading the code it looks like the current testing infrastructure could be used to generate random graphs with some caveats. First, we may not know what the correct solution is but we could ensure only solvable graphs are generated. It could be a secondary test to ensure only non-solvable graphs are generated.

[sdboyer]

Thanks, I do think this helps frame the problem.

VCS DAGs are different than the dependency resolution problem. So a different random structure will be needed. This type of structure may be useful to think about when constructing the random graphs.

Definitely - defining the structure of the random graphs strikes me as being what will probably take the most work. It also demands attention because it will need some design for flexibility - we are likely to add new dimensions to the solver over time, which the random graph generator would need to reflect, if it is to retain its utility.

Whereas that worst-case lattice you describe for VCS operations describes only a single dimension - the is-child-of relation - between vertices, our problem here has a slightly more complex model to consider. In the simple case (which most other package managers could get away with), we would ideally treat each "project" as a vertex. However, projects are really just trees of packages, and the relation that we are trying to satisfy is imports - which is a property of individual packages, rather than projects as a whole.

Packages can't vary versions independently of their project, though - we enforce the requirement that all packages from a given project must use the same version. (I think the motivation for maintaining that invariant should be clear here, given the reduction in size of the search space it induces). The solver itself more or less treats the projects as vertices and the packages as properties of those vertices, but that doesn't necessarily mean that's the right model for a random generator.

That's the base shape of the graph. Then there's the question of how to model the satisfiability constraints themselves.

For 3SAT (and by extension all NP-Complete problems) there is currently no know way to reliably and randomly select a "hard-instance" of a problem. If we could randomly generate hard instances of NP-Complete problems we could construct simple and secure cryptographic systems.

Hah, interesting! I've got your paper bookmarked, I'll read through it when I get a chance. But...

However, we do not need to necessarily generate only hard instances. It may be reasonable to simply generate large instances.

This is crucial, and why I was inclined towards a random generator in the first place: I'd go further to say that we expressly don't care about generating hard instances, because I don't think that hard instances have much to do with the shape of real depgraphs.

I suspect - but desperately want evidence - that if we were to analyze the universal Go import graph, we would find it is extremely sparse, with a relatively small number of densely-imported hotspots (e.g., github.com/sirupsen/logrus). I think an ideal approach to this problem would work from aggregate data about the global depgraph, including information like:

• Distribution of number of packages per project
• Distribution of number of non-stdlib imports per package
• Frequency with which new non-stdlib imports are introduced to packages across version changes
• Frequency with which existing non-stdlib imports are removed from packages across version changes
• Distribution of depgraph width for individual projects

(by no means exhaustive list)

With this kind of information on hand, we might be able to guide the random graph generator towards creating graphs that are more realistic.

From reading the code it looks like the current testing infrastructure could be used to generate random graphs with some caveats.

Great! Though note that the "bimodal" fixtures are probably the better ones to go on, as they incorporate the crucial project/package relationship I described above. The basic ones collapse that distinction - they pretend that all projects have exactly one package.

First, we may not know what the correct solution is but we could ensure only solvable graphs are generated.

If that's a guarantee we can make, it'd be amazing. 👍 👍 👍

[timtadh]

@sdboyer That paper is really more about cryptography. Connamacher and Molloy's paper is a better reference.

Doing some examples out by hand, the lattice approach looks promising as you can set it up to be:

1. As large as you like.
2. Generate maximum number of version conflicts at every level in the diamond.

However, that might actually be easy to solve. The hardest instances will be when there are many "promising" partial solutions but only one solution which is difficult to find by any heuristics. I will think more about how to model this.

[sdboyer]

However, that might actually be easy to solve. The hardest instances will be when there are many "promising" partial solutions but only one solution which is difficult to find by any heuristics. I will think more about how to model this.

Great. It's the weird cases in the middle that'll get us.

[timtadh]

After giving this some more thought....

So previously we were thinking of dependency resolution as constraint solving and trying to generate conflicts. However, this is not the only way to look at. We can also look at in terms of a slightly wierd form of the subgraph isomorphism problem. This quick post will just go through an example. I am going to work on an actual algorithm maybe tomorrow. I came up with this idea over lunch and I thought I would put it here before I lost the scrap of paper I wrote it on.

Example

Dependencies for project a. Read a : b(1,2) as a depends on project b versions 1 or 2. For simplicity everything will be a project. Versions will be simply numbers. Projects can depend only on specifically listed numbers. So the listing can be viewed as what you would see after expanding the semver constraints.

a    : b(1,2), c(1,2)
b(1) : d(1)
b(2) : d(2)
c(1) : d(2), e(1)
c(2) : d(2,3), e(1,2)
d(1) : f(1)
d(2) :
d(3) : f(1)
e(1) :
e(2) : f(1)

This leads to the following graph of the dependencies:

To find a solution we need to match (that is find a subgraph isomorphism mapping) the following "grammar." The grammar describes the shape of the possible solutions:

a -> {b, c}
b -> {d}
c -> {d, e}
d -> {}
   | {f}
e -> {}
   | {f}
f -> {}

This leads to 4 candidate graphs to match against the graph of project dependencies

To determine the candidate solutions, match the graphs and find the subgraph isomorphism mappings:

The first middle candidate solution is invalid because version e:2 depends on f:1 and it is not in the graph. So it would be removed, leaving 3 solutions:

EDIT: There is a bug in the example above. I did this by hand and I forgot to put an edge in the graph to get the desired result. will fix later.
EDIT: Should be more correct now.

[Groxx]

Just to chime in: I think it's important to generate invalid graphs as well. Attempts will fail, and it'd be best if they completed in a sane amount of time.

[sdboyer]

It certainly makes sense that there would be a way to express the problem here as a weird version of subgraph isomorphism - both are NP-complete. The jump I'm not quite clear on is why that's helpful for the random input generation problem; as-is, this reads to me more like a thought on changing the core algorithm itself. Which is a discussion we can have, sure, but not what this issue is for 😄

But let's assume I've just missed a connection there, which is fine. I've got a few thoughts on the basic model you seem to be headed for. First:

• So the listing can be viewed as what you would see after expanding the semver constraints.

  This is an interesting structural change, because the typical semver range constraints (~1.0.0 aka 1.0.x, or ^1.0.0 aka 1.x.x) are infinite, admitting ℕ in each of those positions. I don't know the significance of this with respect to the problem, but it does trip something in my head.

• While the grammar makes sense, it seems potentially a bit lossy in that it's not explicit about whether a vertex itself has to be present - only about the valid sets of connected vertices it must have if it is present. But perhaps it's implicit (as it is in gps' tests) that only the first item is required/is the root.

• The third and fourth images are missing key information - the absence or presence of f which from d -> {} | {f}, which also makes it hard to see where you're going here.

Honestly, the last image that really makes much sense to me is the second one. That makes it seem like you're trying for a sort of first-pass check to judge, by shape, as to whether a graph even could be a solution, without having to look at versions at all. But...well, yeah, I'm just not sure where it's going, or how it helps us generate random graphs 😄

Looking forward to seeing more when you have it!

[timtadh]

@sdboyer I will do a longer response later but I wanted to address one thing:

So the listing can be viewed as what you would see after expanding the semver constraints.

This is an interesting structural change, because the typical semver range constraints (~1.0.0 aka 1.0.x, or ^1.0.0 aka 1.x.x) are infinite, admitting ℕ in each of those positions. I don't know the significance of this with respect to the problem, but it does trip something in my head.

The selector (eg. ^1.0.0 or ~1.0.0) can only select versions which exist. There are only countable versions for any particular project. Thus, expanding the constraint to the matched versions yields a countable number of nodes. Since, in practice there are a finite number of projects and every project has a finite number of versions there are only a finite number of nodes created. Thus, the graph is finite in size.

[sdboyer]

Since, in practice there are a finite number of projects and every project has a finite number of versions there are only a finite number of nodes created. Thus, the graph is finite in size.

Sure, ofc, the actual problem we're solving will always be finite. Sounds like this probably isn't significant to our current concerns, then :)

Thanks!

[sdboyer]

bump :)

[fabulous-gopher]

This issue was moved to golang/dep#422