Implement ArrayDeque using scala.Array. #5164

tanishiking · 2025-05-09T07:59:14Z

Simliar to ju.ArrayList #5162, add a Wasm version of implementation of ArrayDeque that doesn't have JS-interop for internal data structure.

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

In WebAssembly, it works around 6~7x- faster than js.Array impl.

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

tanishiking · 2025-05-09T08:01:01Z

javalib/src/main/scala/java/util/ArrayDeque.scala

+    val innerJS = this.innerJS // local copy
+    val innerWasm = this.innerWasm // local copy


Do I understand correctly that, these local copies are for better performance (accessing local copy is faster than class field), right?

Yes, that's correct.

[note]
This is also a problem, let's wait until we decide to use (or not to use) Array[AnyRef] anyway.
If we don't, we can do something like val innerJS = if (isWebAssembly) null else this.innerJS, or maybe we can do the same as PriorityQueue.

javalib/src/main/scala/java/lang/Utils.scala

sjrd · 2025-05-11T10:08:19Z

javalib/src/main/scala/java/util/ArrayDeque.scala

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?

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.

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

Were those benchmarks done in fullLink?

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

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

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?

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 👍

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

javalib/src/main/scala/java/util/PriorityQueue.scala

javalib/src/main/scala/java/lang/Utils.scala

tanishiking · 2025-05-14T10:35:59Z

Perhaps it would be better to split it into two PRs for ArrayDeque and PriorityQueue?

tanishiking · 2025-05-15T02:39:02Z

I took a liberty of splitting a PR for PriorityQueue #5168
Let's focus on ArrayDeque here.

The original implementation of `ju.ArrayDeque` used `js.Array` for its internal data structure. When compiling to WebAssembly, it requires JavaScript interop calls to access the underlying js.Array, leading to a significant performance overhead. This commit optimize the `ju.ArrayDeque` for WebAssembly backend by switching the `ju.ArrayDeque` implementation to use `scala.Array` instead. We've opted for `scala.Array` consistently across both WebAssembly and JavaScript environments, rather than conditionally switching between `js.Array` and `scala.Array`, to avoid complicate the logic by inserting a bunch of if/else here and there. Also, there's minor performance degradation observed when using scala.Array and managing size in user-space on JavaScript is considered acceptable. See the discussion at scala-js#5164

tanishiking · 2025-05-21T11:54:34Z

Updated to use scala.Array anyway on JS and WebAssembly based on the conversation here #5164 (comment)

sjrd

Oops, sorry for the delay.

sjrd · 2025-05-25T20:29:09Z

javalib/src/main/scala/java/util/ArrayDeque.scala

@@ -18,14 +18,13 @@ import java.lang.Utils._
 import java.util.ScalaOps._

 import scala.scalajs.js
+import scala.scalajs.LinkingInfo


This import is not used anymore.

And I guess the import scala.scalajs.js isn't used anymore either.

sjrd · 2025-05-25T20:30:25Z

javalib/src/main/scala/java/util/ArrayDeque.scala

@@ -327,7 +326,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
    do {
      if (i >= capacity)
        i = 0
-      if (Objects.equals(inner(i), o))
+      if (Objects.equals(inner(i).asInstanceOf[E], o))


The cast is probably not necessary here. Object.equals accepts any type of argument.

sjrd · 2025-05-25T20:30:30Z

javalib/src/main/scala/java/util/ArrayDeque.scala

@@ -346,7 +345,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
      i -= 1
      if (i < 0)
        i = inner.length - 1
-      if (Objects.equals(inner(i), o))
+      if (Objects.equals(inner(i).asInstanceOf[E], o))


javalib/src/main/scala/java/util/ArrayDeque.scala

sjrd · 2025-05-25T20:34:59Z

javalib/src/main/scala/java/util/ArrayDeque.scala

-      fillNulls(endIndex + oldCapacity, inner.length)
+      val newArr = new Array[AnyRef](oldCapacity * 2)
+      System.arraycopy(inner, 0, newArr, oldCapacity, endIndex)
+      inner= newArr


Nit:

Suggested change

inner= newArr

inner = newArr

javalib/src/main/scala/java/util/ArrayDeque.scala

sjrd · 2025-05-25T20:39:20Z

javalib/src/main/scala/java/util/ArrayDeque.scala

-      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)


This doesn't look right. Shouldn't it be

