Exponential compile time for the amount of impls.

[wdanilo]

Summary

Hi! After generating over 200 impls with macros, my project build time just grew from a few seconds to 3 hours. Even worse, the compilation time grows exponentially in relation to the number of impls, so I'm reporting a bug. I do not have minimal repro, but I have an open-source code and a simple reproducible recipe.

Description

• There is pub struct Texture<StorageType,InternalFormat,ElemType>.
• StorageType is one of Owned, GpuOnly, and RemoteImage.
• Combination (InternalFormat, ElemType) is approx 70 possibilities.

Then we generate the following impls (if an impl mentions 2 types, then we generate it for each combination), where (S,I,T) stands for (StorageType,InternalFormat,ElemType):

impl InternalFormat for I {...}
impl TextureElement<T> for I {...}

We also generate a single data type gathering all the texture types as variants:

pub enum AnyTextureUniform {
            $( S_I_T(Uniform<Texture<S,I,T>) ),*
}

And a bunch of conversions like

impl From<Uniform<Texture<S, I, T>>> for AnyUniform {...}

Basically, we can assume that for EVERY TEXTURE TYPE WE GENERATE 3 VARIANTS AND APPROXIMATELY 18 IMPLS.

And now the not-fun part. For 8 texture types, it compiles 42s. For 16 types - 1.5 mins. For 32 types - 10 mins. We've got 70 texture types - it takes hours.

Analysis

It seems we've got exponential growth here. Here is a detailed statistics:

How to reproduce

1. Clone the project: https://github.com/luna/ide/tree/wip/wd/rust-bug-68324
2. Run ./scripts/watch.sh - it will compile it and report the time.
3. In the file lib/core/src/system/gpu/data/texture.rs uncomment some lines between 265 and 323. (Each line contains an array of types on the far right - the number of elements is the number of additional texture types we uncomment).
4. Observe the time.

The generation of structs / impls is done in:

• lib/core/src/system/gpu/data/texture.rs line 326
• lib/core/src/system/gpu/data/uniform.rs line 269
• lib/core/src/system/gpu/data/uniform.rs line 272
• lib/core/src/system/gpu/data/uniform.rs line 290

[Aaron1011]

@wdanilo: Do you know when this starting happening for you (bumping stable to stable, nightly to nightly, etc.)?

[wdanilo]

@Aaron1011, sorry for not being precise enough regarding this in my description. It started after adding the impls and structs. Earlier I was not using so many impls.

[nagisa]

What versions of the compiler do you see this behaviour with? Stable? Nightly? Is it a regression? I believe that was the intent behind @Aaron1011’s question.

[wdanilo]

@nagisa I use rustc 1.40.0-nightly. As I replied to @Aaron1011, I do not know if it is a regression. I was not using so many impls before. After generating over 200 impls with macros and noticing that it compiles hours and that the compilation time grows in an exponential way in relation to the number of impls, I filled this bug.

[pnkfelix]

triage: This is a toss-up between P-high and P-medium. For now, assigning P-high priority for the immediate work of determining if this is a regression or not.

Once we have that information, we will revisit the question of prioritization.

[kpp]

Did anyone try to make MRE?

[jdm]

I've started investigating this. Adding a rust-toolchain file to https://github.com/enso-org/ide/tree/wip/wd/rust-bug-68324 that contains nightly-2019-11-04, I've verified that commenting out everything from https://github.com/enso-org/ide/blob/a38038abed8ebe64e93724c83a65ed79ac2ad05f/lib/core/src/system/gpu/data/texture.rs#L262-L323 except the Alpha, Rgb, and Rgba entries yields an incremental compilation time of 20s, and uncommenting everything yields an incremental compilation time of 58s.

[jonas-schievink]

Maybe try this with #69010 applied? The only case of superlinear compile times in the number of impls that I know of is coherence checking, but that is supposed to be O(n²) only, not exponential.

[jackh726]

I'm going to go ahead and close this. I've tried following the repro instructions, but the linked repo is archived and doesn't build (I tried a few things too). If someone else is able to reproduce and confirm the perf problem is still happening, feel free to reopen or open a new issue.

[kpp]

I could not compile it either. Here is what I came up to:

cargo install cargo-watch
cargo install wasm-pack

git clone -b wip/wd/rust-bug-68324 https://github.com/enso-org/ide.git

cd ide
./script/watch.sh

diff --git a/build-utilities/src/lib.rs b/build-utilities/src/lib.rs
index 9bc5f7f4..27b6ba19 100644
--- a/build-utilities/src/lib.rs
+++ b/build-utilities/src/lib.rs
@@ -1,4 +1,4 @@
-#![feature(option_unwrap_none)]
+// #![feature(option_unwrap_none)]
 
 use std::{fs, path};
 use std::io::ErrorKind;
@@ -31,6 +31,6 @@ impl<Str:AsRef<str>> GithubRelease<Str> {
         let result      = fs::remove_file(&file);
         let error       = result.err();
         let fatal_error = error.filter(|err| err.kind() != ErrorKind::NotFound);
-        fatal_error.unwrap_none();
+        assert!(fatal_error.is_none());
     }
 }
diff --git a/lib/core/Cargo.toml b/lib/core/Cargo.toml
index 8aeda162..25fad557 100644
--- a/lib/core/Cargo.toml
+++ b/lib/core/Cargo.toml
@@ -26,7 +26,7 @@ shapely                    = { version = "0.1.0"  , path = "../shapely/impl"  }
 
 bit_field                  = { version = "0.10.0" }
 console_error_panic_hook   = { version = "0.1.6"  }
-enum_dispatch              = { version = "0.2.0"  }
+enum_dispatch              = { version = "0.3.0"  }
 failure                    = { version = "0.1.5"  }
 Inflector                  = { version = "0.11.4" }
 itertools                  = { version = "0.8"    }
diff --git a/lib/core/msdf-sys/Cargo.toml b/lib/core/msdf-sys/Cargo.toml
index 59f13131..5d77db8e 100644
--- a/lib/core/msdf-sys/Cargo.toml
+++ b/lib/core/msdf-sys/Cargo.toml
@@ -15,8 +15,8 @@ basegl-prelude = { version = "0.1.0", path="../../prelude" }
 
 [dev-dependencies]
 wasm-bindgen-test          = "0.3.3"
-futures                    = ""
+futures                    = "*"
 basegl-core-embedded-fonts = { version = "0.1.0", path="../embedded-fonts" }
 
 [build-dependencies]
-basegl-build-utilities = { version = "0.1.0", path="../../../build-utilities" }
\ No newline at end of file
+basegl-build-utilities = { version = "0.1.0", path="../../../build-utilities" }
diff --git a/lib/logger/src/lib.rs b/lib/logger/src/lib.rs
index 420dd368..dd9900c4 100644
--- a/lib/logger/src/lib.rs
+++ b/lib/logger/src/lib.rs
@@ -1,5 +1,5 @@
 #![feature(trait_alias)]
-#![feature(set_stdio)]
+// #![feature(set_stdio)]
 
 use std::fmt::Debug;
 use wasm_bindgen::JsValue;
diff --git a/lib/system/web/src/lib.rs b/lib/system/web/src/lib.rs
index e4a39c39..ce4a4f5c 100644
--- a/lib/system/web/src/lib.rs
+++ b/lib/system/web/src/lib.rs
@@ -1,5 +1,5 @@
 #![feature(trait_alias)]
-#![feature(set_stdio)]
+// #![feature(set_stdio)]
 #![feature(arbitrary_self_types)]
 
 pub mod resize_observer;
@@ -305,12 +305,12 @@ fn _print(msg: &str) -> std::io::Result<()> {
 
 pub fn set_stdout() {
     let printer = Printer::new(_print, true);
-    std::io::set_print(Some(Box::new(printer)));
+    // std::io::set_print(Some(Box::new(printer)));
 }
 
 pub fn set_stdout_unbuffered() {
     let printer = Printer::new(_print, false);
-    std::io::set_print(Some(Box::new(printer)));
+    // std::io::set_print(Some(Box::new(printer)));
 }
 
 #[wasm_bindgen(inline_js = "

I stopped on:

error[E0119]: conflicting implementations of trait `HasFooIndirect` for type `WithFoo<_>`
   --> lib/shapely/impl/src/lib.rs:156:9
    |
153 | /         impl<T>
154 | |         [<Has $name Indirect>] for [<With $name>]<T> {}
    | |_______________________________________________________- first implementation here