Go言語のorderedmapパッケージを改善した

Go言語で書かれたorderedmapというサードパーティパッケージがあります。 github.com

Goのmapには順序がなく、JSONをデコードすると順序が失われ、それをエンコードするとオブジェクトのキーの順序にソートされます。 これに困る人はそこそこいるようで、順序を保持するmapはいくつか実装されてきました。 その中の一つが、orderedmapというパッケージです。 シンプルなインターフェイスが気に入っています。

orderedmapパッケージの利用例

package main

import (
    "encoding/json"
    "fmt"
    "log"

    "github.com/iancoleman/orderedmap"
)

func main() {
    src := `{ "z": 1, "x": 2, "y": 3 }`

    fmt.Println("# map[string]interface{}")
    var v map[string]interface{}
    if err := json.Unmarshal([]byte(src), &v); err != nil {
        log.Fatal(err)
    }
    bs, err := json.MarshalIndent(v, "", "  ")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%s\n\n", bs)

    fmt.Println("# OrderedMap")
    o := orderedmap.New()
    if err := json.Unmarshal([]byte(src), &o); err != nil {
        log.Fatal(err)
    }
    bs, err = json.MarshalIndent(o, "", "  ")
    if err != nil {
        log.Fatal(err)
    }
    fmt.Printf("%s\n\n", bs)
}
# map[string]interface{}
{
  "x": 2,
  "y": 3,
  "z": 1
}

# OrderedMap
{
  "z": 1,
  "x": 2,
  "y": 3
}

しかし、このパッケージのUnmarshal (JSONOrderedMap の変換) の実装は、正直あまりきれいではありませんでした。 v0.1.0までの実装は以下のようになっていました。

  • map[string]interface{}Unmarshal する
  • オブジェクトの各キーに対して、JSON文字列の中の出現位置を探す
    • キーの "エスケープして、 strings.LastIndex で探す
    • JSON文字列を探したインデックスまでを切り取って } を付け加えたときにvalidなJSONかチェックする
      • validなJSONでなければ、ネストされたJSONのキーにヒットしまっているので、更に前にたどってキーのポジションを探す
  • オブジェクトの各値に対して
    • オブジェクトであれば、OrderedMapへの変換を再帰的に行う
    • 配列であれば、各要素の変換を再帰的に行う
  • オブジェクトのキー一覧を、出現位置でソートする

