Skip to content

Rust vs C++

What the Rust rewrite kept bit-identical, what it changed on purpose, and what it fixed.

lzcomplexity began as a C++ library with nanobind bindings. That implementation still lives on the main branch and is the origin of most of what is documented on this site — the LZ76 driver, the block-shuffle surrogate machinery, the information distance, the error heuristics and the CLI JSON schema were all designed there first.

This site documents the Rust rewrite on the rust-backend branch, which is the current production backend: it is what pip install lzcomplexity gives you and what cargo add lzcomplexity-core builds against. The rewrite is a port rather than a redesign: the EMC estimator was replaced outright in 0.13.0, but that replacement has since been applied to the C++ backend too, so all five measures are now bit-identical across the two backends. One field still differs on purpose (the Python default log base), and one differs because the C++ had a bug.

289
differential cases matched
188
EMC cases bit-identical
1
intentional divergence
1
C++ bug fixed

The engine room

AspectC++ (main)Rust (rust-backend)
Build systemCMake + nanobindCargo + maturin (PyO3)
Python packagingone wheel per CPython versionone abi3 wheel per platform (abi3-py39), Python 3.9 and later
Suffix arrayCaPS (custom parallel construction)hybrid: comparison sort below 2048 bytes, cdivsufsort above
LCP arraybundled with CaPSKasai's algorithm, O(n)
ParallelismOpenMP, with TBB / Cilk / std::thread fallbacks chosen at configure timerayon, always
Shuffle RNGChaCha8, one instance per block size, seeded from an FNV-1a hash of the input — modules/core/inc/lz/rng.hthe same, bit-for-bit
Shuffle reproducibilityreproducible on any machine, any thread countreproducible on any machine, any thread count
Spectral analysisspectral.psd, spectral.entropy, spectral.semcremoved — moved to a separate package
Python surfacelz76, factorization, factors, entropy_density, emc, plus metrics and spectral submodulesfive top-level functions, no submodules
Python defaultsalphabet=2, log_base=2 (hard-coded literals)alphabet=None, log_base=None — auto-detected from the data
Toolchain to build from sourceC++20 compiler + CMakeRust + a C compiler — cdivsufsort compiles bundled C

Note

The suffix crate is not a dependency of this workspace, despite what the repository README's comparison table still says. Suffix arrays are built by build_suffix_array (crates/lzcomplexity-core/src/suffix_array.rs), which branches on a SORT_CUTOFF of 2048 bytes: below it, a plain sort_unstable_by over suffix slices, which has a much lower fixed cost at that size; at or above it, cdivsufsort — Rust bindings that compile Yuta Mori's bundled C libdivsufsort — which is O(n log n) in the worst case and so does not degrade on repetitive input the way the comparison sort does.

The suffix array of a string is unique, so the two branches cannot disagree. That is asserted, not assumed: suffix_array::tests::fuzz_sa_matches_reference checks build_suffix_array against the comparison sort on 300 random inputs of length 1–5000 over five alphabets (including non-UTF-8 bytes and all-equal bytes), spanning both branches. It passes.

What is bit-identical

Four outputs match the C++ backend exactly. This was established by differential testing: two virtualenvs, one holding the Rust wheel and one the published C++ wheel lzcomplexity==0.10.2, run over a 289-case sweep of random corpora across alphabets and lengths, including binary sequences up to 700 000 symbols. 289 of 289 cases matched.

Measure Rust name Status
Factor count factorization(seq)[0] exact integer match
Factor boundaries factorization(seq)[1] exact, element for element
Entropy density h(seq) exact at equal log base — see the warning below
Information distance nid(a, b) exact

Two details are worth knowing about that agreement.

The factor-count convention was inherited, not re-derived. complexity counts only complete LZ76 components. When the greedy parse runs past the end of the sequence, the trailing partial component is not counted, so the library's count is one less than the textbook exhaustive-history count whenever the sequence ends mid-component. The exact conversion, verified over 500 random strings, is c_textbook = c + (1 if factors[-1] > len(seq) else 0). Both backends do this, and both are short of the textbook count by the same one. See LZ76 factorization.

The C++ information distance has a dead second formula. Its core exposes two overloads: the Python-facing (T1, T2, args) one uses max(C(XY) − C(X), C(YX) − C(Y)) / max(C(X), C(Y)), and a four-argument helper uses min instead. Tracing the call graph showed the min helper is unreachable from every application path — the Python binding, lzcomplexity --dlz and the lzdistance matrices all reach the max form. The Rust port implements only the max form, which is why every distance path agrees. See Information distance.

Version caveat. The 289-case sweep ran Rust 0.11.0 against C++ 0.10.2. Exactly one commit has touched those four code paths since (8f858be): the suffix-array swap described above, which the fuzz test pins to the comparison-sort reference, plus a pass that reuses and parallelizes the factor counts, which only reorders independent integer computations. The sweep has not been re-run against 1.0.

Warning

h on non-binary data halves after migrating unless you pass log_base=2. The C++ Python binding hard-coded log_base=2, so entropy_density returned bits per symbol. The Rust h defaults log_base to the auto-detected alphabet size, so it returns a normalised value instead. On a 58-nt DNA string:

>>> import lzcomplexity as lz
>>> dna = "ACGTACGTTGCAACGTGGATCCGTAAGCTTACGATCGATCGGATCAGCTAGCATCGAT"
>>> lz.h(dna)                # Rust default: base 4, the detected alphabet
0.9089970509680715
>>> lz.h(dna, log_base=2)    # what the C++ binding returned
1.817994101936143

The ratio is exactly log2(k). On binary input the two conventions coincide, which is why the change is easy to miss. See Alphabets and log bases.

What differs on purpose

emc: the two backends now agree bit-for-bit

This section used to say the two emc values were incomparable. That is no longer true. Both backends now run the same estimator over the same surrogates and return identical values — the same value, the same multi_information and the same summands, to the last bit.

Getting there took two changes, because an emc value is a function of both the formula and the surrogates it is computed from.

The estimator. The C++ originally summed absolute complexity differences across block sizes. It moved to the block-entropy ladder in 0.13.0 (Rust) and the matching C++ release, and both now project that ladder onto the non-negative non-decreasing cone excess entropy provably occupies, reading the total and the per-scale terms off the projection.

AspectC++ (0.10.2, the last release before the port)Both backends, current
Per-scale termg · |CLZ(uRS(l)) − CLZ(u)|the increments of the projected ladder Ê(l) = Hl − l·ĥ, with Hl = l · CLZ(uRS(l)) · g
Signnever negative — the term is an absolute valuenever negative — the projection enforces it
Scales reaching the totalall mm of themall mm of them
gloga(N) / N, a = alphabetlogk(N) / N, k = log_base
Shuffle RNGone shared static std::mt19937 seeded from std::random_deviceChaCha8 per block size, seeded from an FNV-1a hash of the input
Reproducible run to runnoyes, on any machine at any thread count

The g row only bites if you pass alphabet and log_base separately; on the defaults both resolve to the detected alphabet size.

The surrogates. The old C++ shuffle drew from a single function-local static std::mt19937 seeded once from std::random_device, shared across calls and mutated from parallel_for workers — so its emc was reproducible neither run to run nor across thread counts, and could not agree with anything. Both backends now hash the sequence bytes with FNV-1a once, mix the hash with the block index using the 64-bit golden-ratio constant, and seed a private ChaCha8 per block size. The C++ implementation lives in modules/core/inc/lz/rng.h and reproduces Rust's generator exactly, down to the rejection zone (range << range.leading_zeros()) − 1 that rand uses for its bounded draws.

Three divergences in the swap kernel itself also had to go, all of which changed which blocks were eligible: the C++ consumed one extra draw before its second-block loop, it rejected the block immediately to the right of the first (op2 == op1 + block_size) where Rust accepts it, and it required op2 < n − block_size − 1 where Rust allows equality. The C++ also gained the two guards it lacked — a zero block size divided by zero, and a degenerate block count looped forever.

Ê(l) = l · g · ( CLZ(uRS(l)) − CLZ(u) ),   g = logk(N) ⁄ N,   Ê = non_negative_isotonic( Ê(1), …, Ê(mm) )(mm)

mm
largest block size; every scale from 1 to mm enters the projection
uRS(l)
the block-shuffled surrogate at scale l — one draw per scale, now from the same stream in both backends
N, k
sequence length and log base

Now shared by both backends. Earlier versions summed the first differences of this ladder, which telescopes to Ê(mm) alone.

Measured parity

