Sortアルゴリズムの消費メモリについて（続〜In-place merge sort & Multithread merge sort〜）

Quick Sortは理論上は対象データの並び順によって最速のソートになる可能性があるが、最悪の場合（降順にソートされている場合かつPivotを先頭あるいは最後の要素に選択する場合）はO(n^2)かかってしまう、という問題点があり、Merge Sortは安定してO(nlog(n))を達成できるため、Merge Sortが好んで利用されるケースもある。しかし、計算量だけでなくメモリの使用量についても考慮すると、Merge SortはO(n)使用してしまうことになる。このメモリ使用量O(n)を減らすことはできないだろうか、と考えてみる。

Bubble SortのようにIn-placeで要素を変更していくと、余分なメモリを使用する必要がないので、メモリ量はO(1)、つまり２要素の間で入れ替える分だけ用意すれば済むが、計算量はO(n^2)で非常に遅いので使えない。そこで、Merge Sortの改良版として、In-placeでMerge Sortを実施するアルゴリズムを考える。

d.hatena.ne.jp

上記を参考に、実装を読みながらCで実装した。実装したというより読む部分が多かったので、実装上にコメントを多めに入れている。特に不思議だったのは、最小公倍数を求めている（gcd関数がある）ところだ。これは、左のリストのkey以上と右のリストのkey以下を入れ替えるために必要らしい。最小公倍数を求めずに、左のリストのkey以上と右のリストのkey以下を一つのリストとみなして回転するやり方でも問題無いように思えるが、そこは良くわからないので、参考通りに実装した。

void rot_left( int * p, int size, int rot )

    //
    // * Example to explain rotation * //
    //
    // original p = { 0,2,4,6,8, 1,2,3,4,5 }
    // key  = 5
    // rot_left p = { 6,8, 1,2,3,4, (5) }
    //
    // size = 6 ( p = { < 6,8, 1,2,3,4 > ,5 }
    // rot  = 2 ( p = { < 6,8 >, 1,2,3,4,5 }
    //
    // then, gcd is 2 and rotate as follows
    // { < 6,8, 1,2,3,4 > ,5 } <= rot_left p
    // { < 1,8, 3,2,6,4 > ,5 }
    // { < 1,2, 3,4,6,8 > ,5 }
    //

f:id:nishidy:20161104224809p:plain:w400

Cの実装はこちら

In-place merge sort · GitHub

In-place merge sortは、メモリ使用量はO(1)で済むが、計算量はO(n(log(n)^2))となる。実測してみたところ通常のMerge SortのO(nlog(n))に比べるとかなり遅い。ソート処理中に動的にメモリを割り当てる必要がないため、速度的にも期待は持てたのだが実際にはそれほど速くなかった。実際のメモリ使用量については/usr/bin/timeでRSSを測定してみた。ソート対象データとしてはどちらも10,000,000のint型のリストを二つ（一つはソート結果を照合するため）使用しているが、in_place_merge_sortの方がおよそRSSが半分になっていることが分かる。

$ /usr/bin/time -l ./merge_sort 10000000
Merge sort : 4.06 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999
        4.99 real         4.86 user         0.09 sys
 161189888  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
     39360  page reclaims
         2  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         0  voluntary context switches
      2533  involuntary context switches

$ /usr/bin/time -l ./in_place_merge_sort 10000000
In place merge sort : 24.49 sec.
Sorted check OK.
       25.39 real        24.92 user         0.12 sys
  80576512  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
     19678  page reclaims
         3  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         1  voluntary context switches
     11428  involuntary context switches

mallocしたメモリ量をカウントした結果がRSSよりも非常に大きいのはなぜだろうか。念のため、10のリストで実行した結果はこちら。

$ /usr/bin/time -l ./merge_sort 10
Merge sort : 0.00 sec.
Sorted check OK.
mem_size = 0MB, malloc_cnt = 9
        0.01 real         0.00 user         0.00 sys
    548864  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
       141  page reclaims
         2  page faults
         0  swaps
         0  block input operations
         1  block output operations
         0  messages sent
         0  messages received
         0  signals received
         1  voluntary context switches
         3  involuntary context switches

$ /usr/bin/time -l ./in_place_merge_sort 10
In place merge sort : 0.00 sec.
Sorted check OK.
        0.00 real         0.00 user         0.00 sys
    561152  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
       146  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
         0  voluntary context switches
         1  involuntary context switches

