Skip to content

FilmCraft: An open-source, nonlinear video editor written by scratch in pure Rust

10.0 KB
Raw Blame
//! Estimated time left of a job, from how fast it advanced over the last seconds.
//!
//! A job's `done` counter goes up in batches, and the speed of an export changes with what is on the
//! timeline (an intro, a banner, plain camera footage), so the estimate uses the speed of a trailing
//! window, not the average since the start, and it stays quiet until a second of readings shows
//! progress. A stall shows as a falling speed, so the estimate grows instead of freezing.

use std::collections::VecDeque;
use std::time::Duration;

use web_time::Instant;

/// How far back the speed is measured.
const WINDOW: Duration = Duration::from_secs(15);
/// Readings closer together than this are one reading (the UI asks on every frame it draws).
const MIN_GAP: Duration = Duration::from_millis(100);
/// The estimate needs at least this much time between its first and last reading.
const MIN_SPAN: Duration = Duration::from_secs(1);
/// The longest estimate given: a job that all but stopped would otherwise promise millennia.
const MAX_ETA: Duration = Duration::from_secs(100 * 3600);

/// Readings of a job's `done` counter over time.
#[derive(Default)]
pub(crate) struct Pace {
    /// (when, `done` then), oldest first.
    readings: VecDeque<(Instant, u64)>,
}

impl Pace {
    /// Note that the job had done `done` units at `now`.
    pub(crate) fn observe(&mut self, now: Instant, done: u64) {
        // a count that went back (a job that started over) starts the history again
        if self.readings.back().is_some_and(|(_, d)| done < *d) {
            self.readings.clear();
        }
        if self.readings.back().is_none_or(|(t, _)| now.saturating_duration_since(*t) >= MIN_GAP) {
            self.readings.push_back((now, done));
        }
        // keep the newest reading that is a whole window old as the baseline, and nothing before it
        while self.readings.len() > 2 && self.readings.get(1).is_some_and(|(t, _)| now.saturating_duration_since(*t) >= WINDOW) {
            self.readings.pop_front();
        }
        // an idle start (a loudness pass, a slow seek) is not the job's speed: measure from the last
        // reading before it moved, not from a baseline that makes the job look slow for a whole window
        if let Some(first) = self.readings.front().map(|r| r.1)
            && let Some(moved) = self.readings.iter().position(|(_, d)| *d != first)
            && moved >= 2
            && self.readings.get(moved - 1).is_some_and(|(t, _)| t.saturating_duration_since(self.readings[0].0) >= MIN_SPAN)
        {
            self.readings.drain(..moved - 1);
        }
    }

