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

我知道通配符正则表达式的运行成本会更高，但数字表明更改顺序只会使其运行次数增加两倍，与处理的总行数相比，这似乎可以忽略不计。如果我使列表仅包含 regex1，我将获得相同的性能。
最重要的是，当我使用 notepad++ 对同一个文件进行相同的正则表达式搜索时，我得到了 18 个结果，但结果几乎是立即出现的。我知道 JVM 将无法像 native 编译代码那样执行，但它真的期望运行得那么慢吗？还是我以完全错误的方式解决这个问题？
由于到目前为止的回复而做出的一些澄清

我同意使用“error”而不是“.*error.*”来解决这里的时间问题。对我来说，问题是生成正则表达式的字符串将来自应用程序中的用户输入。我想我可以在我的应用程序中做的一件事是一些预处理:(例如，删除任何前导或尾随通配符并保留内部通配符)

我知道，由于第一个匹配的 RegEx 返回，所以顺序很重要。再次，因为这将来自用户输入，我可以让他们负责选择性能良好的订单

欢迎其他提高性能的技巧，但我想在这里回答的主要问题是 为什么订单在我的示例中如此不同 ?除非我错过了什么...

在第一个例子中:
regex2 运行 11676 次(匹配 101 次)
regex1 运行 11575 次(未运行 regex2 匹配的 101 次)
在第二个例子中:
regex1 运行 11676 次(匹配 18 次)
regex2 运行 11658 次(不运行 regex1 匹配的 18 次)
所以 regex1 运行次数增加了 0.86%，regex2 运行次数减少了 0.15%，但运行时间增加了 754%？!
我唯一的随机猜测是某种 JIT JVM Warmup 首先运行简单的正则表达式，它允许第二个更复杂的运行得更快，我应该插入一个虚拟的正则表达式，在执行我关心的正则表达式之前总是很快以提高性能。 ..???

Answer 1

这是一个复杂的问题，对于冗长(遗憾的是不完整)的答案，请提前道歉。
您的测试代码存在误解。您列表中的第一个正则表达式将在 上进行评估全部 行，因此在您的示例中为 11676 次。您的 regex1Count 变量仅返回 的次数正 match 已由(昂贵的)搜索操作返回。因此，更改正则表达式的评估顺序会对性能产生巨大影响，因为第一个正则表达式将用作主要过滤器。
此外，正如@PiRocks 所说，可以简化正则表达式。更重要的是，由于其简单性(搜索单个单词)，这里甚至不需要使用正则表达式。您可以执行文字搜索，它会快得多。
此外，作为多年的 JVM 用户，我必须纠正一个关于性能的常见误解:JVM 应用程序并不总是比本地应用程序慢。每种技术都在自己的领域中大放异彩，要获得最佳性能，通常需要为正确的任务选择正确的工具。例如，JVM 使用 JIT 对经常使用的代码进行积极的优化，垃圾收集器大大降低了变量分配的成本。
无论如何，在当前情况下，我们 不能将手工编写的代码性能与交付的应用程序进行比较，无论双方使用什么技术。为什么 ？因为我们不能确定比较等效的工作流程。在这里，也许记事本有:

在内存中缓冲整个文件，

预先创建了一个索引，

分析输入搜索正则表达式并在执行前消除不必要的复杂性，

多线程搜索，

等

我试图通过 kotlin playground 重现您的案例:

生成随机文本行

测试您的 regex1

通过 java pattern api

比较相同的正则表达式

测试 regex2

对单词“error”执行字面搜索。

结果很明显:与 .*error.* 相比，文字搜索快如闪电。正则表达式。正则表达式是一个非常强大的工具，但它们的复杂性可能难以管理。
现在，还有一个问题:JVM 正则表达式在性能方面执行得很差吗？回答这个问题并不简单。天真地，我们可以尝试使用我制作的游乐场(见下面的代码)，用另一种语言重写它并比较两者的输出。但由于 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 lines\n")
    
    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+"))