[Regex] Replace a child set list with an array on the hot path
JointSet descendants excessively iterate over their child sets.
With lists being used, such iteration has a significant overhead related
to iterator allocation and various additional condition checks.
diff --git a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/AtomicJointSet.kt b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/AtomicJointSet.kt
index a3fcbaa..2c2e068 100644
--- a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/AtomicJointSet.kt
+++ b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/AtomicJointSet.kt
@@ -31,8 +31,8 @@
override fun matches(startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
val start = matchResult.getConsumed(groupIndex)
matchResult.setConsumed(groupIndex, startIndex)
- children.forEach {
- val shift = it.matches(startIndex, testString, matchResult)
+ forEachChildrenIndexed { _, child ->
+ val shift = child.matches(startIndex, testString, matchResult)
if (shift >= 0) {
// AtomicFset always returns true, but saves the index to run this next.match() from;
return next.matches((fSet as AtomicFSet).index, testString, matchResult)
diff --git a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/JointSet.kt b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/JointSet.kt
index fce62bf..f02daed 100644
--- a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/JointSet.kt
+++ b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/JointSet.kt
@@ -30,7 +30,7 @@
*/
open internal class JointSet(children: List<AbstractSet>, fSet: FSet) : AbstractSet() {
- protected var children: MutableList<AbstractSet> = mutableListOf<AbstractSet>().apply { addAll(children) }
+ private var children = children.toTypedArray()
var fSet: FSet = fSet
protected set
@@ -79,8 +79,18 @@
assert(newFSet == fSet)
}
- @OptIn(ExperimentalNativeApi::class)
- children.replaceAll { child -> if (!child.secondPassVisited) child.processSecondPass() else child }
+ children.forEachIndexed { index, child ->
+ if (!child.secondPassVisited) {
+ children[index] = child.processSecondPass()
+ }
+ }
+
return super.processSecondPassInternal()
}
+
+ protected inline fun forEachChildrenIndexed(action: (index: Int, child: AbstractSet) -> Unit) {
+ for (index in children.indices) {
+ action(index, children[index])
+ }
+ }
}
diff --git a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookAheadSets.kt b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookAheadSets.kt
index 13b5ea2..045f5dc 100644
--- a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookAheadSets.kt
+++ b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookAheadSets.kt
@@ -29,8 +29,8 @@
/** Returns startIndex+shift, the next position to match */
override fun tryToMatch(startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
- children.forEach {
- val shift = it.matches(startIndex, testString, matchResult)
+ forEachChildrenIndexed { _, child ->
+ val shift = child.matches(startIndex, testString, matchResult)
if (shift >= 0) {
// PosLookaheadFset always returns true, position remains the same next.match() from;
return next.matches(startIndex, testString, matchResult)
@@ -50,8 +50,8 @@
/** Returns startIndex+shift, the next position to match */
override fun tryToMatch(startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
- children.forEach {
- if (it.matches(startIndex, testString, matchResult) >= 0) {
+ forEachChildrenIndexed { _, child ->
+ if (child.matches(startIndex, testString, matchResult) >= 0) {
return -1
}
}
diff --git a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookBehindSets.kt b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookBehindSets.kt
index d577ea7..ffb2cc4 100644
--- a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookBehindSets.kt
+++ b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/LookBehindSets.kt
@@ -48,8 +48,13 @@
children[it].computeMatchLengthInChars(fSet)
}
- protected fun matchPrefix(childIndex: Int, startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
- val child = children[childIndex]
+ protected fun matchPrefix(
+ childIndex: Int,
+ child: AbstractSet,
+ startIndex: Int,
+ testString: CharSequence,
+ matchResult: MatchResultImpl
+ ): Int {
val prefixLength = prefixLengths[childIndex]
return when {
// the prefix length is unknown, so lets fallback to a generic matching
@@ -69,8 +74,8 @@
/** Returns startIndex+shift, the next position to match */
override fun tryToMatch(startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
matchResult.setConsumed(groupIndex, startIndex)
- for (idx in children.indices) {
- if (matchPrefix(idx, startIndex, testString, matchResult) >= 0) {
+ forEachChildrenIndexed { idx, child ->
+ if (matchPrefix(idx, child, startIndex, testString, matchResult) >= 0) {
matchResult.setConsumed(groupIndex, -1)
return next.matches(startIndex, testString, matchResult)
}
@@ -90,8 +95,8 @@
/** Returns startIndex+shift, the next position to match */
override fun tryToMatch(startIndex: Int, testString: CharSequence, matchResult: MatchResultImpl): Int {
matchResult.setConsumed(groupIndex, startIndex)
- for (idx in children.indices) {
- if (matchPrefix(idx, startIndex,testString, matchResult) >= 0) {
+ forEachChildrenIndexed { idx, child ->
+ if (matchPrefix(idx, child, startIndex, testString, matchResult) >= 0) {
return -1
}
}
diff --git a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/NonCapturingJointSet.kt b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/NonCapturingJointSet.kt
index 07f7ec4..0b31ecc 100644
--- a/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/NonCapturingJointSet.kt
+++ b/libraries/stdlib/native-wasm/src/kotlin/text/regex/sets/NonCapturingJointSet.kt
@@ -34,8 +34,8 @@
val start = matchResult.getConsumed(groupIndex)
matchResult.setConsumed(groupIndex, startIndex)
- children.forEach {
- val shift = it.matches(startIndex, testString, matchResult)
+ forEachChildrenIndexed { _, child ->
+ val shift = child.matches(startIndex, testString, matchResult)
if (shift >= 0) {
return shift
}
