Slow Swift String Performance

A Swift String is a collection of Characters, and a Character represents a single extended grapheme cluster, that can be one or moreUnicode scalars. That makes some index operations like "skip the first N characters" slow.

But the first improvement is to "short-circuit" the isPalindrome()function. Instead of building the reversed string completely, comparethe character sequence with its reversed sequence and stop as soonas a difference is found:

func isPalindrome(_ s: String) -> Bool {    return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }}

s.characters.reversed() does not create a new collection in reverseorder, it just enumerates the characters from back to front.With String(s.characters.reversed()) as in your method however, you force the creation of a new collection for the reversed string,that makes it slow.

For the 110-character string

let string = String(repeating: "Hello world", count: 10)

this reduces the computation time from about 6 sec to 1.2 sec in my test.

Next, avoid index calculations like

let endIndex = string.index(string.startIndex, offsetBy: length-1)

and iterate over the character index itself instead:

func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(string: String, partiton: [String]) {        if string.isEmpty {            result.append(partiton)            return        }        var idx = string.startIndex        repeat {            string.characters.formIndex(after: &idx)            let part = string.substring(to: idx)            if isPalindrome(part) {                let leftPart = string.substring(from: idx)                dfs(string: leftPart, partiton: partiton + [part])            }        } while idx != string.endIndex    }    func isPalindrome(_ s: String) -> Bool {        return !zip(s.characters, s.characters.reversed()).contains { $0 != $1 }    }    dfs(string: s, partiton: [])    return result}

Computation time is now 0.7 sec.

The next step is to avoid string indexing totally, and work withan array of characters, because array indexing is fast. Even better,use array slices which are fast to create and reference the originalarray elements:

func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(chars: ArraySlice<Character>, partiton: [String]) {        if chars.isEmpty {            result.append(partiton)            return        }        for length in 1...chars.count {            let part = chars.prefix(length)            if isPalindrome(part) {                let leftPart = chars.dropFirst(length)                dfs(chars: leftPart, partiton: partiton + [String(part)])            }        }    }    func isPalindrome(_ c: ArraySlice<Character>) -> Bool {        return !zip(c, c.reversed()).contains { $0 != $1 }    }    dfs(chars: ArraySlice(s.characters), partiton: [])    return result}

Computation time is now 0.08 sec.

If your string contains only characters in the "basic multilingual plane" (i.e. <= U+FFFF) then you can work with UTF-16 code points instead:

func partition(_ s: String) -> [[String]] {    var result: [[String]] = []    func dfs(chars: ArraySlice<UInt16>, partiton: [String]) {        if chars.isEmpty {            result.append(partiton)            return        }        for length in 1...chars.count {            let part = chars.prefix(length)            if isPalindrome(part) {                let leftPart = chars.dropFirst(length)                part.withUnsafeBufferPointer {                    dfs(chars: leftPart, partiton: partiton + [String(utf16CodeUnits: $0.baseAddress!, count: length)])                }            }        }    }    func isPalindrome(_ c: ArraySlice<UInt16>) -> Bool {        return !zip(c, c.reversed()).contains { $0 != $1 }    }    dfs(chars: ArraySlice(s.utf16), partiton: [])    return result}

Computation time is now 0.04 sec for the 110 character test string.

So some tips which potentially can improve the performance when working with Swift strings are

• Iterate over the characters/indices sequentially. Avoid "jumping"to the n'th position.
• If you need "random" access to all characters, convert the stringto an array first.
• Working with the UTF-16 view of a string can be faster than workingwith the characters view.

Of course it depends on the actual use-case. In this application,we were able to reduce the computation time from 6 sec to 0.04 sec,that is a factor of 150.