Massive regression in compile times

[CryZe]

After #923 the dependency tree massively increased. The total amount of crates during compilation went from 8 to 36. In particular the "critical path" to compilation now consists of 17 crates as opposed to 5 crates. This means that the url crate is now the sole reason why basically all projects depending on the url crate (indirectly) should now take a whole 20 seconds or so longer to compile than before.

You can compile an entire GUI framework in the time the URL crate compiles now.

Before:

After:

[CryZe]

I've seen multiple responses that syn is the main offender here... but while that looks like it may be the case, it's just not the full picture. The problem is that the url crate is fundamentally an "early" dependency, as in, almost all of the web backend ecosystem (which is the majority of Rust's usage) builds on top of the url crate, often by building their API bindings on top of reqwest which in turn depends on the url crate. This means that the majority of those crates require the url crate to have been built before any of those crates can start building. By having such a large dependency chain of 17 (and I believe even worse 19 with idna master), all those crates can't start compiling, effectively increasing compile times by a lot. And here's the thing... it has been argued that syn is usually already "sunk cost" by almost always being in the dependency tree already anyway, but that just doesn't matter if url and in turns almost all of the web ecosystem crates have to start compiling much later. That's why I said that real world projects that do already have syn are heavily affected by this as well. I almost feel like the icu family of crates got split up in many small crates to help with compilation times, but I'm almost certain that it had an overall negative effect on real world compile times, by causing an even longer chain, forcing the url crate to not be an early compilation crate anymore, which it definitely needs to be.

I think there's some widespread misunderstanding that the dependency count or something not already being in the dependency tree is what determines compile times, but the scheduling of when crates can start compiling is actually the most important and most overlooked problem.

[hsivonen]

Thanks for the extra context. Looking at the build of reqwest with default options and without any application code, it is indeed the case that syn gets absorbed into parallelism better than some other parts that show up sequentially in the image here.

I've filed unicode-org/icu4x#5121 and unicode-org/icu4x#5120 . (The latter thing should get LTOed out, so it's not an issue of ICU4X resulting in extra stuff in an optimized binary; you don't pay for what you don't use in binary size, but you do in compile time.)

[hsivonen]

Looking at the build of reqwest with default options and without any application code, it is indeed the case that syn gets absorbed into parallelism better than some other parts that show up sequentially in the image here.

This was a misreading on my part, and it seems that syn is still a part of the compile time problem.

[hsivonen]

TL;DR: I have implemented a prototype (READMEs and metadata unpolished, repos not in the right org, crates not on crates.io) of a back end adapter for idna 1.0.x where ICU4X is the default and top-level dependents can (once published) opt into the unicode-rs back end by downgrading a crate called idna_adapter from its 1.2.x version stream to its 1.1.x version stream.

I’d appreciate it if the folks for whom compile times or MSRV increase arising from ICU4X was a problem could comment if the approach described below addresses their concerns.

---

Cargo does not have the Right Thing

Unfortunately, Cargo lacks a mechanism for the top level of the compilation to choose a back end for a crate deep in the dependency tree. There is a pre-RFC by @epage, but it can’t be used today.

Unsuitability of Cargo features

Unsuited, because:

1. The dependencies of the default case can’t be removed from the dependency graph, which completely defeats the purpose of addressing build times and MSRV if ICU4X is the default (see below).
2. An intervening crate in the dependency graph can force the decision that really belongs to the top level.
3. Unused dependencies hanging around in the dependency graph makes it harder to make sure that subsequent additions to the application’s dependency graph don’t accidentally start using the crates that were supposed to be around latently and were not supposed to be contributing to release artifact.

Which back end should be the default

As for which one of ICU4X or unicode-rs should be the default back end, I strongly believe that the default should be the one that has the better attributes for the compilation product rather than the one that has the better attributes for the compilation process.

ICU4X results in a smaller binary (assuming that there isn’t something else in the dependency tree pulling in the unicode-rs crates anyway) and in faster run-time performance when the input contain Unicode/Punycode labels. ICU4X also has less opportunity for incorrect results due to different unicode-rs pieces not getting updated to a new Unicode version in sync (see below).

The run-time performance is equal between the two options when the input contains only ASCII labels consisting only of lower-case letters.

In other ASCII-only cases, unicode-rs is actually a bit (single-digit nanoseconds per domain) faster right now due to unicode-org/icu4x#5187 and the way the different tiers of ASCII optimizations are organized in idna. I think this oddity shouldn’t be decisive for the default: @sffc already suggested how to make this better on the ICU4X side. And even if that doesn’t work out, it would be possible to work around this on the idna side by increasing the idna code complexity if this is deemed truly a deal breaker. (Notably, when idna is used via url, the memory allocation to hold the ToASCII form dominates, so this difference is less notable than when the Cow-returning cases are benchmarked with idna directly.)

Mechanism

In the absence of global features for Cargo and regular Cargo features being unsuitable, I have implemented an approach where top-level dependents who wish to optimize for MSRV, compilation time, or for data overlap with something else in their dependency tree using unicode-normalization but nothing else in their dependency using icu_normalizer could (once published) opt into the unicode-rs back end by doing cargo update -p idna_adapter --precise 1.1.0.

Correctness

Compared to those who wish to avoid ICU4X staying on idna 0.5.0, this approach provides the correctness fixes of idna 1.0: The unicode-rs back end takes a new dependency on unicode-joining-type.

The unicode-rs back end comes with some future correctness risk, though. The two ICU4X crates, icu_normalizer and icu_properties can be expected to get updated together (unless the top level manually does something weird to pin one but not the other) and to form a coherent whole representing a single Unicode version at a time. In the case of the unicode-rs back end, unicode-normalization, unicode-bidi, unicode-joining-type, and idna_mapping (a new crate containing UTS 46 mapping data in the style of idna 0.5.0) are updated separately by different people. If idna_mapping represents a newer Unicode version than any of the other three crates, the results computed by idna will be bogus for characters introduced in the Unicode version delta. Right now, the situation is a special case: idna_mapping and unicode-normalization are on Unicode 15.1, but unicode-bidi and unicode-joining-type are on Unicode 15.0, but I think this works out, because the new characters in Unicode 15.1 are Han characters that have the defaults for the purpose of Bidi_Class and Joining_Type.

This can be addressed by not publishing a new idna_mapping crate until the other three have updated to a new Unicode version.

If unicode-joining-type continues to treat Unicode version updates as semver breaks, updating it requires either updating idna_adapter or publishing an adapter crate between idna_adapter and unicode-joining-type that would turn unicode-joining-type’s semver breaks into non-semver break as observed by idna_adapter. If idna_adapter needed to be updated, projects that have downgraded idna_adapter to opt into unicode-rs would need to update it, which would be inconvenient and, unless, idna_mapping also treated Unicode version updates as semver breaks, incorrect as idna_mapping updates could get picked up before unicode-joining-type updates.

The best solution would be to get unicode-joining-type to treat Unicode version updates as not semver-breaking.

Run-time performance

url crate benches (which don’t benefit properly from idna 1.0 returning a Cow in some cases but which demonstrate the usual way of reaching the idna crate in the Rust ecosystem):

M3 Pro unicode-rs

test hyphen ... bench: 194 ns/iter (+/- 4) = 159 MB/s
test leading_digit ... bench: 189 ns/iter (+/- 2) = 116 MB/s
test long ... bench: 263 ns/iter (+/- 1) = 163 MB/s
test plain ... bench: 135 ns/iter (+/- 1) = 148 MB/s
test punycode_ltr ... bench: 519 ns/iter (+/- 2) = 65 MB/s
test punycode_mixed ... bench: 488 ns/iter (+/- 7) = 57 MB/s
test punycode_rtl ... bench: 722 ns/iter (+/- 8) = 47 MB/s
test short ... bench: 168 ns/iter (+/- 1) = 148 MB/s
test unicode_ltr ... bench: 510 ns/iter (+/- 3) = 66 MB/s
test unicode_mixed ... bench: 555 ns/iter (+/- 19) = 45 MB/s
test unicode_rtl ... bench: 725 ns/iter (+/- 28) = 38 MB/s

M3 Pro ICU4X

test hyphen ... bench: 195 ns/iter (+/- 1) = 158 MB/s
test leading_digit ... bench: 198 ns/iter (+/- 1) = 111 MB/s
test long ... bench: 263 ns/iter (+/- 2) = 163 MB/s
test plain ... bench: 134 ns/iter (+/- 0) = 149 MB/s
test punycode_ltr ... bench: 457 ns/iter (+/- 20) = 74 MB/s
test punycode_mixed ... bench: 331 ns/iter (+/- 14) = 84 MB/s
test punycode_rtl ... bench: 435 ns/iter (+/- 2) = 78 MB/s
test short ... bench: 171 ns/iter (+/- 1) = 146 MB/s
test unicode_ltr ... bench: 452 ns/iter (+/- 9) = 75 MB/s
test unicode_mixed ... bench: 399 ns/iter (+/- 11) = 62 MB/s
test unicode_rtl ... bench: 461 ns/iter (+/- 4) = 60 MB/s

Binary size

urldemo

[profile.release]
opt-level = "z"
lto = true
strip = true

unicode-rs

Apple Silicon Mac
600040 bytes (600024 after strip)

wasm32-wasi
369071 bytes

wasm-opt -Oz -o opt.wasm --enable-bulk-memory target/wasm32-wasi/release/urldemo.wasm
352460 bytes

brotli -9 -o opt.wasm.br opt.wasm
139480 bytes

