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

Optimise immutable.Queue for head/tail #11396

Open
NthPortal opened this Issue Feb 9, 2019 · 0 comments

Comments

Projects
None yet
1 participant
@NthPortal
Copy link

NthPortal commented Feb 9, 2019

Optimise immutable.Queue so that head/tail usage pattern does not cause double traversal of in.

Take the following usage pattern:

var queue: Queue[Int] = ???
while (queue.nonEmpty) {
  val elem = queue.head
  queue = queue.tail
  // do something with `elem` here
}

If out is empty and in is not, val elem = queue.head will require traversing in to find its last element, and queue = queue.tail will require reversing in (which requires traversal).

immutable.Queue's methods should be optimised so that when dequeueing elements, it does not leave out empty (unless in is also empty), and when enqueueing elements, it puts at least one element in out if both in and out are empty (although once you're checking, might as well put everything in out).


This change should be binary compatible, as it only requires changes to class internals.

@NthPortal NthPortal added this to the 2.13.1 milestone Feb 9, 2019

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