Skip to content

Implement ArrayDeque using scala.Array. #5164

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.

Sign up for GitHub

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

Merged
merged 1 commit into from
May 26, 2025
Merged

Implement ArrayDeque using scala.Array. #5164

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
61 changes: 20 additions & 41 deletions javalib/src/main/scala/java/util/ArrayDeque.scala
View file
Open in desktop
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For ArrayDeque, it does not seem like we rely all that much on the growability of js.Arrays. The only place that grows is ensureCapacityForAdd(). It always doubles the size of the internal array. It's unlikely that the underlying VM could do a better job than just reallocating at about the same moments.

Perhaps it would be better to just always use Array[AnyRef], even on JS. That would avoid complicating the logic, which in this class is particularly dense already.

@gzm0 WDYT?

Copy link
Contributor Author

@tanishiking tanishiking May 14, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For comparison, I wrote a Array[AnyRef] (even on JS) version b73e8a1

And, I wrote a micro-benchmark for ArrayDeque, and compare the two implementation on JS (scala.Array vs js.Array), each benchmark basically add/poll integer 10000 times.
tanishiking/scalajs-benchmarks@13cd090

The result shows that, js.Array is still slightly faster than scala.Array in most cases. However, considering the complexity of the program, the difference may be negligible.

download

https://colab.research.google.com/drive/17eevbKILkGiT21uqWCDuD3KAkj-de6BT?usp=sharing

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Were those benchmarks done in fullLink?

Copy link
Contributor Author

@tanishiking tanishiking May 15, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It was in fastLink, in fullLink scala.Array and js.Array has a bit smaller difference in addLast bench

download (2)

https://colab.research.google.com/drive/17eevbKILkGiT21uqWCDuD3KAkj-de6BT?usp=sharing

it's interesting that, with scala.Array impl, FIFO and LIFO cases (last two benchmarks) are consistently faster than js.Array

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree with the overall sentiment, that just using scala.Array for JS as well might be worthwhile.

It seems that the investigation here as already gone beyond gut feeling, so I guess we can let the numbers speak.

The current benchmarks do look like there is some overhead not related to resizing. For example, I'd expect peekFirst_Repeatedly to not cause any mutations. Do we have an understanding of where these come from?

Copy link
Contributor Author

@tanishiking tanishiking May 16, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, it was my benchmark programs' fault, the peekFist/peekLast benchmarks anyway add 10000 items to the queue, and resize happened.

Updated the benchmark to add only 16 items to the queue (not to trigger resizing) and peek first/last 10000 times. tanishiking/scalajs-benchmarks@825063f

The result shows that there's really no difference between js.Array and scala.Array 👍

download (4)

I think the difference in poll comes from resizing too, since it push 10000 items (resize happen) and then poll 10000 times.

Original file line number Diff line number Diff line change
Expand Up @@ -17,15 +17,11 @@ import java.lang.Utils._

import java.util.ScalaOps._

import scala.scalajs.js

