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

[Tim Macpherson]

I'm only getting this during stress testing comparisions,

generating  up to 32k of hierachical data nodes under GWT,

whereas Teavm blows at 24k, that's  around 1000 calls in a recursive loop of around 5 functions.

Chrome can handle a lot more than that I think so the stack size error is due to stack memory not height ? 

a little GWT pruning of the stack seems to stop the overflow, it's pruning stack memory ?

The stack trace isn't much help, just mangled functions.

It's best practice to turn recursion into iteration for browser side code ?

GWT doesn't do that because it messes up stack traces.

--
You received this message because you are subscribed to the Google Groups "GWT Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-web-tool...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/google-web-toolkit/d16f0a1f-2394-4ca3-b1cd-9ff29a73585an%40googlegroups.com.

[Colin Alworth]

Seeing the stack trace would be helpful not for the method names, but for the pattern of methods in the stack - if it shows A B C A B C in TeaVM but A A A A in GWT, then we know that GWT is inlining away B and C, so you have a much smaller stack as a result. It might suggest some manual inlining that could get TeaVM performing the way you hope.

If you have a tail recursive function(s) and don't mind losing your stack trace, iteration can be cheaper in multiple ways. Many recursive algorithms also have a natural iterative variation, that may or may not require a Stack of some kind to track details. I wouldn't set a blanket rule on iteration vs recursion - I find recursion easier to write/read/debug, but iteration makes more sense when you know you'll be hundreds or thousands of frames deep when recursing. Finally, there are other ways to handle deeply recursive functions, such as deferring work with Promise, and awaiting results. 

Whatever approach you take, remember to measure twice, cut once.