Feature #18619
Updated by eightbitraptor (Matt V-H) over 2 years ago
# Reverse the order of GC Compaction cursor movement
**Github PR: [https://github.com/ruby/ruby/pull/5637](https://github.com/ruby/ruby/pull/5637)**
## Summary
The current compaction algorithm works by walking up the heap until it finds a slot to fill and then asking "what object can I use to fill this slot"
This PR reverses the cursor movement to walk down the heap until it gets to a moveable live object and then asking "where is the best place to put this object"
This animation shows a very simplified view of what we mean by "reversing the cursor movement"
## Rationale
The current approach works well for a single heap containing fixed width slots because both empty and filled slots within that heap are a known and consistent size, and there is only a single set of scan/compact cursors to manage.
Now that the memory space contains multiple size pools, each containing their own heap and scan/compact cursors the current approach has some problems:
- **Moving objects between pools is hard**
Objects that are mutable, such as strings, can be made larger(eg. using `String#<<`). Currently, when this modification happens we have no way of moving the object to a larger size pool, so we fall back to using `malloc` to allocate the buffer. By doing this we lose the cache locality benefits that VWA provides.
The current compaction algorithm makes moving these objects hard. by starting with an empty slot of a known size, determining what to fill it with (an object from the same heap, or from a different heap that wants to move) would involve either more heap scans, or a data structure to keep track of resized objects that can move between pools.
- **Only the first size pool (40 byte slot_size) is being swept**
The current compaction algorithm uses a global flag attached to `rb_objspace`. When compaction is triggered, the flag is set true, and compaction starts scanning the size pools (starting with the smallest) until the scan/compact cursors have met.
As soon as the first size pool has finished compacting and the cursors have met, the current implementation assumes that compaction has finished, updates the references and disables the global compaction flag, resulting in no compaction of any size pools other than the smallest.
## Implementation
This PR implements an algorithm that flips the order in which we consider the scan and compact cursors. That is: Rather than discovering an empty slot and attempting to fill it, we discover an object that can move, and then find an appropriate place for it.
The outline of the new algorithm (in pseudo-Ruby) looks like this:
```
def find_destination_heap(slot)
# Future versions of this work will determine the most space
# efficient heap in which to move this object to. This version
# always keeps it within the same heap
slot.heap
end
def gc_compact
until all_cursors_met do
size_pools.each do |pool|
pool.heap.compact_cursor.each_slot do |slot|
if is_moveable?(slot)
destination_heap = find_destination_heap(slot)
until move(src: slot, dest: destination_heap.scan_cursor)
sweep(destination_page)
unless has_free_slots(destination_page)
increment_scan_cursor(destination_heap)
end
end
end
end
decrement_compact_cursor(pool.heap)
end
end
end
update_references
```
Some considerations of the new approach are:
- In this initial implementation the destination heap is always the same as the source heap. No movement between size pools is taking place. This is for backward compatibility with the existing compaction algorithm. _Movement between size pools will be added as a seperate feature_.
- We compact a single page from each pool in the loop rather than compacting one pool to completion and then moving to the next. This is to give objects that wish to move between pools chance to do so. If we compacted an entire heap before moving to the next, we risk filling the heap and not providing opportunity for objects in different heaps the chance to move into it.
## Measuring compaction
### Railsbench heap visualisation
We [wrote a tool to help visualise the heap](https://github.com/eightbitraptor/heapviz) before and after compaction.
We ran a [patched version of railsbench](https://github.com/eightbitraptor/railsbench/commit/482bdcf738464d3be4d14428a3739dbcf395e359) to dump the heap before and after compaction on master and this branch.
Colours in the visualisation correspond to different size pools. Pools are ordered from left to right - 40 bytes, 80 bytes, 160 bytes, 320 bytes. Empty slots are white, and pinned slots are coloured black.
Results are:
#### Before compaction (master)
#### After compaction (master)
#### Before compaction (this PR)
#### After compaction (this PR)
 
### Discourse benchmarks
We ran Discourse benchmarks for both master and this PR, with `GC.auto_compact=true` configured in `config/boot.rb`.
Benchmarks were run using
```
ruby script/bench.rb -i 100 -s
```
We can see a slight slowdown when using auto_compact on this branch when compared with master. This can be attributed to the extra work the compactor is now doing as it's compacting all 4 size pools rather than just the first one.
Raw results are as follows:
```
| | Master (auto-compact enabled) | mvh-vwa-compaction (auto-compact enabled) |
|-------------------------|-----------------------------------|-------------------------------------------|
| categories | | |
| 50 | 32 | 53 |
| 75 | 33 | 55 |
| 90 | 36 | 55 |
| 99 | 186 | 174 |
| home | | |
| 50 | 58 | 83 |
| 75 | 60 | 86 |
| 90 | 65 | 90 |
| 99 | 198 | 289 |
| topic | | |
| 50 | 35 | 36 |
| 75 | 35 | 39 |
| 90 | 36 | 55 |
| 99 | 185 | 175 |
| categories_admin | | |
| 50 | 35 | 40 |
| 75 | 55 | 55 |
| 90 | 57 | 57 |
| 99 | 168 | 65 |
| home_admin | | |
| 50 | 83 | 58 |
| 75 | 87 | 63 |
| 90 | 92 | 83 |
| 99 | 243 | 263 |
| topic_admin | | |
| 50 | 35 | 35 |
| 75 | 35 | 36 |
| 90 | 36 | 36 |
| 99 | 160 | 162 |
| timings | load_rails: 2205 | load_rails: 2116 |
| rss_kb | 303556 | 350344 |
| pss_kb | 293186 | 340314 |
| ruby-version | 3.2.0-p-1 | 3.2.0-p-1 |
| processor0 | AMD Ryzen 5 3600 6-Core Processor | AMD Ryzen 5 3600 6-Core Processor |
| physicalprocessorcount: | 1 | 1 |
| memorysize: | 15.61 GiB | 15.61 GiB |
| kernelversion | 5.16.11 | 5.16.11 |
| virtual | physical | physical |
| architecture | x86_64 | x86_64 |
| operatingsystem | Archlinux | Archlinux |
```
## What's next
* Discourse is showing slightly higher memory usage on this branch when compaction is enabled. This could be related to the slightly less efficient compaction results on the smallest size pool (see the differences in the Railsbench heap maps). We will be improving this algorithm to improve performance
* Implement cross size pool movement, as this version of the algorithm still only moves objects within their existing size pool