省メモリプログラミング

省メモリプログラミング

パターン概要

一般技法

Small Architecture システム中の複数のコンポーネント間での強調作用を必要とするメモリ節減技法
Secondary Storage RAMに対する補助装置としてのディスク(あるいはそれに相当するもの)の利用
Compression データを圧縮することによってデータサイズを縮小するための処理ベースの技法
Small Data Structures メモリ使用を工夫して削減するデータ構造とアルゴリズム
Memory Allocation 構造化されていない利用可能メモリの「原始スープ」からデータ構造を生成するためのメカニズムと、それをプログラムが必要としなくなった時点で返却するためのメカニズム

パターンが扱うフォース

フォースとは、

  • その解法が満たすべき要件
  • その解法が克服すべき制約
  • その解法が備えるべき望ましい特性

など、解決に際して考慮されるべき問題の任意の局面である。

重要なフォースの要約
メモリ要求 そのパターンは、システムの実行に必要とされるメモリの絶対量を削減するか?
メモリ予測性 そのパターンは、システムが必要とするであろうメモリ量を事前に予測することを容易にするか?
時間パフォーマンス そのパターンは、システムの実行速度を向上させる傾向にあるか?
リアルタイムレスポンス そのパターンは、一般的にはプログラムの実行時パフォーマンスを予測可能にすることによって、イベントに対する応答待ち時間を短縮するか?
スタートアップ時間 そのパターンは、システムがプログラムの起動要求を受け取ってからプログラムが実行を開始するまでの時間を短縮するか?
ローカル vs グローバル そのパターンは、アプリケーションの異なる部分部分を相互に独立させることによってカプセル化を促進する傾向にあるか?
保守性 そのパターンは、設計品質の向上を促進するか? その後のシステムに対する変更を容易にするか?
プログラマの労力 そのパターンは、そのパターンは、ある特定のシステムを構築するための総プログラマ労力を削減するか?
テストコスト そのパターンは、アプリケーション開発における総テスト労力を削減するか?

削減、再利用、リサイクル

環境問題の専門家は、自然環境に対する人類文明の影響を小さくするための3つの戦略を確認している。

それは「削減」「再利用」「リサイクル」である。

この中で最も有効な戦略は、「削減」である。

なぜなら、「削減」されれば、その後の後始末を考える必要がない。

それとは逆に、リサイクルは効力が最も小さい。

大量のエネルギー消費と、新たに産出するためのエネルギーが必要とされるからだ。

メモリについても、同様のことが言える。

削減するパターン

「Packed Data」「Sharing」「Compression」などのパターンは、データサイズを縮小すると同じに冗長性を排除し、

必要とするメモリの絶対量を削減する。

「Secondary Storage」「Read-Only Memory」パターンは、代替の記憶装置を使うことによって、RAMメモリに対する要求を削減する。

再利用するパターン

「Fixed Allocation」「Pooled Allocation」で確保されたメモリは、たいてい同じ型の書く多くの異なるオブジェクト群を次から次へと格納するのに再利用される。

「Hooks」は、既存の読み取り専用のコードを(置き換えるのではなく)再利用することを可能にする。

リサイクルするパターン

「Variable Allocation」「Reference Counting」「Compaction」「Garbage Collection」「Captain Oates」は、同じメモリを大きく異なる用途で何度も使うことを可能にする。

Small Architecture : 小規模アーキテクチャ

システム全体としてのメモリ使用を制限するには?

⇒すべてのコンポーネントが自身のメモリ使用に責任を負うようにする。

Memory Limit : 限定メモリ

競合する複数のコンポーネント間でメモリを配分するには?

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

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

コンポーネントインターフェースのメモリオーバーヘッドを削減するには?

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

Partial Failure : 部分的失敗

予期できないメモリ要求に対処するには?

⇒メモリ不足になってもシステムが安全な状態に保たれることを保障する。

Captain Oates : 自発的解放

メモリに対する最も重要な要求を満たすには?

