[
https://issues.apache.org/jira/browse/GROOVY-12333?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18110981#comment-18110981
]
ASF GitHub Bot commented on GROOVY-12333:
-----------------------------------------
paulk-asert opened a new pull request, #2872:
URL: https://github.com/apache/groovy/pull/2872
A few hundred KB of nested delimiters cost tens of seconds, then died - with
a StackOverflowError if the stack ran out first, otherwise by exhausting the
heap. Two independent quadratics, both in the nesting.
Depth was assigned eagerly during assembly. find() builds bottom-up, so a
node is attached to a new parent once per enclosing delimiter, and each attach
re-walked the whole subtree beneath it to restamp depths - quadratic, and one
stack frame per level. Depth is now resolved from the parent chain when first
asked for and cached, along with every ancestor walked on the way, so resolving
a whole tree costs O(n) and any node is O(1) once resolved. The walk is
iterative, so nesting no longer consumes stack. A chain 20,000 deep goes from
3646ms to 51ms, and one 10,000 deep whose depths are never read from 853ms to
4ms.
Attaching a node whose depth was already read caches it against a parent
chain that is about to change, so the attach drops the cached depths beneath
it. That walk is iterative too, prunes at any node whose depth was never read,
and does not run during find(), which reads no depths while assembling.
Each node also held its own copy of its matched text. Groups nest, so their
spans overlap and those copies duplicate most of the document once per level:
64KB of nesting retained about 990MB. A node now keeps the source and slices on
demand, which is what the start/end offsets it already carried were for, so
retention is proportional to the input - the same 64KB now retains 2MB. Reading
every group's text costs what it did; reading one group's text repeatedly now
slices each time rather than returning a stored copy, about 2ns per call.
The package-private six-argument constructor consequently takes the source
rather than the already-sliced text, and its offsets index into it. Passing
text detached from its offsets is no longer meaningful, so the range check that
compared them is now a bounds check against the source. find() is the only
production caller and always had the source to hand; it no longer allocates a
substring per group.
The source must be effectively immutable for as long as a node lives. find()
already flattens its input to a String before matching, which guarantees that.
> Improve performance for findBalancedGroups
> ------------------------------------------
>
> Key: GROOVY-12333
> URL: https://issues.apache.org/jira/browse/GROOVY-12333
> Project: Groovy
> Issue Type: Improvement
> Reporter: Paul King
> Assignee: Paul King
> Priority: Major
>
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
