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の肥大化によってスワップが発生してしまった事例がある。つまり、メモリ圧迫時には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の方

コード最適化についての考察

文字列のリストとその出現数をカウントして多い方からN個取得する処理を考える。単純にやろうとすれば、とにかく文字列とその出現数をkey/valueとしてカウントしていき、最後にvalueでソートして多い方からN個取得すればいい。

ただし、Nが非常に小さい場合、このやり方は効率が悪い。つまり例えば、key/valueが1,000,000個あったとして、その中で多い方から5個取り出す場合、1,000,000個のリストをソートすることになり、それだけでO(nlogn)かかるが、Nが小さい場合にはこのソートは必要ない/ほとんど無駄なはずである。

以下の通り実装して、計算にかかる時間を測定した。

  • take_top_n_by_sort() - 単純に全てのkey/valueをカウントして最後にvalueでソートする方法
  • take_top_n_no_sort - ソートを使わず、出現数の多いN個を随時更新していく方法
  • take_top_n_no_sort2 - 出現数の多いN個から最小の出現数を取得する処理をなるべく行わない方法

C++についていえば、このような用途でmapを使う必要性は無いと言える。mapはkeyがソートされたデータ構造となっているが、keyによるvalueの探索にはBinary SearchによるO(logn)が必要になる。一方、unordered_mapはハッシュを使用しており、探索はO(1)で済む。

また、Javaにはmapの実装としてTreeMapやHashMapがあるが、このような用途ではHashMapを使うべきだろう。他の言語でも、key/valueのデータ構造は必ずといって良いほど標準で実装されているが、C++のmapのようなものはあまり見ない。

ただ、これをMacLinux(Google Compute Engine - vCPU 1)で実行してみたところ、Macの方がSortが10倍以上速いため、keyが5Mくらいでは、Sortを使った方法の方でも速くなった。Clang/LLVMではC++11におけるsort()がかなりうまく最適化されているようだ。以下記事を見ても、Clangが最も速いことが分かる。

solarianprogrammer.com

#define SIZE 10000000
#define CHARS 5
#define TOPN 5
  • インプットデータは以下のように正規分布に従って乱数を生成することにより出現数に偏りを持たせているため、文字列の組み合わせ総数は11881376だがそれよりかなり少なくなっている
void make_input_data(vector<string>* out){
        mt19937 mt(1);
        normal_distribution<double> dist(13.0,6.0);
        for(auto i=0;i<SIZE;i++){
                string s;
                for(auto j=0;j<CHARS;j++){
                        s.push_back((char)(((int)dist(mt))%26+65));
                }
                out->push_back(s);
        }
}
  • Macでの実行結果
$ g++ --version
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin14.5.0
Thread model: posix

$ sysctl -a machdep.cpu
machdep.cpu.max_basic: 13
machdep.cpu.max_ext: 2147483656
machdep.cpu.vendor: GenuineIntel
machdep.cpu.brand_string: Intel(R) Core(TM) i5-4258U CPU @ 2.40GHz
...
machdep.cpu.core_count: 2
machdep.cpu.thread_count: 4

$ g++ take_top_n.cpp -std=c++11

$ ./a.out 
Elapsed time for sort() with 5045629 keys : 815ms
Elapsed time for take_top_n_by_sort() : 15689ms
LMOOM
LMKNK
HLLMM
MOKOO
NPNKH

Elapsed time for take_top_n_no_sort() : 47057ms
NPNKH
HLLMM
LMKNK
LMOOM
MOKOO

Elapsed time for take_top_n_no_sort_with_flag() : 15612ms
NPNKH
HLLMM
LMKNK
LMOOM
MOKOO
  • Linuxでの実行結果
$ g++ --version
g++ (Debian 4.9.2-10) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 63
model name      : Intel(R) Xeon(R) CPU @ 2.30GHz
stepping        : 0
microcode       : 0x1
cpu MHz         : 2300.000
cache size      : 46080 KB
physical id     : 0
siblings        : 1
core id         : 0
cpu cores       : 1
apicid          : 0
initial apicid  : 0
fpu             : yes
fpu_exception   : yes
cpuid level     : 13
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2
 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 f
ma cx16 sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm xsaveopt fsgsbase bmi1 a
vx2 smep bmi2 erms
bogomips        : 4600.00
clflush size    : 64
cache_alignment : 64
address sizes   : 46 bits physical, 48 bits virtual
power management:

$ ./a.out 
Elapsed time for sort() with 5045954 keys : 10050ms
Elapsed time for take_top_n_by_sort() : 25432ms
NOLPL
NOKMM
PJOMO
LMNMO
NLOOM

