Repository navigation
Slower binary, slower compiler, bigger binary since some days #46897
Description
In the 2017-12-14 Nightly I've seen a significant (almost 20%) compilation-time increase when I use --emit=metadata on my code. And the successive day (2017-12-15) the compilation got a bit slower still and the run-time of the binary also got about 8% slower. The successive days the situation kept going slightly worse. Extracting parts of my code to show compiler/code performance is not easy, so I've composed this benchmark function (that solves an Euler problem. If this code isn't enough I will write other similar benchmarks):
Source code
use std::mem::size_of;
macro_rules! isqrt { ($e:expr, $t:ident) => ((($e) as f64).sqrt() as $t) }
struct SieveBits { bits: Vec<usize> }
impl SieveBits {
const BPC: usize = size_of::<usize>() * 8;
fn is_bit_set(bits: &[usize], i: usize) -> bool {
debug_assert!(i < bits.len() * Self::BPC);
let offset = i / Self::BPC;
let mask = 1 << (i % Self::BPC);
unsafe { (*bits.get_unchecked(offset) & mask) != 0 }
}
fn reset_bit(bits: &mut [usize], i: usize) {
debug_assert!(i < bits.len() * Self::BPC);
let offset = i / Self::BPC;
let mask = 1 << (i % Self::BPC);
unsafe { *bits.get_unchecked_mut(offset) &= !mask; }
}
fn new(m: usize) -> Self {
if m < 2 {
return Self { bits: vec![] };
}
let mut primes = vec![std::usize::MAX; (m / 3) / Self::BPC + 1];
Self::reset_bit(&mut primes, 0);
let lim = isqrt!(m, usize) + 1;
let mut i = 5;
let mut step = 2;
while i < lim {
if Self::is_bit_set(&primes, i / 3) {
let mut j = i * i;
let mut step2 = step;
while j < m {
Self::reset_bit(&mut primes, j / 3);
j += step2 * i;
step2 = 6 - step2;
}
}
i += step;
step = 6 - step;
}
Self { bits: primes }
}
fn is_prime(&self, i: usize) -> bool {
if i == 2 || i == 3 { true }
else if i % 2 == 0 || i % 3 == 0 { false }
else { Self::is_bit_set(&self.bits, i / 3) }
}
}
fn eratosthenes_sieve_u32(limit: usize) -> Vec<u32> {
assert!(limit <= std::u32::MAX as usize);
#[inline(always)]
fn fill_u8(data: &mut [u8], value: u8) {
unsafe {
std::ptr::write_bytes(data.as_mut_ptr(), value, data.len());
}
}
const L1D_CACHE_SIZE:u32 = 32_768;
let mut result = vec![];
if limit < 2 {
return result;
} else {
result.push(2);
}
let lsqrt = isqrt!(limit, u32);
let mut is_prime = vec![1u8; lsqrt as usize + 1];
let mut i = 2;
while i * i <= lsqrt {
unsafe {
if *is_prime.get_unchecked(i as usize) != 0 {
let mut j = i * i;
while j <= lsqrt {
*is_prime.get_unchecked_mut(j as usize) = 0;
j += i;
}
}
}
i += 1;
}
let segment_size = lsqrt.max(L1D_CACHE_SIZE);
let mut s: usize = 3;
let mut n: usize = 3;
let mut sieve = vec![1u8; segment_size as usize]; // Vector used for sieving.
let mut primes: Vec<u32> = vec![];
let mut next: Vec<u32> = vec![];
let mut low: usize = 0;
while low <= limit {
fill_u8(&mut sieve, 1);
let high = (low + segment_size as usize - 1).min(limit);
unsafe {
while s * s <= high {
if *is_prime.get_unchecked(s) != 0 {
primes.push(s as u32);
next.push((s * s - low) as u32);
}
s += 2;
}
for (i, &p) in primes.iter().enumerate() {
let k = p * 2;
let mut j = *next.get_unchecked(i);
while j < segment_size {
*sieve.get_unchecked_mut(j as usize) = 0;
j += k;
}
*next.get_unchecked_mut(i) = j - segment_size;
}
while n <= high {
if *sieve.get_unchecked(n - low) != 0 { // n is a prime.
result.push(n as u32);
}
n += 2;
}
}
low += segment_size as usize;
}
result
}
fn main() {
fn e249() -> u64 {
const N: usize = 5_000;
const M: u64 = 10_000_000_000_000_000_u64;
let check_every = (((1u64 << 63) / M) as f64).log2().ceil() as usize;
let primes = eratosthenes_sieve_u32(N);
let mut ways = vec![0u64; primes.iter().sum::<u32>() as usize + 1];
ways[0] = 1;
let mut max: usize = 0;
for (i, &p) in primes.iter().enumerate() {
for j in (0 .. max + 1).rev() {
unsafe {
*ways.get_unchecked_mut(j + p as usize) =
*ways.get_unchecked(j + p as usize) +
*ways.get_unchecked(j);
}
}
if (i + 1) % check_every == 0 {
for w in ways[.. max + 1].iter_mut() {
*w = *w % M;
}
}
max += p as usize;
}
let sieve = SieveBits::new(max);
let mut count = ways[2];
let mut i = 3;
while i <= max {
if sieve.is_prime(i) {
count = (count + ways[i]) % M;
}
i += 2;
}
count
}
assert_eq!(e249(), 9_275_262_564_250_418);
}Compiled with:
rustc -C opt-level=3 -C target-cpu=native -C panic=abort test.rs
host: x86_64-pc-windows-gnu
Runtime:
f8af59d 2017-12-13: 0.30 seconds
edbd7d2 2017-12-20: 0.53 seconds
Asm from the the 2017-12-13 compiler:
https://gist.github.com/anonymous/5c475819a2b7d0e01c036582c76cbd19
Asm from the the 2017-12-20 compiler:
https://gist.github.com/anonymous/bb984787c802da22b76c182d0f260872
Activity
arielb1 commentedon Dec 20, 2017
Could someone try to reproduce and bisect this?
arielb1 commentedon Dec 20, 2017
cc @kennytm I think
arielb1 commentedon Dec 20, 2017
We shouldn't have such big asm differences between successive nightlies, and I don't see anything suspicious in the middle, so it would be good to try and nail down the commit that made the difference.
arielb1 commentedon Dec 21, 2017
I see a regression with this code (note: this is distinct from #46863).
@kennytm the bad code accesses the stack pointer (%rsp) You have a fast network connection and know how to use
bisect-rust. Could you please do so?You should grep for
%rspto tell if the code is bad - the bad code includes the following line:Deewiant commentedon Dec 21, 2017
I bisected @leonardo-m's original example, just testing the speed of the executable created by a stage 1
rustc -C opt-level=3 -C target-cpu=native -C panic=abort test.rsand came upon 8a26e04 (PR #46623) as the culprit: the runtime on my machine is around 0.3 seconds before that commit and around 0.7 seconds after.@arielb1's latest example also has a clear difference. The code before that commit (just disassembling the
.rlib):And after:
arielb1 commentedon Dec 21, 2017
That's unfortunate. cc @eddyb
eddyb commentedon Dec 21, 2017
cc @bluss
arielb1 commentedon Dec 21, 2017
Thanks @Deewiant
We're looking into it
leonardo-m commentedon Dec 21, 2017
@Deewiant >just testing the speed of the executable
I am not sure if they share the same cause, first a significant compiler performance decrease using --emit=metadata , then the successive Nightly the decrease of the produced binary performance.
arielb1 commentedon Dec 21, 2017
@leonardo-m
They should not. However, quite a few big commits landed in the Dec 14 nightly.
If you could provide an example that exhibits the slowdown with
--emit=metadata, that would allow us to fix it (is the Dec 13 nightly faster than the Dec 14 nightly which has the same speed, but worse runtime performance, than the Dec 15 nightly?)Auto merge of #46925 - arielb1:make-the-trains-run-on-time, r=arielb1
4 remaining items
leonardo-m commentedon Dec 22, 2017
The --emit=metadata times are computed as the minimum of four tries. Their variance is very small (on the order of +-0.05) so I think they are reliable.
The binary run-time is the minimum of 5 runs, their variance is higher perhaps because they do some I/O, despite using a SSD, about +-0.12.
The compilation is slow so there I've done only one time, so those values are the less reliable, but differences above 1.5 seconds should be reliable.
arielb1 commentedon Dec 22, 2017
@eddyb
For the compilation time issue, maybe there was a bug in NLL that made it active without it being enabled.
For the run-time issue, we need to actually investigate this.
eddyb commentedon Dec 22, 2017
@arielb1 As in, investigate the cause of the run-time fluctuations and how it unregressed?
arielb1 commentedon Dec 22, 2017
This is my good old friend the
sinktorpedo.LLVM optimizes
<Range as Iterator>::nextinto this:This is basically equivalent to this pseudo-Rust code
After the "non-constant-address" write is generated, LLVM is sunk - LLVM has no way of getting rid of the non constant address, and no way of optimizing accesses to the target
Optionwith that non-constant address.arielb1 commentedon Dec 22, 2017
Upstream LLVM (that's the yet-to-be-released LLVM 6) has this patch, which avoids the SimplifyCfg sink problem by not running sinking before inlining
llvm-mirror/llvm@7034870
I have confirmed that - e.g. this code is optimized correctly with the new
optUntil then, I think representing small enums using a struct (rather than an array) should work around this problem.
leonardo-m commentedon Dec 23, 2017
With the 2017-12-22 Nightly all the problems are back:
arielb1 commentedon Dec 23, 2017
@eddyb
Coud you open a PR that turns small unions into LLVM structs (rather than arrays)? That should fix the problem.
leonardo-m commentedon Dec 26, 2017
The binaries generated by the last Nightly (1.24.0-nightly 4a7c072 2017-12-25) is further few percents slower (perhaps because of thinLTO?), the compilation times can't be compared now.
kennytm commentedon Dec 26, 2017
@leonardo-m Is there more stable measure besides compile time / run time? They can be affected too easily by the environment especially when the run time is expected to take less than 1 second. The generated assembly size seems to be a good measure.
Auto merge of #47007 - eddyb:issue-46897, r=arielb1
eddyb commentedon Dec 27, 2017
Please re-test next nightly and reopen if not fixed.
leonardo-m commentedon Dec 28, 2017
The run-time of the binary is now OK. The compilation time with --emit=metadata is still quite large.
eddyb commentedon Dec 28, 2017
@leonardo-m Can you open a separate one for compilation times? Seems to be a separate issue.
leonardo-m commentedon Jan 8, 2018
@eddyb , I've tried here: #47267