Catcrafts/Crafter.Graphics
2
0
Fork 0
Code Issues 1 Pull requests Projects Releases Packages Wiki Activity Actions

perf(ui): LRU-evict the shaped-run cache instead of clearing it (#123) #143

Merged
catbot merged 2 commits from claude/issue-123 into master 2026-06-18 15:30:08 +02:00
Conversation 0 Commits 2 Files changed 3 +117 -6
catbot commented 2026-06-18 15:24:06 +02:00
Member
Copy link

Problem

UIRenderer::ShapeText memoizes origin-relative shaped runs in shapedRuns_. At the kMaxShapedRuns (8192) soft cap the cache did a full clear(). A stream of unique strings (FPS counters, timers) alongside many stable labels periodically nuked every stable entry, forcing a full-UI reshape (UTF-8 decode + per-glyph atlas lookup + layout) on the very next frame — a recurring latency spike.

(Found by an adversarially-verified performance audit; distinct from the GPU-atlas eviction issue #55 — this is the CPU-side shaped-run cache.)

Fix

Replace clear-all with O(1) LRU eviction:

  • Add an auxiliary std::list<const ShapedRunKey*> shapedRunsLru_ (front = most recently used) holding pointers to the keys owned by the node-based unordered_map (stable across rehash). Each ShapedRun stores its list position in lruIt.
  • Hit → splice the entry to the front (O(1), keeps all iterators valid).
  • Overflow → pop the back (least-recently-used) and erase just that one entry (O(1)).
  • InvalidateFont now drops matching entries from both the map and the LRU list.

The hot set of labels, reshaped every frame, stays at the front and survives; only the cold tail of stale unique strings is recycled. Output is byte-identical to before — the glyph buffer is fully rewritten and re-flushed every frame regardless.

Net performance

  • Hit path (common case): one extra splice (~3 pointer writes), negligible next to the full-string hash lookup the hit already performs. No measurable regression.
  • Overflow: O(1) evict-one replaces an amortized O(n) destruction of 8192 entries.
  • Downstream: the periodic full-UI reshape cascade — the actual spike — is eliminated.

Strict win in the pathological case, negligible cost otherwise.

Tests

crafter-build test → 23 passed. Extended ShapeTextCache with introspection-backed checks (the eviction policy isn't observable through output or atlas.dirty):

  • cache size plateaus at a fixed cap — proves evict-one, not clear-all (a clear-all policy would drop to 1 and never plateau);
  • a hot label survives a churn of unique strings far past the cap;
  • the cache stays pinned at the cap (no full wipe);
  • an untouched cold string is eventually evicted (tail recycled).

Adds ShapedRunCacheSize() / IsShapedRunCached() accessors used by the test.

Resolves #123

## Problem `UIRenderer::ShapeText` memoizes origin-relative shaped runs in `shapedRuns_`. At the `kMaxShapedRuns` (8192) soft cap the cache did a full `clear()`. A stream of unique strings (FPS counters, timers) alongside many stable labels periodically nuked **every** stable entry, forcing a full-UI reshape (UTF-8 decode + per-glyph atlas lookup + layout) on the very next frame — a recurring latency spike. (Found by an adversarially-verified performance audit; distinct from the GPU-atlas eviction issue #55 — this is the CPU-side shaped-run cache.) ## Fix Replace clear-all with O(1) LRU eviction: - Add an auxiliary `std::list<const ShapedRunKey*> shapedRunsLru_` (front = most recently used) holding pointers to the keys owned by the node-based `unordered_map` (stable across rehash). Each `ShapedRun` stores its list position in `lruIt`. - **Hit** → `splice` the entry to the front (O(1), keeps all iterators valid). - **Overflow** → pop the back (least-recently-used) and erase just that one entry (O(1)). - `InvalidateFont` now drops matching entries from both the map and the LRU list. The hot set of labels, reshaped every frame, stays at the front and survives; only the cold tail of stale unique strings is recycled. Output is byte-identical to before — the glyph buffer is fully rewritten and re-flushed every frame regardless. ## Net performance - **Hit path (common case):** one extra `splice` (~3 pointer writes), negligible next to the full-string hash lookup the hit already performs. No measurable regression. - **Overflow:** O(1) evict-one replaces an amortized O(n) destruction of 8192 entries. - **Downstream:** the periodic full-UI reshape cascade — the actual spike — is eliminated. Strict win in the pathological case, negligible cost otherwise. ## Tests `crafter-build test` → **23 passed**. Extended `ShapeTextCache` with introspection-backed checks (the eviction policy isn't observable through output or `atlas.dirty`): - cache size **plateaus at a fixed cap** — proves evict-one, not clear-all (a clear-all policy would drop to 1 and never plateau); - a **hot label survives** a churn of unique strings far past the cap; - the cache **stays pinned at the cap** (no full wipe); - an **untouched cold string is eventually evicted** (tail recycled). Adds `ShapedRunCacheSize()` / `IsShapedRunCached()` accessors used by the test. Resolves #123 
At kMaxShapedRuns (8192) UIRenderer::ShapeText did a full shapedRuns_.clear().
A stream of unique strings (FPS counters, timers) alongside many stable labels
periodically nuked every stable entry, forcing a full-UI reshape the next frame.

Track recency with an auxiliary std::list<const ShapedRunKey*> (front = most
recently used) holding pointers to the keys owned by the node-based map. A hit
splices its entry to the front; an overflow pops the least-recently-used entry
from the back and erases just that one — both O(1). The hot set of labels,
reshaped every frame, stays at the front and survives, so the churn of unique
strings only recycles the cold tail. Output is byte-identical either way.

InvalidateFont now drops matching entries from both the map and the LRU list.
Adds ShapedRunCacheSize()/IsShapedRunCached() introspection hooks (the policy
isn't observable through output or atlas.dirty) and a ShapeTextCache test that
asserts the cache plateaus at a fixed cap (evict-one, not clear-all), the hot
label survives a churn past the cap, and an untouched cold string is evicted.

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
# Conflicts:
#	implementations/Crafter.Graphics-UI-Shared.cpp
#	interfaces/Crafter.Graphics-UI.cppm
catbot merged commit 80a69025eb into master 2026-06-18 15:30:08 +02:00
catbot deleted branch claude/issue-123 2026-06-18 15:30:08 +02:00
Sign in to join this conversation.
Reviewers
No reviewers
Labels
Clear labels   
claude:blocked

   
claude:done

   
claude:failed

   
claude:in-progress

   
claude:ready
No labels
claude:blocked
claude:done
claude:failed
claude:in-progress
claude:ready
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
Catcrafts/Crafter.Graphics!143
No description provided.