Elapsed time for take_top_n_no_sort() : 33195ms
NOKMM
NLOOM
LMNMO
PJOMO
NOLPL

Elapsed time for take_top_n_no_sort_with_flag() : 16060ms
NOKMM
NLOOM
LMNMO
PJOMO
NOLPL

コンパイラによる最適化

  • Macのg++に-O3をつけて実施した結果、およそ2倍くらい速くなる
$ g++ take_top_n.cpp -std=c++11 -O3
$ ./a.out 
Elapsed time for sort() with 4787637 keys : 331ms
Elapsed time for take_top_n_by_sort() : 7743ms
LMKNK
LMOOM
HLLMM
MOKOO
NPNKH

Elapsed time for take_top_n_no_sort() : 19158ms
NPNKH
HLLMM
LMKNK
LMOOM
MOKOO

Elapsed time for take_top_n_no_sort_with_flag() : 8985ms
NPNKH
HLLMM
LMKNK
LMOOM
MOKOO

ファイルシステム(ext2/ext3/ext4)の基礎まとめ

ext2

  • 正常にアンマウントが実行されなかった場合には、パーティション全体のメタデータと実データの整合性をfsckによって確認する必要がある

  • ブロック構造 - ブロックサイズは1KB,2KB,4KBのいずれか

http://3.bp.blogspot.com/-grP9mP9Kez8/UQaBRvz2E9I/AAAAAAAAASA/0kgIh9QvkLU/s1600/ext3.JPG

  • スーパーブロックには全体のi-node数など、グループデスクリプタにはそのブロックグループのi-node数など、i-nodeにはファイルのメタデータとデータブロックのアドレスなど、が記録されている

    • スーパーブロックはバックアップされており、mkfs.ext2 -nでバックアップされたブロックを確認することができ、mkfs.ext2 -bでそのブロックを指定することで復旧できる
  • 間接ブロック参照 - ext2のi-nodeにはデータが保存されているブロック番号を格納するサイズ15のテーブルがあり、そのうち#0〜#11は直接ブロック参照(ブロック番号を格納する)、#12は1段間接ブロック参照(ブロック番号を格納したテーブルを参照する)、#13は2段間接ブロック参照(ブロック番号を格納したテーブルを参照するテーブルを参照)、#14は3段間接ブロック参照、に使用される

http://wiki.bit-hive.com/linuxkernelmemo/upload/54/696e6f64655f626c6f636b.png

Ext2 FS - Linuxカーネルメモ

  • 間接ブロック参照によって1ファイル4TBまでブロックを参照できるが、i-nodeのメタデータにあるブロック数が2TB(ブロックサイズが4KBの場合)までしか管理できないので、そちらが1ファイルサイズの限界を決めている

  • 大きいサイズのファイルになると間接参照が多くなるため、書き込みや読み込みの性能が悪くなる

ext3

ジャーナリング

  • データの更新処理を、不可分(アトミック)な一つのトランザクションに集約して記録することで、ファイルシステムの整合性を維持するための仕組み
  • たとえファイルを削除するという単純なトランザクションの中でも、スーパーブロックやファイルのメタデータに対する様々なステップ処理が存在するため、その途中で不正なシャットダウン(アンマウント)が発生し、一部のステップ処理のみが実行される状態になるとメタデータの整合性が崩れる
  • ジャーナルログがあれば、不正なアンマウントが発生してそのパーティションcleanな状態でなくなっても、メタデータと実データとの不整合を復旧するだけでよい
    • fsckはステップ処理単位での復旧も可能だが、ジャーナルログがあれば(トランザクション単位での不可分な更新記録が存在するため)fsckの明示的な実行は不要で、ファイルシステムの機能としてジャーナルログから自動的に復旧する
    • ジャーナルログはあくまでもファイルシステムの整合性を維持するための仕組みであり、実データについては保証しない(書き込んだと思ったものが消失する)
  • ただしext3であっても、何らかの不正な書き込みが発生してメタデータの整合性が壊れると、fsckによるステップ処理単位での復旧が必要になるし、fsckを実施していない期間がある一定期間を超えるとパーティション全体の整合性を確認することになる

qiita.com

O+P Insights: Improving Ext3 performance with an external journal on an SSD Disk

Linuxカーネル2.6解読室

Linuxカーネル2.6解読室

fsck

  • メタデータの矛盾を取り除くコマンド。壊れたデータを復旧するわけではなく、メタデータの整合性が取れるように壊れた部分を排除する。
  • ファイルシステムには定期的にfsckを実行するオプションがある。ジャーナルログを採用しているファイルシステムであっても、マウントを実行した回数や前回fsck実行からの期間、によってサーバ起動時にfsckが発動してパーティション全体を走査することによる起動遅延が発生することがある。
