理論的には、はい...可能です。しかし、GC には問題があります。ガベージを収集するには、メモリに格納されているデータのレイアウトを知る必要があり、メモリ ブロックが使用されているかどうかを示すデータも格納する必要があります...しかし、レイアウトランタイムは型キャストを行うためにオブジェクトの型 (つまり、メモリ レイアウト) を知る必要があるため、情報はランタイムと共有されます。
GC はどのように機能しますか?
GC は、認識しているルート オブジェクトの読み取りを開始します。すべての参照を取得し、それらをin-useとしてマークします。これらの参照されたオブジェクトごとに、レイアウトを取得し、これらのオブジェクトからさらに参照を読み取り、使用中としてマークします...そして、参照がなくなるまでこのプロセスが続きます。
注: タイプ情報とレイアウト情報を同じ意味で使用しています。
例：
Imagine we have some object layouts:
====================================
A: { int, object, double, object }
B: { object, object }
C: { int }
Memory Data:
============
Now we need to describe what is in memory.
The following list is composed of memory positions,
and the data contained in each position.
There are 2 kinds of notation I will use:
- Address: ROOT[ list-of-root-references ]
- Address: type-identifier { object-data }
Note that each object can span multiple memory
positions from the first one.
e.g. 90: B { 0, 0 } -- this reads as
"stored at address 90: type-identifier of B followed by raw data { 0, 0 }"
- A reference is represented by a number,
that point to the memory address of the pointed object.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 } There is a self-reference here!
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 } Note that 0 is a null reference!
The GC need to know the layout of each object.
Otherwise it wouldn't be abled to tell
what knid of information is stored in each memory position.
Running the GC:
===============
Garbage collecting steps, to clean the memory described above:
Step 1: Get ROOT references: 2, 3, 9 and mark as 'in-use'
Step 2: Get references from 2, 3 and 9: 3, 6, 7. Note that 0 is a null reference!
Step 3: Get references from 3, 6 and 7: 6, 7, 8, and mark them.
Step 4: Get references from 6, 7, 8, and mark them: only 8!
Step 5: Get references from 8... it has none! We are finished with marking objects.
Step 6: Delete unmarked objects.
This shows what happened in each step with each object stored in the memory.
Step -> 1 2 3 4 5
Memory
20 x
30 x x
40 DELETE
50 DELETE
60 x x
70 x x
80 x x
90 x
私が説明したのは、非常に基本的な GC アルゴリズムです。
トライカラーのマーキングを見てください...それは本当に素晴らしいです! これが、実際の最新の GC の作成方法です。
ガベージ コレクション (コンピューター サイエンス) - いくつかの最新の GC 方法論について説明します。
しかし... レイアウトに関する情報はどこに保存されているのでしょうか?
GC とランタイムの両方に影響するため、この質問は重要です。高速な型キャストを行うには、型情報を参照の近く、または割り当てられたメモリの近くに配置する必要があります。割り当てられたメモリ ブロックのカタログに型情報を格納することも考えられますが、その場合は、オブジェクトを削除する必要がある場合に new 演算子や GC と同じように、型キャストがカタログにアクセスする必要があります。
参照の近くにレイアウト情報を格納すると、同じオブジェクトへのすべての参照で、ポインタ自体とともに同じ情報が繰り返されます。
例：
To represent the memory data I will introduce the following notation:
- Address: { object-data } -- this time object type is not at the begining!
- A reference is represented by a type-identifier and an address-number,
that point to the memory address of the pointed object,
in the following format: type/number...
e.g. A/20 -- this reads as: "at address 20, there is an object of type A"
Note that: 0/0 is a null reference,
but it still requires space to store the type.
The memory would look like this:
1: ROOT[ B/90, A/20, B/30 ]
20: { 1236, B/30, 0.5, C/60 }
30: { C/60, A/70 }
40: { 1237 }
50: { 1238, A/20, 0.8, A/50 }
60: { 1234 }
70: { 1234, 0/0, 0.7, C/80 }
80: { 1235 }
90: { 0/0, 0/0 }
割り当てられたメモリ ブロックの近くにレイアウト情報を格納する場合は、それで問題ありません。高速で、レイアウト情報の繰り返しを回避します。
例：
The memory looks like the first sample:
*This is the same notation used at the begining of this answer.
1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }
これまでのところ、とてもいいです...しかし、今は共有メモリが必要です。
最初に気付くのは、割り当てられたメモリの近くにレイアウト情報を保存できなくなったことです。
共有メモリを持つ配列を想像してください。
例：
I'll introduce a new notation for arrays:
type-identifier < array-length >
1: ROOT[ 20, 31 ] -- pointer 31 is invalid, destination has no type-identifier.
20: INT<5> -- info about layout of the next memory data (spans by 10 memory units)
30: 2
31: 3 -- should have type-identifier, because someone
32: 5 is pointing here!! Invalid memory!!
33: 7
34: 11
代わりに、ポインターの横にレイアウト情報を配置することもできます。共有メモリ配列が可能になりました:
例：
1: ROOT[ INT<5>/30, INT<2>/31 ]
30: 2
31: 3
32: 5
33: 7
34: 11
このアプローチでは、どこでもレイアウト情報を繰り返さなければならないことを思い出してください...しかし、ここでのポイントは、使用するメモリを少なくすることですよね??? ただし、メモリを共有するには、レイアウト データ/ポインタを格納するためにより多くのメモリが必要です。ドーナツはまだありません。=(
希望は 1 つだけです。実行時の機能を低下させましょう!
これが私の答えです-どのようにそれが可能だと思います=>
メモリ割り当てカタログを使用して型情報を保存するのはどうですか?
これを行うことはできますが、その場合、動的キャストが影響を受け、GC 自体も影響を受けます。GC はオブジェクトを削除するためだけにメモリ カタログにアクセスする必要があると説明したことを思い出してください。これで、単に削除するだけでなく、参照を見つけるたびにカタログにアクセスする必要があります。ああ、神様！！これにより、GC のパフォーマンスが低下し、ランタイムのパフォーマンスも低下します。コストが高すぎると思います！
<= これが私の答えです
しかし...ランタイムが動的キャストをサポートしていない場合はどうなりますか? コンパイラがコンパイル時に型に関するすべてを知っている場合... GCは存在しません...型に関する情報が必要です.
簡単でスマートなソリューションは見えません。
たぶん私はただ間違っているだけです。しかし、これまで以上に良い方法を想像することはできません。最新の GC はこれよりもさらに複雑です... ここでは基本的なことだけを取り上げましたが、最新の GC は他の方法、つまり他のより信頼性の高い方法で最適化していると思います。
その他の参照:
http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
http://www.memorymanagement.org/glossary/t.html
http://www.cs.purdue.edu/homes/sbarakat/cs456/gc-2.pdf
Tri-Color Incremental Updating GC: 各スタックを 2 回スキャンする必要がありますか?