Wasm: Implement ju.ArrayList without js.Array

tanishiking · tanishiking · commit 2010a9cf8289 · 2025-05-07T15:27:56.000+09:00
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.
diff --git a/javalib/src/main/scala/java/util/ArrayList.scala b/javalib/src/main/scala/java/util/ArrayList.scala
@@ -14,75 +14,159 @@ package java.util
 
 import java.lang.Cloneable
 import java.lang.Utils._
+import java.util.ScalaOps._
 
 import scala.scalajs._
+import scala.scalajs.LinkingInfo.isWebAssembly
 
-class ArrayList[E] private (private[ArrayList] val inner: js.Array[E])
+class ArrayList[E] private (innerInit: AnyRef, private var _size: Int)
     extends AbstractList[E] with RandomAccess with Cloneable with Serializable {
   self =>
 
+  /* This class has two different implementations for handling the
+   * internal data storage, depending on whether we are on Wasm or JS.
+   * On JS, we utilize `js.Array`. On Wasm, for performance reasons,
+   * we avoid JS interop and use a scala.Array.
+   * The `_size` field (unused in JS) keeps track of the effective size
+   * of the underlying Array for the Wasm implementation.
+   */
+
+  private val innerJS: js.Array[E] =
+    if (isWebAssembly) null
+    else innerInit.asInstanceOf[js.Array[E]]
+
+  private var innerWasm: Array[AnyRef] =
+    if (!isWebAssembly) null
+    else innerInit.asInstanceOf[Array[AnyRef]]
+
   def this(initialCapacity: Int) = {
-    this(new js.Array[E])
-    if (initialCapacity < 0)
-      throw new IllegalArgumentException
+    this(
+      {
+        if (initialCapacity < 0)
+          throw new IllegalArgumentException
+        if (isWebAssembly) new Array[Any](initialCapacity)
+        else new js.Array[E]
+      },
+      0
+    )
   }
 
-  def this() =
-    this(new js.Array[E])
+  def this() = this(16)
 
   def this(c: Collection[_ <: E]) = {
-    this()
+    this(c.size())
     addAll(c)
   }
 
   def trimToSize(): Unit = {
-    // We ignore this as js.Array doesn't support explicit pre-allocation
+    if (isWebAssembly)
+      resizeTo(size())
+    // We ignore this in JS as js.Array doesn't support explicit pre-allocation
   }
 
   def ensureCapacity(minCapacity: Int): Unit = {
-    // We ignore this as js.Array doesn't support explicit pre-allocation
+    if (isWebAssembly) {
+      if (innerWasm.length < minCapacity) {
+        if (minCapacity > 1073741824) { // 2^30
+          resizeTo(minCapacity)
+        } else {
+          var powerOf2: Int = 1
+          while (powerOf2 < minCapacity)
+            powerOf2 *= 2
+          resizeTo(powerOf2)
+        }
+      }
+    }
+    // We ignore this in JS as js.Array doesn't support explicit pre-allocation
   }
 
   def size(): Int =
-    inner.length
-
-  override def clone(): AnyRef =
-    new ArrayList(inner.jsSlice(0))
+    if (isWebAssembly) _size
+    else innerJS.length
+
+  override def clone(): AnyRef = {
+    if (isWebAssembly)
+      new ArrayList(innerWasm.clone(), size())
+    else
+      new ArrayList(innerJS.jsSlice(0), 0)
+  }
 
   def get(index: Int): E = {
     checkIndexInBounds(index)
-    inner(index)
+    if (isWebAssembly)
+      innerWasm(index).asInstanceOf[E]
+    else
+      innerJS(index)
   }
 
   override def set(index: Int, element: E): E = {
     val e = get(index)
-    inner(index) = element
+    if (isWebAssembly)
+      innerWasm(index) = element.asInstanceOf[AnyRef]
+    else
+      innerJS(index) = element
     e
   }
 
   override def add(e: E): Boolean = {
-    inner.push(e)
+    if (isWebAssembly) {
+      if (size() >= innerWasm.length)
+        expand()
+      innerWasm(size()) = e.asInstanceOf[AnyRef]
+      _size += 1
+    } else {
+      innerJS.push(e)
+    }
     true
   }
 
   override def add(index: Int, element: E): Unit = {
     checkIndexOnBounds(index)
-    inner.splice(index, 0, element)
+    if (isWebAssembly) {
+      if (size() >= innerWasm.length)
+        expand()
+      System.arraycopy(innerWasm, index, innerWasm, index + 1, size() - index)
+      innerWasm(index) = element.asInstanceOf[AnyRef]
+      _size += 1
+    } else {
+      innerJS.splice(index, 0, element)
+    }
   }
 
   override def remove(index: Int): E = {
     checkIndexInBounds(index)
-    arrayRemoveAndGet(inner, index)
+    if (isWebAssembly) {
+      val removed = innerWasm(index).asInstanceOf[E]
+      System.arraycopy(innerWasm, index + 1, innerWasm, index, size() - index - 1)
+      innerWasm(size - 1) = null
+      _size -= 1
+      removed
+    } else {
+      arrayRemoveAndGet(innerJS, index)
+    }
   }
 
   override def clear(): Unit =
-    inner.length = 0
+    if (isWebAssembly) {
+      Arrays.fill(innerWasm, null) // free references for GC
+      _size = 0
+    } else {
+      innerJS.length = 0
+    }
 
   override def addAll(index: Int, c: Collection[_ <: E]): Boolean = {
     c match {
       case other: ArrayList[_] =>
         checkIndexOnBounds(index)
-        inner.splice(index, 0, other.inner.toSeq: _*)
+        if (isWebAssembly) {
+          if (size() + other.size() >= innerWasm.length)
+            resizeTo(size() + other.size())
+          System.arraycopy(innerWasm, index, innerWasm, index + other.size(), size() - index)
+          System.arraycopy(other.innerWasm, 0, innerWasm, index, other.size())
+          _size += c.size()
+        } else {
+          innerJS.splice(index, 0, other.innerJS.toSeq: _*)
+        }
         other.size() > 0
       case _ => super.addAll(index, c)
     }
@@ -91,6 +175,25 @@ class ArrayList[E] private (private[ArrayList] val inner: js.Array[E])
   override protected def removeRange(fromIndex: Int, toIndex: Int): Unit = {
     if (fromIndex < 0 || toIndex > size() || toIndex < fromIndex)
       throw new IndexOutOfBoundsException()
-    inner.splice(fromIndex, toIndex - fromIndex)
+    if (isWebAssembly) {
+      if (fromIndex != toIndex) {
+        System.arraycopy(innerWasm, toIndex, innerWasm, fromIndex, size() - toIndex)
+        val newSize = size() - toIndex + fromIndex
+        Arrays.fill(innerWasm, newSize, size(), null) // free references for GC
+        _size = newSize
+      }
+    } else {
+      innerJS.splice(fromIndex, toIndex - fromIndex)
+    }
+  }
+
+  // Wasm only
+  private def expand(): Unit = {
+    resizeTo(Math.max(innerWasm.length * 2, 16))
+  }
+
+  // Wasm only
+  private def resizeTo(newCapacity: Int): Unit = {
+    innerWasm = Arrays.copyOf(innerWasm, newCapacity)
   }
 }
diff --git a/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala b/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala
@@ -23,7 +23,7 @@ import scala.reflect.ClassTag
 
 class ArrayListTest extends AbstractListTest {
 
-  override def factory: AbstractListFactory = new ArrayListFactory
+  override def factory: ArrayListFactory = new ArrayListFactory
 
   @Test def ensureCapacity(): Unit = {
     // note that these methods become no ops in js
@@ -46,6 +46,27 @@ class ArrayListTest extends AbstractListTest {
         al.addAll(al.size + 1, TrivialImmutableCollection("foo")))
   }
 
+  @Test def constructorInitialCapacity(): Unit = {
+    val al1 = new ju.ArrayList(0)
+    assertTrue(al1.size() == 0)
+    assertTrue(al1.isEmpty())
+
+    val al2 = new ju.ArrayList(2)
+    assertTrue(al2.size() == 0)
+    assertTrue(al2.isEmpty())
+
+    assertThrows(classOf[IllegalArgumentException], new ju.ArrayList(-1))
+  }
+
+  @Test def testClone(): Unit = {
+    val al1 = factory.fromElements[Int](1, 2)
+    val al2 = al1.clone().asInstanceOf[ju.ArrayList[Int]]
+    al1.add(100)
+    al2.add(200)
+    assertTrue(Array[Int](1, 2, 100).sameElements(al1.toArray()))
+    assertTrue(Array[Int](1, 2, 200).sameElements(al2.toArray()))
+  }
+
   @Test def removeRangeFromIdenticalIndices(): Unit = {
     val al = new ArrayListRangeRemovable[Int](
         TrivialImmutableCollection(-175, 24, 7, 44))
diff --git a/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala b/test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala
@@ -16,10 +16,12 @@ import java.{util => ju, lang => jl}
 
 import org.junit.Test
 import org.junit.Assert._
+import org.junit.Assume._
 
 import org.scalajs.testsuite.javalib.lang.IterableFactory
 import org.scalajs.testsuite.javalib.lang.IterableTest
 import org.scalajs.testsuite.utils.AssertThrows.{assertThrows, _}
+import org.scalajs.testsuite.utils.Platform
 import scala.reflect.ClassTag
 
 import Utils._
@@ -117,6 +119,16 @@ trait CollectionTest extends IterableTest {
     assertFalse(coll.contains(TestObj(200)))
   }
 
+  @Test def isEmpty(): Unit = {
+    val coll = factory.empty[Int]
+    assertTrue(coll.size() == 0)
+    assertTrue(coll.isEmpty())
+
+    val nonEmpty = factory.fromElements[Int](1)
+    assertTrue(nonEmpty.size() == 1)
+    assertFalse(nonEmpty.isEmpty())
+  }
+
   @Test def removeString(): Unit = {
     val coll = factory.empty[String]
 
@@ -320,6 +332,10 @@ trait CollectionTest extends IterableTest {
         expected.contains(result))
   }
 
+  @Test def constructorNullThrowsNullPointerException(): Unit = {
+    assumeTrue("assumed compliant NPEs", Platform.hasCompliantNullPointers)
+    assertThrows(classOf[NullPointerException], new ju.ArrayList(null))
+  }
 }
 
 trait CollectionFactory extends IterableFactory {