ICU4X

Apple Silicon Mac
484456 (484440 after strip)

wasm32-wasi
259253

wasm-opt -Oz -o opt.wasm --enable-bulk-memory target/wasm32-wasi/release/urldemo.wasm
218466

brotli -9 -o opt.wasm.br opt.wasm
89499

Compile time

These are the times for compiling reqwest with default macOS dependencies without any application code.

M3 Pro, dev

• idna 0.5.0: 5.5s
• idna 1.0.1: 6.8s
• idna 1.0.x with adapter and unicode-rs: 5.8s
• idna 1.0.x with adapter and ICU4X: 7.0s

M3 Pro, release

• idna 0.5.0: 7.3s
• idna 1.0.1: 8.6s
• idna 1.0.x with adapter and unicode-rs: 7.4s
• idna 1.0.x with adapter and ICU4X: 8.5s

MSRV

With ICU4X, 1.67. With unicode-rs, 1.57 (for panic in const context).

Testing it

Clone the repos https://github.com/hsivonen/rust-url , https://github.com/hsivonen/idna_adapter , and https://github.com/hsivonen/idna_mapping next to each other.

Switch rust-url to the branch deferadapter. Switch idna_adapter to main for ICU4X and to unicode-rs for unicode-rs. (Leave idna_mapping at main.)

If you also have reqwest next to these, add:

[patch.crates-io]
url = { path = "../rust-url/url/" }
form_urlencoded = { path = "../rust-url/form_urlencoded/" }

(Trying to patch idna directly didn’t work for me.)

[TheBlueMatt]

Honestly I'd like a way to opt out of IDN handling entirely - in most applications if a domain has unicode in it I can handle it on the frontend and get the punycode version.

[TheBlueMatt]

In fact, I'd strongly prefer the option to opt my entire application out of IDN handling entirely purely for homograph attack reasons. Not only does it remove code (yay!) but also makes my application (which has no use for IDNs, and in fact in may cases is requesting from URLs where other higher-level specifications mandate the lack of IDN usage) more secure!

[hsivonen]

@TheBlueMatt , noted, but turning off IDN handling entirely is out of scope for the event of folks being unhappy about the implications of using ICU4X.

[TheBlueMatt]

Yea, that's totally fair, just highlighting it as a thing to consider as there may be nontrivial overlap between the groups.

[sffc]

I had also thought it might be appropriate to take what we currently have with the ICU4X dependency (including the opportunity for incremental improvements) and make it the default in rust-url 3.0, keeping rust-url 2.0 on the current implementation. Then people need to effectively "opt in" to the worse compile time but better runtime characteristics.

[hsivonen]

@TheBlueMatt

Yea, that's totally fair, just highlighting it as a thing to consider as there may be nontrivial overlap between the groups.

As a technical matter, I observe that your earlier comment said "in most applications if a domain has unicode in it I can handle it on the frontend and get the punycode version." Allowing Punycode through would require something more specific than taking the current idna_adapter design and replacing it with a stub implementation. A mere stub implementation of the current idna_adapter API would have the effect of rejecting Punycode labels, too.

@sffc

Then people need to effectively "opt in" to the worse compile time but better runtime characteristics.

This can become a problem if parts of the ecosystem stay on url 2 as a rejection of compile times. I think it would be worse for the ecosystem to have a split between url 2 and url 3 compared to providing the idna_adapter solution with both url 2 and url 3. The latter would not give an incentive to stay back on url 2 in order to avoid ICU4X compile times.

If we put the idna_adapter solution out there with other things being equal, then the crates.io download stats would become a rough telemetry indicator of how much the ecosystem really cares about avoiding ICU4X compile times. (Yes, there's the issue that some CI systems redownload crates on every run and projects that vendor dependencies don't show up as lots of crates.io downloads.)

[Manishearth]

The unicode-rs back end takes a new dependency on unicode-joining-type.

Not necessarily, the data could be managed by this crate, which already maintains a copy of some Unicode data. I think the unicode-joining-type situation is more or less orthogonal to this.

TL;DR: I have implemented a prototype (READMEs and metadata unpolished, repos not in the right org, crates not on crates.io) of a back end adapter for idna 1.0.x where ICU4X is the default and top-level dependents can (once published) opt into the unicode-rs back end by downgrading a crate called idna_adapter from its 1.2.x version stream to its 1.1.x version stream.

cc @valenting

One thing missing from this plan is whether or not the Servo team is or ought to commit to a maintenance plan for idna_adapter 1.1.x. I think this might need to be explicitly discussed by the Servo TSC: if our documented way of telling people to obtain the old behavior is "pin the older version", we need to decide under what situations we keep that old version maintained (otherwise in a year or so we'll be in a situation where the solution which we tell people about doesn't work).

I'm not actually sure we need separate crates if this is going to be the default anyway