Big Sky

昨日僕の Twitter タイムラインで q というツールが話題に上がっていました。

GitHub - harelba/q: q - Run SQL directly on CSV or TSV files

Text as Data q is a command line tool that allows direct execution of SQL-like q...

https://github.com/harelba/q

標準入力を SQL で抽出できるという物です。ただ個人的には「こういうの python じゃなくて Go でビルドされてると助かるよなー」と思ったので q と同じ様な動作になるツールを作ってみました。

GitHub - mattn/qq

Select stdin with query

https://github.com/mattn/qq

例えば msys2 のシェル上で ps を実行すると以下の様になりますが

$ ps
      PID    PPID    PGID     WINPID   TTY         UID    STIME COMMAND
     4876    2000    4876      13840  pty1     1061251 18:31:09 /usr/bin/ps
     2000   11384    2000       8804  pty1     1061251 18:30:45 /usr/bin/bash
    11384       1   11384      11384  ?        1061251 18:30:45 /usr/bin/mintty
     7552   13692   13692       9428  pty0     1061251 17:51:39 /usr/bin/ssh
    13692   12148   13692      18360  pty0     1061251 17:51:39 /usr/bin/ssh
     7828       1    7828       7828  ?        1061251 16:11:41 /usr/bin/ssh-agent
    12148       1   12148      12148  ?        1061251 17:51:39 /usr/bin/mintty


これを qq に食わせると

$ ps | qq -q 'select pid from stdin'
2000
11384
9596
7552
13692
7828
12148


この様に表形式のコマンド出力を SQL で抽出ます。

q と違う所は、日本語の幅をきちんと見ている所です。

aaa bb
a b あ


この様なテキストの場合、カラム aaa には a b が、カラム bb には あ が入る事を期待してしまいます。q の場合

$ cat nihongo.txt | q -H 'select bb from -'
b


この様にカラム bb には b が入っていますが、qq だと

$ cat nihongo.txt | qq -q 'select bb from stdin'
あ


あ が格納されています。q の場合、日本語が多く混じると異なるカラムに値が入ってしまいますが、qq だと大丈夫。また qq では q と同じ動作にさせる事もできます。-ip オプションでデリミタを正規表現として渡せるので

$ cat nihongo.txt | qq -ip '\s+' -q 'select bb from stdin'
b


こうすれば b が得られます。また -ic オプションを付けるとカンマセパレータの CSV (ダブルクオート可)で、-it でタブセパレートな TSV で入力データを扱う事ができます。さらに -e オプションでエンコーディング名を指定できるので Windows の Excel で作った CSV ファイルでも安心して扱えます。

品目,単価
みかん,120
りんご,100
トマト,180
$ cat meisai.csv | qq -ic -e cp932 -q "select 単価 from stdin where 品目 = 'みかん'"
120
出力フォーマットはデフォルトが CSV です。-oh を付けるとヘッダカラムが出力されます。-oj を付けると JSON 形式で出力されるのでシステムの一部として使う事も出来るかもしれません。また -or で raw 出力しますので、 $ ps | qq -q "select pid from stdin where command = '/usr/bin/grep'" | xargs kill


の様に awk や grep の代わりに使う事もできます。もちろん golang なのでバイナリ1つで動きますし、python が無い環境でも動きます。SQL なので grep では難しい抽出方法も可能ですね。

最初は q を golang に移植するだけのつもりでしたが、思ったより便利そうなので公開してみました。よろしければどうぞお使い下さい。

後で引数からファイルを取ってunionとか出来る様にする予定なので、その場合は標準入力と区別するために - を採用する予定です。その場合、実行方法が上記の記事と異なる可能性があります。

記事中に間違いがありました。数倍も速くはなりませんでした。確か 1.0X ～ 1.1 倍程度の高速化は得られましたがびっくりするほどの物ではありませんでした。すみません。

