Scala Programming Language
  1. Scala Programming Language
  2. SI-7316

Iterator.single and Iterator.++ when used together are very slow

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.10.1
    • Fix Version/s: Scala 2.11.0-M3
    • Component/s: Collections
    • Labels:
      None

      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 ms
      

      One 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 https://github.com/scala/scala/pull/2331

        Activity

        Hide
        Jason Zaugg added a comment -

        Seems like Paul got this one at the second swing, in https://github.com/scala/scala/commit/e3ddb2d.

        I don't want to add an ad-hoc and potentially brittle performance test for this. I do lament the lack of a place to write and run a real test. What became of scala-meter?

        ~/code/scala RUNNER=scala scala-hash e3ddb2d~1 -nc sandbox/t7316.scala
        [info] e3ddb2d~1 => /Users/jason/usr/scala-v2.11.0-M2-43-g59d4998
        iterate(0) took 1 ms
        iterate(200) took 8 ms
        iterate(400) took 28 ms
        iterate(600) took 97 ms
        iterate(800) took 255 ms
        iterate(1000) took 505 ms
        iterate(1200) took 851 ms
        iterate(1400) took 1390 ms
        iterate(1600) took 2079 ms
        iterate(1800) took 3080 ms
        iterate(2000) took 4155 ms
        ticket/7335 ~/code/scala RUNNER=scala scala-hash e3ddb2d -nc sandbox/t7316.scala
        [info] e3ddb2d => /Users/jason/usr/scala-v2.11.0-M2-44-ge3ddb2d
        iterate(0) took 1 ms
        iterate(200) took 5 ms
        iterate(400) took 1 ms
        iterate(600) took 3 ms
        iterate(800) took 3 ms
        iterate(1000) took 6 ms
        iterate(1200) took 7 ms
        iterate(1400) took 9 ms
        iterate(1600) took 11 ms
        iterate(1800) took 14 ms
        iterate(2000) took 16 ms
        
        Show
        Jason Zaugg added a comment - Seems like Paul got this one at the second swing, in https://github.com/scala/scala/commit/e3ddb2d . I don't want to add an ad-hoc and potentially brittle performance test for this. I do lament the lack of a place to write and run a real test. What became of scala-meter? ~/code/scala RUNNER=scala scala-hash e3ddb2d~1 -nc sandbox/t7316.scala [info] e3ddb2d~1 => /Users/jason/usr/scala-v2.11.0-M2-43-g59d4998 iterate(0) took 1 ms iterate(200) took 8 ms iterate(400) took 28 ms iterate(600) took 97 ms iterate(800) took 255 ms iterate(1000) took 505 ms iterate(1200) took 851 ms iterate(1400) took 1390 ms iterate(1600) took 2079 ms iterate(1800) took 3080 ms iterate(2000) took 4155 ms ticket/7335 ~/code/scala RUNNER=scala scala-hash e3ddb2d -nc sandbox/t7316.scala [info] e3ddb2d => /Users/jason/usr/scala-v2.11.0-M2-44-ge3ddb2d iterate(0) took 1 ms iterate(200) took 5 ms iterate(400) took 1 ms iterate(600) took 3 ms iterate(800) took 3 ms iterate(1000) took 6 ms iterate(1200) took 7 ms iterate(1400) took 9 ms iterate(1600) took 11 ms iterate(1800) took 14 ms iterate(2000) took 16 ms
        Hide
        Paul Phillips added a comment -

        That's funny; that was the FIRST swing! I knew that commit did something useful, but what it didn't do was fix the issue I was after, which was fixed (for the purposes of util.TreeSet) in 61308be6dc. But it seemed to leave the underlying Iterator issue unaddressed.

        Show
        Paul Phillips added a comment - That's funny; that was the FIRST swing! I knew that commit did something useful, but what it didn't do was fix the issue I was after, which was fixed (for the purposes of util.TreeSet) in 61308be6dc. But it seemed to leave the underlying Iterator issue unaddressed.

          People

          • Assignee:
            Paul Phillips
            Reporter:
            Grzegorz Kossakowski
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development