Editing Tracing garbage collection (section)

=== Moving vs. non-moving ===
Once the unreachable set has been determined, the garbage collector may simply release the [[unreachable object]]s and leave everything else as it is, or it may copy some or all of the reachable objects into a new area of memory, updating all references to those objects as needed. These are called "non-moving" and "moving" (or, alternatively, "non-compacting" and "compacting") garbage collectors, respectively.

At first, a moving algorithm may seem inefficient compared to a non-moving one, since much more work would appear to be required on each cycle. But the moving algorithm leads to several performance advantages, both during the garbage collection cycle itself and during program execution:
* No additional work is required to reclaim the space freed by dead objects; the entire region of memory from which reachable objects were moved can be considered free space. In contrast, a non-moving GC must visit each unreachable object and record that the memory it occupied is available.
* Similarly, new objects can be allocated very quickly. Since large contiguous regions of memory are usually made available by a moving GC, new objects can be allocated by simply incrementing a 'free memory' pointer. A non-moving strategy may, after some time, lead to a heavily [[fragmentation (computer)|fragmented]] heap, requiring expensive consultation of "free lists" of small available blocks of memory in order to allocate new objects.
* If an appropriate traversal order is used (such as cdr-first for list [[cons]]es), objects can be moved very close to the objects they refer to in memory, increasing the chance that they will be located in the same [[cache line]] or [[virtual memory]] page. This can significantly speed up access to these objects through these references.

One disadvantage of a moving garbage collector is that it only allows access through references that are managed by the garbage collected environment, and does not allow [[pointer arithmetic]]. This is because any pointers to objects will be invalidated if the garbage collector moves those objects (they become [[dangling pointer]]s). For [[interoperability]] with native code, the garbage collector must copy the object contents to a location outside of the garbage collected region of memory. An alternative approach is to ''pin'' the object in memory, preventing the garbage collector from moving it and allowing the memory to be directly shared with native pointers (and possibly allowing pointer arithmetic).<ref>{{cite web |url=https://docs.microsoft.com/en-us/dotnet/framework/interop/copying-and-pinning |title=Copying and Pinning |work=[[Microsoft Docs]] |access-date=2022-04-25}}</ref>