Unicode Normalization Performance: Benchmarks

Unicode normalization is one of those operations that seems straightforward until you need to do it at scale. Normalizing a string to NFC, NFD, NFKC, or NFKD involves decomposition, canonical ordering of combining marks, and optional recomposition — steps that can be surprisingly expensive when applied to millions of strings in a database or high-throughput text processing pipeline. Understanding where the cost comes from and how to minimize it is essential for building performant Unicode-aware systems.

What Makes Normalization Expensive

Normalization cost comes from a few sources:

Decomposition table lookup: Every character must be checked against the Unicode character database to determine if it has a decomposition mapping. This is typically a trie or two-stage table lookup — fast, but not free at high volume.

Canonical combining class sort: After decomposition, any sequence of combining marks (diacritics, vowel signs, etc.) must be sorted by their Canonical_Combining_Class (CCC) property. This is a sort step on what is often a short subsequence, but it involves per-character property lookups.

Recomposition scan (NFC/NFKC only): After decomposition and sorting, the algorithm scans for starter-combining mark pairs that can be recombined into precomposed forms, performing additional table lookups for each potential composition.

The relative cost of the four forms:

NFKC/NFKD are significantly more expensive than NFC/NFD because compatibility decompositions are more extensive — they expand ligatures (fi → fi), superscripts (² → 2), circled numbers (① → 1), and many other compatibility variants. This produces longer strings and more work.

The Quick_Check Optimization

ICU and most production normalization libraries implement the Quick_Check optimization (also called the fast-path check). The Unicode character database assigns each character a NFC_Quick_Check, NFD_Quick_Check, NFKC_Quick_Check, and NFKD_Quick_Check property with values Yes, No, or Maybe.

• Yes: The character cannot prevent a string from being in this normal form.
• No: The character's presence definitively means the string is NOT in this normal form.
• Maybe: The string might or might not be in normal form depending on surrounding characters.

The quick check algorithm scans the string character by character:

1. If any character has Quick_Check = No for the target form, the string is not normalized — normalize it.
2. If any character has Quick_Check = Maybe, further analysis is required (but only from that point onward).
3. If all characters have Quick_Check = Yes, the string is already normalized — return it unchanged.

The key insight is that for typical Latin-script text, the vast majority of characters have Quick_Check = Yes for NFC (since Latin text is typically written in precomposed form). The quick check becomes a fast linear scan that terminates early for already-normalized input, at minimal cost.

For ASCII-only text, normalization is essentially free: all ASCII characters are already in all four normal forms, and the quick check confirms this immediately.

Benchmarks by Text Type

Actual normalization performance depends heavily on the character distribution of the input:

ASCII-only text: Quick_Check passes immediately. Normalization cost is O(n) scan, essentially one branch-predicted comparison per character. At ~1 GB/s scan rates on modern hardware, this is negligible.

Latin with diacritics (NFC input, normalizing to NFC): Most Western European text is written in NFC (precomposed) form. The quick check passes almost entirely. Cost is similarly low — a fast scan confirming everything is already in form.

Latin with diacritics (NFD input, normalizing to NFC): NFD text (decomposed form) requires full recomposition. Cost increases roughly 3–10x compared to already-normalized NFC input, depending on the density of combining marks.

CJK-heavy text: CJK Unified Ideographs (U+4E00–U+9FFF and extensions) have no combining marks and no compatibility decompositions (for NFC/NFD). Their quick check is Yes. CJK text normalizes nearly as fast as ASCII.

Indic scripts (Devanagari, Tamil, etc.): Indic scripts use combining marks extensively (vowel signs, virama). These have CCC values and may require sorting. Normalization of Indic text is meaningfully slower than Latin or CJK, typically 3–8x slower than equivalent ASCII text.

Mixed multilingual text: Performance is roughly proportional to the fraction of characters requiring actual normalization work.

ICU benchmarks (approximate, from ICU performance tests on x86-64): - NFC of already-NFC text: ~500–800 MB/s - NFD of NFC Latin text: ~200–400 MB/s - NFC of NFD Latin text: ~150–300 MB/s - NFKC of mixed text: ~100–200 MB/s

These numbers vary significantly with CPU cache behavior, string length distributions, and input content.

Streaming Normalization

Standard normalization requires the complete string to be available because sorting combining marks and detecting composition opportunities requires lookahead. However, for streaming contexts (network protocols, file parsers), ICU provides incremental normalization through the Normalizer2 interface's normalizeSecondAndAppend pattern, which can process text in chunks by maintaining state at chunk boundaries.

The key insight for streaming: normalization only requires lookahead within a maximal starter segment — a sequence starting at a starter character (CCC = 0) and ending before the next starter. A chunk boundary that falls between starters (or at a starter) can be normalized independently. ICU's streaming mode handles chunk boundaries correctly even when they fall mid-combining-sequence.

When to Normalize: Input Boundary vs Storage vs Comparison

The most important performance decision is when to normalize, not how to do it fast:

Normalize at input boundaries (recommended default): Apply NFC normalization when text enters your system — from user input, from file reads, from API calls. This ensures all text in your system is in a consistent normal form, eliminating the need to normalize repeatedly downstream.

Normalize before storage: Database columns and search indexes should store normalized text. Storing unnormalized text means every comparison query must either normalize at query time or accept false negatives.

Normalize before comparison: If you cannot guarantee input is normalized, normalize before comparing two strings for equality. Two strings that are canonically equivalent but in different normal forms will compare as unequal under byte comparison.

Avoid normalizing at comparison time in hot loops: Normalizing both strings in every comparison call is expensive. Pre-normalize inputs once and cache.

Database Normalization Strategies

For PostgreSQL, MySQL, and SQLite:

PostgreSQL: Column collations control sorting and comparison but not normalization. Use a CHECK constraint or trigger to enforce NFC storage:

-- Enforce NFC on a column (PostgreSQL 13+ has normalize() function)
ALTER TABLE products ADD CONSTRAINT name_is_nfc
    CHECK (name = normalize(name, NFC));

MySQL/MariaDB: The utf8mb4_unicode_ci collation performs Unicode-aware case-insensitive comparison but does not enforce normalization. Normalize in application code before INSERT.

Application-level approach: The most reliable strategy is to normalize in your ORM or model layer before any database write. In Django:

import unicodedata

class YourModel(models.Model):
    name = models.CharField(max_length=200)

    def save(self, *args, **kwargs):
        self.name = unicodedata.normalize("NFC", self.name)
        super().save(*args, **kwargs)

Real-World Performance Tips

1. Profile before optimizing: For most web applications, normalization is not a bottleneck. Measure first.

2. Use ICU or platform APIs, not Python's unicodedata for bulk operations: Python's unicodedata.normalize() is convenient but not the fastest option for bulk processing. ICU4C via PyICU or Rust via the unicode-normalization crate offer better throughput.

3. Batch normalize at system boundaries: One normalization pass over incoming data is far cheaper than repeated per-operation normalization.

4. Choose NFC for storage: NFC is the form used by most systems that produce Unicode text (web browsers, mobile keyboards, macOS). Storing in NFC minimizes the normalization work needed on incoming data.

5. Avoid NFKC in hot paths: Reserve NFKC for specific use cases (identifier normalization, search folding) where its compatibility decompositions are semantically needed. Do not apply it blindly as a "cleanup" step.

6. Use Quick_Check for cheap pre-screening: When you need to normalize lazily, a quick check scan to determine if normalization is needed before doing the full normalization pass can save significant work on already-normalized inputs.

Normalization performance is ultimately about understanding where your text comes from, what form it is likely already in, and applying normalization precisely once at the right boundary — rather than repeatedly throughout your processing pipeline.