ceylon/ceylon-sdk — pull request #283 by lucaswerkmeister (2014-08-15 14:41:11+00:00)
Title: Better implementation of LinkedList.collect()

`List.collect()` uses `getFromFirst(index)` instead of iterating the list, resulting in O(n²) runtime for lists that don’t offer cheap index-based access. By overriding `collect()` in `LinkedList`, we can go back to O(n) runtime, vastly improving performance.

I have tested three different implementations against a `LinkedList` from current `master` (7b6c7f0c70ecf2e95718731fe2c3b09145963c4e):
```ceylon
import ceylon.collection {
ArrayList,
LinkedList,
MutableList
}

class MyLinkedList_ArraySequence(elements = {}) extends LinkedList(elements) {
"The initial elements of the list."
{Element*} elements;

shared actual Result[] collect(Result collecting(Element element))
=> Array { for (element in this) collecting(element) }.sequence();
}

class MyLinkedList_Comprehension(elements = {}) extends LinkedList(elements) {
"The initial elements of the list."
{Element*} elements;

shared actual Result[] collect(Result collecting(Element element))
=> [for (element in this) collecting(element)];
}

class MyLinkedList_ArrayOfSize(elements = {}) extends LinkedList(elements) {
"The initial elements of the list."
{Element*} elements;

shared actual Result[] collect(Result collecting(Element element)) {
if (!empty) {
assert (exists first = first);
value array = arrayOfSize(size, collecting(first));
variable value i = 1;
for (element in rest) {
array.set(i++, collecting(element));
}
return array.sequence();
} else {
return [];
}
}
}

class S(shared String s) {}

Integer testPerformance(MutableList({S*}) listConstructor, Integer listSize) {
variable value t = 0;
for (i in 1..10) {
value list = listConstructor({ for (j in 1:listSize) S(j.string) });
value tStart = system.nanoseconds;
list.collect((S s) => parseInteger(s.s));
value tEnd = system.nanoseconds;
t += tEnd - tStart;
}
return t;
}

void run() {
for (printFunction in { noop, print }) { // first run for warm-up
for (listSize in { 1_000, 10_000, 100_000 }) {
printFunction(
"``listSize`` elements:
ArrayList: ``testPerformance(({S*} elements) => ArrayList { elements = elements; }, listSize)``ns
LinkedList: ``testPerformance(LinkedList, listSize)``ns
LinkedList, Array.sequence(): ``testPerformance(MyLinkedList_ArraySequence, listSize)``ns
LinkedList, comprehension: ``testPerformance(MyLinkedList_Comprehension, listSize)``ns
LinkedList, arrayOfSize(): ``testPerformance(MyLinkedList_ArrayOfSize, listSize)``ns"
);
}
}
}
```
(The `MyLinkedList_ArrayOfSize` implementation had to be altered a little; a `LinkedList` version would use the unshared `head`.)
```
1000 elements:
ArrayList: 2045339ns
LinkedList: 16831863ns
LinkedList, Array.sequence(): 1929069ns
LinkedList, comprehension: 1903268ns
LinkedList, arrayOfSize(): 1968027ns
10000 elements:
ArrayList: 23150491ns
LinkedList: 1904315964ns
LinkedList, Array.sequence(): 24806347ns
LinkedList, comprehension: 26867767ns
LinkedList, arrayOfSize(): 22684744ns
100000 elements:
ArrayList: 294192537ns
LinkedList: 328916162989ns
LinkedList, Array.sequence(): 333778547ns
LinkedList, comprehension: 328901486ns
LinkedList, arrayOfSize(): 336785355ns
```
As can be seen, they all vastly improve the performance of the `collect` inherited from `List` – for 100k elements, by a factor of 1000! – and all have roughly the same performance. As their relative speed varied between test runs (the `ArrayOfSize` version was slightly faster in an earlier run), I chose the easiest and most obvious implementation; however, I believe an even faster implementation ought to be possible in the future: see #TODO.

This finally fixes the performance after [this commit](https://github.com/ceylon/ceylon.language/commit/81918e7ff58bc2682a0dd4ca9f197b9887097ca3#commitcomment-6771484) broke it. (“I can fix it tomorrow”… yeah, kinda ;) )

CC @gavinking, @quintesse. See also #247 and the commits + issues mentioned in the commit message.