@dzfrias Great!

Don't worry about the clang format CI errors, we can handle that later.

Sounds good. I will start work on porting UTF-16 functions!

@lemire Finished UTF-16 normalization, which should be ready for review. Looks like we will have to wait until GitHub Actions comes alive again before seeing CI results, though.

Here are the benchmark results:

$ ./build/benchmarks/benchmark --procedure normalize_utf16le_to_nfd --input-file ul/*.utf16.txt
We define the number of bytes to be the number of *input* bytes.
We define a 'char' to be a code point (between 1 and 4 bytes).
Using ICU version 78.3
Using iconv version 267
Compiler: Clang 17.0.0
SIMDUTF version: 9.0.0
System: arm64
===========================
testcases: 9
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 91530, iterations: 30000, dataset: ul/Arabic-Lipsum.utf16.txt
   7.772 ins/byte,    1.053 cycle/byte,    4.367 GB/s (16.3 %),     4.598 GHz,    7.381 ins/cycle
  15.543 ins/char,    2.106 cycle/char,    2.184 Gc/s (16.3 %)     2.00 byte/char  20959.0 ns
normalize_utf16le_to_nfd+icu, input size: 91530, iterations: 30000, dataset: ul/Arabic-Lipsum.utf16.txt
  13.059 ins/byte,    2.337 cycle/byte,    1.960 GB/s (11.6 %),     4.579 GHz,    5.588 ins/cycle
  26.118 ins/char,    4.674 cycle/char,    0.980 Gc/s (11.6 %)     2.00 byte/char  46709.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 46922, iterations: 30000, dataset: ul/Chinese-Lipsum.utf16.txt
   6.711 ins/byte,    0.794 cycle/byte,    6.054 GB/s (11.7 %),     4.807 GHz,    8.452 ins/cycle
  13.422 ins/char,    1.588 cycle/char,    3.027 Gc/s (11.7 %)     2.00 byte/char   7750.0 ns
normalize_utf16le_to_nfd+icu, input size: 46922, iterations: 30000, dataset: ul/Chinese-Lipsum.utf16.txt
  10.612 ins/byte,    1.337 cycle/byte,    3.497 GB/s (11.7 %),     4.676 GHz,    7.936 ins/cycle
  21.224 ins/char,    2.674 cycle/char,    1.749 Gc/s (11.7 %)     2.00 byte/char  13417.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 74612, iterations: 30000, dataset: ul/Hebrew-Lipsum.utf16.txt
   6.609 ins/byte,    0.753 cycle/byte,    6.261 GB/s (17.9 %),     4.712 GHz,    8.781 ins/cycle
  13.219 ins/char,    1.505 cycle/char,    3.130 Gc/s (17.9 %)     2.00 byte/char  11917.0 ns
normalize_utf16le_to_nfd+icu, input size: 74612, iterations: 30000, dataset: ul/Hebrew-Lipsum.utf16.txt
   9.158 ins/byte,    1.619 cycle/byte,    2.816 GB/s (11.0 %),     4.558 GHz,    5.657 ins/cycle
  18.316 ins/char,    3.238 cycle/char,    1.408 Gc/s (11.0 %)     2.00 byte/char  26500.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 65532, iterations: 30000, dataset: ul/Hindi-Lipsum.utf16.txt
   8.013 ins/byte,    0.992 cycle/byte,    4.709 GB/s (15.3 %),     4.672 GHz,    8.077 ins/cycle
  16.026 ins/char,    1.984 cycle/char,    2.355 Gc/s (15.3 %)     2.00 byte/char  13916.0 ns
normalize_utf16le_to_nfd+icu, input size: 65532, iterations: 30000, dataset: ul/Hindi-Lipsum.utf16.txt
  14.728 ins/byte,    2.533 cycle/byte,    1.795 GB/s (12.0 %),     4.548 GHz,    5.814 ins/cycle
  29.456 ins/char,    5.067 cycle/char,    0.898 Gc/s (12.0 %)     2.00 byte/char  36500.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 46750, iterations: 30000, dataset: ul/Japanese-Lipsum.utf16.txt
   8.797 ins/byte,    1.242 cycle/byte,    3.778 GB/s (16.4 %),     4.691 GHz,    7.084 ins/cycle
  17.594 ins/char,    2.484 cycle/char,    1.889 Gc/s (16.4 %)     2.00 byte/char  12375.0 ns
normalize_utf16le_to_nfd+icu, input size: 46750, iterations: 30000, dataset: ul/Japanese-Lipsum.utf16.txt
  17.284 ins/byte,    2.599 cycle/byte,    1.759 GB/s (11.3 %),     4.570 GHz,    6.651 ins/cycle
  34.568 ins/char,    5.198 cycle/char,    0.879 Gc/s (11.3 %)     2.00 byte/char  26583.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 54290, iterations: 30000, dataset: ul/Korean-Lipsum.utf16.txt
  21.716 ins/byte,    4.859 cycle/byte,    0.929 GB/s (13.5 %),     4.512 GHz,    4.470 ins/cycle
  43.432 ins/char,    9.717 cycle/char,    0.464 Gc/s (13.5 %)     2.00 byte/char  58458.0 ns
normalize_utf16le_to_nfd+icu, input size: 54290, iterations: 30000, dataset: ul/Korean-Lipsum.utf16.txt
  72.205 ins/byte,   13.979 cycle/byte,    0.326 GB/s (11.8 %),     4.556 GHz,    5.165 ins/cycle
 144.410 ins/char,   27.958 cycle/char,    0.163 Gc/s (11.8 %)     2.00 byte/char 166583.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 173882, iterations: 30000, dataset: ul/Latin-Lipsum.utf16.txt
   0.668 ins/byte,    0.201 cycle/byte,   24.265 GB/s (27.7 %),     4.881 GHz,    3.323 ins/cycle
   1.337 ins/char,    0.402 cycle/char,   12.132 Gc/s (27.7 %)     2.00 byte/char   7166.0 ns
normalize_utf16le_to_nfd+icu, input size: 173882, iterations: 30000, dataset: ul/Latin-Lipsum.utf16.txt
   3.963 ins/byte,    1.131 cycle/byte,    4.009 GB/s (4.7 %),     4.534 GHz,    3.504 ins/cycle
   7.926 ins/char,    2.262 cycle/char,    2.004 Gc/s (4.7 %)     2.00 byte/char  43375.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 115962, iterations: 30000, dataset: ul/Russian-Lipsum.utf16.txt
   6.548 ins/byte,    0.729 cycle/byte,    5.738 GB/s (6.1 %),     4.184 GHz,    8.980 ins/cycle
  13.097 ins/char,    1.458 cycle/char,    2.869 Gc/s (6.1 %)     2.00 byte/char  20208.0 ns
normalize_utf16le_to_nfd+icu, input size: 115962, iterations: 30000, dataset: ul/Russian-Lipsum.utf16.txt
   9.251 ins/byte,    1.712 cycle/byte,    2.648 GB/s (13.5 %),     4.533 GHz,    5.404 ins/cycle
  18.502 ins/char,    3.424 cycle/char,    1.324 Gc/s (13.5 %)     2.00 byte/char  43791.0 ns
input detected as UTF16 little-endian
===========================
normalize_utf16le_to_nfd+arm64, input size: 147724, iterations: 30000, dataset: ul/Spanish-Lipsum.utf16.txt
   2.145 ins/byte,    0.355 cycle/byte,   13.229 GB/s (13.2 %),     4.701 GHz,    6.036 ins/cycle
   4.290 ins/char,    0.711 cycle/char,    6.614 Gc/s (13.2 %)     2.00 byte/char  11167.0 ns
normalize_utf16le_to_nfd+icu, input size: 147724, iterations: 30000, dataset: ul/Spanish-Lipsum.utf16.txt
   5.911 ins/byte,    1.660 cycle/byte,    2.721 GB/s (7.8 %),     4.516 GHz,    3.562 ins/cycle
  11.823 ins/char,    3.319 cycle/char,    1.360 Gc/s (7.8 %)     2.00 byte/char  54292.0 ns

NFKD, NFC, and NFKC results are similar or better.

Main points of consideration with this implementation:

• It has many of the same issues that I mentioned above as UTF-8 normalization does (falls back to scalar on supplementary, supplementary is slow, and canonical recomposition is slow)
• Scalar UTF-16 composition is a big weak spot. On my benchmarks, it is faster than ICU on all inputs except for Latin, in which case it is slower. It would be nice if scalar UTF-16 composition was faster than ICU in all cases.
• I didn't optimize these functions as heavily as I did with UTF-8. I left comments in the places where I thought the implementations could be faster.

Also, in this batch of commits, I changed the UTF-8 code point index table, which resulted in a significant speed up for decomposing Spanish. This came with no changes to the other algorithms relying on this table, though (it reordered the table, but kept the existing class index boundaries the same, so the idx < 64 etc. stuff didn't change).

Lastly, I'm happy to provide more details about the implementation if there are any questions! I was also curious if there is interest in a UTF-32 implementation. I don't really see UTF-32 strings being normalized anywhere in the wild, but I could write an implementation for it. It would be almost identical to the UTF-16 implementation, but probably a bit slower.

Tests should run in CI.

I will have to review all of this carefully, and possibly do some tuning, but it is a great start.

@dzfrias I have a few PRs that I submitted to your branch.

One source of concern is that these features will need to be disabled by default because they would, otherwise, significantly increase the binary size for everyone. That is fine because our library is designed for selective features.

Added benchmarks for the check functions, since they're an important part of the API. They are currently a little bit slower than their writing counterparts on a number of non-ASCII inputs, which I think should be investigated either in this PR or later.

We definitely cannot be broadly slower than UCI. At least, I would not want to release such code in simdutf. So we need to do significant more work on the performance, and, possibly, on the interface. We should at least be faster on one platform such as arm64.

Canonical composition is 2x to 3.5x slower than ICU on arm64 even with the NEON kernels active. Composing decomposed Hangul runs at 0.28x of ICU on the M-series.

Apple M-series (arm64, the branch's vectorized target), ICU 78.3, clang

These numbers drive ICU the way V8 does — quick-check, then normalize only the tail. The built-in benchmark below drives ICU unconditionally, so its ICU column runs slower and simdutf's ratios come out better than shown here; the losses are real either way.

-F is read as raw UTF-16LE — the normalize procedures reinterpret the file
bytes as char16_t (input_data.size() / 2 units), with no transcoding — so the
corpus must be UTF-16LE, not UTF-8. This Python snippet builds a composition-heavy
one with no downloads: it takes multilingual text, NFD-decomposes it so NF(K)C has
real work to do rather than settling on the quick check, and writes UTF-16LE:

python3 - <<'PY'
import unicodedata
samples = [
    "Le vieux château français était déjà là. ",  # accented Latin
    "Ἀλλὰ καὶ ὁ λόγος ",                            # Greek
    "동해물과 백두산이 ",                            # Korean (composes)
    "日本語のテキスト。ガギグ ",                      # Japanese
]
text = unicodedata.normalize("NFD", "".join(samples) * 4000)
open("corpus.utf16le", "wb").write(text.encode("utf-16-le"))
PY

git clone https://github.com/dzfrias/simdutf.git && cd simdutf
git checkout normalization
cmake -B build -DCMAKE_BUILD_TYPE=Release \
      -DSIMDUTF_NORMALIZATION=ON -DSIMDUTF_BENCHMARKS=ON
cmake --build build -j

# -P is a substring match, so each name below selects both the simdutf and the
# +icu procedure. -F takes a dataset; --show-procedures lists everything.
./build/benchmarks/benchmark -F corpus.utf16le \
  -P normalize_utf16le_to_nfc  -P normalize_utf16le_to_nfd \
  -P normalize_utf16le_to_nfkc -P normalize_utf16le_to_nfkd

@lemire Thanks for bringing up these benchmarks. I was surprised at a few of the numbers (particularly the NFD ones), but turns I forgot to update the UTF-16 NFD check functions to route to the arm64 implementation (they were still using scalar)! The other numbers, related to recomposition-heavy workloads, were expected. I haven't spent much time looking at profiles for recomposition-heavy workloads because they appeared in none of the corpus inputs I was working with, but it is a point of interest so I will work on optimizing it. Should be many easy optimizations to apply there to get on par with ICU.

You mentioned interface changes. ICU has a pattern of quick check and return the position of the code point failing the quick check (so everything before that code point can be memcpy'd), as opposed to simdutf which returns a boolean. I did not opt to copy the ICU design and I would have to do a thorough investigation to see how much it would help in real-world inputs. I'm not convinced that such an interface would result in substantial performance gains broadly. Perhaps in inputs with very sparse unstable code points across chunks. In any case, I do not believe not it was a big difference maker between ICU and simdutf in the NFD numbers you reported. The reason simdutf was slower is simply because I forgot to route the check implementation to the vectorized implementation.

@dzfrias It might be. Ultimately it is an empirical matter: what happens when we replace UCI by simdutf in V8 normalization functions. It is either a performance boost or not.

That is true. I will do some experimentation with a different check interface after speeding up recomposition. I think UTF-16 NFD should be much faster than ICU as of the latest commit I just pushed regardless of which check interface we decide on. Now starting work on recomposition optimization.

@dzfrias

For reference. I bench String.prototype.normalize('NFC') in Node.js.

  git clone git@github.com:lemire/node.git && cd node
  git checkout simdutf-normalize
  ./configure --ninja && ninja -C out/Release -j 14      # ~35 min from cold

  git clone --depth 1 https://github.com/lemire/unicode_lipsum.git /tmp/ul

Then fetch the benchmark script:

  # simdutf (default)
  NORMBENCH_JSON=/tmp/sd.json ./out/Release/node normbench.js /tmp/ul/lipsum NFC
  # ICU, same binary
  NORMBENCH_JSON=/tmp/icu.json ./out/Release/node --no-simdutf-normalize normbench.js /tmp/ul/lipsum NFC

The perf IS better with Latin (English/ASCII) but 4x regression in the Korean case is not great.

Here is the normbench.js my AI wrote:

'use strict';
// Benchmarks String.prototype.normalize over the unicode_lipsum corpus.
// Usage: node normbench.js <lipsum-dir> [form ...]
const fs = require('fs');
const path = require('path');

const dir = process.argv[2];
const forms = process.argv.length > 3 ? process.argv.slice(3)
                                      : ['NFC', 'NFD', 'NFKC', 'NFKD'];
const files = fs.readdirSync(dir).filter((f) => f.endsWith('.utf8.txt')).sort();

function bench(str, form) {
  // Warm up and let the call site settle.
  let sink = 0;
  for (let i = 0; i < 50; i++) sink += str.normalize(form).length;

  // Pick an iteration count that keeps each timed run around 100 ms.
  const probe = process.hrtime.bigint();
  for (let i = 0; i < 20; i++) sink += str.normalize(form).length;
  const perIter = Number(process.hrtime.bigint() - probe) / 20;
  const iters = Math.max(10, Math.min(20000, Math.round(1e8 / perIter)));

  let best = Infinity;
  for (let round = 0; round < 5; round++) {
    const start = process.hrtime.bigint();
    for (let i = 0; i < iters; i++) sink += str.normalize(form).length;
    const ns = Number(process.hrtime.bigint() - start) / iters;
    if (ns < best) best = ns;
  }
  if (sink === -1) console.log('unreachable');
  return best;
}

const results = [];
for (const file of files) {
  const raw = fs.readFileSync(path.join(dir, file), 'utf8');
  // Force a flat string.
  const str = raw.slice(0);
  const bytes = str.length * 2; // UTF-16 code units
  for (const form of forms) {
    // Same-form input: the common case, where the string is already normalized.
    const same = str.normalize(form);
    const nsSame = bench(same, form);
    // Cross-form input: NFD input normalized to NFC and vice versa, so real
    // work has to happen.
    const other = form === 'NFC' || form === 'NFKC' ?
      str.normalize('NFD') : str.normalize('NFC');
    const nsWork = bench(other, form);
    results.push({
      file: file.replace('.utf8.txt', ''),
      form,
      units: str.length,
      alreadyNs: nsSame,
      alreadyGBs: (same.length * 2) / nsSame,
      workNs: nsWork,
      workGBs: (other.length * 2) / nsWork,
    });
  }
}

const pad = (s, n) => String(s).padEnd(n);
const padS = (s, n) => String(s).padStart(n);
console.log(`node ${process.version}  v8 ${process.versions.v8}`);
console.log(`${pad('dataset', 18)}${pad('form', 6)}${padS('units', 8)}` +
            `${padS('already ns', 12)}${padS('GB/s', 9)}` +
            `${padS('work ns', 12)}${padS('GB/s', 9)}`);
for (const r of results) {
  console.log(`${pad(r.file, 18)}${pad(r.form, 6)}${padS(r.units, 8)}` +
              `${padS(r.alreadyNs.toFixed(0), 12)}${padS(r.alreadyGBs.toFixed(2), 9)}` +
              `${padS(r.workNs.toFixed(0), 12)}${padS(r.workGBs.toFixed(2), 9)}`);
}
fs.writeFileSync(process.env.NORMBENCH_JSON || '/dev/null',
                 JSON.stringify(results, null, 1));

(Not reviewed by me.)

Ultimately, I will review the benchmarks manually. For now, I would just want to see positive benchmarks on arm64 over a wide range of inputs.

Afterward, we can get fancier.

Moving to x64 and others should not be too hard if we get arm64 working well.

Thank you, this is extremely helpful. I will use these benchmarks as I work to speed up composition.

@lemire Made a substantial amount of optimizations:

• Performing composition is now much faster than before. It is now on par with ICU in the node normbench.js script you gave me, and sometimes faster (it is now faster for Korean). It seems not very worthwhile to try to vectorize the procedure of composition, so I thought on par with ICU (which is itself well optimized) in recomposition heavy workloads is fine. If we want to be substantially faster, we should try to optimize the scalar path.
• I fixed the supplementary code point problem with a multi-stage trie. Supplementary code point benchmarks like Emoji are almost as good as ICU, but the parsing latency in the vectorized path is causing us to be a little bit slower. I will try to work on this when I can.
• Performance on Hindi-Lipsum is not perfect yet. I have some ideas for speeding this one up, though.
• The data tables are now around 70kb smaller than before by virtue of sharing tables between NFD and NF(K)D. The only slowdown induced here could be in cache performance.

I was somewhat avant-garde with these changes and I think they should be fuzzed pretty thoroughly. Especially the new composition algorithm. Composition is a pretty complex procedure and the Unicode Character Database leaves no room for untouched edge cases...

These changes were LLM assisted. Particularly for generating boilerplate code, making propagating breaking changes I made across multiple files (such as when I changed the trie value format), copying some elements of ICU's fast scalar composition algorithm into simdutf, and generating test code. All changes were reviewed by me.

Thanks.

Will review.

I sped up Hindi-Lipsum a little bit. But I also noticed that its NFKC performance is much worse than its NFC performance even though the input has no compatibility decompositions. I need to do a thorough investigation to see why this is happening. Same instructions per byte.

Found a fix for the NFKC on Hindi but it really isn't pretty. I at first thought it was memory cache performance, but reading the profile on macOS instruments showed that it is related to the instruction cache and instruction alignment. I was able to fix the performance difference by manually aligning certain instructions that had different alignments between NFC and NFKC, but this is obviously extremely suboptimal from a code perspective as it is a compiler and CPU-specific detail. I'll try to fix this by speeding up the algorithm in some way as opposed to fixing the machine code manually...

Made some small optimizations that fixed performance for Hindi under NFC and NFKC

As of the latest commit, simdutf is better than ICU (on Apple M-series) for all inputs tested by normbench.js across NFC, NFKC, NFD, and NFKD, both when there is work and when there is not

@dzfrias Thanks. I will review.

(This is complex code so be patient.)