Official API for parsing Cargo.tomls schema

[epage]

Problem

Something is needed by crates.io for creating index entries, rather than reading the json blob which might be out of sync. They switched to community developed crates but this creates hidden relationships when making manifest changes (rust-lang/crates.io#6914).

Proposed Solution

Bigger requests, like #4614, are blocked on the fact that the code ties into everything within cargo. So instead, let's get an incremental step by just putting out the schemas, with no business logic.

Notes

Steps

• Set and verify all MSRVs in CI #12654
• refactor(toml): Make manifest file layout more consitent #12768
• refactor(toml): Decouple parsing from interning system #12881
• refactor(toml): Cleanup noticed on the way to #12801 #12902
• refactor(toml): Pull out the schema #12911
• refactor(util): Prepare for splitting out semver logic #12926
• refactor(util): Pull out mod util_semver #12940
• refactor(toml): Simplify code to make schema split easier #12948
• refactor(toml): Improve consistency #12954
• refactor(toml): Consistently lead with 'Toml' prefix #12960
• refactor(toml): Clean up workspace inheritance #12971
• refactor(toml): Further clean up inheritance #13000
• refactor(toml): Decouple logic from schema #13080
• refactor(schemas): Pull out mod for proposed schemas package #13097
• refactor: Pull PackageIdSpec into schema #13128
• refactor(schema): Remove reliance on cargo types #13154
• fix: Fill in more empty name holes #13164
• refactor: Pull name validation into util_schemas #13166
• refactor(schemas): Pull out as cargo-util-schemas #13178
• Publish

Related work

• fix: Report more detailed semver errors #12924

See also #2259

[epage]

InternedString offers us two big advantages

• Cheap clone
• Cheap equality checks

My hope is that we can switch to a Arc<str> | InlinedStr type that can offer us the same benefits and use it everywhere. The fallback is to use it just for the schema.

I've updated string-rosetta-rs to include equality checks and everything but Arc<str> and arcstr fails on this front. I was hoping to use something with a bit more flexibility than arcstr as not having to switch between String and OptimizedString would be nice, like ecow or hipstr (flexstr doesn't have full mutability but does have a format!-like macro). However, that is for a future date and the overall performance of arcstr seems really tempting, so I'm going to propose we go with that (it is also maintained by a libs team member)

The main alternative to all of this is to make our types generic over the string type which I'd rather avoid because that gets messy.

Next step, benchmarking cargo with the change from InternedString to arcstr

[Eh2406]

Edit: there is one more big advantage to InternedString, it only allocates one copy of strings. It is not uncommon for cargo to have generated the same string in hundreds of places. "serde" is the name of a package, and the name in hundreds of dependencies that depend on that package, and the feature name of the optional feature enabling that dependency in each of throws packages... So when we do benchmarking we should look at memory footprint in addition to wall time.

Cheap equality checks

The thing that makes the equality check so fast is that it does not need to dereference the pointer. Before InternedString was added the cash thrashing caused by the pointer dereferences significantly slow down the resolver. That being said, a lot else has improved since then so this may no longer be critical to performance.

Next step, benchmarking cargo with the change from InternedString to arcstr

A specific benchmark I would care about is building a large lock file. Currently all the benchmarks we have measure the time to build the project with a locked file. Furthermore, they all involve git dependencies so rebuilding a lock file is dominated by git. Which means that "just" adding a "generate lock file" call does not tell us about regressions to the performance of the resolver.

[CAD97]

Note that arcstr's performance as currently shown in the linked repo is a bit misleading: it only has that cheap clone when comparing strings cloned from a shared arcstr. As soon as you compare any strings that aren't that special case, you'll get the usual O(n) comparison of the string data.

If you want to avoid string comparisons when comparing strings, you need some form of interning. It can be pointer based (store strings, compare pointers) instead of purely symbolic (store indices, ask cache for real string), but you do need to deduplicate the strings somehow (i.e. intern them) to be able to exclusively test pointer equality.

[epage]

