読者です 読者をやめる 読者になる 読者になる

Binary Searchと分割統治によるコード最適化

Binary Searchは強力でソート済みでない配列に対して適用することも可能である。それどころか、対象が離散的な値である必要すら無い。 分割統治はそれに良く似た手法で、対象を再帰的に半分にしてく手法である。

今回はランダムに数値が並んだ配列の中で、それらの数値の取りうる範囲が指定されており、その範囲の中で一つだけ数値が欠けていて、その欠けている数値を探し出す問題を考える。例えば範囲が1〜10で配列の長さは9であり、配列の中の数値に重複は無い場合である。

直感的に考えると配列をソートして一つずつ順に数値を見ていけば良い。数値が欠けていればインデックスとの対応が合わないはずだ。 しかしこれは最速でもO(Nlog(N))かかることになる。もう少し詳しく言えば、ソートしてから一つずつ配列を見ていくので、最悪の場合はO(Nlog(N)+N)になるだろう。

このような問題は分割統治を使ってもっと速くできる。Binary Searchのようにインデックスをlow,highとして扱うような使い方では解けないため、ここは配列のサイズを1/2ずつに分割していく方法を組み合わせる。上記の例で言うと、low=1, high=10, mid=5として初期設定し、midより大きい配列、小さい配列、に分ける。欠けている場合は、配列が期待するサイズよりも小さいはずなので、lowかhighにmidを設定し、そちらの配列を再帰的に検査していく。

ここまで考えることができればO(Nlog(N))よりも速くできることが分かるだろう。しかし、ここに辿り着く前にこれがO(Nlog(N))よりも速くなる、ということに気付くのが難しい。実際には、midを元にサイズNの配列を作成するための走査が必要になるためO(N)になる。Binary Searchを用いていることを実感したいならばもう少し詳しく考えて、N+N/2+N/4+...となるので初項=N、公比=1/2、の等比数列の和を求めると、N*(1-(1/2)^N)/1-(1/2)、となり、Nが十分大きければ(1/2)^N≒0となるため、O(N)が導ける。

この問題の解法は、例えば、k個の欠けている数値のうちの一つを探し出す、とか、k個の重複している数値のうちの一つを探し出すなどにも適用できる。 コードは以下。配列をスクランブルした後、最後の要素を削除(配列のサイズをマイナス1)することによって、欠けている配列を作り出している。

Find a lost number in O(N) better than O(NlogN) by sort. · GitHub

MBPでの実行結果。

$ for i in `seq 1 5`; do echo $i; ./find_a_lost_number 100000000; done
1
78221769==78221769:OK
func_O_N : 1.27 sec.
78221769==78221769:OK
func_O_NlogN : 20.13 sec.
2
12264665==12264665:OK
func_O_N : 1.21 sec.
12264665==12264665:OK
func_O_NlogN : 20.09 sec.
3
78228998==78228998:OK
func_O_N : 1.23 sec.
78228998==78228998:OK
func_O_NlogN : 20.05 sec.
4
44908476==44908476:OK
func_O_N : 1.32 sec.
44908476==44908476:OK
func_O_NlogN : 20.35 sec.
5
85940350==85940350:OK
func_O_N : 1.24 sec.
85940350==85940350:OK
func_O_NlogN : 20.17 sec.
$

二つ目の問題は、配列の中で合計値が最大となる部分配列を発見する。配列の要素は整数なので、負の値も存在する。

これには、計算量がO(N3), O(N2), O(NlogN), O(N), となる解法が存在するが、分割統治を利用した解法はO(NlogN)となる。1/2に分割しながら中央の値から左と右の部分配列の合計を計算し、最大となる部分配列を見つける。O(N)の解法の基礎となるアイデアは、配列の最初の要素から合計していくが、合計が負の値になったときはその次の要素を部分配列の最初の要素とする。そうやって部分配列を細切れにしながら合計の最大値を更新していくと、O(N)で、つまり一つのループで計算できる。

Find maximum sum of sub array in O(N^3), O(N^2), O(NlogN), O(N). · GitHub

出力としては、部分配列の最初のインデックス-[合計値]-部分配列の最後のインデックスとしている。

$ ./max_sub_array 3000
1653-[62030]-1900
func_O_N3 : 12.63 sec.
1653-[62030]-1900
func_O_N2 : 0.01 sec.
1653-[62030]-1900
func_O_NlogN : 0.00 sec.
1653-[62030]-1900
func_O_N : 0.00 sec.

$ ./max_sub_array 30000
2795-[4884646]-29986
func_O_N2 : 1.34 sec.
2795-[4884646]-29986
func_O_NlogN : 0.00 sec.
2795-[4884646]-29986
func_O_N : 0.00 sec.

$ ./max_sub_array 30000000
25697428-[46557400133]-28003047
func_O_NlogN : 4.39 sec.
25697428-[46557400133]-28003047
func_O_N : 0.20 sec.

tracerouteのベストプラクティス

ファイヤウォールの設定が厳しいネットワークや、ロードバランサーが動作するネットワーク、使用するパケットのプロトコルによる違い、等を考えて最も経路発見しやすい方法を考える。

ファイヤウォールの設定が厳しいネットワーク

ファイヤウォールの設定が厳しい場合、pingすらインターネット上のサーバに通らないことがある。tracerouteも同様で、デフォルトの設定では通らないことが多いが、ファイヤウォールが必ずといっていいほど通しているポートを使えば良い。TCPではHTTPの80番ポート、UDPではDNSの53番ポート、が最も良く知られたポートの内の一つだろう。実際、tracerouteのデフォルト設定ではデフォルトゲートウェイまでしか経路発見できないが、UDPの53番ポートを使うとかなり先まで経路発見できることがある。

ロードバランサーが動作するネットワーク

ECMPによってロードバランスしているネットワーク(インターネット)では、パケットを投げる度に経路が変わってしまう。ただし、ロードバランスには大きく二つの方式があって、インターフェースをフローで振り分けるか、パケットで振り分けるか、の違いがある。フローは5 tuples (IP/Port Dest/Src Protocol) によってインターフェースを振り分ける方式で、IP/UDP/TCPのヘッダで決まる5 tuplesを固定すれば、ロードバランスによる経路の違いは出ないので安定した経路発見が行えるはずだ。

ただし5 tuplesを固定するために、tracerouteがどのように経路発見を行っているのかを確認しておく必要がある。Linux版のtracerouteコマンドはデフォルトはUDPパケットによる経路発見を行う。つまり、UDPパケットのIPヘッダのTTLを一つずつ増やしていくやり方だ。また、受け取ったTime ExceededのICMPパケットが、どのUDPパケットに対応するのかを判断できる必要がある。大きく遅延したパケットを受信したり、他のアプリケーションが送信したパケットに対するTime Exceededパケットと区別する必要があるし、Linuxのtracerouteのデフォルト動作は以下の通り同時に複数のパケットを投げる。

       -N squeries, --sim-queries=squeries
              Specifies the number of probe packets sent out simultaneously.
              Sending several probes concurrently can  speed  up  traceroute
              considerably. The default value is 16.
              Note that some routers and hosts can use ICMP rate throttling.
              In such a situation specifying too large number  can  lead  to
              loss of some responses.

Time ExceededのICMPパケットはそのデータ部に、元のパケットのIPヘッダとペイロードの最初の8バイトを含めるので、元のUDPパケットのヘッダに存在するポート番号を識別できるため、tracerouteはこれを生かしてUDPの宛先ポート番号を一つずつ増やしながらUDPパケットを生成する。

http://pages.cs.wisc.edu/~agember/cs640/s15/assign3/images/image00.png

Internet Control Message Protocol - Wikipedia

ここで、フローベースのロードバランスに対応しようとすると問題があることが分かる。5 tuplesが変わってしまうとロードバランスの影響を受けるからだ。これに対応したのが Paris Traceroute で、UDPパケットヘッダの宛先ポート番号ではなくチェックサムを使って対応を取る。まるでビットコインのように、UDPパケットのペイロードを用いて任意のチェックサムの値を作り出す。UDPパケットヘッダのチェックサムは最初の8バイトに含まれるので、これもTime ExceededのICMPパケットに含まれる。単純にUDPパケットのペイロードにシーケンス番号を書けないのもこれが理由だ。

http://paris-traceroute.net/images/traceroute_load_balancers.gif

Paris Traceroute

ただ、tracerouteにもこれと同等と思われるオプションが実装されているため、UDPパケットを使いつつ宛先や送信元のポート番号を任意の値に固定できる。例えば、-Uオプションで宛先ポート番号を53に固定する。これは、DNSで使われるポート番号であり、最も通りやすい(経路途中でファイヤウォールにフィルタで破棄される可能性が少ない)ポートの一つだ。また--sport=オプションで、送信元ポートを固定することもできる。

両者の違いはChecksumの使い方にあるようだ。tracerouteのパケットをtcpdump -vvで見てみると[bad udp cksum]と表示されるのが分かる。宛先ポートや送信元ポートを変更してもChecksumの値を変えておらず固定値にしているようだ。一方、paris-tracerouteの方は[udp sum ok]と表示されるため、ヘッダに併せてChecksumを正確に作り直していることが分かる。これが、tracerouteの動作の結果としてどう影響するかは分からないが、全く同じ挙動ではないという点は気をつけておいた方がいいだろう。また、paris-tracerouteは完全に全ての経路を把握してから標準出力に出力するので、複数経路を何らかのアルゴリズムで適当な経路を選択しているのかもしれない*1

なお、Windows版のtracertはICMPパケットを使った経路発見を行う。LinuxのtracerouteでもICMPやTCPを扱えるが、これも細かい仕様は両者で異なると思われるので、同じICMPパケットでも発見できる経路に違いが出るかもしれない。

また、-Aで各ホップの所属するAS番号を取得することができるので活用した方が良い。これは内部でwhoisを使っており*2whoisはポート45番*3を用いてwhoisサーバとやり取りするので、イントラネットがポート45番をフィルタしていると使うことができず、AS番号の部分が[!!]という表示になってしまう。

使用するパケットのプロトコルによる違い

上記でほとんど説明したが、総括するとtracerouteにはICMP/UDP/TCPの違いがあって、ネットワークによってはそれぞれで結果が異なることが予想できるのでいくつか試してみるべきだろう。あと、最後にpingで宛先とのRTTを確認して、どの程度まで経路発見が出来たのかを把握しておくのが良い。

実際にやってみた結果を考慮する*4と以下のようになった。ネットワークによって結果は変わってくるので、これが唯一の解答にはならないとは思う。

  • ファイヤウォールが厳しい場合はWell-Knownなポートを使ってみる
  • ロードバランスによる影響を抑えたい場合は宛先と送信元のポートを固定する
  • ウェブサーバに対してTCP80番を使うとCDNの影響により2〜3ホップで届いてしまうことがある(実際に知りたい経路ではない可能性がある)
  • 宛先ポートと送信元ポートを固定すると結果が悪くなる場合もあったため、デフォルト設定も含めていくつかのオプションを試すべき

*1:そのあたりは論文参照のこと https://paris-traceroute.net/images/e2emon2007.pdf

*2:実際にwhoisコマンドをインストールする必要は無かった

*3:straceで見た限りUDP/TCP両方を使っているようだ

*4:実際に発見した経路は出さないことにする

Git for WindowsにおけるRubyのputsの挙動

Git for Windows (Git bash)でrubyのプログラムを走らせているときプログラムが停止しているような挙動に遭遇した。デバッグしてみると、停止している箇所はユーザからの入力を受け付ける部分であったが、入力待ちで停止しているのではなく、putsでユーザに入力を促すメッセージを表示している部分であった。putsデバッグメッセージを入れると表示せずにそこで停止してしまうことに気づいて、pprintを代用してみたところ、pだと正常にメッセージ表示される。putsの後にpを持ってくると、putsも表示される。これはどうもputsの場合は非同期にバッファに蓄えられており、pの場合はバッファを含めて同期的に全て標準出力に出力される(flushされる)、という挙動になっているらしい。そのため、$stdout.sync = trueをプログラムの先頭に書いておくことで、putsでも正常にメッセージ表示されるようになった。

なお、Cygwinコマンドプロンプトから実行するとこのようなputsの問題は起こらなかった。

MinGWでどうなるかは試していませんが、こういった症状がある記事が見当たらなかったし、なかなかおもしろい挙動だったのでメモ。まあ、Git bashではgitコマンドだけを使うことにしておいた方が良い、ということなのかも。

環境は、Windows 7 32bit / Ruby 2.2 / Git for windows

git-for-windows.github.io

仮想マシンのスタックとネットワークI/Oについて

仮想化コンセプト

  • 仮想マシンモニタ=VMM(Virtual Machine Monitor)は、自身の子プロセスとして仮想マシンを実行し、ユーザモードでは実行できない命令を仮想マシンが発行したときは、CPUで例外が発生するため、それをVMMが補足(trap)*1して、仮想マシンが実行すべき命令をVMMが実行すれば良い(trap-and-emulate)。
  • そのためには、VMMは特権モードで実行し、仮想マシンを特権モードより低いモード(かつ、ユーザモードより高いモード)で実行すれば良い。

x86における仮想化

  • リングのコンセプトには0〜3の4段階があり、リング0はハードウェアにアクセスする特権命令を実行する。つまり、カーネルモードはリング0で実行し、ユーザモードはリング3で実行する。なお、1,2は使用しない。
  • x86では、「非特権命令であるためリング0以外で実行してもトラップは発生しないが、リングの状態やハードウェアリソースの状態に依存する命令」=センシティブ命令、が存在するため、仮想化コンセプト通りにVMMを実装してもうまくいかない。

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0004/004.jpg

  • そこで、バイナリトランスレーションという技術により、VMMが仮想マシンの実行するプログラムを解析して、センシティブ命令を別の命令に置き換えるという手法が確立されたが、実装の難易度が高く、VMMの選択肢が限られていた。

Intel VT-x/AMD-Vの登場

  • Intel VT-xはハードウェア(CPU)による仮想化の実現支援機構で、リング0の状態にVM root modeとVM non-root modeの区別を提供する。
  • かつ、全てのセンシティブな命令をトラップできるようになるので、バイナリトランスレーション等のテクニックも不要になった。
  • ホスト側のオペレーティング・システムがリング0を占有するために、ゲスト側のオペレーティング・システムをリング0以外の1か2で動かす必要があったが、このIntel VTのサポートにより、ゲスト側のオペレーティング・システムをリング0で動かしつつ、VMMはそれよりも上位からの制御が可能になった。

  • Intel VT-x

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0005/002.jpg

http://image.gihyo.co.jp/assets/images/dev/serial/01/vm_work/0005/003.jpg

  • 性能については、バイナリトランスレーションを採用しているVMwareの方が、CPUの仮想化支援機構を利用したKVMよりも、当初は速かった。VMEntryやVMExitによるモードの移行処理のオーバーヘッドが大きかったためである。CPUの技術向上によりこれらの処理に必要なクロック数が下がり、この差は解消されていった。

VMCS(Intel)/VMCB(AMD)

  • 仮想マシンが扱う各種レジスタなどの情報を保存しておくための物理メモリ上の領域。CPUによって、VMEntryの際にはVMCSから情報を復帰し、VMExitの際にはVMCSへ情報を退避する。VMCSに保存されない情報については、VMMによって復帰・退避が行われる。

http://image.slidesharecdn.com/2nd-intelvt-091006192819-phpapp01/95/bitvisor-intelvt-53-728.jpg?cb=1254857383

EPT (Extended Page Table)

  • ゲストOSは各プロセス毎にページテーブルを持つが、VMMはゲストの物理アドレスをホストの物理アドレスに変換する必要があるので、VMMはその変換表をSPT (Shadow Page Table)として管理しその変換をソフトウェア的に実行する。
  • このソフトウェア的な変換をなくすために、仮想マシンごとのゲストの物理アドレスからホストの物理アドレスへの変換を、MMUと同様にCPUによって実行する。これがEPT。
  • VMMによるSPTを用いたソフトウェア的な変換をなくすと共に、ゲストOSのページテーブル変更=SPTの更新時のVMExit/VMEntryのオーバーヘッドをなくすこともできる。

VPID (Virtual Processor Identifier)

  • TLB(Translation Lookahead Buffer)は、直前に利用したプロセスのページテーブルをCPUキャッシュに載せて再利用することで、メモリアクセスを減らして高速化する。
  • 仮想マシンのTLBと、VMMのTLBは異なるため、VMEntry-VMExitの際に(つまり仮想マシンのプロセスがシステムコールを呼んで特権命令を実行する度に)、TLBがフラッシュされてしまい、TLBの本来の意義が果たせなくなってしまう。
  • そこで、TLBをそれぞれの仮想マシンとVMMで使い分けてCPUキャッシュに保持するために、VPIDを導入しそれぞれのTLBを識別して管理できるようにした。

完全仮想化

  • ゲストOSを変更しない完全仮想化であらゆるOSをゲストとして実現する。KVMではQemuによるエミュレーションを利用するが、CPUのエミュレーションは非常に遅いので、Intel-VT/AMD-Vの仮想化支援機構が無いと実用性が無い。
  • KVMではHypervisorはLinuxホスト上でqemu-kvmと呼ばれる一つのプロセスとして動作し、kvm.koというカーネルモジュールを介して特権命令を実行する。

準仮想化

  • ゲストOSを変更する準仮想化で仮想化を実現するが、オープンソースのOSしかゲストとして採用できない。仮想マシンをリング1で実行することで、CPUの仮想化支援機構を必要としない方式。
  • Xen/VMware ESXではHypervisorは物理ハードウェア上で直接動作する。

Nested VMM

  • CPUの仮想化支援機構を、ゲスト上のVMMにも提供する機能。KVM on KVM などが可能になる。仮想マシン/proc/cpuinfovmxsmxといった単語が見える場合は、Nested VMMが有効。

I/Oの仮想化

Intel VT-d

SR-IOV

  • PCI Expressバイスが提供する機能で、VT-dによるダイレクトDMAを行いながらも、仮想マシン間でデバイスの共有が可能になった。
  • NICの場合、仮想スイッチによるCPUを用いたホスト-ゲスト間のトラヒック転送を行う必要がなくなり、物理NICのネイティブな処理能力を発揮することができる。

仮想デバイスによるNICエミュレーション

VMMが、エミュレートした仮想デバイスを仮想マシンに対して提供し、仮想マシンにはその仮想デバイスに対するデバイスドライバがインストールされる。それぞれ、バックエンド、フロントエンド、と呼ばれる。

仮想化環境におけるパケットフォワーディング

  • e1000

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-24-638.jpg?cb=1370268967

  • virtio

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-26-638.jpg?cb=1370268967

  • vhost-net

https://image.slidesharecdn.com/e4-bb-ae-e6-83-b3-e5-8c-96-e7-92-b0-e5-a2-83-e3-81-ab-e3-81-8a-e3-81-91-e3-82-8b-20-e3-83-91-e3-82-b1-e3-83-83-e3-83-88-e3-83-95-e3-82-a9-e3-83-af-e3-83-bc-e3-83-87-e3-82-a3-e3-83-b3-e3-82-b0-130603141515-phpapp01/95/-27-638.jpg?cb=1370268967

Thanks to

www.slideshare.net

ネットワークI/O

  • パケット受信処理

http://www.coderplay.org/images/2015-12-05-1/packet-receive-process.png

  • NAPI - ハードウェア割り込みが多くて性能が上がらない状況を改善するため、ハードウェア割り込みが発生した際にいったん割り込みを禁止して、カーネルが物理デバイスのメモリをポーリングする、という仕組みを提供するLinux Kernel API。ポーリングはプロセススケジューリングによって実行されるため、割り込み禁止からポーリングの間にNICに到着したパケットをまとめてソフトウェア処理できるため効率が良い。

http://www.coderplay.org/images/2015-12-05-1/nic-device-driver-process.png

  • 受信パケットを別のCPUで処理すると、プロセススケジューリングに依存してパケット処理の順序が変わってしまうことでreorderingが発生する頻度が多くなることを避けるため、受信パケットのソフトウェア上の処理は特定のCPUに集中してしまう。

  • RSS - 複数の受信パケットキューに5 tuplesをベースにパケットを振り分けて、それぞれのキューを別のCPUに割り当てて処理する制御を、ソフトウェアとして実現したもの。5 tuplesで振り分けることでreorderingの問題が起こるのを防ぐ。

  • RFS - RSSの仕組みをNIC上にハードウェアとして実現したもの。

  • netmap

    • ユーザアプリケーションが直接参照可能なメモリ領域とNICバイスをmmapによりマッピング
    • 上記のメモリ領域は再利用するためにリングメモリとして事前に確保
    • systemcallあたりの処理パケット数を増やすことによりコストを下げる(amortize)
    • 共有メモリ領域にメモリを確保することによりプロセス間(インターフェース間)のフォワーディングはzero-copyを実現

blog.yuuk.io

www.slideshare.net

www.coderplay.org

Linuxデバイスドライバ 第3版

Linuxデバイスドライバ 第3版

Intel DPDK

  • パケット処理におけるLinuxカーネルの処理がオーバーヘッドとなりつつあり、さらにSR-IOVなどNICと(ユーザスペースで動作する)仮想マシンを直接繋げる技術も登場している。
  • Intel DPDKは、Linuxカーネルバイパスし、ユーザスペースでデバイスドライバを動かして、直接パケットをアプリケーションに届けるようなプログラムを実装するためのSDKを提供する。
  • PMD(Poll Mode Driver)と呼ばれる特別なデバイスドライバを特定のCPUで動かしてNICを監視し、パケットをユーザスペースのアプリケーションに届ける。また、UIO/VFIOといったユーザスペースでデバイスドライバを動かすためのカーネルモジュールを使用する。
  • マルチコアを活用しており、フロー単位でCPUを割り当てるrun-to-completionモードと、処理単位でCPUを割り当てるpipelineモードが選択できる。

http://www.bosco-tech.com/file/160311_icm2015-muramatsu.pdf

f:id:nishidy:20161112001534p:plain:w500

