Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
scabug opened this issue Aug 20, 2011 · 2 comments
Closed

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

scabug opened this issue Aug 20, 2011 · 2 comments
Assignees

Comments

@scabug
Copy link

@scabug scabug commented Aug 20, 2011

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.

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 20, 2011

Imported From: https://issues.scala-lang.org/browse/SI-4933?orig=1
Reporter: Kipton Barros (kbarros)
Affected Versions: 2.9.1

@scabug

This comment has been minimized.

Copy link
Author

@scabug scabug commented Sep 19, 2011

Commit Message Bot (anonymous) said:
(extempore in r25684) ListBuffer.size should be O(1).

Not O(n) like it was. Here's another good candidate for some
mythical performance regression tests. Closes #4933, no review.

@scabug scabug closed this Sep 19, 2011
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.