[m-users.] How to write stack-friendly mercury-code?
paul at bone.id.au
Mon Mar 28 21:51:02 AEDT 2016
On Mon, Mar 28, 2016 at 11:51:52AM +0200, Dirk Ziegemeyer wrote:
> when I increase the data volume that is processed by a mercury application, the windows-version (asm_fast.gc/i686-w64-mingw32.static) stops at runtime with this error message:
> *** Mercury runtime: caught segmentation violation ***
> This may have been caused by a stack overflow, due to unbounded recursion.
> exiting from signal handler
> The Mac OS X version (hlc.gc/x86_64-apple-darwin14.5.0) still works.
> Up to now, I did not care at all about stack consumption. Now, I’d like to learn how to write stack-friendly mercury code in order to avoid overflows at runtime.
> To iterate over data, the application uses predicates from the mercury library like list.foldl2, list.map, map.foldl and list.append.
> Thank you in advance for any guidance on writing robust mercury code.
Hi Dirk, There's a couple of things you can do.
+ Make code tail recursive:
This is pretty obvious but I've included it because how to do this is
not so obvious.
This is tail recursive:
foldl(_, , !Acc).
foldl(P, [X | Xs], !Acc) :-
foldl(P, Xs, !Acc).
But this is not, even though the last call is a recursive call (unlike
map(_, , ).
map(P, [X | Xs], [Y | Ys]) :-
map(P, Xs, Ys).
The construction of [Y | Ys] executes after the recursive call. So the
recursive call cannot be a tail call (see LCMC below for now to fix
this). So code can _look_ tail recursive that isn't. Lots of code can
be transformed into something that uses an accumulator like foldl. This
usually trades stack space for heap space. So it's often easier just to
add more stack space.
This also isn't tail recursive, X and Y are both outputs:
foo(..., X, Y) :-
foo(..., Y, X).
Even though there is no construction after the recursive call, the
outputs must be placed in different registers because of their
respective order. So work needs to be done after the recursive call,
therefore the recursive call isn't a tail call.
+ Reduce the amount of stack space used.
This is a neat trick. If one loop can be easily refactored into two
loops with a depth counter then the number of stack frames used at any
given time can be halved.
foo_inner(N, ...) :-
( if N = 0 then
true % continue with the outer loop, removing the inner 1000
foo_inner(N - 1, ...).
Pick a constant value that only just fits within stack.
+ Enable --last-call-modulo-recursion optimisation (LCMC).
This will make map tail recursive by performing the construction [Y | Ys]
before the recursive call, and filling in the value Ys in this term
within the recursive call.
+ Use a segmented stack
If you use --stack-segments (an stseg grade component, compatible with
low level C grades) then a segmented stack will be used, a segmented
stack grows and shrinks as necessary. Unbounded recursion can now cause
your computer to thrash, rather than just crashing your program. This
is the easiest option, but it doesn't reduce your program's memory usage.
It's a good option if the limit is the size of the stack, and not how
much RAM you have.
+ Increase the size of the stack.
In low-level graces, like asm_fast, put MERCURY_OPTIONS="--detstack-size
N" in your environment. Check the Mercury user's guide.
I've been working on some changes to Mercury that will make it easier for
developers to find which parts of their program are potentially causing
crashes due to stack exhaustion.
More information about the users