ryo’s blog

日々学んだことをまとめています.

第8章 例外的な制御フロー

8章について
この章では、制御フローについて学んでいきます。
例外的な制御フローについて学ぶことで、アプリケーションがどのようにオペレーティング・システムと相互作用するかを理解しやすくなります。
また try, catch ,throw などの構文が理解しやすくなるそうです。
以下まとめです。


例外的な制御フローって?

制御転送 : プロセッサに電源を入れてから切るまでの、プログラム・カウンタの遷移のこと。
制御フロー : 連続する制御転送のこと。

制御フローに対して突発的な変更を行うことで、さまざまな状況に反応する。
この突発的な変更のことを例外的な制御フローとよぶ。

例外

例外ハンドラ

プロセッサはイベントの発生を検出すると、例外テーブルとよばれるジャンプ・テーブルを介して、例外ハンドラをよぶ。
例外ハンドラが処理を終了すると、種類に応じて以下のどれかが起きる。

  1. 制御を現在の命令に戻す。
  2. 例外が起きなければ次に実行されていたはずの命令に戻す。
  3. ブログラムを中断させる。


例外のそれぞれには、例外番号が割り当てられている。
システムの起動時に、オペレーティング・システムは例外テーブルを確保し初期化する。
例外番号はその例外テーブルのインデクスとして使われる。

例外の4つのクラス

  1. 割り込み : ハードウェア割り込みに対する例外ハンドラは、割り込みハンドラとよばれる。
  2. トラップ : 命令実行の結果として発生する意図的な例外。read, fork, exitなどのシステムコールのこと。
  3. フォールト : エラーを訂正できる場合は、命令に制御を戻すが訂正できない場合は、abort ルーチンに制御を移す。
  4. アボート : アボートは回復不能なエラーによって起きる。プログラムを強制終了する。


Linux/x86-64 システムにおける例外

x86-64 では 最大で 256 個までのタイプの例外がある。

  • 除算エラー : ゼロ除算か、除算結果がオーバーフローした場合に発生する。

  • 一般保護フォールト : プログラムが仮想メモリ上の未定義領域を参照した場合や、読み出し専用のセグメントに書き込もうとした場合に起きる。

  • ページ・フォールト : ディスク上の適切な仮想メモリのページを物理メモリのベージにマップし、その後にファールディング命令を再開する。

  • マシン・チェック : フォールティング命令の実行中に検出された致命的なハードウェア・エラーの結果として発生する。


プロセス

例外はプロセスという機能を実現するための基本的な仕組みである。
システム内の各プログラムは、いずれかのプロセスのコンテクストで実行される。

プログラムを実行するたびに、シェルは新しいプロセスを作りその新しいプロセスのコンテクストで実行可能ファイルを実行する。


3つのプロセスを実行する場合

制御フローは 1つしかないがプロセス 1つ 1つに分割され、3つの論理フローとなる。
プロセスはプロセッサを順番に使うので、他のプロセスの実行中の間一時停止している。


平行と並列

倫理フローは、例外ハンドラ、プロセス、シグナル・ハンドラ、スレッドなど様々な形で現れる。

マルチタスク : 他のプロセスと交代しながら実行される場合。
タイム・スライス : 一つのプロセスがフローの一部を連続して実行する期間のこと。

平行フロー : 2 つのフローが時間的にオーバーラップして実行されるとき。
並列フロー : 2つのフローが、異なるプロセッサ・コアあるいはコンピュータ上で実行されている場合。


コンテクスト・スイッチ

例外的制御フローを利用した仕組みのことで、マルチタスクを実装するのに使う。
カーネルはプロセスごとにコンテクストを管理している。

コンテクスト : 一時的に停止されたプロセスを再開するためにカーネルが必要とする状態のこと。

スケジューリング : プロセスが実行されているいずれかの時点で、カーネルは現在実行中のプロセスを一時停止し、以前停止したプロセスを再開すること。


システム・コールにおけるエラー・ハンドリング

エラー処理は省略されがちだが、必ず行うべき。
しかしそのまま書くとコードが膨らんでしまうので、ラッパー関数を作成してエラー処理を行う。

// これを毎回書くとコードが膨む
if ((pid = fork()) < 0) {
    fprintf(stderr, "Error: fork failed\n");
    exit(0);
}

pid = xfork(); // 失敗した場合にラッパー関数がエラー処理をする


プロセスの生成と終了

プロセスは 3つの状態のどれかとなる。

  1. 実行中状態 : 実行中、あるいは実行待ちで、やがてスケジュールされる。
  2. 停止状態 : 実行が停止しており、スケジュールされることがない状態。
  3. 終了状態 : プロセスが永久に停止した状態。


プロセス生成

fork 関数によって子プロセスを生成できる。
子プロセスは親プロセスが持つユーザ・レベルの仮想アドレス空間のコピーを持つ。
コード・セグメント、データ・セグメント、ヒープ、共有ライブラリ、ユーザ・スタックがコピーされる。


子プロセスの回収

終了してるが、回収されていないプロセスをゾンビという。
親プロセスが終了すると、孤児となった子プロセスを init プロセスが引き取るようカーネルが処理を行う。
長く動き続けるプログラムの場合、システムのメモリ資源を消費したままなので、wait関数でゾンビを回収する。


プログラムとプロセスの違い

