scala/scala — pull request #2331 by paulp (2013-03-28 20:33:50+00:00)
Title: Take the N^2 out of the compiler's TreeSet.

If we're going to have custom reimplementations of standard
collections, it seems like they should have some demonstrable
performance advantage. With this commit the time to compile
a particular piece of generated code dropped from this:
```
% time scalac3 ./target/generated/src.scala
Mar 28 13:20:31 [running phase parser on src.scala]
...
Mar 28 13:21:28 [running phase lazyvals on src.scala]
Mar 28 13:21:28 [running phase lambdalift on src.scala] <-- WHOA
Mar 28 13:25:05 [running phase constructors on src.scala]
...
Mar 28 13:25:19 [running phase jvm on icode]
316.387 real, 438.182 user, 8.163 sys
```
To this:
```
97.927 real, 211.015 user, 8.043 sys

% time pscalac ./target/generated/src.scala
Mar 28 13:18:47 [running phase parser on src.scala]
...
Mar 28 13:19:44 [running phase lazyvals on src.scala]
Mar 28 13:19:44 [running phase lambdalift on src.scala]
Mar 28 13:19:46 [running phase constructors on src.scala]
...
Mar 28 13:19:57 [running phase jvm on icode]
99.909 real, 223.605 user, 7.847 sys
```
That's lambdalift dropping from 217 seconds to 2 seconds. Which
should really call into question whether the "demonstrable"
standard is being met. The number of bugs like this is going to be
proportional to the number of distinct implementations. How many
different logical paths do we need to concatenate iterators?

This should be exhibit A as to why the collections should
bundle far less code and behavior. It seems even we, the authors
of the collections, find them too heavyweight to use in our
primary application, favoring instead stripped down versions
of the same data structures. And here we see a huge performance
bug because of it. Wouldn't it be nice if we could use the same
battle-tested code everyone else does?