Optimize dependency resolution algorithm?

[Abscissa]

Is it possible to adjust the dependency resolution algorithm to scale better? I've hit situations (not easy to reproduce AFAICT so far) where the dependency resolution step can take several minutes or even half-hour or more, and (unless --vverbose is used) with no output indicating what it's doing or any indication that no, it has not actually locked up.

[Abscissa]

FWIW, I just hit a case where it took approx 12 hours. As dub grows and gets more heavily used, this problem will probably only get bigger and more common.

[Geod24]

Sounds like a bug. Any idea what the bound is ? I take from your comment it's IO (registry) bound ?

[Abscissa]

Appears to be CPU. I happen to have it running right now (without --vverbose). KDE's System Activity program is reporting approx 5MB (each) in/out IO total, no current IO at all and 30MB memory (completely unchanging). But it's showing an unchanging 25% CPU (I have two hyper-threaded cores, so I'm guessing that might indicate it's a single-threaded program fully saturating one of the 4 available CPU threads).

I've done it before with --vverbose, and I could see that it goes through tons of cycles of trying lots and lots of different combinations of version numbers for the different packages. The first time it happened, I suspected an infinite loop, but I couldn't find any duplicate combinations in the very long --vverbose output. So I let it run and it eventually completed. So I'm suspecting a poorly-scaling algorithm, like an O(2^n) or some such.

[Abscissa]

FWIW, the program I'm hitting this issue with (it's not on github right now) involves 17 packages total (including both direct and indirect dependencies). 19 if you count sub-packages separately.

[s-ludwig]

The issue is that the current ((hopefully) exhaustive) algorithm has a worst case exponential runtime. There are a number of quick paths that make the process linear in the usual case, but some dependency configurations contain pathological cases. There are basically two options how to solve this:

1. Make hitting such cases less likely by adding more quick paths.
2. Use a different algorithm that is not exhaustive, but has guaranteed linear or close to linear runtime.

The latter would only be possible by making some assumptions, such as that a newer version of a package will have dependency specifications that are newer or equal to the older versions. Since this will not always be true, some dependency trees may yield a sub-optimal set of version selections, or, in the worst case, will fail to fine one at all.

[s-ludwig]

BTW, the problem in general is NP, so there is no algorithm that is faster than exponential (unless P==NP of course...). We'd really have to change the problem formulation to be able to fix this completely.

[Abscissa]

Is there any way to at least just bypass the dependency resolution step? I tried touch dub.selections.json but it still tried to go through all the dependency resolution.

[s-ludwig]

--nodeps should help if dub.selections.json is already populated.

[MartinNowak]

It seems that dub doesn't use the dependencies of the earlier packages to narrow down the versions tried for later packages.

[MartinNowak]

And if no dependencies are specified, we should always try to use the latest version of a package in the allowed range.

[MartinNowak]

And when your package specifies 2 dependencies w/o versions and the latest of those have contradicting dependencies, then it's fine to fail, i.e. you need to select compatible versions when they have diamond dependencies.

[triplefox]

Ran across this with a barebones hello world that has a single dependencies line: "gfm": "~>3.0.4". Just in case you're looking for testcases.

[MartinNowak]

Yes, I also found this via gfm.
BTW, bundler also tries older version to find a working configuration, maybe they have a better algorithm.
https://github.com/bundler/bundler/blob/master/lib/bundler/resolver.rb

[MartinNowak]

https://github.com/CocoaPods/Molinillo/blob/master/ARCHITECTURE.md

[John-Colvin]

Is there any easy way to avoid hitting the slow cases here? I've been waiting for 30 mins for what should be a simple build...

[s-ludwig]

I don't know of a way to work around this other than putting indirect dependencies into the root package, but a good way to avoid the most common slow case is to merge #733 (Reviewers welcome ;)

[Abscissa]

I'm not familiar with the relevant section of dub's code (had trouble wrapping my head around what/how it was doing back when I did look), but I was just giving a little thought to how it might be done and I'm starting to wonder: Are we really sure the algorithm's scaling complexity really is the cause of these particular slowdowns after all?

Little back-of-napkin calculation:

Suppose we have a root project with 64 direct and indirect dependencies total. (I know the number of indirect dependencies can vary depending on the dependency versions selected, but let's say all the combinations average to 64 dependencies.) Now suppose each of those packages has, on average, 64 version tags available. Now, I know for a fact that I've hit this problem on a project with considerably less than that, more like 32x32, if even that.

(Furthermore, I would imagine for any remotely realistic project, the list of all versions available for all potentially-used packages, and the deps list for each version, would easily fit in memory. So all that could be cached if it isn't already. So there's no additional nested algorithmic complexity stemming from any redundant loading of deps/version info.)

That amounts to a worst-case-scenario (with a no-shortcuts, brute-force "check every possibility and select the best one found" algorithm), of needing to check 64 * 64 == 4,096 combinations. Unless I'm overlooking something, I'd imagine that once you have a combination to check, the check itself would be computationally very simple.

So, suppose it takes a full second to check each combination (maybe I'm missing something, but I don't see how each check would realistically need to take that long, even if you include the time spent calculating the next combination to be checked). Then that's 4k/60==~68 seconds or just over one minute to resolve dependencies. And I've hit cases of around half-hour, maybe more, on projects with dependency graphs no more than a quarter the size of this example.

I'm thinking we may be looking at a slowdown in the implementation, not the algorithm. Maybe some sort of overlooked nested complexity that doesn't need to be there, or something that could be cached but isn't.

[s-ludwig]

It's not 32*32 but 32^^32! Usually the search will terminate after just a few combinations, because a lot of them are ruled out and the result is usually pretty close to all dependencies being at their latest version. The particular thing that currently causes most (if not all) of the slowdowns is that a special "invalid" version is added in front of each list of versions for each package to support the existing "optional" semantics.

#733 changes this to add an "invalid" version only for dependencies that are actually only referenced as optional, and it appends instead of prepending to the list, which means that the "invalid" version is tried last instead of first.

We'll have to see how it turns out, but I hope that this will give us more time to come up with an algorithm with better worst-case run time. Ideally I'd also like to take that opportunity to let the algorithm also resolve the build configurations in addition to the versions. They are currently calculated separately, which could lead to undesired results in pathological cases.

[Abscissa]

"It's not 32*32 but 32^^32!"

Oops, yea, that's right.

[MartinNowak]

Moved to backlog and scheduled for the next few weeks when I'm done with fixing imports and symbol visibility.

[s-ludwig]

@MartinNowak ping me when you have a concept. I had a few ideas, but didn't fully think them through, yet. The algorithm should be able to handle version and configuration resolution at the same time (which should automatically work if it uses a generic key type like the current DependencyResolver does, it would use tuples of version/configuration then). I don't think that converting it from iterative to recursive itself will improve anything, there either will have to be more early-out conditions, or we need a non-exhaustive search that has a better worst-case complexity.

[MartinNowak]

I'll take #652 (comment) as a starting point, dependency resolution and conservative partial upgrades work really well with bundler.

[MartinNowak]

#733 changes this to add an "invalid" version only for dependencies that are actually only referenced as optional, and it appends instead of prepending to the list, which means that the "invalid" version is tried last instead of first.

Right, 04648ee solved the most pressing 2^N issue with gfm, that was caused by prepending invalid configurations (old method to support optional deps).

[MartinNowak]

Looking at other dependency resolvers, we can improve the following.

Terminology

• requirement: a dependency such as vibe.d ~>0.9.27
• possibility: a specific version of a package (called config in dub)
• activate: selecting a possibility to resolve a requirement (currently done via config_indices)
• selections: existing version selections from dub.selections.json

Improvement Ideas

• Sorting requirements seems to be key for fast resolution.
  Bundler sorts requirements first by existing selections/activations, then by specificity of the requirements, and then by conflicts (could try to group requirements that conflict w/ each other).
  Cabal also uses order of requirements to speed up resolution/failure, i.e. try requirements with few possibilities (e.g. a branch version) or the ones that will more likely fail first.
• Rather than permutating configs and then checking all for validity, we could try to check a possibility only against previously activated possibilities.
  This forward checking part would avoid redundant rechecking of the first activated possibilities.
  Could be done w/ a similar iteration through all_configs and config_indices.
• We should order possibilities so to favor preserving the current selections.
  This would allow us to add dub upgrade specific-package to update as little as possible.
  Updating one package or all packages could be implemented by masking the existing selections.
  There could even be different policies for this ordering, e.g. smallest
  deviation from current version (0.1.2, 0.1.3, 0.1.4..., 0.1.6), or
  current then latest (0.1.2, 0.1.6, 0.1.5..., 0.1.3)
• Molinillo has a strategy to replace an already activated possibility with a different version as a quickpath to resolve conflicts (see here).
  This seems fairlys complex but could improve resolution if conflicts are common.

[MartinNowak]

Think we should close this. The urgent problem has been fixed and the resolver is fairly good/fast already.
The only immediate improvement that I see, is reducing the amount of validity checking, see point 2 of ideas above.