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

Iterator 'drop' method has a complexity bug causing quadratic behavior #8835

Closed
scabug opened this issue Sep 4, 2014 · 2 comments
Closed

Comments

@scabug
Copy link

scabug commented Sep 4, 2014

The Iterator drop method (defined in Iterator.scala) generates nested anonymous classes. When drop is used in a loop, this causes linear traversal to become quadratic, and will also eventually cause a stack overflow if invoked sufficiently many times.

I wrote up a description and analysis of the problem here:
http://erikerlandson.github.io/blog/2014/09/03/matryoshka-class-construction-from-the-scala-iterator-drop-method/

Recommend the implementation be changed from calling 'slice' to something more like:

def drop(n: Int): Iterator[A] = {
var j = 0
while (j < n) {
this.next
j += 1
}
this
}

@scabug
Copy link
Author

scabug commented Sep 4, 2014

Imported From: https://issues.scala-lang.org/browse/SI-8835?orig=1
Reporter: @erikerlandson
Assignee: @erikerlandson
See #9737

@scabug
Copy link
Author

scabug commented Sep 4, 2014

@erikerlandson said:
PR: scala/scala#3963

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant