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

Vector isEmpty is slow #6167

Closed
scabug opened this issue Aug 1, 2012 · 7 comments
Closed

Vector isEmpty is slow #6167

scabug opened this issue Aug 1, 2012 · 7 comments
Assignees
Milestone

Comments

@scabug
Copy link

scabug commented Aug 1, 2012

Vector should override isEmpty:

override def isEmpty = length == 0

Expect five fold performance increase in head, tail, last and init :)

@scabug
Copy link
Author

scabug commented Aug 1, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6167?orig=1
Reporter: Juha Heljoranta (p52mm3x)
Affected Versions: 2.9.2, 2.10.0-M6
Other Milestones: 2.10.0-M7, 2.10.0

@scabug
Copy link
Author

scabug commented Aug 1, 2012

@soc said:
I looked at the code. The issue seems to be that Vector#isEmpty uses IterableLike's implementation !iterator.hasNext.

This in turn invokes Vector#iterator, which does a lot of work:

  @inline override def iterator: VectorIterator[A] = {
    val s = new VectorIterator[A](startIndex, endIndex)
    initIterator(s)
    s
  }

Using Vector#length to implement Vector#isEmpty seems to make sense, because it is only a comparison and an arithmetic operation: def length = def length = endIndex - startIndex

@scabug
Copy link
Author

scabug commented Aug 1, 2012

@retronym said:
I'd suggest that isEmpty should be overridden in SeqLike in terms of lengthCompare.

@scabug
Copy link
Author

scabug commented Aug 1, 2012

@soc said (edited on Aug 1, 2012 9:19:23 PM UTC):
Thanks for reporting this issue, Juha!

Pull request: scala/scala#1036

Edit: Sorry, Jason, I saw your comment too late. I'll look into it.

@scabug
Copy link
Author

scabug commented Aug 1, 2012

@soc said (edited on Aug 1, 2012 9:21:25 PM UTC):
Jason, are you sure? Won't this also lead to the expensive creation of Vector#iterator: https://github.com/scala/scala/blob/master/src/library/scala/collection/SeqLike.scala#L87 ?

@scabug
Copy link
Author

scabug commented Aug 1, 2012

@retronym said:
lengthCompare itself is overridden in IndexedSeqOptimized.

@scabug
Copy link
Author

scabug commented Sep 4, 2012

@soc said:
I'll close this issue because the fix has been added to both the 2.10.x branch and trunk.

@juha: The fix is different to the code you proposed, because we tried to enable other collection classes to benefit from this change, too. Would you be so kind to check if the performance improvement is what you expect, and re-open this ticket if not?

@scabug scabug closed this as completed Sep 4, 2012
@scabug scabug added this to the 2.10.0-M6 milestone Apr 7, 2017
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

2 participants