188 of 188 differential comparisons of lz76RandomShuffleComplexity between the two backends came back bit-identical in value, multi_information and every summand — across lengths 1 to 20 000, alphabets 2, 4, 5 and 26, and periodic, Thue–Morse, Markov, i.i.d. and constant inputs, at both the auto block size and pinned ones. Worst absolute difference: exactly zero.

Two caveats on that parity

It does not extend backwards. An emc from any earlier release of either backend is not comparable with a current one. Do not mix values across versions in one figure, table or test.

It is not guarded by a test. The C++ repository has no test suite, and the parity rests on the C++ reproducing the internal algorithms of Rust's rand 0.8.6 and rand_chacha 0.3.1. A bump of those dependencies could desynchronise the backends silently. If you rely on cross-backend agreement, verify it on your own data rather than assuming it.

entropy_density is a separate story and still differs between the two command-line tools — that divergence is about which flag feeds the log base, is unrelated to emc, and is described under lzcomplexity.

Spectral analysis, removed

spectral.psd, spectral.entropy and spectral.semc were FFT-based measures bundled into the C++ Python module. They are not LZ76 measures and they pulled a bundled FFT into every build, so the Rust package does not ship them; they moved to a separate package. lzcomplexity has no spectral attribute and no metrics attribute, and the CI wheel smoke test asserts that both stay absent.

What differs as a bug fix

factors_stddev, and therefore normal_error, do not match the C++ backend. This is not a design decision. The C++ FoundStddev built its length vector like this:

std::vector<lz_uint> factors_length(lzf.size());   // lzf.size() ZEROS
for (auto i = 1ul; i < lzf.size(); i++) {
  auto size = lzf[i] - lzf[i - 1];
  factors_length.push_back(size);                  // appended AFTER the zeros
  ...
}

std::vector<T> v(n) value-initialises n zeros; push_back then appends the real factor lengths after them. The sum of squares therefore ran over 2·lzf.size() − 1 elements, of which lzf.size() were spurious zeros each contributing mean². The Rust port iterates only the real lengths.

The relationship between the two values is exact:

σC++ = √( σRust2 + L · μ2 ⁄ ℓmax )

σRust
the shipped factors_stddev
L
number of factor boundaries, len(factors)
μ
(factors[-1] − 1) / L, the mean the code uses
ℓmax
length of the longest factor — the divisor, which is why this quantity is not a standard deviation in either backend

normal_error is exactly proportional to factors_stddev, so it differs by the same ratio.

Example

Take "ABRACADABRA". The Rust library reports:

>>> import lzcomplexity as lz
>>> lz.factorization("ABRACADABRA")
(5, [0, 1, 2, 3, 5, 7, 12])
>>> d = lz.lz76("ABRACADABRA")
>>> d["factors_stddev"], d["normal_error"]
(1.6187674827674623, 0.3320213997117467)

Recomputing by hand from those boundaries: L = 7, μ = (12 − 1)/7 = 1.571428…, factor lengths [1, 1, 1, 2, 2, 5], ℓ_max = 5, Σ(ℓ − μ)² = 13.102040…, so σ_Rust = √(13.102040/5) = 1.6187674827674623 ✓. The C++ formula adds L·μ² = 7 × 2.469387… = 17.285714… to that sum, giving σ_C++ = √(30.387755/5) = 2.4652689549840527. Ratio 1.52.

The ratio is not a constant — it grows with sequence length, because the mean factor length grows like log n while the dispersion around it stays near 2.5. Measured on i.i.d. random binary strings (CPython random.seed(0), re-seeded per row):

ncRust factors_stddevC++ formularatio
100183.06597.70712.51
1 0001076.988124.25903.47
10 00077715.723277.98854.96
100 0006 13835.1241231.88636.60
1 000 00050 78991.6784735.20568.02

Short, structured inputs sit much lower: "aaaa" 1.32×, "01010101" 1.26×, "ABRACADABRA" 1.52×, and the 47-symbol binary sequence used elsewhere in these docs 1.78×. As a rule of thumb, expect a factor of 1.3–1.8 on toy strings and 3–8 on realistic data. The Rust value is always the smaller of the two.

Note

The C++ figures in that table were recomputed by transcribing the C++ expression and evaluating it on the same factor boundaries — they were not produced by executing a C++ build. The Rust column is measured. Read the C++ column as "what the published formula evaluates to", which is the claim being made.

