WASM: remove @njit(parallel=True) from gini_coefficient via an O(n log n) rewrite

[mmcky]

Note

Updated 2026-08-21. When this was written, @njit(parallel=True) failed at first call in the browser; since 2026-08-18 the emscripten-forge Numba build carries patch 0010 (emscripten-forge/recipes#6293), which compiles it on the serial pipeline, so gini_coefficient no longer crashes in JupyterLite but runs the serial O(n²) loop. The rewrite remains the intended change, now for performance and for independence from a downstream patch that upstream describes as temporary; PR #937 is approved and awaiting merge, the platform-gate PR #935 is closed, and acceptance criterion 4 now points at #928 without blocking closure. The original text is preserved in the edit history.

Part of #925 (Phase 1). The browser-compliance audit identified this as a hard blocker; it is now a performance problem (see Problem below), and the campaign's open blockers are tracked in #927 (jitted generators) and #944 (cache=True chains, upstream emscripten-forge/recipes#6309).

Status. Implemented in PR #937 (approved by @kp992 2026-08-14, CI green, awaiting merge), which satisfies criteria 1–3 and will close this issue automatically on merge. It supersedes the platform-gate approach in #935, closed 2026-08-14 after the rewrite was adopted.

Problem

gini_coefficient is the library's only use of Numba's ParallelAccelerator pass:

@njit(parallel=True)
def gini_coefficient(y):
    ...
    for i in prange(n):

The in-browser Numba runtime (emscripten-forge) is single-threaded: OpenMP and TBB are disabled at build time. Until 2026-08-18 its only serial fallback was patch 0007, which covers the parallel ufunc target (guvectorize(..., target='parallel')) and not @njit(parallel=True), so the call failed at first use. Compilation is lazy, so import quantecon was unaffected — the failure surfaced the first time a user called qe.gini_coefficient(...) in a JupyterLite notebook.

That is no longer the failure mode. Patch 0010 (emscripten-forge/recipes#6293, merged 2026-08-18, shipped as numba 0.67.0 build 1 on emscripten-forge-4x) rewrites options['parallel'] = False inside numba.core.decorators.jit on sys.platform == "emscripten" and forces NUMBA_NUM_THREADS=1, with a recipe test for exactly the @njit(parallel=True) + prange pattern. On that build the current code compiles and runs in the browser — but on a serial O(n²) path. The benchmarks in the #935 closing comment put that at 9.4 s natively for n = 100,000, roughly 20–30 s in WASM. Deployments built before 2026-08-18 (the notebook.link demo in #927 was on numba 0.66.0) still hit the original crash.

The rewrite is therefore still wanted, on two counts: it removes the serial O(n²) cliff, which matters most in the single-threaded browser, and it removes the library's dependence on a downstream patch whose own comment says it can be removed once the Emscripten stack supports pthreads.

Upstream

Patch 0010 is the outcome of @anutosh491's 2026-08-17 offer on #925 ("Is quantecon dependent on @njit(parallel=True) somehow? I think I might be able to get that working too!"). See emscripten-forge/recipes#6293; the numba recipe now carries ten patches (0001–0010).

Fix

Replace the O(n²) pairwise double loop with the O(n log n) closed form on sorted data, which removes the need for the parallel loop altogether. For y sorted ascending with 1-indexed i, the Gini coefficient is 2·Σ(i·y_i) / (n·Σy) − (n+1)/n:

@njit
def gini_coefficient(y):
    n = len(y)
    y_s = np.sort(y)
    i_weighted = 0.0
    total = 0.0
    for i in range(n):
        i_weighted += (i + 1) * y_s[i]
        total += y_s[i]
    return (2 * i_weighted) / (n * total) - (n + 1) / n

This was originally listed here as an optional follow-up, with a sys.platform != "emscripten" gate on parallel= as the primary fix. Benchmarking in #702 showed the rewrite is the better option on both counts, so the two have been swapped. It removes the Emscripten incompatibility at the source rather than gating around it, and it avoids the serial-O(n²) performance cliff that a platform gate would leave in place for browser users — which matters precisely because the browser is the single-threaded environment. Patch 0010 now applies that same gate upstream for every @njit(parallel=True) function, so the gate's performance drawback is exactly what browser users get today.

Measured against the current implementation (numba 0.62.1, numpy 2.3.5, 10 cores, best-of-5 after JIT warm-up, Pareto(3) inputs):

n	current (10-core parallel)	rewrite (single-threaded)	speedup
1,000	0.235 ms	0.0097 ms	24x
5,000	3.83 ms	0.222 ms	17x
10,000	13.8 ms	0.534 ms	26x
50,000	283 ms	3.29 ms	86x
100,000	1155 ms	6.89 ms	168x

The speedup grows with n because this is an algorithmic change, not a constant-factor one, and the single-threaded rewrite beats the 10-core parallel implementation at every size tested. Agreement with the current implementation is within 1e-9 on random Pareto data across all five sizes.

Note that prange and the parallel=True flag are both dropped. gini_coefficient is the module's only prange user, so the import on line 7 of _inequality.py should be narrowed to from numba import njit.

Smoke suite

ci/wasm/smoke_test.py (on main via #938) currently marks test_gini_coefficient as xfail(IS_EMSCRIPTEN, strict=True), and ci/wasm/test_jupyterlite.py::test_gini_fails_on_emscripten asserts that the call raises. Both encode the pre-patch-0010 failure mode: against numba 0.67.0 build 1 the first will XPASS (and fail, being strict) and the second will fail its assertion, whether or not #937 has merged. They must flip to a pass expectation before the first browser run — tracked in #933. Once a release containing #937 is installed in the browser, a useful check is that the rewrite is what executes — timing a large input against the serial-fallback figures in the #935 closing comment — since a bare "runs without error" no longer distinguishes the rewrite from the serial fallback.

Acceptance criteria

• gini_coefficient no longer uses @njit(parallel=True) or prange
• Existing test_gini_coeff assertions pass unchanged (Pareto and Weibull, rtol=1e-01)
• A regression test pins agreement with the pairwise definition on a small fixed array
• Browser confirmation is tracked in WASM: JupyterLite proof-of-concept deployment and browser smoke suite #928 (its gini_coefficient checklist item) and is not a blocker for closing this issue; it can only be run once a release containing the rewrite is installable in the browser