Make a parser fast and memory-bounded

how-to

Last updated: 2026-10-12 · Last reviewed: not recorded · Dates come from git history; this document was not re-checked against the code when this header was added.

Practices for Poka parser plugins, drawn from profiling this codebase and from reading fast parsers elsewhere. Every rule here has a worked example in parsers/; where a rule came from an outside implementation, it says so.

The constraints that shape everything

A parser plugin is a WASI command module running under caps declared in its own plugin.json:

"wasm": { "memory_mb": 64, "max_time_ms": 5000 }

Exceed either and the host kills the module and shows nothing. So the goal is not "fast in the abstract" — it is bounded: bounded memory, bounded time, bounded output, on adversarial as well as typical input.

Three consequences follow, and they drive most of the advice below:

1. The output is a preview, not a conversion. Nobody reads 1.2 million timeseries rows. Producing them costs memory you do not have and buys nothing.
2. You cannot assume the input is sane. A .ctb declaring a 4 GB uncompressed length, a zip bomb, a 9-byte varint of 0xFF — all are reachable from a file the user double-clicked.
3. Startup cost is part of the budget. A parser that spends 300 ms in dependency initialisation has spent 6% of a 5 s budget before reading a byte.

1. Stream once; never materialise what you will not show

The single highest-leverage rule.

poka-eso faces a 23 MB file with 1.2 million data lines. It makes one pass and keeps a fixed-size accumulator per report id:

// parsers/poka-eso/src/lib.rs
if let Some(v) = parts.next().and_then(|s| s.trim().parse::<f64>().ok()) {
    eso.variables[idx].observe(v);   // count, min, max, sum — 32 bytes
}

Peak memory is the dictionary, not the data — a few thousand Variable structs regardless of whether the file is 2 MB or 200 MB.

The alternative — collecting rows and summarising afterwards — is O(file size) memory for an O(dictionary size) answer.

Corollary: if a format has a header that describes the body, read the header, then decide what the body pass needs to collect. Do not collect first and filter later.

The read cap is the sandbox's, not a constant

f.take(cap).read_to_end(&mut buf) looks bounded and is not: take hides the file's length from read_to_end, whose Vec grows by doubling. A 36 MiB file ends up in a 64 MiB allocation, and a module granted 32 MiB traps with "Read: out of memory" before it has read a header. poka-wav failed on an 8 MiB WAV and poka-m2ts on a 35 MiB stream for exactly this reason, while both manifests were right (poka-interfaces#511).

Use poka_parser_common::read_capped and derive the cap from the grant:

pub const MEMORY_MB: u64 = 32;                       // the manifest's memory_mb
pub const MAX_BYTES: u64 = poka_parser_common::budget_bytes(MEMORY_MB);  // three quarters

read_capped reserves once from the file's real length and reads one byte past the cap, so a file over it is reported (capped) rather than silently passed off as the whole file. A unit test should keep MEMORY_MB equal to plugin.json, or the cap drifts from the sandbox it is meant to respect.

2. Index by the key the format already gives you

Formats usually number their own records. Use that number as an index.

// parsers/poka-eso/src/lib.rs — report ids are dense and start at 1
let mut by_id: Vec<Option<usize>> = Vec::new();
// ...
let Some(&Some(idx)) = by_id.get(id as usize) else { continue };

A Vec lookup is a bounds check and a load. A HashMap<i64, usize> is a hash, a probe, and a cache miss — per line, 1.2 million times.

idfkit reaches the same conclusion from the other direction with its ParsingCache: precompute per object type, not per object. Its docstring is explicit — "Eliminates repeated nested dict traversals during parsing."

Rule of thumb: if the key is a small dense integer, use a Vec. If it is a string you compare more than a few hundred times, hash it once into an index.

3. Bound every scan that is not the main pass

Detection, sniffing and header reads should look at a prefix, never the file.

// parsers/poka-osm/src/lib.rs
const SNIFF_BYTES: usize = 64 * 1024;
let head = prefix(text, SNIFF_BYTES);

idfkit does the same for version detection — content[:10240] — and it matters more than it looks: format dispatch runs on every file the user opens, including the ones this parser will reject.

Watch the slicing:

/// Borrow at most `max` bytes, backing up to a char boundary.
fn prefix(text: &str, max: usize) -> &str {
    if text.len() <= max { return text; }
    let mut end = max;
    while end > 0 && !text.is_char_boundary(end) { end -= 1; }
    &text[..end]
}