$ sudo tune2fs -l /dev/sda1 | egrep -i "mount count|check"
Mount count:              16
Maximum mount count:      -1
Last checked:             Sun Jun 19 00:06:19 2016
Check interval:           0 (<none>)
  • fsckのチェックによってファイルシステムの整合性を保つためにディレクトリやi-nodeの内容が破棄されることで、参照不可能になったデータブロックの内容は/lost+foundディレクトリに#とi-node番号をファイル名として退避される。

kjournald

  • トランザクションを、定期的にディスク上のジャーナルログ領域に書き込む(コミットする)デーモン
  • kjournaldの書き込み間隔はデフォルトで5秒で、この間隔は信頼性と性能(データの永続化とDisk I/Oの回避)のトレードオフとなる

ジャーナルモード

www.atmarkit.co.jp

  • ジャーナルモードはマウントオプションとしてdata=journalなどとして指定する
journal
  • メタデータと実データのトランザクションをコミットしたのち、メタデータと実データをディスク上のデータ領域に書き込む
  • 完全にデータを冗長化することができるが、書き込み性能は悪い
  • ジャーナルログとデータ領域に不整合が発生することがない
ordered
  • 実データが書き込まれたのち、メタデータトランザクションをコミットする
    • つまり、実データの書き込み順序と、トランザクションへのコミット順序が、常に一貫性を保つ(シーケンシャルに実行される)ことを保証する
  • 実データがディスク上のデータ領域に書き込まれる前に不正なアンマウントが発生すると…
    • ジャーナルログから、ディスク上のデータ領域のメタデータを復旧する
    • 新しい実データが(バッファには書き込まれているものの)ディスク上のデータ領域に書き込まれていない場合は、実データは復旧できない
  • 新しい実データの復旧はできないが、ジャーナルログによるメタデータの復旧は可能になる
writeback
  • 実データの書き込み順序と、トランザクションへのコミット順序が、一貫性を保てない
  • 実データがデータ領域に書き込まれる前に不正なアンマウントが発生すると…
    • ジャーナルログはシーケンシャルに書き込まれたものであることが保証されていないため、メタデータの復旧が正しく行われないことがある
  • 書き込み性能は最も良いが、メタデータの復旧がうまくいかない場合があることを許容する動作になる

MySQLInnoDB)との関連について一言

WAL / Double Write
  • WAL (Write Ahead Log) は、トランザクションがコミットされたときに、トランザクションの内容をディスク上のログ領域に書き込む(更新データはバッファ上に残っている)
  • Double Writeは、バッファからディスクへフラッシュされたときに、ディスク上のデータ領域に書き込む前に、ダブルライトバッファ領域に書き込む(更新データのコピーを保持することができる)
  • これらの領域はシーケンシャルに書き込まれていくので、ディスク上のシーク時間が短く、I/Oに必要な時間が短い(Double Writeといっても書き込み時間が二倍になるわけではない)

ext4

  • 遅延確保 - ext3まではバッファ書き込み時にディスク上のブロック割り当てを行うが、これをバッファ書き込み時からディスク書き込み時にまで遅延することで、複数の書き込みをまとめてブロック割り当てを行うことができるため、連続したブロックを割り当てやすくなりフラグメンテーションを起こりにくくする

  • エクステントの導入 - 大きなファイルに対して、複数のブロックの格納場所を全て保持する(かつ、多段参照のオーバーヘッドがある)と非効率なため、隣接するブロックに対してその格納場所を配列として保持することにより効率化する(先頭ブロックの格納場所と連続ブロック数(オフセット)、を組み合わせて複数保持する)

    • 一つのi-nodeに格納できるエクステントは限りがあるので、Extent-IndexをB-treeとして保持することで検索効率を上げる

https://www.usenix.org/legacy/event/lsf07/tech/cao_m.pdf

# ext4
$ mount | grep " / "
/dev/mapper/fedora-root on / type ext4 (rw,relatime,seclabel,data=ordered)
$ stat /etc/fstab 
  File: ‘/etc/fstab’
  Size: 465         Blocks: 8          IO Block: 4096   regular file
Device: fd01h/64769d    Inode: 130747      Links: 1
Access: (0664/-rw-rw-r--)  Uid: (    0/    root)   Gid: (    0/    root)
Context: system_u:object_r:etc_t:s0
Access: 2017-02-14 09:24:21.453460379 +0900
Modify: 2014-03-01 18:43:24.267325166 +0900
Change: 2014-03-01 18:43:24.267325166 +0900
 Birth: -
