Performance

CDTk Performance Architecture

CDTk is engineered for high-speed, hand‑written compiler performance in pure, safe C#. Its architecture centers on deterministic finite automata (DFA) for lexing, table-driven parsing, zero-allocation hot paths, and explicitly validated semantic pipelines. This document details how every stage in CDTk maximizes throughput, and how your language definitions benefit.

---

Design Principles

CDTk’s performance and reliability hinge on these core principles:

• Unified Pipeline: Tokenization, parsing, semantic analysis, and mapping are integrated—no external generators, subprocesses, or tool fragmentation.
• Freeze-Time Construction: Regex compilation, grammar parsing, mapping, and diagnostics all happen once during engine "freeze/build." No dynamic analysis or expensive setup in hot paths.
• Zero Allocations in Hot Loops: Lexing, parsing, and semantic passes are driven by precomputed tables and buffer pools, with zero per-token or per-node allocations.
• Table-Driven, Branch-Predictable Loops: All main driver loops (lexer, parser, semantic visitor) use dense arrays and switch tables for tight, predictable performance.
• Safe Code Only: No unsafe, pointers, stackalloc, or custom memory tricks. CDTk delivers performance via sound design and C#’s managed constructs.

---

High-Performance Lexing (TokenSet & DFA)

CDTk implements a DFA-based lexer derived from your source token definitions (TokenSet):

• DFA Compilation: Regexes and literals defined for tokens are parsed into an AST, built into a non-deterministic finite automaton (NFA) and converted to a deterministic finite automaton (DFA). The DFA is then minimized and encoded as transition tables.
• Character Class Grouping: All chars map to compact integer classes (e.g., digit, letter, whitespace). Transition tables remain small and dense, minimizing cache misses.
• First Match Resolution: Priority is resolved statically—no dynamic lookups or sorting when emitting tokens.
• Ignore Patterns: Dedicated support for ignoring whitespace/comments in the lexing table (see .Ignore() in your token set).
• No Backtracking: All regex patterns used in the DFA lexer are forward-only; non-supported features are flagged at build/validation.

Performance:

• Handles 100–200M chars/sec.
• Each token emitted via preallocated buffer arrays (no per-token heap allocations).

---

Table-Driven Parsing (RuleSet)

Parsing is performed by traversing buffers from the lexer using a table-driven, deterministic parsing engine:

• Precomputed Parsing Tables: All grammar rules (from your RuleSet class) are analyzed, then encoded as parsing tables during freeze/build.
• Arena-Style AST Construction: AST nodes are allocated from pools or buffers, minimizing per-node heap overhead.
• Handles Grammar Complexity: Supports left-recursion, operator precedence, ambiguity resolution, and deeply nested grammars.
• Branch-Free Driver: The parser loop is “read token → consult lookup table → shift/reduce”, with maximally predictable control flow.
• Type-Safe, Declarative Grammar: Your rules are field-defined and validated up front by the diagnostics system.

Performance:

• Builds ASTs at multi-million nodes/sec.
• No dynamic heap churn; buffers are sized/frozen at build.

---

Semantic Engine (MapSet & Scopes)

The semantic engine walks your AST and dispatches mapped handlers:

• Preindexed Semantic Handlers: Each node type and pattern is associated up front (at freeze), yielding O(1) dispatch.
• Pattern-Driven Mapping: MapSets are compiled into lookup and dispatch tables; semantic actions are indexed by node type, not searched at runtime.
• Linear Traversal, No Allocations: Semantic visitor is implemented to make a single pass, filling attribute tables and symbol scopes, all via arrays.
• Preallocated Metadata: Types, symbols, scopes, and annotations are stored in arrays by node/symbol ID for maximum locality.

Performance:

• 15M+ semantic operations/sec in practical workloads.
• Entire semantic pass runs allocation-free unless user handlers allocate.

---

Diagnostics & Validation

CDTk employs rigorous diagnostics at freeze/build time:

• Multi-Stage Diagnostics: Lexical, grammar, and semantic diagnostics are all collected and reported before compilation runs.
• Pattern Risk Analysis: Regex and grammar patterns are analyzed for performance risk (e.g., excessive ambiguity, pathological backtracking).
• Early Error Detection: All errors and warnings are flagged up front, minimizing runtime hazards.

---

Zero-Allocation Hot Paths

All main driver loops (lexer, parser, semantic visitor) use:

• Arrays and IDs, not Object References: Lookups and buffer access are always via dense arrays and integer IDs.
• Freeze-Time Table Construction: All control tables, buffers, regexes, and mappings are built up front.
• Pooling and Buffer Reuse: Temporary state is pooled across runs.
• No Dynamic Reflection or LINQ: The main loop does not branch or allocate for type inspection or object enumeration.

What You Can Control:

• Structure grammar and mapping handlers to avoid allocation.
• Use .Ignore() for tokens you do not need downstream.
• Make judicious use of preallocated data when extending CDTk.

---

Safe Code Only

CDTk guarantees high-speed safely:

• No unsafe, pointers, stackalloc, unmanaged allocators.
• No native interop required ("all managed" pipeline).
• No reflection in hot loop.
• Performance/C# best practices: table-driven, cache-friendly, explicit validation.

---

Performance in Practice

CDTk’s architecture excels in:

• Large scale: Many files, large inputs.
• Complex grammars: Deep nesting, ambiguous patterns.
• Frequent analysis: IDEs, incremental tools, code generation.
• Predictable latency: All flows are deterministic and robust.

How to Benchmark:

• Time lexing, parsing, and semantics separately.
• Use production-size codebases.
• Profile for unintended allocations in mapping handlers.

---

Summary

CDTk achieves:

• DFA lexer: 100–200M char/sec
• Table-driven parser: millions of AST nodes/sec
• Preindexed semantic engine: 15M+ operations/sec
• Zero-allocation hot paths
• Strictly safe-code only design

---

Next Steps

• Learn to use CDTk →