Crate with large static map in external crate fails to compile

[urschrei]

Possibly related: #36799
When attempting to compile https://github.com/urschrei/lonlat_bng using cargo test or cargo build --release on OS X using beta (5276ba7) or nightly (b1e3176), the compilation step doesn't complete (or at least, it hadn't after around 11 hours). It also times out on Linux Nightly and Beta, using Travis.

On current OS X Stable (021bd29), it compiles as expected within ~95s locally, and on Linux Stable, using Travis, although rustdoc for the external crate fails with an OOM error on Linux.

This is probably due to the size of the static map in the external crate (https://github.com/urschrei/ostn15_phf), which is around 40.9mb.

[nagisa]

Seems like a regression in the item-types checking stage.

[nagisa]

last good: 5d994d8b7 2017-01-05
first bad: 6f1ae663e 2017-01-06

These are the changes. There’s a number of possibly relevant ones.

[eddyb]

@nagisa I wonder if it's a stray potentially-infinite loop in #38069, cc @canndrew.

[eddyb]

cc @rust-lang/compiler Maybe someone else knows something.

[canndrew]

Here's a backtrace of where the compiler is after running for a couple of minutes.

#0  0x00007ffff478fc02 in _$LT$rustc_data_structures..obligation_forest..ObligationForest$LT$O$GT$$GT$::process_obligations::h0ff99cdf3dcc3ab2 () from /home/shum/.local/bin/../lib/../lib/librustc-579b052cb6742dd6.so
#1  0x00007ffff48edcf0 in rustc::traits::fulfill::FulfillmentContext::select_where_possible::hd82f7b0c63e2b550 () from /home/shum/.local/bin/../lib/../lib/librustc-579b052cb6742dd6.so
#2  0x00007ffff4f9097a in rustc_typeck::check::FnCtxt::select_obligations_where_possible::hac13e60e80dbcba0 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#3  0x00007ffff4f8b6bb in rustc_typeck::check::FnCtxt::resolve_type_vars_with_obligations::h2178d7ff44c1db76 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#4  0x00007ffff4f3ad28 in rustc_typeck::check::coercion::_$LT$impl$u20$rustc_typeck..check..FnCtxt$LT$$u27$a$C$$u20$$u27$gcx$C$$u20$$u27$tcx$GT$$GT$::try_coerce::hd1aefddffb2298ea () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#5  0x00007ffff4f3c8de in rustc_typeck::check::demand::_$LT$impl$u20$rustc_typeck..check..FnCtxt$LT$$u27$a$C$$u20$$u27$gcx$C$$u20$$u27$tcx$GT$$GT$::demand_coerce::hc4a73b302852d680 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#6  0x00007ffff4ed3e9e in core::ops::impls::_$LT$impl$u20$core..ops..FnOnce$LT$A$GT$$u20$for$u20$$RF$$u27$a$u20$mut$u20$F$GT$::call_once::h4cb23ef6f4635259 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#7  0x00007ffff4eba56d in _$LT$rustc_data_structures..accumulate_vec..AccumulateVec$LT$A$GT$$u20$as$u20$core..iter..traits..FromIterator$LT$$LT$A$u20$as$u20$rustc_data_structures..array_vec..Array$GT$..Element$GT$$GT$::from_iter::h29dc4c517cc097a4 ()
   from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#8  0x00007ffff4f12ca8 in _$LT$T$u20$as$u20$rustc..ty..context..InternIteratorElement$LT$T$C$$u20$R$GT$$GT$::intern_with::h6ca07eab6913ecc4 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#9  0x00007ffff4f9f42f in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#10 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#11 0x00007ffff4ed3e8d in core::ops::impls::_$LT$impl$u20$core..ops..FnOnce$LT$A$GT$$u20$for$u20$$RF$$u27$a$u20$mut$u20$F$GT$::call_once::h4cb23ef6f4635259 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#12 0x00007ffff4eba56d in _$LT$rustc_data_structures..accumulate_vec..AccumulateVec$LT$A$GT$$u20$as$u20$core..iter..traits..FromIterator$LT$$LT$A$u20$as$u20$rustc_data_structures..array_vec..Array$GT$..Element$GT$$GT$::from_iter::h29dc4c517cc097a4 ()
   from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#13 0x00007ffff4f12ca8 in _$LT$T$u20$as$u20$rustc..ty..context..InternIteratorElement$LT$T$C$$u20$R$GT$$GT$::intern_with::h6ca07eab6913ecc4 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#14 0x00007ffff4f9f42f in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#15 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#16 0x00007ffff4fa1f44 in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#17 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#18 0x00007ffff4fa09e5 in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#19 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#20 0x00007ffff4f91df7 in rustc_typeck::check::FnCtxt::check_argument_types::h985e4ddeee75a37e () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#21 0x00007ffff4f6b9f7 in rustc_typeck::check::callee::_$LT$impl$u20$rustc_typeck..check..FnCtxt$LT$$u27$a$C$$u20$$u27$gcx$C$$u20$$u27$tcx$GT$$GT$::confirm_builtin_call::h2cd5aff1bed1fea3 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#22 0x00007ffff4f6a8ae in rustc_typeck::check::callee::_$LT$impl$u20$rustc_typeck..check..FnCtxt$LT$$u27$a$C$$u20$$u27$gcx$C$$u20$$u27$tcx$GT$$GT$::check_call::he10eb01456e5f5af () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#23 0x00007ffff4f9dab8 in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#24 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#25 0x00007ffff4f9a0e1 in rustc_typeck::check::FnCtxt::check_expr_struct_fields::h931680d8935d7d17 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#26 0x00007ffff4fa00c1 in rustc_typeck::check::FnCtxt::check_expr_kind::hadde62228837913a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#27 0x00007ffff4f9cd0e in rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref::h64489ddc97d36346 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#28 0x00007ffff4f896df in rustc_typeck::check::check_const_with_type::hcaf874c983aa4780 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#29 0x00007ffff4f8371d in rustc_typeck::check::check_item_type::h46851e4b2a32991a () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#30 0x00007ffff4f7c6ed in _$LT$rustc_typeck..check..CheckItemTypesVisitor$LT$$u27$a$C$$u20$$u27$tcx$GT$$u20$as$u20$rustc..hir..intravisit..Visitor$LT$$u27$tcx$GT$$GT$::visit_item::h224c1bbad7d277a3 ()
   from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#31 0x00007ffff4f7ea82 in rustc_typeck::check::check_item_types::h2c121166792403e4 () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#32 0x00007ffff4feb8ef in rustc_typeck::check_crate::hcb32a063b7119bae () from /home/shum/.local/bin/../lib/../lib/librustc_typeck-46efec171d67cc9c.so
#33 0x00007ffff7b460a5 in rustc_driver::driver::phase_3_run_analysis_passes::_$u7b$$u7b$closure$u7d$$u7d$::h3312aec6762531cd () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#34 0x00007ffff7aaebf5 in rustc::ty::context::TyCtxt::create_and_enter::hda1e948f4c0f1e0f () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#35 0x00007ffff7b24044 in rustc_driver::driver::compile_input::h2990bdc0fc07a424 () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#36 0x00007ffff7b6b60e in rustc_driver::run_compiler::h5bf788ee0bf13463 () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#37 0x00007ffff7a759ac in std::panicking::try::do_call::hf0803e51e3e750e8 () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#38 0x00007ffff77a6207 in __rust_maybe_catch_panic () from /home/shum/.local/bin/../lib/libstd-413b1fd81b83156f.so
#39 0x00007ffff7a9dd73 in _$LT$F$u20$as$u20$alloc..boxed..FnBox$LT$A$GT$$GT$::call_box::hcc35ddf0d1c1f13d () from /home/shum/.local/bin/../lib/librustc_driver-fba78511ce6cdc51.so
#40 0x00007ffff779be31 in std::sys::imp::thread::Thread::new::thread_start::h1f6ee946a79c10d0 () from /home/shum/.local/bin/../lib/libstd-413b1fd81b83156f.so
#41 0x00007ffff042d1f4 in start_thread () from /nix/store/amjgskg17wv125v9kahqdfxh8sx6mxgp-glibc-2.24/lib/libpthread.so.0
#42 0x00007ffff745d12f in clone () from /nix/store/amjgskg17wv125v9kahqdfxh8sx6mxgp-glibc-2.24/lib/libc.so.6

[arielb1]

This is #38776 (probably this change) - reverting that PR makes things fast again.

[eddyb]

Huh, why would that not hit caches? Is it because the type needs to be inferred?
Maybe we need a primitive fast-path in there to speed up inference before asking for Neg.
Do binops have such a fast-path?

[nikomatsakis]

@eddyb I don't know, I think the current system for binops can also be slow sometimes. It's been vaguely on my list to investigate that a bit more and see if there are fast paths we can do.

[arielb1]

@eddyb

I think this is encountering the O(n^2) quadratic blowup case badly. In that case, we'll have to add "off-main-path" is-not-unsized "obligations".

[arielb1]

We could also try to solve the O(n^2)ness at the root: for each type variable, maintain a list of obligations it's contained in. Also maintain a stream of changes to type variables. When reselecting, walk over the stream and "unlock" all obligations with type vars inside.

I am not sure whether this has better performance than the current approach in the common case.

[arielb1]

Maybe this is worth doing just for obligations with only int/float variables, tho.

[eddyb]

@arielb1 I just checked and -1: i32 will infer to -(1: i32) before ever creating a Neg obligation.
So no integer variable should ever be created, which means my intuition was wrong.
Do we have a sample of the --pretty=expanded of what phf generates here? If not I'll try.

[eddyb]

cargo rustc -p ostn02_phf -- -Z time-passes finishes in 80 seconds locally (master + #40319):

time: 25.393; rss: 1131MB       item-types checking

EDIT: Oh, cargo build finishes in the expected 90-something seconds, for me.

EDIT2: Sigh, I forgot to pull.

[arielb1]

static OSTN15: phf::Map<i32, (f64, f64, f64)> =
    ::phf::Map{key: 1897749892740154578,
               disps:
                   ::phf::Slice::Static(&[(0, 170), (0, 0), (0, 173586),
                                          (0, 26), (0, 8), (0, 423240),
                                          (0, 71), (0, 23628), (0, 547181),
                                          (0, 161), (0, 66), (0, 674140),
                                          (0, 542973), (0, 563345), (0, 0),
                                          (1, 62), (0, 43), (0, 0), (0, 573),
                                          (0, 84), (0, 0), (0, 606), (0, 58),
                                          (0, 361), (0, 1), (0, 571276),
                                          ...]],
               entries:
                   ::phf::Slice::Static(&[(694236, (96.220, -52.874, 53.638)),
                                          (38959, (95.979, -79.836, 47.366)),
                                          (43143, (95.554, -79.980, 48.109)),
                                          (852252,
                                           (104.950, -51.963, 47.498)),
                                          (475318, (84.242, -61.393, 57.396)),
                                          (44038, (98.999, -81.446, 44.332)),
                                          (439407,
                                           (106.186, -66.038, 44.390)),
                                          (581510, (98.788, -57.675, 50.211)),
                                          (142636, (95.231, -77.339, 51.142)),
                                          (411577, (86.475, -65.328, 56.592)),
                                          (220568, (98.154, -76.414, 48.655)),
                                          (394894, (92.088, -67.370, 54.716)),
                                          (212817, (96.985, -76.296, 49.825)),
                                          (591560,
                                           (105.447, -61.071, 45.110)),
                                          (405480, (95.090, -66.762, 53.378)),
                                          (583579, (97.624, -57.536, 51.590)),
                                          (876103,
                                           (105.441, -51.504, 47.074)),
                                          ...]),};

[eddyb]

What's fast:

struct Map {
    slice: &'static [i8]
}

static FOO: Map = Map {
    slice: &[-1, -1, -1, -1 /* repeated N times */]
};

What's slow:

struct Map<T: 'static> {
    slice: &'static [T]
}

static FOO: Map<i8> = Map {
    slice: &[-1, -1, -1, -1 /* repeated N times */]
};

This is #31260, I'll just go implement it 😆. EDIT: fix confirmed, PR coming up soon.