Golang: 文字列比較

Posted on 3 mins read

今回の結論は文字列比較はシンプルなのが良い。

今はgo1.8beta2とかのタグが切られているけれど、今年(2016)の8月Go1.7がリリースされた。 この時の改善項目にbounds check elimination(BCE)最適化が含まれている。

bounds check elimination(BCE)は配列にインデックスを用いてアクセスする際に適切な範囲か確認する必要があるが、静的に判定する事で実行時の確認を極力減らす事を目的としているらしい。

サンプルコードを用いた解説記事があるので読むと分かりやすい。

同じ配列に対して同一スコープ内で以前利用した添え字以下の添え字でのアクセスが確定している時に範囲確認を省略できる(bounds check eliminatd)というもの。 で、同じ人がベンチマークを取っていた。 記事内では*[]int* を対象にしていたけど個人的には文字列が気になった。 go test -benchの練習も兼ねて文字列でBCEのコードを試した。

さほど真面目な検証はしてないけど今回の結論としては文字列比較はシンプルな比較が最速。

やってみた結果はこちら。 こんなものを書きました。 Jxckさんの記事とリファレンスと go help testflagコマンドでだいたい掴める。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

$ go test -bench .
testing: warning: no tests to run
BenchmarkCompareString_Reflect                   5000000               219 ns/op
BenchmarkCompareString_Simple                   1000000000               2.82 ns/op
BenchmarkCompareString_General                  50000000                27.4 ns/op
BenchmarkCompareString_BCE                      100000000               26.2 ns/op
BenchmarkCompareString_Pointer                  50000000                27.5 ns/op
BenchmarkCompareString_PointerAndBCE            100000000               26.6 ns/op
BenchmarkCompareString_GeneralNoNil             50000000                24.9 ns/op
BenchmarkCompareString_BCENoNil                 50000000                26.5 ns/op
BenchmarkCompareString_PointerNoNil             50000000                25.0 ns/op
BenchmarkCompareString_PointerAndBCENoNil       100000000               25.4 ns/op
PASS
ok      _/home/vagrant/works/playground/cmp-strings     19.062s

$ go test -bench . -benchtime 2s
testing: warning: no tests to run
BenchmarkCompareString_Reflect                  20000000               223 ns/op
BenchmarkCompareString_Simple                   2000000000               2.75 ns/op
BenchmarkCompareString_General                  100000000               25.8 ns/op
BenchmarkCompareString_BCE                      100000000               26.4 ns/op
BenchmarkCompareString_Pointer                  100000000               26.7 ns/op
BenchmarkCompareString_PointerAndBCE            100000000               25.7 ns/op
BenchmarkCompareString_GeneralNoNil             100000000               26.4 ns/op
BenchmarkCompareString_BCENoNil                 100000000               24.8 ns/op
BenchmarkCompareString_PointerNoNil             100000000               26.7 ns/op
BenchmarkCompareString_PointerAndBCENoNil       100000000               25.8 ns/op
PASS
ok      _/home/vagrant/works/playground/cmp-strings     31.538s

気になって一番早かったCompareString のアセンブリみてみたらCALL runtime.eqstring でランタイムの専用命令に飛んでいる。

