Skip to content

Remove per-token allocation and sorting from strict lookup #171

Description

@alyldas

Context

The strict token lookup currently allocates a fallback array, a Set of seen rule orders, a lookup-character Set, and then sorts candidates for every token. This work is avoidable because compiled patterns and buckets already have stable rule order.

Proposed Implementation

  • Preserve rule order in compilation-time token-index structures.
  • Replace per-token candidate array cloning, de-duplication Set creation, and sorting with an allocation-bounded ordered lookup.
  • Evaluate fallback and indexed buckets without changing first-match precedence.
  • Prefer numeric pattern ids and reusable per-call scratch state, premerged buckets, or another approach with explicit reentrancy and mutation semantics.
  • Keep symbol-token and phrase behavior unchanged unless profiling identifies the same allocation pattern there.
  • Add instrumentation or a focused benchmark that makes per-token allocation visible.

Acceptance Criteria

  • Strict token matching preserves exact rule precedence and taxonomy metadata.
  • Runtime dictionary mutation rebuilds all affected indexes correctly.
  • Reentrant calls and multiple filter instances cannot share stale or mutable scratch state.
  • The common strict-token lookup performs no candidate Array clone, candidate Set construction, or candidate sort per token.
  • Tests cover fallback rules, multiple case variants, split-token lookup characters, duplicate buckets, overlapping rules, and metadata precedence.
  • check(), analyze(), censor(), and scanner paths keep compatible UTF-16 ranges and early-stop behavior.
  • Same-machine benchmarks include long clean text with many unique tokens, repeated-token text, strict early match, strict late match, and filter construction.
  • A unique-token negative control demonstrates that the new structure does not trade allocation reduction for a material lookup regression.

Non-Goals

  • Do not change dictionary order or matching semantics.
  • Do not add cross-message state.
  • Do not combine strict and loose indexes in this issue.
  • Do not weaken boundary or false-positive behavior.

Dependencies

Independent of #169. Coordinate numeric pattern-id representation with #168 when both changes touch compiled matcher metadata.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions