Unbounded stack growth during interpretation

Bug #408420 reported by Matt Giuca
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Mars
Fix Released
Critical
Matt Giuca

Bug Description

Something is causing interpret.m to be non-tail-recursive, which means each time the execution enters a new basic block, the Mercury stack is pushed.

This means execution uses O(n) space after time n, which is incredibly bad. It means Mars can't handle programs which run for any real length of time.

A quick scan of interpret.m doesn't help -- everything appears to be tail-recursive.

This bug may just wait until a new execution engine is written (interpretation of a bytecode in C, or something along those lines).

Tags: interpreter

Related branches

Matt Giuca (mgiuca)
Changed in mars:
assignee: nobody → Matt Giuca (mgiuca)
importance: Undecided → Critical
status: New → Confirmed
Matt Giuca (mgiuca)
Changed in mars:
status: Confirmed → Triaged
Matt Giuca (mgiuca)
tags: added: interpreter
Revision history for this message
Matt Giuca (mgiuca) wrote :

A detailed study of interpret.m shows the following relationships:

exec_block:
    exec_block_body
exec_block_body:
    foldl(exec_instr)
    exec_block

The mutual recursion between exec_block and exec_block_body is causing problems with the last-call optimizer in Mercury. It seems like a bug in Mercury but it's pretty hard to tell (it's some kind of heuristic). From experimenting, commenting out the calls to exec_instr fixes the problem (which makes no sense -- it isn't involved in either lastcall). Also it appears to be the call to exec_block_body which is pushing the stack; the call to exec_block extends the stack by 0, while the call to exec_block_body extends it by 96 bytes.

From what I have gathered from these experiments, Mercury *always* handles self-recursion properly but doesn't always handle mutual recursion if there are other complex calls. (It handles mutual recursion in some cases though). The solution should just be to manually inline exec_block_body into exec_block, making it self-recursion.

Revision history for this message
Matt Giuca (mgiuca) wrote :

Also note that there is a second issue which affects stack usage for execution: each instruction in a block is executed at a different stack location (actually the stack addresses *ascend* rather than descending, meaning the stack is shrinking). That's because the instructions in a block are executed in a foldr (in exec_block_body) rather than a foldl.

Obviously not ideal (it means linear stack space is used rather than constant), but it's still linear in the size of the block, which is constant in the runtime of the program (it's a nuisance, but it doesn't cause this bug).

Note that you can use context.debug_stackframe to print out these stackframes.

Revision history for this message
Matt Giuca (mgiuca) wrote :

Fixed in trunk r891 (manually inlined exec_block_body into exec_block).
Note that this does *not* make Mars programs tail-call-safe (Mars programs themselves will experience unbounded stack growth on recursion). But it makes iteration in Mars (while loops) execute in constant space.

Changed in mars:
status: Triaged → Fix Committed
milestone: none → 0.2.1
Matt Giuca (mgiuca)
Changed in mars:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.