プログラム : コードとデータの集まり。
プロセス : 実行中のプログラムのプログラムの実体として具体的に存在するもの。

プロセス・グループ

ls | sort というコマンドを実行した場合、この 2つのプロセスは同じプロセス・グループに属している。

Ctrl+C を入力すると、プロセス・グループに属するすべてのプロセスに対して、SIGINT を送信する。

# 一度のSIGINTで終了する
cat | cat | cat


シグナル

シグナル : 小さなメッセージのようなもので、何らかのイベントがシステム内で発生したことをプロセスに通知するもの。

それぞれのシグナルは何らかのシステム・イベントに対応している。
またシグナル・ハンドラを用いて、シグナルをキャッチできる。

ペンディング・シグナル

送信されたもののまだ受信されていないシグナルのこと。
あるシグナル番号に対して一つしか持たないので、それ以降送られてきた場合は捨てられる。

ペンディング・シグナルの集合を pending というビット・ベクタに保持している。
ブロックされているシグナルの集合は blocked というビット・ベクタに保持している。


シグナル・ハンドラの書き方

  1. ハンドラはフラグをセットするだけにするなどシンプルにする。

  2. 非同期シグナル・セーフ関数だけをよぶ。

  3. errno が書き換わらないようにする。

     void sig_handler(int sig)
     {
         int tmp = errno;
         sleep(1); // errnoが書き換わる
         errno = tmp; // もとに戻す
     }
    
  4. データ構造へのアクセスを保護するためシグナルをブロックする。

     // keyの書き換え中に割り込みが発生するとvalueが変えられない
     struct t_dict {
         char *key;
         char *value;
     };
    
  5. グローバル変数はvolatileで宣言して、変数の値をキャッシュさせないようにする。

  6. sig_atomic_tで宣言して、 読み書きが1 命令で実装されているためアトミックであることを保証する。


非局所的ジャンプ

C では非局所的ジャンプというユーザ・レベルの例外的制御フローが提供されている。
ある関数から他の関数に直接飛び込むことができる、setjmpとlongjmpがある。
try catch throw の仕組みに似ている。

try : 例外を監視するブロックを宣言する。
catch : try ブロックで例外が発生した場合、ブロックを実行する。setjmp 関数に似ている。
throw : 例外を発生させる。longjmp 関数に似ている。


感想

以前簡易的なbashの再実装をしたことがあるので、概念的には知っていることがたくさんありました。
ですがその時に知らなかったような仕組みや、より安全なコードの書き方など学ぶことができたので良かったです。
C言語でもジャンプを利用して try catch のような仕組みができるようなので、試してみようと思います。


第7章 リンク

7章について
この章では、そもそもリンクとはなんだろう?ということから始まり、静的リンクと動的リンクの違いや効率化の手法について説明されていました。
リンカが行っている動作について学ぶことで、リンクエラーを避けることができ、大きなプログラムを作成するときに便利になります。
以下まとめです。


リンクとは?

データを一つのファイルにまとめ上げ、メモリ上にコピーし実行できるようにすること。
コンパイル時のほか、ロード時や実行時にもプログラムによって行うことができる。

(例) main.o, func.o, lib.a など必要なものをまとめて a.out を作成する流れのこと。


静的リンク

静的リンカは再配置可能オブジェクト・ファイルおよびコマンド・ライン引数を入力として受け取り、ロードして動かすことのできるリンク済みの実行可能オブジェクト・ファイルを生成する。

実行可能ファイルを生成するためにシンボル解決と再配置の2つの作業を行う。

  • シンボル解決 : オブジェクト・ファイルはシンボルを定義・参照しているので、それを元に適切な処理をする。
  • 再配置 : 各シンボルの定義にメモリ位置を対応づけ、そのシンボルへの参照が対応づけたメモリ位置を指すようにする。


オブジェクト・ファイル

3種類存在する。

  • 再配置可能 : コンパイル時に他の再配置可能オブジェクト・ファイルと統合し、実行可能オブジェクト・ファイルを生成可能。
  • 実行可能 : 直接メモリにコピーし実行可能。
  • 共有 : ロード時もしくは実行時にメモリに関して読み込み動的にリンクできる。


再配置可能オブジェクト・ファイル

主要なセクション

  • .text: 機械語
  • .data: 読み書き可能なデータ(初期化されているグローバルおよび静的変数)
  • .rodata: リードオンリーのデータ
  • .bss: 初期値が 0 のデータ (初期化されていないグローバルおよび静的変数)

-g オプション付きで存在するセクション

  • .debug: ローカル変数および型のエントリを含む
  • .line: ソースの行番号と機械語との対応関係を持つ

-g オプションをつけずにコンパイルするとステップ実行ができなくなる原因は、このセクションを見ると理解できますね。


シンボル

再配置可能オブジェクト・モジュールには、シンボルに関する情報を含むシンボル・テーブルが存在する。

  • 大域シンボル : 他のモジュールから参照可能な(静的でない関数およびグローバル変数)

  • 外部的な大域シンボル : 他のモジュールで定義されている

  • 局所シンボル : そのモジュールでのみ定義・参照される (静的な関数および static 属性付きで定義されたグローバル変数)


シンボル解決

シンボルへの参照を、シンボル・テーブル内にあるシンボルの定義から一つ選び対応づけることで解決する。

  • 局所シンボルの場合 : 局所シンボルの定義はモジュールごとに一つしか存在しないので簡単。

  • 大域シンボルの場合 : 現在のモジュール内で定義されていないシンボルを見つけたとき、そのモジュールを外部へ探しに行く。リンカが参照されているシンボルの定義を見つけられなかったらエラーとなる。


strongシンボル: 関数および初期化済のグローバル変数
weakシンボル: 初期化されていないグローバル変数

以下のルールをもとに解決する。

  • 同名の strong シンボルが複数存在してはならない。
  • 同名の strong シンボルと weak シンボルが存在する場合、strong シンボルを選択する。
  • 同名の weak シンボルが複数存在する場合、任意の一つを選ぶ。

解決できない場合はエラーが発生する。

二重定義

// foo.c
int x = 10;

// bar.c
int x; 宣言だけならエラーにならない

// hoge.c 
int x = 1; // strongシンボルの二重定義でエラーになる。


グローバル変数によるバグ

// foo.c
int y = 1000;
int x = 1000; // foo.c内ではint

// bar.c
double x;

void f() {
    x = -0.0; // bar.c内ではxはdoubleとして扱われる
}

bar.c の x = -0.0 によって x と y のメモリ領域が倍精度浮動小数点数点表現された負のゼロで上書きされてしまう。

そのためx = 0x0 y = 0x80000000 という結果になる。


マングリング

C++ などではソース・コード内に同名の引数が異なるメソッドの定義を許している。 同名の関数や変数を識別するために名前をエンコードすることをマングリングとよぶ。

マングリングの例

int foo(int) {}
// _Z3fooi 

int foo(int, int, float) {}
// _Z3fooiif

例では、引数の頭文字を付加していますが、実際にはもう少し複雑な名前付けを行っています。


ライブラリが必要な理由

Pascal では標準関数が少ないため、コンパイラが関数の呼び出しを認識して適切なコードを直接生成する。

しかし、C言語など標準関数が多いものに関しては、そのやり方は向いていない。
なぜなら関数の追加や削除、修正するたびに、コンパイラのバージョンを新しくする必要があるためである。

そのため静的ライブラリ .a を活用する。
またライブラリを指定する際の原則はコマンド・ラインの末尾に置くこと。

(例)foo.cが lib1.a, lib3.a を呼び出し、それが lib2.a を呼び出す場合

gcc foo.c lib1.a lib3.a lib2.a とする必要がある。


静的ライブラリの欠点

定期的に保守、更新する必要がある。
またライブラリの更新するたびに、再リンクする必要がある。


再配置

リンカがシンボル解決ステップを完了すると、コード内の各シンボルへの参照にただ一つの定義が対応づけられる。

セクションおよびシンボル定義を再配置 : 同じ型のすべてのセクションを統合し、一つの修正セクションにする。

セクション内のシンボルへの参照を再配置 : コード及びデータ・セクション内のシンボルへの参照を修正し、正しい実行時アドレスを指すようにする。

シンボルへの参照を再配置する : 相対アドレスまたは絶対アドレスを用いて重複する再配置する。


共有ライブラリって?

静的ライブラリの欠点を補うために生まれた。
実行時、もしくはロード時に任意のメモリ・アドレスに読み込み、メモリ上のプログラムとリンクすることができる。

複数プロセスが同じライブラリのコードをメモリ上で共有することで資源を節約できる。

.so 拡張子によって識別される。


共有ライブラリの実用

  • ソフトウェアの配布 : ユーザがアプリケーションを実行すると、新しい共有ライブラリが自動的にリンクおよびロードされる。
  • 高性能ウェブ・サーバの構築 : 口座残高、バナー広告などの動的コンテンツ。


共有ライブラリの効率化

共有ライブラリのメモリ資源節約のため、あらかじめアドレス空間内のある領域を各共有ライブラリに割り当てておく。
しかし、ライブラリを使用しない場合でも領域を確保するため空間効率が悪い。
また管理が難しく、割り当てた領域が重ならないように保証しなければならない。

これらの問題を避けるため、メモリ上のどこにでもロードできる形式(PIC)にコンパイルする。


ポジション非依存コード(PIC)

再配置なしにロード可能なコードのこと。

PIC としてコンパイルされた共有ライブラリは任意の位置にロード可能であり、実行時に複数のプロセスで共有できる。
PIC は PLT のように相対アドレッシングのみで構成されていていて、再配置可能なコード。


PIC関数呼び出し

コンパイラには関数の実行時アドレスを予測する方法がない。
通常の方法では、参照の再配置する再配置レコードを生成し、プログラムがロードされたときに動的リンカが解決できるようにする。

GNU では遅延束縛という技術を用いているこの問題を解決している。


遅延束縛

関数のアドレスの解決をそれが実際に呼び出されるまで遅延することで、動的リンカはロード時に不要な再配置を避ける。

関数が最初に呼び出されるときにはコストがかかるが、その後の各呼び出しは低コスト。


言語束縛

多くのライブラリは、C言語C++ などのシステムプログラミング言語で書かれているが他の言語でも使えるようにしたもの。
ライブラリそのものを複数の言語で作成するよりも効率的となる。

またはシステム言語と同じ機能を高級言語で記述できないためという場合もある。


インターポジショニング

共有ライブラリの関数への呼び出しに介入し、代わりに独自のコードを実行できるようにすること。
特定のライブラリ関数のラッパー関数を作成して、全く別の実装に置き換えたりする。
コンパイル時やリンク時、実行時に行うことができる。


感想

オブジェクト・ファイルやライブラリをまとめる上で、内部的にどのように動作しているのか知ることができました。
シンプルに見えて、複雑なプロセスを経ていることが学べて良かったです。
個人的にこれまでは静的ライブラリを利用することが多かったですが、動的ライブラリや共有ライブラリなど、用途に合わせて使ってみようと思いました。


植山類さん講演会 (並行プログラミング)

先週に引き続き、リンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者である植村類さんの講演会に参加しました。

今回は並行プログラミングを主題として、効率化の仕組みや類さんが自作されているリンカmoldについても教えていただきました。

特にlldとmoldの速度の違いに関してはとても興味深かったです。

ここから、学んだことをまとめています。

マルチコアマシン

  • 昔はシングルコアだけだった。

  • 今は PC やスマホもマルチコア

    • チップの微細化が進んでいるから。
  • 10 万円以下だと 4 ~ 6 コア

  • ハイエンドだと 16 ~ 64コア

    • 今の技術的には 64 コアくらいが上限。

    • 微細化が進めばもっと多くなるかも。

  • スパコンだともっと多かったりする。

性能向上
  • マルチコア構成により、複数のプログラムを同時に実行できる。

  • make -jN のように make を実行するとサブプロセスを N 個同時に実行できる。

    • 複数プロセスで実行するため素早く make できる。

マルチスレッドと共有資源

  • 1 つのプログラムをマルチコアマシンで速く動かすには、複数のスレッドを使う。

  • ローカル変数はスレッドごとに別。

    • スレッドごとに別々実行スタックを持つ。
  • マルチスレッドの例として Web サーバやレイトレーシングGUI アプリなどが挙げられる。

  • スレッドもあまり細かくしすぎるとオーバーヘッドが大きくなる。

    • そのため効率が良くならないこともある。
  • 既存のプログラムをマルチスレッド化する万能の方法はない。

  • 個別に良い感じのタスク分割をする。

Web サーバでのマルチスレッド
  • コネクションが多すぎるとスケールしない。

  • 少ないスレッドでイベント駆動型のほうが良いのか?

    • どっちも派閥がある。

    • 一概にどちらが良いとは言えない。

  • google だとマルチスレッド。

  • 1スレッド1コネクションの方がプログラミングは楽。

タスク分割のガイドライン

  • スレッド間で共有するデータは少ないほうが良い。

    • データの整合性を保つための排他制御が必要になる。
  • タスクの粒度は大きい方が良い。

    • 小さい処理を分割してもオーバーヘッドの方が大きい。
  • タスクは多い方が良い。

  • スレッド間の関係は単純な方が良い。

共有データの古典的な問題
  • 銀行で同時に振り込みを行う。

    • 正しく制御しないと残高が合わないってことが起こり得る。
  • そのためロックを使って排他制御を行う。

  • 上手くロックしないとデッドロックが起こる。

    • 互いに相手の終了待ちとなり、いつまでも処理が進まなくなってしまう状態。
排他制御の責任はプログラマーにある?
  • もう少し低いレイヤーでいい感じに制御できないのか。

  • あることはあるが基本的にはプログラムで上手く排他制御するのがベター。

  • トランザクショナル・メモリ を用いて CPU によって排他制御が行うことも可能ではある。

    • 各実行スレッドがそのコピーをローカルに持ち、処理終了時点で参照数値が変更されていないことの確認と、結果の書き込みを一気に行う。

    • 失敗した場合、処理そのものを廃棄してやり直す。

高水準スレッドライブラリ

並行コンテナ

  • 別のスレッドからアクセスしても大丈夫な配列。

  • ベクタやハッシュテーブルなどのデータ構造と同じ API を提供している。

  • 中身の具体的な実装を気にすることなく使える。

Future

  • データの受け渡しとスレッドの同期を一体化したもの。

  • データを生成する側はデータを Future にセットする。

  • 受け取り側は、必要となった時に Future から読み取る。

Wait group

  • カウントダウン・ラッチともいう。

  • 全員の処理を完了するまでの待ち合わせポイントとして使うことができる。

    • メインのルーチンがサブルーチンが全て終わるまで待つ。
  • プロセスの wait みたいなイメージ。

アムダールの法則

  • 並列化されたプログラムの性能を決める要因

    1. 並列化されていない箇所が全体のどれくらいか。

    2. 何個のコアが利用可能か。

(例) シングルコアで30分かかる処理

  • 20分の処理は並列化されている。

  • コアがいくつあっても10分より短くすることができない。

  • 並列化された処理を増やすことが重要となる。

mold と lld の比較

  • lld は並列化されていない処理が多い。

    • 全体の処理時間の大半を占めている。
  • mold はほぼすべての処理が並列化されていないされている。

    • 短時間で処理可能。
mold の速度
  • 手元のマシンでcd出力ファイル 1GB あたり約 1 秒

  • cp で出力ファイルを別ファイルにコピーするのと比較して 2 倍遅い程度

  • かなり速いらしい。

  • 秘訣はたくさんのコアを有効に活用すること。

mold リンカの並列化手法

mold の目標

  • 利用可能なコアを使い切る。

  • 複雑のなことは行わない。

採用した手法

  • データパラレリズム

  • 同じ型のデータがたくさんあり、並列 for ループで同時に処理する。

  • リンカ全体としてはシングルスレッドの場合と同じ複雑さ。

  • 高水準スレッドライブラリはそこまでたくさん使っていない。

無理なく並列化できるデータ構造を考えることが大切。

Intel TBB

  • C++ライブラリ

  • 並列コンテナや 並列 for ループなど、マルチスレッドプログラミングのベースとなる機能

  • mold でも使っている。

並列forループ

  • 異なる繰り返しが同時に走るかもしれない for ループ。
tbb::parallel_for(0, 10000, [&](int i) {
    len[i] = strings[i].size();
});
  • 最大で10000 並列で実行してくれる。

  • 要素が少ないときに呼ぶとオーバーヘッドの方が無駄となる。

並列での名前解決

  • 基本的にはハッシュテーブル。

  • 並列化されたハッシュテーブルに並列 for ループで入れていく。

ファイルオフセットの決定

文字列をファイルに出力する場合

  • 各文字列ごとにファイル上での位置を決める必要がある。

  • 並列に足し算を行って、オフセットを求める。

入力文字
hello xxxx world

hello 文字列長 5 オフセット 5
xxxx  文字列長 4 オフセット 9
world 文字列長 5 オフセット 14

並行ハッシュマップ

  • mold では自作の並行ハッシュテーブルを利用している。

  • ハッシュテーブルのサイズを拡張する操作が遅い。

    • そのためリサイズしたくない。

    • あらかじめ大きなハッシュテーブルを用意する。

  • すべての要素数を数えればちょうどよい大きさのハッシュテーブルができる。

    • しかしそれだと時間がかかるので本末転倒。
  • ユニークな要素数を推定できるアルゴリズムを用いる。

HyperLogLog アルゴリズム
  1. 文字列ごとにハッシュ値計算する。

  2. ハッシュ値の最後に連続している 0 の数を数える。

(例) 最大で 0 が 5個連続しているものがあった場合

  • そのような要素が出現する確率は [tex: \frac {1} {28} = \frac {1} {256} ]

  • おそらく元の要素は 256 種類程度あったと推測できる。

  • 実際は複数の数をハッシュ値を使って複数の予測値を出して、それをすべて合わせることで、よりよい精度で推測を行う。

MapReduce パターン
  • 共有ライブラリのシンボルを参照している未定義シンボルがあり、PLT/GOTを作る場合などに用いられる。

  • ベクタを小さいブロックに分けて、並列に処理する。(Map フェーズ)

  • ブロックを処理した結果として、少量のデータを出力する。

  • 少量のデータをシングルスレッドで処理する。(Reduce フェーズ)

速いプログラムを書くために

  • 推測せず、計測する。

  • 凝ったコードより自然と速くなるようなデータ構造を考える。

  • 複数実装して、一番速いものを選ぶ。

  • 何度か同じプログラムを書く。

    • 再び作ることでより学べる。

    • 最初からいい感じに作るのは無理。

    • 同じ実装で改善できる範囲にも限界がある。

    • lldb で実装すると書き直しになるので mold を作った。

感想

並列処理を学ぶことの重要性を理解することができました。

工夫次第で劇的に性能向上が期待できるということが学べて良かったです。

また lld と mold の実行速度の違いを例として見ることができたのでよりイメージが湧きました。

最後に教えて頂いた効率的なコードの書き方を今後意識していこうと思います。

第6章 メモリ階層

6章について
この章では、メモリ階層ごとの特性や回転ディスク、半導体ドライブといったデバイスがどのように配置されているかについて書かれていました。
メモリ階層の仕組みや局所性の原理を学ぶことで効率的なプログラムの書き方を学んでいきます。
以下まとめです。


メモリ階層

メモリ階層とデータ移動の流れを理解すれば、上位階層にデータを保持するようなプログラムを書くことが可能となる。


メモリ階層のイメージ

## 上に行くほど小さく速い(高価)
L0: CPUレジスタ
L1: キャッシュ(SRAM)
L2: キャッシュ(SRAM)
L3: キャッシュ(SRAM)
L4: メイン・メモリ(DRAM)
L5: ローカルの二次記憶(ローカル・ディスク)
L6: リモートの二次記憶(分散ファイル・システム, ウェブ・サービス)
## 下に行くほど大きく遅い(安価) 


データの格納場所によるコストの違い

収納場所 コスト(サイクル数)
CPU レジスタ 0
キャッシュ 4 ~ 75
メインメモリ 数百
ディスク 数千万

最上位のレジスタとディスクで、かなりの差があることが分かりますね。


ストレージの技術

初期のコンピュータの RAM は数キロバイトしかなかったが、1982年に10 メガバイト。2015年でその30 万倍と進化している。
そして現在では、ストレージ容量は数年ごとに 2 倍の早さで増加し続けている。


ランダム・アクセス・メモリ(RAM)

RAM にはスタティック(SRAM)とダイナミック(DRAM)の二種類が存在する。

SRAM : DRAMに比べて高速で高価だが容量が小さい。キャッシュ・メモリに用いられる。

DRAM : 主記憶の他、グラフィック・システムのフレーム・バッファに用いられる。


DRAMの種類

定期的に新しい種類が現れ、それぞれアクセス速度を改善するための最適化がなされている。

FPM DRAM : 同じ行への連続したアクセスは行バッファと直接的にはやり取りできるように改良している。

EDO DRAM : FPM DRAM の強化版。それぞれの CAS 信号をより近い時間内に送ることができる。

SDRAM : 制御信号の多くを、外部クロック信号の立ち上がりエッジで起き換える。

DDR SDRAM : SDRAM の強化版。クロック信号の両方のエッジを用いることにより DRAM の速度を倍にする。

VRAM : グラフィック・システムのフレーム・バッファに用いられる。


不揮発メモリ (ROM)

DRAMSRAM は、電源を切ると情報を失う(揮発的)が、ROMは、電源が切られてもその情報を保持する。

ROM は書き込める回数と、その再プログラムのための仕組みによって区別される。

PROM、EPROM、EEPROM、フラッシュ・メモリといった種類がある。

ファームウェア : ROM デバイスに保持されたプログラムのこと。


メイン・メモリへのアクセス

データはプロセッサと DRAM メイン・メモリの間を、バス上で行ったり来たりする。

読み出しトランザクション : メイン・メモリから CPU へデータを転送する。

書き込みトランザクション : CPU からメイン・メモリへデータを転送する。


バス

バスとは並列する配線の集まりでコンピュータ内部でデータや信号を伝達するための回路や通路のこと。

CPUや主記憶装置、入出力装置などのそれぞれの装置が共通の伝送路であるバスで接続されている。


CPUとメイン・メモリを接続するバスの構成例

f:id:ryo_manba:20211002001331p:plain

構成要素は CPU チップ、I/O ブリッジとよばれるチップ・セット、メイン・メモリを形作る DRAM メモリ・モジュール群。

これらの構成要素は 2つのバスで接続されている。

システム・バス :CPU を I/O ブリッジに接続する。

メモリ・バス : I/O ブリッジをメインメモリに接続する。


ディスク・ストレージ

ディスクは膨大な量のデータを保持するが読み出すのに時間がかかる。

容量は数年ごとに2倍になり続けている。

構成

プラッタ : 円盤状の媒体。

サーフェス : 各プラッタには 2つあり、それらは磁気記憶材料で覆われている。トラックとよばれる同心円の集まりでできている。

スピンドル : プラッタの中心にあって回転している。


半導体ディスク (SSD)

フラッシュ・メモリをベースとしている。

状況によっては従来の回転ディスクの代替となる。

性能

読み出しは書き込みより早い。またデータはページ単位で読み書きされる。
ページは、それが属するブロック全体が消去されて初めて書き込むことができる。

長所 : 半導体メモリでできており、可動部品がない。これによりアクセスタイムが速くなり、電力消費が少なく頑丈となる。

短所 : フラッシュ・ブロックは書き込みを繰り返すうちに消耗してしまうため、寿命がある。そして高価。


局所性

最近参照した他のデータ項目そのものやその近くを参照すること。

時間的局所性 : 一度参照されたメモリに再びアクセスする。(例)同じ変数を利用する。

空間的局所性 : 一度参照されたメモリの近くのメモリにアクセスする。(例)ループ文で1ずつインデックスを増やして配列にアクセスする。


キャッシュ

階層内の各レベルは一つ下位のレベルからのデータをキャッシュする。

キャッシュ・ヒット : 命令処理に必要なデータがキャッシュに存在し、キャッシュからデータを読み込むことができること。

キャッシュ・ミス : 命令処理に必要なデータがキャッシュに存在せず、キャッシュからデータを読み込むことができないこと。

リプレースメント・ポリシー : キャッシュのブロックを置き換えるルール。ランダムに選択されるか、最も古いブロックを選択するかなど。

キャッシュ・ミスの種類 : コールド・ミス、競合ミス、容量ミスなどがある。


キャッシュ・メモリ

CPU とメイン・メモリのギャップ増大のため、L1キャッシュとよばれる小さなSRAMキャッシュ・メモリを導入した。

そしてCPU とメイン・メモリの性能差が増え続けたため、L2, L3 キャッシュも導入された。

キャッシュがデータを保持しているか調べるのに、ハッシュ・テーブルのような仕組みを使っている。


キャッシュの種類

ダイレクト・マップ、セット・アソシアティブ、フル・アソシアティブなどがある。


ミス時のライン・リプレースメント

LFU ポリシー : 一定期間中に最も参照回数が少なかったラインをリプレースする。

LRU ポリシー : 最後のアクセスが最も古いラインをリプレースする。


ライトに関する問題

ライト・スルー : キャッシュ・ブロックを次の下位レベルへ即座に書き込む。

ライト・バック : 更新されたブロックがキャッシュから追い出されるときのみ、一つ下位レベルに書き込むことで可能な限り更新を遅らせる。


ライト・ミスの処理

ライト・アロケート : 該当するブロックを一つ下位から読み出した後、そのキャッシュ・ブロックを更新する。

ノー・ライト・アロケート : キャッシュを通り抜けて一つ下位レベルへ直接ワードへ書き込む。

キャッシュ・パラメタの性能への影響

キャッシュの性能はミス率、ヒット率、ヒット時間、ミス・ペナルティの4つの指標によって評価される。


キャッシュサイズの影響

大きいキャッシュはヒット率を増加させやすい。一方で、大きいメモリを高速に動作させることは難しい。

そのため L1 は L2 よりも L2 は L3 よりも小さい。


ブロック・サイズの影響

大きいブロックはキャッシュ・ライン数が少ない。

利点 : 空間的局所性を利用してヒット率を上げる。

欠点 : 長い転送時間必要とするのでミス・ペナルティが大きい。


局所性を活かすには

空間的局所性を高める : データ・オブジェクトを、メモリに格納されている順序に従ってリードする。

時間的局所性を高める: データ・オブジェクトが一度リードされたら、できる限りそれを繰り返し使用する。


感想

自分は普段メモリ階層についてあまり意識していませんでした。
なんとなくレジスタが速くて、ディスクは遅いくらいのイメージだったので、メモリ階層について学ぶことができてよかったです。
またコード・レベルでも、なるべくよい局所性を持つように工夫していこうと思います。
この本の表紙となっているメモリ・マウンテンについてもようやく知ることができて、スッキリしました。


競プロ典型90問 050(★3) DP

050 - Stair Jump(★3)

問題

N 段の階段 があり、一歩で 1 段か L 段上がれる。

0 段目からN 段目までたどり着く移動方法何通りか、109 + 7 で割った余りを求める。

解法

そこまでに行ける通り数をDPで下から計算する。

答えは大きくなるので常にmodを取りながら計算する。

最終的にDP[N]が答えとなる。

全体計算量はO(N)で解ける。

所感

DP は苦手なのでなかなか思いつかなかった。

DP 関連の資料は多いので、この解き方になれるようにしたい。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll dp[100100] = {};

int main()
{
    ll n, l;
    cin >> n >> l;

    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (i < l)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] + dp[i - l]) % MOD; // lより大きくなったら, i - l から上がってくる場合も考慮する
    }
    cout << dp[n] << endl;
    return 0;
}

競プロ典型90問 048(★3) 貪欲法

048 - I will not drop out(★3)

問題

N 問, K 分間, 満点 A 点, 部分点 B 点(部分点は満点未満, 半分より大きい)

つまり \frac{A_i}{2} \lt B_i \lt A_i を満たす。

1分で部分点, 2分で満点が取れる。

K 分間で得られる最大得点を求める。

解法

得点方法は2パターン。

B 点取る or B 点取ってあるとこから、A - B 点取る。

後はsortして上から貪欲に選んでいく。

所感

最初にpairでsortしてから全探索したが上手くいかなかった。

全探索だと決めつけてしまい時間がかかった。

冷静に考えてみると、満点でも得られる点数は部分点より小さいため、 前計算してから同じ配列に入れて、大きい順に取るだけで大丈夫だった。

上手く行かないときは異なる視点から考えるようにしたい。

コード

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_;
const int INF = (int)1e9;
const ll INFL = (ll)1e18;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
int dx[]={0, 0, -1, 1};
int dy[]={1, -1, 0, 0};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main()
{
    ll n, k, ans = 0;
    cin >> n >> k;
    vector<ll> vec;
    rep(i,n)
    {
        ll a, b;
        cin >> a >> b;
        vec.push_back(b);
        vec.push_back(a - b);
    }
    sort(vec.rbegin(), vec.rend());
    rep(i,k) ans += vec[i];
    cout << ans << endl;
    return 0;
}

植山類さん講演会

植山類さんの講演会に参加してきました。

植山さんは、高速なリンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者でもあります。

そのため今回は特にリンカについて詳しく教えていただきました。

リンカの役割から動的リンクの仕組みまで前提知識がなくても分かりやすいように解説してくださいました。

ここから、学んだことをまとめています。

リンカの役割

オブジェクト・ファイル(.o)をつなぎ合わせて単体の実行ファイルや、共有ライブラリ(.so)にすること。
使用例 : cc -o hello hello.o main.o

リンカのコマンド(ld)も、cc 経由で間接的に起動するのが普通の使い方だという。
ちなみにcc はコンパイラではなくコンパイラドライバらしい。

-### オプションをつけることで実際に cc がどのように ld を起動しているのかを確認できる。
使用例 : clang -o hello hello.o main.o -###

スタートアップルーティン
  • 普通アンダースコアから始まる。

  • _start みたいな感じ。

リンカが使われる場合

オブジェクトファイルは セクション という単位に分割することができる。

オブジェクトファイルの情報の表示
objdump -s hello.o

  • Hello world. みたいな単なる文字列は .rodata (readonly) セクションに位置する。

機械語の入っている .text セクションの逆アセンブル
objdump -d hello.o

主要なセクション
  • .text: 機械語

  • .data: 読み書き可能なデータ

  • .rodata: リードオンリーのデータ

  • .bss: 初期値が0のデータ (初期化されていないグローバル変数)

  • call 命令のプレースホルダからのオフセット値が0だから次の命令を指すことになる。(この辺は難しかった)

実行ファイル
  • 実行ファイルにもコードとデータが分かれて入っている。

  • メモリ領域の上半分はカーネルが使うらしい。

イメージ (下の方がアドレスが若い)

[メモリ]
カーネル
スタック
ヒープ領域
0初期化されたデータ
初期化済みデータ
コード

スタックオーバーフローの仕組み

スタック領域は上の方にあって、使うごとに下に伸びる。
関数の呼び出しを繰り返して深くなりすぎると、メモリがマップされていない領域にアクセスしてしまい、セグフォする。

そんなに下に行くとデータを上書きしてしまうってところでストップをかけてくれる。
そんなに再起回っていたら無限再起だろー。って判定してくれるらしい。

