Skip to content

Instantly share code, notes, and snippets.

@evanw
Created June 15, 2016 05:51
Show Gist options
  • Save evanw/06e074a1d6d5c21e8d32e2c26de07714 to your computer and use it in GitHub Desktop.
Save evanw/06e074a1d6d5c21e8d32e2c26de07714 to your computer and use it in GitHub Desktop.
/*
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment