5 ms·
SIMD for Collision
- brcmthrowaway 3mo agoNo support for any ARM vector instructions.. thats horrible
- tom_ 3mo agoIt looks like it supports NEON: https://github.com/erincatto/box3d/blob/781673be801569a94be7942848755fc0baad3653/src/simd.h#L386 https://github.com/erincatto/box3d/blob/781673be801569a94be7...
- brcmthrowaway 3mo agoOld hat. Should be SVE
- dundarious 3mo agoName a few big products with SVE and not NEON, within the gaming market
- adrian_b 3mo agoNEON is an obsolete and inappropriate name, but I think that what you mean is that among the 64-bit Arm CPUs, all those that support SVE (which includes the CPUs of all recent so-called "gaming smartphones") also support the original Aarch64 floating-point instruction set, which is available in all 64-bit Arm CPUs that have been used in mobile phones, tablets or laptops.
- dundarious 3mo agoThe "and not Neon" was a bit of an unnecessary pre-condition I shouldn't have added. However, given the OP discusses "there were a surprising number of users without AVX2 capable CPUs", I think there would be an un-surprising number of users (for this type of library) without SVE. SVE feels analogous to some of AVX-512 at present -- maybe not that bad.
- adrian_b 3mo agoIndeed, while the SVE support is reasonably widespread because it is included in all the higher-priced Android smartphones launched during the last 4 years and a half, some very cheap smartphones with Cortex-A78, without SVE support, are still being sold.
- dundarious 3mo agoThat's the Switch 2's chip, isn't it? Meaning missing SVE there too. Casual search leads me to believe Steam Frame will also not include it (Snapdragon 8 Gen 3, but added in Elite Gen 5). Another generation, perhaps.
- flohofwoe 3mo agoDo the Apple CPUs support SVE? If not then it's not worth the hassle tbh (and support on Android devices doesn't seem to be great either).
- adrian_b 3mo agoEarlier Apple CPUs do not support SVE. Recent Apple CPUs support a certain variant of the so-called "streaming" SVE (which is included in the SME specification), which is implemented in a way that has poor performance, so it probably exists only for software compatibility, but its use is not recommended. On Apple CPUs, the original 64-bit FP instructions must be used when low latency is important and SME must be used when high throughput is important. Most Android smartphones that were launched on the market since around the beginning of 2022 support SVE, so by the end of this year there will be 5 years of availability. Of course there are people who have not updated their smartphones. I still use an ASUS Zenfone from 2019, which precedes SVE (though I think that this year I might finally buy a new smartphone among those that use Mediatek 9500 or Exynos 2600, because I am curious to experiment with the new Arm SME2 instruction set). Among the cheapest smartphones, there are still sold some with old Cortex-A78 cores (launched in 2020), which do not support SVE.
- adrian_b 3mo agoNEON is a name that should never be used again, because it is extremely ambiguous. Whenever someone speaks about Arm NEON it is impossible to guess what instruction set is meant. The 32-bit Arm architectures have used several kinds of floating-point units, with very distinct capabilities, so when compiling a program for 32-bit Arm CPUs you must always provide a specific FPU selecting option to the C/C++ compiler, the one correct for the target CPU, otherwise the performance will be suboptimal. (an example of how such a compiler option looks like: "-mfpu=fpv5-d16") Only the 64-bit Aarch64 has cleaned up this mess, so for Armv8-A there is a well defined FPU instruction set, supported by all CPUs. The Armv9.0-A and Armv9.2-A CPUs continue to support the original 64-bit FP instruction set, but they add SVE and SVE2. The Armv9.3-A CPUs, launched last autumn, continue to support the original 64-bit FP instruction set + SVE + SVE2, but they add SME and SME2. The Apple CPUs implement the original 64-bit FP instruction set but they do not implement SVE/SVE2 (except in a non-performant "streaming" mode), but in the past they had a non-documented AMX extension and now they have SME.
- ack_complete 3mo agoFor a while it looked like ARM was trying to call the ARMv8 vector instruction set ASIMD instead of NEON, but they seem to have thrown in the towel as the ARM Intrinsics Guide simply refers to Neon.
- wolfd 3mo agoThis is free software.
- grg0 3mo agoAs a SIMD noob, one thing that wasn't obvious to me is that SIMD can also speed you up if your mem throughput is underutilized by having the CPU load more data per instruction. It isn't just about compute speedups, which is typically what it's advertised for. Using perf on Linux has been very educational for me to get an intuition for modern CPU performance.
- Cloudef 3mo agoThe way simd speeds up "compute" is indeed mainly the reason that you operate on multiple pieces of data at once.
- ChrisGreenHeur 3mo agoIf so they should just name it that
- ks6g10 3mo agoThey should name it Multiple memory data, one single CPU instruction, or mmdosci for short. Easy to remember.
- grg0 3mo agoYeah, and in the blog post he mentions that he had to transform the data to SoA. If he had done that alone, he might already have seen a speedup from better cache utilization. Also, I see no mention of alignment in the post. I understand x86/AVX2 likes your load/stores to be aligned, even if it technically allows unaligned access.
- dzaima 3mo agoUnaligned loads/stores aren't super bad; if still within a cacheline, there's zero penalty, and on crossing cachelines it's alike two ops (except page crossing, which is more bad). So, for 32B loads/stores and 64B cachelines, it's 1.5x more L1 cache ops (as half of the ops will cross a cacheline); perhaps bad if you're L1-cache-throughput-bound, but less so if you're at L2+ as the extra work sits in L1.
- NotGMan 3mo ago[dead]
- dcrazy 3mo agoWookash Podcast just interviewed Erin Catto (the Box2D author): https://podcasts.apple.com/us/podcast/what-makes-a-good-physics-engine-erin-catto/id1683109481?i=1000778335530 https://podcasts.apple.com/us/podcast/what-makes-a-good-phys... (sorry, I couldn’t find a player-agnostic feed link, even on wooka.sh, the podcast’s own website!)
- RossBencina 3mo agoHere's the video: https://www.youtube.com/watch?v=DQNqo2xtq6U https://www.youtube.com/watch?v=DQNqo2xtq6U
- Decabytes 3mo agoI feel like SIMD has been around for decades. Why has it taken this long to catch on? I feel like I have been hearing it a lot through the past few years. It feels like it’s talked about like some programming silver bullet
- actionfromafar 3mo agoLLMs?
- r3trohack3r 3mo agohttps://en.wikipedia.org/wiki/Single_instruction,_multiple_data https://en.wikipedia.org/wiki/Single_instruction,_multiple_d... Looking at the Wikipedia article - I wonder if it is because SIMD and SIMT are enabled by hardware first
- bellowsgulch 3mo agoThe average programmer isn’t falling into pits of success with auto vectorization. And you’re using languages like Python or Lua and not using a dependency that uses it for you, forget about it.
- xphos 3mo agoRemember the part of the article where he talks about a shocking number of people didnt have the version of AVX he wanted. This is a big issue because SIMD is writing ASM for the most part not C code so new architecture you have problems . RVV riscv SIMD has an interesting way to adapt to different CPU tiering and is a rather complete SIMD architecture but most SIMD architectures have small holes which can be mildly annoying Simd is by far the most efficient cycles wise paradigm but its also brittle. When the shape of data is odd which is common enough you have to handle it properly which is sometimes a distraction from what people actually care about. Also GPUs exist, GPUs despite being way less power efficient are not brittle in this same way they have issues if memory is difficult but most problems work nicely on GPUs so people just do that because its easier and the tiering problem is less a big deal because GPU process instructions different than SIMD and batching and what not is left to hardware not the programmer
- RossBencina 3mo ago
- throwaway2027 3mo agohttps://www.youtube.com/watch?v=6BIfqfC1i7U https://www.youtube.com/watch?v=6BIfqfC1i7U
- zamalek 3mo agoBack in the day I was writing a liero clone, and came up with a neat scheme for pixel-perfect collisions (probably serendipitously, no claims it's unique). A 64bit integer can be seen as an 8x8 mask. You can pixel shift it up and down by simply bitshift left or right by 8n bits. Pixel shift left and right required more instructions; if I was to write it today I would probably store an additional rotated version instead (as that would then effectively pixel shift left and right with bit shifts). You then have the terrain chopped up into these 8x8s too, and can then do a collision test with at most 4 of them with the 1 character/entity mask.
- Animats 3mo agoExhaustively doing all the edge-edge collision tests is working far too hard. That's why he needs SIMD. I did the first ragdoll physics system about 20 years ago, when we had less compute available.[1] GJK, which the author mentions, is the preferred algorithm for convex hull collisions. GJK is a hill-climber. You start with two points, one on each object, and walk them towards each other along edges, picking the direction that produces the most improvement. This is O(sqrt N) on the number of vertices per object. That's with two random starting points. If you're doing this repeatedly, as in an animation, you can start from the winning points of the previous round. If the objects are not rotating and moving very fast, the recheck is constant time. If they move a little, it takes slightly longer, of course. Many modern programs don't use the incremental form, but it's much faster. GJK is a very fussy algorithm numerically. The optimization involves subtracting large numbers and caring about small differences. Loss of significance due to underflow can be a problem, and can cause the termination condition to not terminate, with the optimization cycling between a few near-optimal solutions. The loss of significance problems show up as objects settle into parallel-face contact, which is why this algorithm tended to loop when put inside a physics simulation where objects settled. Passed tests with randomly oriented convex hulls all day. This was hard to fix. I had a hack solution that detected cycling, and Prof. Stephen Cameron at Oxford finally fixed the numerical math to behave.[2] (You can get his code from his web site, there's a substantial license fee for commercial use, and he died years ago. I licensed the code back in the 1990s, but can't sublicense or release it. If someone really wants it, they'll need to find his heirs and negotiate.) You also need "good" convex hulls. Your options are hulls with polygonal faces that won't be perfectly flat due to numerical precision limits, or hulls with triangular faces that are sometimes coplanar. Using a convex hull generator which can enforce a minimum break angle of about 1 degree, with polygonal faces, seems to work best. Now there's OpenGJK.[3] Haven't looked at that. Hopefully they've dealt with all these problems. I was doing this back in the stone age of game physics, when nothing worked out of the box. [1] https://www.youtube.com/watch?v=5lHqEwk7YHs https://www.youtube.com/watch?v=5lHqEwk7YHs [2] https://www.cs.ox.ac.uk/stephen.cameron/distances/ https://www.cs.ox.ac.uk/stephen.cameron/distances/ [3] https://github.com/MattiaMontanari/openGJK https://github.com/MattiaMontanari/openGJK
- dundarious 3mo ago
- freecook 3mo agouseful
- animal531 3mo agoMy favourite is probably Bepuphysics due to its C# nature: https://www.youtube.com/watch?v=tjtwSq3u6Dg https://www.youtube.com/watch?v=tjtwSq3u6Dg Unfortunately it was created before Unity could use vectorization and other C# engines were just starting out as well. The source, a great resource for learning C# SIMD, even though its a few years old by now: https://github.com/bepu/bepuphysics2 https://github.com/bepu/bepuphysics2
- Rohansi 3mo ago> Unfortunately it was created before Unity could use vectorization It still can't unless you use Unity's Burst compiler. You're not going to be able to use bepuphysics2 in Unity because it was written for standard C#.
- animal531 3mo agoUnity has begun to roll out CoreCLR in beta now which is a move from Mono to modern .NET 10. The official release and LTS versions are still some months out though.
- Rohansi 3mo agoThat's true but I haven't seen word from them on what is changing with IL2CPP. They've already confirmed that there are no plans to use CoreCLR's superior GC in IL2CPP so they could also just not support the intrinsics so it falls back to scalar operation. IL2CPP support is an important detail because many of the platforms Unity targets only work with IL2CPP and Unity recommends IL2CPP for release builds on the rest.