Introduction

The concordance index (C-index), or Harrell's C-statistic, measures the discriminative ability of a survival model by estimating the probability that, for a randomly chosen pair of individuals, the one who experienced the event first had a higher predicted risk. It is the dominant evaluation metric in clinical risk modeling, prognostic scoring, and time-to-event machine learning.

Despite its ubiquity, standard implementations—including the widely used lifelines Python library—rely on naive O(N²) pairwise comparison algorithms. At scale (N ≥ 10,000) or under bootstrap resampling (1,000+ iterations), this quadratic complexity introduces substantial computational overhead that limits the practical use of bootstrap-based confidence intervals and paired model comparisons.

fast-cindex addresses this bottleneck through two complementary strategies: (1) an O(N log N) algorithm based on an array-backed binary search tree, and (2) Numba JIT compilation with parallel bootstrap loops.

Methodology

O(N log N) Algorithm

The concordance count can be reformulated as a rank-query problem. For each death event, the algorithm queries how many prior deaths had lower predicted risk scores—a problem efficiently solved with an order-statistics tree.

fast-cindex builds a complete balanced BST from the sorted unique death scores using an array-based representation (avoiding pointer-dereference overhead). The core loop proceeds as follows:

1. Group simultaneous death events (tied event times).
2. Query the tree for concordant count: the number of historical deaths with lower risk scores than the current death group (_btree_rank()).
3. Insert the current death group into the tree (_btree_insert()).
4. Query the tree for censored observations against the updated historical record.

This yields O(N log N) time complexity, compared to O(N²) for naive pairwise iteration.

Numba JIT Compilation

The BST operations and main concordance loop are implemented in pure NumPy-compatible Python and decorated with Numba's @njit (no-Python JIT) decorator with fastmath=True. This compiles the hot path to native machine code at first call, achieving performance comparable to hand-written C.

Parallelized Bootstrap

The bootstrap loop in bootstrap_cindex() and compare_cindex() uses @njit(parallel=True) with prange, distributing bootstrap iterations across all available CPU cores. The compare_cindex() function applies identical bootstrap samples to both models, enabling valid paired statistical testing with controlled type I error.

Public API

from fast_cindex import cindex, bootstrap_cindex, compare_cindex

# Single C-index
c = cindex(times, scores, observed)

# Bootstrap confidence interval
dist = bootstrap_cindex(times, scores, observed, n_bootstraps=1000, seed=42)
ci_low, ci_high = np.percentile(dist, [2.5, 97.5])

# Paired model comparison
delta_dist = compare_cindex(times, observed, scores1, scores2, n_bootstraps=1000, seed=42)
p_value = np.mean(delta_dist <= 0)

Convention: higher scores indicate higher predicted risk.

Results

Benchmarks were run on the Rossi recidivism dataset (432 observations), subsampled to four sizes, with 1,000 bootstrap iterations where applicable. Timings exclude the one-time Numba JIT compilation overhead (~2.9 s).

Single C-Index

Bootstrap (1,000 iterations)

Speedups grow with N for the single C-index case, reflecting the algorithmic improvement from O(N²) to O(N log N). Bootstrap speedups are dominated by parallelism and exceed 140× at practical clinical dataset sizes.

Discussion

The combination of algorithmic improvement and JIT compilation makes bootstrap-based inference practical where it was previously cost-prohibitive. A 1,000-iteration bootstrap on a 10,000-sample dataset takes under 200 ms with fast-cindex versus 28 seconds with lifelines—a difference that changes whether researchers run bootstrap inference routinely or skip it entirely.

The paired bootstrap comparison (compare_cindex) is particularly notable: by using identical resamples for both models, it controls for within-sample correlation and provides valid p-values for model selection without inflating type I error.

Limitations. The one-time JIT compilation cost (~2.9 s) makes fast-cindex slower than lifelines for single calls in a fresh process. Users in interactive or scripting contexts should warm up the JIT before benchmarking or call the function twice (the second call is fast).

Conclusion

fast-cindex reduces concordance index computation from O(N²) to O(N log N) and delivers 27–147× speedups over lifelines through Numba JIT compilation and parallel bootstrap loops. It is available via pip install fast-cindex under the Apache 2.0 license. Source code: https://github.com/deweihu96/fast-cindex

References

• Harrell, F. E., Califf, R. M., Pryor, D. B., Lee, K. L., & Rosati, R. A. (1982). Evaluating the yield of medical tests. JAMA, 247(18), 2543–2546.
• Davidson-Pilon, C. (2019). lifelines: survival analysis in Python. Journal of Open Source Software, 4(40), 1317.
• Lam, S. K., Pitrou, A., & Seibert, S. (2015). Numba: A LLVM-based Python JIT compiler. Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC.