Comparing strings might not be something you think about when optimizing software. Typically, optimization includes tasks like splitting loops across goroutines, finding a faster hashing algorithm, or something that sounds more scientific. There is a sense of accomplishment we get when making changes like this. However, string comparison can often be the top bottleneck in a pipeline. For example, the snippet below is often used, but it is the worst solution (benchmarks below) and it has caused real problems.
strings.ToLower(name) == strings.ToLower(othername)
This appears to be pretty straightforward. Convert each string to lowercase and then compare. To understand why this is a bad solution you have to know what a string represents and how `ToLower` works.
But first, let’s talk about the primary use-cases for string comparisons. When comparing using the normal `==` operator, we get the quickest and most optimized solution. However, APIs and similar software usually take case into consideration. This is when we drop in `ToLower` and call it feature-complete.
In Go, a string is an immutable sequence of runes. Rune is a term Go uses to represent a code point. You can read more about strings, bytes, runes and characters at the Go blog. `ToLower` is a standard library function that loops over each rune in a string, converts it to lowercase, and returns the newly formed string. So the above code traverses each string entirely before the comparison. It is tight-bound to the length of the strings. Here is some pseudo code that roughly represents the complexity of the above snippet.
Note: Because strings are immutable, strings.ToLower allocates new memory space for two new strings. This contributes to the time complexity, but this is not the focus now. For brevity, the pseudo code below assumes that strings are mutable.
// Pseudo code func CompareInsensitive(a, b string) bool { // loop over string a and convert every rune to lowercase for i := 0; i < len(a); i++ { a[i] = unicode.ToLower(a[i]) } // loop over string b and convert every rune to lowercase for i := 0; i < len(b); i++ { b[i] = unicode.ToLower(b[i]) } // loop over both a and b and return false if there is a mismatch for i := 0; i < len(a); i++ { if a[i] != b[i] { return false } } return true }
The time complexity is O(n) where n is len(a) + len(b) + len(a). Here’s an example:
CompareInsensitive(“fizzbuzz”, “buzzfizz”)
That means we will loop up to 24 times to discover that two *completely distinct strings* do not match. This is highly inefficient. We could tell these strings were distinct by comparing unicode.ToLower(a[0]) and unicode.ToLower(b[0]) (pseudo code). So let’s take that into consideration.
To optimize, We can *remove* the first two loops in `CompareInsensitive` and compare each character in each position. If runes don’t match, we would then convert the runes to lowercase and then compare again. If they still don’t match then we break the loop and consider the two strings a mismatch. If they match we can continue to the next rune until the end is reached or until a mismatch is found. Let’s rewrite this code.
// Pseudo code func CompareInsensitive(a, b string) bool { // a quick optimization. If the two strings have a different // length then they certainly are not the same if len(a) != len(b) { return false } for i := 0; i < len(a); i++ { // if the characters already match then we don’t need to // alter their case. We can continue to the next rune if a[i] == b[i] { continue } if unicode.ToLower(a[i]) != unicode.ToLower(b[i]) { // the lowercase characters do not match so these // are considered a mismatch, break and return false return false } } // The string length has been traversed without a mismatch // therefore the two match return true }
The new function is much more efficient. The upper bounds is the length of one string rather than the sum of the length of both strings. What does this look like with our comparison above? Well, the loop will only ever run eight times at most. However, since the first two runes are not the same this loop only runs once. We have optimized our comparison over twenty fold!
Fortunately, there is a function in the strings package for this. It’s called strings.EqualFold.
Benchmarks
When both strings are equal
Operations executedNanoseconds (ns) per operationBenchmarkEqualFoldBothEqual-820000000124 ns/opBenchmarkToLowerBothEqual-810000000339 ns/op
When both strings are equal until the last rune
Operations executedNs per operationBenchmarkEqualFoldLastRuneNotEqual-820000000129 ns/opBenchmarkToLowerLastRuneNotEqual-810000000346 ns/op
When both strings are distinct
Operations executedNs per operationBenchmarkEqualFoldFirstRuneNotEqual-830000000011.2 ns/opBenchmarkToLowerFirstRuneNotEqual-810000000333 ns/op
When both strings have a different case at rune 0
Operations executedNs per operationBenchmarkEqualFoldFirstRuneDifferentCase-820000000125 ns/opBenchmarkToLowerFirstRuneDifferentCase-810000000433 ns/op
When both strings have a different case in the middle
Operations executedNs per operationBenchmarkEqualFoldMiddleRuneDifferentCase-820000000123 ns/opBenchmarkToLowerMiddleRuneDifferentCase-810000000428 ns/op
There is a staggering difference (by 30 times!) when the first rune of each string does not match. This is because instead of looping over both strings and then comparing, the loop only runs one time and immediately returns false. In every case, `EqualFold` outperforms our initial comparison by orders of magnitude.
Does it Matter?
You might be thinking that 400 nanoseconds does not matter. In most cases you might be right. However, some micro-optimizations are as simple as any other solution. In this case it is easier than the original solution.
Quality engineers have simple optimizations in their normal workflow. They don’t wait to optimize software once it becomes an issue, they write optimized software from the beginning. Even for the best engineers, it is unlikely and unrealistic to write the most efficient software from the ground up. It is virtually impossible to think of every edge-case and optimize for it. After all, we rarely know the wild behaviors of our users until we set them loose on our software.
However, embedding these simple solutions into your normal workflow will improve the lifespan of applications and prevent unnecessary bottlenecks in the future. Even if that bottleneck never matters, you didn’t waste any effort.
Brett Jones is a Senior Software Engineer and Tech Lead for the Insights team at DigitalOcean. He is happily married with two amazing kids. He loves philosophy, history, fantasy books, and the Dallas Stars. You can find his work at github.com/blockloop.