"".CompareString_Simple t=1 size=108 args=0x28 locals=0x30
        0x0000 00000 (./string.go:8)    TEXT    "".CompareString_Simple(SB), $48-40
        0x0000 00000 (./string.go:8)    MOVQ    (TLS), CX
        0x0009 00009 (./string.go:8)    CMPQ    SP, 16(CX)
        0x000d 00013 (./string.go:8)    JLS     101
        0x000f 00015 (./string.go:8)    SUBQ    $48, SP
        0x0013 00019 (./string.go:8)    MOVQ    BP, 40(SP)
        0x0018 00024 (./string.go:8)    LEAQ    40(SP), BP
        0x001d 00029 (./string.go:8)    FUNCDATA        $0, gclocals<C2><B7>1c5a071f4ad97fe89533b360c694a573(SB)
        0x001d 00029 (./string.go:8)    FUNCDATA        $1, gclocals<C2><B7>33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x001d 00029 (./string.go:9)    MOVQ    "".a+64(FP), AX
        0x0022 00034 (./string.go:9)    MOVQ    "".b+80(FP), CX
        0x0027 00039 (./string.go:9)    CMPQ    AX, CX
        0x002a 00042 (./string.go:9)    JEQ     $0, 60
        0x002c 00044 (./string.go:9)    MOVL    $0, AX
        0x002e 00046 (./string.go:9)    MOVB    AL, "".~r2+88(FP)
        0x0032 00050 (./string.go:9)    MOVQ    40(SP), BP
        0x0037 00055 (./string.go:9)    ADDQ    $48, SP
        0x003b 00059 (./string.go:9)    RET
        0x003c 00060 (./string.go:9)    MOVQ    "".a+56(FP), DX
        0x0041 00065 (./string.go:9)    MOVQ    DX, (SP)
        0x0045 00069 (./string.go:9)    MOVQ    AX, 8(SP)
        0x004a 00074 (./string.go:9)    MOVQ    "".b+72(FP), AX
        0x004f 00079 (./string.go:9)    MOVQ    AX, 16(SP)
        0x0054 00084 (./string.go:9)    MOVQ    CX, 24(SP)
        0x0059 00089 (./string.go:9)    PCDATA  $0, $0
        0x0059 00089 (./string.go:9)    CALL    runtime.eqstring(SB)
        0x005e 00094 (./string.go:9)    MOVBLZX 32(SP), AX
        0x0063 00099 (./string.go:9)    JMP     46
        0x0065 00101 (./string.go:9)    NOP
        0x0065 00101 (./string.go:8)    CALL    runtime.morestack_noctxt(SB)

そしてruntime.eqstring のコードは*/usr/local/go/src/runtime/asm_amd64.s* に含まれており、以下の通りとてもシンプルにアセンブリで書かれていた。 大雑把な流れは下になっていた。

  1. ポインタ一致検査
  2. 実体検査 2. 実体サイズ(8以下, 64以下, それ以外)で切り替えて実行

64バイトより大きいバイトではAVX2命令を利用した処理に飛んでいる。 AVX2命令はSIMD命令で複数の演算を並列処理することで効率化するらしい。 AVX2命令群はスカラー・浮動小数点などいろいろとサポートしているらしい。 Intel® 64 and IA-32 Architectures Software Developer Manualsが公式リファレンス。

AVX2命令に入る以外のジャンプ先を含めたソースコードを貼ると下な感じになっていてsmall, bigloopともシンプルな挙動だった。

TEXT runtime·eeqstringSB),NOSPLIT,$0-33
  MOVQ  s1str+0(FP), SI
  MOVQ  s2str+16(FP), DI
  CMPQ  SI, DI
  JEQ eq
  MOVQ  s1len+8(FP), BX
  LEAQ  v+32(FP), AX
  JMP runtime·memeqbody(SB)
eq:
  MOVB  $1, v+32(FP)
  RET

// a in SI
// b in DI
// count in BX
// address of result byte in AX
TEXT runtime·memeqbody(SB),NOSPLIT,$0-0
  CMPQ  BX, $8
  JB  small
  CMPQ  BX, $64
  JB  bigloop
  CMPB    runtime·support_avx2(SB), $1
  JE  hugeloop_avx2

  // 8 bytes at a time using 64-bit register
bigloop:
  CMPQ  BX, $8
  JBE leftover
  MOVQ  (SI), CX
  MOVQ  (DI), DX
  ADDQ  $8, SI
  ADDQ  $8, DI
  SUBQ  $8, BX
  CMPQ  CX, DX
  JEQ bigloop
  MOVB  $0, (AX)
  RET

  // remaining 0-8 bytes
leftover:
  MOVQ  -8(SI)(BX*1), CX
  MOVQ  -8(DI)(BX*1), DX
  CMPQ  CX, DX
  SETEQ (AX)
  RET
comments powered by Disqus