Skip to content

Optimize Viterbi cost calculation by batching word processing#598

Merged
mosuka merged 1 commit intomainfrom
viterbi
Jan 9, 2026
Merged

Optimize Viterbi cost calculation by batching word processing#598
mosuka merged 1 commit intomainfrom
viterbi

Conversation

@mosuka
Copy link
Copy Markdown
Member

@mosuka mosuka commented Jan 9, 2026

Optimize Viterbi cost calculation by batching word processing

  • Introduced a batch processing approach in the Viterbi algorithm to improve performance and cache locality.
  • Added buffers to the Lattice struct to store word entries and preceding state costs in a Struct-of-Arrays (SoA) format during processing.
  • Implemented add_edges_in_lattice_batched to process multiple candidate words starting at the same position in a single pass over preceding edges.
  • Optimized the Mode::Normal path by inlining cost calculations and skipping penalty overhead.
  • Reduced memory allocation and pointer chasing by reusing internal buffers within the Lattice structure.
  • Achieved significant performance improvements across various scenarios:
    • Up to 37% speedup when using user dictionaries.
    • 13% speedup for long text tokenization with detailed output.
    • 7-9% improvement in standard tokenization scenarios.

@mosuka mosuka merged commit 75e0b2a into main Jan 9, 2026
8 checks passed
@mosuka mosuka deleted the viterbi branch January 9, 2026 12:51
mosuka added a commit that referenced this pull request Jan 10, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant