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

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

文字列のリストとその出現数をカウントして多い方から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

*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

  • MBR/GPTにインストールされているブートローダをメモリにロードして制御を移す

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

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/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

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

カーネル

  • initrd/initramfsを展開して、初期ルートファイルシステムをramfsとしてマウントする
  • [initrdの場合] /linuxrcを、一時的なinitプロセスとして起動する
  • [initramfsの場合] /initを、一時的なinitプロセスとして起動する
  • 初期ルートファイルシステムに置かれているカーネルモジュールをロードして、様々なファイルシステムでフォーマットされているパーティションを認識する
  • 初期ルートファイルシステムから、読み込み専用でマウントしたルートファイルシステムへマウントポイントを移す
  • [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

いかなる算術演算子も使わずに加算を実現する

という問題を解く。

答えは、ビット演算子をたくみに使って加算を実現する。 つまり、ビット演算子は算術演算子には含まれないので、使っても良い。

具体的には、XORによって各位の加算を実現し、ANDと左シフト演算子によって繰り上げを実現する。 繰り上げがなくなった時点で(ゼロになった時点で)、計算は終了する。

以下のように、デバッグしながら実行してみる。

#include <stdio.h>
#define BITS 32

void bit(int n){
        int i;
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int bitplus(int a, int b){
        bit(a); bit(b); printf("\n");
        if(b==0)
                return a;
        return bitplus( a^b, (a&b)<<1 );
}

int main(int argc, char* argv[])
{
        int a = atoi(argv[1]);
        int b = atoi(argv[2]);
        bit(a); bit(b); printf("\n");
        printf("Ans = %d\n\n", bitplus( a^b, (a&b)<<1 ));
        return 0;
}
$ ./bitplus 3 5
00000000000000000000000000000011
00000000000000000000000000000101

00000000000000000000000000000110
00000000000000000000000000000010

00000000000000000000000000000100
00000000000000000000000000000100

00000000000000000000000000000000
00000000000000000000000000001000

00000000000000000000000000001000
00000000000000000000000000000000

Ans = 8

$ ./bitplus 65535 65536
00000000000000001111111111111111
00000000000000010000000000000000

00000000000000011111111111111111
00000000000000000000000000000000

Ans = 131071

$ ./bitplus 65535 65535
00000000000000001111111111111111
00000000000000001111111111111111

00000000000000000000000000000000
00000000000000011111111111111110

00000000000000011111111111111110
00000000000000000000000000000000

Ans = 131070

$ python
Python 3.4.3 (default, Oct 24 2015, 14:51:44) 
[GCC 4.2.1 Compatible Apple LLVM 6.1.0 (clang-602.0.53)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> int("10101010",2)
170
>>> int("01010101",2)
85
>>> quit()

$ ./bitplus 170 85
00000000000000000000000010101010
00000000000000000000000001010101

00000000000000000000000011111111
00000000000000000000000000000000

Ans = 255

$ ./bitplus 171 85
00000000000000000000000010101011
00000000000000000000000001010101

00000000000000000000000011111110
00000000000000000000000000000010

00000000000000000000000011111100
00000000000000000000000000000100

00000000000000000000000011111000
00000000000000000000000000001000

00000000000000000000000011110000
00000000000000000000000000010000

00000000000000000000000011100000
00000000000000000000000000100000

00000000000000000000000011000000
00000000000000000000000001000000

00000000000000000000000010000000
00000000000000000000000010000000

00000000000000000000000000000000
00000000000000000000000100000000

00000000000000000000000100000000
00000000000000000000000000000000

Ans = 256

右シフト演算

負の値を右シフトした場合、符号ビットが立っているので、1で埋められる。

...
        int k = -65535;
        bit(k);
        bit(k>>=10);
        bit(k<<=10);
...
11111111111111110000000000000001
11111111111111111111111111000000
11111111111111110000000000000000

なお、シフト対象となる左辺値の型のサイズより大きい値でシフトしようとすると、以下のようにMacApple LLVM version 7.0.2 (clang-700.1.81))ではwarningが出るが実行はできる。

...
        bit(k>>=64);
...
$ gcc bitplus.c 
bitplus.c:87:14: warning: shift count >= width of type [-Wshift-count-overflow]
        bit(k>>=64);
             ^  ~~
1 warning generated.

ただ、結果としての値は、シフト演算を行う前の値になっていた。

11111111111111110000000000000001

Cではこのようなシフト演算は規定外なので、何が起こるかはプラットフォームに依存する。

Goだと、以下の記事の通り、-1になる。

Goでは、nビットシフトは1ビットシフトをn回行ったのと同じ(CやJavaは違う) - Qiita

$ cat bit.go 
package main

import (
    "fmt"
)

func main() {
    var a int32 = -65535
    fmt.Printf("%b\n", a>>64)
}
$ go run bit.go 
-1

浮動小数点数のビット表現

IEEE 754 - Wikipedia

浮動小数点のビット表現を見てみる。float型の変数からアドレスを取得し、それをint型のポインタとしてキャストしてから、その値を取り出す。

#include <stdio.h>
#define BITS 32

void bitf(float f){
        int i;
        int n = *((int *)&f);
        for(i=0;i<BITS;i++)
                printf("%d", (n >> (BITS-1-i)) & 1);
        printf("\n");
}

int main()
{
        bitf(-10.5);
        bitf(10.5);
        return 0;
}
$ ./floatbit 
11000001001010000000000000000000
01000001001010000000000000000000

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Float_example.svg/590px-Float_example.svg.png

符号部は、負数で1、正数で0。 仮数部と指数部の算出は以下の通り。 算出した指数部には規定通り127のバイアスを加える。

10.5 * 2^0
= 5.25 * 2^1
= 2.625 * 2^2
= 1.3125 * 2^3
= (1+0.3125) * 2^3

0.3125 * 2 = 0.625 (0)
0.625 * 2 = 1.25 (1)
0.25 * 2 = 0.5 (0)
0.5 * 2 = 1.0 (1)

指数部は3+127=130で10000010仮数部は2ビット目と4ビット目が立つので0101、となるので、-10は1_10000010_01010000...となる。