<p>I'm implementing a moving garbage collection algorithm, but I don't know how the GC can find an object's address after it has been moved. I thought of 3 options:</p>
<h3>Forwarding Pointer</h3>
<p>The first way is to use forwarding pointers.</p>
<pre class="lang-rust prettyprint-override"><code>struct Gc {
    ptr_object: usize,
    ptr_forward: usize,
    gc_marks: FLAGS,
    size: usize,
}
</code></pre>
<p>Each moved object leaves a forwarding pointer in place. When a pointer to be updated points to an already-moved object, the forward address is used. This has two problems:</p>
<ol>
<li><p>Keeping the forwarding pointer means this block cannot be recycled.  The block will be recycled only after all the elements in the block are recycled. The space utilization rate is low, which may lead to fragmentation.</p>
</li>
<li><p>Another problem is that the block does not know whether there are live objects inside, the block is just a segment of bytes.</p>
</li>
</ol>
<h3>Tagged Forwarding Pointer</h3>
<p>This is a compressed form of the previous case. Rather than storing a forward pointer in every object, a status bit is used.</p>
<pre class="lang-rust prettyprint-override"><code>struct Gc {
    ptr: usize,
    gc_marks: FLAGS,
    // forward if size is 0, since size at least sizeof(gc_head)
    size: Option&lt;NonZeroUsize&gt;,
}
</code></pre>
<h3>Forwarding Table</h3>
<p>The third way is a &quot;forwarding table&quot;, which recycles the entire block, but if the surviving object is moved, then its new address is recorded in the forwarding table.</p>
<p>The problem is: how does the GC know whether an object has already been recorded in the forwarding table? The GC must look up all pointers in the forwarding table, which may be very inefficient.</p>
<h2>Question</h2>
<p>I don't know which way is better, or if there's a better approach. Is there any other way to balance efficiency and space utilization and cache continuity?</p>

<garbage-collection>
How to find the updated address of an object in a moving garbage collector?
<p>There is another option, each object reference is a pointer/index into an array of pointers (plus GC meta data as needed).</p>
<p>When the program needs to dereference the reference it will do a lookup in the table. And when an object moves you update only that pointer in the table and the entry in that table remains in place.</p>
<p>This can still create fragmentation in that table but any holes can get filled by any newly allocated object. So the end result is that the table grows to a high water mark and then remains stable.</p>
<p>This is like the forwarding table but it is always used.</p>

CC BY-SA 4.0
2023-06-30T11:25:19.633Z
2023-06-30T11:25:19.633Z
ratchet freak
CC BY-SA 4.0
2023-07-01T04:36:48.223Z
This reminds me of the way memory handles were used in the original MacOS.
Barmar
<p>The standard approach differs depending on which type of moving collector you’re implementing. Since your question doesn’t specify, I’ll provide the usual strategy for the two simplest standard archetypes of a moving garbage collector.</p>
<h2>2-space copying collector</h2>
<p>The simplest moving garbage collector is known as a <em>2-space copying collector</em>, usually implemented via <a href="https://en.wikipedia.org/wiki/Cheney%27s_algorithm" rel="noreferrer">Cheney’s algorithm</a>. In this approach, two separate heap areas are used, and at each collection, the objects are copied from one area to the other. This means the system needs twice as much memory as is actually taken up by the heap, but collection is very fast.</p>
<p>In this approach, the “forwarding pointer” strategy you describe is used. There is no challenge to knowing when the block can be recycled because once a collection takes place, all allocations have been evacuated to the new heap, and <em>all</em> blocks from the old heap can be recycled. This algorithm also has no fragmentation issues because it is inherently compacting: objects are densely copied to the new heap without gaps.</p>
<h2>Mark–compact collector</h2>
<p>Traditional mark-and-sweep is nonmoving, but a standard variation is a <a href="https://en.wikipedia.org/wiki/Mark%E2%80%93compact_algorithm" rel="noreferrer">mark–compact collector</a>, which provides a compromise between a 2-space collector and mark-and-sweep. It is slower than a 2-space collector because it requires several passes over the heap, but it avoids the memory overhead of maintaining two separate heaps, and it avoids the memory fragmentation problems of mark-and-sweep.</p>
<p>A common mark–compact collection algorithm is known as the Lisp 2 algorithm. Collection proceeds in three passes over the heap:</p>
<ol>
<li><p>First, each live object is assigned a <em>destination</em> address, which is stored in an extra field reserved in every object for this purpose. A single variable can be used to keep track of the next free destination address, advanced as necessary as addresses are assigned.</p>
</li>
<li><p>Second, all pointers contained within heap objects are updated to the assigned destination addresses stored within the referenced heap objects. This step essentially results in a very large number of briefly-dangling pointers.</p>
</li>
<li><p>Finally, all objects are moved to their intended destinations, so the pointers updated in the previous step now actually point to their intended targets.</p>
</li>
</ol>
<p>This algorithm is very easy to implement, but it does require an additional word in every heap object to store the destination address. Since it is compacting (it’s in the name!), fragmentation is not an issue.</p>

CC BY-SA 4.0
2023-06-30T06:50:01.100Z
2023-06-30T06:55:19.947Z
2023-06-30T06:55:19.947Z
Alexis King
CC BY-SA 4.0
2023-12-13T23:06:07.840Z
The space overhead of the extra pointers for a mark-and-compact algorithm seems pretty modest compared with only being able to use half the heap as in a two-space collector, and the time overhead seems fairly modest given that the extra space the mark-and-compact heap would have to play with would greatly reduce the number of compactions required.
supercat
# How to find the updated address of an object in a moving garbage collector?
Posted by: username_0 on 2023-06-30
I'm implementing a moving garbage collection algorithm, but I don't know how the GC can find an object's address after it has been moved. I thought of 3 options:
Forwarding Pointer
The first way is to use forwarding pointers.
struct Gc {
    ptr_object: usize,
    ptr_forward: usize,
    gc_marks: FLAGS,
    size: usize,
}

Each moved object leaves a forwarding pointer in place. When a pointer to be updated points to an already-moved object, the forward address is used. This has two problems:

Keeping the forwarding pointer means this block cannot be recycled.  The block will be recycled only after all the elements in the block are recycled. The space utilization rate is low, which may lead to fragmentation.

Another problem is that the block does not know whether there are live objects inside, the block is just a segment of bytes.


Tagged Forwarding Pointer
This is a compressed form of the previous case. Rather than storing a forward pointer in every object, a status bit is used.
struct Gc {
    ptr: usize,
    gc_marks: FLAGS,
    // forward if size is 0, since size at least sizeof(gc_head)
    size: Option,
}

Forwarding Table
The third way is a "forwarding table", which recycles the entire block, but if the surviving object is moved, then its new address is recorded in the forwarding table.
The problem is: how does the GC know whether an object has already been recorded in the forwarding table? The GC must look up all pointers in the forwarding table, which may be very inefficient.
Question
I don't know which way is better, or if there's a better approach. Is there any other way to balance efficiency and space utilization and cache continuity?
**Tags:** garbage-collection
---
## 2 answers
### Answer by username_3 on 2023-06-30. Score: 7 | Accepted answer
The standard approach differs depending on which type of moving collector you’re implementing. Since your question doesn’t specify, I’ll provide the usual strategy for the two simplest standard archetypes of a moving garbage collector.

## 2-space copying collector

The simplest moving garbage collector is known as a *2-space copying collector*, usually implemented via [Cheney’s algorithm](https://en.wikipedia.org/wiki/Cheney%27s_algorithm). In this approach, two separate heap areas are used, and at each collection, the objects are copied from one area to the other. This means the system needs twice as much memory as is actually taken up by the heap, but collection is very fast.

In this approach, the “forwarding pointer” strategy you describe is used. There is no challenge to knowing when the block can be recycled because once a collection takes place, all allocations have been evacuated to the new heap, and *all* blocks from the old heap can be recycled. This algorithm also has no fragmentation issues because it is inherently compacting: objects are densely copied to the new heap without gaps.

## Mark–compact collector

Traditional mark-and-sweep is nonmoving, but a standard variation is a [mark–compact collector](https://en.wikipedia.org/wiki/Mark%E2%80%93compact_algorithm), which provides a compromise between a 2-space collector and mark-and-sweep. It is slower than a 2-space collector because it requires several passes over the heap, but it avoids the memory overhead of maintaining two separate heaps, and it avoids the memory fragmentation problems of mark-and-sweep.

A common mark–compact collection algorithm is known as the Lisp 2 algorithm. Collection proceeds in three passes over the heap:

1. First, each live object is assigned a *destination* address, which is stored in an extra field reserved in every object for this purpose. A single variable can be used to keep track of the next free destination address, advanced as necessary as addresses are assigned.
2. Second, all pointers contained within heap objects are updated to the assigned destination addresses stored within the referenced heap objects. This step essentially results in a very large number of briefly-dangling pointers.
3. Finally, all objects are moved to their intended destinations, so the pointers updated in the previous step now actually point to their intended targets.

This algorithm is very easy to implement, but it does require an additional word in every heap object to store the destination address. Since it is compacting (it’s in the name!), fragmentation is not an issue.
> **Comments:**
> **username_4** (2023-12-13): The space overhead of the extra pointers for a mark-and-compact algorithm seems pretty modest compared with only being able to use half the heap as in a two-space collector, and the time overhead seems fairly modest given that the extra space the mark-and-compact heap would have to play with would greatly reduce the number of compactions required.  
---
### Answer by username_1 on 2023-06-30. Score: 2
There is another option, each object reference is a pointer/index into an array of pointers (plus GC meta data as needed).

When the program needs to dereference the reference it will do a lookup in the table. And when an object moves you update only that pointer in the table and the entry in that table remains in place.

This can still create fragmentation in that table but any holes can get filled by any newly allocated object. So the end result is that the table grows to a high water mark and then remains stable.

This is like the forwarding table but it is always used.
> **Comments:**
> **username_2** (2023-07-01): This reminds me of the way memory handles were used in the original MacOS.  
---
