visiontrack-cpp

An optimized C++ ByteTrack, parity-gated against the visiontrack-mot NumPy reference.

This is a performance-engineering project, not a research one. It answers a single question: how fast can an honest ByteTrack go, and what exactly buys the speed? The research findings live in the sibling project, visiontrack.hulage.in.

pip install visiontrack-cpp

Both halves of that figure come from one script. bench/compare.py feeds both trackers the same detections, compares the full output streams bit-for-bit, and only then reports a timing — so the speedup is, by construction, a ratio between two identical computations. It refuses to print a number it has not verified, and has no flag to skip the check.

The rule

The NumPy implementation is the oracle. A faster tracker that changes the numbers is worthless.

Parity is proven before any optimization is attempted, so every later speedup is demonstrably behaviour-preserving rather than hopefully so.

Why a separate repo

VisionTrack's claim is a from-scratch tracker whose core is readable NumPy. A C++ core inside that repo would destroy the claim — a reader could no longer tell which implementation produced a published number. Keeping them apart also keeps the compiler toolchain, CMake build and platform wheels out of a project that needs none of them.

Because visiontrack-mot is on PyPI, this repo depends on the reference the way any third party would: a pinned, versioned dependency. The dependency runs one way and never back.

Status

All four phases resolved. Phases 1, 2 and 4 are complete. Phase 3 (GPU) is closed by measurement rather than left blocked: the only GPU-shaped work here is gating's N·M independent 4×4 solves, and it does not pay. Apple GPUs have no float64, so a bit-exact Metal path does not exist; and even granting a float64 GPU, Amdahl caps the win at 1.82× on synthetic scenes while dispatch overhead exceeds the entire gating computation on real ones — MOT17-09's median frame spends 0.85 µs there. PHASE3.md has the arithmetic and bench/gpu_feasibility.py reproduces it.

Phase 1 — all six milestones done. Both trackers produce identical (frame, track_id, box, score) streams over the full 525 frames of MOT17-09 on all three detector variants — 7,545 observations, zero divergence — and identical HOTA/IDF1/CLEAR-MOT to the last bit. Geometry, the Kalman filter and the solver are bit-identical underneath. Two inexactnesses remain, both measured and bounded rather than assumed away. 200 tests passing in ~5 seconds.

Run the harness yourself: parity/run_parity.py, latest output in parity/REPORT.md.

Parity is not a property of one machine

Bit-exactness is a claim about a compiled binary, so it has to be checked on every toolchain that compiles one. CI builds twelve wheels and runs the suite against each, and all twelve agree with the reference exactly:

Three compilers, two architectures, and — the part worth pausing on — two different LAPACK implementations. The Kalman gain is solved, not inverted, so the reference calls np.linalg.solve and the C++ calls Eigen. Those agreeing to the last bit against both Accelerate and OpenBLAS is stronger evidence than any single platform could give: a solve that merely looked right would not match two independent LAPACKs.

Every wheel also has to pass ci/check_oracle.py before its tests run. It refuses to compare against a NumPy that pip built from source, because such a NumPy links whatever LAPACK the build host had and is therefore not the reference. That check exists because its absence sent three CI runs chasing a divergence that was never in the tracker — see PHASE4.md.

Milestone 4 was the risky one — see Tie-breaking below for what it cost. Milestone 5 is where the parity gate stopped being a claim and became a result.

The harness

python parity/run_parity.py                        # the report, to stdout
python parity/run_parity.py --with-tests --scaling  # + unit parity + throughput sweep
python parity/run_parity.py --markdown parity/REPORT.md --json parity/report.json

Exit status is 0 only if every variant reaches trajectory parity, so it drops into CI unchanged. It needs the MOT17 cache from the sibling visiontrack checkout; point VISIONTRACK_MOT17_CACHE elsewhere if yours lives somewhere else, and it skips cleanly when the cache is absent.

The harness is itself tested — including that it detects an injected one-ULP divergence. A gate that cannot fail proves nothing.

Install

pip install visiontrack-cpp

Wheels are built for CPython 3.10-3.13 on macOS 11+ arm64, Linux x86_64 (manylinux_2_28, so glibc ≥ 2.28) and Windows x86_64. Anywhere else — Linux aarch64, an older glibc, a newer Python — pip falls back to the sdist, which needs a C++17 compiler and CMake ≥ 3.20; Eigen it will fetch itself if the machine has none.

The Linux floor is glibc 2.28 rather than the older manylinux2014 because NumPy ≥ 2.4 requires glibc 2.27 and publishes no manylinux2014 wheel. On an older host pip would compile NumPy from source, and a source-built NumPy is not the reference the parity claim is made against.

Building from source

brew install eigen          # optional; see below
pip install -e ".[test]"
pytest

Eigen resolution has three steps, in order: an installed Eigen found by CMake config, then the usual system include paths, then a pinned download of Eigen 3.4.0. Two switches control it:

The download is pinned rather than floating because Eigen picks different kernels between versions, and this package's claim is bit-for-bit agreement with NumPy. A floating dependency would make a wheel's numerics depend on the day it was built. VT_SYSTEM_EIGEN=OFF is what a release wheel wants: it makes the binary's arithmetic a property of this repo rather than of whatever the build host had in /opt/homebrew.

Parity has been confirmed under both Eigen 3.4.0 and 3.5.0 — full suite and the trajectory gate, same 7,545 observations, zero divergence either way. That is two data points, not a guarantee for every Eigen version, which is why the fetch is pinned.

Checking a build is sound

>>> import visiontrack_cpp as vt
>>> vt.build_info()
{'module_version': '0.1.0', 'eigen_version': '3.5.0',
 'pybind11_version': '3.1', 'cxx_standard': 201703, 'fp_contract_off': True}

fp_contract_off is the one to read. It is measured against the binary that was actually built — not read off a macro — and False means the compiler fused a multiply-add somewhere and this build cannot match NumPy. See Load-bearing build flags below for why that is fatal rather than cosmetic.

The parity gate

Metric-level agreement is not the gate. Association is discrete: a 1e-16 difference in one cost entry can flip an assignment, change a track ID, and cascade through every later frame — while MOTA barely moves. Metric parity would pass a visibly wrong tracker.

The gate is trajectory-level, in three tiers:

1. Unit parity — each ported function vs its NumPy original on randomized and degenerate inputs.
2. Trajectory parity (the real gate) — identical (frame, track_id, box) streams on MOT17-09, across all three cached detector variants.
3. Metric parity — a backstop, scored by the reference's own eval/ so both trackers are measured by the same code.

Load-bearing build flags

CMakeLists.txt sets -ffp-contract=off. Do not remove it. clang defaults to -ffp-contract=fast at -O2/-O3, which fuses a + b*c into a single FMA instruction that rounds once where NumPy rounds twice. That is a 1-ULP difference on every height-scaled term of the Kalman process noise. It is invisible in a single call, compounds over a trajectory, and is exactly the kind of drift that flips a near-tied association thousands of frames later.

The FMA result is arguably more accurate. It is still wrong here: correctness in this repo means "identical to the oracle", not "closer to the real number".

The one place parity is not exact

gating_distance Cholesky-factorizes the innovation covariance, then calls np.linalg.solve on that factor. Measuring rather than assuming produced two findings:

• NumPy's cholesky is bit-identical to the textbook Cholesky–Banachiewicz ordering, so the port uses that instead of Eigen's LLT, which rounds differently.
• NumPy's solve reaches Accelerate's LAPACK, and its output matches neither a textbook LU with partial pivoting nor the reciprocal-scaling variant that LAPACK's own reference dgetf2 describes. Matching it exactly would mean reimplementing a specific vendor kernel.

So gating carries a few-ULP residual, asserted at rtol=1e-14. The tests also assert that no track/measurement pair disagrees about passing the chi-square gate. Whether the residual ever changes a real association is a question only milestone 5's trajectory parity can answer.

Trajectory parity — the result

The gate the whole project is built around now passes. Over MOT17-09's full 525 frames, driven by the same cached public detections the reference's own evaluator uses:

Identical means identical: same track IDs, same boxes bit-for-bit, same scores, same frames. Not "within tolerance".

That matters more than the unit tests it rests on, because a tracker is a feedback loop — its output at frame N is part of its input at frame N+1. One flipped association does not stay one flipped association; it renames a track and every later frame inherits the rename. Unit parity cannot see that.

What this did not prove. Milestone 3 left gating_distance carrying a few-ULP residual, and stages 1 and 3 compare that value against the chi-square threshold — so in principle a pair sitting on the threshold could be gated differently by the two implementations. Trajectory parity passing does not mean the residual is harmless; it means the residual did not fire on these frames. So it was measured instead:

Eleven orders of magnitude of headroom on this data. That is an empirical statement about MOT17-09, not a proof — a different sequence could sit closer. The test asserts a margin of 1e6 residuals rather than merely "no disagreement", so it fails while there is still room to investigate rather than after a silent flip.

Because real data never lands on a gate boundary, no trajectory test can reach that case. The boundary tests construct it directly, one ULP either side of both gates.

The other place parity is not exact

appearance_distance ends in tf @ df.T, which NumPy routes to Accelerate's BLAS. It is not bit-exact — about 1–2 ULP, at every embedding dimension tested including 4.

This is the exact mirror of the Kalman finding, and the pair is worth stating together:

• In the Kalman filter, clang fused a + b*c into an FMA and NumPy did not. -ffp-contract=off fixed it.
• In appearance, Accelerate is the one fusing, and the port cannot follow.

Three candidate explanations were measured against np.dot at dimension 4 and all three were rejected: a naive left-to-right dot product, a pairwise one, and even an exact-then-round-once chain (a perfect FMA). It is Accelerate's own blocked kernel — the same dead end as the gating solve.

It is tolerated because w_app is 0.0 in every Phase 1 path, so the term never reaches the solver, and a test pins that default.

Phase 1 scope guards

TrackerConfig accepts use_gmc, use_oru and w_ocm — and refuses to build if any of them is enabled. Those are research extensions the plan leaves in Python. Accepting them and quietly ignoring them would produce a tracker that is parity-clean on the default path and silently wrong the moment someone flips a switch, which is the worst available failure mode for a project whose entire claim is parity.

Tie-breaking

When two assignments have equal cost, the implementation picks the winner, not the mathematics. Both solvers minimize the same sum and may legitimately return different optima. Four behaviours turned out to be load-bearing:

• The transpose in linear_assignment when rows > cols. > not >=: a square matrix is not transposed, and transposing changes the scan order.
• Both tie-break comparisons are strictly-less, so the lowest column index wins. Relaxing either to <= still returns an optimal assignment, and a different one.
• The slack expression order: cost - u - v, two left-to-right subtractions, not cost - (u + v).

The last one is the interesting one, because it nearly escaped. Regrouping the slack changed the values in 82 of 2400 random matrices but never changed the answer — it looked cosmetic. A targeted search over mixed magnitudes with ULP-level ties found that it does flip the assignment, roughly 5 times in 6000. Those five witnesses are pinned as a regression test.

Every one of these was verified by mutation: each behaviour was deliberately broken and the suite re-run. All four fail loudly (13–16 tests each). A fifth candidate — splitting the fused minv/delta scan into two passes — leaves the suite green, correctly: each minv[j] is already final when compared, so the fused scan yields the same minimum with the same tie-break.

Random float costs almost never tie, so a suite built on them would have passed all five mutants. The tests are weighted towards degenerate input instead: an exhaustive sweep of all 512 3×3 binary matrices, all 729 ternary 2×3 and 3×2 matrices, constant and circulant matrices, and saturated 1 - IoU costs where most box pairs do not overlap and are therefore tied at exactly 1.0 — which is what the tracker actually feeds the solver.

When trajectory parity fails, the fix is a frame-indexed diff of the first divergent assignment — never a loosened tolerance.

Throughput — where the plan was wrong

Phase 1 was supposed to produce no speedup. The plan said so explicitly, and gave a reason: a naive C++ port of vectorized NumPy is often slower, because "NumPy's inner loops are already compiled BLAS-adjacent code".

Measured, that prediction is wrong by a wide margin — 55–74× on real sequences, 71–91× across synthetic scenes from 5 to 400 simultaneous objects (bench/BENCHMARK.md).

Why this differs from the parity report. parity/REPORT.md puts the real sequences at 35–55×, and it is measuring something subtly different: it runs both trackers in the same loop, one frame at a time, un-warmed and once. Sharing a loop with NumPy costs the C++ tracker 21% (9.55 → 11.59 µs on MOT17-09-SDP, measured directly) because NumPy's allocations evict its working set between calls — while costing NumPy itself 0.3%, since 2 µs of interference is nothing against a 700 µs frame. The bias is asymmetric and it lands entirely on the smaller number. The harness's job is the parity gate, where interleaving is exactly right — the two trackers must see identical state at identical times. For throughput, bench/compare.py is the measurement of record: each tracker timed alone, warmed, min-of-9.

The reason matters more than the number, and two tempting explanations are both wrong:

• Not Detection construction. It looked like the NumPy timing might be inflated by object construction the array-based C++ entry point skips. Measured separately: at most 3% of a frame.
• Not NumPy per-call overhead on small matrices. Plausible — MOT17-09's median cost matrix is 9×7 — but it predicts the advantage collapsing as the problem grows. It does not: the ratio stays flat out to 400×400.

Profiling the reference gives the real answer, in two parts:

• _kuhn_munkres is not vectorized NumPy at all. It is an interpreted O(n³) triple loop, and the largest single entry in the profile. The plan's premise is simply false for that function.
• The per-track calls operate on 4- and 8-element arrays. xyah_to_xyxy runs ~8,850 times per 60 frames, kalman.update ~2,950, each on one track. At that size NumPy's per-call machinery dwarfs the arithmetic it performs.

So the hot path was never the vectorized numerics the plan had in mind — it was Python-level work on tiny arrays, and that is what the port removed.

This revises Phase 2 rather than confirming it. The plan wanted its headline to be "LAPJV replaced the O(n³) Hungarian and the numbers did not move". Much of that cost turns out to have been interpreter overhead the port has already eliminated, so the remaining algorithmic win should be expected to be smaller than the plan assumed. It now has a fair baseline to be measured against, which is what Phase 1 was for.

Honest expectations, and how they turned out

Phase 1 was planned on the expectation of no speedup — that a first-draft C++ port might even be slower than vectorized NumPy, whose inner loops are already compiled. The deliverable was meant to be the harness alone.

The harness was delivered and the prediction was refuted: 55–74× on real sequences, for the reasons in Throughput above. The speedup is a real measurement, but it is not the achievement — it is a baseline, obtained from a deliberately unoptimized port with no SIMD, no LAPJV and no memory-layout work.

What Phase 1 actually produced is the thing that makes any later number believable: a gate that fails on a single flipped association. Without it, "50× faster" would be an unfalsifiable claim about a tracker nobody had checked.

New to C++ / CMake / pybind11?

learning/LEARNING.md explains this project from zero — what a compiler does, why Python is slow but NumPy isn't, what each tool in the build is for, and why parity is checked on full output streams rather than accuracy scores. No prior C++ assumed.

Licence

MIT.