Why Rust compiler (1.77.0 to 1.85.0) reserves 2x extra stack for large enum?

compiler
1

Hello, team,

Almost a year ago I found an interesting case with Rust compiler version <= 1.74.0 reserving stack larger than needed to model Result type with boxed error, the details are available here - Rust: enum, boxed error and stack size mystery. I could not find the root cause that time, only that updating to Rust >= 1.75.0 fixes the issue.

Today I tried the code again on Rust 1.85.0, https://godbolt.org/z/6d1hxjnMv, and to my surprise, the method fib2 now reserves 8216 bytes (4096 + 4096 + 24), but it feels that around 4096 bytes should be enough.

example::fib2:
 push   r15
 push   r14
 push   r12
 push   rbx
 sub    rsp,0x1000            ; reserve 4096 bytes on stack
 mov    QWORD PTR [rsp],0x0
 sub    rsp,0x1000            ; reserve 4096 bytes on stack
 mov    QWORD PTR [rsp],0x0
 sub    rsp,0x18              ; reserve 24 bytes on stack
 mov    r14d,esi
 mov    rbx,rdi
 ...
 add    rsp,0x2018
 pop    rbx
 pop    r12
 pop    r14
 pop    r15
 ret

I checked all the versions from 1.85.0 to 1.77.0, and all of them reserve 8216 bytes. However, the version 1.76.0 reserves 4104 bytes, https://godbolt.org/z/o9reM4dW8

Rust code

extern crate thiserror;

use std::hint::black_box;

use thiserror::Error;

#[derive(Error, Debug)]
#[error(transparent)]
pub struct Error(Box<ErrorKind>);

#[derive(Error, Debug)]
pub enum ErrorKind {
    #[error("IllegalFibonacciInputError: {0}")]
    IllegalFibonacciInputError(String),
    #[error("VeryLargeError:")]
    VeryLargeError([i32; 1024])
}

pub fn fib0(n: u32) -> u64 {
    match n {
        0 => panic!("zero is not a right argument to fibonacci_reccursive()!"),
        1 | 2 => 1,
        3 => 2,
        _ => fib0(n - 1) + fib0(n - 2),
    }
}

pub fn fib1(n: u32) -> Result<u64, Error> {
    match n {
        0 => Err(Error(Box::new(ErrorKind::IllegalFibonacciInputError("zero is not a right argument to Fibonacci!".to_string())))),
        1 | 2 => Ok(1),
        3 => Ok(2),
        _ => Ok(fib1(n - 1).unwrap() + fib1(n - 2).unwrap()),
    }
}

pub fn fib2(n: u32) -> Result<u64, ErrorKind> {
    match n {
        0 => Err(ErrorKind::IllegalFibonacciInputError("zero is not a right argument to Fibonacci!".to_string())),
        1 | 2 => Ok(1),
        3 => Ok(2),
        _ => Ok(fib2(n - 1).unwrap() + fib2(n - 2).unwrap()),
    }
}


fn main() {
    use std::mem::size_of;
    println!("Size of Result<i32, Error>: {}", size_of::<Result<i32, Error>>());
    println!("Size of Result<i32, ErrorKind>: {}", size_of::<Result<i32, ErrorKind>>());
    
    let r0 = fib0(black_box(20));
    let r1 = fib1(black_box(20)).unwrap();
    let r2 = fib2(black_box(20)).unwrap();

    println!("r0: {}", r0);
    println!("r1: {}", r1);
    println!("r2: {}", r2);
}

Is this an expected behaviour? Do you know what is going on?

Thank you.

PS: Copy of Reddit post Why Rust compiler (1.77.0 to 1.85.0) reserves 2x extra stack for large enum?

1 Like
2