また、Multithreadを使ってMerge sortを高速化できないか実装してみた。ソート対象の範囲は共有しなくて良いので、ロックなしでthreadが実行できる。GCPのvCPUx16のインスタンスを使って、thread数を変えながら実行時間を測定してみた。なお、thread数もmalloc回数もロック無しで雑にカウントしているので信頼はできない。また、こちらでは消費メモリについてはそれほど気にしていない。ソート対象はsrand(100)で固定、3回ずつ測定を実施した。

thread数を大きくした場合に、thread無しの実装よりも速くなった。ただ、GCPの環境では実行するたびに測定結果に数秒の揺らぎがあったので、単純にスレッド数の違いが測定時間に影響しているのかどうかはまだ疑わしい。なお、GCPはIntel VT-xは使っていないらしい。仮想化環境はKVMだが、CPUはVMに排他的に割り当てられていないのだろうか？（それともこれはnested virtualization = KVM on KVM が可能でないことを確認をしただけなのだろうか？） Nested VMMは無効だということですね。

Merge sort with multi-threaded (without lock) · GitHub

$ cat /proc/cpuinfo | egrep "model name" | uniq
model name      : Intel(R) Xeon(R) CPU @ 2.50GHz
$ cat /proc/cpuinfo | egrep "processor" | wc -l
16
$ grep -i vmx /proc/cpuinfo 
$ dmesg | grep -i vmx

$ for i in 2 4 8 16 18 20; do for j in {1..3};do ./sort 10000000 $i; done; echo ""; done
Merge sort with multi-thread: 3.58 sec.
Sorted check OK.
mem_size = 1088MB, malloc_cnt = 26107177
# of threads = 2
Merge sort with multi-thread: 3.54 sec.
Sorted check OK.
mem_size = 1094MB, malloc_cnt = 26378016
# of threads = 2
Merge sort with multi-thread: 2.86 sec.
Sorted check OK.
mem_size = 1078MB, malloc_cnt = 25520760
# of threads = 2

Merge sort with multi-thread: 3.54 sec.
Sorted check OK.
mem_size = 951MB, malloc_cnt = 21693873
# of threads = 4
Merge sort with multi-thread: 3.62 sec.
Sorted check OK.
mem_size = 953MB, malloc_cnt = 21775278
# of threads = 4
Merge sort with multi-thread: 3.56 sec.
Sorted check OK.
mem_size = 942MB, malloc_cnt = 21880252
# of threads = 4

Merge sort with multi-thread: 3.95 sec.
Sorted check OK.
mem_size = 665MB, malloc_cnt = 13939773
# of threads = 9
Merge sort with multi-thread: 4.06 sec.
Sorted check OK.
mem_size = 492MB, malloc_cnt = 9169216
# of threads = 10
Merge sort with multi-thread: 3.76 sec.
Sorted check OK.
mem_size = 648MB, malloc_cnt = 13171368
# of threads = 9

Merge sort with multi-thread: 3.69 sec.
Sorted check OK.
mem_size = 484MB, malloc_cnt = 8216468
# of threads = 16
Merge sort with multi-thread: 2.25 sec.
Sorted check OK.
mem_size = 436MB, malloc_cnt = 7040719
# of threads = 17
Merge sort with multi-thread: 1.83 sec.
Sorted check OK.
mem_size = 485MB, malloc_cnt = 8194432
# of threads = 18

Merge sort with multi-thread: 1.85 sec.
Sorted check OK.
mem_size = 480MB, malloc_cnt = 8200301
# of threads = 19
Merge sort with multi-thread: 2.40 sec.
Sorted check OK.
mem_size = 436MB, malloc_cnt = 6874139
# of threads = 18
Merge sort with multi-thread: 2.25 sec.
Sorted check OK.
mem_size = 451MB, malloc_cnt = 6861356
# of threads = 19

Merge sort with multi-thread: 1.79 sec.
Sorted check OK.
mem_size = 511MB, malloc_cnt = 8695299
# of threads = 21
Merge sort with multi-thread: 2.15 sec.
Sorted check OK.
mem_size = 455MB, malloc_cnt = 7680709
# of threads = 21
Merge sort with multi-thread: 2.03 sec.
Sorted check OK.
mem_size = 464MB, malloc_cnt = 7855797
# of threads = 21

$ for i in {1..3};do ./sorts_low_mem 10000000; echo ""; done
Quick sort : 5.45 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.93 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

Quick sort : 5.43 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.97 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999

Quick sort : 5.49 sec.
Sorted check OK.
mem_size = 1419MB, malloc_cnt = 6832420
Merge sort : 2.96 sec.
Sorted check OK.
mem_size = 889MB, malloc_cnt = 9999999