Note that arcstr's performance as currently shown in the linked repo is a bit misleading: it only has that cheap clone when comparing strings cloned from a shared arcstr. As soon as you compare any strings that aren't that special case, you'll get the usual O(n) comparison of the string data.

This depends on how much we are doing comparisons of the data from the same source or not.

If you want to avoid string comparisons when comparing strings, you need some form of interning. It can be pointer based (store strings, compare pointers) instead of purely symbolic (store indices, ask cache for real string), but you do need to deduplicate the strings somehow (i.e. intern them) to be able to exclusively test pointer equality.

We have string interning today. The problem is that I doubt people want that as part of the Cargo.toml parsing API.

[epage]

Just did a quick benchmark with hipstr being used only for manifests

$ ../dump/cargo-12801-bench.rs run
    Finished dev [unoptimized + debuginfo] target(s) in 0.07s
     Running `target/debug/cargo -Zscript -Zmsrv-policy ../dump/cargo-12801-bench.rs run`
warning: `package.edition` is unspecified, defaulting to `2021`
    Finished dev [unoptimized + debuginfo] target(s) in 0.04s
     Running `/home/epage/.cargo/target/0a/7f4c1ab500f045/debug/cargo-12801-bench run`
$ hyperfine "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     119.6 ms ±   2.7 ms    [User: 99.6 ms, System: 19.6 ms]
  Range (min … max):   115.6 ms … 124.5 ms    25 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     118.9 ms ±   2.8 ms    [User: 98.3 ms, System: 20.2 ms]
  Range (min … max):   115.6 ms … 125.3 ms    25 runs

Summary
  ../cargo-new check ran
    1.01 ± 0.03 times faster than ../cargo-old check
$ hyperfine --prepare "cargo clean" "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     19.626 s ±  0.198 s    [User: 151.846 s, System: 22.022 s]
  Range (min … max):   19.348 s … 19.966 s    10 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     19.807 s ±  0.403 s    [User: 152.382 s, System: 22.086 s]
  Range (min … max):   19.469 s … 20.861 s    10 runs

Summary
  ../cargo-old check ran
    1.01 ± 0.02 times faster than ../cargo-new check
$ hyperfine --prepare "cargo clean && rm -f Cargo.lock" "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     20.864 s ±  0.217 s    [User: 152.427 s, System: 22.366 s]
  Range (min … max):   20.632 s … 21.227 s    10 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     20.934 s ±  0.509 s    [User: 151.831 s, System: 22.348 s]
  Range (min … max):   20.410 s … 21.871 s    10 runs

Summary
  ../cargo-old check ran
    1.00 ± 0.03 times faster than ../cargo-new check

Code:

cargo-12801-bench.rs:

#!/usr/bin/env nargo
```cargo
[dependencies]
lexopt = "0.3"
xshell = "0.2"
```

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let args = Args::parse_args()?;

    for command in args.commands {
        match command {
            Command::Setup(args) => setup(args)?,
            Command::Run => run()?,
        }
    }

    Ok(())
}

fn setup(args: SetupArgs) -> Result<(), Box<dyn std::error::Error>> {
    let sh = xshell::Shell::new()?;
    let tmp = tmp();
    let old_path = tmp.join("cargo-old");
    let new_path = tmp.join("cargo-new");
    let built_path = std::path::Path::new("target/release/cargo");

    if args.hard && tmp.exists() {
        std::fs::remove_dir_all(&tmp)?;
    }
    std::fs::create_dir_all(&tmp)?;

    if !tmp.join("cargo").exists() {
        let _dir = sh.push_dir(&tmp);
        xshell::cmd!(sh, "git clone git@github.com:rust-lang/cargo.git").run()?;
    }

    xshell::cmd!(sh, "git checkout master").run()?;
    xshell::cmd!(sh, "cargo build --release").run()?;
    dbg!(built_path);
    dbg!(&old_path);
    std::fs::copy(built_path, &old_path)?;

    xshell::cmd!(sh, "git checkout intern").run()?;
    xshell::cmd!(sh, "cargo build --release").run()?;
    std::fs::copy(built_path, &new_path)?;

    xshell::cmd!(sh, "git checkout master").run()?;

    Ok(())
}

