Bugzilla

The current order of re-using regions from non-full runs seems to rely on the run's position in memory.

We assume that allocations for objects of the same size often happen in bursts, as well as deallocations, as a consequence of object trees or other structures being built up and later being torn down all together.
In such situations it helps to keep allocations from the same burst happen as much as possible in the same runs, such that it gets more likely to free entire runs when the corresponding free burst occurs.

We thus use an MRU policy for NotFull runs to keep allocations as local as possible.

This has two reasons:
1. It is cheap, as all our book-keeping is O(1), no tree-balancing needed.
2. It hopefully fosters that more allocations from the same unit of code end up together in the same run, as most likely they will be freed and/or used together at the same time.

The policy is as follows:
a. A newly allocated run becomes the head. This happens only when the list was empty.
b. The last head continues to be the head for subsequent allocations even if another run gets partly freed in the meantime until it is entirely filled, only then it is removed from the list.
c. A previously full run that frees a region is added at the end of the list. This breaks the MRU policy until d. happens. The reasoning is that since we just freed one single region, the overhead to keep this run "as-is" is lowest possible.
d. Each time we free more from a run, we move it to the second position in our list, if possible and needed. This keeps the center of the list in "most recently freed" order but leaves the head untouched.

The resulting list has three parts:
| stable head | n more free MRU ordered runs | m less free unordered runs |

The current order of re-using regions from non-full runs relies on the run's position in memory.

In general we assume that allocations for objects of the same size often happen in bursts, as well as deallocations, as a consequence of object trees or other structures being built up and later being torn down all together or in bigger portions.
In such situations it helps to keep allocations from the same burst happen as much as possible in the same runs, such that it gets more likely to free entire runs when the corresponding free burst occurs. Keeping objects close together fosters also to have less "cache miss" situations during use.

We want to use an MRF ("most-recently-freed") policy to refill non-full runs.

This has two reasons:

    It is cheap, as all our non-full-runs' book-keeping is O(1), no tree-balancing or walking is needed.
    It hopefully fosters that more allocations from the same unit of code end up together in the same run, as most likely they will be freed and/or used together at the same time.

The policy is as follows:
a. A newly allocated run becomes the head. This happens only when the list was empty.
b. If a run is entirely filled again, it is removed from the list and the next MRF run in the list becomes the head.
c. If a run is entirely freed, it is also removed from the list (and from the bin, entering the tree of recycleable runs).
d. Each time we free something from a run, we move it to the head position in our list, if possible and needed. This keeps the entire list in "most recently freed" order.

The current order of re-using regions from non-full runs relies on the run's position in memory.

In general we assume that allocations for objects of the same size often happen in bursts, as well as deallocations, as a consequence of object trees or other structures being built up and later being torn down all together or in bigger portions.
In such situations it helps to keep allocations from the same burst happen as much as possible in the same runs, such that it gets more likely to free entire runs when the corresponding free burst occurs. Keeping objects close together fosters also to have less "cache miss" situations during use.

We want to use an MRF ("most-recently-freed") policy to refill non-full runs.

This has two reasons:
1. It is cheap, as all our non-full-runs' book-keeping is O(1), no tree-balancing or walking is needed.
2. It hopefully fosters that more allocations from the same unit of code end up together in the same run, as most likely they will be freed and/or used together at the same time.

The policy is as follows:
a. A newly allocated run becomes the head. This happens only when the list was empty.
b. If a run is entirely filled again, it is removed from the list and the next MRF run in the list becomes the head.
c. If a run is entirely freed, it is also removed from the list (and from the bin, entering the tree of recycleable runs).
d. Each time we free something from a run, we move it to the head position in our list, if possible and needed. This keeps the entire list in "most recently freed" order.