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
Labels
Milestone

Comments

@scabug
Copy link

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 1, 2012

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

@scabug

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug 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

This comment has been minimized.

Copy link
Author

@scabug scabug commented Aug 1, 2012

@retronym said:
lengthCompare itself is overridden in IndexedSeqOptimized.

@scabug

This comment has been minimized.

Copy link
Author

@scabug 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 Sep 4, 2012
@scabug scabug added the performance label Apr 7, 2017
@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
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.