mallocで確保できるサイズより小さいサイズでスタックがセグフォする理由

mallocで 4GB 確保できても スタックでは 2GB でセグフォする。
理由としては、技術的には可能だが普通はプログラムエラーなのであえて終わらせてるらしい。

カーネルのパラメータを変えれば大きいスタック領域も確保できるらしい。

ちなみに32bitマシンでは、スタック領域がそんなに取れないが、64bitマシンはメモリ領域が広いのでもしかしたら動作が早くなるかもしれないという。
なぜなら、stackポインタの移動にはそこまでコストはかからないから。mallocとfreeはコストがかかる。

リロケーション

オブジェクトファイルはでプログラム全体の一つの断片で、それ単体では実行できない。

リンカが複数のオブジェクトファイルを 1つにまとめる。(リロケートするという。)

コンパイラが関数をコンパイルするときには関数がが実行時にどこに存在するのかわからないので、アドレスを埋められない。

  • objdump -dr hello.o でリロケートの流れが見える。
リロケーションレコード
  1. どの場所を修正するか。

  2. どのアドレスで修正するか。

  3. どのように修正するか。

リンカの起源

1947年にリンカっぽいものができた。(アセンブリが発明されるよりも前。)

機械語で直接コードを書いているとしても、リンカは存在しないと困ってしまう。
なぜならsortなどの汎用性があるコードを書いて再利用するのに便利なので。

アーカイブファイル

スタティックライブラリ (アーカイブファイル .a ) は、 .oファイルをまとめたもの。

実行例 : ar t /hoge/libc.a

  • t をつけると tar みたいに展開して実態が見れる。

libc.a には、libc の関数が別々の .o ファイルに小分けされて入っている。
これは元々の libcのソースコードのレベルから、別のファイルに分けられている。
それらをコンパイルして最後にまとめて .a にまとめている。

必要なファイルだけが勝手に選ばれる仕組みが必要でアーカイブファイルが生まれた。
手動だとプログラムがどのオブジェクトファイルに依存しているかを分けるのが大変なので。

.oを小分けすることで使う関数だけをアーカイブファイルから取れるのでメモリの節約になる。

ダイナミックライブラリ

大きいコードを別々の実行ファイルにも埋め込むのは無駄なのでダイナミックライブラリを活用する。

しかしそこまで劇的に性能が上がるってわけでもないらしい。
理由としてはダイナミックライブラリを呼び出すのにもオーバーヘッドが生じるから。

再リンクをせずにコードだけをアップデートのしたいときには便利である。

使い方としては、実行ファイルとライブラリを別ファイルにわけて、ロードするときにメモリ上で組み合わせる。

実行例 : objdump -T libc.so(これで流れが確認できる)

ちなみにダイナミックリロケーションすることでロード時に書き換える場所が多くなるのでプログラムの起動が遅くなる。
ページ共有ができなくなるので物理メモリの使用量が増える。

GOT/PLT

ダイナミックライブラリを参照しているシンボルのためにGOT/PLT作る。

ライブラリの関数やデータを参照している場所を一箇所に集約することでダイナミックリロケーションのデメリットを解消する。

直接、アクセスするのではなく、 PLT, GOTを用いる。

  • 相対的なアドレスは常にメモリ上で固定なので常に同じ命令で参照できる。

ローダーのためにダイナミックリロケーションを作る。

GOT/PLTを使わないシステム

昔のバイナリフォーマット a.out には GOT/PLTはなかった。
共有ライブラリは特定のライブラリアドレスにロードされるのが前提にリンクされていたという。

オーバーヘッドは a.out 方式の方が小さい。

a.out フォーマットの問題

2つの共有ライブラリのアドレスが重なっているとロードできない。
そのため共有ライブラリのを配布する場合、適当なアドレスを予約してそれを他の人が使わないように登録しておくといった重複排除の仕組みが必要となる。

しかし共有ライブラリのサイズが成長していって結局他のもとかぶってしまうことが起こり得る。
そういった背景から a.out フォーマットから GOT/PLT へと移行した。

リンクエラーの原因

シンボル名が解決できない場合。(使いたい関数が存在しない)

シンボル名が重複している場合。(同名の関数が定義されている)

リンカの雑多な機能

  • 特定のアドレスにロードされるのが特定のライブラリ関数やデータを配置する。(主に組み込みやカーネルプログラムのため)

  • インライン関数など、複数のオブジェクトファイルに重複して含まれているものを一つだけ選ぶ。

  • 共有ライブラリからどのシンボルをエクスポートするかを選ぶ。

  • 誰からも参照されていないセクションを出力ファイルに入れない。

他にもいくつかあるらしい。

マングリング

C++名前空間や、同名の関数を引数の型でオーバーロードする場合の名前解決に役立つ。

  • 型や引数によって名前を変えている。

  • もし引数や関数名が被っていても上手いことやってくれるらしい。

int foo(int) {}
// _Z3fooi:

int foo(int, int, float) {}
// _Z3fooiif

上記のようにマングリングが行われる。

感想

とても勉強になりました。新しい学びが多く面白かったです。
CSAPPで事前に予習していたおかげで全体の流れが理解できた気がします。 また今回学んだことは今後の学習に役立てていこうと思います。
貴重な機会を提供してくれた42 Tokyoの皆さん、公演していただいた植山類さんありがとうございました!