Wasm: Implement ju.ArrayList without js.Array for Wasm backend #5162

tanishiking · 2025-05-05T07:16:38Z

The original implementation of ju.ArrayList uses js.Array as its internal data structure. When compiling to Wasm, operations on ju.ArrayList require JS interop calls to access the underlying js.Array, which causes a slow performance.
This commit introduces an implementation of ju.ArrayList for the Wasm backend. This version uses Scala's Array instead of js.Array for better performance.

The second commit fixes JS implementation of removeRange to throw an IndexOutOfBoundsException if fromIndex or toIndex is out of range.

Upstreamed from scala-wasm#39

tanishiking · 2025-05-05T07:21:39Z

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

+    val newArr = new Array[Any](newCapacity)
+    System.arraycopy(innerWasm, 0, newArr, 0, size())
+    innerWasm = newArr


Couldn't use Arrays.copyOf since innerWasm needs to be casted to Array[AnyRef] for filling it with null, which fails if E was AnyVal.

sjrd

Thanks. This looks good overall.

I mostly have coding style comments, as well as comments related to using an Array[AnyRef].

sjrd · 2025-05-05T07:54:08Z

test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala

+  @Test def isEmpty(): Unit = {
+    val coll = factory.empty[Int]
+    assertTrue(coll.size() == 0)
+    assertTrue(coll.isEmpty())
+  }


Add another case with a non-empty collection (created with fromElements) to test the false case.

sjrd · 2025-05-05T07:58:01Z

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

+    if (fromIndex < 0 || toIndex > size() || toIndex < fromIndex) {
+      throw new IndexOutOfBoundsException()
+    }


Consider switching the commits. In the first commit, add the new tests, and fix this missing IndexOutOfBoundsException. In the second commit, introduce the Wasm rewriting. This will remove the need for the churn with the platform-dependent assumption.

Sure! Switched the commit order, and added bounds check for addAll to the first commit as well :)

sjrd · 2025-05-05T08:03:05Z

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

+  private var innerWasm =
+    if (!isWebAssembly) null
+    else innerInit.asInstanceOf[Array[Any]]


I suggest creating this array as an Array[AnyRef]. They erase to the same thing, but Array[AnyRef] will allow to use the methods of Arrays. It's common practice even inside the Scala standard library to use an Array[AnyRef] when we need a performant "array of anything".

Note that it is always valid to cast to AnyRef, even for values that "are AnyVals". AnyVal is a Scala compiler fiction. It erases to AnyRef as well. Casting to AnyRef is a no-op in the IR/bytecode.

Note that it is always valid to cast to AnyRef, even for values that "are AnyVals". AnyVal is a Scala compiler fiction. It erases to AnyRef as well. Casting to AnyRef is a no-op in the IR/bytecode.

Interesting, I'll play around with it, but for now we cast it to Array[AnyRef] and can use the Arrays functions. Thanks!

sjrd · 2025-05-05T08:07:51Z

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

+      if (isWebAssembly)
+        new Array[Any](Math.max(initialCapacity, 0))
+      else new js.Array[E],


Suggested change

if (isWebAssembly)

new Array[Any](Math.max(initialCapacity, 0))

else new js.Array[E],

if (isWebAssembly) new Array[Any](Math.max(initialCapacity, 0))

else new js.Array[E],

To avoid the Math.max, though, we can move the initialCapacity < 0 check before the super call, like this:

def this(initialCapacity: Int) = { this( { if (initialCapacity < 0) throw new IllegalArgumentException if (isWebAssembly) new Array[Any](initialCapacity) else new js.Array[E], }, 0 }

sjrd · 2025-05-05T08:11:19Z

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

    addAll(c)
  }

  def trimToSize(): Unit = {
-    // We ignore this as js.Array doesn't support explicit pre-allocation
+    if (isWebAssembly) resizeTo(size())


Coding style: Always use a separate line for side-effecting branches of control structures (see here)

sjrd · 2025-05-05T08:22:03Z

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

  }

  override def clear(): Unit =
