Swift string vs [Character] and performance

user_7247062 0
Viewed 356

From the very beginning Swift strings were tricky since they work properly with UTF and there is a standard example from Apple:

    let cafe1 = "Cafe\u{301}"
    let cafe2 = "Café"
    print(cafe1 == cafe2)
    // Prints "true"

It means that comparison has some implicit logic and it's not a simple comparison of two memory areas are the same. I used to see recommendations to flat out strings into [Character] since when you do this all unicode-related conversions take place once and then all operations are faster. Additionally strings are not necessarily use continuous memory area which makes it more expensive to compare them than character arrays.

Long story short, I solved this problem on leetcode: https://leetcode.com/problems/implement-strstr/ and tried different approaches: KMP, character arrays and strings. To my surprise strings are the fastest.

How is it so? KMP has some prework and it is less efficient in general but why strings are faster than [Character]? Is it new for some recent Swift version or do I miss something conceptually?

Code that I used for reference:

  1. [Character], 8ms, 15mb memory
    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }
        
        var result: Int = -1
        
        let str = Array(haystack)
        let pattern = Array(needle)
        
        for i in 0...(str.count - pattern.count) {
            if str[i] == pattern[0] && Array(str[i...(i + pattern.count - 1)]) == pattern {
                result = i
                break
            }
        } 
        
        return result 
    }
  1. Strings, 4ms(!!!), 14.5mb memory
    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }
        
        var result: Int = -1
        
        for i in 0...(haystack.count - needle.count) {
            var hIdx = haystack.index(haystack.startIndex, offsetBy: i)
            if haystack[hIdx] == needle[needle.startIndex] {
                var hEndIdx = haystack.index(hIdx, offsetBy: needle.count - 1)
                if haystack[hIdx...hEndIdx] == needle {
                    result = i
                    break
                }
            }
        }
        
        return result 
    }
swift unicode string performance
1 Answers

First, I think there may be some misunderstandings on your part:

flat out strings into [Character] since when you do this all unicode-related conversions take place once and then all operations are faster

This doesn't make a lot of sense. Character has exactly the same issues as String. It still may be made of composed or decomposed UnicodeScalars that need special handling for equality.

Additionally strings are not necessarily use continuous memory area

This is equally true of Array. Nothing in Array promises that memory is contiguous. That's why ContiguousArray exists.

As to why String is faster than hand-coded abstractions, that should be obvious. If you could easily out-perform String with no major tradeoffs, then stdlib would implement String to do that.

To the mechanics of it, String does not promise any particular internal representation, so it heavily depends on how you're creating your strings. Small strings, for example, can be reduced all the way to a tagged pointer that requires zero memory (it can live in a register). Strings can be stored in UTF-8, but they can also be stored in UTF-16 (which is extremely fast to work with).

When Strings are compared with other Strings that know they have the same internal representations, then they can apply various optimizations. And this really points to one part of your problem:

Array(str[i...(i + pattern.count - 1)])

This is forcing a memory allocation and copy to create a new Array out of str. You would probably do much better if you used Slice for this work rather than making full Array copies. You'd almost certainly find in that case that you're exactly matching String's implementations (using SubStr).

But the real lesson here is that you're unlikely to beat String at its own game in the general case. If you happen to have very specialized knowledge about your Strings, then I can see where you'd be able to beat the general-purpose String algorithms. But if you think you're beating stdlib for arbitary strings, why would stdlib not just implement what you're doing (and beat you using knowledge of the internal details of String)?

user_973370
Related