GWT resilience to recursion

[Tim Macpherson]

• GWT’s JavaScript Optimization: GWT's compiler is famously aggressive at inlining and "smashing" code. Depending on the complexity of your tree logic, GWT might have been able to flatten certain recursive calls into iterative loops during its permutation phase, effectively creating an implicit trampoline.

That's what AI says, I'm probably hoping in vain for a high-level "compiler nerd" discussion that the current GWT group just isn't primed for.

Yahoo Mail: Search, Organize, Conquer

[Colin Alworth]

Based on my knowledge of the compiler, it is straight up making this up, there's no reality to what it is saying, about inlining being possible for recursive calls, or rewriting to loops. Throwing the word "permutation" in doesn't really help matters, this really isn't specific to how GWT uses permutations at all (but it does sound important I guess). Its unfortunate too, as the logic here is pretty easy to follow and well commented, exactly the kind of thing I would imagine an LLM could take great advantage of.

Both the Java AST's MethodInliner and the JS AST's JsInliner explicitly omit self-recursive from being eligible for inlining, to prevent infinite expansion. In theory there are some specific cases where self-recursive calls could be inlined into themselves and improve matters (via something like "partial inlining" and "outlining"), but we don't do that today, and would only take that on very cautiously.

https://github.com/gwtproject/gwt/blob/main/dev/core/src/com/google/gwt/dev/jjs/impl/MethodInliner.java#L126

https://github.com/gwtproject/gwt/blob/378fd96ed0212a0edbcad58c91042bc21f9ee922/dev/core/src/com/google/gwt/dev/js/JsInliner.java#L1332-L1337

GWT never transforms recursive calls to iterative (though your IDE can likely do this for you in certain cases), that would mess up stack traces even more than we already do.

Mutually-recursive functions are allowed to be inlined into one another, but the compiler will detect if inlining A into B means that B now calls itself, and will forbid further inlining. Consider this code:
String many(int i) {

  if (i <= 0) {

    return "";

  }

  return "a" + more(i);

}

String more(int i) {

  return many(i - 1) + many(i - 1);

}

This is mutually recursive, since each function calls the other. The "many" function could be rewritten to make it easier to optimize, but it is far simpler to just inline away "more":

String many(int i) {

  if (i <= 0) {

    return "";

  }

  return "a" + many(i - 1) + many(i - 1);

}

This also cuts the stack down by half, since a deep call to many(100) calls more(100) calls many(99) calls more(99) calls many(98)... but now many(100) calls many(99) calls many(98)...

For simpler inlining, it might also be that you _almost_ blow the stack in GWT, but a little bit of inlining saves you, but TeaVM doesn't.

JS calling conventions matter here too - GWT's JsInterop means that Java varargs ends up being part of the JS stack instead of being a single array reference on the stack. I don't know how TeaVM handles those cases, but there are places in GWT where we are defensive about keeping that stack size under control.

https://github.com/gwtproject/gwt/blob/378fd96ed0212a0edbcad58c91042bc21f9ee922/user/super/com/google/gwt/emul/java/lang/String.java#L153-L162

Finally, it is possible that TeaVM has to add an extra call in the chain as part of how it emulates the JVM, but I'm not confident of that answer.

Can you share some details of the recursive function, and what the TeaVM stack looks like when it blows? A little information on what that ends up looking like should shed some light here quickly.

[RobW]

We've been using GWT for nearly 20 years now and never seen a single occurence of this. I definitely would treat anything AI says on the matter with extreme suspicion.

-R