-    inner.length = 0
+    if (isWebAssembly) {
+      removeRange(0, size())


This never needs to check bounds nor move elements. Consider using a direct Arrays.fill:

Suggested change

removeRange(0, size())

Arrays.fill(innerWasm, null) // free references for GC

sjrd · 2025-05-05T08:23:36Z

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


  override def addAll(index: Int, c: Collection[_ <: E]): Boolean = {
    c match {
      case other: ArrayList[_] =>
-        inner.splice(index, 0, other.inner.toSeq: _*)
+        if (isWebAssembly) {
+          checkIndexOnBounds(index)


Looks like another bounds check that was missing from the JS implementation, and that should be applied to both cases.

Ah, right, added the bound check in the first commit (and check in both JS and Wasm in second) 👍

sjrd · 2025-05-05T08:27:14Z

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

+        for (i <- (size() - toIndex + fromIndex) until size()) {
+          innerWasm(i) = null
+        }
+        _size -= (toIndex - fromIndex)


Consider computing val newSize = _size - (toIndex - fromIndex) first, to use it also as the start index for the null-filling. Currently this code performs that computation twice, but in slightly different ways, which is confusing.

Also, with an Array[AnyRef] the loop is an Arrays.fill.

sjrd · 2025-05-05T08:28:20Z

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

+
+  // Wasm only
+  private def expand(): Unit = {
+    resizeTo(Math.max(innerWasm.length * 2, 1))


I wonder if it would be better to use 16 instead of 1 as lower bound here.

If we need to resize once, we probably need to resize more later, so we should directly go with the default 16 that we use when no initial capacity is provided.

sjrd · 2025-05-05T08:29:42Z

test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala

+    assertTrue(Array[Int](1, 2, 100) sameElements al1.toArray())
+    assertTrue(Array[Int](1, 2, 200) sameElements al2.toArray())


Coding style: We don't use the infix syntax for alphanumeric method calls anymore (except for eq, ne, to and until):

Suggested change

assertTrue(Array[Int](1, 2, 100) sameElements al1.toArray())

assertTrue(Array[Int](1, 2, 200) sameElements al2.toArray())

assertTrue(Array[Int](1, 2, 100).sameElements(al1.toArray()))

assertTrue(Array[Int](1, 2, 200).sameElements(al2.toArray()))

Same several times below.

tanishiking · 2025-05-05T15:17:29Z

Thanks! I think addressed all the feedbacks.

gzm0

Optional drive-by suggestions

gzm0 · 2025-05-06T05:14:28Z

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

+      if (isWebAssembly) new Array[AnyRef](16)
+      else new js.Array[E],
+      0
+    )


Just this(16)? Let the other ctor handle wasm v.s. JS?

Right, nice catch, thanks!

gzm0 · 2025-05-06T05:15:37Z

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

+      if (isWebAssembly) new Array[AnyRef](c.size())
+      else new js.Array[E],
+      0
+    )


Maybe also here this(c.size())?

gzm0 · 2025-05-06T05:19:44Z

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

-    // We ignore this as js.Array doesn't support explicit pre-allocation
+    if (isWebAssembly) {
+      if (innerWasm.length < minCapacity)
+        resizeTo(minCapacity)


Should we round up to the next power of 2 here?

Sounds good 👍

https://github.com/scala-js/scala-js/pull/5162/files#diff-de47e70080341dc21a1ea1f68a02da92b8a6f85065317b155b2f79d12fbe7164R69-R79

sjrd

A few last details, but otherwise looks good to me.

test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala

test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala

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

removeRange should throws an `IndexOutOfBoundsException` if fromIndex or toIndex is out of range. addAll should also throw when the index is not within bounds.

The original implementation of ju.ArrayList uses js.Array as its internal data structure. When compiling to Wasm, operations on ju.ArrayList require JS interop calls to access the underlying js.Array, which causes a slow performance. This commit introduces an implementation of ju.ArrayList for the Wasm backend. This version uses Scala's Array instead of js.Array for better performance.

sjrd

I took the liberty to move the addAll test to the right commit.

tanishiking force-pushed the arraylist-wasm branch from a1da481 to b511ec4 Compare May 5, 2025 07:18

tanishiking commented May 5, 2025

View reviewed changes

sjrd requested changes May 5, 2025

View reviewed changes

tanishiking force-pushed the arraylist-wasm branch 2 times, most recently from a7d756d to 443c741 Compare May 5, 2025 15:09

tanishiking requested a review from sjrd May 5, 2025 15:17

tanishiking force-pushed the arraylist-wasm branch from 443c741 to 7d87768 Compare May 6, 2025 01:51

gzm0 reviewed May 6, 2025

View reviewed changes

tanishiking force-pushed the arraylist-wasm branch 3 times, most recently from 2010a9c to 7a0e0c6 Compare May 7, 2025 07:46

sjrd requested changes May 7, 2025

View reviewed changes

tanishiking force-pushed the arraylist-wasm branch from 7a0e0c6 to 99cd41e Compare May 7, 2025 13:18

tanishiking added 2 commits May 7, 2025 17:44

Check index on bounds in ArrayList addAll and removeRange.

4913fc9

removeRange should throws an `IndexOutOfBoundsException` if fromIndex or toIndex is out of range. addAll should also throw when the index is not within bounds.

sjrd force-pushed the arraylist-wasm branch from 99cd41e to a088ec4 Compare May 7, 2025 15:46

sjrd approved these changes May 7, 2025

View reviewed changes

sjrd merged commit 008c33a into scala-js:main May 8, 2025
3 checks passed

tanishiking deleted the arraylist-wasm branch May 8, 2025 03:33

This was referenced May 8, 2025

Support ju.ArrayList in targetPureWasm scala-wasm/scala-wasm#39

Closed

js.Array usage tracking in javalib scala-wasm/scala-wasm#41

Open

Wasm: Implement ArrayDeque without js.Array in Wasm backend #5164

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Wasm: Implement ju.ArrayList without js.Array for Wasm backend #5162

Wasm: Implement ju.ArrayList without js.Array for Wasm backend #5162

tanishiking commented May 5, 2025 •

edited

Loading

tanishiking May 5, 2025 •

edited

Loading

sjrd left a comment

sjrd May 5, 2025

sjrd May 5, 2025

tanishiking May 5, 2025

sjrd May 5, 2025

tanishiking May 5, 2025

sjrd May 5, 2025

sjrd May 5, 2025

sjrd May 5, 2025

sjrd May 5, 2025

tanishiking May 5, 2025

sjrd May 5, 2025

sjrd May 5, 2025

sjrd May 5, 2025

tanishiking commented May 5, 2025

gzm0 left a comment

gzm0 May 6, 2025

tanishiking May 7, 2025

gzm0 May 6, 2025

gzm0 May 6, 2025

tanishiking May 7, 2025

sjrd left a comment

sjrd left a comment

	removeRange(0, size())
	Arrays.fill(innerWasm, null) // free references for GC

		assertTrue(Array[Int](1, 2, 100) sameElements al1.toArray())
		assertTrue(Array[Int](1, 2, 200) sameElements al2.toArray())

Wasm: Implement ju.ArrayList without js.Array for Wasm backend #5162

Wasm: Implement ju.ArrayList without js.Array for Wasm backend #5162

Conversation

tanishiking commented May 5, 2025 • edited Loading

tanishiking May 5, 2025 • edited Loading

Choose a reason for hiding this comment

sjrd left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

tanishiking commented May 5, 2025

gzm0 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sjrd left a comment

Choose a reason for hiding this comment

sjrd left a comment

Choose a reason for hiding this comment

tanishiking commented May 5, 2025 •

edited

Loading

tanishiking May 5, 2025 •

edited

Loading