AVX2 and runtime switching of SIMD implementations

[EthanRutherford]

I brought this topic up in the discord server, but TL;DR I believe box3D could see some strong perf gains from increasing from 4 to 8 wide SIMD instructions. The majority of devices in use today support AVX2, and it's possible to detect support at runtime and switch out implementations with function pointers. I've been experimenting with this locally, applying it to the collideHulls code, and at one point it was working. I pulled in some changes from main, though, and at present the collision code is no longer working, but it is a proof of concept showing that runtime detection and switching is working. SSE works, and in theory AVX2 will work as soon as I can find the logic error.

[erincatto]

We should try the contact solver first. Especially since there is a Box2D example.

[EthanRutherford]

Here's my working branch where I've set up all the code around adding AVX2. I've stripped out what I was experimenting with in collideHulls, as it wasn't fully working yet, so there's no longer any actual dynamic dispatch going on. However, it's relatively straightforward, looks like this:

// declare wide versions
void FooW4();
void FooW8();

// declare dispatcher
void dispatchFoo();

// function pointer for dynamic dispatch
void (*doFoo)() = dispatchFoo;

// called once on first invocation, then replaces itself with best compatible implementation
void dispatchFoo() {
    if (checkCPUSupportsW8()) {
        doFoo = FooW8;
    } else {
        doFoo = FooW4;
    }
    doFoo();
}

// public api
void Foo() {
    doFoo();
}

My approach is to split the simd interface into w4 and w8 versions of all structures and functions, and architecture macros will determine which simd interfaces are included. There's a new macro for when dynamic dispatch is enabled, and flags for which widths are available (B3_SIMD_WIDTH is no longer a global macro, since we can have multiple widths available at compile time, to be chosen between at runtime). This has the added benefit of allowing 8-wide SIMD to be added piecemeal, as we can just hardcode everything to use the 4 wide interface first, and then add 8-wide versions and static or dynamic switching one function at a time. I've done the first part in that branch.

I initially was experimenting with trying to write one implementation that could be included twice, switching which intrinsics it calls in each version by defining macros, but I wasn't a big fan of the approach. The ergonomics of this in C++ with templates and if constexpr () would be perfect for this, but trying to replicate that in C with macros and include-guard-less headers just feels messy and error prone. And, at least for the major SIMD areas, the contact solver and hull collider, there's a lot of code in those implementations that depends on the SIMD width being 4, and it was proving difficult to untangle with preprocessor macros. It would be ideal if we could avoid having two separate copies of the code for each SIMD method, both because it would be more code to maintain as well as a possible source of determinism mismatches, but I'm not sure whether or not it's worth the tradeoff.

[EthanRutherford]

forgot to link the branch: https://github.com/erincatto/box3d/compare/main...EthanRutherford:Prometheus:AVX2?expand=1

[EthanRutherford]

I've added 8 wide versions of contact solver as well as collide hulls. Tests have been run and pass, I've run visual spot checks in the samples app, and tested across clang-cl as well as msvc. I don't have any *nix systems, so that still needs to be verified, but I suspect there shouldn't be any problems. Builds for non-x86 should behave exactly as before. If compiling the lib with the __AVX2__ macro defined, or BOX3D_FORCE_AVX2, the library will be compiled with static dispatch rather than function pointers (similarly, one can define BOX3D_FORCE_SSE2 for static sse). On my machine, there wasn't any noticeable difference in perf between static and dynamic versions, but the option is there. Here's the raw results of the benchmarks run with SSE vs AVX benchmarks.zip, but I've also had copilot compile the results into a markdown table for easy viewing below:

