What is the runtime performance of `String.contains(_:)`?

Development Foundation
1

I'm curious if anyone has more information about the runtime complexity performance of testing if one string contains another:

import Foundation

let query = "a"
let s = "abc"
let result = s.contains(query)
print(result)

There seems to be one concrete version of this API:

And one generic version across StringProtocol:

What I am not able to see so far is any documentation explaining what the runtime expectations of this should be.

AFAIK these both forward down to CFString:

Which is doing a lot of work in about 500 LOC. Would anyone be able to help quickly confirm if the expected runtime should be O[n * m]? Or is it using something like Rabin–Karp to improve expected runtime?

2

I’ve never looked at that piece of code before, having just skimmed it now, so treat this as a drive by comment from a human simulating an AI if you want.

It looks like most of the complexity here is around localization and so on, and I don’t see anything that looks like a preprocessing pass over str2 to suggest this is doing anything like Rabin-Karp or Boyer-Moore. I could be wrong though.

But typically if you want one of those algorithms you’d want an API to expose the pattern preprocessing step.

I also haven’t done any benchmarks, but in theory a regex .*foo.* could compile down to an automaton that is asymptotically faster than the O(m*n) algorithm. Perhaps constant time overhead will eat any wins there though.

If you really need this to be as efficient as possible, I would suggest rolling your own, string matching algorithms are quite fun and you’ll learn a lot of tricks along the way. (Of course that’s assuming you don’t need to deal with exotic encodings, for UTF8 just treating the pattern as a string of bytes is almost always good enough I think).

4 Likes
3

Also worth noting that _ns and _ephemeralString both bridge the Strings in question, which for non-ASCII may well be significantly slower than the actual search.

3 Likes
4

Shameless self-plug and FWIW, but we switched our internal usage from String.contains to use FuzzyMatch with a query matching configuration set up for strict non-fuzzy matching parameters giving String.contains semantics -- which gives a 10x improvement for us -- may or may not be usable for you depending on full Unicode/localization requirements and other factors, so YMMV on applicability (we work with a limited set of languages though, so it's definitely not for everyone). Some documentation in the repo if you want details on approach.

3 Likes
5

I can confirm @Slava_Pestov 's comment and assure you that we're not doing any optimization here like Boyer-Moore.

The localized path is a little tricky. It's neither performant or correct. The right solution would be to use the collation algorithm, but we're not using that here.

Also, I know that you're referring to the corelibs's implementation, but just a note that even on Darwin we're using a mix of our in-house implementation (very similar if not entirely the same as the one you linked here) and ICU API, so I think the complexity would be the the max of the two

2 Likes