オブジェクトのキーの順序を保持したい → キーの文字列の出現位置を探索してソートすれば良い、という素朴な発想でこういう実装になっているのだと思いますが、この処理には様々な問題があります。

  • オブジェクトのキーを文字列から探すときに " しかエスケープしておらず、{ "\n": 1 } のようなものはうまくUnmarshalできない
    • { "A\u0041A\u0041A": 0 } のようなキーもありうるので、strings.LastIndex でポジションを探す方針には限界がある (指数関数的な個数のエスケープを試す必要がある)
  • パフォーマンスが良くない (#2)
    • validなJSONかかどうかをチェックするという処理でいちいち json.Unmarshal している (orderedmap.go#L178-L192)。
    • 探索範囲を絞ったりスペースをスキップしたりするために、文字列のアロケーションが多い
  • ネストしたJSONに対処するために実装が複雑で、一見してバグっていない自信がない (主観)
    • 重複キーに対しては結構怪しい気がする

個人的には好きなパッケージですが、Unmarshalの実装が複雑であまり使いたくないという気持ちがありました。 しかし作者も課題感を持っているようでしたし、解決策も思いついたので、実装し直すことにしました。

標準パッケージのencoding/json*DecoderにはToken() (Token, error)という関数があります。 JSONトークンを一つずつデコードする関数です。 *DecoderJSONのステートを持っているので、単なるlexerではなくてvalidなJSONトークン列を返してくれます。 これを使います。

  • map[string]interface{}Unmarshal する
  • JSONから *Decoder を作り、dec.Token() を使ってトークンをたどっていく
    • キーはスライスに追加する
      • 重複キーは後ろに移動する
    • 値の最初のトークンによって、オブジェクトか配列かその他の場合に分かれる
      • 値がオブジェクトの場合
        • map[string]interface{}またはOrderedMap (重複キー) の場合はOrderedMapに変換する処理を行う
        • それ以外の場合 (型が違う) は重複キーなので、OrderedMapへのデコードを行うが得られた値は捨てる
      • 値が配列の場合
        • 配列の各要素に対してオブジェクトか配列の場合は再帰的にデコードを行う
        • それ以外の場合 (型が違う、配列のインデックスを超えているなど) は重複キーなので、デコードを行うが得られた値は捨てる

この実装によって様々な点が改善されました。

  • オブジェクトのキーがエスケープされていても問題なく動く
    • { "A\u0041A\u0041A": 0 } のようなものでもOK
  • 以前の実装では何度も文字列上を走査する必要があったが、この実装では二回スキャンすればよい
    • 実装を突き詰めてJSONパースを自前で持てば一回で済むが、そこはencoding/jsonに任せて小さく実装している
  • オブジェクトのキー一覧をソートする必要がない
    • ただし重複キーが大量にある場合のパフォーマンスは良くない
  • 文字列のアロケーションが大幅に減少し、パフォーマンスも改善される
  • 実装が比較的読みやすい

ベンチマークは以下のように改善されています。 アロケーションは半分以下に抑えられ、パフォーマンスも三倍近く改善しています。

benchmark                     old ns/op     new ns/op     delta
BenchmarkUnmarshalJSON-16     125485        37536         -70.09%

benchmark                     old allocs    new allocs    delta
BenchmarkUnmarshalJSON-16     964           389           -59.65%

benchmark                     old bytes     new bytes     delta
BenchmarkUnmarshalJSON-16     49885         13174         -73.59%

一方、Marshal (OrderedMapJSONへの変換) にも改善を入れました。 Unmarshal ほどの問題はありませんでしたが、オブジェクトのキーのエスケープが足りていない ({ "\n": 1 } 相当を出力すると改行が入りvalidなJSONにならない) とか、文字列のアロケーションが多いといった問題を解決しています。 文字列の結合をbytes.Bufferに置き換える単純なお仕事です。

ベンチマークは以下のようになっています。 アロケーションはかなり減りましたが、パフォーマンスとしては7%程度の改善にとどまっています。

benchmark                   old ns/op     new ns/op     delta
BenchmarkMarshalJSON-16     15687         14535         -7.34%

benchmark                   old allocs    new allocs    delta
BenchmarkMarshalJSON-16     94            33            -64.89%

benchmark                   old bytes     new bytes     delta
BenchmarkMarshalJSON-16     9309          2195          -76.42%

以上の改善は、v0.2.0としてリリースされています。 個人的には実装がかなりクリアになり (まあ自分で書いたし)、パフォーマンスも良くなったので、安心してこのパッケージを使えるようになりました。 また一つ世界が良くなりましたね。 おしまい!

gojq が homebrew/core に入りました、他近況

gojqはGoで実装されたjqコマンドおよびライブラリです。2019年の4月から開発を始めて、現在も様々な改善を行っています。

これまでgojqのHomebrew formulaはitchyny/tapより配信していましたが、このたび公式のhomebrew/coreに入りました。 これにより、次のコマンドでインストールできるようになりました。

brew install gojq

tapの考え方についてはTapsを参照してください。

実は、私への連絡もなしにいきなりhomebrew/coreに入れられていて、formulaの品質が悪かったのですが、色々と指摘したらすぐに直してくれました。 自分のコントロールできない部分に置くのが正直嫌だったのですが、すでに入ってしまったのを怒ってもしょうがないし、bottleによるメリットも大きいので良いかなと思います。 ただ、連絡はしてほしかったですね… (というかメイン開発者の意向を無視して勝手にformula追加できるのどうなの…)

formulaの配布元tapを移動するときは、tap_migrations.json を使います。 tapのリポジトリのトップにこの名前のJSONを作っておけば、既存のtapを使っているユーザーもスムーズにtapの移行が行われます。 今回はhomebrew/coreに移動したので、以下のようなJSONファイルを配置しました

{
  "gojq": "homebrew/core"
}

gojqは様々なフィードバックを受けて完成度があがっています。 最近あったものとしては、$HOMEが空のときにうまく動かないというものです (#58)。 デフォルトのモジュールパスの~/.jqを展開するためにos.UserHomeDirを使っていたのですが、値を取れないときにエラーとして終了していました。 $HOMEが取れないケースというのは想定したことなかったのです。 AWS Lambdaで動かすとこれが空になるそうですね。

Fuzzingによるコーナーケースの修正も行っています。 例えば ""[:{}] とか infinite * "x" のようなクエリのクラッシュが発見されています。 また先日は全探索によるバグの探索も行いました。 コマンド引数に渡すクエリ文字列を生成して、コマンドの実行結果を比較するという感じです。

jqとgojqの終了ステータスの差異をチェックするコード

package main

import (
    "fmt"
    "os/exec"
    "syscall"
)

func main() {
    source := []byte(" ")
    for {
        check(string(source))
        for i := len(source) - 1; i >= 0; i-- {
            if source[i] != '~' {
                source[i]++
                if i == 0 && (source[i] == '-' || source[i] == '+') ||
                    source[i] == '#' {
                    source[i]++
                }
                if source[i] == '1' {
                    source[i] = ':'
                }
                break
            }
            source[i] = ' '
            if i == 0 {
                source[0] = '!'
                source = append(source, '!')
            } else if i == len(source)-1 {
                source[i]++
            }
        }
    }
}

var sem = make(chan struct{}, 10)

func check(src string) {
    sem <- struct{}{}
    go func() {
        defer func() { <-sem }()
        if x, y := run("jq", "-n", src), run("gojq", "-n", src); x != y {
            fmt.Printf("ng: %q %d %d\n", src, x, y)
        } else if x == 0 {
            fmt.Printf("ok: %q %d %d\n", src, x, y)
        }
    }()
}

func run(command string, args ...string) int {
    cmd := exec.Command(command, args...)
    if err := cmd.Start(); err != nil {
        return -1
    }
    if err := cmd.Wait(); err != nil {
        if exiterr, ok := err.(*exec.ExitError); ok {
            if status, ok := exiterr.Sys().(syscall.WaitStatus); ok {
                return status.ExitStatus()
            }
        }
    }
    return 0
}

この調査では 1?/1 (lexerのバグで、?//という演算子をチェックして失敗した後のoffsetのバグ)、0.._ (これもlexerのバグで、クエリのエラーとすべきものを受け付けてしまっていた) や @a? (compilerのバグで、定義されていないformatをcompile errorとしてはいけない) といったクエリの挙動が異なることが発見されました。 実装に相当自信があっても、Fuzzingや探索を行ってみると、何かしらのバグは見つかるものですね。

gojq v0.12.0からはJSONに色を付けるライブラリを自前で持ち、パフォーマンスが三倍以上改善しました。 以前はgo-prettyprintにお世話になっていましたが、オブジェクトのキーのエスケープがバグっていたのと (#15にて修正済)、NaNや無限大の正規化が (これらはnullと出力するというjqの仕様を実装する必要がある) オーバーヘッドになっていたこと、またこのライブラリのパフォーマンスがあまり良くないことが問題でした。 色付けを行う部分を自前にすることで、jq仕様の正規化も組み込むことができ、またメモリーアロケーションも大幅に減少することができました。 go-prettyjsonのパフォーマンスの改善に関しては#17にてフィードバックしています (二倍近くは速くなりそうです)。

gojqは言語処理系です。 作り始めて二年近くになり、処理系もパーサーもそれぞれ完全なリライトをしています。 コミット数も1000を超え、様々なことを学ぶことができました。 Goのツールにライブラリとしてgojqを埋め込む利用例も増えています。 ソフトウェアは完成することはありません。 これからもgojqを楽しんでいきたいと思います。

一括リネームツール mmv でディレクトリツリーを扱えるようにした

一年前、ファイルをエディターで一括リネームするmmvコマンドを作りました。

itchyny.hatenablog.com

github.com

mmvはリネームの依存関係を解析して順番を決定します。例えば

a => b
b => c

というリネームを愚直に上から実行すると、ファイルbが消えてしまいます。 mmvはリネーム先がリネームの対象となっている場合は、そちらのリネーム (上の例では b => c) を先に実行します。 もし

a => b
b => c
c => a

のようにリネームが循環している場合は、一時的なパスに一旦退避してからリネームします。

a   => tmp
c   => a
b   => c
tmp => b

このツールを作ったときはこれで機能的には十分だと思っていましたが、去年の12月に面白いissueが立ちました (#11)。 mmv $(find .) のようにディレクトリツリーを対象にするとうまく動かないというのです。

a   => b
a/x => b/x
a/y => b/z
a/z => c/z

mmvはリネームの対象の中でパスが他のパスのディレクトリとなっているケースは想定していませんでした。 リネームを実行すると以下のような問題が起きてしまいます。

  • a/x => b/xa => b より先に実行してしまうと、最初のリネームが先に b/ を作成してしまうので a => b が失敗し、a/ 以下の他のファイルは移動されない
  • a => ba/z => c/z より先に実行してしまうと、 a/z はすでに b/z に移動しているので対象ファイルが見つからない

この問題を1か月ほど悩んだ末に、先日ようやく実装することができました。

  • 移動先の浅いパスのリネームから順番に行う。これでリネーム先のディレクトリが先に作られてしまう問題を修正。
  • ディレクトリがリネームされる場合は、一時的なパスに先に退避する。

例えば以下のようなリネームを行う場合は

a   => b
a/x => b/x
a/y => b/z
a/z => c/z

mmvは以下の順番でリネームを行います。

a/y  => tmp1
a/z  => tmp2
a    => b
tmp1 => b/z
tmp2 => c/z

ディレクトa のリネームが行われるので、その中のファイルを一旦退避しています。 ただし a/x => b/xa => b のリネームに任せることで、リネームの数を抑えています。

このように書いてしまえばシンプルな処理に見えますね。 しかし、mmvは親ディレクトリの解析と、先述の依存関係の解析を同時に行います。 また、愚直に実装してしまうと O(n²) になってしまうので、先にディレクトリの深さでパスをグルーピングする実装を行いました。 色々なケースを想像していると重い腰が上がらず、1か月もかかってしまいました。

このツールを作ったときは機能を増やさない信念と称してツールの機能が膨れ上がらないようにと思っていました。 実際、git mv したいとか -dry-run したいとか言う要望は、mmv の信念にはそぐわないので却下しています *1。 しかし親ディレクトリの解析はmmvの中で実装するのに適切な機能であり、また面白そうなチャレンジだったので実装しました。

昨日リリースしたv0.1.3よりこの機能をお使いいただけます。 是非お使いください。 現場からは以上です。

*1:git mvは外部コマンドを開く必要があり、mmvは複数のrename(2) に過ぎないという考え方と合わない。-dry-run はmmvのインタラクティブ性と合わない。

2020年を振り返って

今年はコロナ禍でリモートワークになり、生活リズムが大きく変わりました。年末も帰省を控えているため、人生で初めて実家で過ごさない正月となります。年末年始を京都で過ごすのは初めてで少しわくわくしています。仕事は担当サービスのコンテナ化やAWS化などを手伝いながら、インターン講師をやったり、プロジェクトのタスクマネジメント的なことをやってました。むずかしいですね。

OSS活動としてはmmvを作ったりHomebrewのインストーラーをBashに書き直したりgojqのパーサーを書き直したりtimefmt-gorassemble-goを作ったりしていました。gojqJSONを出力する処理を自前で書くことでjqコマンドの3倍以上のパフォーマンスを出せるようになりました。他には、jqのリポジトリwatchしてissueの打ち返しをしたり、Vim 9 scriptの仕様に関するフィードバックを行ったりしていました。

秋頃に競技プログラミングにハマり、AtCoderをRustで解いていました。昔やっていた頃よりもツールやライブラリが揃っていて参加しやすくなったと感じました。しかしgojqでやることが増えたら自然と競技プログラミングをやる時間も減ってしまいました。なかなか続かないですね… Rustをもっと書きたいんですがどうしても時間がかかってしまってGoを選んでしまいます。

9月に家族で天橋立に行きました。200kmほど運転を担当し、天気が良くて気持ちよかったです。しかし連休に行ったのもありとても混雑していて大変でした。12月には京都水族館に行きました。クラゲが可愛かったです。

将棋が強くなりたくて対局を観たりアプリをやったりしていたのですが、最近は時間がなくてやれてません。将棋鑑賞、なかなか大変な趣味です。夏頃には筋トレグッズを買ってしばらくやっていましたが、これも続きませんでした。来年こそは続けるんだ。YouTubeをPremiumにしてから結構見るようになりました。しみさん夫婦るかちゃんねるはるまきちゃんねるあたりが好きです。

今年の良かったアニメは『アサルトリリィ BOUQUET』『安達としまむら』『かぐや様は告らせたい?~天才たちの恋愛頭脳戦~』『魔女の旅々』『ストライクウィッチーズ ROAD to BERLIN』あたりですね。アサルトリリィはOP・EDもWEBラジオも赤尾ひかるさんも良かったです。舞台をやっているからなのか、声優さんたちが仲がいいですね。『魔女の旅々』の本渡楓さんもよかったです。ドラマもかなり見ていて『危険なビーナス』『七人の秘書』『テセウスの船』『監察医 朝顔』『アリバイ崩し承ります』あたりがよかったです。映画は『TENET』が最高でした。クリストファー・ノーランは常に最高を届けてくれます。

来年はいい一年になりますように。

伊東閑「責任感と罪悪感はきちんと分けないと、身を滅ぼすわよ」

アサルトリリィ BOUQUET 第11話

Vimの古いバージョンをコンパイルし高速にbisectする (macOS編)

Vimプラグインを作っていると、特定の機能がどのバージョンで実装されたか調べるのが難しいことがあります。 ヘルプ (:h vim7, :h vim8) や git log のコミットメッセージから探せば多くのケースでは見つかるのですが、うまく検索できなくて見つからないこともあります。 また、急にテストが古いVimで落ちるようになったときに、どの機能が原因で落ちているのかつかめないこともあります。

確実な方法は git bisect すれば良いのですが、これには2つの問題があります。

後は純粋な興味もあって、古いバージョンのビルド済みバイナリーを作っておこうと思い立ちました。 しかし1パッチごとにビルドするのはあまりに大変です。 そもそも当時のコンパイルでもビルドできず、その後のパッチで直ったりするバージョンがあるので、どうしてもビルドできないバージョンは存在します。 後はディスク容量の問題もあります。

まずは以下のようなスクリプトで100パッチごとにビルドしてみることにしました。 macOS・clang 12.0.0 (clang-1200.0.32.27) で v7.3.000 から v8.2.2000 までの103バージョンをビルドすることができました。

vim-backcompile.sh

#!/bin/bash
set -euxo pipefail

if [[ ! -d /tmp/vim ]]; then
  git clone https://github.com/vim/vim.git /tmp/vim
fi
cd /tmp/vim

BACKUP_DIR=/tmp/vim-backup
mkdir -p "$BACKUP_DIR"

while true; do
  git restore .
  while ! git describe --tags | grep -E '^v\d[.]\d(?:[.]\d(?:\d*00)?)?$'; do
    git reset --hard HEAD^
  done
  gsed -i '/sizeof(uint32_t) != 4/,+1s/exit/return/' src/auto/configure # v8.2.1119
  gsed -i '/if (\(p\|res\|e1.*\) [!=]= NUL)/s/NUL/NULL/g' src/*.c # v8.0.0046
  gsed -i '/#define VV_NAME/s/, {0}$//' src/eval.c # v7.4.1648
  gsed -i '/static struct vimvar/,+4s/dictitem_T/dictitem16_T/;/char\s*vv_filler.*/d' src/eval.c # v7.4.1648
  if ! git grep 'struct dictitem16_S' src/structs.h >/dev/null; then
    gsed -i '/typedef struct dictitem_S dictitem_T;/a struct dictitem16_S {\n  typval_T di_tv;\n  char_u di_flags;\n  char_u di_key[17];\n};\ntypedef struct dictitem16_S dictitem16_T;' src/structs.h # v7.4.1648
  fi
  gsed -i 's/__ARGS(\(.*\))/\1/' src/proto/os_mac_conv.pro # v7.4.1202
  gsed -i 's/!builtin_first == i/(!builtin_first) == i/' src/term.c # v7.4.914
  gsed -i '/extern int sigaltstack/s/^/\/\//' src/os_unix.c # v8.0.1236
  gsed -i '/+multi_byte/,+6s/FEAT_BIG/FEAT_NORMAL/' src/feature.h # v7.3.968
  if ! ./configure; then
    make distclean || :
    rm -f auto/config.cache
    ./configure
  fi
  make -j8
  src/vim --version
  MAJOR=$(./src/vim --version | head -n 1 | awk '{ print $5 }' | tr -d '\n')
  MINOR=$(./src/vim --version | grep patch | awk '{ print $3 }' | sed -e 's/^[0-9]*-//g' | tr -d '\n' || :)
  cp src/vim "$BACKUP_DIR/vim-$MAJOR.$(printf "%04d" "$MINOR")"
  git reset --hard HEAD^
done
  • ビルドが通っても起動できない事があったので、 src/vim --version で起動チェックを行う
  • 変わっていくソースコードにパッチファイルは使いにくいので、今のコンパイラコンパイルできない箇所は sed で雑にパッチを当てる。

実行ファイルのサイズが少しずつ増える様子が分かりました。

今は上のスクリプトを少し変えて、25パッチごとにビルドして実行ファイルを保存しています。 ビルドできなかったのは 8.0.0750 (8.0.0751で修正), 7.4.1625 (7.4.1626で修正) のみでした。

ビルド済み実行ファイルが揃ったので、次はこれを使ってbisectします。

vim-bisect.sh

#!/bin/bash
set -euo pipefail

script_dir="$(cd "$(dirname "${BASH_SOURCE[0]}")" >/dev/null 2>&1 && pwd)"

VERSIONS=($(cd "$script_dir" && ls vim-[0-9]* | sort --version-sort --field-separator=.))

find_index() {
  for i in "${!VERSIONS[@]}"; do
    if [[ "${VERSIONS[$i]}" = "$1" ]]; then
      echo "$i"
    fi
  done
}

exec_command="${1:?specify bisecting command}"
low_version="${2:-${VERSIONS[0]}}"
high_version="${3:-${VERSIONS[${#VERSIONS[@]}-1]}}"
if [[ ! "$low_version" =~ ^vim- ]]; then
  low_version="vim-$low_version"
fi
if [[ ! "$high_version" =~ ^vim- ]]; then
  high_version="vim-$high_version"
fi
low_index="$(find_index "$low_version")"
high_index="$(find_index "$high_version")"

test_version() {
  env VIM="$script_dir/$1" bash -c "$exec_command"
}

if test_version "$high_version"; then
  echo "$high_version is good"
  exit 1
fi
if ! test_version "$low_version"; then
  echo "$low_version is bad"
  exit 1
fi

bad_version="$high_version"
while [[ "$low_index" -lt "$high_index" ]]; do
  mid_index="$(((low_index + high_index) / 2))"
  version="${VERSIONS[$mid_index]}"
  if test_version "$version"; then
    echo "$version: good"
    low_index="$((mid_index + 1))"
  else
    echo "$version: bad"
    high_index="$((mid_index))"
    bad_version="$version"
  fi
done

echo "$bad_version is the bad version"

$VIM という環境変数に実行ファイルのパスを入れるので、 vim-bisect.sh '! env THEMIS_VIM=$VIM /tmp/vim-themis/bin/themis --reporter spec >/dev/null' のようなコマンドで vim-themis を使ったテストを回すことができます。

すべてのパッチバージョンに対する実行ファイルを用意できるわけではないので、git bisect みたいにこのパッチがbad commitというところまではいけませんが、50パッチや25パッチの範囲くらいならコミットログに全部目を通すことはできます。 ビルド済みbisectはめちゃくちゃ便利なので、ぜひ試してみてください。

おしまい