Performance of the new Regex in Swift 5.7 degrades quadratically without need

Using Swift
1

Today I tried to use the new Regex from Swift 5.7 to parse CSS variables in a 2000 line CSS file. The old NSRegularExpression class performed the job in 0.0001s on my Intel iMac whereas the new Regex takes 1000x longer, namely 0.25s. Luckily, @objc found an even simpler test case which directly shows the problem:

let pattern = "^ +A"
let regex1 = try! NSRegularExpression(pattern: pattern)
let regex2 = try! Regex(pattern)
let numberOfSpaces = 50000
let testString = String(repeating: " ", count: numberOfSpaces)
let date = Date()
print(regex1.firstMatch(in: testString, range: .init(location: 0, length: numberOfSpaces)) == nil)
print(-date.timeIntervalSinceNow)
print(try! regex2.firstMatch(in: testString) == nil)
print(-date.timeIntervalSinceNow)

Regex seems to perform a lot of unneeded backtracking. I consider this a serious bug.

6 Likes
2

Are you testing by compiling with optimizations enabled?

3

The optimizer level does not make a difference in this case.

4

Good to know.

5

Note this seems to be O(n*n): Doubling numberOfSpaces leads to a roughly quadrupled run time.

1 Like
6

I opened Issue 483 to track this.

3 Likes