Feature #18619: Reverse the order of GC Compaction cursor movement

• Status: Closed
• Assignee: -
• Target version: -

[eightbitraptor (Matt V-H)]

Reverse the order of GC Compaction cursor movement

Github PR: 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 before and after compaction.

We ran a patched version of railsbench 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

[Eregon (Benoit Daloze)]

From the After compaction (this PR) image, it seems some objects of the leftmost heap are not moved, even though they are not pinned, is that a bug? (not a problem for After compaction (master))

[Dan0042 (Daniel DeLorme)]

Any idea why this PR results in so many more pinned slots?

[eightbitraptor (Matt V-H)]

Thanks for the quick feedback folks.

Eregon (Benoit Daloze) wrote in #note-1:

From the After compaction (this PR) image, it seems some objects of the leftmost heap are not moved, even though they are not pinned, is that a bug? (not a problem for After compaction (master))

@tenderlovemaking (Aaron Patterson) and I have investigated this and we believe we've found a bug in the heapviz library we wrote to visualise the heap. I am currently fixing the tooling and then will regenerate the heap dumps. Until we've done that I'm not able to confirm what's causing the discrepancy between the branches.

Dan0042 (Daniel DeLorme) wrote in #note-2:

Any idea why this PR results in so many more pinned slots?

This was a bug in my implementation, which I've recently fixed - I'll regenerate the heap maps, once I've fixed the bug that we found when investigating the above issue.

[eightbitraptor (Matt V-H)]

• Description updated (diff)

[eightbitraptor (Matt V-H)]

eightbitraptor (Matthew Valentine-House) wrote in #note-3:

Thanks for the quick feedback folks.

Eregon (Benoit Daloze) wrote in #note-1:

From the After compaction (this PR) image, it seems some objects of the leftmost heap are not moved, even though they are not pinned, is that a bug? (not a problem for After compaction (master))

@tenderlovemaking (Aaron Patterson) and I have investigated this and we believe we've found a bug in the heapviz library we wrote to visualise the heap. I am currently fixing the tooling and then will regenerate the heap dumps. Until we've done that I'm not able to confirm what's causing the discrepancy between the branches.

After fixing the bug in heapviz. I determined that there was a bug in the way we were handling unmoveable objects that resulted in undesired scan cursor movement resulting in empty pages. This is now fixed on the branch, and the post-compaction heap dump images have been updated.

Thanks for pointing this out @Eregon (Benoit Daloze)

[eightbitraptor (Matt V-H)]

• Status changed from Open to Closed

Applied in changeset git|76572e5a7fc0ffde6501fd9a8c034bb621f11688.

---

[Feature #18619] Reverse the order of compaction movement

This commit changes the way compaction moves objects and sweeps pages in
order to better facilitate object movement between size pools.

Previously we would move the scan cursor first until we found an empty
slot and then we'd decrement the compact cursor until we found something
to move into that slot. We would sweep the page that contained the scan
cursor before trying to fill it

In this algorithm we first move the compact cursor down until we find an
object to move - We then take a free page from the desired destination
heap (always the same heap in this current iteration of the code).

If there is no free page we sweep the page at the sweeping_page cursor,
add it to the free pages, and advance the cursor to the next page, and
try again.

We sweep one page from each size pool in this way, and then repeat that
process until all the size pools are compacted (all the cursors have
met), and then we update references and sweep the rest of the heap.