Passing closures arround beyond one call causes compiler to hang

[Hugobros3]

I hit a compiler hang when trying refactor the BVH builder i'm workin on to use functional interfaces. The compiler just gets stuck maxing out one core and eats RAM until I kill it. It got up to 8Gb at one point, so I don't believe giving it more would help.

I bisected the problem down to that part of my code: https://github.com/AnyDSL/bvh/blob/119b05091e3ea59136018bfec0213f48815ec584/src/builder.impala#L38

I made a derived standalone example that somewhat narrows down the problem. I have an outer recursive function, then an inner helper recursive function that has it's number of iterations known at compile-time (the original code merges nodes of a binary tree into either a quad or an octree), the helper function also needs to perform recursion and to touch variables within a closure. Performing either of these two tasks in that helper function causes the hang. They are commented out here:

extern fn break_compiler() -> i32 {

    let mut acc = 0;
    let incr = @ || { acc++; }; // captures acc

    outer_recursive(5, incr) + acc
}

fn inner_recursive(j: i32, limit: i32, incr2: (fn () -> ())) -> () {
    if(j == 0) {
        return()
    } else {
        if(limit > 0) {
             inner_recursive( j - 1, limit - 1, incr2);
             inner_recursive( j - 1, limit - 1, incr2);
        } else {
            // uncommenting either makes the compiler loop forever and eat memory
            //let child = outer_recursive(j - 1, incr2);
            //incr2();
        }
    }
}

fn outer_recursive(i: i32, incr: (fn () -> ())) -> i32 {
    let inner_recursion_depth = 2;
    let infinite_recursion = 1; // set to 0 for infinite recursion

    if i == 0 {
        return(1)
    }

    incr();

    inner_recursive(i - 1, inner_recursion_depth, incr);
    inner_recursive(i - 2, inner_recursion_depth, incr);

    outer_recursive(i - infinite_recursion, incr) * i
}

This is seemingly not the same issue as #76, since I tried to reproduce that one and it's not causing me any issues. I'm also unsure as to how to work around the issue

[Hugobros3]

Equivalent C++ code that worked prior to the refactor: https://github.com/AnyDSL/bvh/blob/119b05091e3ea59136018bfec0213f48815ec584/src/standalone.cpp#L162

[madmann91]

You need to place explicit annotations to make the compiler finish quicker:

extern fn break_compiler() -> i32 {

    let mut acc = 0;
    let incr = @ || { acc++; }; // captures acc

    outer_recursive(5, incr) + acc
}

fn @(?j & ?limit) inner_recursive(j: i32, limit: i32, incr2: (fn () -> ())) -> () {
    if j == 0 {
        return()
    } else if limit > 0 {
         inner_recursive(j - 1, limit - 1, incr2);
         inner_recursive(j - 1, limit - 1, incr2);
    } else {
        // uncommenting either makes the compiler loop forever and eat memory
        //let child = outer_recursive(j - 1, incr2);
        //incr2();
    }
}

fn @(?i) outer_recursive(i: i32, incr: (fn () -> ())) -> i32 {
    let inner_recursion_depth = 2;
    let infinite_recursion = 1; // set to 0 for infinite recursion

    if i == 0 {
        return(1)
    }

    incr();

    inner_recursive(i - 1, inner_recursion_depth, incr);
    inner_recursive(i - 2, inner_recursion_depth, incr);

    outer_recursive(i - infinite_recursion, incr) * i
}

[Hugobros3]

Issue solved thanks to @madmann91's explanations. Though I guess the compiler could warn you when this happens (via some form of sanity check)?

[madmann91]

That's not possible due to the halting problem: The compiler cannot figure out whether your function terminates or not.

[Hugobros3]

But you don't have to solve the halting problem, you can simply monitor the compiler memory usage & time spend processing the function and notify the user via the console, print something such as "hey the compiler is having a hard time processing this, maybe take a second look at your code" when it's abnormally high. It's not a huge improvement, just a small usability tweak.

[madmann91]

Agreed, but we do not really have this at the top of our list. We may do this in the next version of Impala. Right now, you can use top to monitor the cpu time and memory.