Iterator.single and Iterator.++ when used together are very slow #7316
Description
Consider the following code:
def iterate(n: Int): Iterator[Int] = Iterator.single(n) ++ (if (n == 0) Iterator.empty else iterate(n-1))
def time[T](label: String)(thunk: => T): T = {
val start = System.currentTimeMillis
val result = thunk
val end = System.currentTimeMillis
println(s"$label took ${end-start} ms")
result
}
for (n <- 0 to 2000 by 200) {
time(s"iterate($n)") {
iterate(n).foreach(_ => ())
}
}when run I get:
$ scala iterate.scala
iterate(0) took 1 ms
iterate(200) took 9 ms
iterate(400) took 27 ms
iterate(600) took 96 ms
iterate(800) took 237 ms
iterate(1000) took 475 ms
iterate(1200) took 834 ms
iterate(1400) took 1360 ms
iterate(1600) took 2123 ms
iterate(1800) took 3091 ms
iterate(2000) took 4078 msOne would expect linear increase of the time we need to iterate all elements returned by iterate method. I didn't dig deeper to understand why this code is so slow but I decided to log a ticket instead. Original inspiration for this code comes from scala/scala#2331