PT4A msort と GNU sort の動作の違いに関する考察
msort
コマンドmsort(マニュアルへのリンク)は Personal Tukubai for Academic に含まれるソートコマンドです。次のような使い方をします。
msort key=<key> <file>
PT4A msortはGNU sortの再実装ではなく、データ処理を行う上で最もニーズの高い処理の1つであるソートを高速に処理するための目的に作られました。sortとmsortの一番の違いはmsortはソートキーを必ず1つは指定しなければならないことです。またsortは多くのオプションがありますが、msortはソートキーを明示的に指定し、セパレーターと並列度しかオプションしかなくシンプルな構造になっています。では、msortとsortの違いを見ていきましょう。
テスト実行環境
コマンドのパフォーマンスを計測するのに利用するOS/ディストリビューションのバージョンとバーチャルマシン環境は次の通りです。
搭載メモリなど
$ free -h
total used free shared buff/cache available
Mem: 15Gi 479Mi 8.6Gi 1.0Mi 6.6Gi 14Gi
Swap: 2.0Gi 111Mi 1.9Gi
CPU の種類
model name : Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz
バーチャルマシンに割り当てられているCPU数 (並列可能な数)
8
(注意) Intel(R) Core(TM) i9-10900KはCPU数20(10コア20スレッド)ですが本テストはバーチャルマシン上での動作させており、このバーチャルマシンへ割り当てているCPU数は8となっている点に注意してください。
利用するsortのバージョンは次の通りです。
$ sort --version sort (GNU coreutils) 8.30 Copyright (C) 2018 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <https://gnu.org/licenses/gpl.html>. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Written by Mike Haertel and Paul Eggert.
利用するmsortのバージョンは次の通りです。msortが採用しているソートアルゴリズムはマージ・ソートです。
$ msort --version
Usage : msort key=<key> <file>
Options : -e
-s<c>
-p<n>
Version : Mon Jan 17 11:50:14 JST 2022
Edition : 5
1000万行のデータを用意する
まず、その前にソートするためのデータを作成してみましょう。次のコマンド行は最大10桁の数字列を1000万行ほど自動生成しファイルの保存をします。ファイルのデータサイズは約106MByteです。
$ od -An -w4 -tu4 /dev/urandom | head -10000000 | tr -d ' ' >10MLines.dat $ wc 10MLines.dat 10000000 10000000 106608208 10MLines.dat $ head 10MLines.dat 3613546729 5318627087 4608112986 3092536765 1871548190 4081958277 4572049794 3621535927 998641267 2244235894
コマンドのパフォーマンスの計測
ここではパフォーマンスを計測するのにコマンドtime (/usr/bin/time)を使います。ファイルをsortコマンドに与えて実行時の実処理時間、CPU利用度、最大実メモリ使用量を測定してみます。ソートする値は数値として処理します。
ではコマンドsortで処理してみます
$ /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 10MLines.dat > /dev/null Real 2.67 sec,CPU 371%,MaxRSS 1356596 Kbyte
実際に処理にかかった実処理時間は2.67秒です。CPUが100%を越えている表示となっていますが、これはCPU(この場合は並列処理の率になります)がいくつか同時に動作しているということになります。CPUが371%ということは、3つから4つのCPUで並列に処理していることを意味しています。最後の実メモリ量は、このコマンドが実行中に使った最大の実メモリ量で、ここでは約1.36Gbyteになっています。
ではmsortで行ってみましょう。msortは1行に1つのアイテムでもソートキーの指定が必要となっています。
$ /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' msort key=1n 10MLines.dat > /dev/null Real 1.31 sec,CPU 99%,MaxRSS 652892 Kbyte
実処理時間は1.31秒です。CPUは100%以下なので並列では処理していません。最大実メモリ量は約650Mbyteです。
パイプを介しての利用
パイプからsortコマンドにデータを入力すると、sortは並列に動作せず、かつ利用する実メモリも小さくなります。結果として処理時間は長くなります。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 > /dev/null Real 6.03 sec,CPU 99%,MaxRSS 9304 Kbyte
同じ条件でmsortを実行してみます。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' msort key=1n > /dev/null Real 2.10 sec,CPU 98%,MaxRSS 652892 Kbyte
msortは処理時間はsortの約1/3、並列に動作せず、利用する実メモリはファイル指定の時と同じサイズです。sortはダイナミックに実メモリの利用量を変化させている一方でmsortは変化せず入力がファイルで与えた時もパイプで与えた時も一定です。
sortでも十分なバッファサイズを与えれば自動で並列度をあげることができますので、バッファサイズに最初のsortで利用されたRSS (MaxRSS)サイズと同じサイズを指定してみます。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 --buffer-size=1356596 > /dev/null Real 2.76 sec,CPU 367%,MaxRSS 1356592 Kbyte
ファイルでソートするファイルを指定した時と同等の並列度と、ほぼ同じ処理時間で行うことが出来ました。
ソートで並列処理を指定
並列度を明示的に8に指定してsortとmsortを実行してみます。
sortの実行結果は次の通りです。
$ /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 --parallel=8 10MLines.dat > /dev/null Real 2.65 sec,CPU 372%,MaxRSS 1356460 Kbyte
sortのCPU利用率(並列度)は372%になりました。これはデフォルトで何も指定しない場合と同様な動作になっています。
msortの実行結果は次の通りです。
$ /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' msort -p8 key=1n 10MLines.dat > /dev/null Real 0.42 sec,CPU 577%,MaxRSS 652292 Kbyte
msortのCPU利用度は577%になっています。これはソートのアルゴリズムだけではなく、入力から出力に至るまでの範囲で並列化できる部分は並列で動作するようになっているためです。
パイプ処理時に並列処理を加える
今度はパイプ処理時に並列処理を明示的に指定してみます。
sortでは並列度を指定しない場合、並列に処理できませんでした。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 --parallel=8 > /dev/null Real 6.01 sec,CPU 99%,MaxRSS 9352 Kbyte
sortで並列度をあげるために並列度を指定するのと、バッファサイズを指定するのと両方を行ってみます。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' sort -n -k 1 --parallel=8 --buffer-size=1356460 > /dev/null Real 2.71 sec,CPU 373%,MaxRSS 1356444 Kbyte
msortでも並列度を8に指定して処理してみますが、先程のファイルで並列度を与えた時と同じです。
$ cat 10MLines.dat | /usr/bin/time -f 'Real %e sec,CPU %P,MaxRSS %M Kbyte' msort -p8 key=1n > /dev/null Real 0.47 sec,CPU 514%,MaxRSS 652396 Kbyte
結論
msortはsortのように多様なオプションは持っていませんが、極めて高速にソート処理ができるコマンドであることがわかりました。
- sortは入力ファイルを与えると自動的に並列処理を行い処理の高速化が行われますが、同じ条件の時、msortは並列処理をしないにもかかわらずsortよりも処理時間が短くなっています。
- 並列度が同じ指定であればmsortの方がsortより並列度が高くなり、msortの方が短い時間で処理が終了します。
- sortは入力がパイプの場合、最少のリソースで動作しようとする一方、msortは入力条件によって調節せず常に同じ利用リソースで動作します。
- 入力がパイプの場合、sortは並列度を高めるために適切なバッファサイズの指定が必須となりますが、msortは必要ありません。
シェルスクリプト・プログラミングにおいてmsortは使い勝手のよい高速なソートコマンドであるといえるでしょう。
(す）