Unbounded stack growth during interpretation
Bug #408420 reported by
Matt Giuca
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).
Related branches
Changed in mars: | |
assignee: | nobody → Matt Giuca (mgiuca) |
importance: | Undecided → Critical |
status: | New → Confirmed |
Changed in mars: | |
status: | Confirmed → Triaged |
tags: | added: interpreter |
Changed in mars: | |
status: | Fix Committed → Fix Released |
To post a comment you must log in.
A detailed study of interpret.m shows the following relationships:
exec_block: exec_instr)
exec_block_body
exec_block_body:
foldl(
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.