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

ArrayDeque::trimToSize throws OutOfBoundsException #11624

Open
isaacl opened this issue Jul 11, 2019 · 2 comments

Comments

Projects
None yet
3 participants
@isaacl
Copy link

commented Jul 11, 2019

My scala/scala#8092 introduced a bug in ArrayDeque.

scala> ArrayDeque.range(0, 256).trimToSize()
java.lang.IndexOutOfBoundsException: 256 is out of bounds (min 0, max 255)
  at scala.collection.mutable.ArrayDeque.reset(ArrayDeque.scala:566)
  at scala.collection.mutable.ArrayDeque.scala$collection$mutable$ArrayDeque$$resize(ArrayDeque.scala:494)
  at scala.collection.mutable.ArrayDeque.trimToSize(ArrayDeque.scala:474)
  ... 36 elided

This is caused by an peculiar choice in trimToSize

def trimToSize(): Unit = resize(length - 1)

Instead we need functions like shouldShrink and canShrink, and trimToSize needs to call the latter. I'll put out a PR shortly to fix this.

cc @Ichoran

@NthPortal

This comment has been minimized.

Copy link

commented Jul 11, 2019

should it just be resize(length)?

@isaacl

This comment has been minimized.

Copy link
Author

commented Jul 11, 2019

Hmm maybe

isaacl added a commit to isaacl/scala that referenced this issue Jul 11, 2019

Improve ArrayDeque resizing logic
Don't trim array unless it's less than 2/5 filled.
This avoids expensive resizes when an ArrayDeque hovers
around a power of 2 size.

Reimplement `trimToSize` to resize array as long as
smaller size fits data.

Fixes scala/bug#11624 crash.

isaacl added a commit to isaacl/scala that referenced this issue Jul 11, 2019

Improve ArrayDeque resizing logic
Don't trim array unless it's less than 2/5 filled.
This avoids expensive resizes when an ArrayDeque hovers
around a power of 2 size.

Reimplement `trimToSize` to resize array as long as
smaller size fits data.

Fixes scala/bug#11624 crash.

isaacl added a commit to isaacl/scala that referenced this issue Jul 12, 2019

Improve ArrayDeque resizing logic
Don't trim array unless it's less than 2/5 filled.
This avoids expensive resizes when an ArrayDeque hovers
around a power of 2 size.

Reimplement `trimToSize` to resize array as long as
smaller size fits data.

Fixes scala/bug#11624 crash.

isaacl added a commit to isaacl/scala that referenced this issue Jul 12, 2019

Improve ArrayDeque resizing logic
Don't trim array unless it's less than 2/5 filled.
This avoids expensive resizes when an ArrayDeque hovers
around a power of 2 size.

Reimplement `trimToSize` to resize array as long as
smaller size fits data.

Fixes scala/bug#11624 crash.

@dwijnand dwijnand added this to the 2.13.1 milestone Jul 12, 2019

@dwijnand dwijnand added the has PR label Jul 12, 2019

isaacl added a commit to isaacl/scala that referenced this issue Jul 14, 2019

Improve ArrayDeque resizing logic
Don't trim array unless it's less than 2/5 filled.
This avoids expensive resizes when an ArrayDeque hovers
around a power of 2 size.

Reimplement `trimToSize` to resize array as long as
smaller size fits data.

Fixes scala/bug#11624 crash.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.