2021-09-24

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

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

プログラムの最適化
最適化コンパイラ
コードレベルの最適化
スーパースカラ
投機実行
レジスタ関連
ループ･アンローリング
条件付き移動
write/read依存
性能向上の4つのテクニック
感想

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種に分類できる。

Read-only : 計算するための値として利用されるが、ループ中で更新されることはない。
Write-only : データ移動演算のデスティネーションとして利用される。
Local : 更新かつ利用されるが、イテレーション間に依存しない。
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つのテクニック

ハイ･レベルの設計 : 適切なアルゴリズムとデータ構造を選ぶ。
基本コーディング原則 :コンパイラが関数を効率的なコードを生成できるよう、最適化阻害要因を避ける。
ロー･レベルの最適化 : ハードウェア能力を活用するようコードを構成すること(ループ･アンローリングや複数累積器などの利用)
コードのプロファイル : GPROFなどを利用して情報を得る。

GPROF

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

各関数がどの程度CPU時間を費やしているか。
各関数がどの関数にどの程度呼び出されたか。

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

感想

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

2021-09-23

競プロ典型90問 046(★3) 組合せの問題

競プロ典型90問

046 - I Love 46（★3）

問題

3つの長さ N の数列 A, B, C が与えられる。

$A_i+B_j+C_k$ が46の倍数となる $(i,j,k)$ $(1≤i,j,k≤N)$ の選び方の総数を求める。

解法

3つの数列が最大10⁵と制約が厳しいため全探索ではTLEになってしまう。

そのため、最初にmodを取ることで、0〜45の46種類に絞る。

46³ = 97336通りしかないので、これで全探索が可能になる。

所感

制約を見て実直に全探索ではなく、条件を絞ることは早めに気づけた。

式があっていたのにWAが出てしまい、30分くらい悩んだ。

mapをint型にしていたので、オーバーフローしていたのが原因だった。

少しでもオーバーフローのリスクがある場合は迷わず long long を使おうと思う。

コード