# ext3
$ dd if=/dev/zero of=ext3img bs=1M count=100
100+0 records in
100+0 records out
104857600 bytes (105 MB) copied, 0.386865 s, 271 MB/s
$ mkfs.ext3 -F ext3img 
mke2fs 1.42.12 (29-Aug-2014)
Discarding device blocks: done                            
Creating filesystem with 102400 1k blocks and 25688 inodes
Filesystem UUID: 235bf453-34b4-430e-b508-4279dbc61c6c
Superblock backups stored on blocks: 
    8193, 24577, 40961, 57345, 73729

Allocating group tables: done                            
Writing inode tables: done                            
Creating journal (4096 blocks): done
Writing superblocks and filesystem accounting information: done 

$ sudo mkdir /mount
$ sudo mount -t ext3 -o loop ext3img /mount/
$ mount | grep ext3
/home/nishidy/ext3img on /mount type ext3 (rw,relatime,seclabel,data=ordered)
$ sudo touch /mount/file
$ sudo vim /mount/file 
$ stat /mount/file 
  File: ‘/mount/file’
  Size: 12          Blocks: 4          IO Block: 1024   regular file
Device: 700h/1792d  Inode: 14          Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Context: unconfined_u:object_r:file_t:s0
Access: 2017-02-14 09:31:39.000000000 +0900
Modify: 2017-02-14 09:31:25.000000000 +0900
Change: 2017-02-14 09:31:25.000000000 +0900
 Birth: -
  • チェックサムの導入 - ジャーナルログにチェックサムが追加されて、ジャーナルログに対するチェックサムチェックが可能になり、信頼性が向上する

  • H-Tree - ext2/ext3ではディレクリ構造が連結リストにより管理されていたが、連結リストでは探索にO(n)の時間がかかるため、B-Treeの改良版であるH-Treeが採用されており、これにより探索時間が短縮される*1

Directory indexing

  • 動的なi-node確保 - …

B-Tree

https://upload.wikimedia.org/wikipedia/commons/6/68/B-tree_example.svg

  • Balanced Tree(平衡木の一つ)
  • 検索における計算量
    • 木に含まれる全てのキーの数をn、ノードが持つ子の最大数をm(ノードが持つキーの最大数をm-1)とする
    • ノードが持つ子の平均数は m/2 になり、よって木の深さは となる
    • ノードのキー探索回数は、mが大きいときにはBinary Searchによってlog mとなる(キーはソート済み)
    • よって計算時間は log m * となり、計算量は O( log m * ( log n / log m) ) となって、結果的にO(log n)となる

e.g.

30 50 70 | 
10 20 | 40 | 60 | 80 90 | 

B+-Tree

  • B-Treeを拡張した、Key-Valueを格納する木構造
  • リーフノードのみがValueを持つ(全てのKey-Valueがリーフノードに存在する)ため、必ずリーフノードまで辿り着く必要がある

e.g.

30 50 70 | 
10 20 | 30 40 | 50 60 | 70 80 90 |

http://www.drk7.jp/MT/drk/images/091108/ora003.png

Oracle の B*Tree インデックスの内部構造についてお勉強中(その1) - drk7jp

Interactive B+ Tree

B*-Tree

  • B+-Treeを拡張して、ノードの持つキー数をなるべく多く保つ(as dense as possible)ことで、メモリ利用効率や検索速度が向上
    • 最大数のキーを保持しているノードに挿入する場合、(B+-Treeのように)即座にノードを分割するのではなく、隣のノードに空きがある場合は、親ノードを介した回転を伴って、隣のノードにキーを移動させる
    • 隣のノードも最大数のキーを保持している場合、二つのノードを三つのノードに分割する

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

The Art of Computer Programming Volume 3 Sorting and Searching Second Edition 日本語版 (Ascii Addison Wesley programming series)

XFS

  • アロケーショングループ
    • パーティションを同一サイズの複数のエリアに分け、各アロケーショングループを独立に管理することにより、書き込み処理を並列に行うことができるようにする
    • ext4ではスーパーブロックにパーティション全体を管理する情報が書き込まれているため、書き込み処理はシーケンシャルな実装にする必要がある
    • XFSでは各アロケーショングループにおいてスーパーブロックが独立しているため、スレッドでCPU的には並列な書き込み処理が実装できる*2