    /// The time `remaining` more units take at the pace of the readings, when they show one.
    pub(crate) fn eta(&self, remaining: u64) -> Option<Duration> {
        let (t0, d0) = *self.readings.front()?;
        let (t1, d1) = *self.readings.back()?;
        let span = t1.saturating_duration_since(t0);
        if span < MIN_SPAN || d1 <= d0 {
            return None;
        }
        let per_second = (d1 - d0) as f64 / span.as_secs_f64();
        let left = remaining as f64 / per_second;
        // `try_from_secs_f64` refuses what a `Duration` cannot hold; that is "more than the cap" here
        (left >= 0.0).then(|| Duration::try_from_secs_f64(left).map_or(MAX_ETA, |d| d.min(MAX_ETA)))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn at(t0: Instant, secs: f64) -> Instant {
        t0 + Duration::from_secs_f64(secs)
    }

    /// Feed `readings` (seconds, done) and ask for the time left of `total`.
    fn eta(readings: &[(f64, u64)], total: u64) -> Option<f64> {
        let t0 = Instant::now();
        let mut p = Pace::default();
        for (s, d) in readings {
            p.observe(at(t0, *s), *d);
        }
        let done = readings.last().map_or(0, |r| r.1);
        p.eta(total.saturating_sub(done)).map(|d| d.as_secs_f64())
    }

    /// A job at `fps` units per second, read every `step` seconds for `secs`.
    fn steady(fps: f64, step: f64, secs: f64) -> Vec<(f64, u64)> {
        (0..=(secs / step) as u64).map(|i| (i as f64 * step, (i as f64 * step * fps) as u64)).collect()
    }

    #[test]
    fn a_steady_job_gives_the_time_it_has_left() {
        // 50 units a second, 4 s in, of 1000: 800 units left = 16 s
        let e = eta(&steady(50.0, 0.15, 4.0), 1000).unwrap();
        assert!((e - 16.0).abs() < 0.5, "{e}");
        // and the estimate falls as the job goes on: 10 s in, 500 left
        let e = eta(&steady(50.0, 0.15, 10.0), 1000).unwrap();
        assert!((e - 10.0).abs() < 0.5, "{e}");
    }

    #[test]
    fn nothing_is_promised_before_there_is_progress_to_measure() {
        assert_eq!(eta(&[], 100), None);
        assert_eq!(eta(&[(0.0, 0)], 100), None, "one reading");
        assert_eq!(eta(&[(0.0, 0), (0.5, 20)], 100), None, "less than a second of readings");
        assert_eq!(eta(&[(0.0, 5), (2.0, 5)], 100), None, "nothing done in two seconds (a loudness pass, a seek)");
        // then, once frames flow
        assert!(eta(&[(0.0, 0), (2.0, 0), (3.0, 30)], 100).is_some());
    }

    #[test]
    fn the_estimate_follows_a_change_of_speed_within_the_window() {
        // 100 units a second for 20 s, then 20 a second for 20 s (a banner comes in): the last
        // 15 s dominate, so with 10 000 units to do the estimate is near the slow speed's
        let mut r = steady(100.0, 0.15, 20.0);
        let (t, d) = *r.last().unwrap();
        r.extend((1..=133).map(|i| (t + i as f64 * 0.15, d + (i as f64 * 0.15 * 20.0) as u64)));
        let done = r.last().unwrap().1;
        let e = eta(&r, 10_000).unwrap();
        let slow = (10_000 - done) as f64 / 20.0;
        let fast = (10_000 - done) as f64 / 100.0;
        assert!((e - slow).abs() < (e - fast).abs(), "estimate {e}, slow {slow}, fast {fast}");
    }

    #[test]
    fn an_idle_start_does_not_hold_the_estimate_back() {
        // 20 s with nothing done (a loudness pass), then 50 units a second for 3 s: the pace is 50 a
        // second, not what a 15 s window that is mostly idle would say
        let mut r: Vec<(f64, u64)> = (0..=133).map(|i| (i as f64 * 0.15, 0)).collect();
        let t = r.last().unwrap().0;
        r.extend((1..=20).map(|i| (t + i as f64 * 0.15, (i as f64 * 0.15 * 50.0) as u64)));
        let e = eta(&r, 1000).unwrap();
        let done = r.last().unwrap().1;
        assert!((e - (1000 - done) as f64 / 50.0).abs() < 1.0, "{e}");
        // the short flat spells between batches of a running job are not an idle start
        let batches: Vec<(f64, u64)> = (0..=40).map(|i| (i as f64 * 0.15, (i / 2) as u64 * 8)).collect();
        assert!(eta(&batches, 1000).is_some());
    }

    #[test]
    fn a_stall_makes_the_estimate_grow() {
        let mut r = steady(50.0, 0.15, 4.0);
        let before = eta(&r, 1000).unwrap();
        let (t, d) = *r.last().unwrap();
        r.extend((1..=40).map(|i| (t + i as f64 * 0.15, d)));
        let after = eta(&r, 1000).unwrap();
        assert!(after > before * 1.5, "{before} -> {after}");
    }

    #[test]
    fn a_count_that_goes_back_starts_over() {
        // a second pass, or a job reusing its counters: the old history must not count
        let mut r = steady(50.0, 0.15, 4.0);
        let (t, _) = *r.last().unwrap();
        r.extend((1..=20).map(|i| (t + i as f64 * 0.15, (i as f64 * 0.15 * 10.0) as u64)));
        let e = eta(&r, 100).unwrap();
        let done = r.last().unwrap().1;
        assert!((e - (100 - done) as f64 / 10.0).abs() < 1.0, "{e}");
    }

    #[test]
    fn readings_that_arrive_together_count_once_and_the_history_stays_small() {
        let t0 = Instant::now();
        let mut p = Pace::default();
        for _ in 0..1000 {
            p.observe(t0, 1);
        }
        assert_eq!(p.readings.len(), 1);
        // an hour of 150 ms readings keeps about a window of them
        for i in 0..24_000u64 {
            p.observe(at(t0, 1.0 + i as f64 * 0.15), 1 + i);
        }
        assert!(p.readings.len() <= (WINDOW.as_millis() / MIN_GAP.as_millis()) as usize + 3, "{}", p.readings.len());
    }

    #[test]
    fn a_job_reports_its_time_left_until_it_is_done() {
        use std::sync::atomic::Ordering;
        let t0 = Instant::now();
        let progress = crate::Progress::default();
        // no total yet, nothing to estimate
        assert_eq!(progress.eta_at(t0), None);
        progress.total.store(1000, Ordering::Relaxed);
        let mut last = None;
        for i in 0..=60u64 {
            progress.done.store(i * 5, Ordering::Relaxed); // 50 units a second, read every 0.1 s
            last = progress.eta_at(at(t0, i as f64 * 0.1));
        }
        // 6 s in, 300 done, 700 left at 50 a second
        let left = last.expect("a second of readings shows progress").as_secs_f64();
        assert!((left - 14.0).abs() < 0.5, "{left}");
        // done: nothing left to wait for
        progress.done.store(1000, Ordering::Relaxed);
        assert_eq!(progress.eta_at(at(t0, 7.0)), None);
        // a finished job (cancelled, failed) has none either, whatever it had left
        let other = crate::Progress::default();
        other.total.store(1000, Ordering::Relaxed);
        for i in 0..=30u64 {
            other.done.store(i * 5, Ordering::Relaxed);
            other.eta_at(at(t0, i as f64 * 0.1));
        }
        assert!(other.eta_at(at(t0, 3.1)).is_some());
        other.finished.store(true, Ordering::Relaxed);
        assert_eq!(other.eta_at(at(t0, 3.2)), None);
    }

    #[test]
    fn extreme_numbers_give_a_capped_estimate_or_none_and_never_panic() {
        // almost no progress against a huge total: capped
        let e = eta(&[(0.0, 0), (10.0, 1)], u64::MAX).unwrap();
        assert!((e - MAX_ETA.as_secs_f64()).abs() < 1.0, "{e}");
        // huge counters
        assert!(eta(&[(0.0, u64::MAX - 100), (2.0, u64::MAX - 50)], u64::MAX).is_some());
        // a clock that does not move forward: no estimate, no division by zero
        assert_eq!(eta(&[(1.0, 0), (1.0, 50), (1.0, 100)], 1000), None);
        // nothing left
        let t0 = Instant::now();
        let mut p = Pace::default();
        p.observe(t0, 0);
        p.observe(at(t0, 2.0), 100);
        assert_eq!(p.eta(0), Some(Duration::ZERO));
    }
}