Blog

How to Efficiently Compare Strings in Go

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 executed Nanoseconds (ns) per operation
BenchmarkEqualFoldBothEqual-8 20000000 124 ns/op
BenchmarkToLowerBothEqual-8 10000000 339 ns/op

When both strings are equal until the last rune


Operations executed Ns per operation
BenchmarkEqualFoldLastRuneNotEqual-8 20000000 129 ns/op
BenchmarkToLowerLastRuneNotEqual-8 10000000 346 ns/op

When both strings are distinct


Operations executed Ns per operation
BenchmarkEqualFoldFirstRuneNotEqual-8 300000000 11.2 ns/op
BenchmarkToLowerFirstRuneNotEqual-8 10000000 333 ns/op

When both strings have a different case at rune 0


Operations executed Ns per operation
BenchmarkEqualFoldFirstRuneDifferentCase-8 20000000 125 ns/op
BenchmarkToLowerFirstRuneDifferentCase-8 10000000 433 ns/op

When both strings have a different case in the middle


Operations executed Ns per operation
BenchmarkEqualFoldMiddleRuneDifferentCase-8 20000000 123 ns/op
BenchmarkToLowerMiddleRuneDifferentCase-8 10000000 428 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.