Processing a List of 100,000 strings creates a recursion 100,000 layers deep
Generates text that depends on changing data (like dynamic HTML).
Brought to you by:
revusky
Menu
▾
▴
1 Attachments
#90 Processing a List of 100,000 strings creates a recursion 100,000 layers deep
After about 10,000 recursive calls, the stackOverflow occurs. It happens because the list of size 100,000 is actually 99,999 levels deep of a binary tree where the left side is very deep ConcatenatedSequence and the right side is a 1-level deep SimpleSequence.
What I see in the stacktrace is that groups.ftl calls " ${sampleSQLBuilder.insertGroup(group, publicLayouts)}" and from here, we go into group.ftl which calls "<#assign layoutSets = dataFactory.newLayoutSets(group.groupId, publicLayouts?size)>". And, at this point, the publicLayouts variable is already 100,000 entries large. So, enumerating the size is a recursive call through the 99,999 entry tree which causes the stackOverflow.
We are using Freemarker 2.3.17.
After seeing the problem occur, I put some System.out.println statements in AddConcatExpression.java[ConcatenatedSequence.size()]:151
Here's the groups.ftl file we used.
Here's the group.ftl file we used.
Here's the file which creates the large array.
In particular, the line of interest is: <#assign publicLayouts = publicLayouts + [layout]>
Here, 'layout' is a large string.
The problem seems to occur because AddConcatExpression.java[ConcatenatedSequence]:136 is a binary tree. One possible solution that I had considered and was wondering if it might be considered by others is the idea of checking if the items being added are both ((instanceof SimpleSequence) == true). If so, we can create a new SimpleSequence and add the values from both sequences to this one item. Thus, the 'left' object would be the entire new list and the 'right' object would be null.
This approach would perhaps help to reduce the number of recursions that would occur when enumerating the size of the array.
Here's a sample stack trace for this problem.
Here's the full stack trace from the debugger.
It's know behavior, and it's documented that what you are doing is not the intended usage of sequence concatenation (http://freemarker.org/docs/dgui_template_exp.html#dgui_template_exp_sequenceop_cat). You don't want to concatenate sequences here after all, you want to add elements to it. So it's not really a bug.
The root of the problem is that there are no mutable collections (or maps) in FTL. You aren't supposed to build complex data-structures with it. I admit it would be better if FTL supports that too, but there's a lot of other higher priority things to do, so it won't happen any time soon. So for now, either move the sequence building out of the template, or use something like FMPP's mutable hashes and sequences (http://fmpp.sourceforge.net/pphash.html#sect43).
Another route is making the treatment of immutable collections more efficient. Like we could maintain a balanced tree of starting indexes and associated with the sequence objects. Also, if we want to add elements one-by-one, it's waste to crated a 1-long list from each of them. But again the problem is the lack of developer time. It would be good to have, but more important issues are waiting to be solved.
BTW, you are talking about strings. But the problem is with sequences, not strings. Concatenating strings doesn't make recursive data-structures.
Ticket moved from /p/freemarker/bugs/392/
Thank you for the explanation.
As you explained it, it makes perfect sense to mark this as an improvement.
And, you are correct, I wrote "strings" when I should have wrote "sequences".
Hopefully, one day this feature will be added to the product.