[SR-7749] Poor performance of String.replacingOccurrences(of:with:) in corelibs-foundation #3694
Description
| Previous ID | SR-7749 |
| Radar | rdar://56072687 |
| Original Reporter | gmilos (JIRA User) |
| Type | Bug |
| Status | Resolved |
| Resolution | Done |
Additional Detail from JIRA
| Votes | 0 |
| Component/s | Foundation |
| Labels | Bug |
| Assignee | @kevints |
| Priority | Medium |
md5: a019946d343f3e398647d7c8f94dddec
Issue Description:
The following piece of code:
import Foundation
let repeating = "\"."
let original = String(repeating: repeating, count: 1000000)
let start = Date()
_ = original.replacingOccurrences(of: "\"", with: "")
print("took: \(Date().timeIntervalSinceReferenceDate - start.timeIntervalSinceReferenceDate)")takes over 20s on Linux (4.1 release, Ubuntu 14.04), in comparison to Darwin version, which takes 0.1s.
The cause is O(n^2) algorithm, or more precisely O(m*n), where m is number of matches, n is the length of the string, used here:
If we built up a new string afresh, appending segments that don't match, we'd have O(n) algorithm.