Btrfs

  • コピーオンライト(CoW)
    • データ更新時にスナップショットを作成することで、障害時の実データのロールバックが可能に
    • データコピー時には実体への参照のみを作成することで、高速な処理が可能に(データ更新時に実体を作成)
  • 透過圧縮
    • ディスクに書き込む・読み込む際にファイルシステムのサポートによってデータを圧縮・解凍する(LZO、ZLIB)
    • 圧縮・解凍のためにCPU使用率が上がるが、書き込む量を減らすことで、ディスクスペースの利用効率だけでなく、ディスクI/Oの効率を上げる効果がある
  • LVMのようなボリューム管理機能
    • 複数デバイスを一つのボリュームとして扱うことができ、balance機能によって自動的に書き込み領域を各デバイスに分散することで性能向上が可能に
    • オンラインでのデバイスの追加・削除が可能に

www.slideshare.net

ハードリンクとシンボリックリンクの違い

  • ハードリンクは、オリジナルファイルと同じi-node番号を持つファイル。i-node番号が同じファイルのため、オリジナルファイルをどのパスに移動しても、ハードリンクはパスに関係無くオリジナルファイルへ追従することができる。ただし、ハードリンクはオリジナルファイルと別のファイルシステム上には作成できない。i-node番号体系が異なるためである。
  • i-nodeには参照カウントがあり、ハードリンクが作成されるとオリジナルファイルの参照カウントがインクリメントされる。ハードリンクが削除されると参照カウントはデクリメントされる。参照カウントが0になった時点で実体のブロックは解放可能となる。
  • シンボリックリンクの実体はオリジナルファイルへのパスである。従って、シンボリックリンクはハードリンクと別のファイルシステム上にも作成できる。ただし、オリジナルファイルを削除したことに気が付かない。

  • ディレクトリエントリは、ファイル名とi-node番号を対としたリストを持つ。従って、i-nodeにファイル名の情報は無い。".“は自分自身のi-node番号を指すため、ディレクトリ作成時に参照カウントは2となる。”..“は親ディレクトリへのi-node番号を指すため階層構造をルート方向へ追跡することができる。

chroot配下でchroot外へディレクトリへリンクする場合

ディレクトリ自体のハードリンクに関しての覚え書き - Qiita

*1:H-TreeのHはHashで、Hash値をキーに用いることで、B-Treeよりも高速な検索になるらしい。HashなのでO(1)だが、Treeなので階層別にHashが必要になるのと、リーフは衝突に備えてリストにする必要がある

*2:物理的には並列ではなく並行なはずだが、RAID0を使っていたり、LVMで複数のPhysical Volumeの上にLogical Volumeを作成していたりした場合は、より効果があるのかもしれない

FeliCa/Suicaについて調べた

SuicaFeliCa)がiPhone7とApple Watch series 2に搭載されることになったので、この機会にいろいろ調べてみた。まだ、憶測の域をこえないところはある。

Sony Japan | FeliCa | FeliCaとは | FeliCaって何?

How to protect from fraud?

  • 中央サーバでトランザクションを一元管理するしかないが、Suicaのような高速な応答性を求められるアプリケーションで、それをどのように実現するか?
  • 改札機器端末 → 駅 → 中央サーバ の階層型分散システム
    • 各階層でトランザクションのキャッシュを持つことで、中央サーバが応答不能になっても即座にサービス停止とはならない
      → 改札機器端末は各アカウントの3日分のトランザクションを蓄えられる容量があるらしい
    • 上階層へのトランザクションの更新処理は、キューに溜める非同期型になっているため、入場時の改札機器端末の応答速度は、カードと改札機器端末の間の処理にかかる時間に縮められる
    • 改札端末には各駅までの運賃がキャッシュされており、運賃計算時に即座に反応できるようになっている
    • 出場時の改札機器端末の応答速度を速めるため、入場時にある程度前もって計算してカードに保存しておく(e.g. 入場駅から定期区間の始めまでの運賃)

How to avoid data break?

  • FelicaFeliCa OS)はファイルシステム上に更新中のデータを二面持ちしているため、更新処理が完了しなかった場合(更新処理中に物理的にNFCの範囲外に離れてしまった場合)でも、元データに復旧する事ができる

  • カード側と改札機器端末側(リーダ/ライタ側)でデータの不整合が発生した場合(カード側で更新処理が完了したが改札機器端末側にそれを伝えられなかった場合)でも、中央サーバ側で不整合の状態を記録しておき、次回アクセス時にカード側の整合状態を中央サーバに伝達して不整合を修復する

http://www.sice.jp/ia-j/papers/jitk6-20050722-1305.pdf
http://www.sice.jp/ia-j/papers/jitk6-20050722-1305.pdf

Linuxのブートシーケンスの基礎まとめ

ファームウェアBIOS or UEFI*1)が

  • マザーボードのROMからメモリにロードされて実行開始し、ハードウェアをスキャン(POST - Power-On Self Test というハードウェアの自己診断を)する
  • [BIOSの場合] プライマリHDDのMBR(先頭のセクタ(512バイト))を見る
  • [UEFIの場合] プライマリHDDのGPTヘッダ(LBA1 or 最終セクタ)を見る

https://upload.wikimedia.org/wikipedia/ja/c/cc/GUID_Partition_Table.png

GPTとMBRはどのように違うのか? - かーねる・う゛いえむにっき

BIOS/UEFI/MBR/GPT

  • MBRでは232≒2.2TBまでのディスクしか扱えない
  • GPTでは264≒8.5ZBまでのディスクを扱うことができる

  • BIOSIntel CPUのリアルモード(16bitモード)でないと起動できないため、1MBまでのメモリしか利用できない

  • UEFIはプロセッサ非依存のため、32bitプロセッサなら32bit命令が、64bitプロセッサなら64bit命令が使えるため、潤沢なメモリを利用できる
  • BIOSはGPTに対応していないため、GPTに対応したUEFIを使う

  • MBRパーティションテーブルには四つのパーティション構成情報が書き込める (四つ以上は、四つ目を拡張パーティションテーブルとして対応)

  • MBRの最後の2バイトは0xaa55というMBR signatureが書き込まれている
$ sudo hexdump -s 500 -n 12 /dev/sda
00001f4 0000 0000 0000 0000 0000 aa55          
0000200
  • 一方、GPTは128までパーティションが管理でき、物理や論理といった煩雑な管理は必要ない

  • BIOSのようにGPTを認識しないファームウェアにはMBRを見せることができる

  • 末尾にもGPTヘッダがあり冗長構成となっている

2TB以上のディスクは

  • MBRでは扱うことができない and fdiskコマンドでは扱うことができない
  • GPTを使う必要がある and ( parted or gdisk コマンドを使う必要がある )

  • 追加した2TB以上のディスクにパーティションラベルを付ける

# parted /dev/sdd
(parted) mklabel gpt

ブートローダ(GRUB or LILO)が

GRUB2

GNU GRUB - Wikipedia

initrd/initramfs

  • initrdはブロックデバイスgzip圧縮したもの
  • initramfsはファイルシステムをcpioでアーカイブしたものをgzip圧縮したもの
  • initrdにカーネルモジュールを追加しようとするとマウントが必要(etc.)
     → 扱いにくいのでObsolete
     → 現在では一般的にinitramfsを使う
  • initrdに含まれるファイルにアクセスするためにループバックマウントされる

initrd/initramfsの必要性

vmlinuz/vmlinux/bzImage/zImage

  • bootパーティションには、vmlinuzと呼ばれる、カーネルイメージを含むファイルが置かれている
  • vmlinuzは、カーネルイメージ(vmlinux)をgzip圧縮したものと、圧縮されたカーネルイメージを伸張し展開するコードをそれ自身に伴った形式ものである
  • このファイル形式をbzImageという
  • なお、zImageでは512KB以下のイメージしか扱えない

uImage

  • U-Boot用のカーネルイメージのファイル形式
  • U-Bootは、主に組み込み用途で使われるブートローダで、ネットワークブート(PXEクライアント)の機能を持つなど、高機能版のブートローダGRUBでネットワークブートをする場合は、おそらくNIC側のPXEクライアント機能を使う必要がある)

System.map

  • System.mapは、vmlinuxに対するnmコマンドの実行結果であり、カーネルに関するメモリアドレスと型、シンボルの対応テーブルを表す
  • nmは、実行形式のファイルやライブラリなどからシンボルテーブルを取得するためのコマンド
  • ブートに必要なデータではなく、Kernel PanicやOopsが発生した際のデバッグに使われる(実行時のメモリアドレスからシンボルを特定する)

kexec

  • カーネルを入れ替えるためにリブートする際、これらのブートシーケンスを行わず、ブートローダカーネルに制御を移した段階から始めることができるため、リブート時間を短くすることができる

カーネル

  • ハードウェアリソースに対応する初期設定やデバイスドライバの初期設定を行う
  • idleプロセス(PID=0)を起動する
  • initrd/initramfsを展開して、初期ルートファイルシステムをramfsとしてマウントする
  • [initrdの場合] /linuxrcを、一時的なinitプロセス(PID=1)として起動する
  • [initramfsの場合] /initを、一時的なinitプロセス(PID=1)として起動する
  • 初期ルートファイルシステムに置かれているカーネルモジュールをロードして、様々なファイルシステムでフォーマットされているパーティションを認識する
  • 初期ルートファイルシステムから、読み込み専用でマウントしたルートファイルシステムへマウントポイントを移す
  • [initrdの場合] 一時的なinitプロセスの終了後に、/sbin/initを実行して、initプロセス(PID=0)を起動する
  • [initramfsの場合] /initが、exec /sbin/initを実行して、initプロセス(PID=0)を起動する(execは現在のプロセスを別のプロセスで置き換える)

