Performance

CDTk Performance Architecture

CDTk is engineered to deliver hand‑written compiler performance using only safe C#. This page dives into how CDTk achieves high throughput across lexing, parsing, and semantic analysis, and how you can keep your own language definitions running at full speed.

---

Design principles

CDTk’s performance comes from a few non‑negotiable principles:

• Single, unified pipeline
  No separate tools, no external generators. The entire compilation pipeline lives in one coherent, tightly‑coupled engine.

• Freeze‑based architecture
  All expensive setup (regex compilation, grammar analysis, mapping tables) happens once at build/freeze time — never in hot paths.

• Zero allocations in hot loops
  Lexing, parsing, and semantic dispatch are implemented to avoid per‑token, per‑node, or per‑visit allocations.

• Branch‑predictable, table‑driven inner loops
  Tight loops with predictable control flow, driven by precomputed tables instead of dynamic branching.

• Safe code only
  No unsafe, no pointers, no stackalloc, no custom unmanaged allocators. All gains come from architecture and data layout.

---

High-performance lexing (TokenSet)

CDTk’s lexer is a DFA‑based engine built from your TokenSet. The goal is simple: scan characters at tens or hundreds of millions per second, deterministically.

Core techniques

• Deterministic Finite Automaton (DFA)
  Regexes and literal tokens are normalized into a compact DFA representation. This DFA is encoded into arrays (transition tables) indexed by current state and input character class.

• No backtracking
  CDTk does not use backtracking regex engines in the hot path. Everything is forward‑only, with a single active state at a time.

• Character class grouping
  Input characters are mapped to small integer classes (e.g., digit, letter, underscore, other) to keep transition tables dense and branch‑predictable.

• First‑match wins
  Token priority is resolved by construction, not by dynamic sorting. The lexer knows exactly which token type to emit when a state is accepting.

Performance characteristics

• 50–200M characters/sec, depending on input shape and pattern complexity.
• Inner loop is a small, predictable state machine: load char → compute class → lookup next state → repeat.
• Token emission uses preallocated arrays or segmented buffers, avoiding per‑token allocations.

How to keep lexing fast

• Prefer simple, linear regexes aligned with DFA construction.
• Avoid pathological patterns that require many character classes for no real gain.
• Use .Ignore() for whitespace/comments so you don’t do extra work in later stages.

---

Table-driven parsing (RuleSet)

CDTk’s parser builds a typed AST using a table‑driven engine constructed from your RuleSet. It’s designed to support complex grammars without sacrificing speed.

Core techniques

• Precomputed parsing tables
  At build/freeze time, CDTk analyzes your rules and produces tables that encode parsing decisions, rule expansions, and reductions.

• Arena‑allocated AST construction
  AST nodes are allocated via an arena (or equivalent pattern), keeping allocations linear and locality high. No per‑node heap overhead in hot paths.

• Grammar flexibility without generator overhead
  The same engine can handle left recursion, ambiguity, operator precedence, and nested constructs, all driven by your RuleSet.

• Tight, loop‑friendly driver
  The parser’s main loop is a simple “read token → consult table → shift/reduce” pattern, with minimal branching.

Performance characteristics

• Multi‑million nodes/sec AST construction.
• Minimal heap churn thanks to arena‑style patterns and pre‑resized buffers.
• No reflection, no dynamic type inspection in the hot path — node types are known at build time.

How to keep parsing fast

• Structure rules to avoid unnecessary ambiguity that forces more complex table decisions.
• Factor out common patterns into reusable rules instead of duplicating complex structures.
• Avoid giant “catch‑all” rules that match everything; they increase decision surface.

---

Semantic engine (MapSet + scopes)

After parsing, CDTk’s semantic engine walks the AST and dispatches to your mappings. This is where symbol resolution, type propagation, and validation live.

Core techniques

• Pre‑indexed handlers
  Instead of searching for matching handlers at runtime, CDTk assigns handlers to node types and patterns at freeze time. Semantic dispatch becomes simple index lookups.

• Pattern‑driven mapping
  MapSet uses pattern definitions that are compiled into efficient lookup structures. At runtime, deciding “what handler to run for this node” is O(1) or close.

• Linear, cache‑friendly traversal
  AST traversal is implemented as a predictable loop/recursion pattern with minimal branching and no per‑visit allocations.

• Metadata tables
  Semantic metadata (types, symbols, scopes, etc.) is stored in arrays or tables indexed by node or symbol ID, not in scattered dictionaries.

Performance characteristics

• 14M+ operations/sec under realistic semantic workloads.
• Core loop: fetch node → resolve handler index → invoke → write results to preallocated metadata tables.
• No allocations during the main semantic pass, assuming your own handlers avoid allocation.

---

Zero-allocation hot paths

CDTk’s pipeline is built to run without heap allocations in the hot loops of lexing, parsing, and semantics.

Techniques used

• Freeze-time construction
  All complex objects (regexes, DFAs, parse tables, mapping tables) are built once. Freeze turns definition time into a one‑time cost.

• Array‑based storage
  Internal structures use arrays (T[]) and integer indices. Lookups are O(1) and CPU‑cache‑friendly.

• Index‑based references
  Instead of references to arbitrary objects, nodes and symbols are often referenced by integer IDs, which map into arrays of metadata.

• Pooling and reuse
  Where intermediate buffers are needed, they are pooled or reused across compilations, rather than reallocated.

What you control

CDTk keeps its own internal loops clean; you can help by:

• Reusing data structures across compilations where appropriate.
• Avoiding heavy LINQ or allocations in your mappings and semantic logic.
• Using simple fields and IDs instead of deep object graphs in your own metadata.

---

Safe code only

A key point: CDTk’s performance does not rely on unsafe tricks.

• No unsafe blocks
• No raw pointers
• No manual memory management
• No stackalloc‑heavy codepaths
• No P/Invoke to custom native code

Instead, it leverages:

• Compile‑time analysis (freeze)
• Table‑driven design
• Careful data layout
• Highly predictable control flow

This makes CDTk suitable for environments where safety, maintainability, and debuggability matter just as much as speed.

---

Performance in practice

When CDTk shines

CDTk’s architecture is especially effective when:

• You have large inputs or many files.
• You need to run semantic analysis repeatedly (e.g., IDEs, incremental tools).
• Your language has complex grammar and rich semantics that would be expensive in naïve implementations.

How to benchmark your own compiler

To understand your own performance:

1. Measure each stage separately
   • Time lexing, parsing, and semantics individually.
2. Test with realistic inputs
   • Small samples hide cost; large codebases reveal patterns.
3. Inspect allocations
   • Use a profiler to ensure your handlers don’t introduce per‑node or per‑token allocations.
4. Adjust definitions, not the framework
   • Tuning your grammar and mappings is usually enough to unlock CDTk’s full speed.

---

Summary

CDTk’s performance story rests on:

• A DFA‑based lexer capable of 50–200M chars/sec.
• A table‑driven parser with arena‑style AST construction.
• A preindexed semantic engine reaching 14M+ ops/sec.
• A freeze‑based, zero‑allocation architecture in hot paths.
• A strict safe‑code‑only implementation philosophy.

The result is a compiler toolkit that feels high‑level and declarative but behaves, under load, like a meticulously hand‑tuned engine.

Next Steps

• Learn: Learn to use CDTk.