⇒より重要なタスクを失敗させるよりも、重要度の低いコンポーネントが使うメモリを犠牲にする。

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

読み取り専用のコードとデータをどうできるか?

⇒読み取り専用のコードとデータを読み取り専用メモリに格納する。

Hooks : フック

読み取り専用の記憶装置中の情報を変更するには?

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


Secondary Storage : 補助記憶装置

主記憶装置が足りなくなった場合に何ができるか?

⇒実行時の追加メモリとして補助記憶装置を使う。

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

数多くの異なる機能を提供するシステムのメモリ要求を削減するには?

⇒システムを独立した実行可能プログラム群に分割し、一度に1つだけを実行させる。

Data Files : データファイル

メインメモリにデータが収まらない場合に何ができるか?

⇒一度には少量のデータだけを処理し、残りデータは補助記憶装置上に保持する。

Resource Files : リソースファイル

大量の構成データを管理するには?

⇒構成データを補助記憶装置上に保持し、必要に応じてロードならびに破棄する。

Package : パッケージ

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

⇒プログラムをパッケージに分割し、必要とされた時点で各パッケージをロードする。

Paging : ページング

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

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

Compression : 圧縮

小さなメモリ中に大量のデータを収納するには?

⇒圧縮した形を使うことによって、要求されるメモリ量を削減する

Table Compression : テーブル圧縮

数多くの短い文字列を圧縮するには?

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

Difference Coding : 差分コーディング

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

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

Adaptive Compression : 適応型圧縮

大規模データを格納するのに要求されるメモリを削減するには?

⇒適応型の圧縮アルゴリズムを使う

Small Data Structures : 小規模データ構造

データ用に必要とされるメモリを削減するには?

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

Packed Data : 詰め込みデータ

データ構造を保持する上で要求されるメモリを削減するには?

⇒最小のスペースだけを占めるよう、データ項目を構造中に詰め込む。

Sharing : 共有

同じ情報の多重複製を回避するには?

⇒情報を一度だけ格納し、それが必要とされるすべての箇所で共有する。

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

他のクライアントに影響を与えることなく共有オブジェクトを変更するには?

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

Embedded Pointers : 埋め込みポインタ

オブジェクトのコレクションによって使われるスペースを削減するには?

⇒コレクションを支えるポインタを各オブジェクトの中に埋め込む。

Multiple Representations : 多重表現

オブジェクトの複数の異なる実装をサポートするには?

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

Memory Allocation : メモリ割り当て

データ構造を保持するためにメモリをアロケートするには?

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

  • Fixed Allocation : システムの起動時にオブジェクトを事前アロケートする
  • Memory Discard : 一時オブジェクトを(多くの場合スタックに)グループ化してアロケートする
  • Variable Allocation : 必要に応じて動的にヒープからオブジェクトをアロケートする
  • Pooled Allocation : 事前アロケートされたメモリスペースから動的にオブジェクトをアロケートする

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

  • フラグメンテーション
  • メモリ枯渇

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

決してメモリ不足にならないことを保障するには?

⇒初期化の間にオブジェクトを事前アロケートする。

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

使われない空きスペースの発生を回避するには?

⇒可変サイズのオブジェクトを必要な辞典でアロケートならびにデアロケートする。

Memory Discard : メモリの一括破棄

一時的なオブジェクトをアロケートするには?

⇒一時的なワークスペースからオブジェクトをアロケートし、完了次第、ワークスペースを破棄する。

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

同種のオブジェクトを数多くアロケートするには?

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

Compaction : コンパクション

フラグメンテーションによって失われたメモリを取り戻すには?

⇒オブジェクト間での未使用スペースが排除されるよう、メモリ内でオブジェクトを移動させる。

Reference Counting : 参照カウンタ

共有オブジェクトを削除すべき時点を見極めるには?

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

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

共有オブジェクトを削除すべき時点を見極めるには?

⇒参照されていないオブジェクトを識別し、それらをデアロケートする。