Systemd

  • /sbin/initは、現在systemdに置き換えが進んでおり、単に/sbin/initがsystemdへのシンボリックリンクになっているLinuxディストリビューションも存在する
  • systemdは、サービスの起動を並列に実行することによる起動処理の高速化、cronやxinetd(リソース効率化のため通信を検出した際にそのポートに対応するプロセスを起動するスーパーデーモン)に対応する機能の集約、cgroupによるリソース制御を用いたプロセスの優先度管理、などを行う

initプロセスが

  • /etc/inittabに書かれている通りrunlevelを設定し、該当する/etc/rc.d/rcXを実行する
  • スクリプトを実行する際は、forkによってinitプロセスがそのスクリプトを実行するプロセスの親プロセスとなる
  • 読み込み専用でマウントされたルートファイルシステムに対してfsckを実行*2し、実行後に読み書き可能で再マウントする
  • initプロセスが、/etc/fstabに書かれている通り各パーティションをマウントする

fstab - ArchWiki

runlevel

  • runlevelの定義はOSに依存するが、0:停止、1:シングルユーザ、2:マルチユーザ(ネットワーク無、Xディスプレイ無)、3:マルチユーザ(ネットワーク有、Xディスプレイ無)、5:マルチユーザ(ネットワーク有、Xディスプレイ有)、6:リブート、のパターンが多い
  • Sで始まるファイルは起動用スクリプト(S=Start)であり、Kで始まるファイルは停止用スクリプト(K=Kill)になる

*1:Unified Extensible Firmware Interface

*2:grubの設定ファイルでkernel(linux)コマンドに対して読み込み専用のモード(ro)が指定されているのはfsckを実行するため

AVL木の更新状況が見たい

AVL木は平衡二分木の一つで、ノードの追加・削除のたびに木の再構成を行い、検索時の計算時間を最小に抑えるようなデータ構造を維持する。木の再構成を行わない場合、最悪の場合には木の片側のみを使ってしまい検索時にO(n)の時間がかかってしまうが、再構成を行うことにより木を厳密に平衡に保つためO(logn)の時間で検索できる。更新・削除にも時間がかかるが、その分検索の時間を速くすることを目的としている。

実装を進めるにあたって、更新時の回転操作を正しく理解するためにも、木構造そのものを見ることが出来る方が分かり易いだろう、ということで、まず木構造デバッグできるよう実装した。 ノードは双方向の連結リストになっているが、可視化する場合には幅優先探索によって同じ階層のノードを取得し、それをヒープ構造に入れることにした。ある階層の全てのノードがNULLになるまで、あるノードがNULLであっても子ノードの取得を続けるようにしているため、こうしておくと、あるノードの親がNULLかどうかも確認しやすい。見やすさのため、親がNULLの場合は何も出力が行わないようにする。NULLノードは[]で示している。

数字の隣はラベルで、AVL木において重要な役割を持つ。LEFT、EQUAL、RIGHT、はそれぞれ左部分木が深いか、平衡か、右部分木が深いか、が分かるようになっている。

Thanks to :

http://dopal.cs.uec.ac.jp/okamotoy/lect/2005/DSA/avl.pdf

  • 挿入を実施しながら木構造や回転を確認(モバイルだと崩れますが...)
$ java AVLTree
Please input the value for root node. : 8
('q' for quit, 'p' for print, 's' for search.)
Please input. : p
 8E---| 
 []  [] 

Please input. : 3
Please input. : 14
Please input. : p
 8E-------|     
 3E---| 14E---| 
 []  []  []  [] 

Please input. : 2
Please input. : 6
Please input. : p
 8L---------------|             
 3E-------|     14E-------|     
 2E---|  6E---|  []      []     
 []  []  []  []                 

Please input. : 12
Please input. : 15
Please input. : p
 8E---------------|             
 3E-------|     14E-------|     
 2E---|  6E---| 12E---| 15E---| 
 []  []  []  []  []  []  []  [] 

Please input. : 1
Please input. : 4
Please input. : p
 8L-------------------------------|                             
 3E---------------|             14E---------------|             
 2L-------|      6L-------|     12E-------|     15E-------|     
 1E---|  []      4E---|  []      []      []      []      []     
 []  []          []  []                                         