Benchmark	Threads	AVX2 (ms)	SSE (ms)	Gain (%)
convex_pile	1	4,797.570	5,033.290	4.7
convex_pile	2	2,593.420	2,728.290	4.9
convex_pile	3	1,794.060	1,912.060	6.2
convex_pile	4	1,410.250	1,503.760	6.2
convex_pile	5	1,179.910	1,258.580	6.3
convex_pile	6	1,056.900	1,097.240	3.7
convex_pile	7	963.479	990.006	2.7
convex_pile	8	889.933	945.992	5.9
convex_pile	9	885.876	909.128	2.6
convex_pile	10	859.332	895.363	4.0
convex_pile	11	836.920	875.529	4.4
convex_pile	12	815.772	840.458	2.9
joint_grid	1	1,090.410	1,082.080	-0.8
joint_grid	2	558.939	556.696	-0.4
joint_grid	3	383.324	380.995	-0.6
joint_grid	4	296.645	294.717	-0.7
joint_grid	5	241.566	241.984	0.2
joint_grid	6	207.799	210.869	1.5
joint_grid	7	187.402	189.603	1.2
joint_grid	8	178.402	183.461	2.8
joint_grid	9	179.579	182.960	1.8
joint_grid	10	170.976	171.559	0.3
joint_grid	11	165.028	164.861	-0.1
joint_grid	12	161.257	160.145	-0.7
junkyard	1	9,938.860	11,184.900	11.1
junkyard	2	5,295.050	5,697.260	7.1
junkyard	3	3,703.390	3,963.980	6.6
junkyard	4	2,901.700	3,122.600	7.1
junkyard	5	2,503.540	2,667.680	6.2
junkyard	6	2,211.370	2,335.490	5.3
junkyard	7	2,036.440	2,134.590	4.6
junkyard	8	1,917.290	2,004.690	4.4
junkyard	9	1,866.110	1,940.800	3.8
junkyard	10	1,812.380	1,873.470	3.3
junkyard	11	1,766.900	1,818.830	2.9
junkyard	12	1,727.420	1,773.230	2.6
large_pyramid	1	1,104.210	1,423.700	22.4
large_pyramid	2	588.390	718.878	18.2
large_pyramid	3	407.368	497.013	18.0
large_pyramid	4	316.519	389.470	18.7
large_pyramid	5	271.021	326.923	17.1
large_pyramid	6	250.115	300.106	16.7
large_pyramid	7	222.614	268.484	17.1
large_pyramid	8	212.932	258.289	17.6
large_pyramid	9	215.370	256.305	16.0
large_pyramid	10	219.350	252.564	13.2
large_pyramid	11	219.599	250.293	12.3
large_pyramid	12	218.057	247.388	11.9
large_world	1	4.491	5.513	18.5
large_world	2	7.156	7.856	8.9
large_world	3	8.188	9.333	12.3
large_world	4	9.119	9.981	8.6
large_world	5	9.494	10.071	5.7
large_world	6	10.018	10.561	5.1
large_world	7	11.286	10.565	-6.8
large_world	8	12.548	11.105	-13.0
large_world	9	12.867	12.695	-1.4
large_world	10	12.399	10.661	-16.3
large_world	11	14.529	13.971	-4.0
large_world	12	12.775	13.696	6.7
many_pyramids	1	1,217.240	1,525.970	20.2
many_pyramids	2	625.029	761.230	17.9
many_pyramids	3	423.398	519.462	18.5
many_pyramids	4	320.830	399.593	19.7
many_pyramids	5	273.617	336.177	18.6
many_pyramids	6	239.482	295.048	18.8
many_pyramids	7	218.540	265.786	17.8
many_pyramids	8	209.865	247.941	15.4
many_pyramids	9	207.640	243.750	14.8
many_pyramids	10	203.371	232.543	12.5
many_pyramids	11	200.125	228.279	12.3
many_pyramids	12	194.863	217.373	10.4
rain	1	1,717.370	1,702.210	-0.9
rain	2	937.407	943.301	0.6
rain	3	668.820	673.742	0.7
rain	4	533.361	543.120	1.8
rain	5	454.202	462.815	1.9
rain	6	415.129	420.501	1.3
rain	7	386.859	388.258	0.4
rain	8	370.249	372.005	0.5
rain	9	369.515	370.039	0.1
rain	10	365.782	365.252	-0.1
rain	11	361.751	357.046	-1.3
rain	12	354.779	356.066	0.4
sleep	1	601.154	774.368	22.4
sleep	2	338.498	419.592	19.3
sleep	3	242.363	300.332	19.3
sleep	4	203.105	248.404	18.2
sleep	5	179.062	213.726	16.2
sleep	6	173.492	205.055	15.4
sleep	7	162.385	190.070	14.6
sleep	8	162.127	188.139	13.8
sleep	9	171.855	195.583	12.1
sleep	10	170.850	192.842	11.4
sleep	11	175.244	200.124	12.4
sleep	12	180.056	205.318	12.3
spinner	1	2,600.410	2,708.150	4.0
spinner	2	1,566.130	1,641.800	4.6
spinner	3	1,160.580	1,211.210	4.2
spinner	4	946.607	996.926	5.0
spinner	5	824.177	902.905	8.7
spinner	6	815.052	865.366	5.8
spinner	7	747.736	816.621	8.4
spinner	8	733.619	781.080	6.1
spinner	9	740.715	791.596	6.4
spinner	10	752.889	796.388	5.5
spinner	11	790.422	823.248	4.0
spinner	12	793.398	830.053	4.4
trees100	1	153.655	149.236	-3.0
trees100	2	100.307	99.422	-0.9
trees100	3	81.900	79.649	-2.8
trees100	4	73.837	72.930	-1.2
trees100	5	69.936	70.203	0.4
trees100	6	68.551	68.097	-0.7
trees100	7	69.637	69.098	-0.8
trees100	8	70.217	70.067	-0.2
trees100	9	71.380	70.750	-0.9
trees100	10	71.095	70.384	-1.0
trees100	11	71.221	71.185	0.0
trees100	12	71.659	71.567	-0.1
trees25	1	653.336	618.291	-5.7
trees25	2	366.442	350.057	-4.7
trees25	3	268.146	260.499	-2.9
trees25	4	230.946	225.468	-2.4
trees25	5	210.903	207.248	-1.8
trees25	6	198.459	197.515	-0.5
trees25	7	192.991	189.627	-1.8
trees25	8	187.030	185.185	-1.0
trees25	9	185.373	184.767	-0.3
trees25	10	184.258	183.197	-0.6
trees25	11	184.401	181.936	-1.4
trees25	12	183.628	182.377	-0.7
trees50	1	268.112	260.857	-2.8
trees50	2	162.866	158.347	-2.9
trees50	3	124.865	120.980	-3.2
trees50	4	111.841	109.799	-1.9
trees50	5	105.340	102.782	-2.5
trees50	6	100.010	99.870	-0.1
trees50	7	99.217	97.823	-1.4
trees50	8	100.571	98.587	-2.0
trees50	9	99.465	98.385	-1.1
trees50	10	101.968	99.075	-2.9
trees50	11	101.139	100.519	-0.6
trees50	12	102.614	99.751	-2.9
washer	1	14,883.300	16,304.100	8.7
washer	2	8,184.410	8,670.480	5.6
washer	3	5,634.640	6,030.600	6.6
washer	4	4,480.890	4,751.850	5.7
washer	5	3,764.810	4,042.170	6.9
washer	6	3,364.880	3,542.730	5.0
washer	7	3,093.750	3,225.610	4.1
washer	8	2,955.030	3,046.390	3.0
washer	9	2,773.440	2,972.110	6.7
washer	10	2,717.650	2,892.530	6.0
washer	11	2,787.730	2,801.450	0.5
washer	12	2,735.980	2,749.770	0.5

benchmarked on Intel Core i9-12900KS

[Ronniko]

Waiting Intel ultra core 400 with AVX 10.1

https://learn.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.x86.avx10v1?view=net-9.0