Elixir Pure Rewrite: NIF/GenServer to Pure Elixir #

Sprint L report covering the uncommitted changes in packages/kiri/ and bench/. Date: 2026-02-26

Summary #

The Elixir package has been rewritten from a thin NIF/GenServer wrapper around Rust to a pure Elixir morphological analyzer with a pluggable backend system. The Viterbi lattice solver, double-array trie traversal, dictionary parsing, and all OOV providers now run as ordinary Elixir functions. The Rust NIF is no longer required.

The core concurrency problem — a single GenServer bottleneck feeding a single NIF reference — is eliminated. Kiri.tokenize/3 is now a pure function that any number of BEAM processes can call concurrently with zero coordination.

---

Motivation #

Three problems drove the rewrite:

1. GenServer bottleneck. Every tokenize call serialized through a single GenServer. Concurrent workloads queued behind one process even though the NIF itself held an RwLock. Community feedback (see docs/dev-log/discord.txt) called this out directly: "Why is it constrained to a single GenServer?"

2. Memory explosion at concurrency. Sprints J–K reduced dictionary duplication (Arc-shared bytes + trie), but each tokenizer still needed its own Grammar and LexiconSet parsed from the NIF. At 16 workers, RSS hit 5+ GB.

3. OO-to-FP mismatch. The NIF approach ported Sudachi's mutable Java lattice data structures into Rust, then called them from immutable Elixir through a narrow FFI pipe. Community advice was clear: "The algorithm itself has to be rewritten, going back to the original goal of the algorithm, not the algorithm as written in the other language."

---

Architecture: Before and After #

Aspect	Before (NIF/GenServer)	After (Pure Elixir)
API	create_tokenizer/2 → pid	load_dictionary/2 → %Dictionary{}
Tokenize	GenServer.call(pid, {:tokenize, ...})	Kiri.tokenize(dict, text, opts) (pure function)
Dictionary	NIF mmap + Arc sharing	Pre-converted .kiri format + :persistent_term
Viterbi	Rust NIF via kiri-engine	Fold-based Lattice.build_and_solve/2
Trie	Rust DoubleArrayTrie	Pure Elixir Dictionary.Trie (binary pattern matching)
OOV	Rust MeCab + Simple OOV	Oov.Mecab + Oov.Simple in Elixir
Concurrency	Serialized through GenServer	Unlimited concurrent callers
Memory model	207 MB data + 150 MB trie + per-tokenizer Grammar	~150 MB in :persistent_term, ~2 KB struct per caller
Rust dependency	Required (rustler + kiri-nif + kiri-engine)	Optional (pluggable backend)

---

New Module Map #

Backend system #

• Kiri.Backend — Behavior with single callback tokenize/3. Allows runtime backend selection via :backend option.
• Kiri.Backend.Elixir — Full pure-Elixir tokenization pipeline: input text normalization, lattice construction, Viterbi solve, path rewrite, morpheme building. Includes fallback single-character tokenization when lattice solve fails.
• Kiri.Backend.Nif — Placeholder that raises with a helpful message. The NIF path still exists in Kiri.Tokenizer (GenServer) for backward compatibility but is not the default.

Dictionary system #

• Kiri.Dictionary — Loads a pre-converted .kiri directory into :persistent_term. Returns a lightweight %Dictionary{} struct (~2 KB) with keys into persistent storage.
• Kiri.Dictionary.Converter — Converts Sudachi .dic files to .kiri format. Parses header, grammar, lexicon sections and writes each as a separate binary file. Bundles MeCab config (char.def, unk.def) into meta.etf.
• Kiri.Dictionary.Trie — Pure Elixir DARTSCLONE double-array trie traversal via binary pattern matching. Supports common_prefix_search/4 and exact_match_search/4. Bit-field extraction matches the Rust implementation exactly.
• Kiri.Dictionary.Lexicon — Combines trie + word ID table + word params for dictionary lookup. Supports multi-dictionary stacking with word ID masking.
• Kiri.Dictionary.Grammar — Connection cost matrix via binary offset calculation. Single function: get_connect_cost/4.
• Kiri.Dictionary.WordInfo, WordIdTable, WordParams, SudachiFormat — Low-level binary parsers for each dictionary section.

Lattice and Viterbi #

• Kiri.Lattice — Fold-based Viterbi shortest-path solver. State is an immutable %{byte_pos => [nodes]} map. Folds over byte positions, inserting lexicon matches, MeCab OOV candidates, and simple OOV fallbacks at each word boundary. Connects nodes via dynamic programming, then backtraces the optimal path.
• Kiri.Lattice.Node — Struct with enforced keys for lattice nodes. Includes lazy extra_word_info (populated immediately for OOV, deferred for dictionary words).

OOV providers #

• Kiri.Oov.Mecab — MeCab-style character-category grouping. Generates group nodes (full continuous run) and individual nodes (1..N code points) per matching category.
• Kiri.Oov.Simple — Single-character fallback when no dictionary or MeCab words match.

Input text processing #

• Kiri.InputText — Replaces the old mutable Builder pattern with an immutable struct. to_lattice_input/1 produces packed tuples for O(1) elem/2 access during Viterbi. The old Builder module is reduced to a delegation shim for NIF backward compatibility.

Mix tasks #

• Mix.Tasks.Kiri.Convert — mix kiri.convert system_core.dic output.kiri converts Sudachi dictionaries. Accepts --char-def and --unk-def overrides.

Tests #

• edge_cases_test.exs — Unicode edge cases (emoji, 4-byte CJK, zero-width), split mode verification, concurrent tokenization (8 async workers), dictionary lifecycle (load/unload).

---

Key Design Decisions #

1. Pre-converted .kiri format #

The NIF loaded Sudachi .dic files directly via mmap. In pure Elixir, parsing a 207 MB binary dictionary at startup is expensive. The .kiri format pre-splits the dictionary into separate binary files (trie.bin, connection.bin, word_params.bin, etc.) that can be loaded directly into :persistent_term with zero parsing overhead.

Conversion is a one-time mix kiri.convert step.

2. :persistent_term for zero-copy sharing #

Dictionary binary sections live in :persistent_term, a global store that is not garbage-collected and is accessible from all processes without copying. The %Dictionary{} struct stores only the keys and metadata needed to find the right persistent term entries.

This means 100 concurrent tokenizers share the same ~150 MB of dictionary data with zero additional memory cost per tokenizer.

3. Fold-based Viterbi (no mutable state) #

The Viterbi solver uses Enum.reduce/3 over byte positions. The accumulator is an immutable map of %{end_position => [node_list]}. Each step:

1. Retrieves candidate previous nodes at the current position
2. Inserts new nodes from lexicon lookup, MeCab OOV, and simple OOV
3. Connects each new node to its best predecessor via connection cost lookup
4. Adds connected nodes to the accumulator at their end position

Backtracing follows best_prev_index pointers from EOS to BOS. No mutable arrays, no GenServer state, no NIF calls.

4. Tuple-based hot paths #

InputText.to_lattice_input/1 converts :array structures to tuples before returning. Erlang tuples support O(1) elem/2 reads, which matters in the Viterbi inner loop (called once per byte position per candidate node). The old code used :array.get/2 (O(log N)) or list indexing (O(N)).

5. Binary pattern matching for dictionary access #

All dictionary reads use calculated-offset binary pattern matching:

<<_::binary-size(offset), value::little-signed-integer-size(16), _::binary>> = binary

This avoids allocating intermediate data structures. The BEAM's binary matching is highly optimized for this pattern — it's essentially pointer arithmetic.

6. Pluggable backend #

Kiri.Backend is a behavior. The pure Elixir backend is the default. The NIF backend can be restored by passing backend: :nif to tokenize/3. This keeps the door open for future NIF optimization of specific hot paths (e.g., trie traversal) without changing the public API.

---

Performance Optimizations in Modified Modules #

Several existing modules received targeted optimizations alongside the rewrite:

• CharCategory: Ranges stored as a sorted tuple instead of a list. Lookup uses a recursive scan with early exit (low > cp short-circuits). Was Enum.reduce over unsorted list.

• Normalize: Text string is threaded as a parameter through the rewrite loop instead of being reconstructed via get_text/1 on every character. Eliminates O(n^2) cost. lower_code_point uses binary pattern match (<<cp::utf8>>) instead of charlist round-trip. count_codepoints_fast pattern-matches 1- and 2-codepoint strings directly.

