RegEx的Kotlin性能问题

Question

我正在制作一个使用正则表达式的日志解析应用程序，我看到了一些奇怪的行为，我希望有人能帮助解释，也许还能给出克服这些行为的技巧。首先，这是代码：

import java.io.File
var regex1Count = 0
var regex2Count = 0
var noMatchCount = 0
val regex1 = Regex(".*error.*", RegexOption.IGNORE_CASE)
val regex2 = Regex("exception|crashed|death|fatal|killed| f | e ", RegexOption.IGNORE_CASE)
fun main(args: Array<String>) {
val file = File("C:\Users\pnogas\Desktop\mobicontrol.log")
val time = System.currentTimeMillis()
val result = file.useLines { sequence ->
sequence.mapNotNull { line ->
parseLine(line)
}.toList()
}
println("took ${(System.currentTimeMillis() - time) / 1000.0} seconds")
println("regex1Count = $regex1Count, regex2Count = $regex2Count, noMatchCount = $noMatchCount")
}
private fun parseLine(line: String) {
for (filter in listOf(regex2, regex1)) {
if (filter.containsMatchIn(line)) {
if (regex1 == filter) {
regex1Count++
} else if (regex2 == filter) {
regex2Count++
}
return
}
}
noMatchCount++
}

当我运行此代码时，它输出：

took 4.198 seconds
regex1Count = 16, regex2Count = 101, noMatchCount = 11559

但是，如果我将一行更改为listOf(regex1，regex2)而不是listOf)(regex2，regex1)：

took 35.049 seconds
regex1Count = 18, regex2Count = 99, noMatchCount = 11559

我知道通配符regex的运行成本会更高，但数字表明，更改顺序只会使它多运行两倍，与处理的行总数相比，这似乎可以忽略不计。如果我让列表只包含regex1，我会得到同样的性能。

最重要的是，当我使用notepad++在同一个文件上进行相同的regex搜索时，我得到了18个结果，但结果几乎是立竿见影的。我知道JVM不能像本机编译的代码那样执行，但它真的会运行得那么慢吗。还是我的做法完全错了？

由于到目前为止的回复而做出的一些澄清

1. 我同意使用"；错误"；而不是"*错误；将在这里解决时间问题。对我来说，问题是生成RegEx的字符串将来自应用程序中的用户输入。我想我可以在我的应用程序中做的一件事是进行一些预处理：(例如，删除任何前导或尾随通配符，并保留内部通配符)

2. 我知道，自从第一个RegEx比赛回归以来，秩序很重要。同样，由于这将来自用户输入，我同意让他们负责选择性能订单

3. 其他性能改进技巧也很受欢迎，但我想在这里回答的主要问题是为什么订单在我的示例中如此重要？除非我错过了什么。。。

在第一个示例中：regex2运行11676次(匹配101次)regex1运行11575次(没有运行匹配的101次regex2)

在第二示例中：regex1运行11676次(匹配18次)regex2运行11658次(未运行匹配的18次regex1)

因此，regex1运行次数增加了0.86%，regex2运行次数减少了0.15%，但运行时间增加了754%？！我唯一的随机猜测是，有某种JIT JVM预热首先运行简单的regex，这允许第二个更复杂的regex更快地运行，我应该在执行我关心的regex之前插入一个始终快速的伪regex，以提高性能。。。？？？

Answer 1

这是一个复杂的问题，很抱歉提前给出了很长的(遗憾的是不完整的)答案。

您的测试代码存在误解。列表中的第一个正则表达式将在所有行上进行求值，因此在您的示例中为11676次。regex1Count变量only返回(代价高昂的)搜索操作返回正匹配的次数。因此，更改正则表达式的求值顺序可能会对性能产生巨大的影响，因为第一个正则表达式将作为主要过滤器。

此外，正如@PiRocks所说，正则表达式可以简化。更重要的是，由于它的简单性(搜索单个单词)，在这里甚至不需要使用regex。你可以执行文字搜索，而且速度会快得多。

此外，作为一名多年的JVM用户，我必须纠正一个关于性能的常见误解：JVM应用程序并不总是比本地应用程序慢。每种技术都在自己的领域大放异彩，要获得最大的性能，通常需要为正确的任务选择正确的工具。例如，JVM使用JIT对频繁使用的代码进行积极的优化，垃圾收集器大大降低了变量分配的成本。

无论如何，在当前的情况下，无论双方使用什么技术，我们都无法将手工制作的代码性能与附带的应用程序进行比较。为什么？因为我们不能确定是否比较等效的工作流。这里，可能记事本有：

• 将整个文件缓冲在内存中
• 提前创建索引
• 分析了输入搜索正则表达式并在执行之前消除了不必要的复杂性
• 多线程搜索
• 等等

我试图通过kotlin游乐场重现你的案例：

1. 生成随机文本行
2. 测试您的regex1
3. 通过java模式api比较相同的regex
4. 测试regex2
5. 对单词"执行文字搜索；错误">

结果很明显：与.*error.*正则表达式相比，文字搜索是闪电般的。Regex是一个非常强大的工具，但它们的复杂性可能很难管理。

现在，还有一个问题：JVM regex在性能方面实现得不好吗？要回答这个问题并不简单。天真地说，我们可以尝试使用我制作的游乐场(见下面的代码)，用另一种语言重写它，并比较两者的输出。但由于JVM JIT/预热时间的原因，这种比较会有偏差。

我们必须对这两种实现进行广泛的循环，收集统计数据，并最后比较结果，以获得良好的洞察力。

供参考，这里是操场及其输出:

Log example :
ex quam Suspendisse  vel sed  rhoncus aliquet. elit.
nibh amet, sed  nibh eleifend diam amet ex eleifend.
Measure Regex on 12000 lines
Regex 1 for 10 words per line took 0.439 seconds
Regex 1 for 20 words per line took 0.843 seconds
Java pattern 1 for 10 words per line took 0.407 seconds
Java pattern 1 for 20 words per line took 1.347 seconds
Regex 2 for 50 words per line took 0.463 seconds
Literal search for 1000 words per line took 0.836 seconds

import kotlin.random.Random
import java.lang.StringBuilder
import java.lang.System
import java.util.regex.Pattern
fun main() {
println("Log example :")
generateLogs(nbLines = 2, wordPerLine = 10).forEach { println(it) }

println("nMeasure Regex on 12000 linesn")

val regex1 = Regex(".*error.*", RegexOption.IGNORE_CASE)
for (nbWords in listOf(10, 20)) {
roughMeasurement("Regex 1 for $nbWords words per line") {
val matched = generateLogs(wordPerLine = nbWords)
.count { regex1.containsMatchIn(it) }
}
}

val javaPattern = Pattern.compile(".*error.*", Pattern.CASE_INSENSITIVE)
for (nbWords in listOf(10, 20)) {
roughMeasurement("Java pattern 1 for $nbWords words per line") {
val matched = generateLogs(wordPerLine = nbWords)
.count { javaPattern.matcher(it).find() }
}
}

val regex2 = Regex("(exception)|(crashed)|(death)|(fatal)|(killed)| f | e ", RegexOption.IGNORE_CASE)
roughMeasurement("Regex 2 for 50 words per line") {
val matched = generateLogs()
.count { regex2.containsMatchIn(it) }
}

roughMeasurement("Literal search for 1000 words per line") {
val matched = generateLogs(wordPerLine = 1000)
.count { it.indexOf("error") >= 0 }
}
}
fun roughMeasurement(title: String, action: () -> Unit) {
val start = System.nanoTime()
action()
val end = System.nanoTime()
val timeSeconds = (end - start).toDouble() * 1e-9
println("$title took ${"%.3f".format(timeSeconds)} seconds")
}
/* 
* LOG GENERATION UTILITIES
*/

fun generateLogs(nbLines : Int = 12000, wordPerLine : Int = 50) : Sequence<String> {
return (1..nbLines).asSequence()
.map { generateSentence(wordPerLine) }   
}
fun generateSentence(nbWords : Int) : String {
require(nbWords > 2) { "Need more than two words per sentence" }
val builder = StringBuilder(nbWords * 3)
for (i in 0..nbWords-2) {
builder.append(wordPool.pick()).append(' ')
}
builder.append(wordPool.pick())

return builder.toString()
}
fun List<String>.pick() = this[Random.nextInt(0, size)]
/** 
* Authorized words in log generation. 
* To test for worst-case scenario, we've omitted searched keywords: 
* error exception crashed death fatal killed
*/
val wordPool = """
Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Suspendisse eu ex eu ligula egestas posuere ac et velit.
Fusce sed nisl diam. Proin eleifend nibh vel felis fermentum,
a luctus diam eleifend. Pellentesque feugiat magna sit amet 
arcu eleifend, vel lacinia justo aliquet. In quam magna, 
rhoncus a lacinia vel.
""".split(Regex("\s+"))