gc-arena 0.7.0

use alloc::rc::Rc;
use core::cell::Cell;

/// Tuning parameters for a given garbage collected [`crate::Arena`].
///
/// Any allocation that occurs during a collection cycle will incur "debt" that is exactly equal
/// to the number of allocated `Gc`s. This "debt" is paid off by running the collection algorithm
/// some amount of time proportional to the debt. Exactly how much "debt" is paid off and in what
/// proportion by the different parts of the collection algorithm is configured by the chosen values
/// here. We refer to the amount of "debt" paid off by running the collection algorithm as "work".
///
/// The most important idea behind choosing these tuning parameters is that we always want the
/// collector (when it is not sleeping) to deterministically run *faster* than allocation. We do
/// this so we can be *completely sure* that once collection starts, the collection cycle will
/// finish and memory will not grow without bound. If we are tuning for low pause time however,
/// it is also important that not *too* many costly operations are run within a single call to
/// [`crate::Arena::collect_debt`], and this goal is in tension with the first, more important goal.
///
/// How these two goals are balanced is that we must choose our tuning parameters so that the total
/// amount of "work" performed to either *remember* or *free* one `Gc` is always *less than one*,
/// as this makes the collector deterministically run faster than the rate of allocation (which
/// is crucial). The closer the amount of "work" performed to remember or free one `Gc` is to 1.0,
/// the slower the collector will go and the higher the maximum amount of used memory will be. The
/// closer the amount of "work" performed to remember or free one `Gc` is to 0.0, the faster the
/// collector will go and the closer it will get to behaving like a stop-the-world collector.
///
/// All live `Gc`s in a cycle are either remembered or freed once, but it is important that *both
/// paths* require less than one unit of "work" per `Gc` to fully complete. There is no way to
/// predict a priori the ratio of remembered vs forgotten values, so if either path takes too close
/// to or over 1.0 unit of work per `Gc` to complete, collection may run too slowly.
///
/// # Factors that control the time the GC sleeps
///
/// `sleep_factor` is fairly self explanatory. Setting this too low will reduce the time of the
/// [`crate::arena::CollectionPhase::Sleeping`] phase but this is not harmful (it can even be set
/// to zero to keep the collector always running!), setting it much larger than 1.0 will make the
/// collector wait a very long time before collecting again, and usually not what you want.
///
/// `min_sleep` is also self explanatory and usually does not need changing from the default value.
/// It should always be relatively small.
///
/// # Timing factors for remembered values
///
/// Every live `Gc` value in an [`crate::Arena`] that is reachable from the root is "remembered".
/// Every remembered value will always have exactly three things done to it in a given cycle:
///
/// 1) It will at some point be found and marked as reachable (and potentially queued for tracing).
///    When this happens, `mark_factor` work is recorded.
/// 2) Entries in the queue for tracing will eventually be traced by having their
///    [`crate::Collect::trace`] method called. At this time, `trace_factor` work is recorded.
///    Calling `Collect::trace` will usually mark other `Gc`s as reachable and queue them for
///    tracing if they have not already been, so this step may also transitively perform other work,
///    but each step is only performed exactly once for each individual remembered value.
/// 3) During the [`crate::arena::CollectionPhase::Sweeping`] phase, each remembered value has to
///    be iterated over in the sweep list and removed from it. This a small, constant amount of
///    work that is very fast, but it should always perform *some* work to keep pause time low, so
///    `keep_factor` work is recorded.
///
/// # Timing factors for forgotten values
///
/// Allocated values that are not reachable in a GC cycle are simpler than
/// remembered values. Only two operations are performed on them, and only during
/// [`crate::arena::CollectionPhase::Sweeping`]: dropping and freeing.
///
/// If a value is unreachable, then when it is encountered in the free list it will be dropped (and
/// `drop_factor` work will be recorded), and then the memory backing the value will be freed (and
/// `free_factor` work will be recorded).
///
/// # Timing factors for weakly reachable values
///
/// There is actually a *third* possible path for a value to take in a collection cycle which is a
/// hybrid of the two, but thankfully it is not too complex.
///
/// If a value is (newly) weakly reachable this cycle, first the `Gc` will be marked as (weakly)
/// reachable (`mark_factor` work is recorded), then during sweeping it will be *dropped*
/// (`drop_factor` work is recorded), and then *kept* (`keep_factor` work is recorded).
///
/// # Summary
///
/// This may seem complicated but it is actually not too difficult to make sure that the GC will not
/// stall: *every path that a `Gc` can take must never do 1.0 or more unit of work per `Gc` within
/// a cycle*.
///
/// The important formulas to check are:
///
/// - We need to make sure that remembered values are processed faster than allocation:
///   `mark_factor + trace_factor + keep_factor < 1.0`
/// - We need to make sure that forgotten values are processed faster than allocation:
///   `drop_factor + free_factor < 1.0`
/// - We need to make sure that weakly remembered values are processed faster than allocation:
///   `mark_factor + drop_factor + keep_factor < 1.0`
///
/// It is also important to note that this is not an exhaustive list of all the possible paths a
/// `Gc` can take, but every path will always be a *subset* of one of the above paths. The above
/// formulas represent every possible the worst case: for example, if a weakly reachable value has
/// already been dropped then only `mark_factor + keep_factor` work will be recorded, and if we
/// can prove that a reachable value has [`crate::Collect::NEEDS_TRACE`] set to false, then only
/// `mark_factor + keep_factor` work will be recorded. This is not important to remember though, it
/// is true that when the collector elides work it may not actually record that work as performed,
/// but this will only *speed up* collection, it can never cause the collector to stall.
#[derive(Debug, Copy, Clone)]
pub struct Pacing {
    /// Controls the length of the [`crate::arena::CollectionPhase::Sleeping`] phase.
    ///
    /// At the start of a new GC cycle, the collector will wait until the live `Gc` count reaches
    /// `<current heap count> + <previous remembered count> * sleep_factor` before starting
    /// collection.
    pub sleep_factor: f64,

