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/ディストリビューションのバージョンとバーチャルマシン環境は次の通りです。

OSの種類

 Linux build2v1 5.13.0-35-generic #40~20.04.1-Ubuntu SMP Mon Mar 7 09:18:32 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

搭載メモリなど

$ 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は使い勝手のよい高速なソートコマンドであるといえるでしょう。

(す）