8000 Wasm: Implement ArrayDeque without js.Array in Wasm backend · scala-js/scala-js@b9c9fcf · GitHub
[go: up one dir, main page]
Skip to content

Commit b9c9fcf

Browse files
tanishikingtanishiking
committed
Wasm: Implement ArrayDeque without js.Array in Wasm backend
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 #5164
1 parent eed6479 commit b9c9fcf

File tree

1 file changed

+22
-43
lines changed

1 file changed

+22
-43
lines changed

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

Lines changed: 22 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -18,14 +18,13 @@ import java.lang.Utils._
1818
import java.util.ScalaOps._
1919

2020
import scala.scalajs.js
21+
import scala.scalajs.LinkingInfo
2122

2223
class ArrayDeque[E] private (initialCapacity: Int)
2324
extends AbstractCollection[E] with Deque[E] with Cloneable with Serializable {
2425
self =>
2526

26-
private val inner: js.Array[E] = new js.Array[E](Math.max(initialCapacity, 16))
27-
28-
fillNulls(0, inner.length)
27+
private var inner: Array[AnyRef] = new Array[AnyRef](Math.max(initialCapacity, 10000 16))
2928

3029
private var status = 0
3130
private var startIndex = 0 // inclusive, 0 <= startIndex < inner.length
@@ -56,7 +55,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
5655
startIndex -= 1
5756
if (startIndex < 0)
5857
startIndex = inner.length - 1
59-
inner(startIndex) = e
58+
inner(startIndex) = e.asInstanceOf[AnyRef]
6059
status += 1
6160
empty = false
6261
true
@@ -71,7 +70,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
7170
endIndex += 1
7271
if (endIndex > inner.length)
7372
endIndex = 1
74-
inner(endIndex - 1) = e
73+
inner(endIndex - 1) = e.asInstanceOf[AnyRef]
7574
status += 1
7675
empty = false
7776
true
@@ -95,8 +94,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
9594
def pollFirst(): E = {
9695
if (isEmpty()) null.asInstanceOf[E]
9796
else {
98-
val res = inner(startIndex)
99-
inner(startIndex) = null.asInstanceOf[E] // free reference for GC
97+
val res = inner(startIndex).asInstanceOf[E]
98+
inner(startIndex) = null // free reference for GC
10099
startIndex += 1
101100
if (startIndex == endIndex)
102101
empty = true
@@ -111,8 +110,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
111110
if (isEmpty()) {
112111
null.asInstanceOf[E]
113112
} else {
114-
val res = inner(endIndex - 1)
115-
inner(endIndex - 1) = null.asInstanceOf[E] // free reference for GC
113+
val res = inner(endIndex - 1).asInstanceOf[E]
114+
inner(endIndex - 1) = null // free reference for GC
116115
endIndex -= 1
117116
if (startIndex == endIndex)
118117
empty = true
@@ -139,12 +138,12 @@ class ArrayDeque[E] private (initialCapacity: Int)
139138

140139
def peekFirst(): E = {
141140
if (isEmpty()) null.asInstanceOf[E]
142-
else inner(startIndex)
141+
else inner(startIndex).asInstanceOf[E]
143142
}
144143

145144
def peekLast(): E = {
146145
if (isEmpty()) null.asInstanceOf[E]
147-
else inner(endIndex - 1)
146+
else inner(endIndex - 1).asInstanceOf[E]
148147
}
149148

150149
def removeFirstOccurrence(o: Any): Boolean = {
@@ -222,7 +221,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
222221
else if (nextIndex >= inner.length)
223222
nextIndex = 0
224223

225-
inner(lastIndex)
224+
inner(lastIndex).asInstanceOf[E]
226225
}
227226

228227
override def remove(): Unit = {
@@ -278,7 +277,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
278277
nextIndex = inner.length - 1
279278
}
280279

281-
inner(lastIndex)
280+
inner(lastIndex).asInstanceOf[E]
282281
}
283282

284283
override def remove(): Unit = {
@@ -327,7 +326,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
327326
do {
328327
if (i >= capacity)
329328
i = 0
330-
if (Objects.equals(inner(i), o))
329+
if (Objects.equals(inner(i).asInstanceOf[E], o))
331330
return i
332331
i += 1 // let i overrun so we catch endIndex == capacity
333332
} while (i != endIndex)
@@ -346,7 +345,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
346345
i -= 1
347346
if (i < 0)
348347
i = inner.length - 1
349-
if (Objects.equals(inner(i), o))
348+
if (Objects.equals(inner(i).asInstanceOf[E], o))
350349
return i
351350
} while (i != startIndex)
352351
-1
@@ -358,20 +357,12 @@ class ArrayDeque[E] private (initialCapacity: Int)
358357
// Nothing to do (constructor ensures capacity is always non-zero).
359358
} else if (startIndex == 0 && endIndex == inner.length) {
360359
val oldCapacity = inner.length
361-
inner.length *= 2
362-
// no copying required: We just keep adding to the end.
363-
// However, ensure array is dense.
364-
fillNulls(oldCapacity, inner.length)
360+
inner = Arrays.copyOf(inner, oldCapacity * 2)
365361
} else if (startIndex == endIndex) {
366362
val oldCapacity = inner.length
367-
inner.length *= 2
368-
// move beginning of array to end
369-
for (i <- 0 until endIndex) {
370-
inner(i + oldCapacity) = inner(i)
371-
inner(i) = null.asInstanceOf[E] // free old reference for GC
372-
}
373-
// ensure rest of array is dense
374-
fillNulls(endIndex + oldCapacity, inner.length)
363+
val newArr = new Array[AnyRef](oldCapacity * 2)
364+
System.arraycopy(inner, 0, newArr, oldCapacity, endIndex)
365+
inner= newArr
375366
endIndex += oldCapacity
376367
}
377368
}
@@ -397,10 +388,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
397388
pollLast()
398389
true
399390
} else if (target < endIndex) {
400-
// Shift elements from endIndex towards target
401-
for (i <- target until endIndex - 1)
402-
inner(i) = inner(i + 1)
403-
inner(endIndex - 1) = null.asInstanceOf[E] // free reference for GC
391+
System.arraycopy(inner, target + 1, inner, target, endIndex - target)
392+
inner(endIndex - 1) = null // free reference for GC
404393
status += 1
405394

406395
/* Note that endIndex >= 2:
@@ -429,13 +418,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
429418
* ==> contradiction.
430419
*/
431420

432-
// for (i <- target until startIndex by -1)
433-
var i = target
434-
while (i != startIndex) {
435-
inner(i) = inner(i - 1)
436-
i -= 1
437-
}
438-
inner(startIndex) = null.asInstanceOf[E] // free reference for GC
421+
System.arraycopy(inner, startIndex, inner, startIndex + 1, target - startIndex)
422+
inner(startIndex) = null // free reference for GC
439423

440424
status += 1
441425

@@ -451,9 +435,4 @@ class ArrayDeque[E] private (initialCapacity: Int)
451435
false
452436
}
453437
}
454-
455-
private def fillNulls(from: Int, until: Int): Unit = {
456-
for (i <- from until until)
457-
inner(i) = null.asInstanceOf[E]
458-
}
459438
}

0 commit comments

Comments
 (0)
0