1687a9c05b0c
chartcache.rs
//! Rendered charts kept between frames.
//!
//! Resolving a chart's series and laying it out is O(points). Doing it for every visible chart on
//! every frame kept the UI thread busy while scrolling a workbook with a few big charts (#1139,
//! part of #1098). The primitives a chart renders to depend on the workbook, the chart's place in
//! it, the zoom, the screen's pixels-per-point and the fonts text is measured with, so those are
//! what an entry is checked against.
//!
//! **Why "the workbook is unchanged" can be known without a change counter.** A document's
//! workbook is an `Arc<Workbook>` and its content is only reachable for writing through
//! `Arc::make_mut` (or by replacing the `Arc`), because the model has no interior mutability and
//! the code base forbids `unsafe`. While a `Weak` to the allocation exists, `make_mut` never
//! mutates it in place: it clones (other strong owners, e.g. an undo snapshot) or moves the value
//! to a new allocation (the `Weak` is cut loose). So if the document's current `Arc` still points
//! at the allocation the cache holds a `Weak` to, nothing was written since the entries were
//! built, however the write would have been made (command, undo, redo, recalculation, file load,
//! a direct edit from the UI, a future code path). The `Weak` also keeps the allocation from being
//! freed and reused, so a pointer match cannot be a stranger that landed on the same address.
use std::collections::HashMap;
use std::sync::{Arc, Weak};
use gridcraft_chart::Prim;
use gridcraft_engine::model::Workbook;
/// Most charts kept, over all documents.
const MAX_ENTRIES: usize = 64;
/// Most memory kept (estimated from the primitives), over all documents.
const MAX_BYTES: usize = 48 << 20;
struct Entry {
/// Zoom and pixels-per-point the primitives were measured for (`f32::to_bits`).
z: u32,
ppp: u32,
prims: Arc<[Prim]>,
bytes: usize,
/// Tick of the last use; the smallest is evicted first.
used: u64,
}
struct DocCharts {
/// The workbook the entries were built from.
wb: Weak<Workbook>,
/// (sheet index, index in the sheet's `charts`). The workbook is unchanged while the entries
/// live, so the pair names one chart.
charts: HashMap<(usize, usize), Entry>,
}
#[derive(Default)]
pub(crate) struct ChartCache {
docs: HashMap<u64, DocCharts>,
tick: u64,
bytes: usize,
/// Charts built (resolved and rendered) so far; for tests.
#[cfg(test)]
pub(crate) builds: usize,
}
fn prim_bytes(p: &Prim) -> usize {
std::mem::size_of::<Prim>()
+ match p {
Prim::Line { pts, .. } | Prim::Polygon { pts, .. } => pts.len().saturating_mul(std::mem::size_of::<[f32; 2]>()),
Prim::Text { text, .. } => text.len(),
_ => 0,
}
}
impl ChartCache {
/// The primitives of chart `index` of `sheet` in document `uid` whose workbook is `wb`, for
/// zoom and pixels per point `(z, ppp)`. `build` renders the chart when there is no valid entry.
pub(crate) fn get(
&mut self,
uid: u64,
wb: &Arc<Workbook>,
sheet: usize,
index: usize,
(z, ppp): (f32, f32),
build: impl FnOnce() -> Vec<Prim>,
) -> Arc<[Prim]> {
self.tick = self.tick.wrapping_add(1);
let tick = self.tick;
let doc = self.docs.entry(uid).or_insert_with(|| DocCharts { wb: Arc::downgrade(wb), charts: HashMap::new() });
if !std::ptr::eq(doc.wb.as_ptr(), Arc::as_ptr(wb)) {
// The document changed (or is another one with this uid): nothing built from the old
// workbook can be trusted.
let dropped: usize = doc.charts.values().map(|e| e.bytes).sum();
doc.charts.clear();
doc.wb = Arc::downgrade(wb);
self.bytes = self.bytes.saturating_sub(dropped);
}
let (zb, pb) = (z.to_bits(), ppp.to_bits());
if let Some(e) = doc.charts.get_mut(&(sheet, index))
&& e.z == zb
&& e.ppp == pb
{
e.used = tick;
return e.prims.clone();
}
#[cfg(test)]
{
self.builds += 1;
}
let prims: Arc<[Prim]> = build().into();
let bytes = prims.iter().map(prim_bytes).fold(0usize, usize::saturating_add);
let Some(doc) = self.docs.get_mut(&uid) else { return prims };
if let Some(old) = doc.charts.remove(&(sheet, index)) {
self.bytes = self.bytes.saturating_sub(old.bytes);
}
// A chart that alone would fill a quarter of the budget is not worth keeping.
if bytes <= MAX_BYTES / 4 {
doc.charts.insert((sheet, index), Entry { z: zb, ppp: pb, prims: prims.clone(), bytes, used: tick });
self.bytes = self.bytes.saturating_add(bytes);
self.evict();
}
prims
}
/// Drops least recently used entries until the caps hold.
fn evict(&mut self) {
loop {
let count: usize = self.docs.values().map(|d| d.charts.len()).sum();
if count <= MAX_ENTRIES && self.bytes <= MAX_BYTES {
return;
}
let oldest = self.docs.iter().flat_map(|(uid, d)| d.charts.iter().map(move |(k, e)| (e.used, *uid, *k))).min();
let Some((_, uid, key)) = oldest else { return };
if let Some(e) = self.docs.get_mut(&uid).and_then(|d| d.charts.remove(&key)) {
self.bytes = self.bytes.saturating_sub(e.bytes);
}
}
}
/// Forgets the documents that are not in `live` (closed workbooks).
pub(crate) fn retain_docs(&mut self, live: impl Iterator<Item = u64>) {
let live: Vec<u64> = live.collect();
let bytes = &mut self.bytes;
self.docs.retain(|uid, d| {
let keep = live.contains(uid);
if !keep {
*bytes = bytes.saturating_sub(d.charts.values().map(|e| e.bytes).sum());
}
keep
});
}
/// Forgets everything (the fonts text was measured with changed).
pub(crate) fn clear(&mut self) {
self.docs.clear();
self.bytes = 0;
}
#[cfg(test)]
pub(crate) fn len(&self) -> usize {
self.docs.values().map(|d| d.charts.len()).sum()
}
#[cfg(test)]
pub(crate) fn docs(&self) -> usize {
self.docs.len()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::SheetApp;
use crate::chartview::tests::RENDERS;
use egui::{Event, vec2};
use gridcraft_chart::ApproxMeasure;
use gridcraft_engine::Session;
use serde_json::json;
type Harness = egui_kittest::Harness<'static, SheetApp>;
fn wb() -> Arc<Workbook> {
Arc::new(Workbook::new())
}
fn rect_prim(w: f32) -> Vec<Prim> {
vec![Prim::Rect { x: 0.0, y: 0.0, w, h: 1.0, fill: None, stroke: None, radius: 0.0 }]
}
fn line_prim(points: usize) -> Vec<Prim> {
vec![Prim::Line { pts: vec![[0.0, 0.0]; points], color: [0, 0, 0, 255], width: 1.0, dash: false }]
}
#[test]
fn a_workbook_written_after_caching_is_never_taken_for_the_cached_one() {
let mut cache = ChartCache::default();
let mut w = wb();
let build = || rect_prim(1.0);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
assert_eq!(cache.builds, 1, "same workbook: a hit");
// Sole owner of the Arc: without the Weak this write would happen in place, at the same address.
Arc::make_mut(&mut w).active_sheet.set(0);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
assert_eq!(cache.builds, 2, "a write through make_mut moved the workbook to a new allocation");
// Shared with an undo snapshot: make_mut clones, the pointer changes as well.
let snapshot = w.clone();
Arc::make_mut(&mut w).active_sheet.set(0);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
assert_eq!(cache.builds, 3);
// Replacing the Arc with an equal workbook (a reload) is a change too.
w = Arc::new((*snapshot).clone());
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
assert_eq!(cache.builds, 4);
// The old allocation is still held by the cache's Weak while its owner is gone, so a new
// workbook can't be mistaken for it by landing on the same address.
drop(snapshot);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
assert_eq!(cache.builds, 4);
}
#[test]
fn zoom_scale_chart_and_document_are_part_of_the_key() {
let mut cache = ChartCache::default();
let w = wb();
let build = || rect_prim(1.0);
cache.get(1, &w, 0, 0, (1.0, 1.0), build);
cache.get(1, &w, 0, 0, (1.25, 1.0), build);
cache.get(1, &w, 0, 0, (1.25, 2.0), build);
cache.get(1, &w, 0, 1, (1.25, 2.0), build);
cache.get(1, &w, 1, 0, (1.25, 2.0), build);
cache.get(2, &w, 0, 0, (1.25, 2.0), build);
assert_eq!(cache.builds, 6);
cache.get(1, &w, 0, 1, (1.25, 2.0), build);
cache.get(2, &w, 0, 0, (1.25, 2.0), build);
assert_eq!(cache.builds, 6, "each of those is cached");
}
#[test]
fn the_cache_is_capped_in_entries_and_bytes_and_drops_the_least_recently_used() {
let mut cache = ChartCache::default();
let w = wb();
for i in 0..MAX_ENTRIES + 10 {
cache.get(1, &w, 0, i, (1.0, 1.0), || rect_prim(1.0));
// Chart 0 is used all the time, so it survives.
cache.get(1, &w, 0, 0, (1.0, 1.0), || rect_prim(1.0));
}
assert_eq!(cache.len(), MAX_ENTRIES);
let before = cache.builds;
cache.get(1, &w, 0, 0, (1.0, 1.0), || rect_prim(1.0));
assert_eq!(cache.builds, before, "the busy chart is still there");
cache.get(1, &w, 0, 1, (1.0, 1.0), || rect_prim(1.0));
assert_eq!(cache.builds, before + 1, "the idle one was evicted");
// Bytes: each of these is ~4 MiB of points; only a handful fit.
let mut cache = ChartCache::default();
let points = (4 << 20) / std::mem::size_of::<[f32; 2]>();
for i in 0..40 {
cache.get(1, &w, 0, i, (1.0, 1.0), || line_prim(points));
}
assert!(cache.bytes <= MAX_BYTES && cache.len() < 40, "{} entries, {} bytes", cache.len(), cache.bytes);
// One that would fill a quarter of the budget is not kept, and is still returned.
let mut cache = ChartCache::default();
let big = cache.get(1, &w, 0, 0, (1.0, 1.0), || line_prim(MAX_BYTES / 4 / std::mem::size_of::<[f32; 2]>() + 1000));
assert!(!big.is_empty());
assert_eq!((cache.len(), cache.bytes), (0, 0));
}
#[test]
fn closed_documents_are_forgotten() {
let mut cache = ChartCache::default();
let w = wb();
cache.get(1, &w, 0, 0, (1.0, 1.0), || line_prim(10));
cache.get(2, &w, 0, 0, (1.0, 1.0), || line_prim(10));
cache.retain_docs([2].into_iter());
assert_eq!((cache.docs(), cache.len()), (1, 1));
cache.retain_docs(std::iter::empty());
assert_eq!((cache.docs(), cache.len(), cache.bytes), (0, 0, 0));
}
/// A workbook with charts of several kinds over numbers, dates and categories.
fn corpus() -> Session {
let mut s = Session::new();
s.new_workbook();
s.execute("range.setValues", json!({"range": "A1", "values": [["Date", "Sales", "Cost", "Share"]]})).unwrap();
for i in 0..40u32 {
let date = format!("2024-{:02}-{:02}", 1 + i / 28, 1 + i % 28);
s.execute("cell.set", json!({"cell": format!("A{}", i + 2), "input": date})).unwrap();
s.execute("cell.set", json!({"cell": format!("B{}", i + 2), "input": format!("{}", (i * 37) % 101)})).unwrap();
s.execute("cell.set", json!({"cell": format!("C{}", i + 2), "input": format!("=B{}/2+{}", i + 2, i)})).unwrap();
s.execute("cell.set", json!({"cell": format!("D{}", i + 2), "input": format!("{}", (i % 5) + 1)})).unwrap();
}
for (i, (kind, range)) in [
("column", "A1:C41"),
("line", "A1:C41"),
("scatter", "B1:C41"),
("pie", "A1:B6"),
("combo", "A1:C41"),
("area", "A1:B41"),
("bar", "A1:D41"),
("doughnut", "A1:B6"),
]
.into_iter()
.enumerate()
{
s.execute("insert.chart", json!({"range": range, "type": kind, "at": format!("H{}", 2 + i * 16), "width": 320, "height": 220})).unwrap();
}
s
}
#[test]
fn cached_output_equals_a_fresh_render_for_a_corpus_of_charts() {
let s = corpus();
let d = s.doc().unwrap();
let sh = d.wb.active().unwrap();
assert_eq!(sh.charts.len(), 8);
let mut cache = ChartCache::default();
for (i, ch) in sh.charts.iter().enumerate() {
let fresh = || {
let data = gridcraft_chart::resolve(&d.wb, d.wb.active_sheet.get(), ch);
gridcraft_chart::render(ch, &data, ch.anchor.width, ch.anchor.height, &ApproxMeasure)
};
let expect = fresh();
assert!(expect.len() > 3, "{:?} renders something", ch.kind);
let first = cache.get(d.uid, &d.wb, d.wb.active_sheet.get(), i, (1.0, 1.0), fresh);
let second = cache.get(d.uid, &d.wb, d.wb.active_sheet.get(), i, (1.0, 1.0), || panic!("must be a hit"));
assert_eq!(&*first, &expect[..], "{:?}: built entry", ch.kind);
assert_eq!(&*second, &expect[..], "{:?}: cached entry", ch.kind);
}
assert_eq!(cache.builds, 8);
}
// --- frames ---
fn harness(s: Session) -> Harness {
let mut h = egui_kittest::Harness::builder().with_size(vec2(1400.0, 900.0)).build_ui_state(
|ui, app: &mut SheetApp| {
let ctx = ui.ctx().clone();
app.logic(&ctx);
app.ui(ui);
},
SheetApp::new(s, Default::default()),
);
h.run_steps(8);
h
}
/// Two charts side by side, both in view, over A1:B12 (B3 is `=B2*2`).
fn two_charts() -> Session {
let mut s = Session::new();
s.new_workbook();
s.execute("range.setValues", json!({"range": "A1", "values": [["Day", "Sales"]]})).unwrap();
for i in 2..=12u32 {
let input = if i == 3 { "=B2*2".to_string() } else { format!("{}", i * 3 % 17) };
s.execute("cell.set", json!({"cell": format!("A{i}"), "input": format!("2024-03-{i:02}")})).unwrap();
s.execute("cell.set", json!({"cell": format!("B{i}"), "input": input})).unwrap();
}
s.execute("insert.chart", json!({"range": "A1:B12", "type": "column", "at": "D2", "width": 300, "height": 200})).unwrap();
s.execute("insert.chart", json!({"range": "A1:B12", "type": "scatter", "at": "L2", "width": 300, "height": 200})).unwrap();
s
}
fn builds() -> usize {
RENDERS.with(|c| c.get())
}
/// Runs `change`, lets a few frames pass and returns how many charts were rendered meanwhile.
fn rendered_after(h: &mut Harness, change: impl FnOnce(&mut Harness)) -> usize {
let before = builds();
change(h);
h.run_steps(4);
builds() - before
}
fn exec(h: &mut Harness, id: &str, params: serde_json::Value) {
h.state_mut().session.execute(id, params).unwrap();
}
#[test]
fn frames_without_a_change_render_each_chart_once() {
let mut h = harness(two_charts());
assert!(builds() >= 2, "the charts were drawn");
let n = rendered_after(&mut h, |h| h.run_steps(30));
assert_eq!(n, 0, "30 idle frames render nothing again");
// Pointer movement and wheel scrolling (view state only) change no workbook.
let scroll_before = h.state().view().scroll;
let n = rendered_after(&mut h, |h| {
for i in 0..10 {
h.input_mut().events.push(Event::PointerMoved(egui::pos2(300.0 + i as f32 * 7.0, 400.0)));
h.input_mut().events.push(Event::MouseWheel {
unit: egui::MouseWheelUnit::Point,
source: egui::MouseWheelSource::Unknown,
delta: vec2(0.0, -2.0),
phase: egui::TouchPhase::Move,
modifiers: egui::Modifiers::NONE,
});
h.run_steps(1);
}
});
assert_ne!(h.state().view().scroll, scroll_before, "the sheet did scroll");
assert_eq!(n, 0, "hover and scrolling reuse the rendered charts");
assert_eq!(h.state().chart_cache.lock().unwrap().len(), 2);
}
#[test]
fn every_kind_of_change_renders_the_charts_again_exactly_once() {
let mut h = harness(two_charts());
type Case<'a> = (&'a str, Box<dyn Fn(&mut Harness)>);
let cases: Vec<Case> = vec![
("cell edit", Box::new(|h| exec(h, "cell.set", json!({"cell": "B5", "input": "99"})))),
("recalc through a dependency", Box::new(|h| exec(h, "cell.set", json!({"cell": "B2", "input": "7"})))),
("calculate now", Box::new(|h| exec(h, "formulas.calculateNow", json!({})))),
("undo", Box::new(|h| exec(h, "edit.undo", json!({})))),
("redo", Box::new(|h| exec(h, "edit.redo", json!({})))),
("row hide", Box::new(|h| exec(h, "home.hideRows", json!({"rows": "6:7"})))),
("chart resize", Box::new(|h| exec(h, "chart.set", json!({"chart": 1, "width": 360, "height": 240})))),
("format change", Box::new(|h| exec(h, "home.bold", json!({"range": "A1:B1"})))),
("number format", Box::new(|h| exec(h, "home.numberFormat", json!({"range": "B2:B12", "format": "0.00"})))),
(
"document theme",
Box::new(|h| {
exec(
h,
"pageLayout.themeColors",
json!({"colors": ["#000000", "#FFFFFF", "#44546A", "#E7E6E6", "#C00000", "#ED7D31", "#A5A5A5", "#FFC000", "#5B9BD5", "#70AD47", "#0563C1", "#954F72"]}),
)
}),
),
];
for (what, change) in cases {
let n = rendered_after(&mut h, |h| change(h));
assert_eq!(n, 2, "{what}: both visible charts rendered once");
let n = rendered_after(&mut h, |h| h.run_steps(5));
assert_eq!(n, 0, "{what}: and then nothing more");
}
// Zoom is part of the key too.
let n = rendered_after(&mut h, |h| exec(h, "view.zoom", json!({"percent": 150})));
assert_eq!(n, 2, "zoom");
}
#[test]
fn switching_sheets_and_loading_files_render_the_new_charts_once() {
let mut h = harness(two_charts());
exec(&mut h, "home.insertSheet", json!({"before": 1}));
h.run_steps(4);
// The new sheet has no charts; coming back renders this sheet's two once.
let n = rendered_after(&mut h, |h| exec(h, "sheet.activate", json!({"sheet": 0})));
assert_eq!(n, 2, "sheet switch");
let n = rendered_after(&mut h, |h| h.run_steps(5));
assert_eq!(n, 0);
// File load: the same workbook opened from bytes is a new document with its own charts.
let bytes = h.state_mut().session.execute("file.saveBytes", json!({})).unwrap();
let b64 = bytes["base64"].as_str().unwrap().to_string();
let n = rendered_after(&mut h, |h| exec(h, "file.open", json!({"name": "again.xlsx", "base64": b64})));
assert_eq!(n, 2, "file load");
assert_eq!(h.state().session.documents().len(), 2);
let n = rendered_after(&mut h, |h| h.run_steps(5));
assert_eq!(n, 0);
assert_eq!(h.state().chart_cache.lock().unwrap().docs(), 2, "both open documents are cached");
// Back in the first document nothing is rendered: its entries were kept.
let n = rendered_after(&mut h, |h| h.state_mut().session.set_active(0));
assert_eq!(n, 0, "the first document's charts were still cached");
// Closing a document forgets its entries; the other one is shown (and rendered) now.
let n = rendered_after(&mut h, |h| exec(h, "file.close", json!({"force": true})));
assert_eq!(h.state().session.documents().len(), 1);
assert_eq!(h.state().chart_cache.lock().unwrap().docs(), 1);
assert_eq!(n, 0, "the remaining document's charts were cached too");
}
#[test]
fn a_chart_with_a_volatile_series_is_rendered_on_every_frame() {
let mut h = harness(two_charts());
{
let d = h.state_mut().session.active_mut().unwrap();
let sh = Arc::make_mut(&mut d.wb).sheet_mut(0).unwrap();
sh.charts[0].series[0].values = "=RAND()".into();
}
h.run_steps(4);
let n = rendered_after(&mut h, |h| h.run_steps(6));
assert!(n >= 6, "the volatile chart is resolved again on each frame, got {n}");
assert!(n < 12, "the other chart still comes from the cache, got {n}");
}
#[test]
fn closed_documents_are_forgotten_without_painting_a_chart() {
let mut h = harness(two_charts());
assert_eq!(h.state().chart_cache.lock().unwrap().docs(), 1);
exec(&mut h, "file.new", json!({}));
h.run_steps(4);
assert_eq!(h.state().session.documents().len(), 2);
// The charts' document is no longer shown, but still open.
assert_eq!(h.state().chart_cache.lock().unwrap().docs(), 1);
h.state_mut().session.set_active(0);
h.run_steps(2);
exec(&mut h, "file.close", json!({"force": true, "document": true}));
h.run_steps(2);
assert_eq!(h.state().session.documents().len(), 1);
assert_eq!(h.state().chart_cache.lock().unwrap().docs(), 0, "no chart is painted, yet the closed document's entries are gone");
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.