Made ConcatenatedSequence.get(int) a lot less slow when it was made from a lot of concatenated sequences. Not fast still, but way faster in those cases, and is a backward compatible solution. (That is, it's a solution that doesn't assume that the nested sequences weren't changed since the concatenation. It could be much faster if we can assume that.)
diff --git a/src/main/java/freemarker/core/AddConcatExpression.java b/src/main/java/freemarker/core/AddConcatExpression.java
index 54e4d71..dba2d4e 100644
--- a/src/main/java/freemarker/core/AddConcatExpression.java
+++ b/src/main/java/freemarker/core/AddConcatExpression.java
@@ -244,10 +244,56 @@
}
@Override
- public TemplateModel get(int i)
- throws TemplateModelException {
- int ls = left.size();
- return i < ls ? left.get(i) : right.get(i - ls);
+ public TemplateModel get(int index) throws TemplateModelException {
+ if (index < 0) {
+ return null;
+ }
+
+ int totalSize = 0;
+
+ ConcatenatedSequence[] concSeqsWithRightPending = new ConcatenatedSequence[2];
+ int concSeqsWithRightPendingLength = 0;
+ ConcatenatedSequence concSeqInFocus = this;
+
+ while (true) {
+ TemplateSequenceModel left;
+ while ((left = concSeqInFocus.left) instanceof ConcatenatedSequence) {
+ if (concSeqsWithRightPendingLength == concSeqsWithRightPending.length) {
+ concSeqsWithRightPending = Arrays.copyOf(concSeqsWithRightPending, concSeqsWithRightPendingLength * 2);
+ }
+ concSeqsWithRightPending[concSeqsWithRightPendingLength++] = concSeqInFocus;
+ concSeqInFocus = (ConcatenatedSequence) left;
+ }
+ {
+ int segmentSize = left.size();
+ totalSize += segmentSize;
+ if (totalSize > index) {
+ return left.get(index - (totalSize - segmentSize));
+ }
+ }
+
+ while (true) {
+ TemplateSequenceModel right = concSeqInFocus.right;
+ if (right instanceof ConcatenatedSequence) {
+ concSeqInFocus = (ConcatenatedSequence) right;
+ break; // To jump at the left-descending loop
+ }
+ {
+ int segmentSize = right.size();
+ totalSize += segmentSize;
+ if (totalSize > index) {
+ return right.get(index - (totalSize - segmentSize));
+ }
+ }
+
+ if (concSeqsWithRightPendingLength == 0) {
+ return null;
+ }
+
+ concSeqsWithRightPendingLength--;
+ concSeqInFocus = concSeqsWithRightPending[concSeqsWithRightPendingLength];
+ }
+ }
}
@Override
diff --git a/src/manual/en_US/book.xml b/src/manual/en_US/book.xml
index f307d9e..e164e38 100644
--- a/src/manual/en_US/book.xml
+++ b/src/manual/en_US/book.xml
@@ -30092,35 +30092,51 @@
</listitem>
<listitem>
- <para>When concatenating many sequences (like Java
+ <para>When concatenating many sequences (like of Java
<literal>List</literal>-s) with the <literal>+</literal>
- operator:</para>
+ operator, the resulting sequence is now much less slow to read.
+ (Background: the <literal>+</literal> operator, when applied on
+ two sequences, produces a result sequence that just view, not a
+ copy of the original sequences. Thus is very fast to add
+ together long sequences. But, if you concatenate many, like
+ hundreds, of sequences, reading the sequence back will become
+ expensive. It was always like that, so it's still not
+ recommended to concatenate more then a few tens of sequences.
+ But if that recommendation is not kept, now the slowdown can be
+ way less punishing.)</para>
<itemizedlist>
<listitem>
- <para>In previous versions iIterating 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 <replaceable>seq</replaceable> as
- <replaceable>...</replaceable>></literal>, or
- <literal><replaceable>seq</replaceable>?join(',
- ')</literal>). Accessing items by index (like
- <literal><replaceable>seq</replaceable>[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>
+ <para>Iteration (like listing) is now reasonably fast, and
+ need not be concerned about. The speed of fetching the next
+ item is now mostly independent of the number of sequences
+ concatenated, while earlier it has become slower as that
+ number grew. By iteration we mean going through all the
+ items, strictly in order, without using an index explicitly.
+ Examples of iteration are <literal><#list
+ <replaceable>concatedSeq</replaceable> as
+ <replaceable>...</replaceable>></literal>, and
+ <literal><replaceable>concatedSeq</replaceable>?join(',
+ ')</literal>.</para>
+ </listitem>
+
+ <listitem>
+ <para>Accessing items by index, like
+ <literal><replaceable>concatedSeq</replaceable>[i]</literal>,
+ is now much faster than before, but still can be slow if you
+ had concatenated a lot of sequences. Item access speed is
+ now roughly O(N), where N is number of concatenated
+ sequences (not the number of items!), so traversing the
+ whole sequence by index is O(N²).</para>
</listitem>
<listitem>
<para>In previous versions
- <literal><replaceable>seq</replaceable>?size</literal> could
- cause stack overflow (if you have concatenated thousands of
- sequences). Now the impementation is not recursive.</para>
+ <literal><replaceable>concatedSeq</replaceable>?size</literal>
+ could cause stack overflow if it
+ <literal><replaceable>concatedSeq</replaceable></literal>
+ was concatenated together from thousands of sequences. Now
+ the stack usage is constant and negligible.</para>
</listitem>
</itemizedlist>
</listitem>
@@ -30156,6 +30172,17 @@
</listitem>
<listitem>
+ <para>When concatenating sequences (like Java
+ <literal>List</literal>-s) with the <literal>+</literal>
+ operation in templates, the resulting
+ <literal>TemplateSequenceModel</literal> now also implements
+ <literal>TemplateCollectionModel</literal> (with is similar to
+ Java's <literal>Iterable</literal>). It's because using that is
+ much more efficient then indexed access, if the sequence was
+ concatenated together from a lot of sequences.</para>
+ </listitem>
+
+ <listitem>
<para>We don't generate RMIC stub classes for
<literal>freemarker.debug.impl.Rmi*Impl</literal> classes
anymore. Almost nobody uses that API, but if you do, you
diff --git a/src/test/java/freemarker/core/ConcatenatedSequenceTest.java b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
index 1280cae..f36af67 100644
--- a/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
+++ b/src/test/java/freemarker/core/ConcatenatedSequenceTest.java
@@ -210,6 +210,9 @@
actualItems.add(((TemplateScalarModel) seq.get(i)).getAsString());
}
assertEquals(Arrays.asList(expectedItems), actualItems);
+ assertNull(seq.get(-1));
+ assertNull(seq.get(size));
+ assertNull(seq.get(size + 1));
}
if (repeatable) {
