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

immutable.Queue should override :+ using enqueue

    Details

      Description

      Kim Hansen reported on #scala that +: is two magnitudes slower than enqueue:

      object QueuePerformance {
      println("Test performance of Queue") //> Test performance of Queue
       
      import scala.collection.immutable.Queue
      
      def time[A](f: => A) = {
      f
      for (_ <- 1 to 3) {
      val s = System.nanoTime
      f
      println("time: " + (System.nanoTime - s) / 1e6 + "ms")
      }
      }       //> time: [A](f: => A)Unit
       
      val count = 10000 //> count : Int = 10000
       
      time {
      var q = Queue.empty[Int]
      for (i <- 1 to count) {
      q = q enqueue i
      }
      println(q.dequeue._1)
      }       //> 1
              //| 1
              //| time: 19.326757ms
              //| 1
              //| time: 3.575115ms
              //| 1
              //| time: 1.428872ms
      time {
      var q = Queue.empty[Int]
      for (i <- 1 to count) {
      q = q :+ i
      }
      println(q.dequeue._1)
      }       //> 1
              //| 1
              //| time: 576.121048ms
              //| 1
              //| time: 511.96562ms
              //| 1
              //| time: 582.245494ms
      }
      

      The same thing should probably happen for +:.

        Activity

        Show
        Adriaan Moors added a comment - https://github.com/scala/scala/pull/3250

          People

          • Assignee:
            Simon Ochsenreither
            Reporter:
            Simon Ochsenreither
          • Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development