Superlinear compile time for large arrays of constants

[RalfJung]

pub static FIELDS: [&i32; BIG_NUMBER] =[
    &("bar", 42, "foo", 3.14).1,
   ...
];

takes superlinear time to compile as BIG_NUMBER increases:

6 * 1024: 4s
12 * 1024: 20s
24 * 1024: 131s

Built using CARGO_INCREMENTAL=0 cargo build --release on current nightly.

Looks at least quadratic to me.

Cc @oli-obk

Python script to generate code

#!/usr/bin/python3
import sys

SIZE = int(sys.argv[1]) * 1024

def print_array_elems(elem):
    sys.stdout.write("[\n")
    for i in range(SIZE):
        sys.stdout.write("    "+elem+",\n")
    sys.stdout.write("]")

def print_array(name, elem_type, elem):
    sys.stdout.write("pub static {}: [{}; {}] =".format(name, elem_type, SIZE))
    print_array_elems(elem)
    sys.stdout.write(";\n")

print_array("FIELDS", "&i32", '&("bar", 42, "foo", 3.14).1')

[nagisa]

This, I believe, is a duplicate of… (takes a look through I-compiletime)… let’s say #37155.

[RalfJung]

FWIW, the quadratic complexity occurs already with nightly-2018-07-07, i.e., before the CTFE loop checker landed.

EDIT: In fact, even nightly-2017-10-01 has the problem already. That's before miri was put into rustc. So I think @nagisa you are right, this is probably an ancient issue.

[nagisa]

Lets close this in order to not clutter the issue list then.

[nagisa]

Since I’m pretty sure this is a duplicate of one of those I-compiletime issues. I encourage to post your test case on one of those.