blog.slankdev.net

*1:例外発生時に呼ばれるコールバック関数をオーバーライトしてる?

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

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

Bubble SortのようにIn-placeで要素を変更していくと、余分なメモリを使用する必要がないので、メモリ量はO(1)、つまり2要素の間で入れ替える分だけ用意すれば済むが、計算量は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/timeRSSを測定してみた。ソート対象データとしてはどちらも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の環境では実行するたびに測定結果に数秒の揺らぎがあったので、単純にスレッド数の違いが測定時間に影響しているのかどうかはまだ疑わしい。なお、GCPIntel 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

Binary Searchの集合への適用について

Binary Search – topcoder

Binary Searchは、例えばソートされている整数のリストにある値が含まれているかどうかを確認するときに使うと、単純なループでチェックするよりもかなり計算量を抑えることができる。単純にループで確認するやり方は計算量がO(n)になるが、Binary SearchではO(log(n))になる。どのくらい違うかというとO(1)≒O(log(n))≪O(n)くらいに考えれば良い。

このようにBinary Searchでリストから値を検索するためのライブラリは多くの言語で提供されている。ただ、Binary Searchはもっと強力で、ある実数の集合に対する適用が可能だ。対象が一見してシーケンシャルなものである必要はない。これは競プロでは良く使われる手法であり、慣れてくれば問題文を理解した時点ですぐにBinary Searchによる解法が適当だと判断できるようになるらしい。

対象が集合になってもBinary Searchとして考えるのはリストである。ただし、noyesがそれぞれ連続して現れるように述語(Predicate)を考える必要がある。noyesの境目は一つであり、その境目に向かってBinary Searchが進んで行くことになる。実装における勘所は以下になる。

  • 解答すべき値をLower boundとUpper boundの間で上下に振り、与えられた条件が答えになるような述語を考える
  • 与えられた条件の中で、最小値(Lower bound)と最大値(Upper bound)を考える

述語はyesnoを返却する関数を考えれば良い。ただし、リストに適用した場合の述語は、medianと比較した結果を返すだけ、であるのに比べると、もっと複雑になる。また、与えられた条件の中でboundを導き出すことも非常に重要である。例えば、以下の問題では実際にboundを取り違えて正しい値に収束しない実装を書いてしまった。

Problem Statement for FairWorkload

    int getMostWork(int[] folders, int workers){
        int low = 0;
        int high= 0;

        for(int f: folders){ high+=f; }

        int mid=0, c=0, t=0, m=0;
        while(low<high){
            mid = low + (high-low)/2;
            c=t=0;
            for(int f: folders){
                if(mid<f){ break; }
                if(t+f<=mid){ t+=f; }
                else{ 
                    t=f; c++;
                }
            }

            if(c<workers){ high = mid; }
            else{ low = mid+1; }
        }

        return low;
    }

この場合、Upper boundは全ての数を足し合わせたもので問題無いが、Lower boundは0以上でかつ十分小さな値、であればなんでも良いわけではない。ここは条件として与えられたリストの中の最大の値を使わなければいけない。

        for(int f: folders){
            if(low<f){ low=f; } // XXX
            high+=f;
        }

ソートされた整数のリストに対するBinary Searchのboundは、そのリストのインデックスの最大値と最小値であることは明白だが、集合に適用する場合はここを考えるのが一つの勘所になる。

このようにしてTopCoderのModerateレベルのBinary Searchで解ける問題を解いてみた。実装は以下。TopCoderは実際に解いた解答者の実装を公開しているので、そちらを参考にする方が良い。

FairWorkload - SRM 169 · GitHub

Mortgage – SRM 189 · GitHub

HairCuts – SRM 261 · GitHub

UnionOfIntervals – SRM 277 · GitHub

Linuxにおける各種メモリについて

Linuxで扱う様々な種類や単位のメモリについてまとめておく。また、メモリというリソースに関する制御や管理について考察する。

ulimit

$ ulimit -a | egrep "memory|stack"
max locked memory       (kbytes, -l) 64
max memory size         (kbytes, -m) unlimited
stack size              (kbytes, -s) 8192
virtual memory          (kbytes, -v) unlimited
  • max locked memory - mlockシステムコールを使うことにより、メモリの内容がディスク上にスワップされないようにする(=Lockする)ことができる。その最大容量。
  • max memory size - 静的(スタック領域)や動的(ヒープ領域)に確保するメモリの最大容量。
  • virtual memory - ディスク上の仮想メモリ空間(スワップされたプロセスが使用する)の最大容量。
  • stack size - 静的(スタック領域)に確保するメモリの最大容量。

ulimitの機能

  • シェル組み込みの機能で、ユーザ毎にCPUやメモリ、ファイル、PIPEなどのリソースの使用量に制限を設ける。
  • ソフトリミットはハードリミットを超えない範囲で設定が可能で、ハードリミットを上げることができるのはrootのみ。
  • ulimitの制御は、setrlimit/getrlimitシステムコールを使って行われる。
$ strace bash -c "ulimit -S -s 65535" 2>&1 | grep -i rlimit
getrlimit(RLIMIT_NPROC, {rlim_cur=1024, rlim_max=3897}) = 0
getrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
getrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
setrlimit(RLIMIT_STACK, {rlim_cur=65535*1024, rlim_max=RLIM64_INFINITY}) = 0
$ strace bash -c "ulimit -H -s 819200" 2>&1 | grep -i rlimit
getrlimit(RLIMIT_NPROC, {rlim_cur=1024, rlim_max=3897}) = 0
getrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
getrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=RLIM64_INFINITY}) = 0
setrlimit(RLIMIT_STACK, {rlim_cur=8192*1024, rlim_max=819200*1024}) = 0 
  • なお、ディスク(パーティション)の使用量制限に関してはulimitではなくquotaで行う。

quota

  • ユーザ単位・グループ単位でディスク(パーティション)の使用量に制限を設ける。
  • mountオプションとしてusrquota・grpquotaを指定する必要がある。
  • ソフトリミットは猶予期間内であれば超えることができるが、猶予期間を超えるとソフトリミットまで削減(削除)される。
  • ハードリミットは超えることができない。
  • quotaの管理は、パーティションのトップディレクトリに置かれるaquota.user, aquota.groupファイル上で行われる。

ps / pmap / time*1

$ ps aux | head -n1
USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
$ pmap -X $(pidof bash) | head -n2
2571:   pmap -X 2571 2073
         Address Perm   Offset Device  Inode   Size  Rss Pss Referenced Anonymous Swap Locked Mapping
$ /usr/bin/time -apv ls 2>&1 | grep resident
    Maximum resident set size (kbytes): 2428
    Average resident set size (kbytes): 0
  • VSS/VSZ (Virtual Set Size) - プロセスが確保したメモリ。ただし、実際には使用していないメモリを含む。
  • RSS (Resident Set Size) - プロセスが実際に使用しているメモリ。ただし、共有ライブラリのメモリを含む。共有ライブラリのメモリは各プロセスで重複してカウントされている。
  • PSS (Proportional Set Size) - プロセスが実際に使用しているメモリ。ただし、共有ライブラリのメモリをプロセス数で割ったものを含む。共有ライブラリのメモリ量を、使用しているプロセス数で割ることで、RSSの問題点を解決している。

  • (例)dhclientとcupsdはlibcryptoを共有ライブラリとして利用しており、それぞれのプロセスのRSSとしてカウントされている。

$ ldd /sbin/dhclient | grep libcrypto
    libcrypto.so.10 => /usr/lib64/libcrypto.so.10 (0x00007f62d75f7000)
$ ldd /usr/sbin/cupsd | grep libcrypto
    libcrypto.so.10 => /usr/lib64/libcrypto.so.10 (0x00007fd442cef000)
$ ps -FC dhclient
UID        PID  PPID  C    SZ   RSS PSR STIME TTY          TIME CMD
root      2394   842  0 25553 19040   0 23:27 ?        00:00:00 /sbin/dhclient -d -sf /usr/libexec/nm-dhcp-helper -pf /var/run/dhclient-p2p1.pid -lf /var/lib/
$ ps -FC cupsd
UID        PID  PPID  C    SZ   RSS PSR STIME TTY          TIME CMD
root      1709     1  0 47262  2044   0 23:11 ?        00:00:00 /usr/sbin/cupsd -f
$ man ps
...
       rss         RSS       resident set size, the non-swapped physical
                             memory that a task has used (inkiloBytes).
                             (alias rssize, rsz).
...
  • pmapのRSSとSizeは、実際にメモリに読み込まれているかどうかの違いがある。この違いは、デマンドページングによりページフォルトが発生するまで実際のメモリへの読み込みを遅延する、ことによって現れる。それによって、例えば共有ライブラリの中の実際に使用する関数のみをメモリに読み込んで実行することができる。Sizeは実際には読み込まれておらず、論理アドレスに割り当てただけの部分もカウントしている。

  • デマンドページングはmalloc発行時にも効果を発揮する。mallocを発行すると論理アドレス上ではメモリを割り当てたことになるが、物理メモリ上ではまだメモリ領域は確保されず、実際にメモリに書き込んだ際、初めて物理メモリ上でメモリ領域が確保される。この機構により実際の物理メモリ容量よりも大きいメモリをmallocにより割り当てることができ、これをオーバーコミットと呼ぶ。ただし、実際に物理メモリ以上の領域に書き込もうとすると、メモリ不足の例外が発生するか、OOM Killerにより停止されるだろう。オーバーコミットの容量はsysctlである程度制御が可能である。

/proc/meminfo

$ cat /proc/meminfo | egrep -i "active|dirty|claim|mem|slab"
MemTotal:        1017448 kB
MemFree:           97304 kB
MemAvailable:     316264 kB
Active:           317736 kB
Inactive:         371132 kB
Active(anon):     209564 kB
Inactive(anon):   244268 kB
Active(file):     108172 kB
Inactive(file):   126864 kB
Dirty:               324 kB
Shmem:              3444 kB
Slab:             192720 kB
SReclaimable:     152860 kB
SUnreclaim:        39860 kB
  • anon(Anomymous) - プロセスが確保したメモリ。ディスクに退避(スワップ)されることがある。
  • file(File-backed) - OSがディスクキャッシュとして確保したメモリ。(Dirtyなもの以外は)もともとディスク上に存在するデータ。
  • Shmem - tmpfsとして使用されているメモリ。tmpfsはメモリ上にのみ存在するが、スワップの対象となりディスクに書き出される。

  • Active/Inactive - LRU的に、最近使用されたメモリか、利用されていないメモリか。

  • Dirty - ディスクに書き込まれていないFile-backedなバッファ。syncでディスクに書き込むと0になり、Cleanなバッファとなる。Cleanなバッファは、echo 1 > /proc/sys/vm/drop_cachesで解放される。

