Potential perf win: Pre-allocate `ATNConfigSet` collections

[jonhoo]

As discussed on Bluesky, here's one of the LLM-generated performance improvement suggestions from profiling https://github.com/jonhoo/avdl on (synthetic) bigger .avdl files with the ANTLR-generated parser. I'd be happy to test out changes if you don't have a benchmark handy!

Symptom

Hash map operations in ATNConfigSet show significant self-time: ATNConfigSet::local_hash_key at 2.1% (81/3785 samples), ATNConfigSet::add_cached at 1.3% (49 samples), hashbrown::...::HashMap::insert at 2.3% (86 samples), and hashbrown::...::RawTable::reserve_rehash at 1.0% (37 samples). Together these account for ~6.7% of total self-time, a portion of which is caused by repeated reallocation of zero-initialized collections as configs are added one at a time.

Root cause

ATNConfigSet::new_base_atnconfig_set (atn_config_set.rs:95) creates configs: vec![] and config_lookup: HashMap::with_hasher(...) — both with zero capacity. During LL(*) prediction, configs are added one at a time via add_cached, triggering:

• Vec reallocation: Vec::new() starts at capacity 0. The growth pattern (0 → 4 → 8 → 16 → ...) means the first ~4 configs cause 2 reallocations.
• HashMap rehashing: HashMap::with_hasher(...) starts at capacity 0. Each growth step rehashes all existing entries. With the default load factor of 87.5%, a set of 10 configs triggers ~2 rehashes.

New ATNConfigSets are created frequently in the hot path: compute_reach_set (line 549, 580), compute_start_state (line 687), remove_all_configs_not_in_rule_stop_state (line 655), split_according_to_semantic_validity (lines 870–871), and compute_reach_set in lexer_atn_simulator.rs (line 286).

A typical parser decision point processes 5–20 configs per set.

Affected files

• runtime/Rust/src/atn_config_set.rs:95–108 — constructor new_base_atnconfig_set, and new_ordered (line 111)
• runtime/Rust/src/parser_atn_simulator.rs — call sites at lines 549, 580, 655, 687, 722, 870, 871
• runtime/Rust/src/lexer_atn_simulator.rs — call sites at lines 286, 421

Suggested fix

1. Add a with_capacity(n: usize) constructor to ATNConfigSet:

   pub fn with_capacity(full_ctx: bool, capacity: usize) -> ATNConfigSet {
       ATNConfigSet {
           cached_hash: 0,
           config_lookup: HashMap::with_capacity_and_hasher(
               capacity,
               MurmurHasherBuilder {},
           ),
           configs: Vec::with_capacity(capacity),
           conflicting_alts: Default::default(),
           dips_into_outer_context: false,
           full_ctx,
           has_semantic_context: false,
           read_only: false,
           unique_alt: 0,
           hasher: Self::local_hash_key,
       }
   }

2. Replace ATNConfigSet::new_base_atnconfig_set(full_ctx) with ATNConfigSet::with_capacity(full_ctx, 16) at the hot-path call sites in parser_atn_simulator.rs. A capacity of 16 covers the vast majority of decision points (5–20 configs) without waste.

3. Similarly update new_ordered() (used in lexer_atn_simulator.rs) to pre-allocate.

This change is purely additive — the existing zero-capacity constructor remains available for cold paths or cases where the expected size is unknown.

[rrevenantt]

ATN and DFA are lazily created only once, all subsequent parsing happens on cached DFA in a tight loop. So this optimization will affect code path that will be entered only fixed amount of times for whole program execution regardless of how much files do you parse. I don't mind this change, but i don't see much point in it either.

[jonhoo]

In my particular case, I have a binary that you'll generally only pass a handful of files to at a time, and then the program will exit, and then the construction time ends up being a decent chunk of the overall execution time.

[tinovyatkin]

@jonhoo the short-lived-CLI angle resonates — that first-parse cost is exactly what I've been tuning for in antlr-rust-runtime. Full disclosure: we don't pre-size the config collections either. What moved the needle more was getting construction out of the hot path entirely — the lexer DFA is compiled at generation time (zero tokenizer warmup), and learned parser decision DFAs are shared across parser instances, so ATN simulation isn't re-paid per process. For a "parse a few files then exit" tool that's where a lot of the cold-start cost lives. Might be an interesting comparison point for your avdl profiling.