Large stack size of yyParser::yy_reduce in debug builds

[ignatz]

Maybe you're aware of this already...

TL;DR: the sum of local variables in yy_reduce is larger than 1MB in debug builds. Which means that trivial parses will fail automatically for debug builds on some systems (e.g. Windows).

Context

I'm using sqlite3-parser and got a report by someone building on Windows that their default stack size of 1MB isn't enough. I don't have Windows and I found this quite curious but was able to reproduce by limiting stack size. I found that yyParser::yy_reduce was the culprit.

$ ulimit -S -s 1024
$ cargo run --example sql_cmd "CREATE TABLE _procedure(name text primary key, type text, body text)"
...
thread 'main' has overflowed its stack

0x0000555555599f11 in sqlite3_parser::parser::parse::yyParser::yy_reduce (self=<error reading variable: Cannot access memory at address 0x526>,
    yyruleno=<error reading variable: Cannot access memory at address 0x7fffffef760e>, yy_look_ahead=0, yy_lookahead_token=0x55555569c088 <log::MAX_LOG_LEVEL_FILTER>)
    at target/debug/build/sqlite3-parser-afeaa46f3a33d80e/out/parse.rs:4169
4169        fn yy_reduce(
(gdb) bt
#0  0x0000555555599f11 in sqlite3_parser::parser::parse::yyParser::yy_reduce (self=<error reading variable: Cannot access memory at address 0x526>,
    yyruleno=<error reading variable: Cannot access memory at address 0x7fffffef760e>, yy_look_ahead=0, yy_lookahead_token=0x55555569c088 <log::MAX_LOG_LEVEL_FILTER>)
    at target/debug/build/sqlite3-parser-afeaa46f3a33d80e/out/parse.rs:4169
#1  0x00005555555c68ba in sqlite3_parser::parser::parse::yyParser::sqlite3Parser (self=0x7fffffffc2d8, yymajor=sqlite3_parser::dialect::token::TokenType::TK_TABLE, yyminor=...)
    at target/debug/build/sqlite3-parser-afeaa46f3a33d80e/out/parse.rs:6571
#2  0x000055555558b542 in sqlite3_parser::lexer::sql::{impl#1}::next (self=0x7fffffffc2d8) at src/lexer/sql/mod.rs:205
#3  0x000055555556cd03 in sql_cmd::main () at examples/sql_cmd.rs:14

I looked at the generated code and was first a bit puzzled. It seems to be an instance of: https://internals.rust-lang.org/t/match-expressions-use-a-lot-of-stack-space-in-debug-mode/17173. (match expressions, ifs, local scopes... all the same). I was able to "verify" this behavior by removing stack allocations in unused branches until above program would eventually run. Feels like spooky action at a distance :)

Possible Solutions

• My first instinct was to look for code-gen attributes to tell the rust compiler to always overlap local variables but didn't find anything. Hopefully, I'm just ignorant
• Reduce local allocations, e.g. move branches into inlined functions, optimize stack size of AST types, ... 🤷
• Ignore this issue

Curious to hear your thoughts

[gwenn]

See #8

[ignatz]

Awesome! I see: tursodatabase/libsql#1051 is the same issue. Do you forsee #8 to be enough or just a piece in the puzzle?

[gwenn]

I only guess: the main difference between the C parser and Rust parser is the AST (and tagged union vs enum)...

[ignatz]

The other major difference is the compiler. Reserving space for all variables in all scopes and mutually exclusive branches in debug builds is a bespoke choice of the rust compiler

[gwenn]

Indeed, in release mode:

$ ulimit -S -s 128
[vagrant@archlinux lemon-rs]$ cargo  run -r --example sql_cmd "CREATE TABLE _procedure(name text primary key, type text, body text)"
    Finished `release` profile [optimized] target(s) in 0.03s
     Running `target/release/examples/sql_cmd 'CREATE TABLE _procedure(name text primary key, type text, body text)'`
CREATE TABLE _procedure (name text PRIMARY KEY, type text, body text);

[gwenn]

Could you please confirm that if we simply the actions (almost no local variables), we should reduce the stack size ?
By actions, I mean like:

lemon-rs/src/parser/parse.y

Lines 295 to 299 in 6f46367

	ccons(A) ::= DEFAULT term(X). {
	let name = self.ctx.constraint_name();
	let constraint = ColumnConstraint::Default(X);
	A = NamedColumnConstraint{ name, constraint };
	}