#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()
{
    int    n, x, y, z;
    ll ans = 0;
    cin >> n;
    map<ll, ll> a, b, c;

    rep(i,n)
    {
        cin >> x;
        a[x % 46]++;
    }
    rep(i,n)
    {
        cin >> y;
        b[y % 46]++;
    }
    rep(i,n)
    {
        cin >> z;
        c[z % 46]++;
    }

    for (int i = 0; i < 46; i++) {
        for (int j = 0; j < 46; j++) {
            for (int k = 0; k < 46; k++) {
                if ((i + j + k) % 46 == 0)
                    ans += a[i] * b[j] * c[k];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

2021-09-15

第4章プロセッサ･アーキテクチャ

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

ISA(命令セット･アーキテクチャ)
プログラマ･ビジブルって？
ハードウェア設計
レジスタファイル
シーケンシャルなプロセッサ(SEQ)
処理ステージの説明
パイプライン処理
効率低下の要因
パイプライン･ハザードとは？
例外処理
感想

4章について
この章では、基本的な論理回路の仕組みから始まり、x86-64をベースとしたY86-64の実装を通してプロセッサについて書かれていました。

プロセッサを学ぶことで、コンピュータ･システム全体の働きを深く知ることができます。

以下まとめです。

ISA(命令セット･アーキテクチャ)

プロセッサによって、サポートされている命令とそれらのバイト単位でのエンコーディング方法をまとめた総称のこと。

命令は、1バイト、または複数バイトの列としてエンコードされる。

ISAのモデルはシーケンシャル(逐次的)な命令の実行のように見えるが、プロセッサは並列処理をしている。

プログラマ･ビジブルって？

読み書き可能なステートのことをプログラマ･ビジブルなステートとよぶ。

Y86のステートはx86と似ており、15本のプログラム･レジスタを持っており、それぞれ64ビットのワードを格納する。

それぞれ1ビットからなる3つの条件コードを持っている。

条件コード : 算術論理演算の結果に関する情報を保持するために使われる。

プログラマ･カウンタ(PC) : 現在実行している命令の実行をアドレスを保持する。

ハードウェア設計

ハードウェア設計では、ビット演算や、様々な種類のメモリ素子にビット･データを保持するために電子回路が用いられる。

ディジタル･システム構成の主要3要素

組み合わせ回路(ビット演算)
メモリ素子(ビットデータを保持)
クロック信号(メモリ素子の更新)

論理ゲート

ディジタル回路において、計算を行う基本要素のこと。

AND(&&), OR(||), NOT(!) それぞれに対応した記号がある。

ちなみに演算量は1ビット(ワード全体を演算しているわけではないため)

f:id:ryo_manba:20210916092133p:plain — 組み合わせ回路の例1

組み合わせ回路とHCLによるブール式

組み合わせ回路 : 論理ゲートを組み合わせたもの。

f:id:ryo_manba:20210916092220p:plain — 組み合わせ回路の例2

上記の組み合わせ回路をHCLで書くと以下になる。

bool eq = (a && b) || (!a && !b);

HCLはC言語スタイルの文法なので、直感的ですね。

違う点としては、= は代入ではなく、式に名前をつけているだけであること。

マルチプレクサ(MUX) : 2つ以上の入力を1つの信号として出力する。

ALU(演算装置) : 制御信号の状態に応じて、算術論理演算を行う。

メモリとクロッキング : 組み合わせ回路は情報を保持できないため、シンプルに入力の変化に対して、結果を出力する。

順序回路 : 状態を持ち、その上で計算を行う。

クロック : 記憶回路にいつ新しい値を反映させるかを決める周期的な信号のこと。

レジスタ : ハードウェアと、マシン語レベルのプログラミングでは異なる意味を持つため｢ハードウェア･レジスタ｣、｢プログラム･レジスタ｣と区別される。

レジスタファイル

リード･ポートとライトポートを持つ。

リード･ポートが2つあるマルチポート化されたメモリでは、複数の読み書きが同時に行える。

ちなみに同じレジスタに同時に読み書きを行おうとした場合、リード･ポートの出力は、古い値から新しい値に遷移するという。

シーケンシャルなプロセッサ(SEQ)

各クロック･サイクルにおいて、一つの命令を実行するために必要なすべてのステップが完全に処理される。

サイクル･タイムが非常に長くなり、クロック･レートが低くなるといったデメリットがある。

SEQを開発することで、最終的に効率的なパイプライン･プロセッサ実装へつながるという。

処理ステージの説明

命令の振る舞いは種類ごとに異なるが、すべての命令が一つのシーケンスに従うようにする必要がある。

そのため、各ステージにおける処理の詳細は、命令の種類に応じて違っていても良い。

フェッチ : プログラム･カウンタにある値を、メモリ･アドレスとして用い、命令のデータを読み出す。

デコード : 最大二つのオペランドをレジスタ･ファイルから読み出し、valA と valB の片方あるいは双方の値を得る。

実行 : 演算処理、実効アドレスの計算、スタック･ポインタの移動

メモリ : データをメモリに書き込むか、メモリからデータを読み出す。

ライト･バック : 最大二つまでの結果をレジスタ･ファイルに書き込む。

PCアップデート : PCの内容を次の命令のアドレスに更新する。

nop命令 : 何の処理を行うことなくステージ間を流れる(PCは1インクリメントされる)

halt命令 : プロセッサを停止させるためにプロセッサのステータス･コードをHLTにセットする。

SEQの問題点

遅すぎること。

しかし、1サイクル内にすべてのステージに信号を伝搬させるために遅い必要がある。

これだとハードウェア･ユニットを有効に活用できないので、パイプライン化を導入する。

パイプライン処理

丸亀製麺で一列に並ぶイメージ。

うどんだけが食べたくても、すべてのステージを通過する必要がある。

パイプライン化によるメリットは、レイテンシ(個々の客のサービスに要する時間)は増加する可能性はあるが、スループット(単位時間あたりに提供できる客の数)は向上すること。

丸亀製麺は偉大ですね。

パイプライン化されていない場合

回路(300ps)->レジスタ(20ps)
遅延(320ps)
スループット(3.12GIPS)
回路->回路->回路

パイプライン化されている場合

回路A,B,Cの3種類(100ps)
レジスタ(20ps)

A->レジスタ->B->レジスタ->C->レジスタ
遅延(360ps)
スループット(8.33GIPS)
A->B->C
   A->B->C
      A->B->C

遅延は伸びているが、スループットは向上している。

効率低下の要因

非均一な分割

システムのスループットは最も低速なステージの速度によって制限される。

そのため、計算にかかる速度を均一にすることが重要となる。

1つのステージに時間がかかる例

回路A(50ps)
回路B(150ps)
回路C(100ps)
レジスタ(20ps)

A->レジスタ->B->レジスタ->C->レジスタ
A->BBB->CC
   A  ->BBB->CC
        A  ->BBB->CC
#Bの処理が終わらないと進めない

深いパイプライン処理

最新のプロセッサはとても深いパイプライン(15やそれ以上)を使用することで、各ステージの遅延を小さくしている。

パイプライン･ハザードとは？

ハザードには、危険、有害といった意味があります。

つまり、パイプライン･ハザードとは、依存関係により正しい処理ができなくなる危険性のことを指します。

データ依存 : 命令によって計算された結果が後続の命令のためのデータとして使われる場合。

制御依存 : ジャンプ、コール、リターンといった命令の実行時に、ある命令が後続の命令のロケーションを決める場合。

データ･ハザード対策

結果を待つために nop命令を挟む。

そうすることでまだ書き込まれていない状態のレジスタを読んでしまうことを防ぐ。

ストール : ハザードの条件が成立しなくなるまで、命令の進行を待たせること。

バブル : nop命令のようなもの。進行を待たせる。

フォワーディング : 結果の値をパイプライン･ステージから、より早いステージへと渡す技術。

Load/Useデータ･ハザード : メモリから読みだした値を後続の命令が使用する場合に発生する。

制御ハザード対策

フェッチ･ステージで次の命令を確実に決められないときに生じる。

条件分岐で予測ミスした場合に、ミスが見つかるまでの間に次の命令がフェッチされてしまう。

そこで、バブルを利用し、その命令をキャンセルさせて、後続の命令をフェッチすることができる。

例外処理

内部的例外 : halt命令や組み合わせが無効な命令、無効なアドレスへのアクセス

外部的例外 :ユーザがマウスのボタンをクリック、インターフェースが新しいパケットを受信

例外が発生した場合、ステータス・コードを適切にセットし、プロセッサを停止させる。

完全な設計の場合は、プロセッサは例外処理モードに例外ハンドラを起動して処理を続ける。

例外発生から停止までの流れ

命令が例外を生成するとき、例外の原因をステータス・フィールドにセットする。
その例外ステータスは、命令の他の情報と一緒にパイプラインを伝わっていき、ライト･バック･ステージに到達する。
この時点で、例外の発生を検出して実行を停止させる。

実行ステージの浮動小数点演算ユニットを拡張したり、メインのパイプラインとは独立に動作する特別なハードウェア機能ユニットを扱うことで処理を高速にする。

感想

Y86-64の実装から各ステージごとの処理の流れについて、体系的に学ぶことができました。
実はこんな仕組みで動いてたんだなと。全然知らなかったので、普段使っているPCを褒めてあげたいですね。
またパイプライン処理の部分は、読み進めていて面白かったです。
この章は全体的に図で説明されているものが多かったので、理解しやすかった気がしました。

2021-09-09

競プロ典型90問 038(★3) オーバーフロー

競プロ典型90問

038 - Large LCM（★3）

問題

A, Bの最小公倍数を求める。

$10^{18}$ を超える場合は Large と出力する。

解法

最小公倍数は $lcm(a,b)=a*b/gcd(a,b)$ で表される。

そのまま計算すると $a*b$ でオーバーフローすることがあるので、式を変換する。

$b/gcd≤10^{18}$ であれば $a*b/gcd≤10^{18}$ が成り立つので正しく答えが求まる。

ちなみに Boost Multiprecision Library を使うと、多倍長整数の計算が扱えるのでそのまま計算するだけで良い。

所感

オーバーフローや誤差などの数字を扱う問題は、ちょっとした気付きで解ける事が多い気がする。

Boostの存在を知れたので良かった。

計算に時間がかかるのでそこは注意したい。

コード

実行時間(3 ms)

#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 a, b;
    cin >> a >> b;
    ll t = b / gcd(a, b);
    if (t > INFL / a) cout << "Large" << endl;
    else cout << t * b << endl;
    return 0;
}

boost を使った解法

実行時間 (12ms)

#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;

int main()
{
    Bint a, b, ans = 0;
    cin >> a >> b;
    ans = lcm(a, b);
    if (ans > (int64_t)1e18) cout << "Large" << endl;
    else cout << ans << endl;
    return 0;
}

2021-09-01

第3章プログラムのマシン･レベルの表現

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

高水準言語と低水準言語
マシン･レベル･コード
符号拡張
データ移動
ジャンプ命令
データ転送と制御転送
プロシージャ
ポインタ演算
配列の格納
構造体と共用体
アラインメント制約
バッファ･オーバーフロー
セキュリティ対策
感想

3章について
この章では、コンパイラによって生成されるマシン･コードの読み方や、マシン語レベルでの基本的な命令パターンについて学ぶことができます。
プログラムがマシン上でどのように表現されるかを理解することで、より良いコードが書けるそうです。
以下まとめです。

高水準言語と低水準言語

高水準言語 : 人間寄りの言語、特定のマシンに依存しない (C, Java, Python など普段目にするものは大概こっち)
低水準言語 : マシン寄りの言語、特定のマシンに依存する(アセンブリ, 機械語)

高水準言語は、最適化コンパイラを用いるだけで、効率的に書かれたアセンブリ･コードと同等の効率が得られる場合がある。

また、マシン･コードを学ぶことで、コンパイラの最適化を理解し、潜在的なコードの非効率性を解析できる。

近年だと、アセンブリを書く能力より、読んで理解できることの方が重要になってきているという。

マシン･レベル･コード

フォーマットと振る舞いは 命令セット･アーキテクチャ(ISA)により定義されている。

プログラム･カウンタ(PC) : 次に実行すべき命令メモリ中のアドレスを示す。

整数レジスタ･ファイル : アドレス(Cのポインタ)や整数データを保持する。

条件コード・レジスタ : 算術または論理演算命令の状態を保持する。

ディスアセンブラ : マシン･コードからアセンブリに近いフォーマットを生成する。

CPU

CPUは64ビットの数値を格納する16本の汎用レジスタ･セットを持つ。

レジスタは16ビット、32ビット、64ビットと拡大されている。

符号拡張

符号付の数値を表現するビット列が格納領域のビット幅より短い場合に、隙間を適切に埋めること。

-10を2の補数表現で表す。
8ビット
11110110
16ビットに符号拡張
11111111 11110110 = -10
符号拡張しない場合
00000000 11110110 = 246(値が変わってしまう)

データ移動

命令の中で最も多く使用されるのは、データを別のところへコピーする命令である。

#include <stdio.h>

// xpをyに書き換えてから、元のxpの値を返す
long exchange(long *xp, long y)
{
    long x = *xp;
    *xp = y;
    return x;
}

int main()
{
    long xp = 100;
    long y = 42;
    long ret = exchange(&xp, y);
    // xp=42, y=42, ret=100
    printf("xp=%ld, y=%ld, ret=%ld\n", xp, y, ret);
    return 0;
}

mov命令を使ってデータ移動を行う。

_exchange:
movq    (%rdi), %rax   ## xをメモリから読み出し、その値を%raxへ格納する。
movq    %rsi, (%rdi)   ## yを%rdiにあるxpへ書き込む
ret    ##関数がコールされたポイントへ戻る命令

ジャンプ命令

その名の通り、別の処理にジャンプさせることができる。

主に if-else などの条件分岐に使用される。

つまりアセンブリでは、シンプルな条件分岐も goto 文のように書かれているらしい。

直接ジャンプ: ジャンプターゲットが命令の一部としてエンコードされている。
間接ジャンプ: ジャンプターゲットがレジスタかメモリから読み込まれる。
条件付きジャンプ: 他に条件コードに応じてジャンプを実行する。(直接ジャンプのみ)

直接ジャンプ
jmp .L1    ##　.L1をラベルとして扱う。

間接ジャンプ
jmp *%rax   ##　%raxレジスタの値がジャンプターゲット。
jmp *(%rax) ##　%raxレジスタの値をアドレスとしてジャンプターゲットをメモリから読み込む。

データ転送と制御転送

データ転送 : 代入などの処理
制御転送 : if-else文などの条件分岐

データ転送は制御転送よりも効率的

制御転送の場合、評価されるまで次の命令が分からないため次の命令を予測をする。

しかし、予測をミスした場合、命令をやり直す必要があるためコストがかかる。

そのため、データ転送のほうが効率的となる。

例外として、そもそも代入にコストがかかる場合は、制御転送のほうが効率的。

また、ポインタのデリファレンスなどが行われるリスクがあるからため使えない場合もある。

使用ケースは限られてるけど、プロセッサよっては効率的に処理できるよってことですね。

プロシージャ

関数やメソッド、ルーチンみたいなもの。

プロシージャ呼び出しにかかるコストを最小化するために、3つメカニズムを利用している。

呼び出す際、PCはコードの開始アドレスを指すようにセットする。
レジスタを介してデータを受け渡す。
実行開始時にローカル変数のための領域を割り当て、戻る際にその領域を開放する。

この仕組みのおかげで、再帰的に呼び出す場合でも、それぞれのローカル変数が干渉しないってことみたいですね。

レジスタ

呼び出し先退避レジスタ : レジスタ値の上書きできない。

呼び出し元退避レジスタ : レジスタ値の上書きできる。(関数でポインタを引数として渡す場合など)

ポインタ演算

配列のアクセス添字表現は、ポインタにも適用できる。

つまりA[i] という配列参照は、*(A+i),*(i+A),i[A]と等価である。

#include <stdio.h>

int main()
{
    char *a = "hello";

    printf("%c, %c, %c, %c\n", a[1], *(a+1), *(1+a), 1[a]);
    return 0;
}

$ ./a.out 
e e e e

1[a]みたいにアクセスする機会はなさそうですが、雑学として知っていると面白いかもしれませんね。

配列の格納

メモリ上で配列要素は、行優先順で格納される。

行    要素     アドレス
A[0] A[0][0]   XA
     A[0][1]   XA + 4
A[1] A[1][0]   XA + 8
     A[1][1]   XA + 12

このメモリの並びを知っていると非効率なコードを回避できる。

for(i = 0; i < 1000; i++){
    for(j = 0; j < 1000; j++){
       res1 += a1[i][j] + a2[i][j]; // 連続したアドレスにアクセスするため速い
       res2 += a1[j][i] + a2[j][i]; // アクセスが毎回バラバラなため遅い
    }
}

構造体と共用体

構造体 : 配列の実装に似ており、要素はメモリ上の連続領域に格納される。

共用体: 複数の要素がすべてが同じブロックに対応する。

struct S3 {
    char   c;
    int    i[2];
    double v;
};
union U3 {
    char   c;
    int    i[2];
    double v;
};

型  c  i  v　　　サイズ
S3  0  4 　16  24
U3  0  0  0   8 / / 総サイズは要素の最大サイズとなる(この場合double(8バイト))

共用体は使い方によっては、メモリ使用量を抑えることができる。

またすべてが同じブロックに対応するため、どのメンバを指すかによって、キャストにも使える。

アラインメント制約

オブジェクトのアドレスは、ある定数 K (2, 4, 8のいずれか)の整数倍の値となる。

Intelは性能改善のため、データをメモリ上でアラインメントすることを推奨しているみたい。

バッファ･オーバーフロー

スタック上に格納された文字配列に対し、サイズを超えた文字列を格納してしまうと起きる。

他の保持情報が改ざんされるので、システムのセキュリティ攻撃使われることもある。

セキュリティ対策

スタック･ランダマイゼーション : プログラムの実行ごとにスタックの場所を変化させる。

スタック･プロテクト : カナリア値とよばれる値をスタック･フレーム内に挿入し、プログラム実行時後に変更されている場合は、エラーを発生させる。

セキュリティ画一性 : 古いマシンだと、スタックの場所がほぼ一定のため、1台のスタック･アドレスが特定されると、多くのマシンが攻撃可能となってしまうこと。

感想

これまでアセンブリに触れていなかったので、新しい発見ばかりで面白かったです。
さっくりとまとめていますが、実際の内容はこの100倍くらい学ぶことがあると思います。
各命令セットの詳細やC言語で書かれたコードに対応するアセンブリ･コードなど、とても興味深い内容でした。
練習問題もたくさんあり、まだ解いていないものもあるので、引き続き勉強してみようと思います。

2021-08-29

競プロ典型90問 032(★3) 順列全探索

競プロ典型90問

032 - AtCoder Ekiden（★3）

問題

N人の駅伝選手。

コースは 1からN区まであり、選手 i が j 区までかかる時間は $A_{ij}$

M 個のルールがあり、 $X_i$ と $Y_i$ はたすきの受け渡しができない。

ゴールまでにかかる時間の最小値を求める。

解法

制約が N ≤ 10 と小さいため最大でも 10! = 3628800で収まる。

順列全探索を用いることで計算量 $O(N!*N)$ で求められる。

所感

配列の添字を間違える事があったので、条件に応じて 0-indexedか1-indexedを切り替えるなど工夫する。

順列全探索の問題は最近のABCでも何回か出てるのでマスターせねば。

コード

#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 n, m;
int a[20][20];
int x[100], y[100];
bool naka[100][100];

int main()
{
    cin >> n;
    rep(i,n) rep(j,n) cin >> a[i][j];
    cin >> m;
    rep(i,m) cin >> x[i] >> y[i];

    vector<int> vec;
    rep(i,n) vec.push_back(i+1); // 順列全探索用の配列
    rep(i,m) // バトンを渡せないところをチェックする
    {
        naka[x[i]][y[i]] = true;
        naka[y[i]][x[i]] = true;
    }

    int ans = INF;
    do
    {
        int sum = 0;
        bool flag = true;
        rep(i,n - 1)
        {
            if (naka[vec[i]][vec[i + 1]] == true) // バトンが渡せないところがあればその数列は満たさない
            {
                flag = false;
                break;
            }
        }
        if (flag == true) // ゴールにたどり着けたらそれまでのコストを計算する
        {
            rep(i,n) sum += a[vec[i]- 1][i];
            chmin(ans, sum);
        }
    } while(next_permutation(vec.begin(), vec.end()));

    if (ans == INF) ans = -1;
    cout << ans << endl;
    return 0;
}

2021-08-25

競プロ典型90問 020(★3) 浮動小数点の誤差

競プロ典型90問

020 - Log Inequality（★3）

問題

$\log_2 a$ < $b \log_2 c$ が成り立つか。

解法

愚直に log() を使って求めると誤差が出てしまう。

そのため全て整数で処理をする必要がある。

対数 log は底が同じ値の場合、log が外せるので、

$\log_ax = \log_ay$ は $x = y$ と表せる。

そして累乗の場合は、

$b \log_a c = \log_a c ^ b$ が成り立つ。

後はこの公式を利用して、整数で比較すれば誤差なく答えが求まる。

所感

浮動小数点を扱う問題で特に制約の範囲が広い場合は要注意。

できるだけ怪しい浮動小数点演算は使わずに整数で計算した方が良さそう。

累乗も pow() だと誤差が出る場合もあるので、ループ処理で行うようにする。

コード

#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 a, b, c, x;
    cin >> a >> b >> c;

    x = c;
    rep(i,b - 1) x *= c;
    if (a < x) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}