そろそろ Go1.7 がリリースされるそうですが、皆さん如何お過ごしですか。Go 界隈の波平こと mattn ですこんにちわ。ﾊﾞｶﾓｰ(略

Go1.7 ではコンパイラの最適化が行われ、ビルド速度がかなり短縮される様になりました。毎日ビルドしてる僕としては非常に嬉しい機能改善ですね。

さてとてもキャッチ―なタイトルで釣ってしまった訳ですが、気にしたら負けなのでどんどん話を進めます。

var t [256]byte

func f(b *[16]byte) {
    for i, v := range b {
        b[i] = t[v]
    }
}


例えばこのコードを見て下さい。このコードはココから拝借しました。issue の内容はスコープ外の t を参照している為、LEAQ がバイトコード出力されるのですがこれによりパフォーマンスが落ちるというもの。LEAQ とはスレッド固有変数にアクセスする為の x64 TLS 命令です。

例えば以下のコードを go tool compile -S foo.go でバイトコード出力します。

package main

var t [256]byte

func f(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func main() {
}


すると以下のアセンブリが出力されます。

0x002f 00047 (s1.go:7)  TESTQ   CX, CX
0x0032 00050 (s1.go:7)  JEQ $0, 149
0x0034 00052 (s1.go:7)  MOVQ    BX, AX
0x0037 00055 (s1.go:7)  CMPQ    CX, $-1
0x003b 00059 (s1.go:7)  JEQ 144
0x003d 00061 (s1.go:7)  CQO
0x003f 00063 (s1.go:7)  IDIVQ   CX
0x0042 00066 (s1.go:7)  MOVQ    BX, SI
0x0045 00069 (s1.go:7)  SARQ    $63, BX
0x0049 00073 (s1.go:7)  MOVBQZX BL, BX
0x004c 00076 (s1.go:7)  LEAQ    (SI)(BX*1), DI
0x0050 00080 (s1.go:7)  MOVBQZX DIB, DI
0x0054 00084 (s1.go:7)  SUBQ    BX, DI
0x0057 00087 (s1.go:7)  CMPQ    DI, $256
0x005e 00094 (s1.go:7)  JCC $0, 137
0x0060 00096 (s1.go:7)  LEAQ    "".t(SB), BX
0x0067 00103 (s1.go:7)  MOVBLZX (BX)(DI*1), BX
0x006b 00107 (s1.go:7)  CMPQ    DX, CX
0x006e 00110 (s1.go:7)  JCC $0, 137
0x0070 00112 (s1.go:7)  MOVQ    "".b+8(FP), DI
0x0075 00117 (s1.go:7)  MOVB    BL, (DI)(DX*1)
0x0078 00120 (s1.go:6)  LEAQ    1(SI), BX
0x007c 00124 (s1.go:7)  MOVQ    DI, DX
0x007f 00127 (s1.go:6)  CMPQ    BX, $100000000
0x0086 00134 (s1.go:6)  JLT $0, 47


ループ内で毎回 LEAQ を実行しているのが分かるかと思います。golang の場合、goroutine で外部から t を書き換えられる、もしくは t に nil を代入出来てしまう為、厳密にループ途中で新しい t を参照したり nil リファレンス例外を出すためにはループ内で LEAQ を使って毎回 t を参照しなければなりません。

しかし TLS 命令はある程度コストの掛かる命令です。そこで以下の1行を足します。

var t [256]byte

func f(b []byte) {
    t := t // ココ
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}


一見まったく意味のなさそうなコードに見えますが、これにより t が関数内に束縛され TLS 関数を使う必要がなくなります。もう一度アセンブリを見てみましょう。

0x0057 00087 (s2.go:7)  MOVQ    "".b+272(FP), AX
0x005f 00095 (s2.go:7)  MOVQ    $0, CX
0x0061 00097 (s2.go:7)  CMPQ    CX, $100000000
0x0068 00104 (s2.go:7)  JGE $0, 181
0x006a 00106 (s2.go:8)  MOVQ    CX, DX
0x006d 00109 (s2.go:8)  SARQ    $63, CX
0x0071 00113 (s2.go:8)  MOVQ    CX, BX
0x0074 00116 (s2.go:8)  ANDQ    $15, CX
0x0078 00120 (s2.go:8)  LEAQ    (DX)(CX*1), SI
0x007c 00124 (s2.go:8)  ANDQ    $15, SI
0x0080 00128 (s2.go:8)  SUBQ    CX, SI
0x0083 00131 (s2.go:8)  MOVBQZX BL, CX
0x0086 00134 (s2.go:8)  LEAQ    (DX)(CX*1), BX
0x008a 00138 (s2.go:8)  MOVBQZX BL, BX
0x008d 00141 (s2.go:8)  SUBQ    CX, BX
0x0090 00144 (s2.go:8)  CMPQ    BX, $256
0x0097 00151 (s2.go:8)  JCC $0, 197
0x0099 00153 (s2.go:8)  MOVBLZX "".t(SP)(BX*1), CX
0x009d 00157 (s2.go:8)  TESTB   AL, (AX)
0x009f 00159 (s2.go:8)  CMPQ    SI, $16
0x00a3 00163 (s2.go:8)  JCC $0, 197
0x00a5 00165 (s2.go:8)  MOVB    CL, (AX)(SI*1)
0x00a8 00168 (s2.go:7)  LEAQ    1(DX), CX
0x00ac 00172 (s2.go:7)  CMPQ    CX, $100000000
0x00b3 00179 (s2.go:7)  JLT $0, 106


今度は t に関する LEAQ が消えました。実際にどれくらい効果があるのかベンチマークを書いてみました。

package main

import "testing"

var t [256]byte

func f1(b []byte) {
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func f2(b []byte) {
    t := t
    for i := 0; i < 100000000; i++ {
        b[i%len(b)] = t[i%len(t)]
    }
}

func BenchmarkWithLEAQ(b *testing.B) {
    var m [16]byte
    f1(m[:])
}

func BenchmarkWithoutLEAQ(b *testing.B) {
    var m [16]byte
    f2(m[:])
}


ベンチマークの実行は go test -bench . で行います。結果は以下の通り。

BenchmarkWithLEAQ-4                    1        1035500000 ns/op
BenchmarkWithoutLEAQ-4                 3         334666666 ns/op
PASS
ok      github.com/mattn/leaq   4.722s


たった1行で3倍1.0X倍から1.1倍程度のパフォーマンスアップが出来ました。この様に、並行でアクセス可能な変数をローカルで拘束する事で簡単に高速化が行えました。地味なテクニックですが手持ちの処理が遅くて困ってる人は一度試してみては如何でしょうか。なお、このテクニックはループ回数が多い場合に効いてきます。逆にループ回数が少ないと冒頭の LEAQ 分だけ損してしまう為、上記の f1/f2 を多い回数ループすると逆に f1 の方が速くなります。この辺はコンパイラの気持ちになって考えると答えが出てくるかもしれません。

変数のアトミック性を TLS を使って同期して実現してるのだと思ってましたが間違っていましたので記事を修正しました。

次回予告「並列ダウンロードするHTTPクライアントをバンド幅制限するサーバをGoで実装した」 / “高速でダウンロードできるツールを Go で実装した。 - Qiita” https://t.co/6NfEyJCwbu

— Kazuho Oku (@kazuho) July 13, 2016

並列ダウンローダを使うと幾らかサーバに負荷が掛かってしまいます。golang のサーバ側で帯域制限を行う場合には2つ方法があります。

• 転送量制限する
• 接続数制限する

まずは転送量制限。転送量の制限には throttled が便利です。

GitHub - throttled/throttled: Package throttled implements rate limiting access to resources such as HTTP endpoints.

README.md Throttled Package throttled implements rate limiting access to resources such as HTTP endp...

https://github.com/throttled/throttled

http.Handler 互換のミドルウェアなので既存のサーバに埋め込む形で使えます。 store, err := memstore.New(65536)
if err != nil {
    log.Fatal(err)
}

quota := throttled.RateQuota{throttled.PerMin(20), 5}
rateLimiter, err := throttled.NewGCRARateLimiter(store, quota)
if err != nil {
    log.Fatal(err)
}

httpRateLimiter := throttled.HTTPRateLimiter{
    RateLimiter: rateLimiter,
    VaryBy:      &throttled.VaryBy{Path: true},
}

http.ListenAndServe(":8080", httpRateLimiter.RateLimit(myHandler))


次に接続数制限。接続数制限には netutil.LimitedListener を使います。

netutil - GoDoc

package netutil import "golang.org/x/net/netutil" Package netutil provides network utility functions...

https://godoc.org/golang.org/x/net/netutil#LimitListener

こちらは net.Listener にかぶせるだけで最大接続本数を制限できます。

package main

import (
    "fmt"
    "golang.org/x/net/netutil"
    "log"
    "net"
    "net/http"
)

func main() {
    l, err := net.Listen("tcp", ":8080")
    if err != nil {
        log.Fatal(err)
    }
    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        fmt.Fprintf(w, "")
    })
    http.Serve(netutil.LimitListener(l, 100), http.DefaultServeMux)
}


今年の夏も暑そうですが、頑張って乗り切りましょう。