And do you know how to monitor the max stack size used by one program (maybe dtrace) ?

[ignatz]

Could you please confirm that if we simply the actions (almost no local variables), we should reduce the stack size ?

I don't know. We would need to test if they get elided. At the end of the day, the compiler still has to reserve space for temporaries. How, when and where is an implementation detail. Also not all temporaries could be removed because of borrow checker rules etc.

What I originally had in mind, which should work:

impl yyParser<'_> {
    fn yy_reduce(...) {
      // ...
      match yyruleno {
        // ...
        28 => {
         {
           let col = self.yy_move(-1).yy444();
           let cd = ColumnDefinition{ col_name: col.0, col_type: col.1, constraints: self.yy_move(0).yy305() };
           let mut map = IndexMap::new();
           ColumnDefinition::add_column(&mut map, cd)?;
           yylhsminor = YYMINORTYPE::yy285( map);
         }
         self[-1].minor = yylhsminor;
       }
       // ...
      }
      // ...
    }
}

to

impl yyParser<'_> {
    fn yy_reduce(...) {
      // ...
      match yyruleno {
        // ...
        28 => {
           self[-1].minor = yylhsminor = self.branch_28(...);
       }
       // ...
      }
      // ...
    }

    #[inline]
    fn branch_28(&mut self, ...) {
       let col = self.yy_move(-1).yy444();
       let cd = ColumnDefinition{ col_name: col.0, col_type: col.1, constraints: self.yy_move(0).yy305() };
       let mut map = IndexMap::new();
       ColumnDefinition::add_column(&mut map, cd)?;
       return  YYMINORTYPE::yy285( map);
   }
}

Do you forsee #8 to be enough or just a piece in the puzzle?

To be more explicit, what I meant is that even getting slightly below 1MB isn't great since the stack is a shared resource. So if my bigger program already uses a few hundred KB, it would still be great for trivial a parse to work. Less is always better. That said, reducing the enum size would be nice because it also helps release builds despite not being a pressing issue.

Also there's clearly limits. I don't know what you had in mind. At the end of the day, the enum, i.e. tagged union, is always as big as its biggest member. We could probably squeeze some bytes with alignment/packing but the biggest wins would certainly be to move data on the heap, which would in turn come with some performance cost.

And do you know how to monitor the max stack size used by one program (maybe dtrace) ?

I was just looking. In principle you shouldn't need tracing or other runtime introspection, since the stack layout is determined at compile-time.

Sadly there doesn't seem to be any official tooling. And all the community tools depend on unstable APIs and eventually throw in the towel. I tried https://github.com/japaric/cargo-call-stack but couldn't get it to work.
Alternatively, one should be able to pass "-Cllvm-args=--stack-size-section" but haven't tried to extract the object information yet.

For runtime introspection you should also be able to just substract the address of a parent frame variable from the address of a child frame variable. To get the stack size of a specific object you can use size_of::<T>().

[gwenn]

We could probably squeeze some bytes with alignment/packing but the biggest wins would certainly be to move data on the heap, which would in turn come with some performance cost.

We already need to box recursive type like Expr so that should not be a problem.

[ignatz]

Then #79 should be fine.

If nothing else it let me calculate that yy_reduce is allocating space for ~470 instances of Stmt (stack-delta / (s0 - s1)). This also means that if we were to further half Stmt's size, we'd only safe an additional ~110kb or 14% of total stack size.

As opposed to pushing branches into their own stack frames, which would reduce the overall stack size to a few kB similar to release builds for arguably quite some work.

[ignatz]

Friendly ping

[gwenn]

Maybe as a workaround:
https://stackoverflow.com/questions/60751806/how-to-compile-some-dependencies-with-release
(I need time to investigate)

[ignatz]

Awesome, I think that's more than acceptable. Thanks.

Just for future reference: my PR is as minimal as possible. I simply looked at which types was the largest, thus defining the size of the enum/union and shrunk it, then did the same to the second largest, ... until I felt I had enough buffer with with respect to the 1MB Windows default stack size.

Even with a higher optimization level (-O1 is plenty) there's no guarantee that things will fit given that the stack is a shared resource so some reduction in size like my PR or something else would still be appreciated. Thanks