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

ListBuffer.size is O(n), but ListBuffer.length is O(1)

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: Scala 2.9.1
    • Fix Version/s: None
    • Component/s: Collections
    • Labels:
      None
    • Environment:

      Scala version 2.9.1.RC3

      Description

      The length and size methods on ListBuffer differ. The former is overridden in ListBuffer.scala to have an O(1) implementation, but the latter forwards to "underlying", which uses the O(n ) implementation from TraversableOnce.

      To reproduce,

      def time[A](f: => A): A = {
        val t1 = System.currentTimeMillis
        val ret = f
        val t2 = System.currentTimeMillis
        println("%g secs".format((t2 - t1)/1000.))
        ret
      }
      
      val lb = collection.mutable.ListBuffer.tabulate[Int](1000*1000)(identity)
      
      time(for (j <- 0 until 10000) { lb.length })
      time(for (j <- 0 until 10000) { lb.size })
      

      I get,

      scala> time(for (j <- 0 until 1000) { lb.length })
      0.00000 secs
      
      scala> time(for (j <- 0 until 1000) { lb.size })
      5.48300 secs
      

      The issue came up on StackOverflow, where Daniel Sobral explained the behavior,
      http://stackoverflow.com/questions/7061842/what-is-the-running-time-for-size-on-scalas-listbuffer

      It would also be nice to update the ScalaDoc for `ListBuffer.length` and `size` with performance characteristics.

        Activity

        Hide
        Commit Message Bot added a comment -

        (extempore in r25684) ListBuffer.size should be O(1).

        Not O like it was. Here's another good candidate for some
        mythical performance regression tests. Closes SI-4933, no review.

        Show
        Commit Message Bot added a comment - (extempore in r25684 ) ListBuffer.size should be O(1). Not O like it was. Here's another good candidate for some mythical performance regression tests. Closes SI-4933 , no review.

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development