Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does Go do string comparison?

Tags:

go

http://golang.org/ref/spec#Comparison_operators

Go supports string comparison without any special functions. Does the Go runtime do work behind the scenes to make comparisons of string literals?

like image 588
Brenden Avatar asked Nov 27 '13 02:11

Brenden


People also ask

How does string compare work in Golang?

Using Compare() method: You can also compare two strings using the built-in function Compare() provided by the strings package. This function returns an integer value after comparing two strings lexicographically. The return values are: Return 0, if str1 == str2.

How is string comparison done?

The algorithm to compare two strings is simple: Compare the first character of both strings. If the first character from the first string is greater (or less) than the other string's, then the first string is greater (or less) than the second. We're done.

How are string represented in Go?

Go supports two styles of string literals, the double-quote style (or interpreted literals) and the back-quote style (or raw string literals). The zero values of string types are blank strings, which can be represented with "" or `` in literal. Strings can be concatenated with + and += operators.

How do you compare in Go?

The Go programming language has a small set of known rules for comparing and ordering values. As you saw, while values from all types are comparable using the == (or !=) operator, only a few types can be compared using order operators such as <, >, <=, and >=.


2 Answers

As you can see in the following assembly dump, string comparison is delegated to a runtime.eqstring function from the runtime (line 17) after a short circuit check to see if the two operands are the same in-memory string (line 11):

$ cat foo.go package main  func main() {         a := "hello"         b := "world"         _ = a == b }  $ go tool 6g -S foo.go --- prog list "main" --- 0000 (foo.go:3) TEXT    main+0(SB),$40-0 0001 (foo.go:3) LOCALS  ,$0 0002 (foo.go:4) LEAQ    go.string."hello"+0(SB),BX 0003 (foo.go:4) MOVQ    (BX),SI 0004 (foo.go:4) MOVQ    8(BX),CX 0005 (foo.go:5) LEAQ    go.string."world"+0(SB),BX 0006 (foo.go:5) MOVQ    (BX),DX 0007 (foo.go:5) MOVQ    8(BX),AX 0008 (foo.go:6) JMP     ,11 0009 (foo.go:6) MOVQ    $1,AX 0010 (foo.go:6) JMP     ,23 0011 (foo.go:6) CMPQ    CX,AX 0012 (foo.go:6) JNE     ,22 0013 (foo.go:6) MOVQ    SI,(SP) 0014 (foo.go:6) MOVQ    CX,8(SP) 0015 (foo.go:6) MOVQ    DX,16(SP) 0016 (foo.go:6) MOVQ    AX,24(SP) 0017 (foo.go:6) CALL    ,runtime.eqstring+0(SB) 0018 (foo.go:6) MOVBQZX 32(SP),BX 0019 (foo.go:6) CMPB    BX,$0 0020 (foo.go:6) JEQ     ,22 0021 (foo.go:6) JMP     ,9 0022 (foo.go:6) MOVQ    $0,AX 0023 (foo.go:7) RET     ,  --- prog list "init" --- 0024 (foo.go:7) TEXT    init+0(SB),$0-0 0025 (foo.go:7) MOVBQZX initdone·+0(SB),AX 0026 (foo.go:7) LOCALS  ,$0 0027 (foo.go:7) CMPB    AX,$0 0028 (foo.go:7) JEQ     ,34 0029 (foo.go:7) CMPB    AX,$2 0030 (foo.go:7) JNE     ,32 0031 (foo.go:7) RET     , 0032 (foo.go:7) CALL    ,runtime.throwinit+0(SB) 0033 (foo.go:7) UNDEF   , 0034 (foo.go:7) MOVB    $2,initdone·+0(SB) 0035 (foo.go:7) RET     , 

Unless you are working on the compiler or runtime, this shouldn't concern you too much: just use the operators as the spec defines, and expect that the comparison to be O(n) with the length of the string.

like image 77
James Henstridge Avatar answered Sep 18 '22 22:09

James Henstridge


runtime/string.goc (go1.3):

func eqstring(s1 String, s2 String) (v bool) {     if(s1.len != s2.len) {         v = false;         return;     }     if(s1.str == s2.str) {         v = true;         return;     }     v = runtime·memeq(s1.str, s2.str, s1.len); }  int32 runtime·strcmp(byte *s1, byte *s2) {     uintptr i;     byte c1, c2;      for(i=0;; i++) {         c1 = s1[i];         c2 = s2[i];         if(c1 < c2)             return -1;         if(c1 > c2)             return +1;         if(c1 == 0)             return 0;     } } 

Note: The runtime· separator is a Unicode middle-dot, not a period.

like image 45
peterSO Avatar answered Sep 17 '22 22:09

peterSO