Solution for PR #97 Speedup ConcatenatedSequence iteration, but it works differently as the PR.
diff --git a/src/main/java/freemarker/core/AddConcatExpression.java b/src/main/java/freemarker/core/AddConcatExpression.java
index f02be12..077af8d 100644
--- a/src/main/java/freemarker/core/AddConcatExpression.java
+++ b/src/main/java/freemarker/core/AddConcatExpression.java
@@ -191,9 +191,10 @@
return ParameterRole.forBinaryOperatorOperand(idx);
}
- private static final class ConcatenatedSequence
+ // Non-private for unit testing
+ static final class ConcatenatedSequence
implements
- TemplateSequenceModel {
+ TemplateSequenceModel, TemplateCollectionModel {
private final TemplateSequenceModel left;
private final TemplateSequenceModel right;
@@ -214,6 +215,149 @@
int ls = left.size();
return i < ls ? left.get(i) : right.get(i - ls);
}
+
+ @Override
+ public TemplateModelIterator iterator() throws TemplateModelException {
+ return new ConcatenatedSequenceIterator(this);
+ }
+
+ }
+
+ private static class ConcatenatedSequenceIterator implements TemplateModelIterator {
+ /** The path from the root down to the parent of {@link #currentSegment} */
+ private ParentStep parentStep = null;
+
+ private TemplateSequenceModel currentSegment;
+ private int currentSegmentNextIndex;
+ private TemplateModelIterator currentSegmentIterator;
+
+ private boolean hasPrefetchedResult;
+ private TemplateModel prefetchedNext;
+ private boolean prefetchedHasNext;
+
+ public ConcatenatedSequenceIterator(ConcatenatedSequence concatSeq) throws TemplateModelException {
+ // Descent down to the first nested sequence, and memorize the path down there
+ descendToLeftmostSubsequence(concatSeq);
+ }
+
+ private void setCurrentSegment(TemplateSequenceModel currentSegment) throws TemplateModelException {
+ if (currentSegment instanceof TemplateCollectionModel) {
+ this.currentSegmentIterator = ((TemplateCollectionModel) currentSegment).iterator();
+ this.currentSegment = null;
+ } else {
+ this.currentSegment = currentSegment;
+ this.currentSegmentNextIndex = 0;
+ this.currentSegmentIterator = null;
+ }
+ }
+
+ @Override
+ public TemplateModel next() throws TemplateModelException {
+ ensureHasPrefetchedResult();
+
+ if (!prefetchedHasNext) {
+ throw new TemplateModelException("The collection has no more elements.");
+ }
+
+ TemplateModel result = prefetchedNext;
+ hasPrefetchedResult = false; // To consume prefetched element
+ prefetchedNext = null; // To not prevent GC
+ return result;
+ }
+
+ @Override
+ public boolean hasNext() throws TemplateModelException {
+ ensureHasPrefetchedResult();
+ return prefetchedHasNext;
+ }
+
+ private void ensureHasPrefetchedResult() throws TemplateModelException {
+ if (hasPrefetchedResult) {
+ return;
+ }
+
+ while (true) {
+ // Try to fetch the next value from the current segment:
+ if (currentSegmentIterator != null) {
+ boolean hasNext = currentSegmentIterator.hasNext();
+ if (hasNext) {
+ prefetchedNext = currentSegmentIterator.next();
+ prefetchedHasNext = true;
+ hasPrefetchedResult = true;
+ return;
+ }
+ } else if (currentSegment != null) {
+ int size = currentSegment.size();
+ if (currentSegmentNextIndex < size) {
+ prefetchedNext = currentSegment.get(currentSegmentNextIndex++);
+ prefetchedHasNext = true;
+ hasPrefetchedResult = true;
+ return;
+ }
+ } else {
+ // No current segment => We have already reached the end of the last segment in the past
+ prefetchedHasNext = false;
+ hasPrefetchedResult = true;
+ return;
+ }
+
+ // If we reach this, then the current segment was fully consumed, so we switch to the next segment.
+
+ if (parentStep == null) {
+ setIteratorEndWasReached();
+ return;
+ }
+
+ if (!parentStep.rightVisited) {
+ parentStep.rightVisited = true;
+ descendToLeftmostSubsequence(parentStep.concSeq.right);
+ } else {
+ while (true) {
+ // Ascend one level
+ parentStep = parentStep.parentStep;
+
+ if (parentStep == null) {
+ setIteratorEndWasReached();
+ return;
+ }
+
+ if (!parentStep.rightVisited) {
+ parentStep.rightVisited = true;
+ descendToLeftmostSubsequence(parentStep.concSeq.right);
+ break;
+ }
+ }
+ }
+ }
+ }
+
+ private void descendToLeftmostSubsequence(TemplateSequenceModel maybeConcSeq) throws TemplateModelException {
+ while (maybeConcSeq instanceof ConcatenatedSequence) {
+ ConcatenatedSequence concSeq = (ConcatenatedSequence) maybeConcSeq;
+ parentStep = new ParentStep(concSeq, parentStep);
+ maybeConcSeq = concSeq.left;
+ }
+ setCurrentSegment(maybeConcSeq);
+ }
+
+ private void setIteratorEndWasReached() {
+ currentSegment = null;
+ currentSegmentIterator = null;
+ prefetchedNext = null;
+ prefetchedHasNext = false;
+ hasPrefetchedResult = true;
+ }
+
+ private static class ParentStep {
+ private final ConcatenatedSequence concSeq;
+ private final ParentStep parentStep;
+ private boolean rightVisited;
+
+ public ParentStep(ConcatenatedSequence concSeq, ParentStep parentStep) {
+ this.concSeq = concSeq;
+ this.parentStep = parentStep;
+ }
+ }
}
private static class ConcatenatedHash
diff --git a/src/main/java/freemarker/template/Configuration.java b/src/main/java/freemarker/template/Configuration.java
index 2558bfb..a89bb59 100644
--- a/src/main/java/freemarker/template/Configuration.java
+++ b/src/main/java/freemarker/template/Configuration.java
@@ -981,7 +981,7 @@
* <p>
* 2.3.33 (or higher):
* <ul>
- * <li><p>Comparing string is now way faster. If your template does lot of string comparisons, this can
+ * <li><p>Comparing strings is now way faster. If your template does lot of string comparisons, this can
* mean very significant speedup. We now use a simpler way of comparing strings, and because templates
* were only ever allowed equality comparisons between strings (not less-than, or greater-than), it's very
* unlikely to change the behavior of your templates. (Technically, what changes is that instead of using
diff --git a/src/manual/en_US/book.xml b/src/manual/en_US/book.xml
index c1bf77c..1e7a410 100644
--- a/src/manual/en_US/book.xml
+++ b/src/manual/en_US/book.xml
@@ -30072,7 +30072,7 @@
<listitem>
<para><link
xlink:href="https://github.com/apache/freemarker/pull/87">GitHub
- PR 87</link> Comparing string is now way faster, if the <link
+ PR 87</link> Comparing strings is now way faster, if the <link
linkend="pgui_config_incompatible_improvements_how_to_set"><literal>incompatible_improvements</literal>
setting</link> is at least 2.3.33. If your template does lot of
string comparisons, this can mean very significant speedup. With
@@ -30090,6 +30090,24 @@
we still do UNICODE normalization, so combining characters won't
break your comparison.)</para>
</listitem>
+
+ <listitem>
+ <para>When concatenating many sequences (like Java
+ <literal>List</literal>-s) with the <literal>+</literal>
+ operator, iterating through the resulting sequence has become
+ very slow as the number of sequences added increased. Now
+ iteration is reasonably fast, regardless of the number of
+ sequences added. But this still only applies to mere iteration
+ (like using <literal><#list seq as
+ <replaceable>...</replaceable>></literal>, or
+ <literal>seq?join(', ')</literal>). Accessing items by index
+ (like <literal>seq[n]</literal>) is still as slow as it always
+ was. (Note that <literal>+</literal> is still only meant to be
+ used to quickly create a concatenated view from a few sequences,
+ and not for constructing sequences from hundreds of small
+ sequences. So it's still not recommended to concatenate more
+ then a few tens of sequences.)</para>
+ </listitem>
</itemizedlist>
</section>
diff --git a/src/test/java/freemarker/core/ConcatenatedSequenceTest.java b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
new file mode 100644
index 0000000..8cedd9c
--- /dev/null
+++ b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
@@ -0,0 +1,216 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package freemarker.core;
+
+import static org.junit.Assert.*;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.function.Supplier;
+
+import org.junit.Test;
+
+import freemarker.core.AddConcatExpression.ConcatenatedSequence;
+import freemarker.template.SimpleCollection;
+import freemarker.template.SimpleSequence;
+import freemarker.template.TemplateModelException;
+import freemarker.template.TemplateModelIterator;
+import freemarker.template.TemplateScalarModel;
+import freemarker.template.TemplateSequenceModel;
+
+public class ConcatenatedSequenceTest {
+ interface SeqFactory {
+ TemplateSequenceModel create(String... items);
+ boolean isUnrepeatable();
+ }
+
+ @Test
+ public void testForSequences() throws TemplateModelException {
+ test(new SeqFactory() {
+ @Override
+ public TemplateSequenceModel create(String... items) {
+ return new SimpleSequence(List.of(items));
+ }
+
+ @Override
+ public boolean isUnrepeatable() {
+ return false;
+ }
+ });
+ }
+
+ @Test
+ public void testForCollectionsWrappingIterable() throws TemplateModelException {
+ test(new SeqFactory() {
+ @Override
+ public TemplateSequenceModel create(String... items) {
+ return new CollectionAndSequence(new SimpleCollection(Arrays.asList(items)));
+ }
+
+ @Override
+ public boolean isUnrepeatable() {
+ return false;
+ }
+ });
+ }
+
+ @Test
+ public void testForCollectionsWrappingIterator() throws TemplateModelException {
+ test(new SeqFactory() {
+ @Override
+ public TemplateSequenceModel create(String... items) {
+ return new CollectionAndSequence(new SimpleCollection(Arrays.asList(items).iterator()));
+ }
+
+ @Override
+ public boolean isUnrepeatable() {
+ return true;
+ }
+ });
+ }
+
+ public void test(SeqFactory segmentFactory) throws TemplateModelException {
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create(), segmentFactory.create()));
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create(), segmentFactory.create("b")),
+ "b");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create("a"), segmentFactory.create()),
+ "a");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(segmentFactory.create("a"), segmentFactory.create("b")),
+ "a", "b");
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b")),
+ segmentFactory.create("c")),
+ segmentFactory.create("d")),
+ "a", "b", "c", "d");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ segmentFactory.create("b")),
+ new ConcatenatedSequence(
+ segmentFactory.create("c"),
+ segmentFactory.create("d"))
+ ),
+ "a", "b", "c", "d");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ segmentFactory.create("a"),
+ new ConcatenatedSequence(
+ segmentFactory.create("b"),
+ new ConcatenatedSequence(
+ segmentFactory.create("c"),
+ segmentFactory.create("d")
+ )
+ )
+ ),
+ "a", "b", "c", "d");
+
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create("c", "d")),
+ new ConcatenatedSequence(
+ segmentFactory.create("e", "f"),
+ segmentFactory.create("g", "h"))
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b", "c"),
+ new ConcatenatedSequence(
+ segmentFactory.create("d", "e"),
+ segmentFactory.create("f", "g", "h"))
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ new ConcatenatedSequence(
+ new ConcatenatedSequence(
+ segmentFactory.create("a", "b"),
+ segmentFactory.create("c", "d")),
+ segmentFactory.create("e", "f", "g", "h")
+ ),
+ "a", "b", "c", "d", "e", "f", "g", "h");
+
+ if (!segmentFactory.isUnrepeatable()) {
+ // Test when the same segment seq instance is for multiple times in a concatenated seq.
+ assertConcatenationResult(segmentFactory.isUnrepeatable(), () ->
+ {
+ TemplateSequenceModel ab = segmentFactory.create("a", "b");
+ ConcatenatedSequence abab = new ConcatenatedSequence(ab, ab);
+ return new ConcatenatedSequence(abab, abab);
+ },
+ "a", "b", "a", "b", "a", "b", "a", "b");
+ }
+ }
+
+ private void assertConcatenationResult(
+ boolean repeatable,
+ Supplier<ConcatenatedSequence> seqSupplier,
+ String... expectedItems)
+ throws TemplateModelException {
+ ConcatenatedSequence seq = seqSupplier.get();
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ for (TemplateModelIterator iter = seq.iterator(); iter.hasNext(); ) {
+ actualItems.add(((TemplateScalarModel) iter.next()).getAsString());
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ }
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ for (TemplateModelIterator iter = seq.iterator(); iter.hasNext(); ) {
+ assertTrue(iter.hasNext());
+ actualItems.add(((TemplateScalarModel) iter.next()).getAsString());
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ }
+
+ if (repeatable) {
+ seq = seqSupplier.get();
+ }
+
+ {
+ List<String> actualItems = new ArrayList<>();
+ int size = seq.size();
+ for (int i = 0; i < size; i++) {
+ actualItems.add(((TemplateScalarModel) seq.get(i)).getAsString());
+ }
+ assertEquals(Arrays.asList(expectedItems), actualItems);
+ }
+ }
+
+}
\ No newline at end of file
