pubgrub: Solving slows down dramatically when testing hundreds of versions

When testing many consecutive versions of a given package, the cost of computing compatible versions seems to increase non-linearly over time.

Concretely, running this example slows down noticeably for me at around 100 iterations, and grinds to a ~halt in the 200s:

use pubgrub::error::PubGrubError;
use pubgrub::range::Range;
use pubgrub::report::{DefaultStringReporter, Reporter};
use pubgrub::solver::{OfflineDependencyProvider, resolve};
use pubgrub::version::SemanticVersion;

fn main() {
    let mut dependency_provider = OfflineDependencyProvider::<&str, SemanticVersion>::new();

    // root depends on foo...
    dependency_provider.add_dependencies(
        "root", (1, 0, 0),
        vec![
            ("foo", Range::any()),
        ],
    );

    for i in 1..1000 {
        dbg!(i);

        // foo depends on bar...
        dependency_provider.add_dependencies(
            "foo", (i, 0, 0),
            vec![
                ("bar", Range::any()),
            ],
        );

        match resolve(&dependency_provider, "root", (1, 0, 0)) {
            Ok(sol) => println!("{:?}", sol),
            Err(PubGrubError::NoSolution(mut derivation_tree)) => {
                derivation_tree.collapse_no_versions();
                eprintln!("{}", DefaultStringReporter::report(&derivation_tree));
            }
            Err(err) => panic!("{:?}", err),
        };
    }
}

I suspect that this may have to do with the increased size of the intersected versions. For example, after testing and rejecting Django 5.0a1, we produce a term like:

[ 0a0.dev0, 5.0a1 [  [ 5.0a1.post0.dev0, ∞ [

We then test Django 4.2.6, which gives us:

[ 0a0.dev0, 4.2.6 [  [ 4.2.6.post0.dev0, ∞ [

We then take the intersection of these terms, which gives us:

[ 0a0.dev0, 4.2.6 [  [ 4.2.6.post0.dev0, 5.0a1 [  [ 5.0a1.post0.dev0, ∞ [

This continues until we have a range like:

[ 0a0.dev0, 4.2rc1 [  [ 4.2rc1.post0.dev0, 4.2 [  [ 4.2.post0.dev0, 4.2.1 [  [ 4.2.1.post0.dev0, 4.2.2 [  [ 4.2.2.post0.dev0, 4.2.3 [  [ 4.2.3.post0.dev0, 4.2.4 [  [ 4.2.4.post0.dev0, 4.2.5 [  [ 4.2.5.post0.dev0, 4.2.6 [  [ 4.2.6.post0.dev0, 5.0a1 [  [ 5.0a1.post0.dev0, ∞ [

If you’re testing hundreds of versions, the terms continue to grow, and I suspect this leads to some kind of quadratic behavior, since we’re increasing the number of terms linearly with the number of tested versions.

The intersections aren’t “wrong”, and it’s possible that we’re doing something wrong with our version formulations – but could we take advantage of the fact that we know there are no versions in these partial ranges?

For example, given [ 0a0.dev0, 5.0a1 [ [ 5.0a1.post0.dev0, ∞ [ and [ 0a0.dev0, 4.2.6 [ [ 4.2.6.post0.dev0, ∞ [, it would be preferable to reduce to [ 0a0.dev0, 4.2.6 [, if I’m understanding the syntax correctly.

About this issue

Original URL
State: closed
Created 8 months ago
Comments: 24 (24 by maintainers)

Most upvoted comments

I have been working on several different approaches to see what will make a difference on these benchmarks. None of them are at a state for public discussion. Each on their own did not make a significant performance difference. Today I experimented with putting them altogether. And I’m seeing significant results!

The current version of the benchmark is:

    let mut dependency_provider = OfflineDependencyProvider::<&str, Range<NumberVersion>>::new();

    // root depends on foo...
    dependency_provider.add_dependencies("root", 1, vec![("foo", Range::full())]);

    for i in 1..500 {
        // foo depends on bar...
        dependency_provider.add_dependencies("foo", i, vec![("bad", Range::full())]);
    }

    let start = Instant::now();
    _ = resolve(&dependency_provider, "root", 1);
    let time = start.elapsed().as_secs_f32();
    let len = dependency_provider
        .versions(&"foo")
        .into_iter()
        .flatten()
        .count();
    println!("{len}, {time}");

with a slower variation by changing ("bad", Range::full()) to ("bad", Range::higher_than(i)).

Time (s)	`full`	`higher_than`
dev	4.5	11.6
hacks	1.2	2.6

This is without optimizations for making VS smaller! This is also without #104 ! And does not include creating an arena for package names. All of which clearly show up on the flame graph.

I will clean up some of my hacks into PR’s, but probably not till after PackagingCon. I may also push for us to merge #104, as keeping two versions of each of these commits is getting difficult.

Eh2406 on Oct 25, 2023

Before #112 Range<NumberVersion> does not grow as it’s smart enough to know that there cannot be versions in between consecutive integers. So I ran the following code (in release) with both NumberVersion and SemanticVersion

fn main() {
    let mut dependency_provider = OfflineDependencyProvider::<&str, Range<NumberVersion>>::new();

    // root depends on foo...
    dependency_provider.add_dependencies("root", 1, vec![("foo", Range::any())]);

    for i in 1..500 {
        let start = Instant::now();

        // foo depends on bar...
        dependency_provider.add_dependencies("foo", i, vec![("bar", Range::any())]);

        _ = resolve(&dependency_provider, "root", 1);
        let time = start.elapsed().as_secs_f32();

        println!("{i}, {time}");
    }
}

I used Excel to fit a trendline (note: the two lines are on different axes): It is quite clear that both of these lines are nonlinear. It also looks like the SemanticVersion is growing more steeply then the NumberVersion. From this I conclude that there are other nonlinear things going on, and that but that the growth of the VS is most of the problem.

Eh2406 on Oct 18, 2023

I was able to update our branch to pull in those changes, and I let this pathological resolution run for 60 seconds. dev got through 433 candidate versions, while the changed branch only got through 212 candidate versions unfortunately. Hopefully I didn’t mislead with the above benchmark 😦 It’s also possible I messed up somewhere pulling in the changes… I’ll double check now. Though I’d be interested to see how it affects the ron file benchmark.

charliermarsh on Nov 7, 2023