Three new books, Go Optimizations 101, Go Details & Tips 101 and Go Generics 101 are published now. It is most cost-effective to buy all of them through this book bundle in the Leanpub book store.

Please follow Go 101 Twitter account @Go100and1 to get latest news of Go 101 books/articles/apps/libraries.

No Safe Efficient Ways to Do Three-way String Comparisons in Go

Three-way string comparison is widely used in programming (proof 1 and proof 2). But up to now (Go 1.19), the strings.Compare function in the standard library is (intentionally) implemented with a non-opitimized way:

func Compare(a, b string) int {
	// NOTE(rsc): This function does NOT call the runtime cmpstring function,
	// because we do not want to provide any performance justification for
	// using strings.Compare. Basically no one should use strings.Compare.
	// As the comment above says, it is here only for symmetry with package bytes.
	// If performance is important, the compiler should be changed to recognize
	// the pattern so that all code doing three-way comparisons, not just code
	// using strings.Compare, can benefit.
	if a == b {
		return 0
	}
	if a < b {
		return -1
	}
	return +1
}

When comparing two unequal strings, the implementation will perform two comparison operations. Whereas a perfect implementation only needs one, just like the implementation of bytes.Compare shown below, in which bytealg.Compare is implemented using assembly code on most architectures.

func Compare(a, b []byte) int {
	return bytealg.Compare(a, b)
}

The strings.Compare implementation is comparatively inefficent. Specifically, it is less efficent when the two string operands are not equal but their lengths are equal.

Benchmark code constantly shows strings.Compare uses 2x CPU time of bytes.Compare when comparing unequal same-length byte sequences (we view both strings and byte slices as byte sequences here).

The internal comment for the current strings.Compare implementation is some interesting. The comment suggests that we should not use strings.Compare in Go at all, but no alternative efficient ways are available now yet (ironically, this function is used in Go toolchain code and recommended by a standard library function). It mentions that the compiler should make special optimizations to automatically convert the code using comparision operators into internal optimized three-way comparisons if possible. However, such compiler optimizations have never been made, and there are no plans to make such optimizations yet as far as I know. Personally, I doubt such optimizations are feasible to be made for any use case. So I think the strings.Compare should be implemented efficiently, to avoid breaking user expectations.

(This is one of the dozens of facts mentioned in the Go Optimizations 101 book.)

Update: view discussions on reddit and HN.


Index↡

The Go 101 project is hosted on Github. Welcome to improve Go 101 articles by submitting corrections for all kinds of mistakes, such as typos, grammar errors, wording inaccuracies, description flaws, code bugs and broken links.

If you would like to learn some Go details and facts every serveral days, please follow Go 101's official Twitter account @go100and1 or join Go 101 slack channels.

Tapir, the author of Go 101, has been on writing the Go 101 series books and maintaining the go101.org website since 2016 July. New contents will be continually added to the book and the website from time to time. Tapir is also an indie game developer. You can also support Go 101 by playing Tapir's games (made for both Android and iPhone/iPad):
Individual donations via PayPal are also welcome.

Index: