Issue #20022 has been updated by peterzhu2118 (Peter Zhu).

Secondly, it compacts twice; once in order of ascending size pool, and once descending. This means that we are guaranteed to be able to move everything we want to move into a size pool before we start advancing that pool's own compact cursor.

If we figure out the optimal size of every object and we set the heap to size `(optimal_size * 2) + 1`, it should guarantee that every object is moved before the cursors meet. Then, I think, we should only need to compact once. ---------------------------------------- Bug #20022: GC.verify_compaction_references does not actually move all objects https://bugs.ruby-lang.org/issues/20022#change-105416 * Author: kjtsanaktsidis (KJ Tsanaktsidis) * Status: Open * Priority: Normal * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN ---------------------------------------- While debugging https://bugs.ruby-lang.org/issues/20021, I ran into a separate issue which I figured was worth resolving whilst I had it in my head. The intention of GC.verify_compaction_references is, I believe, to force every single movable object to be moved, so that it's possible to debug native extensions which not correctly updating their references to objects they mark as movable (if this is _not_ the case, you can stop reading now and accept my apologies!) To do this, it doubles the number of allocated pages for each size pool, and sorts the heap pages so that the free ones are swept first; thus, every object in an old page should be moved into a free slot in one of the new pages. This worked fine until movement of objects between size pools during compaction was implemented. That causes some problems for verify_compaction_references: - We were doubling the number of pages in each size pool, but actually if some objects need to move into a different pool, there's no guarantee that they'll be enough room in that one. - It's possible for the sweep & compact cursors to meet in one size pool before all the objects that want to move into that size pool from another are processed by the compaction. You can see these problems by changing some of the movement tests in test_gc_compact.rb to try and move e.g. 50,000 objects instead of 500 (by changing `HASH_COUNT`); the test is not able to actually move all of the objects in a single compaction run. What I implemented in this PR (https://github.com/ruby/ruby/pull/9041) is two things: - Firstly, it examines every object and determine where it wants to be compacted into; we use this information to calculate the desired number of pages to add to each size pool. - Secondly, it compacts twice; once in order of ascending size pool, and once descending. This means that we are guaranteed to be able to move everything we want to move into a size pool before we start advancing that pool's own compact cursor. With these fixes in place, I was able to make the compaction tests move any amount of objects (previously, `test_moving_hashes_down_size_pools` would begin failing on my machine if I set `HASH_COUNT` to above about 6,000. -- https://bugs.ruby-lang.org/

Issue #20022 has been updated by kjtsanaktsidis (KJ Tsanaktsidis).

If we figure out the optimal size of every object and we set the heap to size (optimal_size * 2) + 1, it should guarantee that every object is moved before the cursors meet.

This sounds like a good idea (not least because it avoids hacking at the actual compaction implementation just for this development tool). Unfortunately I don't think the right formula is _quite_ that simple. 2N+1 isn't enough pages for all of the test cases - I added some iterations to some of the other move up/down test cases and they fail. They fail worse if I make them move up/down by more than one size pool... so I'm thinking the right factor has something to do with what size pool objects are coming from as well as going to (e.g. something along these lines:) ``` size_t weighting_factor = 1; if (dest_pool->slot_size > page->size_pool->slot_size) { weighting_factor <<= (dest_pool - page->size_pool); } else if (dest_pool->slot_size < page->size_pool->slot_size) { weighting_factor <<= (page->size_pool - dest_pool); } tdata->required_slots_weighted[dest_pool_idx] += weighting_factor; ``` This isn't quite it either though. I haven't been able to figure out the right formula yet but I'll try and have another go over the weekend... in the meanwhile I pushed up some WIP to my branch if you have a bright idea about the right formula. ---------------------------------------- Bug #20022: GC.verify_compaction_references does not actually move all objects https://bugs.ruby-lang.org/issues/20022#change-105433 * Author: kjtsanaktsidis (KJ Tsanaktsidis) * Status: Open * Priority: Normal * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN ---------------------------------------- While debugging https://bugs.ruby-lang.org/issues/20021, I ran into a separate issue which I figured was worth resolving whilst I had it in my head. The intention of GC.verify_compaction_references is, I believe, to force every single movable object to be moved, so that it's possible to debug native extensions which not correctly updating their references to objects they mark as movable (if this is _not_ the case, you can stop reading now and accept my apologies!) To do this, it doubles the number of allocated pages for each size pool, and sorts the heap pages so that the free ones are swept first; thus, every object in an old page should be moved into a free slot in one of the new pages. This worked fine until movement of objects between size pools during compaction was implemented. That causes some problems for verify_compaction_references: - We were doubling the number of pages in each size pool, but actually if some objects need to move into a different pool, there's no guarantee that they'll be enough room in that one. - It's possible for the sweep & compact cursors to meet in one size pool before all the objects that want to move into that size pool from another are processed by the compaction. You can see these problems by changing some of the movement tests in test_gc_compact.rb to try and move e.g. 50,000 objects instead of 500 (by changing `HASH_COUNT`); the test is not able to actually move all of the objects in a single compaction run. What I implemented in this PR (https://github.com/ruby/ruby/pull/9041) is two things: - Firstly, it examines every object and determine where it wants to be compacted into; we use this information to calculate the desired number of pages to add to each size pool. - Secondly, it compacts twice; once in order of ascending size pool, and once descending. This means that we are guaranteed to be able to move everything we want to move into a size pool before we start advancing that pool's own compact cursor. With these fixes in place, I was able to make the compaction tests move any amount of objects (previously, `test_moving_hashes_down_size_pools` would begin failing on my machine if I set `HASH_COUNT` to above about 6,000. -- https://bugs.ruby-lang.org/

