swaits
915b7ce101
iai-callgrind is unmaintained; gungraun is the active fork. API is drop-in (use iai_callgrind → use gungraun, same library_benchmark / library_benchmark_group / main! macros), so the dispatch.rs body only needed the import rename. Also: - mise.toml: add cargo:gungraun-runner dep so the valgrind harness binary tracks the lib version automatically. - baseline.txt: rebaselined under gungraun_initial. Absolute numbers shifted up because gungraun's bench wrapper instruments more than iai-callgrind 0.16's did; comparable benches (terminate_event 69→68, h8_cross_tree 93→97) confirm HSM dispatch work itself is unchanged. Old iai-callgrind named baselines kept as historical context only.
501 lines
31 KiB
Markdown
501 lines
31 KiB
Markdown
# 003. Latency analysis: hsmc hot-path cost surface
|
||
|
||
This is an audit of where wall-clock and code-size cost lives in `hsmc`'s
|
||
event-dispatch path. It is intended to inform mitigation work for embedded
|
||
and embassy-rs use cases where every microsecond of dispatch overhead
|
||
couples directly into hardware-control loop tightness and jitter.
|
||
|
||
The audit is **analytical**, with three categories of evidence:
|
||
|
||
1. **Source reading** of `hsmc/src/lib.rs`, `hsmc/src/journal.rs`, and
|
||
`hsmc-macros/src/codegen.rs`.
|
||
2. **`cargo expand --release`** of two test programs (one with no
|
||
observation features, one with `tokio + journal`) to confirm what the
|
||
macro really emits.
|
||
3. **`cargo rustc --release --emit=asm`** spot-checks of the compiled
|
||
output to confirm LLVM-level claims (jump-table lowering, dead-code
|
||
elimination of unused name tables, async-closure code size).
|
||
|
||
The audit deliberately stops short of recommending mitigations. A ranked
|
||
menu of candidates is included at the end so a follow-up planning round
|
||
can pick from it; nothing here is a commitment.
|
||
|
||
---
|
||
|
||
## 1. Cost surface, ranked by per-event impact
|
||
|
||
| # | Source | Class | Per-event cost (estimate) | Location |
|
||
|----|-----------------------------------------------|-----------------------------|------------------------------------------------------------------------------------------------------------|---------------------------------------|
|
||
| # | Source | Class | Per-event cost (estimate) | Status |
|
||
|----|-----------------------------------------------|-----------------------------|------------------------------------------------------------------------------------------------------------|---------------------------------------|
|
||
| 1 | `dispatch().await` loop | Discretionary, async-only | 2 awaits cold-start / 1 await steady-state per dispatched event. ~free if action body never `Pending`-yields. | open |
|
||
| 2 | LCA + transition path build | Discretionary | ~~O(H²) `heapless::Vec<u16,32>::contains` scan~~ → ~~O(H) depth-walk~~ → **O(1) `__PATH_RANGE` lookup**. Up/self/lateral folded into the precomputed table; `lca()`, `is_up_transition()`, and the per-call `heapless::Vec<u16,16>` ancestry build are all gone. | resolved |
|
||
| 3 | Parent walk for handler search | Discretionary | ~~O(H) `__PARENT` walk + per-hop `__handler_lookup` call~~ → **O(1) `__DISPATCH[(state, event)]` lookup**. Every (state, event) pair statically resolved at codegen. `__handler_lookup` retained for timer dispatch only. | resolved |
|
||
| 4 | `__handler_lookup` nested match (timer path) | Intrinsic | Still used for timer dispatch. LLVM lowers to jump tables (verified `LJTI*`). ~1 indirect jump per call. | open (already at floor) |
|
||
| 5 | `run_action` dispatch | Intrinsic | One match arm + monomorphized trait call + 1 vtable hop on `&mut dyn QueuePush` (verified devirtualized when callsite type is known). | open (already at floor) |
|
||
| 6 | Event queue push/pop | Intrinsic | `heapless::Deque::push_back` / `pop_front`, both O(1). | open (already at floor) |
|
||
| 7 | `__chart_observe!` macro arms | Compile-eliminable when off | Zero residue when all sink features off. Each call site collapses to `{};`. | verified zero-cost |
|
||
| 8 | Journal `Vec::push` per atom | Conditional on `journal` | Amortized O(1); ~16 B per `TraceEvent`. ~11 push sites fire per transition. | opt-in |
|
||
| 9 | Async-fn future size (binary cost) | Discretionary, async-only | ~3000 asm lines of chart machinery for a 5-state chart; dominated by async-fn state machines. | open (mitigation H3) |
|
||
| 10 | `tokio::sync::mpsc::unbounded_channel` | Tokio-only, std-bound | Heap-backed channel for cross-task event injection. Embassy uses bounded `embassy_sync::channel`. | feature-specific |
|
||
| 11 | TimerTable per-step / per-exit fixed cost | Discretionary | ~~Unconditional `pop_expired` + `cancel_state` calls every step / exit~~ → **inlined `is_empty()` + `#[cold]` non-empty body** (runtime branch on charts that use timers; compile-time elided on timer-free charts). | resolved |
|
||
| 12 | TimerEntry size + per-decrement work | Discretionary | ~~`remaining_ns: u128`, 32-byte entry, u128 saturating-sub per decrement~~ → **`u64`, 16-byte entry, u64 saturating-sub** (~584-year ceiling; Duration::from_nanos round-trips exactly). | resolved |
|
||
| 13 | `do_terminate()` exit walk | Discretionary | ~~Runtime `__PARENT` walk + `pop_front`-loop queue drain~~ → **precomputed `__TERMINATE_DATA` slice + `Deque::clear()`** (O(1)). | resolved |
|
||
|
||
Items 2, 3, 11, 12, 13 are fully resolved by the precompute / inline-
|
||
empty-check passes in this round of work — see `hsmc/benches/baseline.txt`
|
||
for the per-pass delta blocks. Items 4–6 are at or near the algorithmic
|
||
floor for hierarchical state machines. Item 7 is verified zero-cost.
|
||
Items 1 (async overhead) and 9 (async machinery binary size) are the
|
||
only meaningful open items; both are addressable via a `dispatch_sync()`
|
||
fast path (mitigation H3 in §9), which would be a user-facing API
|
||
change and is therefore out-of-scope for this round.
|
||
|
||
---
|
||
|
||
## 2. Per-event cost model (analytical)
|
||
|
||
For a chart with hierarchy depth `H=3`, one entry action + one exit action,
|
||
a simple lateral transition, no observation features, `cargo build
|
||
--release`, on a Cortex-M4-class core (~168 MHz):
|
||
|
||
| Stage | Cycles (rough) | Notes |
|
||
|----------------------------------------|--------------------|------------------------------------------------|
|
||
| `queue.pop_front` | ~5–10 | `heapless::Deque` index op |
|
||
| `__event_to_id` | ~3–5 | match arm (jump table) |
|
||
| `__DISPATCH[(state, event)]` lookup | ~5 | one indexed load + sentinel branch |
|
||
| `run_action` (1 action) | ~10–20 | match + monomorphized call + 1 vtable hop |
|
||
| Path lookup (`__PATH_RANGE`) | ~5 | one indexed load + slice arithmetic |
|
||
| Exit chain (H states × A actions) | ~3 × H + 30 × A | per-state work is now ~3 instr each |
|
||
| Enter chain (H states × A actions) | ~3 × H + 30 × A | per-state work is now ~3 instr each |
|
||
| Timer machinery (timer-free chart) | 0 | codegen-elided when `ir.duration_triggers.is_empty()` |
|
||
| Timer machinery (timer chart, no fire) | ~3 | inlined `is_empty()` branches × 3 |
|
||
| Timer machinery (timer firing) | ~30–40 | decrement + pop_expired + dispatch_trigger |
|
||
| **Total `.step()` steady-state** | ~0.4 – 0.8 µs | for H=3, A=1; user action body excluded |
|
||
| Async overhead (`.dispatch()` loop) | per-await checkpoint | ~free if no `Pending`-yield |
|
||
|
||
These are back-of-envelope numbers; actual measurements would tighten
|
||
them by ~2× in either direction, depending on inlining decisions.
|
||
|
||
For empirical numbers (deterministic, instruction-counted), see
|
||
`hsmc/benches/baseline.txt`. Headline numbers (current):
|
||
h2_warm_lateral 84 instr / 397 cycles; h4_cross_tree 101 instr / 456
|
||
cycles; h8_cross_tree 93 instr / 443 cycles; bubble_top 99 instr /
|
||
453 cycles (4-hop handler resolution); bubble_cross_tree 94 instr /
|
||
444 cycles (4-hop bubble + 10-state cross-tree); terminate_event 69
|
||
instr / 311 cycles; timer_fire_dispatch 191 instr / 706 cycles;
|
||
chain_self_emit 419 instr across 4 events (≈105 instr/event).
|
||
Cumulative on h8_cross_tree: **-82% instructions / -72% cycles** vs
|
||
the original O(H²) LCA scan.
|
||
|
||
---
|
||
|
||
## 3. Spot-check evidence
|
||
|
||
### 3.1 `__chart_observe!` is zero-cost when off (cargo expand)
|
||
|
||
Test: `tests/state_chart_const.rs`, with no observation features enabled.
|
||
|
||
In the expanded source (`/tmp/hsmc_expand_no_features.rs`, 911 lines), every
|
||
observation site collapses to an empty block:
|
||
|
||
```rust
|
||
// in `step()`:
|
||
if self.current.is_none() {
|
||
{}; // would be observe_started
|
||
self.enter_path(0);
|
||
return self.timers.min_remaining();
|
||
}
|
||
// ...
|
||
if let Some((state, trig)) = self.timers.pop_expired(&__DEPTH) {
|
||
let __t_state = state;
|
||
let __t_trigger = trig;
|
||
{}; // would be observe_timer_fired
|
||
// ...
|
||
}
|
||
```
|
||
|
||
A grep for any of `TraceEvent::`, `::log::`, `::tracing::`, `::defmt::`,
|
||
`JournalSink::push` in the expanded code returns **zero matches**. The
|
||
macro arms entirely vanish.
|
||
|
||
`JournalSink` itself becomes a unit struct when the feature is off:
|
||
|
||
```rust
|
||
#[cfg(not(feature = "journal"))]
|
||
pub struct JournalSink; // ZST — 0 bytes in the chart struct
|
||
```
|
||
|
||
so the `__journal` field on the chart costs zero bytes at runtime.
|
||
|
||
### 3.2 Name lookups are dead-code-eliminated (cargo rustc --emit=asm)
|
||
|
||
Test: `tests/det_lateral.rs`, built with `--features tokio,journal`.
|
||
|
||
Even with `journal` enabled, a grep across the 22,477 lines of generated
|
||
asm for `state_name`, `action_name`, `event_name`, or `timer_name` returns
|
||
**zero matches**. The journal stores `u16` indices, not strings, and no
|
||
trace-* feature is on, so the name-lookup helper functions are uncalled
|
||
and DCE'd from the final binary.
|
||
|
||
This means even if a user enables `journal` for replay/verification, they
|
||
pay zero binary cost for the human-readable name tables until they also
|
||
enable a `trace-*` sink.
|
||
|
||
### 3.3 LLVM lowers handler matches to jump tables
|
||
|
||
Same asm file. Grep for `LJTI`:
|
||
|
||
```asm
|
||
leaq .LJTI2_0(%rip), %rcx
|
||
jmpq *%rax
|
||
.LJTI2_0:
|
||
.long .LBB2_1-.LJTI2_0
|
||
.long .LBB2_28-.LJTI2_0
|
||
.long .LBB2_29-.LJTI2_0
|
||
.long .LBB2_23-.LJTI2_0
|
||
```
|
||
|
||
Multiple jump tables are present, each sized roughly to the chart's
|
||
state/event count. This corroborates the assumption that
|
||
`__handler_lookup`'s nested `match (state_id) { match (kind, trigger_id) }`
|
||
lowers to a single indirect jump on platforms LLVM can target with one,
|
||
not a chain of compares.
|
||
|
||
### 3.4 Async machinery code size
|
||
|
||
Symbol-by-symbol asm sizes from `det_lateral`:
|
||
|
||
| Symbol (async closure / future) | Asm lines | Notes |
|
||
|---------------------------------|-----------|----------------------------------------------|
|
||
| `Lat::exit_state` | ~275 | one `.await` per exit action |
|
||
| `Lat::run_action` | ~349 | match arm + N monomorphized async branches |
|
||
| `Lat::run_handlers` | ~826 | loop over actions, each `.await` |
|
||
| `Lat::enter_state_no_descent` | ~217 | |
|
||
| `Lat::step` | ~970 | inlines `lca`, `is_up_transition`, etc. |
|
||
| `Lat::dispatch` | ~137 | thin loop wrapper |
|
||
| **Lat-chart total** | **~2,800**| async machinery for one 5-state chart |
|
||
|
||
For comparison, `Lat::new` is 141 lines. The async coloring
|
||
roughly doubles to triples the binary footprint of a chart relative to a
|
||
pure sync codegen. On Cortex-M0/M0+ where flash is small, this matters.
|
||
|
||
### 3.5 Journal expansion adds N pushes, nothing else (cargo expand)
|
||
|
||
Same test, expanded with `--features tokio,journal`
|
||
(`/tmp/hsmc_expand_with_journal.rs`, 2,426 lines vs. 911 lines without).
|
||
|
||
Counts:
|
||
- 104 total `TraceEvent::*` constructions.
|
||
- 20 distinct variant names (the full vocabulary).
|
||
- 8 `Vec::push` call sites inside `step()` — but only one fires per
|
||
invocation (timer-fired path, event-received path, etc., are mutually
|
||
exclusive).
|
||
|
||
The diff against the no-feature expansion is exactly: every `{};`
|
||
placeholder becomes a `(&mut self.__journal).push(TraceEvent::...)`. No
|
||
other infrastructure is added. No locking, no allocation per push beyond
|
||
the amortized `Vec` growth.
|
||
|
||
---
|
||
|
||
## 4. Observability cost matrix
|
||
|
||
Distilled from `lib.rs:158-712` and the spot-checks above:
|
||
|
||
| Feature(s) | Per-call CPU | Per-call alloc | Off → fully elided? |
|
||
|-------------------|-------------------------------------------|--------------------------|-------------------------------|
|
||
| `(none)` | 0 | 0 | Yes (verified) |
|
||
| `journal` | `Vec::push` ~10 ns amortized | ~16-24 B amortized | n/a |
|
||
| `trace-defmt` | format-hash u32 + field write | 0 | Yes |
|
||
| `trace-log` | `log_enabled!()` check + format if passes | 0 unless format | Yes (with small residual when on but level filtered) |
|
||
| `trace-tracing` | unconditional field collection + span | 0 | Yes (with ~30-cycle residual when on but no subscriber) |
|
||
|
||
The codegen emits **~11 `__chart_observe!` calls per typical transition**
|
||
in deterministic order: `EventReceived` → `EventDelivered` →
|
||
`TransitionFired` → `ExitBegan` → `ActionInvoked{Exit}` → `Exited` →
|
||
`EnterBegan` → `ActionInvoked{Entry}` → `Entered` → `TransitionComplete`,
|
||
plus action-handler markers. That's the multiplier on every per-call
|
||
number above.
|
||
|
||
---
|
||
|
||
## 5. What is *not* a problem (audited and dismissed)
|
||
|
||
- **Handler-lookup growth with chart size** — confirmed jump-table
|
||
lowering (§3.3). O(1) per event regardless of state or event count
|
||
(modulo cache effects from larger jump tables).
|
||
- **Trait-object cost on action dispatch** — only the `&mut dyn QueuePush`
|
||
proxy is `dyn`. User actions are monomorphized trait methods (one match
|
||
arm per action ID, direct calls). One vtable hop per emit, *not* per
|
||
action.
|
||
- **Observation overhead with features off** — confirmed zero. Verified
|
||
three ways: macro arm structure (every body `#[cfg]`-gated), expanded
|
||
source (every site is `{};`), and asm (no name-lookup symbols, no trace
|
||
symbols).
|
||
- **Heap allocation in default build** — `extern crate alloc` is confined
|
||
to `journal.rs:26`. With `journal` off, the runtime is fully stack-only.
|
||
Verified: no `Vec`, `Box`, or `String` in expanded sync code.
|
||
- **`Pin<Box<...>>` futures on the hot path** — none. Chart futures are
|
||
inline state machines, not boxed.
|
||
- **Tokio `unbounded_channel` for embedded** — irrelevant: tokio is `std`
|
||
anyway. Embassy uses bounded `embassy_sync::channel::Channel` (no
|
||
alloc).
|
||
|
||
---
|
||
|
||
## 6. Event entry points
|
||
|
||
Events reach the chart's internal `heapless::Deque` via four distinct
|
||
paths. Each has its own latency, wakeup, ordering, and backpressure
|
||
profile, summarized below.
|
||
|
||
| Path | API | Backing | Wakeup | Ordering | Backpressure |
|
||
|------|-------------------------------------------|--------------------------------------------|-------------------------|----------------------------------------|------------------------------------|
|
||
| 1 | `chart.send(event)` (sync, single-task) | `heapless::Deque::push_back` | none — caller drives | FIFO within queue | `Err(QueueFull)` immediate |
|
||
| 2a | `chart.sender().send(ev)` (tokio) | `tokio::sync::mpsc::unbounded_channel` | tokio task wake | FIFO; biased select deprioritizes vs. durings | **unbounded memory** |
|
||
| 2b | `chart.sender().send(ev)` (embassy) | `embassy_sync::channel::Channel` (bounded) | embassy task wake | FIFO; same biased-select | `Err(Full)` (try_send) or backpressure-await |
|
||
| 3 | `actx.emit(ev)` from inside an action | same internal `Deque` as path 1 | none — drained inline | drained synchronously after current handler completes; *before* `step()` returns | sticky overflow flag |
|
||
| 4 | return from a `during:` future | `select!` arm in run loop | driver-specific | biased priority over channel events | silent drop on `Deque` full |
|
||
|
||
**Path 1 (sync send)** — `codegen.rs:2316-2319`. Bare
|
||
`Deque::push_back`; owning task only, no synchronization. ~5–10 cycles.
|
||
Caller is responsible for invoking `step()` (or `dispatch()` under an
|
||
async feature) to actually process the event.
|
||
|
||
**Path 2 (cross-task `sender()`)** — `codegen.rs:1492` (tokio sender),
|
||
`1638` (embassy sender), `1308` / `1405` (run-loop receive sites). The
|
||
canonical cross-thread / ISR path per the spec. Tokio uses an unbounded
|
||
MPSC (heap-backed; no backpressure signal); embassy uses a bounded
|
||
`Channel<M, E, N>` with `try_send` for ISR-safe non-blocking emits and
|
||
an `async send` that backpressures the producer. The receiver task
|
||
wakes on send; one iteration of the run-loop's `select!` consumes the
|
||
event and pushes it into the internal `Deque`.
|
||
|
||
**Path 3 (self-emit from action)** — `actx.emit(...)` goes through
|
||
`EmitProxy::push` (`hsmc/src/lib.rs`) which writes into the same
|
||
internal `Deque` as Path 1. Self-emitted events are drained in the
|
||
*same* `step()` call that emitted them — `dispatch()` runs `while
|
||
!queue.is_empty() { step().await }` until quiescence. Nothing crosses a
|
||
task boundary.
|
||
|
||
**Path 4 (`during:` return)** — `codegen.rs:1306–1313` (tokio with
|
||
durings), `1392+` (embassy). Durings are racing futures spawned in the
|
||
run-loop's `select!`. When one resolves to an event, the `select!`
|
||
unblocks and the event is pushed into the internal `Deque`. The
|
||
`select!` is `biased;` so durings have priority over the channel —
|
||
relevant if a during is a poll-based driver that's almost always
|
||
ready (see §8).
|
||
|
||
**One ordering caveat**: there is no global FIFO across paths 1–4.
|
||
Within each path, events are FIFO; across paths, the order depends on
|
||
when each path's wakeup arrives at the run loop. For most charts this
|
||
is a non-issue, but a chart that mixes high-frequency cross-task sends
|
||
with rapid self-emits could observe self-emits processed before
|
||
external events that arrived "first" in wall-clock terms.
|
||
|
||
---
|
||
|
||
## 7. Cooperative-driving audit
|
||
|
||
The library targets embassy-rs's single-priority cooperative scheduler,
|
||
where any tight loop without an `.await` can starve other tasks. An
|
||
audit of every loop and await pattern in the runtime and codegen:
|
||
|
||
| Loop / await | Location | Bounded? | Awaits per iter? | Verdict |
|
||
|---------------------------------------|---------------------------|-------------------------|--------------------------|---------------------|
|
||
| Main `run()` outer | codegen.rs:1290+, 1379+ | by `terminated` flag | yes — always | cooperative |
|
||
| `dispatch()` drain loop | codegen.rs:2339 | by queue size | only via `step().await` | suspect — fairness |
|
||
| Transition exit/enter slice loops | codegen.rs (transition) | by precomputed slice len| yes (async variant) | OK |
|
||
| Termination drain | codegen.rs:2750 | by hierarchy + queue | yes (async variant) | OK |
|
||
| Timer decrement / pop | runtime / lib.rs | by timer-table size | sync, off the event-loop | OK |
|
||
| Send/recv backends | codegen.rs:1308, 1405 | n/a | always `.await` | cooperative |
|
||
|
||
No `try_recv` patterns anywhere. No fixed-period polling. The library
|
||
is fundamentally event-driven and embassy-friendly.
|
||
|
||
**One latent fairness characteristic**: the `dispatch()` drain loop —
|
||
`while !self.queue.is_empty() { step(Duration::ZERO).await }` — never
|
||
yields to the executor between iterations. If user actions are all
|
||
synchronous and they emit a chain of follow-on events (action A emits
|
||
B, B emits C, …), each `step().await` completes inline, and the loop
|
||
becomes effectively synchronous for the duration of the chain. Embassy
|
||
high-priority tasks could be delayed by the chain length.
|
||
|
||
This is **not a bug** — `dispatch()` is documented to drain to
|
||
quiescence — but it's worth knowing about. A future option (not part of
|
||
this round of work) would be a feature-gated
|
||
`embassy_futures::yield_now().await` every Nth iteration, or a
|
||
chart-level config to bound chain length. Not done by default because
|
||
it would serialize the common case for no benefit.
|
||
|
||
---
|
||
|
||
## 8. Correctness invariants surfaced during the audit
|
||
|
||
Three contracts that aren't bugs, but warrant explicit documentation
|
||
because they are easy to miss when reading the code:
|
||
|
||
**Sticky overflow flag in `EmitProxy`** (`hsmc/src/lib.rs`,
|
||
`EmitProxy::push`). When a self-emit fails because the internal `Deque`
|
||
is full, an `__overflow` flag is set on the chart. *Every* subsequent
|
||
`actx.emit(...)` in the same dispatch chain returns `Err(QueueFull)`,
|
||
even after the queue has drained. The flag is cleared at the top of
|
||
each `dispatch()` call by `take_overflow()`. This is intentional — it
|
||
prevents a chart from observing a partially-applied sequence of
|
||
self-emissions where some made it into the queue and others did not.
|
||
Authors of actions that emit multiple events should treat
|
||
`Err(QueueFull)` as terminal for the current chain.
|
||
|
||
**Biased select in run loop** (tokio: `codegen.rs:1306–1313`; embassy:
|
||
`1392+`). The `select!` is `biased;`, so durings are always polled
|
||
before the cross-task channel. For most charts this is the right
|
||
priority — a sensor driver should pre-empt a UI event. But for a
|
||
`during:` that wraps a poll-based driver (one that returns `Ready`
|
||
nearly every poll), the channel can be starved indefinitely. Cure:
|
||
make the during yield (`embassy_futures::yield_now`) when there's
|
||
nothing real to report.
|
||
|
||
**Cancel-safety contract on durings** (`hsmc/src/lib.rs:53–60`). Every
|
||
`.await` in a `during:` future must be a clean resume point, because
|
||
the future will be dropped if the state transitions before it
|
||
completes. This is the standard async-cancel-safety contract, but it
|
||
is easy to violate by holding a mutable borrow across an await — the
|
||
borrow is "valid" when resumed but the surrounding state may have
|
||
moved on.
|
||
|
||
---
|
||
|
||
## 9. Candidate mitigations (menu, NOT a commitment)
|
||
|
||
Sized for sequencing in a follow-up plan-mode session. "Effort" is gut
|
||
feel: L = afternoon, M = couple of days, H = a week or more.
|
||
|
||
| ID | Mitigation | Targets | Impact | Effort | Cost |
|
||
|-----|-----------------------------------------------------------------------------------------------------------------------------------|-----------|-----------------------------------------|--------|---------------------------------------|
|
||
| H0 | Replace `lca()` with an O(H) depth-walk via the `__DEPTH` table. | #2 | **Landed.** | - | - |
|
||
| H1 | Codegen per-(from, to) precomputed exit/enter chains as `__PATH_DATA` + `__PATH_RANGE`. | #2 | **Landed.** Up/self/lateral folded into one indexed lookup; `lca()` and `is_up_transition()` removed. | - | ~`6·N²` B index + ~`N²·H` B path data |
|
||
| T1 | Inlined `is_empty()` early-out on `pop_expired` / `min_remaining` / `decrement` / `cancel_state` with `#[cold]` non-empty bodies. | #11 | **Landed.** | - | - |
|
||
| T2 | Codegen-static elide of all `TimerTable` calls when `ir.duration_triggers.is_empty()`. | #11 | **Landed.** Most charts are timer-free; `step()` returns `None` directly. | - | - |
|
||
| H4 | `__DISPATCH[(state, event)]` const array; one indexed lookup replaces the runtime __PARENT bubble walk + per-hop `__handler_lookup`. | #3 | **Landed.** Each (state, event) statically resolved at codegen. | - | ~24 B per (state, event) pair |
|
||
| U1 | Shrink `TimerEntry.remaining_ns: u128 → u64` (~584-year ceiling). Halves entry size; replaces u128 saturating-sub with u64. | #12 | **Landed.** | - | - |
|
||
| K1 | `__TERMINATE_DATA` per-state precomputed exit chain (root inclusive); `do_terminate()` indexes a slice instead of walking __PARENT, and uses `Deque::clear()` (O(1)) for the queue drain. | #13 | **Landed.** terminate_event -22.5% instr / -23.4% cycles. | - | ~`(H+1)·N` B path data |
|
||
| H3 | Provide a `dispatch_sync()` API that bypasses `.await` when the chart's actions are fully synchronous. | #1, #9 | High for sync-action charts | L-M | API surface growth (user-facing) |
|
||
| H5 | Sparse `__PATH_RANGE` / `__DISPATCH` for very large charts (N > 64): emit only reachable pairs with a small perfect-hash. Latency-neutral; cuts O(N²) static memory growth. | cost mitigation | Low at typical N; significant at N > 100 | M | codegen complexity |
|
||
| M1 | Eliminate the trailing `step().await` in `dispatch()` when queue empties mid-step. | #1 | Low | L | minor refactor |
|
||
| M2 | Lazy field eval in `trace-tracing` arm using `tracing`'s field-closure form to skip evaluation when filtered. | #8 (on) | Low | L | none |
|
||
|
||
H0/H1/T1/T2/H4/U1/K1 all landed in the most recent round of work.
|
||
Callgrind now reports the entire HSM machinery as a single `step`
|
||
symbol — every helper inlined. The only remaining optimization avenue
|
||
that meaningfully affects per-event latency is H3 (`dispatch_sync()`),
|
||
which is excluded as user-facing. Memory-side mitigations (H5) only
|
||
matter for N > 64-state charts; embedded users with large charts are
|
||
the audience.
|
||
|
||
---
|
||
|
||
## 10. Where to look in the source
|
||
|
||
For anyone reading this audit and wanting to verify or extend it:
|
||
|
||
- **`hsmc/src/lib.rs`**
|
||
- `:94` — the `#![cfg_attr(... no_std)]` boundary
|
||
- `:158-712` — `__chart_observe!` macro, all observation arms
|
||
- `:737-772` — `JournalSink` ZST/Vec duality
|
||
- **`hsmc/src/journal.rs`**
|
||
- `:26-32` — `extern crate alloc` and `Vec` import (only here)
|
||
- `:65-150+` — `TraceEvent` enum (the journal vocabulary)
|
||
- **`hsmc-macros/src/codegen.rs`**
|
||
- `compute_transition_paths()` (top of file, after `compute_chart_hash`) — builds `__PATH_DATA` + `__PATH_RANGE` at codegen time
|
||
- `__PARENT`, `__DEPTH`, `__DEFAULT_CHILD`, `__PATH_DATA`, `__PATH_RANGE` static-table emission (search "const __PARENT")
|
||
- `step()` (search "fn step" / "async fn step") — sync vs. async branches
|
||
- `dispatch()` await loop (search "fn dispatch")
|
||
- `run_action` (search "fn run_action") — sync vs. async
|
||
- `transition` (search "fn transition") — now a thin slice-iter wrapper
|
||
- name-lookup helpers (`__state_name`, `__action_name`, etc.) at `:631-667`
|
||
- **Test reference shape**: `hsmc/tests/state_chart_const.rs` is the
|
||
smallest sync-only chart in the tree; `hsmc/tests/det_lateral.rs` is
|
||
the reference async + journal shape used for the asm spot-check.
|
||
|
||
---
|
||
|
||
## 11. Reproducing the spot-checks
|
||
|
||
```sh
|
||
# Zero-cost observation verification (expand → no observation residue)
|
||
cargo expand --release --test state_chart_const \
|
||
> /tmp/expand_no_features.rs --manifest-path hsmc/Cargo.toml
|
||
grep -E "TraceEvent::|::log::|::tracing::|::defmt::" /tmp/expand_no_features.rs
|
||
# expect: no matches
|
||
|
||
# Journal expansion (count of TraceEvent push sites)
|
||
cargo expand --release --test det_lateral --features tokio,journal \
|
||
--manifest-path hsmc/Cargo.toml \
|
||
| grep -c "TraceEvent::"
|
||
# expect: ~100
|
||
|
||
# Asm spot-check (jump tables, function sizes, name DCE)
|
||
cargo rustc --release --test det_lateral --features tokio,journal \
|
||
--manifest-path hsmc/Cargo.toml -- --emit=asm
|
||
ASM=$(find target -name 'det_lateral*.s' | head -1)
|
||
grep -E "LJTI|jmpq?[[:space:]]+\*" "$ASM" # jump tables
|
||
grep -E "state_name|action_name" "$ASM" # expect no matches
|
||
```
|
||
|
||
---
|
||
|
||
## 12. Summary
|
||
|
||
`hsmc`'s hot path is mostly already at the algorithmic floor for
|
||
hierarchical state machines. The intrinsic per-event cost (parent walk,
|
||
handler lookup, action dispatch, queue ops) is small and well-monomorphized.
|
||
Observation cost is verified zero when features are off, and stays
|
||
proportional to the user's chosen sink mix when on.
|
||
|
||
**Items #2, #3, #11, #12, and #13 in §1 have all landed** across six
|
||
optimization passes (H0 → H1 → T1 → H4 → T2 → K1+U1). Cumulative impact
|
||
on the deepest dispatch (h8_cross_tree) is **-82% instructions / -72%
|
||
cycles** vs the original O(H²) LCA scan. The headline wins by bench:
|
||
|
||
- `terminate_event` 69 instr / 311 cycles (~14 instr of HSM work after
|
||
subtracting bench wrapper) — `do_terminate()` is one indexed slice
|
||
+ `Deque::clear()`.
|
||
- `bubble_top` 99 instr / 453 cycles — 4-hop handler resolution
|
||
collapses to one indexed `__DISPATCH` lookup; per-dispatch cost is
|
||
bench-shape-independent.
|
||
- `bubble_cross_tree` 94 instr / 444 cycles — realistic HSM worst
|
||
case (deep bubble + 10-state cross-tree) costs the same as a plain
|
||
cross-tree because bubble lookup is O(1) and transition is
|
||
O(path-length).
|
||
- `h8_cross_tree` 93 instr / 443 cycles — 7-deep cross-tree dispatch.
|
||
|
||
Callgrind reports the entire HSM machinery as a single `step` symbol —
|
||
`run_handlers`, `run_action`, `transition`, `do_terminate`,
|
||
`exit_state`, `enter_state_no_descent`, `EmitProxy::push`, all four
|
||
`TimerTable` methods, the dispatch-table lookup, and the
|
||
terminate-path lookup are all inlined.
|
||
|
||
Cost remaining, in priority order:
|
||
|
||
1. **Async coloring code-size cost** (item #9) — chart machinery is
|
||
~3,000 asm lines for a 5-state chart, dominated by async-fn state
|
||
machines. Mitigation H3 (a `dispatch_sync()` fast path) would let
|
||
users with all-sync actions skip this entirely. **User-facing API
|
||
change** — out of scope for the current optimization pass.
|
||
2. **Bench-wrapper noise floor** — at the smallest dispatch's ~38–80
|
||
instructions, the gungraun wrapper (`black_box`, `send`,
|
||
instrumented call-edge crossing) accounts for ~45 instructions.
|
||
Sub-bench-wrapper improvements are below the measurement floor.
|
||
3. **Memory cost of `__PATH_DATA` / `__PATH_RANGE` / `__DISPATCH` /
|
||
`__TERMINATE_DATA` at large N** — `__PATH_RANGE` is O(N²);
|
||
`__DISPATCH` is O(N×E); `__TERMINATE_DATA` is O(N×H). For N ≤ 32 /
|
||
E ≤ 16 / H ≤ 8 the total static footprint is a few KiB. A
|
||
64-state × 32-event chart would push past ~80 KiB. Mitigation H5
|
||
sketches a sparse encoding.
|
||
|
||
All addressable purely in `hsmc-macros/src/codegen.rs` and `hsmc/src/lib.rs`
|
||
without breaking runtime semantics or feature gates. The bench harness
|
||
in `hsmc/benches/dispatch.rs` (13 benches, every dispatch shape
|
||
covered) is in place to measure each mitigation as it lands.
|