Two further caveats apply to both backends. factors_stddev divides the sum of squares by the longest factor length rather than by the sample size, so it is not a standard deviation in either implementation. And poison_error is a long-standing misspelling of Poisson that the Rust port preserved because the dict key is now API-frozen. Neither error estimate is derived from a published statistical model; do not report them as confidence intervals. See Reading the numbers.

API migration

The Python module keeps the import name lzcomplexity, but little else about the surface survived unchanged. The Rust package exports exactly five functions and no submodules.

C++ (0.10.2)Rust (1.0)What changed
lz.factorization(seq) → intlz.factorization(seq) → (int, list[int])returns the count and the boundaries; take [0] for the old value
lz.factors(seq) → (int, list)lz.factorization(seq)merged into factorization; factors is gone
lz.entropy_density(seq)lz.h(seq)renamed, and the default log base changed
lz.emc(seq) → (max_block_size, emc_value, multi_information)lz.emc(seq) → (value, summands)different tuple and a different estimator; max_block_size and multi_information moved into lz76(seq)["emc"]
lz.lz76(seq) → 4-tuplelz.lz76(seq) → dictkeys: complexity, h, factors, emc, epsilon, factors_stddev, normal_error, poison_error, extras
lz.metrics.information_distance(a, b)lz.nid(a, b)the metrics submodule is gone
lz.metrics.rid(a, b)no equivalentthe binding was already commented out in the C++ source
lz.spectral.psd / .entropy / .semcno equivalentmoved to a separate package
alphabet=2, log_base=2alphabet=None, log_base=Noneauto-detected; alphabet feeds only epsilon, never h
jobs=hardware_concurrency()jobs=0accepted and ignored; set RAYON_NUM_THREADS instead
partitions=1partitions=1signature unchanged, but inert — the Rust core stores the value and never reads it

A minimal migration:

# C++ 0.10.2
import lzcomplexity as lz

c         = lz.factorization(seq)
c, fac    = lz.factors(seq)
hbits     = lz.entropy_density(seq)
mm, e, mi = lz.emc(seq)
d         = lz.metrics.information_distance(a, b)

# Rust 1.0
import lzcomplexity as lz

c, fac      = lz.factorization(seq)
hbits       = lz.h(seq, log_base=2)      # keep the old units explicitly
e, summands = lz.emc(seq)
full        = lz.lz76(seq)
mm, mi      = full["emc"]["max_block_size"], full["emc"]["multi_information"]
d           = lz.nid(a, b)

The right-hand column, run on seq = "01001010101101010101110101010101010000100101011" and the pair a, b = "ABRACADABRA", "ABRACADABRZ":

>>> lz.factorization(seq)
(9, [0, 1, 2, 4, 7, 12, 22, 31, 36, 41, 48])
>>> lz.h(seq, log_base=2)
1.063644673725505
>>> lz.emc(seq)
(0.17727411228758438, [0.05909137076252813, 0.0, 0.11818274152505626, 0.0])
>>> full = lz.lz76(seq)
>>> full["emc"]["max_block_size"], full["emc"]["multi_information"]
(4, 0.11818274152505626)
>>> lz.nid(a, b)
0.3333333333333333

Note

The C++ module docstring showed attribute access — result.complexity — on the value returned by lz76(). That example was already stale in the C++ source: the binding returned a plain tuple, not an object. If you wrote code against that docstring it never worked; if you wrote it against the binding, the Rust dict is a one-line change.

The full Rust surface, with every parameter, is on the Python API page.

Behaviour the port deliberately did not change

Two C++ quirks were reproduced rather than silently corrected:

  • The CLI's -l flag does not affect lz76EntropyDensity. The C++ batch path computed c · log_alphabet(n) / n, in which the log base cancels; the entropy density there is controlled by -a. The Rust CLI copies that formula, and the Rust h() copies the other C++ function — the single-sequence one that reads log_base. Both backends contain the same disagreement between their CLI and their library. See lzcomplexity.
  • The +10 bump on the auto EMC block size, and the n ≤ 10 shuffle floor. Both are inherited verbatim: the bump is applied only when n > 50, and the swap kernel returns without doing anything when n ≤ 10. Because the surrogate is then identical to the input, emc is 0.0 for sequences of ten symbols or fewer in both backends.

Everything else that differs is listed above.