현재 3권의 신간들인 Go Optimizations 101, Go Details & Tips 101Go Generics 101이 출간되어 있습니다. Leanpub 서점에서 번들을 모두 구입하시는 방법이 비용 대비 효율이 가장 좋습니다.

Go에 대한 많은 정보들과 Go 101 책들의 최신 소식을 얻으시려면 Go 101 트위터 계정인 @Go100and1을 팔로잉 해주세요.

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 프로젝트는 Github 에서 호스팅됩니다. 오타, 문법 오류, 부정확한 표현, 설명 결함, 코드 버그, 끊어진 링크와 같은 모든 종류의 실수에 대한 수정 사항을 제출하여 Go 101을 개선을 돕는 것은 언제나 환영합니다.

주기적으로 Go에 대한 깊이 있는 정보를 얻고 싶다면 Go 101의 공식 트위터 계정인 @go100and1을 팔로우하거나 Go 101 슬랙 채널에j가입해주세요.

Go 101의 저자인 Tapir는 2016년 7월부터 Go 101 시리즈 책들을 집필하고 go101.org 웹사이트를 유지 관리하고 있습니다. 새로운 콘텐츠는 책과 웹사이트에 수시로 추가될 예정입니다. Tapir는 인디 게임 개발자이기도 합니다. Tapir의 게임을 플레이하여 Go 101을 지원할 수도 있습니다. (안드로이드와 아이폰/아이패드용):
  • Color Infection (★★★★★), 140개 이상의 단계로 이루어진 물리 기반의 캐주얼 퍼즐 게임
  • Rectangle Pushers (★★★★★), 2가지 모드와 104개 이상의 단계로 이루어진 캐주얼 퍼즐 게임
  • Let's Play With Particles, 세가지 미니 게임이 있는 캐주얼 액션 게임
페이팔을 통한 개인 기부도 환영합니다.

색인: