8000 Wasm: Implement ju.ArrayList without js.Array for Wasm backend by tanishiking · Pull Request #5162 · scala-js/scala-js · GitHub
[go: up one dir, main page]
Skip to content

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

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 2 commits into from
May 8, 2025
Merged

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

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
4913fc9
Check index on bounds in ArrayList addAll and removeRange.
tanishiking May 5, 2025
a088ec4
Wasm: Implement ju.ArrayList without js.Array.
tanishiking May 2, 2025
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
8000
Diff view
Prev Previous commit
Wasm: Implement ju.ArrayList without js.Array. 
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.
  • Loading branch information
@tanishiking @sjrd
tanishiking 8000 authored and sjrd committed May 7, 2025
commit a088ec4b5f3e22f1f287365ef84bf6ec9ced3adb
140 changes: 119 additions & 21 deletions javalib/src/main/scala/java/util/ArrayList.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,75 +14,154 @@ 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[AnyRef](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 > (1 << 30))
resizeTo(minCapacity)
else
resizeTo(((1 << 31) >>> (Integer.numberOfLeadingZeros(minCapacity - 1)) - 1))
}
}
// 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 // free reference for GC
_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) {
ensureCapacity(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)
}
Expand All @@ -91,6 +170,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)
}
}
30 changes: 29 additions & 1 deletion test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/ArrayListTest.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,16 +14,18 @@ package org.scalajs.testsuite.javalib.util

import org.junit.Test
import org.junit.Assert._
import org.junit.Assume._

import org.scalajs.testsuite.utils.AssertThrows.assertThrows
import org.scalajs.testsuite.utils.Platform

import java.{util => ju}

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
Expand All @@ -33,6 +35,32 @@ class ArrayListTest extends AbstractListTest {
al.trimToSize()
}

@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 constructorNullThrowsNullPointerException(): Unit = {
assumeTrue("assumed compliant NPEs", Platform.hasCompliantNullPointers)
assertThrows(classOf[NullPointerException], new ju.ArrayList(null))
}

@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))
Expand Down
10 changes: 10 additions & 0 deletions test-suite/shared/src/test/scala/org/scalajs/testsuite/javalib/util/CollectionTest.scala
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -117,6 +117,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]

Expand Down
0