class ArrayDeque[E] private (initialCapacity: Int)
extends AbstractCollection[E] with Deque[E] with Cloneable with Serializable {
self =>

private val inner: js.Array[E] = new js.Array[E](Math.max(initialCapacity, 16))

fillNulls(0, inner.length)
private var inner: Array[AnyRef] = new Array[AnyRef](Math.max(initialCapacity, 16))

private var status = 0
private var startIndex = 0 // inclusive, 0 <= startIndex < inner.length
Expand Down Expand Up @@ -56,7 +52,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
startIndex -= 1
if (startIndex < 0)
startIndex = inner.length - 1
inner(startIndex) = e
inner(startIndex) = e.asInstanceOf[AnyRef]
status += 1
empty = false
true
Expand All @@ -71,7 +67,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
endIndex += 1
if (endIndex > inner.length)
endIndex = 1
inner(endIndex - 1) = e
inner(endIndex - 1) = e.asInstanceOf[AnyRef]
status += 1
empty = false
true
Expand All @@ -95,8 +91,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
def pollFirst(): E = {
if (isEmpty()) null.asInstanceOf[E]
else {
val res = inner(startIndex)
inner(startIndex) = null.asInstanceOf[E] // free reference for GC
val res = inner(startIndex).asInstanceOf[E]
inner(startIndex) = null // free reference for GC
startIndex += 1
if (startIndex == endIndex)
empty = true
Expand All @@ -111,8 +107,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
if (isEmpty()) {
null.asInstanceOf[E]
} else {
val res = inner(endIndex - 1)
inner(endIndex - 1) = null.asInstanceOf[E] // free reference for GC
val res = inner(endIndex - 1).asInstanceOf[E]
inner(endIndex - 1) = null // free reference for GC
endIndex -= 1
if (startIndex == endIndex)
empty = true
Expand All @@ -139,12 +135,12 @@ class ArrayDeque[E] private (initialCapacity: Int)

def peekFirst(): E = {
if (isEmpty()) null.asInstanceOf[E]
else inner(startIndex)
else inner(startIndex).asInstanceOf[E]
}

def peekLast(): E = {
if (isEmpty()) null.asInstanceOf[E]
else inner(endIndex - 1)
else inner(endIndex - 1).asInstanceOf[E]
}

def removeFirstOccurrence(o: Any): Boolean = {
Expand Down Expand Up @@ -222,7 +218,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
else if (nextIndex >= inner.length)
nextIndex = 0

inner(lastIndex)
inner(lastIndex).asInstanceOf[E]
}

override def remove(): Unit = {
Expand Down Expand Up @@ -278,7 +274,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
nextIndex = inner.length - 1
}

inner(lastIndex)
inner(lastIndex).asInstanceOf[E]
}

override def remove(): Unit = {
Expand Down Expand Up @@ -358,20 +354,14 @@ class ArrayDeque[E] private (initialCapacity: Int)
// Nothing to do (constructor ensures capacity is always non-zero).
} else if (startIndex == 0 && endIndex == inner.length) {
val oldCapacity = inner.length
inner.length *= 2
// no copying required: We just keep adding to the end.
// However, ensure array is dense.
fillNulls(oldCapacity, inner.length)
// No moving required within the array; we grow only at the end.
inner = Arrays.copyOf(inner, oldCapacity * 2)
} else if (startIndex == endIndex) {
val oldCapacity = inner.length
inner.length *= 2
// move beginning of array to end
for (i <- 0 until endIndex) {
inner(i + oldCapacity) = inner(i)
inner(i) = null.asInstanceOf[E] // free old reference for GC
}
// ensure rest of array is dense
fillNulls(endIndex + oldCapacity, inner.length)
val newArr = new Array[AnyRef](oldCapacity * 2)
System.arraycopy(inner, 0, newArr, oldCapacity, endIndex)
inner = newArr
endIndex += oldCapacity
}
}
Expand All @@ -398,9 +388,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
true
} else if (target < endIndex) {
// Shift elements from endIndex towards target
for (i <- target until endIndex - 1)
inner(i) = inner(i + 1)
inner(endIndex - 1) = null.asInstanceOf[E] // free reference for GC
System.arraycopy(inner, target + 1, inner, target, endIndex - (target + 1))
inner(endIndex - 1) = null // free reference for GC
status += 1

/* Note that endIndex >= 2:
Expand Down Expand Up @@ -429,13 +418,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
* ==> contradiction.
*/

// for (i <- target until startIndex by -1)
var i = target
while (i != startIndex) {
inner(i) = inner(i - 1)
i -= 1
}
inner(startIndex) = null.asInstanceOf[E] // free reference for GC
System.arraycopy(inner, startIndex, inner, startIndex + 1, target - startIndex)
inner(startIndex) = null // free reference for GC

status += 1

Expand All @@ -451,9 +435,4 @@ class ArrayDeque[E] private (initialCapacity: Int)
false
}
}

private def fillNulls(from: Int, until: Int): Unit = {
for (i <- from until until)
inner(i) = null.asInstanceOf[E]
}
}