    /// The minimum length of the [`crate::arena::CollectionPhase::Sleeping`] phase.
    ///
    /// if the calculated sleep amount using `sleep_factor` is lower than `min_sleep`, this will
    /// be used instead. This is mostly useful when the heap is very small to prevent rapidly
    /// restarting collections.
    pub min_sleep: usize,

    /// The multiplicative factor for "work" performed per `Gc` when a `Gc` is first marked as
    /// reachable.
    pub mark_factor: f64,

    /// The multiplicative factor for "work" performed per `Gc` when the held value has its
    /// [`crate::Collect::trace`] method called.
    pub trace_factor: f64,

    /// The multiplicative factor for "work" performed per `Gc` when a reachable `Gc` is iterated
    /// over during [`crate::arena::CollectionPhase::Sweeping`].
    pub keep_factor: f64,

    /// The multiplicative factor for "work" performed per `Gc` when a `Gc` value that is forgotten
    /// or only weakly reachable is dropped during [`crate::arena::CollectionPhase::Sweeping`].
    pub drop_factor: f64,

    /// The multiplicative factor for "work" performed per `Gc` when the allocation for a `Gc` is
    /// freed during [`crate::arena::CollectionPhase::Sweeping`].
    pub free_factor: f64,
}

impl Pacing {
    pub const DEFAULT: Pacing = Pacing {
        sleep_factor: 0.5,
        min_sleep: 256,
        mark_factor: 0.1,
        trace_factor: 0.4,
        keep_factor: 0.05,
        drop_factor: 0.2,
        free_factor: 0.3,
    };

    /// A good default "stop-the-world" [`Pacing`] configuration.
    ///
    /// This has all of the work factors set to zero so that as soon as the collector wakes from
    /// sleep, it will immediately perform a full collection.
    ///
    /// It is important to set the sleep factor fairly high when configuring a collector this way
    /// (close to or even somewhat larger than 1.0).
    pub const STOP_THE_WORLD: Pacing = Pacing {
        sleep_factor: 1.0,
        min_sleep: 256,
        mark_factor: 0.0,
        trace_factor: 0.0,
        keep_factor: 0.0,
        drop_factor: 0.0,
        free_factor: 0.0,
    };
}

impl Default for Pacing {
    #[inline]
    fn default() -> Pacing {
        Self::DEFAULT
    }
}

#[derive(Debug, Default)]
struct MetricsInner {
    pacing: Cell<Pacing>,

    total_gcs: Cell<usize>,

    wakeup_amount: Cell<f64>,
    artificial_debt: Cell<f64>,

    // Statistics for `Gc` allocations and deallocations that happen during a GC cycle.
    allocated_gcs: Cell<usize>,
    dropped_gcs: Cell<usize>,
    freed_gcs: Cell<usize>,

    // Statistics for `Gc`s that have been marked as non-white this cycle.
    marked_gcs: Cell<usize>,

    // Statistics for `Gc`s that have their contents traced.
    traced_gcs: Cell<usize>,