Slicing a &str mid-codepoint panics, and a parser must never panic — the host reports a crash, not a failed parse.

4. Cap the output, and say when you did

Every AST carries truncated. Use it rather than emitting an unbounded tree.

// The pattern used across the tree parsers
if used >= MAX_NODES { truncated = true; break; }

Expand a record only if the whole record fits:

// parsers/poka-eio/src/lib.rs
let children = if used + values.len() <= MAX_NODES {
    used += values.len();
    /* build them */
} else {
    truncated = true;
    vec![]      // a half-expanded record reads as data loss
};

poka-dsbxml takes this furthest, because it has to: a ten-zone model holds 34,609 <Attribute> and 17,880 <Point3D> elements. It walks only the hierarchy elements and collapses everything else to a count per type. Its test asserts the result stays under a quarter of the raw element count.

5. Validate declared sizes before you allocate

Any length that came from the file is hostile until checked.

// parsers/poka-ctb/src/lib.rs
if declared_uncompressed as usize > MAX_INFLATED {
    return Err(format!("CTB declares {declared_uncompressed} uncompressed bytes, above the inflate cap"));
}

// parsers/poka-ifczip/src/lib.rs
if size > MAX_INFLATED {
    return Err(format!("inner model is {size} bytes, above the {MAX_INFLATED}-byte inflate cap"));
}

The same applies to loop bounds derived from file data — page pointers, record counts, nesting depth:

// parsers/poka-isproj/src/lib.rs
const MAX_PAGES_VISITED: usize = 10_000;
if page == 0 || depth > 32 || *visited >= MAX_PAGES_VISITED { return; }

A corrupt b-tree with a cycle will otherwise spin until the host kills it.

Also guard forward progress. A malformed length of zero turns a while into an infinite loop:

// parsers/poka-cat/src/lib.rs
if tlv.end <= at { return; }   // no forward progress: malformed
at = tlv.end;

6. Work on bytes; decode late and once

Decoding a whole file to String costs a full copy plus UTF-8 validation. When you only need structure, work on &[u8].

This is idfkit's biggest single win: its tokenizer runs byte-level regexes (_OBJECT_PATTERN.finditer(content) where content is bytes), decoding per-field and lazily. The per-character loop lives inside the C regex engine instead of the interpreter.

In Rust the equivalent is to avoid the String round-trip for binary formats — poka-cat, poka-isproj, poka-ctb, poka-blo and poka-ekd all read &[u8] directly and only build strings for the fields they emit.

When you do need text, decode exactly once, and if the encoding is not UTF-8, transcode with a table rather than a dependency:

// parsers/poka-err/src/lib.rs — 128-entry table, no crate
pub fn decode(bytes: &[u8]) -> (String, &'static str) {
    match std::str::from_utf8(bytes) {
        Ok(s) => (s.to_string(), "UTF-8"),
        Err(_) => (bytes.iter().map(|&b| if b < 0x80 { b as char }
                                    else { CP1250_HIGH[(b - 0x80) as usize] }).collect(),
                   "Windows-1250"),
    }
}

7. Prefer no dependency to a small one

idfkit is instructive here: zero required runtime dependencies, all stdlib, no compiled extensions — every Requires-Dist is behind an extra == marker. That is a cause of its speed, not a trade-off against it. Importing pandas alone costs more wall-clock than parsing a small IDF outright.

The wasm equivalent is module size and instantiation cost. Two examples from this codebase:

• poka-isproj reads the SQLite file format directly — header, sqlite_master b-tree, varints, serial types, overflow chaining — rather than linking an embedded database engine to list seven table names.
• poka-cat has a ~40-line DER reader instead of a full ASN.1 stack, because the Microsoft catalog payload has no published module to decode against anyway. It still uses x509-parser for certificates, which are standard — the rule is "no gratuitous dependency", not "no dependencies".

Weigh it honestly: if the format is genuinely complex and a crate is already in the workspace (zip, flate2, roxmltree, symphonia), use it.

8. Avoid quadratic accumulation

The lazy pattern for counting distinct things is a linear scan per item:

match list.iter_mut().find(|(k, _)| k == key) {   // O(n) per item
    Some((_, c)) => *c += 1,
    None => list.push((key.to_string(), 1)),
}

A bounded alphabet is a necessary condition for this, not a sufficient one. The cost is lookups × alphabet, and the lookup count usually scales with the file even when the alphabet does not.

