20,741
edits
How the Nasal GC works: Difference between revisions
Jump to navigation
Jump to search
m
→Pool storage
m (→Mark/Sweep) |
m (→Pool storage) |
||
| Line 22: | Line 22: | ||
{{#ev:youtube|rp8PvFvSO_c|600|Lecture on GC (45 minutes)}} | {{#ev:youtube|rp8PvFvSO_c|600|Lecture on GC (45 minutes)}} | ||
= Mark/Sweep = | |||
When using a mark-and-sweep collector, unreachable objects are not immediately reclaimed. Instead, garbage is allowed to accumulate until all available memory has been exhausted. When that happens, the execution of the program is suspended temporarily while the mark-and-sweep algorithm collects all the garbage. Once all unreferenced objects have been reclaimed, the normal execution of the program can resume. | |||
Obviously, the main disadvantage of the mark-and-sweep approach is the fact that that normal program execution is suspended while the garbage collection algorithm runs. In particular, this can be a problem in a program that must satisfy real-time execution constraints (like a flight simulator). For example, an interactive application that uses mark-and-sweep garbage collection becomes unresponsive periodically. | |||
The mark-and-sweep algorithm is called a tracing garbage collector because is traces out the entire collection of objects that are directly or indirectly accessible by the program. The objects that a program can access directly are those objects which are referenced by local variables on the processor stack as well as by any static variables that refer to objects. In the context of garbage collection, these variables are called the roots . An object is indirectly accessible if it is referenced by a field in some other (directly or indirectly) accessible object. An accessible object is said to be live . Conversely, an object which is not live is garbage. | |||
The mark-and-sweep algorithm consists of two phases: In the first phase, it finds and marks all accessible objects. The first phase is called the mark phase. In the second phase, the garbage collection algorithm scans through the heap and reclaims all the unmarked objects. The second phase is called the sweep phase. | |||
The mark/sweep algorithm can also be easily expressed in Nasal tself: | |||
<syntaxhighlight lang="php"> | |||
var garbageCollect = func (roots) { | |||
foreach(var root; roots) { | |||
mark(root); | |||
} | |||
sweep(); | |||
} | |||
</syntaxhighlight> | |||
The mark() function would just recursively check (i.e. calling itself) if the "marked" flag is set or not, and make sure to set the mark bit for all referenced objects: | |||
<syntaxhighlight lang="php"> | |||
var mark = func (obj) { | |||
if (!obj.marked) { | |||
obj.marked=1; | |||
foreach( var referenced; referenced_by(obj) ) | |||
mark(referenced); | |||
} | |||
} | |||
</syntaxhighlight> | |||
Finally, the sweep() function (reap() in the Nasal GC), will free all unreachable objects and reclaim the memory: | |||
<syntaxhighlight lang="php"> | |||
var sweep = func { | |||
foreach(var obj; allocated_objects) { | |||
if (obj.marked) obj.marked=0; | |||
else reclaim(obj); | |||
} | |||
} | |||
</syntaxhighlight> | |||
Nasal's implementation of sweep() ( called reap() ) works such that it is always executed for a handful of different type-specific memory pools. In addition, it also makes sure to allocate new memory if required. | |||
= Pool storage = | = Pool storage = | ||