    // Statistics for reachable `Gc`s as they are iterated through during the sweep phase.
    remembered_gcs: Cell<usize>,
}

#[derive(Clone)]
pub struct Metrics(Rc<MetricsInner>);

impl Metrics {
    pub(crate) fn new() -> Self {
        Self(Default::default())
    }

    /// Return a value identifying the arena, for logging purposes.
    #[cfg(feature = "tracing")]
    pub(crate) fn arena_id(&self) -> tracing::field::DebugValue<*const ()> {
        // Be very cheeky and use the `Metrics` address as a (temporally) unique ID.
        // TODO: use a monotonically increasing global counter instead?
        tracing::field::debug(Rc::as_ptr(&self.0) as *const ())
    }

    /// Sets the pacing parameters used by the collection algorithm.
    ///
    /// The factors that affect the gc sleep time will not take effect until the start of the next
    /// collection.
    #[inline]
    pub fn set_pacing(&self, pacing: Pacing) {
        self.0.pacing.set(pacing);
    }

    /// Returns the current number of `Gc`s allocated that have not yet been freed.
    #[inline]
    pub fn total_gc_count(&self) -> usize {
        self.0.total_gcs.get()
    }

    /// Adjust the allocation debt artificially.
    #[inline]
    pub fn adjust_debt(&self, amt: f64) {
        self.0.artificial_debt.update(|d| d + amt);
    }

    /// All arena allocation causes the arena to accumulate "allocation debt". This debt is then
    /// used to time incremental garbage collection based on the tuning parameters in the current
    /// `Pacing`. The allocation debt will generally increase at a rate faster than that of
    /// allocation so that collection will always complete.
    #[inline]
    pub fn allocation_debt(&self) -> f64 {
        let total_gcs = self.0.total_gcs.get();
        if total_gcs == 0 {
            // If we have no live `Gc`s, then there is no possible collection to do so always
            // return zero debt.
            return 0.0;
        }

        let allocated_gcs = self.0.allocated_gcs.get() as f64;

        // Every allocation after the `wakeup_amount` in a cycle is a debit.
        let cycle_debits =
            allocated_gcs - self.0.wakeup_amount.get() + self.0.artificial_debt.get();

        // If our debits are not positive, then we know the total debt is not positive.
        if cycle_debits <= 0.0 {
            return 0.0;
        }

        let pacing = self.0.pacing.get();

        let cycle_credits = self.0.marked_gcs.get() as f64 * pacing.mark_factor
            + self.0.traced_gcs.get() as f64 * pacing.trace_factor
            + self.0.remembered_gcs.get() as f64 * pacing.keep_factor
            + self.0.dropped_gcs.get() as f64 * pacing.drop_factor
            + self.0.freed_gcs.get() as f64 * pacing.free_factor;

        (cycle_debits - cycle_credits).max(0.0)
    }

    pub(crate) fn finish_cycle(&self, reset_debt: bool) {
        let pacing = self.0.pacing.get();
        let remembered_count = self.0.remembered_gcs.get();
        let wakeup_amount =
            (remembered_count as f64 * pacing.sleep_factor).max(pacing.min_sleep as f64);

        let artificial_debt = if reset_debt {
            0.0
        } else {
            self.allocation_debt()
        };

        self.0.wakeup_amount.set(wakeup_amount);
        self.0.artificial_debt.set(artificial_debt);

        self.0.allocated_gcs.set(0);
        self.0.dropped_gcs.set(0);
        self.0.freed_gcs.set(0);
        self.0.marked_gcs.set(0);
        self.0.traced_gcs.set(0);
        self.0.remembered_gcs.set(0);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_allocated(&self, count: usize) {
        self.0.total_gcs.update(|c| c + count);
        self.0.allocated_gcs.update(|b| b + count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_dropped(&self, count: usize) {
        self.0.dropped_gcs.update(|b| b + count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_freed(&self, count: usize) {
        self.0.total_gcs.update(|c| c - count);
        self.0.freed_gcs.update(|b| b + count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_marked(&self, count: usize) {
        self.0.marked_gcs.update(|c| c + count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_traced(&self, count: usize) {
        self.0.traced_gcs.update(|c| c + count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_untraced(&self, count: usize) {
        self.0.traced_gcs.update(|c| c - count);
    }

    #[inline(always)]
    pub(crate) fn mark_gc_remembered(&self, count: usize) {
        self.0.remembered_gcs.update(|c| c + count);
    }
}