Use fast_reject in coherence

[arielb1]

libcore seems to spend several seconds in coherence checking the #[derive] impls. Using fast_reject should make this faster.

[retep998]

This is especially prominent in winapi which spends the majority of its time in coherence checking (and will only get worse as I add more things).

time: 0.124     parsing
time: 0.000     recursion limit
time: 0.002     gated macro checking
time: 0.038     configuration 1
time: 0.000     crate injection
time: 0.014     macro loading
time: 0.000     plugin loading
time: 0.000     plugin registration
time: 0.294     expansion
time: 0.009     complete gated feature checking 1
time: 0.111     configuration 2
time: 0.058     maybe building test harness
time: 0.052     prelude injection
time: 0.005     checking that all macro invocations are gone
time: 0.007     complete gated feature checking 2
time: 0.064     assigning node ids and indexing ast
time: 0.005     external crate/lib resolution
time: 0.008     language item collection
time: 0.296     resolution
time: 0.007     lifetime resolution
time: 0.000     looking for entry point
time: 0.005     looking for plugin registrar
time: 0.028     region resolution
time: 0.004     loop checking
time: 0.005     static item recursion checking
time: 0.085     type collecting
time: 0.011     variance inference
time: 18.252    coherence checking
time: 3.895     type checking
time: 0.952     const checking
time: 0.053     privacy checking
time: 0.003     stability index
time: 0.010     intrinsic checking
time: 0.008     effect checking
time: 0.034     match checking
time: 0.014     liveness checking
time: 0.169     borrow checking
time: 0.238     rvalue checking
time: 0.011     reachability checking
time: 0.049     death checking
time: 0.569     stability checking
time: 0.000     unused lib feature checking
time: 2.470     lint checking
time: 0.000     resolving dependency formats
time: 4.093     translation
  time: 0.076   llvm function passes
  time: 0.021   llvm module passes
  time: 1.040   codegen passes
  time: 0.011   codegen passes
time: 1.334     LLVM passes
time: 0.231     linking

[arielb1]

partially fixed by #24965. We could still use fast-reject for all types, through.

[retep998]

Yep, my times seem to have improved significantly

time: 0.155     parsing
time: 0.000     recursion limit
time: 0.039     configuration 1
time: 0.002     gated macro checking
time: 0.000     crate injection
time: 0.015     macro loading
time: 0.000     plugin loading
time: 0.000     plugin registration
time: 0.302     expansion
time: 0.007     complete gated feature checking 1
time: 0.108     configuration 2
time: 0.062     maybe building test harness
time: 0.052     prelude injection
time: 0.003     checking that all macro invocations are gone
time: 0.008     complete gated feature checking 2
time: 0.057     assigning node ids and indexing ast
time: 0.005     external crate/lib resolution
time: 0.008     language item collection
time: 0.265     resolution
time: 0.008     lifetime resolution
time: 0.000     looking for entry point
time: 0.004     looking for plugin registrar
time: 0.021     region resolution
time: 0.004     loop checking
time: 0.006     static item recursion checking
time: 0.076     type collecting
time: 0.008     variance inference
time: 0.251     coherence checking
time: 1.974     type checking
time: 0.203     const checking
time: 0.047     privacy checking
time: 0.002     stability index
time: 0.010     intrinsic checking
time: 0.007     effect checking
time: 0.035     match checking
time: 0.015     liveness checking
time: 0.160     borrow checking
time: 0.190     rvalue checking
time: 0.012     reachability checking
time: 0.038     death checking
time: 0.493     stability checking
time: 0.000     unused lib feature checking
time: 0.663     lint checking
time: 0.000     resolving dependency formats
time: 2.876     translation
  time: 0.072   llvm function passes
  time: 0.022   llvm module passes
  time: 1.033   codegen passes
  time: 0.012   codegen passes
time: 1.325     LLVM passes
time: 0.250     linking

[steveklabnik]