$ cat /proc/meminfo  | grep Dirty
Dirty:              1032 kB
$ sync
$ cat /proc/meminfo  | grep Dirty
Dirty:                 0 kB
  • Slab - SReclaimable + SUnreclaim

    • SReclaimable - 解放可能なSlab。 echo 2 > /proc/sys/vm/drop_cachesで解放される。
    • SUnreclaim - 解放不可能なSlab。
  • echo 2 > /proc/sys/vm/drop_caches の直後でもSReclaimableは0にならないが、slabtopで確認するとdentryやinodeがSlabを使用しているのが分かる。バックグラウンドプロセスやカーネルの処理が動いているため、すぐにSlabの割り当てが行われているのだろう。

$ cat /proc/meminfo | egrep -i "slab|claim"
Slab:             210504 kB
SReclaimable:     170240 kB
SUnreclaim:        40264 kB
$ echo 2 > /proc/sys/vm/drop_caches 
$ cat /proc/meminfo | egrep -i "slab|claim"
Slab:              79436 kB
SReclaimable:      45460 kB
SUnreclaim:        33976 kB
$ slabtop -o -sc | head -n 12
 Active / Total Objects (% used)    : 579600 / 661586 (87.6%)
 Active / Total Slabs (% used)      : 11754 / 11754 (100.0%)
 Active / Total Caches (% used)     : 74 / 100 (74.0%)
 Active / Total Size (% used)       : 51588.87K / 78695.04K (65.6%)
 Minimum / Average / Maximum Object : 0.01K / 0.12K / 8.00K

  OBJS ACTIVE  USE OBJ SIZE  SLABS OBJ/SLAB CACHE SIZE NAME                   
 29368   8839  30%    0.99K   1894       16     30304K ext4_inode_cache       
  9674   9378  96%    0.55K    691       14      5528K inode_cache            
 63189  20416  32%    0.08K   1239       51      4956K Acpi-State             
 21210  12372  58%    0.19K   1010       21      4040K dentry                 
118528 118528 100%    0.03K    926      128      3704K kmalloc-32   
$ slabtop --help
...
The following are valid sort criteria:
 c: sort by cache size
...
  • VmallocUsed - カーネルが使用しているSlab以外のメモリ。ただし、デバイス上の物理メモリを含んでいる。デバイス上の物理メモリは/proc/vmallocinfoioremapの部分。
$ sudo cat /proc/vmallocinfo | grep ioremap
0xffffc90000000000-0xffffc90000004000   16384 acpi_os_map_iomem+0xf7/0x150 phys=3fff0000 ioremap
0xffffc900001f8000-0xffffc900001fb000   12288 pci_iomap+0x55/0xb0 phys=f0806000 ioremap
0xffffc900001fc000-0xffffc900001fe000    8192 usb_hcd_pci_probe+0x14d/0x550 phys=f0804000 ioremap
0xffffc90000280000-0xffffc900002a1000  135168 pci_ioremap_bar+0x46/0x80 phys=f0000000 ioremap
0xffffc90000300000-0xffffc90000701000 4198400 vgdrvLinuxProbePci+0x9c/0x210 [vboxguest] phys=f0400000 ioremap

$ sudo cat /proc/vmallocinfo | grep ioremap | awk '{print $2}' | paste -s -d '+'
16384+12288+8192+135168+4198400
$ sudo cat /proc/vmallocinfo | grep ioremap | awk '{print $2}' | paste -s -d '+' | bc
4370432
  • PageTables - 各プロセスにおける論理アドレスから物理アドレスへの変換表。なお、現在CPUで実行中のプロセスのページテーブルは、CR3レジスタでそのメモリアドレスが示される。

free

  • /proc/meminfoの内容を元に、メモリの使用量や残量を示してくれる。なおx86(32bit)では、lオプションはカーネルが使用するLowメモリと、プロセスが使用するHighメモリを分けて表示してくれる。なおカーネルが使用するLowメモリは、物理アドレスの1MB〜893MBまで、また各プロセスの論理アドレスの3GB〜4GBの領域を占める。x86_64(64bit)では、LowメモリやHighメモリといった区別が無いため、lオプションで表示する場合は全てLowメモリとして表示し、Highメモリは常に0として表示されるようである。
$ free -l
             total       used       free     shared    buffers     cached
Mem:       1017448     949096      68352       4004      88984     131476
Low:       1017448     949096      68352
High:            0          0          0
-/+ buffers/cache:     728636     288812
Swap:       839676      45872     793804

Slab

  • メモリの割り当てや解放を繰り返して毎回初期化するよりも、カーネルはOSにメモリを戻さずに(解放せずに)初期化した状態のまま保持し続けておき、 必要になったらそこから再利用することでパーフォーマンスが上がる。Slabはオブジェクトキャッシュとも呼ばれる。

  • 小さい単位のメモリ割り当て・解放を、その都度メモリから自由に行うとフラグメントの問題を引き起こしやすくなるが、Slabとして保持しておいて再利用することで、少なくともスラブを利用している限りにおいてはフラグメントの問題は起こらない。

  • SlabのAPI

    • kmem_cache_create - Slabを確保する
    • kmem_cache_alloc - Slabから実際に使うオブジェクトへメモリを払い出す
    • kmem_cache_free
  • Slabは単一のオブジェクトを連続したメモリ上に複数格納する。

http://4.bp.blogspot.com/-zfUCD_rkxMI/VKkcpQ789dI/AAAAAAAABrQ/j1fpLSFTrVU/s1600/study%2B%283%29.png

  • Slabがemptyになると、リープ(OSに戻す)対象となる。

http://1.bp.blogspot.com/-G4jHb5oQfyM/VKkcpZo14fI/AAAAAAAABrM/y-FCpnX7cKQ/s1600/slab%2B%281%29.png

  • Cache Coloring - Slabのオブジェクトはページに沿って配置されているため、CPUの特定のキャシュラインに集中してしまう。別のオブジェクトがCPUの別のキャッシュラインに載るように、Slabごとに少しフラグメントを持たせる。