Could you try using cargo-bisect-rustc to narrow the introduction of the issue to a particular nightly? If you can do that, that should make it easy to pinpoint the introduction of the problem. (Unless it turns out that there's an LLVM version bump in that timeframe.)

3

This is probably LLVM being conservative about address uniqueness. This version doesn't reserve extra stack space:

pub fn fib2(n: u32) -> Result<u64, ErrorKind> {
    match n {
        0 => Err(ErrorKind::IllegalFibonacciInputError(
            "zero is not a right argument to Fibonacci!".to_string(),
        )),
        1 | 2 => Ok(1),
        3 => Ok(2),
        _ => {
            let a = {
                let x = fib2(n - 1);
                unw(&x)
            };
            let b = {
                let x = fib2(n - 2);
                unw(&x)
            };
            Ok(a + b)
        }
    }
}

fn unw<T: Copy, E>(x: &Result<T, E>) -> T {
    *x.as_ref().unwrap_or_else(|_| panic!())
}

and as far as I tested, all of the modifications here are currently necessary to convince LLVM that the return slots are allowed to have the same address for both recursive calls.

2 Likes
5

Thanks for the explaination, yet another instance of scopes being very important for Rust compiler!

6

Thanks for the suggestion, didn't know about that tool. The run cargo bisect-rustc --start 1.76.0 --end 1.77.0 --script ./test.sh -vv -- build --release found the regerssion:

********************************************************************************
Regression in nightly-2024-01-16
********************************************************************************

fetching https://static.rust-lang.org/dist/2024-01-15/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2024-01-15: 40 B / 40 B [======================================================================================================================] 100.00 % 1013.29 KB/s converted 2024-01-15 to 30dfb9e046aeb878db04332c74de76e52fb7db10
fetching https://static.rust-lang.org/dist/2024-01-16/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2024-01-16: 40 B / 40 B [=========================================================================================================================] 100.00 % 1.08 MB/s converted 2024-01-16 to 714b29a17ff5fa727c794bbb60bfd335f8e75d42
looking for regression commit between 2024-01-15 and 2024-01-16
fetching (via remote github) commits from max(30dfb9e046aeb878db04332c74de76e52fb7db10, 2024-01-13) to 714b29a17ff5fa727c794bbb60bfd335f8e75d42
ending github query because we found starting sha: 30dfb9e046aeb878db04332c74de76e52fb7db10
get_commits_between returning commits, len: 7
  commit[0] 2024-01-14: Auto merge of #119970 - GuillaumeGomez:rollup-p53c19o, r=GuillaumeGomez
  commit[1] 2024-01-15: Auto merge of #119581 - Nadrieril:detangle-arena, r=compiler-errors
  commit[2] 2024-01-15: Auto merge of #119508 - Zalathar:graph, r=compiler-errors
  commit[3] 2024-01-15: Auto merge of #119878 - scottmcm:inline-always-unwrap, r=workingjubilee
  commit[4] 2024-01-15: Auto merge of #119987 - matthiaskrgr:rollup-f7lkx4w, r=matthiaskrgr
  commit[5] 2024-01-15: Auto merge of #119988 - lnicola:sync-from-ra, r=lnicola
  commit[6] 2024-01-15: Auto merge of #119610 - Nadrieril:never_pattern_bindings, r=compiler-errors
ERROR: no CI builds available between 30dfb9e046aeb878db04332c74de76e52fb7db10 and 714b29a17ff5fa727c794bbb60bfd335f8e75d42 within last 167 days

Repo with code to find regression, REASY/rust-extra-stack-repro

1 Like
7

Thanks for the suggestion, didn't know about that tool. For some reason cannot post text, here what it finds if I run the tool

image
image1498×364 77.5 KB

1 Like
10

That was just the overly cautious spam filter, probably misinterpreting cli tool output here as some kind of weird/spam content, and holding your posts for review as a new user, sorry for that! It should get better once you reach the next "trust level"[1]. (Also, I'll try to reassess the amount of actual spam, and maybe we can turn it a bit less sensitive to begin with, here on the internals forum anyway.)

  1. Get to trust level 1 by…

    • Entering at least 5 topics
    • Reading at least 30 posts
    • Spend a total of 10 minutes reading posts
    ↩︎
4 Likes