8000 Wasm: Implement ju.ArrayList without js.Array. · scala-js/scala-js@a088ec4 · GitHub
[go: up one dir, main page]
Skip to content

Commit a088ec4

Browse files
tanishikingsjrd
tanishiking
authored and
sjrd
committed
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.
1 parent 4913fc9 commit a088ec4

File tree

3 files changed

+158
-22
lines changed

3 files changed

+158
-22
lines changed

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

Lines changed: 119 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -14,75 +14,154 @@ package java.util
1414

1515
import java.lang.Cloneable
1616
import java.lang.Utils._
17+
import java.util.ScalaOps._
1718

1819
import scala.scalajs._
20+
import scala.scalajs.LinkingInfo.isWebAssembly
1921

20-
class ArrayList[E] private (private[ArrayList] val inner: js.Array[E])
22+
class ArrayList[E] private (innerInit: AnyRef, private var _size: Int)
2123
extends AbstractList[E] with RandomAccess with Cloneable with Serializable {
2224
self =>
2325

26+
/* This class has two different implementations for handling the
27+
* internal data storage, depending on whether we are on Wasm or JS.
28+
* On JS, we utilize `js.Array`. On Wasm, for performance reasons,
29+
* we avoid JS interop and use a scala.Array.
30+
* The `_size` field (unused in JS) keeps track of the effective size
31+
* of the underlying Array for the Wasm implementation.
32+
*/
33+
34+
private val innerJS: js.Array[E] =
35+
if (isWebAssembly) null
36+
else innerInit.asInstanceOf[js.Array[E]]
37+
38+
private var innerWasm: Array[AnyRef] =
39+
if (!isWebAssembly) null
40+
else innerInit.asInstanceOf[Array[AnyRef]]
41+
2442
def this(initialCapacity: Int) = {
25-
this(new js.Array[E])
26-
if (initialCapacity < 0)
27-
throw new IllegalArgumentException
43+
this(
44+
{
45+
if (initialCapacity < 0)
46+
throw new IllegalArgumentException
47+
if (isWebAssembly) new Array[AnyRef](initialCapacity)
48+
else new js.Array[E]
49+
},
50+
0
51+
)
2852
}
2953

30-
def this() =
31-
this(new js.Array[E])
54+
def this() = this(16)
3255

3356
def this(c: Collection[_ <: E]) = {
34-
this()
57+
this(c.size())
3558
addAll(c)
3659
}
3760

3861
def trimToSize(): Unit = {
39-
// We ignore this as js.Array doesn't support explicit pre-allocation
62+
if (isWebAssembly)
63+
resizeTo(size())
64+
// We ignore this in JS as js.Array doesn't support explicit pre-allocation
4065
}
4166

4267
def ensureCapacity(minCapacity: Int): Unit = {
43-
// We ignore this as js.Array doesn't support explicit pre-allocation
68+
if (isWebAssembly) {
69+
if (innerWasm.length < minCapacity) {
70+
if (minCapacity > (1 << 30))
71+
resizeTo(minCapacity)
72+
else
73+
resizeTo(((1 << 31) >>> (Integer.numberOfLeadingZeros(minCapacity - 1)) - 1))
74+
}
75+
}
76+
// We ignore this in JS as js.Array doesn't support explicit pre-allocation
4477
}
4578

4679
def size(): Int =
47-
inner.length
48-
49-
override def clone(): AnyRef =
50-
new ArrayList(inner.jsSlice(0))
80+
if (isWebAssembly) _size
81+
else innerJS.length
82+
83+
override def clone(): AnyRef = {
84+
if (isWebAssembly)
85+
new ArrayList(innerWasm.clone(), size())
86+
else
87+
new ArrayList(innerJS.jsSlice(0), 0)
88+
}
5189

5290
def get(index: Int): E = {
5391
checkIndexInBounds(index)
54-
inner(index)
92+
if (isWebAssembly)
93+
innerWasm(index).asInstanceOf[E]
94+
else
95+
innerJS(index)
5596
}
5697

5798
override def set(index: Int, element: E): E = {
5899
val e = get(index)
59-
inner(index) = element
100+
if (isWebAssembly)
101+
innerWasm(index) = element.asInstanceOf[AnyRef]
102+
else
103+
innerJS(index) = element
60104
e
61105
}
62106

63107
override def add(e: E): Boolean = {
64-
inner.push(e)
108+
if (isWebAssembly) {
109+
if (size() >= innerWasm.length)
110+
expand()
111+
innerWasm(size()) = e.asInstanceOf[AnyRef]
112+
_size += 1
113+
} else {
114+
innerJS.push(e)
115+
}
65116
true
66117
}
67118

68119
override def add(index: Int, element: E): Unit = {
69120
checkIndexOnBounds(index)
70-
inner.splice(index, 0, element)
121+
if (isWebAssembly) {
122+
if (size() >= innerWasm.length)
123+
expand()
124+
System.arraycopy(innerWasm, index, innerWasm, index + 1, size() - index)
125+
innerWasm(index) = element.asInstanceOf[AnyRef]
126+
_size += 1
127+
} else {
128+
innerJS.splice(index, 0, element)
129+
}
71130
}
72131

73132
override def remove(index: Int): E = {
74133
checkIndexInBounds(index)
75-
arrayRemoveAndGet(inner, index)
134+
if (isWebAssembly) {
135+
val removed = innerWasm(index).asInstanceOf[E]
136+
System.arraycopy(innerWasm, index + 1, innerWasm, index, size() - index - 1)
137+
innerWasm(size - 1) = null // free reference for GC
138+
_size -= 1
139+
removed
140+
} else {
141+
arrayRemoveAndGet(innerJS, index)
142+
}
76143
}
77144

78145
override def clear(): Unit =
79-
inner.length = 0
146+
if (isWebAssembly) {
147+
Arrays.fill(innerWasm, null) // free references for GC
148+
_size = 0
149+
} else {
150+
innerJS.length = 0
151+
}
80152

81153
override def addAll(index: Int, c: Collection[_ <: E]): Boolean = {
82154
c match {
83155
case other: ArrayList[_] =>
84156
checkIndexOnBounds(index)
85-
inner.splice(index, 0, other.inner.toSeq: _*)
157+
if (isWebAssembly) {
158+
ensureCapacity(size() + other.size())
159+
System.arraycopy(innerWasm, index, innerWasm, index + other.size(), size() - index)
160+
System.arraycopy(other.innerWasm, 0, innerWasm, index, other.size())
161+
_size += c.size()
162+
} else {
163+
innerJS.splice(index, 0, other.innerJS.toSeq: _*)
164+
}
86165
other.size() > 0
87166
case _ => super.addAll(index, c)
88167
}
@@ -91,6 +170,25 @@ class ArrayList[E] private (private[ArrayList] val inner: js.Array[E])
91170
override protected def removeRange(fromIndex: Int, toIndex: Int): Unit = {
92171
if (fromIndex < 0 || toIndex > size() || toIndex < fromIndex)
93172
throw new IndexOutOfBoundsException()
94-
inner.splice(fromIndex, toIndex - fromIndex)
173+
if (isWebAssembly) {
174+
if (fromIndex != toIndex) {
175+
System.arraycopy(innerWasm, toIndex, innerWasm, fromIndex, size() - toIndex)
176+
val newSize = size() - toIndex + fromIndex
177+
Arrays.fill(innerWasm, newSize, size(), null) // free references for GC
178+
_size = newSize
179+
}
180+
} else {
181+
innerJS.splice(fromIndex, toIndex - fromIndex)
182+
}
183+
}
184+
185+
// Wasm only
186+
private def expand(): Unit = {
187+
resizeTo(Math.max(innerWasm.length * 2, 16))
188+
}
189+
190+
// Wasm only
191+
private def resizeTo(newCapacity: Int): Unit = {
192+
innerWasm = Arrays.copyOf(innerWasm, newCapacity)
95193
}
96194
}

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

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,16 +14,18 @@ package org.scalajs.testsuite.javalib.util
1414

1515
import org.junit.Test
1616
import org.junit.Assert._
17+
import org.junit.Assume._
1718

1819
import org.scalajs.testsuite.utils.AssertThrows.assertThrows
20+
import org.scalajs.testsuite.utils.Platform
1921

2022
import java.{util => ju}
2123

2224
import scala.reflect.ClassTag
2325

2426
class ArrayListTest extends AbstractListTest {
2527

26-
override def factory: AbstractListFactory = new ArrayListFactory
28+
override def factory: ArrayListFactory = new ArrayListFactory
2729

2830
@Test def ensureCapacity(): Unit = {
2931
// note that these methods become no ops in js
@@ -33,6 +35,32 @@ class ArrayListTest extends AbstractListTest {
3335
al.trimToSize()
3436
}
3537

38+
@Test def constructorInitialCapacity(): Unit = {
39+
val al1 = new ju.ArrayList(0)
40+
assertTrue(al1.size() == 0)
41+
assertTrue(al1.isEmpty())
42+
43+
val al2 = new ju.ArrayList(2)
44+
assertTrue(al2.size() == 0)
45+
assertTrue(al2.isEmpty())
46+
47+
assertThrows(classOf[IllegalArgumentException], new ju.ArrayList(-1))
48+
}
49+
50+
@Test def constructorNullThrowsNullPointerException(): Unit = {
51+
assumeTrue("assumed compliant NPEs", Platform.hasCompliantNullPointers)
52+
assertThrows(classOf[NullPointerException], new ju.ArrayList(null))
53+
}
54+
55+
@Test def testClone(): Unit = {
56+
val al1 = factory.fromElements[Int](1, 2)
57+
val al2 = al1.clone().asInstanceOf[ju.ArrayList[Int]]
58+
al1.add(100)
59+
al2.add(200)
60+
assertTrue(Array[Int](1, 2, 100).sameElements(al1.toArray()))
61+
assertTrue(Array[Int](1, 2, 200).sameElements(al2.toArray())) EBCC
62+
}
63+
3664
@Test def removeRangeFromIdenticalIndices(): Unit = {
3765
val al = new ArrayListRangeRemovable[Int](
3866
TrivialImmutableCollection(-175, 24, 7, 44))

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -117,6 +117,16 @@ trait CollectionTest extends IterableTest {
117117
assertFalse(coll.contains(TestObj(200)))
118118
}
119119

120+
@Test def isEmpty(): Unit = {
121+
val coll = factory.empty[Int]
122+
assertTrue(coll.size() == 0)
123+
assertTrue(coll.isEmpty())
124+
125+
val nonEmpty = factory.fromElements[Int](1)
126+
assertTrue(nonEmpty.size() == 1)
127+
assertFalse(nonEmpty.isEmpty())
128+
}
129+
120130
@Test def removeString(): Unit = {
121131
val coll = factory.empty[String]
122132

0 commit comments

Comments
 (0)
0