Extremely slow compilation when the code initializes nested arrays

[koute]

The problem

Having the curve25519-dalek crate as a dependency anywhere in the dependency graph makes it impossible to do any fuzzying since it takes an extremely long time for it to finish compiling through cargo fuzz build.

(This is most likely a problem in either rustc or LLVM; posting an issue about it here for visibility, and because I don't have the time to actually dig to the very bottom of this.)

Reproduction (real world)

1. git clone https://github.com/dalek-cryptography/curve25519-dalek.git
2. cd curve25519-dalek
3. cargo fuzz init
4. cargo fuzz build

Reproduction (minimal)

1. cargo new --lib foobar
2. Paste this into foobar/src/lib.rs:

#[derive(Copy, Clone)]
pub struct FieldElement(pub (crate) [u64; 5]);

impl Default for FieldElement {
    #[inline(always)]
    fn default() -> Self {
        FieldElement([ 1, 0, 0, 0, 0 ])
    }
}

macro_rules! impl_basepoint_table {
    (Name = $name:ident, LookupTable = $table:ident) => {
        #[derive(Clone)]
        pub struct $name(pub(crate) [$table<FieldElement>; 32]);

        impl $name {
            #[inline(never)]
            pub fn create() -> $name {
                $name([$table::default(); 32])
            }
        }
    }
}

impl_basepoint_table! {Name = EdwardsBasepointTableRadix16, LookupTable = LookupTableRadix16}
impl_basepoint_table! {Name = EdwardsBasepointTableRadix32, LookupTable = LookupTableRadix32}
impl_basepoint_table! {Name = EdwardsBasepointTableRadix64, LookupTable = LookupTableRadix64}
impl_basepoint_table! {Name = EdwardsBasepointTableRadix128, LookupTable = LookupTableRadix128}
impl_basepoint_table! {Name = EdwardsBasepointTableRadix256, LookupTable = LookupTableRadix256}

macro_rules! impl_lookup_table {
    (Name = $name:ident, Size = $size:expr) => {

        #[derive(Copy, Clone)]
        pub struct $name<T>(pub(crate) [T; $size]);

        impl<T: Copy + Default> Default for $name<T> {
            #[inline(always)]
            fn default() -> $name<T> {
                $name([T::default(); $size])
            }
        }

    }
}

impl_lookup_table! {Name = LookupTableRadix16,  Size =   8}
impl_lookup_table! {Name = LookupTableRadix32,  Size =  16}
impl_lookup_table! {Name = LookupTableRadix64,  Size =  32}
impl_lookup_table! {Name = LookupTableRadix128, Size =  64}
impl_lookup_table! {Name = LookupTableRadix256, Size = 128}

6. cd foobar
7. cargo fuzz init
8. cargo fuzz build

Expected behavior

The crate compiles fast; cargo build of the minimal reproduction crate takes less than 1s, and cargo fuzz build should take a comparable amount of time (excluding the time it takes to build the dependencies it needs).

Actual behavior

The compilation takes a very long time; the minimal reproduction example takes over 1 minute to compile on my machine. The real world reproduction takes significantly longer (don't know how long exactly; I got tired of waiting).

Workaround

For the minimal reproduction:

 impl Default for FieldElement {
-    #[inline(always)]
+    #[inline(never)]
     fn default() -> Self {
         FieldElement([ 1, 0, 0, 0, 0 ])
     }
 }

For the curve25519-dalek crate:

diff --git a/src/backend/serial/u64/field.rs b/src/backend/serial/u64/field.rs
index a73d4b5..ec1def3 100644
--- a/src/backend/serial/u64/field.rs
+++ b/src/backend/serial/u64/field.rs
@@ -270,6 +270,7 @@ impl FieldElement51 {
     }
 
     /// Construct one.
+    #[inline(never)]
     pub fn one() -> FieldElement51 {
         FieldElement51([ 1, 0, 0, 0, 0 ])
     }

This makes it compile fast again.

Versions

• rustc 1.62.0-nightly (69a5d2481 2022-04-27)
• cargo-fuzz 0.11.0 (installed from crates.io)
• curve25519-dalek 0d49dfacf66bed4b41e445d0e6942b3c27f3b263
• Arch Linux running on amd64