poka-dsbxml had exactly this. XML element names are a bounded alphabet — around eighty distinct tags in a DesignBuilder export — so the linear scan looked safe. But it ran once per element, and a 10 MB export has hundreds of thousands of them: tens of millions of string comparisons to maintain a census of eighty entries. Replacing it with a HashMap<String, usize> index alongside the ordered Vec (so the displayed order is unchanged) was part of taking that file from 180 ms to 92 ms.

So: a linear scan is fine when both the alphabet and the number of lookups are small. When the lookup count scales with the file, index it, however small the alphabet is. State which case you are in; the choice is not obvious to a later reader.

poka-mtr is the counter-example worth copying. Meter IDs are dense small integers, so the data path indexes a Vec<Option<usize>> directly and does no lookup at all — which is why it streams 31 MB at 144 MB/s with the whole remaining cost in parse::<f64>.

9. Reserve capacity when the size is known

let mut rows = Vec::with_capacity(eso.variables.len().min(MAX_ROWS));

Growth reallocation copies. When the header states a count — and you have validated it against rule 5 — reserve once.

10. Do not build what you are about to throw away

Two habits worth breaking:

• Building a display string for a node you then discard against the node cap. Check the cap first.
• Cloning a field to pass it to a formatter. &str is usually enough; format! borrows fine.

11. Do not copy a name to decide that you do not want it

The most common waste in this codebase, found in three parsers in one pass. The shape is always the same: lift a name out of the input into an owned String, test it against a fixed set, and drop it.

// Once per attribute, on a file with millions of them.
let key = String::from_utf8_lossy(a.key.local_name().as_ref()).into_owned();
if !wanted_attribute(&key) { continue; }

Compare in place and copy only on the way in:

let local = a.key.local_name();
let Ok(name) = std::str::from_utf8(local.as_ref()) else { continue };
let Some(key) = wanted_attribute(name) else { continue };   // -> &'static str

Having the predicate return the matched constant rather than a bool is worth the small awkwardness: the caller stores a &'static str and the copy disappears entirely, not just from the rejected cases.

The same mistake in text parsers is upper- or lower-casing a line to test a prefix:

if t.to_ascii_uppercase().starts_with("INPUT BDL") { ... }   // allocates per line
let b = t.as_bytes();
if b.len() >= 9 && b[..9].eq_ignore_ascii_case(b"INPUT BDL") { ... }

Where a lower-cased copy genuinely is needed — poka-idd matches directives against twenty-odd names — write it into one String the loop reuses and clear()s, rather than allocating a fresh one per line:

fn split_directive<'a>(s: &'a str, name: &mut String) -> &'a str {
    name.clear();
    ...
    name.extend(head.chars().map(|c| c.to_ascii_lowercase()));
    value                                    // a slice of the input
}

Sniffers deserve particular suspicion, because they run before you have even decided you want the file. poka-inp's was copying the first 64 KB character by character and then upper-casing every line of it; slicing the head and comparing in place took it from 0.48 ms to nothing measurable — a quarter of that parser's total cost, spent deciding whether to start.

And a repair pass that usually repairs nothing should return Cow:

pub fn declare_missing_namespaces(text: &str) -> (Cow<'_, str>, Vec<String>) {

Six early returns in poka-xcu each copied the whole document to hand back something identical to the input.

12. Carry scan state across continuation lines

Formats that continue a value onto the next line until something balances — YAML flow sequences, BDL parenthesised lists, IDF fields — invite this:

let mut depth = open_parens(&value);        // rescans the whole value
while depth > 0 {
    value.push_str(next_line);
    depth = open_parens(&value);            // ...and again, and again
}

Reading an N-line value costs O(N²) characters. Keep the scanner instead of the answer:

#[derive(Default, Clone, Copy)]
struct ParenScan { depth: i32, in_quote: bool, in_star: bool }

impl ParenScan {
    fn feed(&mut self, s: &str) { /* ... */ }
    fn open(&self) -> bool { self.depth > 0 }
}

scan.feed(rhs);
while scan.open() && ... {
    value.push_str(piece);
    scan.feed(piece);                       // only the new text
}

The quote flags have to move into the struct too — whether a ( is inside a string depends on every line before it, which is the reason the naive version rescanned in the first place.

This was worth 18× on poka-tbd: one 306 KB Apple .tbd stub went from 80 ms to 4.35 ms, because a wrapped symbols: [ ... ] list is thousands of continuation lines and every one re-read the whole accumulation.

While you are there: most values do not continue. Check first, and parse the single-line case straight out of the source without building the accumulator at all.

13. Transcode through a table, not a search

A single-byte encoding differs from Latin-1 in a handful of positions, which makes a small override list look reasonable:

if let Some((_, c)) = LATIN9_OVERRIDES.iter().find(|(k, _)| *k == b) {
    return *c;
}
b as char

That is a scan of the override list per byte of the file. Build the 256-entry table once and index it. Better still, exploit the fact that these encodings agree with ASCII, which is almost the whole file: copy the runs between high bytes in bulk and map only the high bytes.

let mut out = String::with_capacity(bytes.len() + bytes.len() / 8);
let mut run = 0;
for (i, &b) in bytes.iter().enumerate() {
    if b < 0x80 { continue; }
    out.push_str(std::str::from_utf8(&bytes[run..i]).unwrap_or(""));
    out.push(map[b as usize]);
    run = i + 1;
}

poka-dsbxml decodes ISO-8859-15 on every file, so this ran on every byte of every export; fixing it and the second full copy behind it took the parser from 61 MB/s to 96 MB/s. The identical fix applies to poka-bdl-common's Windows-1252 path, which was 4.5× faster afterwards.

Where the decode is a no-op — the bytes are already valid UTF-8 — return Cow::Borrowed and do not copy at all.

14. Inline the small fixed-size strings

poka-idd stored each field's index token (A1, N12) in a String. The validator already refuses anything longer than five characters, so every one of the 8,225 fields in a single schema took a heap allocation to hold at most five bytes.

#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
pub struct Token { bytes: [u8; MAX_TOKEN], len: u8 }

Worth doing when the format itself bounds the length — and only then; a fixed buffer that can truncate real data is a correctness bug, not an optimisation. Give it Display and PartialEq<&str> so call sites and tests read the same as before.

The related habit: do not build a Vec of records only to move them somewhere else. The same parser collected each line's fields into a temporary Vec<Field>, popped the last one back off, and extended the object with the rest — an allocation and two moves of a 300-byte struct per field, for a list that is usually one element long. split_last() and pushing straight into the destination does the same work with neither.

15. Measure before believing any of this

cargo build -p poka-eso --target wasm32-wasip1 --release

Two numbers to watch:

• Module size. The 26 parsers built so far average ~120 KB. A sudden jump usually means a dependency pulled in formatting or regex machinery.
• Wall clock on the largest real sample. Every parser has a tests/bench.rs that parses the whole corpus in-process and prints BENCH <crate>: X MB in Y ms = Z MB/s plus its three slowest files. Use that, not the wall clock of cargo test — most of what the latter reports is compilation and file I/O. poka-dsbxml looked like a 22-second parser by that measure; the actual parse of all 25 models is 0.6 s.

Three things that measurement kept teaching, all of which cost time to relearn:

Throughput can be a measurement artefact. poka-ctb reads at an apparent 1.6 MB/s, which looks alarming until you notice a .ctb inflates 18.6×: it is doing eighteen times the work its file size suggests. Normalise by the bytes actually processed, not the bytes on disk.

Split the parse into phases before optimising any of it. A twenty-line test that times decode, grammar and render separately is worth more than any amount of reading. For poka-inp the breakdown was decode 0.18 ms, sniffer 0.48 ms, grammar 1.24 ms — nobody would have guessed that the function deciding whether the file was worth reading was a quarter of the cost.

When the phase timings do not explain the total, bisect by stubbing. poka-idd spent 5.79 ms parsing a 260 KB schema and none of the obvious suspects accounted for it. Making field_line return None unconditionally dropped the parse to 1.93 ms, which said two thirds of the work was field construction — and that pointed at the 8,225 fields the file declares. Counting lines would have suggested 1,480; the lines pack several tokens each. Revert the stub immediately; it exists to produce one number.

One calibration figure for this platform, because it decides whether allocation count is worth chasing at all: a String allocate-and-free pair costs ~72 ns here (Windows, release build). Ten thousand of them is 0.7 ms. That is why "one allocation per line" is a real problem on a half-million-line file and irrelevant on a header.

The release profile already sets opt-level = "z", lto = true, codegen-units = 1, strip = true, which trades a little speed for substantially smaller modules. That is the right trade here: instantiation cost scales with module size, and every parser is instantiated per preview.

Checklist

• One pass over the body; fixed-size accumulators
• Dense integer keys indexed by Vec, not HashMap
• Detection and header reads bounded to a prefix
• &str slicing respects char boundaries
• Output capped, truncated set honestly
• Every file-declared length checked before allocating
• Loops over file-derived structure have a visit/depth bound and a forward-progress guard
• Binary formats read &[u8]; text decoded once
• No dependency added for something a table or 40 lines would do
• Linear-scan accumulators only where the alphabet and the lookup count are small, and said which
• Nothing copied out of the input to decide whether it is wanted
• Sniffers and no-op repairs borrow (Cow) rather than copying the file
• Continuation joins carry their scanner state; no rescanning the accumulation
• Single-byte transcoding goes through a 256-entry table, ASCII in bulk
• No panics: no unchecked indexing, no unwrap on file data
• A scaling test exists for every lookup that was made sub-quadratic

Never panic

The host reports a panic as a crash, not a failed parse. That means no unchecked indexing, no unwrap on anything derived from file data, and no &text[..n] without a boundary check. Return a Result with a message that tells the user something:

// Good: names what the file actually is
"not a SANKOM Audytor file — this is a PDF document, saved with a .ekd extension"

// Bad
"parse error"

Where these came from

• This codebase: poka-eso (streaming, dense indexing), poka-dsbxml (collapse-the-bulk, census indexing, table transcoding), poka-ctb / poka-ifczip (inflate caps), poka-isproj (format-direct over a dependency, visit bounds), poka-cat (forward-progress guard), poka-err / poka-blo (transcode tables), poka-tbd and poka-bdl-common (incremental continuation scanning), poka-inp and poka-idd (allocation-free name matching), poka-b18 / poka-osc (dense and lazy indexes), poka-mtr (the dense-integer data path done right).
• DesignBuilderSoftware/db-eplusout-reader: the ESO dictionary/body split, and the observation that the body only needs one value per line.
• idfkit 0.15.0: zero required dependencies, byte-level regex tokenizing, mmap above a threshold, __slots__, ParsingCache per object type, frozenset membership, local rebinding in the hot loop, and bounded version search.

What this was worth, measured

Every figure is the in-process tests/bench.rs number over the real corpus, before and after. Nothing here changed what any parser produces; the test suite (1,055 tests over the fifty formats) passes identically either side.

Eight lookups scaled badly and no longer do:

Not one of them showed up in a corpus benchmark, because no corpus file is large enough. They were found by reading. So: corpus benchmarks find constant factors, reading finds asymptotics. You need both.

Write the scaling test as a ratio, not a wall clock

This is the part worth taking seriously, because the obvious version of the test does not work. The first guards here all looked like this:

let start = Instant::now();
let b = parse(&big_input);
assert!(start.elapsed().as_secs_f64() < 2.0, "quadratic again");

Three of them passed against the very code they were written to catch. The bound has to be loose enough to survive a slow machine and a debug-ish CI box, and by the time it is that loose it will happily accept an order of magnitude of regression. poka-b18's guard ran the old O(S²) lookup in 0.06 s against a 2 s bound.

Time two sizes instead and compare them. The ratio does not care how fast the machine is:

let t_small = time_it(&input(N));
let t_large = time_it(&input(N * 2));
let ratio = t_large / t_small;
assert!(ratio < 3.0, "doubling the input made it {ratio:.1}× slower — \
                      linear is ~2, quadratic ~4");

Rewritten this way, every one of these guards fails on the code it guards, at 4.0–4.8× — and the poka-inp one immediately failed at 4.2× after the defect it was written for had been fixed, which is how children_of was found. A test that cannot fail teaches you nothing; a test that can will find the thing you missed.

Four things it takes to make the ratio meaningful:

• Vary only the dimension that matters. poka-ifczip's histogram is not quadratic in the file size — IFC's type alphabet is fixed, so it was linear with an 800× constant. Doubling the entity count proved nothing. Varying the schema width at a fixed entity count separates them, and shows 14.7×.
• Time the operation, not the setup. Build the inputs first and time only the call under test; a linear parse in the timed region dilutes the ratio towards 2 and hides the defect.
• Measure something a timer can see. poka-b18's first ratio version compared 0.0002 s against 0.0007 s and failed spuriously on a busy machine. Repeat the call until the interval is milliseconds, and take the best of three — a disturbed run is always the slow one.
• Warm up once. The first timed run otherwise pays for page faults and branch-predictor training that the second one gets for free, which biases the ratio downwards.

Revision history