Please input. : 5
Rotate left at 6!
Please input. : p
 8L-------------------------------|                             
 3E---------------|             14E---------------|             
 2L-------|      5E-------|     12E-------|     15E-------|     
 1E---|  []      4E---|  6E---|  []      []      []      []     
 []  []          []  []  []  []                                 

Please input. : 7
Rotate left at 8!
Please input. : p
 5E-------------------------------|                             
 3L---------------|              8E---------------|             
 2L-------|      4E-------|      6R-------|     14E-------|     
 1E---|  []      []      []      []      7E---| 12E---| 15E---| 
 []  []                                  []  []  []  []  []  [] 

Please input. : 0
Rotate left at 2!
Please input. : p
 5E-------------------------------|                             
 3L---------------|              8E---------------|             
 1E-------|      4E-------|      6R-------|     14E-------|     
 0E---|  2E---|  []      []      []      7E---| 12E---| 15E---| 
 []  []  []  []                          []  []  []  []  []  [] 

Please input. : 20
Please input. : p
 5R---------------------------------------------------------------|                                                             
 3L-------------------------------|                              8R-------------------------------|                             
 1E---------------|              4E---------------|              6R---------------|             14R---------------|             
 0E-------|      2E-------|      []              []              []              7E-------|     12E-------|     15R-------|     
 []      []      []      []                                                      []      []      []      []      []     20E---| 
                                                                                                                         []  [] 

Please input. : 22
Rotate right at 15!
Please input. : p
 5R---------------------------------------------------------------|                                                             
 3L-------------------------------|                              8R-------------------------------|                             
 1E---------------|              4E---------------|              6R---------------|             14R---------------|             
 0E-------|      2E-------|      []              []              []              7E-------|     12E-------|     20E-------|     
 []      []      []      []                                                      []      []      []      []     15E---| 22E---| 
                                                                                                                 []  []  []  [] 

Please input. : q
$ 
  • のべ16ノードを挿入した木を100回作成(検索の確認は無し(0回))

f:id:nishidy:20160905232657g:plain

  • のべ10,000,000ノードを挿入した木を作成し、10回検索を実施して各時間を測定
  • 計算時間はO(logn)、つまり対数をeとするとlog(10,000,000)=16.118で、これはO(n)と比べると、60万倍以上早い(つまり、数十〜数百msかかる可能性がある)
$ java AVLTree 10000000 10
Found node 7443458 in 11830 ns.
Found node 1542990 in 7199 ns.
Found node 9059491 in 5348 ns.
Found node 2189518 in 5501 ns.
Found node 5773482 in 3459 ns.
Found node 7512803 in 4832 ns.
Found node 7103487 in 6813 ns.
Found node 5575799 in 5398 ns.
Found node 5292306 in 84161 ns.
Found node 8909173 in 20869 ns.
$ 

実装はこちら。削除は複雑なため未実装です。

AVLTree with debugging the tree in Java · GitHub

Sortアルゴリズムの消費メモリについて(続)

ソートにおいて、ソート対象の配列に対するポインタを操作すれば、各関数の中でソート対象の配列が持つ要素に対するメモリを確保する必要が無くなる。もし、ソート対象の配列の要素の型がポインタよりも小さいサイズであれば、その要素に対するメモリを確保した方が良いが、例えばソート対象の配列の要素が構造体である場合は、その要素に対するメモリ量が大きいので、ダブルポインタでポインタをソート対象として扱うべきである。ポインタのサイズはプラットフォームに依存するので、sizeof()で確認する。

ダブルポインタを用いてポインタに対してメモリを確保するソート(sort())と、データの型に対してメモリを確保するソート(_sort())、それからライブラリのソート(qsort())、を比較してみた。ソート処理全体で確保した総メモリ量と、mallocを呼んだ回数をカウントしている。なお、構造体のソート対象のキー(age)以外は、参照もしないので、初期化すらしていない。ダブルポインタを用いる方がメモリ量が小さいし速い。ただ、やはりライブラリのソートの方がかなり速い。

なお、前回のプログラムでQuick sortのmalloc回数が多かったのは、ソート対象の配列数が1になった場合にreturnしていないため。

$ ./structsort 5000000
Size of Data struct : 68
Size of a pointer : 8
(Size of short: 2)
(Size of int: 4)
(Size of long: 8)

Quick sort (double pointer): 5.22 sec.
1045MB,3385634
Good. Sorted.

Quick sort : 6.48 sec.
8887MB,3385634
Good. Sorted.

Quick sort (library function) : 3.20 sec.
Good. Sorted.

実装はこちら Sort function optimized with double pointer · GitHub