Repository navigation
Improve performance of unicodedata.normalize #150889
Description
Feature or enhancement
Proposal:
The performance of unicodedata.normalize can be improved with a more efficient implementation of find_nfc_index. This was found while reviewing one of the PRs for gh-149079 where O(N²) behaviour in unicodedata.normalize("NFC", ...) was reported. The running time of the find_nfc_index part in normalize is O(N·t) with t the table size. The dependency on t is due to a linear search. t is a constant, so this is O(N), but with a large factor. This is no security issue. Whether relevant for real-world applications I am not sure on.
Several approaches work to improve performance. Some of the rejected ones:
| approach | result | why not |
|---|---|---|
| Lookup table | fastest on all cases (~5× on Greek/Cyrillic) | adds a generated data table (~1.5–3 KB) |
| Galloping (exponential + binary search) | very fast (~3×) | needed extra work (an inlined linear prefix, out-of-line tail) to keep the common low-codepoint cases — ASCII, Latin, Greek — from regressing |
| Affine / piecewise formula (no table) | — | the codepoint→index map is too non-linear (dense clusters + large gaps) to fit (see image below) |
Both the LUT and galloping work well but were rejected: the LUT adds data, and
galloping only stays regression-free with enough added complexity.
In the PR we still have a linear scan, but the per step cost is almost halved.
Benchmarks
unicodedata.normalize(), the f<N> suffix is the nfc_first index the lookups mostly hit):
| case | speedup vs main |
|---|---|
decomposed Greek (f44) |
2.16× |
decomposed Cyrillic (f57) |
2.09× |
Vietnamese double-diacritic (f6/f8) |
2.0× |
combining-mark runs, gh-149079 input (f34) |
1.79× |
Vietnamese double-diacritic (f12) |
1.45× |
decomposed Latin (f3) |
1.32× |
NFKC fullwidth→ASCII (f3) |
1.11× |
| ASCII / already-normalized | unchanged |
Gains grow with how deep the codepoint sits in the table (longer scans benefit
most); ASCII and already-normalized text are unaffected (handled by a fast path).
Benchmark script
import pyperf
import unicodedata
normalize = unicodedata.normalize
nfd = lambda s: normalize("NFD", s)
# gh-149079 attack input: starter + long alternating-CCC combining run (f34)
ISSUE = "a" + (chr(0x0301) + chr(0x0316)) * 50000
# decomposed text by script (low -> deep table positions)
LATIN = nfd("Café déjà vu naïve coördinate Renée " * 80) # f3
GREEK = nfd("ἀνθρώπων μέγιστος ἥρως ὠκεανός φῶς " * 80) # f44
CYRILLIC = nfd("Йёжик в тумане идёт спокойно " * 100) # f57
# once-accented Latin bases + accent -> Ấ/Ế/Ǘ (f6/f8/f12)
IDX6 = (chr(0x00C2) + chr(0x0301)) * 800
IDX8 = (chr(0x00CA) + chr(0x0301)) * 800
IDX12 = (chr(0x00DC) + chr(0x0301)) * 800
# NFKC fullwidth -> ASCII (urllib/idna spoofing-check shape); already-NFC control
FULLWIDTH = "ｇｏｏｇｌｅｄｏｃｓ" * 100
ALREADY = "Café déjà naïve Renée coördinate " * 100
def bench(loops, form, s):
range_it = range(loops)
t0 = pyperf.perf_counter()
for _ in range_it:
normalize(form, s)
return pyperf.perf_counter() - t0
if __name__ == "__main__":
runner = pyperf.Runner()
runner.bench_time_func("nfc_issue_ccc_f34", bench, "NFC", ISSUE)
runner.bench_time_func("nfc_latin_f3", bench, "NFC", LATIN)
runner.bench_time_func("nfc_double_diacritic_f6", bench, "NFC", IDX6)
runner.bench_time_func("nfc_double_diacritic_f8", bench, "NFC", IDX8)
runner.bench_time_func("nfc_double_diacritic_f12", bench, "NFC", IDX12)
runner.bench_time_func("nfc_greek_f44", bench, "NFC", GREEK)
runner.bench_time_func("nfc_cyrillic_f57", bench, "NFC", CYRILLIC)
runner.bench_time_func("nfkc_fullwidth_f3", bench, "NFKC", FULLWIDTH)
runner.bench_time_func("nfc_already", bench, "NFC", ALREADY)Has this already been discussed elsewhere?
No response given
Links to previous discussion of this feature:
No response
Activity
serhiy-storchaka commentedon Jun 4, 2026
Great analysis! The PR is simple and straightforward, it simply moves a rare condition check outside of the loop and simplify the end of the loop condition, so we only have one comparison per iteration instead of three, but one additional comparison after the end of the loop. I have approved it.
But I am interesting in your lookup table idea. What kind of table did you use? We already use a table of size 225*8=1800 bytes for
nfc_first, doubling it's size is not a big deal. I think we can use a kind of precomputed skewed binary tree, so for ASCII, extended Latin, Cyrillic and Greek it will use approximately the same number of iterations, and for other characters at most 10 iterations. And large gaps can be detected quickly.eendebakpt commentedon Jun 4, 2026
The code for the LUT table is here: main...eendebakpt:cpython:gh-149079-find-nfc-index-lut. The galloping approach is main...eendebakpt:gh-149079-find-nfc-index-inlined (it needed some tweaking so the compiler inlined the importants parts).
For the LUT performance I measured this:
Feel free to pick up any of the branches.
gh-150889: Improve performance of unicodedata.normalize() (GH-150890)
serhiy-storchaka commentedon Jun 6, 2026
Let's stick to the simpler option for now.
pythongh-150889: Improve performance of unicodedata.normalize() (pyth…