まっつーのブログ

本の感想や振り返りなど雑多に書いてます

第7章 リンク

CS:APP コンピュータ･システム

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章 メモリ階層

CS:APP コンピュータ･システム

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)

DRAM やSRAM は、電源を切ると情報を失う(揮発的)が、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

競プロ典型90問

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) 貪欲法

競プロ典型90問

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の皆さん、公演していただいた植山類さんありがとうございました！

第5章 プログラム性能の最適化

CS:APP コンピュータ･システム

5章について
この章では、コードの性能を向上させる数多くのテクニックが紹介されていました。
またコンパイラの最適化について知り、どのようなコードが最適化をサポートするのかを理解することができます。
以下まとめです。


プログラムの最適化

最新のコンパイラの性能はますます向上しているが、実行環境に依存するプログラムには弱いため、コンパイラが最適化しやすいコードを書く必要がある。

具体的には、条件分岐や関数呼び出しなどの不要な処理を削除すること。

またアセンブリを見ることで、クリティカル･パスを発見し、実行時間を特定することができる。


最適化コンパイラ

コンパイラはプログラムでどの値が計算され、どう利用されるかを特定するアルゴリズムを持つ。

また利用者が最適化のレベルを指定できる。

例えば gcc -Og を指定すると基本的な最適化が適用される。

これら最適化により性能は向上するが、標準的なデバッガーによるデバッグが困難になることもあるので注意が必要。


保守的な最適化

コンパイラは安全な最適化のみを適用する。

そのため最適化により、結果が異なってしまうリスクがある場合には最適化を行わない。

具体例としては、メモリ･エイリアシングや、副作用を持つ(プログラムの状態を変更する)関数の呼び出しなどが挙げられる。


メモリ･エイリアシング : 2つのポインタが同一のメモリ位置を指していること。

x = 1000, y = 3000;
*q = y;  // 3000
*p = x;  // 1000
t1 = *q; // 1000 or 3000 // 事前に q = &pしているかによって結果が異なる

対策としては、ポインタを restrict で修飾して、が別名を持たないことをコンパイラに指示するという手法がある。


コードレベルの最適化

インライン展開 : 関数のコードを展開(実際のコードに置き換え)し、関数への制御転送をしないようにする手法。


コード移動

// ループの回数分関数が呼ばれる
for (int i = 0; i < strlen(s); i++)

// 前計算する
len = strlen(s);
for (int i = 0; i < len; i++)


不要なメモリ参照の削除

// ループの回数分destにアクセスする
for (int i = 0; i < len; i++) {
    *dest = *dest + acc;
}

// 一時変数に結果を累積する
int acc;
for (int i = 0; i < len; i++) {
    acc = acc + data[i];
}
*dest = acc;

この場合、一時変数を用いて結果を累積することで、dest へのアクセスが1回だけで済む。

ループのたびにメモリから値を読み書きするとコストがかかってしまう。


また累積器を複数もたせるという手法もある。

// 偶奇で2つの累積器を使う
for (int i = 0; i < max; i+=2) {
        even = even + data[i]; 
        odd = odd + data[i+1]; 
}
int res = even + odd;


スーパースカラ

複数の命令を同時にフェッチし、複数の実行ユニットを並列に動作させる。

プログラムの持つ命令レベルの並列性を利用して性能の向上を図るアーキテクチャ。


投機実行

プロセッサは、分岐が進むであろう方向のフェッチとデコード、演算の実行を分岐予測が正しいか分かる前に開始する。

演算は評価されるが、実際に実行すべきと判断されるまでレジスタやメモリを更新しない。

分岐予測が間違っていた場合、分岐の時点に状態をリセットする。


レジスタ関連

レジスタの分類

ループを構成するコードに対して、レジスタを4種に分類できる。

  1. Read-only : 計算するための値として利用されるが、ループ中で更新されることはない。

  2. Write-only : データ移動演算のデスティネーションとして利用される。

  3. Local : 更新かつ利用されるが、イテレーション間に依存しない。

  4. Loop : ソースとデストの両方で利用され、イテレーションで生成された値は別のイテレーションでも利用される。


レジスタ･リネーミング
レジスタを再利用しているために不必要な順序依存性が生じているのを、避ける手法。
他のレジスタを利用して再利用されているレジスタに割り当て、依存を無くすことができる。


レジスタ･スピル

並列実行を行う上で利用可能なレジスタ数を超える場合、スピルが発生する。

スピル : 実行時スタックに割り当てられたメモリ上の領域に一時的な値を格納する。

メモリはレジスタよりも遅いため、コストがかかる。


ループ･アンローリング

ループ命令を展開(アンロール)することで、並列実行可能なコードを増やし高速化を図る手法。

ちなみに浮動小数点加算、乗算は結合的ではないため適用されない。

またGCCは最適化レベル 3 以上で適用してくれるらしい。

// 通常のループ
for (int i = 0; i < 100; i++) {
    free(a[i]);
}

// 展開後
for (int i = 0; i < 100; i+=5){
    free(a[i]);
    free(a[i+1]);
    free(a[i+2]);   
    free(a[i+3]);
    free(a[i+4]);
}


条件付き移動

制御移動はコストがかかるので if-else を使わずに処理する。

void minmax(int a[], int b[], int n)
{
 // if 文で min-maxを代入するよりも効率が良くなる
    for (int i = 0; i < n; i++) {
        int min = a[i] < b[i] ? a[i] : b[i];
        int max = a[i] < b[i] ? b[i] : a[i];
        a[i] = min;
        b[i] = max;
    }
}


write/read依存

同じメモリ位置に対して読み書きを行うことで、依存が生まれ速度低下を引き起こす。

読み書きのメモリ･アドレスが一致する場合は、データのストア、ロードなどもクリティカルパスに関わってくる。


性能向上の4つのテクニック

  1. ハイ･レベルの設計 : 適切なアルゴリズムとデータ構造を選ぶ。

  2. 基本コーディング原則 :コンパイラが関数を効率的なコードを生成できるよう、最適化阻害要因を避ける。

  3. ロー･レベルの最適化 : ハードウェア能力を活用するようコードを構成すること(ループ･アンローリングや複数累積器などの利用)

  4. コードのプロファイル : GPROFなどを利用して情報を得る。


GPROF

GPROFを活用することで、2つの情報が得られる。

  1. 各関数がどの程度CPU時間を費やしているか。

  2. 各関数がどの関数にどの程度呼び出されたか。

gcc -Og -pg test.c
./a.out
gprof a.out # gprofを呼び出して解析する。


感想

これまでは最適化のオプションをつければ、どんなコードでもコンパイラが効率良く展開してくれると思っていました。
実際にはコードの内容がかなり最適化に影響するということが学べて良かったです。
今後は意識的に最適化をサポートするようなコードを書いていこうと思います。
これまでの章と比べ、普段からすぐ使えそうな内容だったので読んでいて特に面白かったです。