Issue #20022 has been updated by kjtsanaktsidis (KJ Tsanaktsidis). I stared at this and did a bit of `printf` on it, and I _think_ I worked out that the formula for how many pages to add in one heap actually relates to how many objects there are in all the other heaps, even if they're not moved. Here's my working... Let us have two size pools, `P0` and `P1`. Let `P0` have slot size `S0`, and `P1` have slot size `S1`. Let the page size be `Z` bytes. Let us start with the heap of `P0` in the following configuration: HEAP START (sweep cursor starts here) (`F0` free pages) (`N` pages of objects which want to be moved to `P1`, totaling `N * (Z/S0)` objects) (`M0` pages of objects which want to remain in `P0`, totaling `M0 * (Z/S0)` objects) HEAP END (compact cursor starts here) And with `P1` in the following configuration: HEAP START (sweep cursor starts here) (`F1` free pages) (`M1` pages of objects which want to remain in `P1`, totaling `M1 * (Z/S1)` objects) HEAP END (compact cursor starts here) Let `M1 < M0`. Now, consider what happens to the loop in `gc_sweep_compact` as we compact this heap. The objective is to work out what values for `F0` and `F1` are required such that the sweep & compact cursors do not meet until all objects have been moved to their desired size pool. For the first `M1` iterations of the loop, we are copying objects only within the two size pools. - For `P0`, the compact cursor will advance by `M1` (number of iterations), and the sweep cursor will advance by `M1` (all objects are moved within the pool, and the newly-filled pages are swept). - For `P1`, the compact cursor will advance by `M1`, and the sweep cursor will advance by `M1` (by the same logic). For the subsequent `(M0 - M1)` loop iterations, we still need to copy objects within `P0`. `P1`, however will simply be compacting empty pages with nothing in it. - For `P0`, the compact cursor will advance by `(M0 - M1)`, and the sweep cursor will advance by `(M0 - M1)` (by the same logic as the previous iterations) - For `P1`, the compact cursor will advance by `(M0 - M1)` (since it iterates too), but the sweep cursor will not advance at all (no objects are being copied into free pages in `P1`). For the next `N` iterations, the compaction loop will be copying objects out of `P0` and into `P1` when compacting `P0`, and doing nothing again when compacting `P1`. - For `P0`, the compact cursor will advance by `N` (number of iterations), and the sweep cursor will not advance at all (no pages are being filled in `P0`). - For `P1`, the compact cursor will advance by `N`, and the sweep cursor will advance by `((S1/S0) * N)` (we are copying `N` objects into new pages in `P1`, and their size changes from `S0` to `S1`, so they occupy a different number of pages). Thus, during the process: - `P0` will have had its compact cursor advance by `M1 + (M0 - M1) + N == M0 + N`, and its sweep cursor advance by `M1 + (M0 - M1) == M0` - `P0` will have had its compact cursor advance by `M1 + (M0 - M1) + N == M0 + N`, and its sweep cursor advance by `M1 + (S1/S0)*N` And so, the correct number of free pages `F0` and `F1` which need to be in `P0` and `P1` for the cursors not to meet is: * `F0 == (M0 + N) + (M0) == 2*M0 + N` * `F1 == (M0 + N) + (M1 + (S1/S0)*N) == M0 + M1 + (1 + (S1/S0)) * N` --- I have to have a think about how to generalize this to arbitrary heap layouts and five size pools - anyway figured I'd show my working as I go through it :P ---------------------------------------- Bug #20022: GC.verify_compaction_references does not actually move all objects https://bugs.ruby-lang.org/issues/20022#change-105510 * Author: kjtsanaktsidis (KJ Tsanaktsidis) * Status: Open * Priority: Normal * Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN ---------------------------------------- While debugging https://bugs.ruby-lang.org/issues/20021, I ran into a separate issue which I figured was worth resolving whilst I had it in my head. The intention of GC.verify_compaction_references is, I believe, to force every single movable object to be moved, so that it's possible to debug native extensions which not correctly updating their references to objects they mark as movable (if this is _not_ the case, you can stop reading now and accept my apologies!) To do this, it doubles the number of allocated pages for each size pool, and sorts the heap pages so that the free ones are swept first; thus, every object in an old page should be moved into a free slot in one of the new pages. This worked fine until movement of objects between size pools during compaction was implemented. That causes some problems for verify_compaction_references: - We were doubling the number of pages in each size pool, but actually if some objects need to move into a different pool, there's no guarantee that they'll be enough room in that one. - It's possible for the sweep & compact cursors to meet in one size pool before all the objects that want to move into that size pool from another are processed by the compaction. You can see these problems by changing some of the movement tests in test_gc_compact.rb to try and move e.g. 50,000 objects instead of 500 (by changing `HASH_COUNT`); the test is not able to actually move all of the objects in a single compaction run. What I implemented in this PR (https://github.com/ruby/ruby/pull/9041) is two things: - Firstly, it examines every object and determine where it wants to be compacted into; we use this information to calculate the desired number of pages to add to each size pool. - Secondly, it compacts twice; once in order of ascending size pool, and once descending. This means that we are guaranteed to be able to move everything we want to move into a size pool before we start advancing that pool's own compact cursor. With these fixes in place, I was able to make the compaction tests move any amount of objects (previously, `test_moving_hashes_down_size_pools` would begin failing on my machine if I set `HASH_COUNT` to above about 6,000. -- https://bugs.ruby-lang.org/