Suggested change

System.arraycopy(inner, target + 1, inner, target, endIndex - target)

System.arraycopy(inner, target + 1, inner, target, endIndex - (target + 1))

oops, nice catch, thanks!

sjrd · 2025-05-25T22:21:31Z

Oh also, the commit message needs to be changed. It's not Wasm-only anymore.

The original implementation of `ju.ArrayDeque` used `js.Array` for its internal data structure. However, when compiling to WebAssembly, it requires JavaScript interop calls are required to access the underlying js.Array, leading to a significant performance overhead. This commit switches the internal data structure of ju.ArrayDeque to use scala.Array instead, for both the WebAssembly and JavaScript backends. Using `scala.Array` in both environments avoids complicating the logic by conditionally using `js.Array` or `scala.Array` based on whether it's Wasm or JS. This change significantly improves ArrayDeque's performance on WebAssembly and results in only minor performance degradation on JavaScript. See the discussion at scala-js#5164

tanishiking · 2025-05-26T05:11:15Z

Thanks, I've addressed all feedbacks (restoring comments I accidentally deleted 🙇) and rewritten the commit message.

sjrd

LGTM.

@gzm0 Do you want to also have a look?

tanishiking commented May 9, 2025

View reviewed changes

tanishiking changed the title ~~Wasm: Implement ArrayDeque without js.Array in Wasm backend~~ Wasm: Implement ArrayDeque and PriorityQueue without js.Array in Wasm backend May 9, 2025

sjrd requested changes May 11, 2025

View reviewed changes

He-Pin reviewed May 11, 2025

View reviewed changes

javalib/src/main/scala/java/lang/Utils.scala Outdated Show resolved Hide resolved

tanishiking mentioned this pull request May 15, 2025

Wasm: Implement PriorityQueue without js.Array in Wasm backend #5168

Open

tanishiking force-pushed the arraydeque-wasm branch from 249ba0b to 1ba7624 Compare May 15, 2025 02:37

tanishiking changed the title ~~Wasm: Implement ArrayDeque and PriorityQueue without js.Array in Wasm backend~~ Wasm: Implement ArrayDeque without js.Array in Wasm backend May 15, 2025

tanishiking force-pushed the arraydeque-wasm branch from 1ba7624 to 057d9ad Compare May 21, 2025 10:14

tanishiking force-pushed the arraydeque-wasm branch from 057d9ad to b9c9fcf Compare May 21, 2025 11:48

tanishiking requested review from sjrd and gzm0 May 25, 2025 20:23

sjrd requested changes May 25, 2025

View reviewed changes

tanishiking force-pushed the arraydeque-wasm branch from b9c9fcf to 08ce2c6 Compare May 26, 2025 05:06

tanishiking requested a review from sjrd May 26, 2025 05:11

sjrd changed the title ~~Wasm: Implement ArrayDeque without js.Array in Wasm backend~~ Implement ArrayDeque using scala.Array. May 26, 2025

sjrd approved these changes May 26, 2025

View reviewed changes

gzm0 approved these changes May 26, 2025

View reviewed changes

gzm0 merged commit e293a4c into scala-js:main May 26, 2025
3 checks passed

tanishiking deleted the arraydeque-wasm branch May 27, 2025 02:34

		val innerJS = this.innerJS // local copy
		val innerWasm = this.innerWasm // local copy

	System.arraycopy(inner, target + 1, inner, target, endIndex - target)
	System.arraycopy(inner, target + 1, inner, target, endIndex - (target + 1))

Implement ArrayDeque using scala.Array. #5164

Implement ArrayDeque using scala.Array. #5164

Uh oh!

Conversation

tanishiking commented May 9, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tanishiking May 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tanishiking May 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tanishiking May 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

tanishiking May 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

tanishiking commented May 14, 2025

Uh oh!

tanishiking commented May 15, 2025

Uh oh!

tanishiking commented May 21, 2025

Uh oh!

sjrd left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sjrd commented May 25, 2025

Uh oh!

tanishiking commented May 26, 2025

Uh oh!

sjrd left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

tanishiking commented May 9, 2025 •

edited

Loading

tanishiking May 15, 2025 •

edited

Loading

tanishiking May 14, 2025 •

edited

Loading

tanishiking May 15, 2025 •

edited

Loading

tanishiking May 16, 2025 •

edited

Loading