Triage: unsure what the status is here.

[ishitatsuyuki]

@retep998 Can you check if this is still an issue today?

[retep998]

> cargo rustc --features "everything impl-default" -- -Ztime-passes
   Compiling winapi v0.3.4 (file:///C:/Users/Peter/Code/winapi-rs)
  time: 0.630; rss: 130MB       parsing
  time: 0.000; rss: 130MB       recursion limit
  time: 0.000; rss: 130MB       crate injection
  time: 0.000; rss: 130MB       plugin loading
  time: 0.000; rss: 130MB       plugin registration
  time: 2.792; rss: 472MB       expansion
  time: 0.000; rss: 472MB       maybe building test harness
  time: 0.034; rss: 473MB       maybe creating a macro crate
  time: 0.088; rss: 473MB       creating allocators
  time: 0.107; rss: 473MB       AST validation
  time: 0.364; rss: 512MB       name resolution
  time: 0.116; rss: 512MB       complete gated feature checking
  time: 0.479; rss: 648MB       lowering ast -> hir
  time: 0.131; rss: 648MB       early lint checks
  time: 0.480; rss: 651MB       indexing hir
  time: 0.000; rss: 408MB       load query result cache
  time: 0.000; rss: 408MB       looking for entry point
  time: 0.003; rss: 408MB       looking for plugin registrar
  time: 0.044; rss: 408MB       loop checking
  time: 0.034; rss: 408MB       attribute checking
  time: 0.125; rss: 411MB       stability checking
  time: 0.615; rss: 488MB       type collecting
  time: 0.014; rss: 488MB       outlives testing
  time: 0.032; rss: 492MB       impl wf inference
  time: 0.449; rss: 524MB       coherence checking
  time: 0.016; rss: 524MB       variance testing
  time: 1.237; rss: 663MB       wf checking
  time: 1.406; rss: 730MB       item-types checking
  time: 1.953; rss: 817MB       item-bodies checking
  time: 0.479; rss: 864MB       rvalue promotion
  time: 0.881; rss: 871MB       privacy checking
  time: 0.062; rss: 871MB       intrinsic checking
  time: 0.144; rss: 875MB       match checking
  time: 0.070; rss: 875MB       liveness checking
  time: 2.893; rss: 1040MB      borrow checking
  time: 0.055; rss: 1049MB      MIR borrow checking
  time: 0.029; rss: 1049MB      MIR effect checking
  time: 0.251; rss: 1050MB      death checking
  time: 0.000; rss: 1050MB      unused lib feature checking
  time: 0.804; rss: 1067MB      lint checking
  time: 0.000; rss: 1067MB      dumping chalk-like clauses
  time: 0.000; rss: 1067MB      resolving dependency formats
    time: 3.527; rss: 1149MB    write metadata
    time: 0.014; rss: 1149MB    translation item collection
    time: 0.000; rss: 1149MB    codegen unit partitioning
    time: 0.000; rss: 1150MB    translate to LLVM IR
    time: 0.000; rss: 1150MB    assert dep graph
    time: 0.000; rss: 1150MB    llvm function passes [winapi0]
    time: 0.000; rss: 1151MB    serialize dep graph
    time: 0.000; rss: 1151MB    llvm module passes [winapi0]
  time: 3.548; rss: 1151MB      translation
    time: 0.002; rss: 1138MB    codegen passes [winapi0]
  time: 0.006; rss: 1135MB      LLVM passes
  time: 0.000; rss: 221MB       serialize work products
  time: 0.091; rss: 221MB       linking
    Finished dev [unoptimized + debuginfo] target(s) in 22.8 secs

Coherence doesn't seem to be a major bottleneck for winapi at the moment, but there is some room to be faster.

[arielb1]

The original issue was fixed a long time ago. Further improvements are probably a part of Chalk.

Note that IIRC coherence is mainly slow because it takes the blame for loading metadata.