search

kawasin73 / knowledge

気になったツールやサイト、勉強した内容をまとめます。
9 stars 0 forks source link

本：省メモリプログラミング #5

Closed kawasin73 closed 5 years ago

kawasin73 commented 6 years ago

省メモリプログラミングを読みます。

「スモールメモリソフトウェア」とは、好きなだけのメモリを使えないすべてのソフトウェアをいう

amazon

img_3577

kawasin73 commented 6 years ago

1章 小規模アーキテクチャ

メモリ制約はシステムの設計全体を横断するものであり、システムのすべての部分に影響を及ぼす。 コンポーネントは一貫性と責任に基づいて分割される。 共通のメモリ方針を設ける。

インターフェイス設計で考慮すべき問題

Memory Limit：限定メモリ

コンポーネントごとにメモリの上限を設定し、その上限を超えるアロケーションは失敗させる

開発時にメモリ使用量を計測して上限を設定する。 メモリ使用量を記録して上限を超える場合は、利用可能なメモリがシステム中にないときと同じようにメモリアロケーションに失敗させる

上限は全てのコンポーネントの上限がシステムのメモリ量を超えてもいい。一つのコンポーネントがシステムのメモリの大半を使い果たさないように設定すれば良い。 上限は動的にメモリを確保するコンポーネントに設ければ十分

アプローチ

Small Interfaces：小規模インターフェイス

コンポーネント間でのインターフェイス呼び出しでデータの受け渡しをするためのメモリが必要になる。そのメモリは誰の責任になるのか。

データの受け渡しをクライアント側が制御するよう、インターフェイスを設計する。

コンポーネントインターフェイス設計

一方、インターフェイスが複雑になる可能性があり、プログラマの規律が要求され、チーム間のコミュニケーションが必要になる。開発時間のパフォーマンスが悪くなる可能性がある。

実装方法

Partial Failure：部分失敗

通常はメモリ不足に陥った時にプロセスをクラッシュさせることが受け入れられている。 メモリ制限のあるシステムではメモリ不足になってもシステムが安全な状態に保たれることを保証することが望ましい。

安定した状態に戻るまで、縮小モードで処理を続行。

ユーザーへ適切に伝える

プログラムの最小限のメモリ要求は減少し、メモリ要求の予測性が向上する

実装

  1. メモリの枯渇を検出する
  2. 安全な状態に回復させる
    • 大抵はメモリ要求を出したコンポーネントの機能を失敗させるだけ。またはこのコンポーネントだけ縮小モードへ移行
    • 他の重要でないコンポーネントのデータを削除
  3. リソースを解放する
    • 失敗した機能の過程で確保されたリソースの解放を忘れないようにする
  4. 縮小モード
    • コンポーネントは部分的な失敗をクライアントから隠蔽する。エラーを知るインターフェイスは提供するが、知ることを強制しない
  5. 災難時基金
    • メモリ枯渇の処理自体にメモリが要求される。あらかじめそのためにメモリを確保しておく

Captain Oates：自発的解放

プロセスによって重要度は違うし、コンポーネントごとに重要度は異なる。

より重要なタスクを失敗させるよりも、重要度の低いコンポーネントが使うメモリを犠牲にする メモリが不足した時にシステム中の全コンポーネントにメモリ状態の警告イベントをつうちする。警告の度合い（赤、黄、緑など）によってコンポーネントそれぞれで独立にメモリ解放や処理の縮小・停止などを行う。

イベント通知の仕組みがない場合は、各コンポーネントがポーリングを行う。

これは各コンポーネントでの規律を要する

Read-Only Memory：読み取り専用メモリ

実行可能コードや辞書などの静的な情報を読み取り専用メモリに格納する。 ROM は一般に製造が容易であり、安価で信頼性が高く、電力が経済的・・・など優れている点が多い

ROM は補助記憶装置へ保存し直す必要がないため早くメインメモリから削除できる。 補助記憶装置から値を取得しないため読み込みも早くなる 領域を共有できるためメモリ要求を削減できる

書き換え手順が必要なため保守が困難になる

実装

Hooks：フック

ROM だとデータを設定した後にバグが確認されても出荷されたものを上書きすることが困難

そこで書き込み可能な記憶装置中のフックを通して読み取り専用の情報にアクセスし、このフックを変更することによって、該当の情報が変更になったかのようにみせる

設計品質、保守性、拡張性が向上するが、フックを経由するため時間パフォーマンスとフックベクタのためのメモリ領域とフックの利用による信頼性を犠牲にする

同じ実行ファイルを複数のユーザーがそれぞれにカスタマイズして利用できる（emacs）

実装

kawasin73 commented 6 years ago

2章 Secondary Storage：補助記憶装置

利用可能な主記憶装置よりもメモリ要求が大きいとき、実行時の追加のメモリとして補助記憶装置を使う

シンプルだけどプログラマの規律が必要 -> ハードウェアあるいはオペレーティングシステムのサポートを必要とするかわりにプログラマの規律が少しだけでいい の順番で紹介される

Application Switching：アプリケーション切り替え

同時に実行されるのは1つのアプリケーションのみ。 システムを独立した実行可能プログラム群に分割し、一度に1つだけを実行させる。 そのほかのコンポーネントは実行しないか退避させる。

分割されたプログラムはそれぞれ別の言語で実装しても構わない。

OS はアプリケーションの切り替え（2つのアプリケーションが同時に存在しても一つを遅延させて実行する）をサポートしていることがある

実現方法

Data Files：データファイル

コードはメモリ上に収まるが、データがメモリ上に収まらない データをシーケンシャルに扱う 一度にには少量のデータだけを処理し、残りのデータは補助記憶装置上に保持する

一時的なクロスリファレンスを作成し、メモリ内インデックスとしてアクセスする

処理をいくつかのフェーズに分けて、それぞれ別のプログラムとして独立させることができる

Resource Files：リソースファイル

大量の構成データを管理する 読み取り専用のデータを補助記憶装置上のファイルに保存し、必要に応じてロードして破棄する

フォントや画像、ダイアログ、メッセージなど

プログラム中にハードコードするかわりにリソースファイルを使いメモリを削減。ファイルにランダムアクセスする。そのためにインデックス（典型的にはファイルの先頭）が必要。大抵は複数のリソースファイルに対応する

リソースファイルを実装する上での考慮点

Packages：パッケージ

オプション部分の多い大規模プログラムを扱う

プログラムをパッケージに分割し、必要とされた時点で各パッケージをロードする 動的ロードをサポートしている環境で実現できる

必要になるまでパッケージがロードされないため、稼働中に遅延が発生する可能性がある。リアルタイム運用には向かない。

差し替え可能であるのでセキュリティの問題もある

必要なもの

実装する際の考慮事項

パッケージの単位をワーキングセットという

Paging：ページング

メモリが無限に存在するかのように思わせる

Data Files の欠点

システムのコードとデータを補助記憶装置上に保持し、必要に応じてメインメモリとの間で転送する

メモリアクセスには局所性があるとき、小さなワーキングセットをもつだけで良いことが多い。

ページングの手法

デマンドページングが一般的であるが、仮想メモリを実現するシステムのサポートが必要

メモリの上限や境界を意識せずにプログラミングできる。

ページングを実装する時に考慮するべき事項

kawasin73 commented 5 years ago

3章 Compression：圧縮

冗長性の種類

圧縮技法の評価

Table Compression：テーブル圧縮

数多くの短い文字列を圧縮するのに適している

一般的な要素ほど少ないビット数を要求するよう、可変長のビット群に書く要素をエンコードする

シーケンシャルなアクセスの時間パフォーマンスは劣化しない。ランダムアクセスは劣化する。 テストをする必要がある

実装

Difference Coding：差分コーディング

データシーケンスによって使われるメモリを削減する

ストリームデータは途中へのランダムアクセスはほぼない。

各データ項目間の差分によってデータシーケンスを表現する

この2つを組み合わせることもできる

パフォーマンスはよく、リアルタイムレスポンスが保たれる サイズが削減されないこともある

Adaptive Compression：適応型圧縮

大規模データを保存するメモリ量を削減する。

圧縮対象のデータに応じて圧縮アルゴリズムを選ぶ。

gzip, jpeg, png ...

処理時間が大きくなる。一時メモリが必要となる

圧縮アルゴリズムはライブラリとしてオープンソースで手に入るため、実装はしないことが多い。

kawasin73 commented 5 years ago

4章 Small Data Structures：小規模データ構造

必要とされるオペレーションをサポートする最小のデータ構造を選ぶ

データ構造の設計

考慮事項

Packed Data：詰め込みデータ

最小のスペースだけを占めるよう、データ項目をこうぞうちゅうに埋め込む

メモリを削減する方法

位置調整されていないため CPU アクセスは遅くなる デフォルトではスペースよりも時間パフォーマンスを優先している メモリ消費が大きい部分で使うのがよい

Sharing：共有

情報を一度だけ格納し、それが必要とされる全ての箇所で共有する。変更されないデータに対して有効。ポインタでアクセスする。変更可能なインターフェイスを削除する

共有キャッシュを用いる。ユニークなキーが必要になる

Copy-on-Write：書き込み時コピー

変更が必要になるまでオブジェクトを共有し、変更が必要になった時点でコピーを作り、以降はそのコピーを使う

参照カウンタを持ち、参照カウンタが2以上で書き込みがあったときにコピーする

実装

Embedded Pointers：埋め込みポインタ

連結リスト構造

オブジェクトのコレクションによって使われるスペースを削減するためにコレクションを支えるポインタを各オブジェクトに埋め込む

トラバースは、再帰よりもイテレーションを使う

実装

Multiple Representations：多重表現

同じ情報を様々な方法で表現できる。最善の実装がない

個々の実装が共通のインターフェイスを満たすようにする。

実装方法

kawasin73 commented 5 years ago

5章 Memory Allocation：メモリ割り当て

要求を満たすことのできる最もシンプルなアロケーション技法を選ぶ

C, C++ の場合は、Variable Allocation よりも Memory Discard の方が使いやすい

Java などは Variable Allocation がデフォルト

固定アロケーションはリアルタイムレスポンスと時間パフォーマンスを向上させる

メモリアロケーションを設計する際に考慮するべき事項

Fixed Allocation：固定アロケーション

初期化の間にオブジェクトを事前アロケートし、決してメモリ不足に陥らないことを保証する。 アロケートする数は、ハードコードせずに定数に設定し変更可能にする

メモリ使用を正確に予測可能、アロケーション時間は一定、スペースのオーバーヘッドが最小、プログラマの労力を削減、テストが容易、外部フラグメンテーションの削減

最悪ケースの量をアロケートするため、平均的な量よりも大きい。内部フラグメンテーションする、スケーラビリティが下がる

実装

Variable Allocation：可変アロケーション

汎用ライブラリはクライアントの性質について前提を設けることができない

メモリ使用を最小限に抑えながらも柔軟なシステムをサポートするために、可変サイズのオブジェクトを必要な時点でアロケートならびにデアロケートする

オーバーヘッドがあり、また、予測ができない

実装

ほとんどのオブジェクト指向言語ではデフォルトで行われている

Memory Discard：メモリの一括破棄

動的アロケーションの遅いアロケーションを許容できないとき。一時的なワークスペースからオブジェクトをアロケートし、完了次第ワークスペースを破棄する。

メモリの解放はワークスペース単位で行う

スタックよりも長命になれる

システムの時間パフォーマンスが改善される 自動的なメモリ管理に頼る言語は一般に Memory Discardパターンを直接にはサポートしない

実装

Pooled Allocation：プールアロケーション

小さなオブジェクトを頻繁にアロケート、デアロケートする。

オブジェクト群のプールを事前アロケートし、使われていないオブジェクトをリサイクルする

オブジェクトのヘッダのためのメモリとフラグメンテーションがなくなる、一方でメモリの別の目的での再利用ができなくなる

Compaction：コンパクション

コンピュータメモリが線状に配置され、ポインタを通じてアクセスするためフラグメンテーションは発生する。 外部フラグメンテーションを解消するために、オブジェクト間での未使用スペースが排除されるようにメモリ内でオブジェクトを移動させる

移動させた後に該当のオブジェクトへのすべての参照が適切に更新されることを保証する。ポインタを全て書き換えるより、関節参照を使う

時間パフォーマンスの低下、予測できない。ただし、リアルタイムのようきゅうを満たすインクリメンタルコンパクションのアルゴリズムはある。

実装する上で考慮すること

Reference Counting：参照カウント

個々の共有オブジェクトについて参照の数をカウントし、その数がゼロになった時点で該当オブジェクトを削除する

コンポーネント間の結合を弱める

リアルタイムレスポンスが改善される 実行時オーバーヘッドが大きい（10 ~ 20%になることもある）

Garbage Collection：ガベージコレクション

共有オブジェクトを削除すべき時点を見極めるために、参照されていないオブジェクトを識別し、それらをデアロケートする

システムの処理を中断し、システム中のすべてのオブジェクト参照をたどる。

がルートとなる

トラバース中に以前と同じオブジェクトに遭遇した場合はそれ以下は調べる必要はない。

GC は通常の処理に対する時間的、空間的オーバーヘッドは無視できるほど小さい

しかし、処理中に大きな休止を招く可能性がある

kawasin73 commented 5 years ago

フォース