Java中抗ReDoS的逗号前后去空格正则优化方案问询

我在Java中使用正则匹配「零个或多个空白字符+逗号+零个或多个空白字符」，用于清理字符串，初始代码如下：

String new1 = test1.replaceAll("\\s*,\\s*", ",");

回溯问题分析 #

当字符串中没有逗号时，这个正则会触发大量回溯。以字符串String s = "Hello World";（单词间4个空格，无逗号）为例，匹配过程如下：

• 第一步：第一个\s*匹配"Hello"后的4个空格；
• 第二步：尝试匹配逗号失败；
• 第三步：回溯到第一个\s*，改为匹配3个空格后再次尝试匹配逗号，依然失败；
• 第四步：重复上述回溯过程，直到穷尽所有可能，最终判定匹配失败。

尝试的优化方案 #

为了避免回溯，我尝试了两种优化方式：

1. 原子组方案：

String new1 = test1.replaceAll("(?>\\s*),(?>\\s*)", ",");

2. 占有量词方案：

String new1 = test1.replaceAll("\\s*+,\\s*+", ",");

基准测试结果 #

我用JMH编写了基准测试，测试字符串为"hello"和"world"之间包含50000个空格且无逗号的情况，测试结果如下：

Benchmark                    Mode  Cnt  Score   Error  Units
RegexBench.atomicGroup      thrpt       0.387          ops/s
RegexBench.replaceAll       thrpt       0.162          ops/s
RegexBench.replaceExtended  thrpt       0.248          ops/s

从结果来看，原子组方案的吞吐量约为原生方案的2倍，但整体性能仍未达到理想状态。

困惑点 #

通过调试工具分析，\s*,\s*仅需86步即可判定无匹配，而原子组模式需要172步，理论上原生方案应该更快，但Java中的实际测试结果却与此相反，这让我感到困惑。

基准测试代码 #

@State(Scope.Thread)
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 1)
@Measurement(iterations = 1)
@Fork(1)
public class RegexBench {

    final static String s1 = divideTwoWordsByNumberOfSpaces("hello", "world", 50000);

    public static void main(final String[] args) throws IOException {
        org.openjdk.jmh.Main.main(args);
    }

    static String divideTwoWordsByNumberOfSpaces(final String word1, final String word2, final int numberOfSpaces) {
        final StringBuilder sb = new StringBuilder();
        sb.append(word1);
        for (int i = 0; i < numberOfSpaces; i++) {
            sb.append(" ");
        }
        sb.append(word2);
        return sb.toString();
    }

    @Benchmark
    public void replaceAll(final Blackhole blackhole) {
        String new1 = s1.replaceAll("\\s*,\\s*", ",");
    }

    @Benchmark
    public void replaceExtended(final Blackhole blackhole) {
        String new1 = s1.replaceAll("\\s*+,\\s*+", ",");
    }

    @Benchmark
    public void atomicGroup(final Blackhole blackhole){
        String new1 = s1.replaceAll("(?>\\s*),(?>\\s*)", ",");
    }
}

依赖配置（pom.xml） #

<!-- JMH核心依赖 -->
<dependency>
  <groupId>org.openjdk.jmh</groupId>
  <artifactId>jmh-core</artifactId>
  <version>1.36</version>
</dependency>

<!-- JMH注解处理器 -->
<dependency>
  <groupId>org.openjdk.jmh</groupId>
  <artifactId>jmh-generator-annprocess</artifactId>
  <version>1.36</version>
</dependency>

内容的提问来源于stack exchange，提问作者SkogensKonung