• NumericParser: byte_size/1 replaces String.length/1 for the significand field, which is always ASCII digits. byte_size is O(1); String.length is O(N) for UTF-8.

• PathRewrite: Category arrays converted from :array to tuple for O(1) elem/2. Array sizes threaded as parameters to avoid repeated tuple_size/1 calls. Word info resolution accepts a function or NIF reference (polymorphic dispatch).

• MecabConfig: Eliminated duplicated @category_name_to_bit map. Now delegates to CharCategory.category_name_to_bit/0.

• Persistent term sentinels: CharCategory.default_instance/0 and Normalize.default_instance/0 use :not_loaded atom instead of nil to avoid ambiguity with actual nil values in :persistent_term.get/2.

---

Benchmark Changes #

• bench/tokenize.exs — Updated to load .kiri format dictionaries.
• bench/tokenize_concurrent.exs (new) — Distributes corpus across 128 concurrent workers via Task.async_stream/3. Measures wall-clock throughput for the concurrent pure-Elixir backend.
• bench/run.sh — Elixir benchmarks relabeled from "NIF (Rust)" to "Pure (x128)". Runs the concurrent benchmark instead of single-threaded NIF.
• bench/profile.exs (new) — OTP profiler harness supporting cprof (call counts), eprof (time distribution), and fprof (caller/callee timing). Traces all core modules.
• bench/PROFILING.md (new) — Guide to profiling the pure Elixir tokenizer.

---

Test Changes #

All existing tests updated from GenServer pid (tok) to %Dictionary{} struct (dict):

• kiri_test.exs — setup_all loads dictionary once, shared across all tests
• sudachi_comparison_test.exs — Same fixture-driven comparison, new API
• input_text_test.exs — Builder references replaced with InputText
• edge_cases_test.exs (new) — Unicode edge cases, concurrent tokenization, lifecycle

---

What Remains #

• NIF backend adaptation: Kiri.Backend.Nif is a placeholder. Adapting it to the new %Dictionary{} struct requires updating the NIF to accept persistent_term keys instead of managing its own dictionary lifecycle.
• Profiling and optimization: The pure Elixir Viterbi is expected to be slower than the Rust NIF for single-threaded throughput. The concurrent benchmark (128 workers) is the more meaningful metric for BEAM workloads.
• Precompiled NIF binaries: Still blocked on CI + binary hosting.
• User dictionary support: The .kiri converter handles system dictionaries. User dictionary loading in the pure Elixir path needs implementation.

---

File Inventory (New) #

packages/kiri/lib/
  kiri/backend.ex                    Backend behavior
  kiri/backend/elixir.ex             Pure Elixir tokenization pipeline
  kiri/backend/nif.ex                NIF backend placeholder
  kiri/dictionary.ex                 Dictionary loader (persistent_term)
  kiri/dictionary/converter.ex       .dic → .kiri converter
  kiri/dictionary/grammar.ex         Connection cost matrix
  kiri/dictionary/lexicon.ex         Trie + word ID + params lookup
  kiri/dictionary/sudachi_format.ex  Binary format parser
  kiri/dictionary/trie.ex            DARTSCLONE double-array trie
  kiri/dictionary/word_id_table.ex   Trie value → word ID mapping
  kiri/dictionary/word_info.ex       Word metadata reader
  kiri/dictionary/word_params.ex     Per-word connection parameters
  kiri/input_text.ex                 Immutable input text (replaces Builder)
  kiri/lattice.ex                    Fold-based Viterbi solver
  kiri/lattice/node.ex               Lattice node struct
  kiri/oov/mecab.ex                  MeCab-style OOV provider
  kiri/oov/simple.ex                 Single-character OOV fallback
  lib/mix/tasks/kiri.convert.ex      Mix task for dictionary conversion

packages/kiri/test/
  edge_cases_test.exs                Unicode, concurrency, lifecycle tests

bench/
  tokenize_concurrent.exs            128-worker concurrent benchmark
  profile.exs                        OTP profiler harness (cprof/eprof/fprof)
  PROFILING.md                       Profiling guide