Repository navigation
The collide pass runs at 1.7-1.8x the reference on 5,000 resting cubes #17
Description
bench/dynamics.ae (PR #16): 5,000 cubes resting on a slab; the first collide pass (pairs, 5,000 hull-hull manifolds, 5,000 islands linked, the contacts coloured) takes 7.7 ms here against 4.6 ms for the reference's zero-time step; ten recycling passes take 3.9 ms against 2.2 ms (78 ns per contact against 44).
Suspects: each contact is reached by id into a 300-byte Contact (the reference prefetches the next contact and its b3Contact is 216 bytes with a union for the caches; ours carries both a MeshContactCache and a TriangleCache), the manifold points as four named struct fields copied through point_copy, and the hull-hull manifold itself (the distance layer's 1.3-1.5x). The recycling path is only dot products, transforms and a loop over the points, so its 1.8x is mostly the access pattern.
To do, once the contact solver reads these arrays: profile the pass with the instrumented build, split the contact's caches into a union-like block, gather the awake contacts' hot fields into a dense array for the pass, and measure the first pass again.
Activity
dynamics: point the collide note at issue #17
nicolas-maman commentedon Sep 20, 2026
Re-measured on main a61a6e8 (build flags of #24, wide contacts of #25):
scripts/bench.sh dynamicsfirst collide 6.4 ms vs 4.8 (1.34x, was 1.7x), ten recycling passes 2.65 vs 2.42 ms (1.1x, was 1.8x). A sampling profile of the first pass (40 worlds, scripts/profile.sh): manifold.compute_separating_axis is half of it, build_face_a_contact 16%, the pairs and tree 15%; the reference's SAT runs its support and edge tests over SoA vertex arrays in SIMD (convex_manifold.c b3GetSupportWide, b3NegativeTransformFromSoA), ours is its scalar path in doubles. In the large pyramid's step the narrow phase plus recycling is 1.9 vs 1.2 ms of 14.7 vs 9.7, so this is 0.7 ms of the 5 ms gap; a SoA SAT kernel beside the contact lanes (lanes.c) is the fix when it comes to the top.nicolas-maman commentedon Oct 3, 2026
#83 made the collide pass prefetch further down each contact's chain. It already fetched the contacts eight ahead and their manifolds four ahead. It now also fetches the shapes' bounds and body ids four ahead, and the bodies' set, index and kind two ahead. Interleaved against the previous main:
What's left is the layout, not a missed fetch. Each contact still leads through a large
Contactrecord, twoWorldShaperecords, twoBodyrecords and two 424-byteBodySimrecords before the recycle test can run. The reference walks compact per-setb3ContactSimrecords that carry the manifold and the body sim indices inline. A compact contact sim, built when the contact is made and kept beside the awake set, is the next step for this issue. For the first collide pass on fresh contacts, the earlier note still holds: an SoA SAT kernel (b3GetSupportWide).nicolas-maman commentedon Oct 3, 2026
Measured on 2026-10-03 and dropped, so it isn't tried again: prefetching each contact's two body sims one contact ahead in the collide pass (the transform, centre, extent and flags lines, on top of #83's shape and body prefetch). Large pyramid, interleaved against main: collide 1.50-1.63 ms with it against 1.54-1.61 ms without (one outlier round aside). No change. The recycle test isn't waiting on the sims' lines, so what's left is the compact contact-sim layout described above.
nicolas-maman commentedon Oct 5, 2026
Re-measured on main 3aa5d25 (2026-10-05), bench/dynamics against bench/dynamics_box3d.c, three runs each:
That's 1.15-1.25x and 1.1-1.4x, down from the 1.7-1.8x in the title. Split by Box3D's own profile (
b3World_GetProfileafter a zero-time step) against ours:update_pairstakes 2.1 ms against 1.6-1.7.About 55% of pair creation's samples land outside the executable. That's page faults on the 3.9 MB of fresh contact and manifold memory: 408-byte
Contactand 504-byteManifoldrecords in double precision, against Box3D's float ones. Only 7 blocks are allocated, so the allocation count isn't the cost.What's left here is record size, the same theme as #95 and #96. One option is still untried: keeping the mesh contact cache (64 bytes) out of line for convex contacts, as Box3D's union does. That saves about 8% of the memory.
nicolas-maman commentedon Oct 5, 2026
Closing: main b47a270 (with #111) measured against Box3D in the same session, three runs each:
The first pass is at parity and the recycling within 10-20%, down from the title's 1.7-1.8x. What got it there: the prefetching and recycling work (#79, #83), the SAT changes (#87, #94, #101), and #111's 64 bytes off every contact.
The rest of the recycling gap is our double-precision records against Box3D's float ones (a 344-byte Contact and a 504-byte Manifold), the same theme #95 tracks. Reserving the contact arrays through
WorldDef.contact_counttakes the first pass to 4.6-4.7 ms, but only by moving the page faults into world creation. Box3D also grows from 16 inside its timed region, so that isn't a gain.RESULTS: dynamics re-measured (collide at parity, #17 closed)