TLDR

重複行を除去する uniq コマンドを早く実行するツール "quniq" を Go で作ってみました。

自分が測った限りでは、他の重複除去を行なうワンライナーと比べて、処理に要する時間が少なくとも 1/3 程度になることが確認できました。

背景

みなさまご存知の通り、 uniq はソート済みの入力を受け付けて重複行を除いた出力を吐き出すツールです。また -c オプションで重複件数も出力したりすることが可能です。特に集計の前処理として余分な行を除外したり、アクセスログ中の特定要素のランキング化に利用されることが多いように感じます。

uniq はソート済みの入力を期待するためよく cat /path/to/file | sort | uniq のように sort した結果をパイプで渡すことが多いと思うのですが、入力のサイズが大きくなってくると sort に時間がかかるようになってきます。そこで今回はより短い所要時間で重複行を除去したり件数カウントができるツール quniq を実装してみることにしました。

設計と実装

高速化のための方針は単純で、 sort を要求せずかつマルチスレッドで処理するようにするというものです。これをシンプルに実現し、かつツールの利用を簡単にしたかったため、今回は Go で実装することにしました。

実装の概略図を示したものは以下のとおりです。

f:id:syu_cream:20171104222326p:plain

特徴的な点として、 goroutine を複数立てて各 goroutine で一旦入力を map に格納していることが上げられます。 goroutine ごとに個別の map を操作するためこの点では mutex など同期プリミティブは不要であり、また map の key として各入力行を利用するため重複行除去の効果が期待できます。その後各 goroutine が処理した map を、最終的な結果を格納する map にマージします。この map の操作は mutex で排他処理をしておきます。その他、入力データを格納する buffer は sync パッケージの Pool で管理し、メモリアロケーションの負荷軽減とコード上における goroutine 間 buffer 所有権の管理を行っております。

使い方

普通に go get してご利用ください

$ go get github.com/syucream/quniq

quniq は入力が sort 済であることを期待しないので、直接重複除去したい入力を渡してみてください。

$ cat /path/to/file | qunic -c

オプションとしては uniq における -c, -u, -d, -i っぽいものを提供する他、パフォーマンスに左右する -inbuf-weight, -max-workers を提供します。最後に上げた 2 件のオプションは実行環境によって適した値が変わってくると思うので、いろいろお試しください。

評価

今回は筆者の手持ちの環境である MacBook Air Early 2014, Core i7 4650U 1.6GHz, Mem 8GB なマシンで測定を行ってみます。また適当に重複がありそうな巨大なファイルを以下のようにして作成しています。本記事での測定では総計 4GB ほどの入力データを用意しました。

$ cat /dev/urandom | tr -dc '0-9' | fold -w 4 | head -n 100000000 > randlog_0
$ cp randlog_0 randlog_1
...

sort | uniq の結果

まずは定番の sort | uniq した時の所要時間を、 bash の time コマンドで測定してみます。ちなみにこんな記事を目にしたので LANG=C を一応与えてみています。

bash-3.2$ time cat randlog_* | LANG=C gsort | guniq > /dev/null

real    15m39.761s
user    12m59.955s
sys     2m10.857s

sort には --parallel オプションが指定できるのでこれを明示的に与えてみると...少しだけ早くなるように見えます。

bash-3.2$ time cat randlog_* | LANG=C gsort --parallel 4 | guniq > /dev/null

real    14m24.231s
user    12m32.867s
sys     2m7.031s

awk の結果

"uniq large file" とかでぐぐってると awk で処理するワンライナーが見つかったりします。これは quniq のように map 的な構造で重複除去を行なう & 入力がソートされてなくても良い手法になります。 time の結果を見ると sort | uniq するより早く完了していますね。

bash-3.2$ time cat randlog_* | awk '!_[$0]++' > /dev/null

real    11m13.350s
user    10m59.538s
sys     0m5.868s

sort -u の結果

重複除去だけなら sort コマンドの -u でも行えます。一応こちらのパフォーマンスも測定してみましょう。

bash-3.2$ time cat randlog_* | LANG=C gsort -u > /dev/null

real    6m4.100s
user    5m46.810s
sys     0m10.659s

--parallel を与えると？

bash-3.2$ time cat randlog_* | LANG=C gsort -u --parallel 4 > /dev/null

real    5m56.870s
user    5m40.977s
sys     0m10.251s

sort -u はかなり早そうです！しかしこの場合は uniq -c のような件数取得が行えなくなるので uniq のユースケースをカバーしきれるわけではないですが・・・。

quniq の結果

最後に拙作ツール quniq の結果を貼ってみますと、、、 sort -u と比較しても約 6m -> 2m と、所要時間が 1/3 ほどになっていることがわかります。 sort | uniq と比べると約14m -> 2m と 1/7 くらいになっていますね！

bash-3.2$ time cat randlog_* | ./quniq --max-workers 4 > /dev/null

real    1m45.362s
user    4m29.294s
sys     0m10.177s

おわりに

というわけで uniq を少し早く処理するツールを作ってみました。分散処理基盤に突っ込んで力技で重複除去などしてもいいかも知れませんが、手軽に解決したい時の "苦肉"の策として quniq を使える余地はあるんじゃないかと思います。

ブログ・ア・ラ・クレーム

技術的なメモとかライフログとか。

uniq を少し早く処理するツール "quniq" を作った