http://www.secretmango.com/jimb/Whitepapers/slabs/slabcolor.gif

Slabが大量消費されていることでメモリを圧迫する問題(問題?)

  • dentryやinodeはSlabのヘビーユーザであり、それによってSlabが大量に消費されていることがある。/proc/sys/vm/drop_cachesに2 or 3を書き込むことで、Slab(SReclaimable)は解放されるが、Slabを完全に解放してしまうとLinuxとしての性能は格段に落ちる。

    • dentry - Linuxには、システムコールから各種ファイルシステムを抽象化して統一的に扱うために、VFSの層が存在する。VFSでは、dentryという構造体を使用してディレクトリ構造やファイル名とinodeとの対応などをキャッシュする。なお、dentryはメモリ上にのみ存在し、ファイルシステムの一部のデータとして存在しているわけではない。
    • inode - ファイルシステムでファイルを管理するためのメタ情報。ファイルのサイズやパーミッション、データブロックの位置などが管理されている。
    • ページキャッシュ - ファイルのデータブロックのキャッシュ。
  • そもそもメモリをたくさん消費しているのはリソースを効率良く使用できている状態とも言えるので、問題なのはそれによってスワッピングが発生しているか否かであり、それはvmstatコマンドのsi,soの項目を確認することで分かる。SlabもLRUによって管理されているはずなので、基本的にはそれにまかせるのが得策なのではないだろうか。 なお、vmstatで最初に表示される結果は、起動時からの平均値、になる。

$ vmstat
procs -----------memory---------- ---swap-- -----io---- -system-- ----cpu----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa
 1  1  51596  75360  71636 172804    1   10   337    19  142  462  1  2 96  1

$ man vmstat
...
   Swap
       si: Amount of memory swapped in from disk (/s).
       so: Amount of memory swapped to disk (/s).
...
  • Slabのページキャッシュに対する比率を制御するには、/proc/sys/vm/vfs_cache_pressure を使う。100を基準として、Slabの比率を増やしたり減らしたりできるらしい。その他、/proc/sys/vmで管理されているパラメータについてはこちら → https://www.kernel.org/doc/Documentation/sysctl/vm.txt

Slabの肥大化で実際にスワップが発生した問題とその解決方法

  • いきなり上記で書いた内容と矛盾するが、Slabの肥大化によってスワップが発生してしまった事例がある。つまり、メモリ圧迫時にはLinuxによるLRUに基づくSlabの解放を期待したがうまく動いてくれなかった、ということになる。原因として考えられるのは、dentry cacheを解放するスピードが間に合わないのか、とある。解決方法としては、tmpfsを使うことによりSlabの肥大化を回避できるとのことだが、その理由としてはtmpfsがLinuxのVFSを使わないからでしょうかとのことだが、tmpfsではそそもそもdentry cacheを生成しないのだろうか。この事例から「一時ファイルはtmpfsにおいて処理する」は鉄則だろう。

blog.nomadscafe.jp

  • negative dentry - 存在しないパスを開くと、それについてもnegativeなdentry cacheとしてキャッシュする。dentry cacheにヒットしない場合、ファイルシステムに問い合わせることでディスクI/Oが発生するが、negative entryがあればその必要が無いのでディスクI/Oを減らす効果が期待できる。negative dentryはsar -vコマンドの結果のdentunusdが示す値に含まれているらしい。なお、negative cacheはDNSでも不要なクエリを発生させないために使われることがある。
$ sar -v | tail -n +3 | head -n4
12:10:01 AM dentunusd   file-nr  inode-nr    pty-nr
12:20:01 AM     80492      4832     75177         1
12:30:01 AM     80506      4832     75184         1
12:40:01 AM     80495      4800     75166         1
$ man sar
...
              dentunusd
                     Number of unused cache entries in the directory cache.
...

d.hatena.ne.jp

ページキャッシュを効率よく管理するためのアプローチ

  • cachectld - posix_fadviseとPOSIX_FADV_DONTNEEDをディレクトリ単位で適用することにより、必要なページキャッシュは残しつつ、不要なページキャッシュだけをディレクトリ単位で解放する。

tech.mercari.com

ページキャッシュが不要ならO_DIRECTを使うアプローチは?

  • openシステムコールにO_DIRECTフラグを渡すと、ファイルへの書き込みや読み込みをVFSを介さずにファイルシステムと直接行うため、メモリにページキャッシュを残すことが無い。これは、再利用することが無いと分かっている大きなファイルを開くときには、無用にメモリを使用することが無く、他のAnonymousやFile-backedなメモリに対して優しいと言える。ただし書き込みの際は、バッファへの書き込みが行われず、プロセスがディスクへの書き込み待ちで長い時間ブロックされることになるため注意が必要。

  • 書き込みはページキャッシュとしてメモリに蓄えられた後で非同期に(flusherスレッドによってデフォルト5秒間隔で)ディスクへ書き込まれるので、通常はプロセスが書き込みでブロックされることはない。一時的にメモリを消費してしまうものの、ディスクへ書き込んだ直後に該当のページキャッシュを解放するような仕組みがあっても良さそう。

ramfs

  • ramfsはtmpfsのようにメモリ上に作成されるファイルシステムだが、ramfsの方は物理ディスクがないにも関わらず、File-backedとして登録されるため、ディスクにスワップされることがない。

プロのための Linuxシステム構築・運用技術 (Software Design plus)

プロのための Linuxシステム構築・運用技術 (Software Design plus)

*1:シェル組み込みのtimeではなく、シェルスクリプトとしてインストールされている/usr/bin/timeの方