[m-users.] How to write stack-friendly mercury-code?

[Paul Bone]

On Mon, Mar 28, 2016 at 11:51:52AM +0200, Dirk Ziegemeyer wrote:
> Hi,
> 
> 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) :-
            P(X, !Acc),
            foldl(P, Xs, !Acc).

    But this is not, even though the last call is a recursive call (unlike
    Prolog).

        map(_, [], []).
        map(P, [X | Xs], [Y | Ys]) :-
            P(X, Y),
            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(...).
        foo(...) :-
            foo_inner(1000, ...),
            foo(...).

        foo_inner(N, ...) :-
            ( if N = 0 then
                true % continue with the outer loop, removing the inner 1000
                stack frames
            else
                ...,
                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.

Cheers.


-- 
Paul Bone