fn run() -> Result<(), Box<dyn std::error::Error>> {
    let sh = xshell::Shell::new()?;
    let tmp = tmp();

    let _dir = sh.push_dir(&tmp.join("cargo"));
    xshell::cmd!(sh, "../cargo-old check").run()?;
    xshell::cmd!(sh, "hyperfine '../cargo-old check' '../cargo-new check'").run()?;
    xshell::cmd!(sh, "hyperfine --prepare 'cargo clean' '../cargo-old check' '../cargo-new check'").run()?;
    xshell::cmd!(sh, "hyperfine --prepare 'cargo clean && rm -f Cargo.lock' '../cargo-old check' '../cargo-new check'").run()?;

    Ok(())
}

fn tmp() -> std::path::PathBuf {
    "target/tmp/bench".into()
}

enum Command {
    Setup(SetupArgs),
    Run,
}

struct SetupArgs {
        hard: bool
}

struct Args {
    commands: Vec<Command>,
}

impl Args {
    fn parse_args() -> Result<Self, lexopt::Error> {
        use lexopt::prelude::*;

        let mut args = Self {
            commands: Default::default(),
        };
        let mut parser = lexopt::Parser::from_env();
        while let Some(arg) = parser.next()? {
            match arg {
                Value(command) => {
                    let command = command.parse_with(|command| match command {
                        "setup" => Ok(Command::Setup(SetupArgs{
                            hard: false
                        })),
                        "run" => Ok(Command::Run),
                        _ => Err("invalid command, needed `setup`, `run`"),
                    })?;
                    args.commands.push(command);
                }
                Long("hard") => {
                    if let Some(Command::Setup(args)) = args.commands.last_mut() {
                        args.hard = true;
                    } else {
                        return Err(arg.unexpected());
                    }
                }
                Long("soft") => {
                    if let Some(Command::Setup(args)) = args.commands.last_mut() {
                        args.hard = false;
                    } else {
                        return Err(arg.unexpected());
                    }
                }
                _ => {
                    return Err(arg.unexpected());
                }
            }
        }

        Ok(args)
    }
}

[epage]

To double check my assumptions, I went ahead and ran the benchmark with String. Apparently, we don't need anything fancy.

$ hyperfine "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     119.3 ms ±   3.2 ms    [User: 98.6 ms, System: 20.3 ms]
  Range (min … max):   115.6 ms … 124.3 ms    24 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     119.4 ms ±   2.4 ms    [User: 98.0 ms, System: 21.1 ms]
  Range (min … max):   115.7 ms … 123.6 ms    24 runs

Summary
  ../cargo-old check ran
    1.00 ± 0.03 times faster than ../cargo-new check
$ hyperfine --prepare "cargo clean" "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     20.249 s ±  0.392 s    [User: 157.719 s, System: 22.771 s]
  Range (min … max):   19.605 s … 21.123 s    10 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     20.123 s ±  0.212 s    [User: 156.156 s, System: 22.325 s]
  Range (min … max):   19.764 s … 20.420 s    10 runs

Summary
  ../cargo-new check ran
    1.01 ± 0.02 times faster than ../cargo-old check
$ hyperfine --prepare "cargo clean && rm -f Cargo.lock" "../cargo-old check" "../cargo-new check"
Benchmark 1: ../cargo-old check
  Time (mean ± σ):     21.105 s ±  0.465 s    [User: 156.482 s, System: 22.799 s]
  Range (min … max):   20.156 s … 22.010 s    10 runs

Benchmark 2: ../cargo-new check
  Time (mean ± σ):     21.358 s ±  0.538 s    [User: 156.187 s, System: 22.979 s]
  Range (min … max):   20.703 s … 22.462 s    10 runs

Summary
  ../cargo-old check ran
    1.01 ± 0.03 times faster than ../cargo-new check

[Rustin170506]

Thank you for working on this! 💚 💙 💜 💛 ❤️