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

Commit 057d9ad

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 scala-js#5164
1 parent eed6479 commit 057d9ad

File tree

1 file changed

+55
-57
lines changed

1 file changed

+55
-57
lines changed

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

Lines changed: 55 additions & 57 deletions
Original file line numberDiff line numberDiff line change
@@ -18,18 +18,24 @@ 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+
/* This class has two different implementations for the internal storage.
28+
* depending on whether we are on Wasm or JS.
29+
* On JS, we utilize `js.Array`. On Wasm, for performance reasons,
30+
* we use a scala.Array to avoid JS interop.
31+
*/
2732

28-
fillNulls(0, inner.length)
33+
private var inner: Array[AnyRef] = new Array[AnyRef](Math.max(initialCapacity, 16))
2934

3035
private var status = 0
3136
private var startIndex = 0 // inclusive, 0 <= startIndex < inner.length
32-
private var endIndex = inner.length // exclusive, 0 < endIndex <= inner.length
37+
private var endIndex = // exclusive, 0 < endIndex <= inner.length
38+
inner.length
3339
private var empty = true
3440

3541
def this() = this(16)
@@ -55,8 +61,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
5561
ensureCapacityForAdd()
5662
startIndex -= 1
5763
if (startIndex < 0)
58-
startIndex = inner.length - 1
59-
inner(startIndex) = e
64+
startIndex = length() - 1
65+
inner(startIndex) = e.asInstanceOf[AnyRef]
6066
status += 1
6167
empty = false
6268
true
@@ -69,9 +75,9 @@ class ArrayDeque[E] private (initialCapacity: Int)
6975
} else {
7076
ensureCapacityForAdd()
7177
endIndex += 1
72-
if (endIndex > inner.length)
78+
if (endIndex > length())
7379
endIndex = 1
74-
inner(endIndex - 1) = e
80+
inner(endIndex - 1) = e.asInstanceOf[AnyRef]
7581
status += 1
7682
empty = false
7783
true
@@ -95,12 +101,12 @@ class ArrayDeque[E] private (initialCapacity: Int)
95101
def pollFirst(): E = {
96102
if (isEmpty()) null.asInstanceOf[E]
97103
else {
98-
val res = inner(startIndex)
99-
inner(startIndex) = null.asInstanceOf[E] // free reference for GC
104+
val res = inner(startIndex).asInstanceOf[E]
105+
inner(startIndex) = null // free reference for GC
100106
startIndex += 1
101107
if (startIndex == endIndex)
102108
empty = true
103-
if (startIndex >= inner.length)
109+
if (startIndex >= length())
104110
startIndex = 0
105111
status += 1
106112
res
@@ -111,13 +117,13 @@ class ArrayDeque[E] private (initialCapacity: Int)
111117
if (isEmpty()) {
112118
null.asInstanceOf[E]
113119
} else {
114-
val res = inner(endIndex - 1)
115-
inner(endIndex - 1) = null.asInstanceOf[E] // free reference for GC
120+
val res = inner(endIndex - 1).asInstanceOf[E]
121+
inner(endIndex - 1) = null // free reference for GC
116122
endIndex -= 1
117123
if (startIndex == endIndex)
118124
empty = true
119125
if (endIndex <= 0)
120-
endIndex = inner.length
126+
endIndex = length()
121127
status += 1
122128
res
123129
}
@@ -138,13 +144,19 @@ class ArrayDeque[E] private (initialCapacity: Int)
138144
}
139145

140146
def peekFirst(): E = {
141-
if (isEmpty()) null.asInstanceOf[E]
142-
else inner(startIndex)
147+
if (isEmpty()) {
148+
null.asInstanceOf[E]
149+
} else {
150+
inner(startIndex).asInstanceOf[E]
151+
}
143152
}
144153

145154
def peekLast(): E = {
146-
if (isEmpty()) null.asInstanceOf[E]
147-
else inner(endIndex - 1)
155+
if (isEmpty()) {
156+
null.asInstanceOf[E]
157+
} else {
158+
inner(endIndex - 1).asInstanceOf[E]
159+
}
148160
}
149161

150162
def removeFirstOccurrence(o: Any): Boolean = {
@@ -189,7 +201,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
189201
def size(): Int = {
190202
if (isEmpty()) 0
191203
else if (endIndex > startIndex) endIndex - startIndex
192-
else (endIndex + inner.length) - startIndex
204+
else (endIndex + length()) - startIndex
193205
}
194206

195207
def iterator(): Iterator[E] = new Iterator[E] {
@@ -219,10 +231,10 @@ class ArrayDeque[E] private (initialCapacity: Int)
219231
nextIndex += 1
220232
if (nextIndex == endIndex)
221233
nextIndex = -1
222-
else if (nextIndex >= inner.length)
234+
else if (nextIndex >= length())
223235
nextIndex = 0
224236

225-
inner(lastIndex)
237+
inner(lastIndex).asInstanceOf[E]
226238
}
227239

228240
override def remove(): Unit = {
@@ -275,10 +287,10 @@ class ArrayDeque[E] private (initialCapacity: Int)
275287
} else {
276288
nextIndex -= 1
277289
if (nextIndex < 0)
278-
nextIndex = inner.length - 1
290+
nextIndex = length() - 1
279291
}
280292

281-
inner(lastIndex)
293+
inner(lastIndex).asInstanceOf[E]
282294
}
283295

284296
override def remove(): Unit = {
@@ -313,21 +325,22 @@ class ArrayDeque[E] private (initialCapacity: Int)
313325
status += 1
314326
empty = true
315327
startIndex = 0
316-
endIndex = inner.length
328+
endIndex = length()
317329
}
318330

319331
private def firstIndexOf(o: Any): Int = {
320332
// scalastyle:off return
321333
if (isEmpty())
322334
return -1
323335
val inner = this.inner // local copy
324-
val capacity = inner.length // local copy
336+
val capacity = length() // local copy
325337
val endIndex = this.endIndex // local copy
326338
var i = startIndex
327339
do {
328340
if (i >= capacity)
329341
i = 0
330-
if (Objects.equals(inner(i), o))
342+
val obj = inner(i).asInstanceOf[E]
343+
if (Objects.equals(obj, o))
331344
return i
332345
i += 1 // let i overrun so we catch endIndex == capacity
333346
} while (i != endIndex)
@@ -345,8 +358,9 @@ class ArrayDeque[E] private (initialCapacity: Int)
345358
do {
346359
i -= 1
347360
if (i < 0)
348-
i = inner.length - 1
349-
if (Objects.equals(inner(i), o))
361+
i = length() - 1
362+
val obj = inner(i).asInstanceOf[E]
363+
if (Objects.equals(obj, o))
350364
return i
351365
} while (i != startIndex)
352366
-1
@@ -356,22 +370,14 @@ class ArrayDeque[E] private (initialCapacity: Int)
356370
private def ensureCapacityForAdd(): Unit = {
357371
if (isEmpty()) {
358372
// Nothing to do (constructor ensures capacity is always non-zero).
359-
} else if (startIndex == 0 && endIndex == inner.length) {
360-
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)
373+
} else if (startIndex == 0 && endIndex == length()) {
374+
val oldCapacity = length()
375+
inner = Arrays.copyOf(inner, oldCapacity * 2)
365376
} else if (startIndex == endIndex) {
366-
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)
377+
val oldCapacity = length()
378+
val newArr = new Array[AnyRef](oldCapacity * 2)
379+
System.arraycopy(inner, 0, newArr, oldCapacity, endIndex)
380+
inner= newArr
375381
endIndex += oldCapacity
376382
}
377383
}
@@ -397,10 +403,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
397403
pollLast()
398404
true
399405
} 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
406+
System.arraycopy(inner, target + 1, inner, target, endIndex - target)
407+
inner(endIndex - 1) = null // free reference for GC
404408
status += 1
405409

406410
/* Note that endIndex >= 2:
@@ -429,13 +433,8 @@ class ArrayDeque[E] private (initialCapacity: Int)
429433
* ==> contradiction.
430434
*/
431435

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
436+
System.arraycopy(inner, startIndex, inner, startIndex + 1, target - startIndex)
437+
inner(startIndex) = null // free reference for GC
439438

440439
status += 1
441440

@@ -452,8 +451,7 @@ class ArrayDeque[E] private (initialCapacity: Int)
452451
}
453452
}
454453

455-
private def fillNulls(from: Int, until: Int): Unit = {
456-
for (i <- from until until)
457-
inner(i) = null.asInstanceOf[E]
458-
}
454+
@inline
455+
private def length(): Int =
456+
inner.length
459457
}

0 commit comments

Comments
 (0)
0