Bug #19534: [ruby 3.2.1] Regular expression comparisons may be slower than in older versions.

• Status: Closed
• Assignee: make_now_just (Hiroya Fujinami)
• Target version: -
• ruby -v: ruby 3.2.1 (2023-02-08 revision 31819e82c8) [x86_64-darwin19]
• Backport: 2.7: UNKNOWN, 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN

[mizuKyo (kyosuke mizukami)]

Hello Sir.
When scanning a string with a regular expression created using many Japanese words, there was a slowdown compared to older versions.
I hope it will be fixed.

• Environment

% ruby -v
ruby 3.2.1 (2023-02-08 revision 31819e82c8) [x86_64-darwin19]

• Reproduction Code

require "benchmark"
​
Benchmark.bm do |bm|
  3.times do
    keywords = Array.new(5000)
    keywords.each_index do |idx|
      keywords[idx] = (1..20).map {|e| (0x3042+Random.new.rand(0..82)).chr(Encoding::UTF_8)}.join
    end
    regx = ::Regexp.union(keywords)
​
    text = (1..600).map {|e| (0x3042+Random.new.rand(0..82)).chr(Encoding::UTF_8)}.join
​
    bm.report { text.scan(regx) }
  end
end

• Execution Result(ruby 3.2.1 (2023-02-08 revision 31819e82c8))

       user     system      total        real
   1.987753   0.005704   1.993457 (  1.999683)
   1.760431   0.001623   1.762054 (  1.763006)
   1.735989   0.001269   1.737258 (  1.738554)

• Execution Result(ruby 3.1.2p20 (2022-04-12 revision 4491bb740a))

       user     system      total        real
   0.235801   0.000000   0.235801 (  0.235812)
   0.236888   0.000087   0.236975 (  0.236976)
   0.235981   0.000000   0.235981 (  0.235983)

[wanabe (_ wanabe)]

According to git bisect, this seems to be happening after 881bf9a0b8.
It appears to me that this slowdown is due to #19104 and is an unavoidable sacrifice to avoid ReDoS.

If this is a problem in the actual application, it may give more reason why the problem should be solved.

[hsbt (Hiroshi SHIBATA)]

• Status changed from Open to Assigned
• Assignee set to make_now_just (Hiroya Fujinami)

[jeremyevans0 (Jeremy Evans)]

• Status changed from Assigned to Closed