match_stack_space.rs

/*
This demonstrates a problem I ran into when writing a parser in Rust. It
appears that adding more branches to a match expression causes the function
to consume more stack space. The stack space used in this example isn't too
extreme but in my actual parser, each function call uses around 15kb of stack
space which adds up very quickly. It only takes around 30 nested calls to
use 512kb of stack space, after which a stack overflow crash occurs.

Here's the output of this program on https://play.rust-lang.org/:

small:
stack space: 0.3kb
stack space: 0.7kb
stack space: 1.0kb
stack space: 1.4kb
stack space: 1.7kb
stack space: 2.1kb
stack space: 2.4kb
stack space: 2.8kb
stack space: 3.1kb
stack space: 3.4kb
stack space: 3.8kb
large:
stack space: 0.6kb
stack space: 1.3kb
stack space: 1.9kb
stack space: 2.6kb
stack space: 3.2kb
stack space: 3.8kb
stack space: 4.5kb
stack space: 5.1kb
stack space: 5.8kb
stack space: 6.4kb
stack space: 7.0kb
*/

enum Token {
  T0,
  T1,
  T2,
  T3,
  T4,
  T5,
  T6,
  T7,
  T8,
  T9,
  T10,
  T11,
  T12,
  T13,
  T14,
  T15,
  T16,
  T17,
  T18,
  T19,
  T20,
  T21,
  T22,
  T23,
  T24,
  T25,
  T26,
  T27,
  T28,
  T29,
  T30,
  T31,
  T32,
  T33,
  T34,
  T35,
  T36,
  T37,
  T38,
  T39,
  T40,
  T41,
  T42,
  T43,
  T44,
  T45,
  T46,
  T47,
  T48,
  T49,
}

fn stack_depth() -> u64 {
  let x = 0;
  unsafe {
    let raw: u64 = std::mem::transmute(&x);
    raw
  }
}

fn small(token: Token, count: u32, base: u64) {
  println!("stack space: {:.1}kb", (base - stack_depth()) as f64 / 1024.0);

  if count > 0 {
    match token {
      Token::T0 => small(token, count - 1, base),
      Token::T1 => small(token, count - 1, base),
      Token::T2 => small(token, count - 1, base),
      Token::T3 => small(token, count - 1, base),
      Token::T4 => small(token, count - 1, base),
      Token::T5 => small(token, count - 1, base),
      Token::T6 => small(token, count - 1, base),
      Token::T7 => small(token, count - 1, base),
      Token::T8 => small(token, count - 1, base),
      Token::T9 => small(token, count - 1, base),
      _ => small(token, count - 1, base),
    }
  }
}

fn large(token: Token, count: u32, base: u64) {
  println!("stack space: {:.1}kb", (base - stack_depth()) as f64 / 1024.0);

  if count > 0 {
    match token {
      Token::T0 => large(token, count - 1, base),
      Token::T1 => large(token, count - 1, base),
      Token::T2 => large(token, count - 1, base),
      Token::T3 => large(token, count - 1, base),
      Token::T4 => large(token, count - 1, base),
      Token::T5 => large(token, count - 1, base),
      Token::T6 => large(token, count - 1, base),
      Token::T7 => large(token, count - 1, base),
      Token::T8 => large(token, count - 1, base),
      Token::T9 => large(token, count - 1, base),
      Token::T10 => large(token, count - 1, base),
      Token::T11 => large(token, count - 1, base),
      Token::T12 => large(token, count - 1, base),
      Token::T13 => large(token, count - 1, base),
      Token::T14 => large(token, count - 1, base),
      Token::T15 => large(token, count - 1, base),
      Token::T16 => large(token, count - 1, base),
      Token::T17 => large(token, count - 1, base),
      Token::T18 => large(token, count - 1, base),
      Token::T19 => large(token, count - 1, base),
      Token::T20 => large(token, count - 1, base),
      Token::T21 => large(token, count - 1, base),
      Token::T22 => large(token, count - 1, base),
      Token::T23 => large(token, count - 1, base),
      Token::T24 => large(token, count - 1, base),
      Token::T25 => large(token, count - 1, base),
      Token::T26 => large(token, count - 1, base),
      Token::T27 => large(token, count - 1, base),
      Token::T28 => large(token, count - 1, base),
      Token::T29 => large(token, count - 1, base),
      Token::T30 => large(token, count - 1, base),
      Token::T31 => large(token, count - 1, base),
      Token::T32 => large(token, count - 1, base),
      Token::T33 => large(token, count - 1, base),
      Token::T34 => large(token, count - 1, base),
      Token::T35 => large(token, count - 1, base),
      Token::T36 => large(token, count - 1, base),
      Token::T37 => large(token, count - 1, base),
      Token::T38 => large(token, count - 1, base),
      Token::T39 => large(token, count - 1, base),
      Token::T40 => large(token, count - 1, base),
      Token::T41 => large(token, count - 1, base),
      Token::T42 => large(token, count - 1, base),
      Token::T43 => large(token, count - 1, base),
      Token::T44 => large(token, count - 1, base),
      Token::T45 => large(token, count - 1, base),
      Token::T46 => large(token, count - 1, base),
      Token::T47 => large(token, count - 1, base),
      Token::T48 => large(token, count - 1, base),
      Token::T49 => large(token, count - 1, base),
    }
  }
}

fn main() {
  let base = stack_depth();

  println!("small:");
  small(Token::T0, 10, base);

  println!("large:");
  large(Token::T0, 10, base);
}