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. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
