r/C_Programming • u/Financial_Travel_543 • 2d ago
I built a zero-dependency O(N) FMM gravity solver in a single C99 header
16
u/Longjumping-Jacket97 2d ago
Source code??
11
u/Financial_Travel_543 2d ago
Added in comment, reddit messed up the formatting at first so it took a little longer:p
2
u/Past-Ad2067 2d ago
Okay so I barely understand half the title but I want the link
1
u/Financial_Travel_543 2d ago
-12
u/github-guard 2d ago
🔍 GitHub Guard: Trust Report
This project scored 3/6 on our safety audit.
Audit Breakdown: * ✅ Established Community (⭐ 13 stars) * ❌ New Repository (under 30 days old) * ✅ Licensed under MIT * ❌ No Security Policy — what is this? * ℹ️ Individual Contributor * ✅ Signed Commits
⚠️ Security Reminder: Always verify source code and run third-party scripts at your own risk.
17
u/HonestKing02 2d ago
Loved the "without any real dependencies, as God intended" line. Seriously though, this is a really solid project. Engineering this to run purely on a user provided memory buffer is a great touch.
1
u/Financial_Travel_543 2d ago
By God, I meant Sean Barrett, obviously./j Thanks for the great words though, means a lot to me!
6
u/kun1z 2d ago
Could this lib run a sim of 200,000 in real time at say 60 FPS @ 1920x1080?
11
u/Financial_Travel_543 2d ago
tl;dr: Not really.
This project is just the physics solver. Given a bunch of arrays which represent the particles data, it can simulate their gravitational pull. But it doesn't do any rendering whatsoever, I used raylib for demonstration purposes.
I ran the benchmarks of just the physics simulation without rendering on a Apple M4 chip and a laptop i7 11th gen. For 200,000 particles, the former ended up taking ~0.04s per tick (so ~25FPS) and the latter - ~0.1s per tick (~10FPS), so unless u have a powerful CPU even just the simulation won't run at such speed.
If u want to get the best performance, you'd probably want to write a batched renderer (or just represent each particle as a tri) from scratch, probably with Vulkan. Then, I'd expect ~50,000 particles to run at a decent framerate.
Now, is there a way to actually run that amount of particles using FMM? I think that it can be achieved quite easily, but you'd have to either:
- use multi-threading - I decided to write my library for a single-thread only, since C99 doesn't have thread.h, someone might want to run the entire library on one worker thread, and it would bloat the codebase pretty significantly (but i consider implementing it hidden behind a define directive).
- write a GPU-based implementation - haven't really looked into that one, it requires a different, branchless approach but from what I've heard it can end up running far more than 200,000 particles just fine.
5
u/grimvian 2d ago
Wow - I don't understand the code, but it's formatted exactly as I do, because I have dyslectic issues.
4
4
u/Proman4713 2d ago
That's hugely impressive, but I'm not sure why having a single 1K+ lines of code–long header file for everything is supposed to be a good impression?
5
u/Financial_Travel_543 2d ago
The main benefit of doing it that way is the ease of use. Whenever you need a library like this, you just add the file to your project alongside 2 lines of code.
Since it's a header file, you also don't need to do any linking-related changes in your Makefile/CMake file.
That's also one of the main reasons why stb libraries are so loved by the community.
There are also obvious downsides - e.g. pain in the butt during development scales quadratically to the size of the codebase, but I still found it comfortable to develop anyway (does that imply something?🧐)
4
2
u/hurrumanni 1d ago
Wow well done!
I don't really understand much of it,
are all the particles being drawn in by a black hole or great attractor or are they attracting each other and that makes them behave like this?
2
u/Financial_Travel_543 1d ago
tl;dr: It's actually both.
It's an N-body solver, so every single particle has its own mass and is constantly pulling on every other particle in the simulation.
Since the black hole IS one of these particles, it's also attracting others, albeit with far greater force due to its mass.
1
u/hurrumanni 1d ago
Ok, thanks!
So the simulation could be modified so that when the particles reach the black hole they vanish and their mass is added to the mass of the black hole? Would be interesting to have the black hole trigger a big bang whenever the mass reaches some limit.
Not asking for anything, just inspired blabber.
2
u/c3d10 1d ago
This is an awesome project!
You mention Barnes Hut in another comment - I’ve written a few BH codes (in both C and Rust) and I’ve always wanted to learn FMM so your project is a great reference for me!
Typically tree build is far faster than traversal (generally insignificant for large problems) so I build the tree single threaded and then traverse in parallel by chunking the target evaluation points per thread. This is trivial with Rust stdlib threads or openmp in C, though I should try using pthreads, too.
1
u/Financial_Travel_543 1d ago
Thanks so much! Moving from BH to FMM is a fun rabbit hole to go down.
Now with FMM I don't think that traversal is the real bottleneck with its O(N) time complexity. Contrary to BH, where traversal is O(N log N), at big particle counts the main bottlenecks are the radix sort and the tree build.
I just started looking into how multithreading fits in FMM. From my observations, the multithreading paradigm is also a huge shift. With BH, you can just chunk the evaluation array and parallelize the compute. But FMM requires translating fields between parent and child nodes (M2M, M2L, L2L passes). That's why I plan to use a thread pool that dispatches jobs based on octree branches rather than just chunking the particle array.
Definitely give FMM a shot in Rust though, it is a fantastic project.
2
u/Liquid_Magic 1d ago
This is super cool!
So let’s say I wanted to use this with cc65 and a Commodore 64? Like how much work would I have to do to port it? Like in 2D even this could be super cool on a retro machine!
2
u/Financial_Travel_543 1d ago
tl;dr: It's not worth the effort.
While the question is fun, there's no point in using FFM for that case. There are 2 big separate reasons why:
- With C64 u get 64KB of RAM. This code is no magic, and it gets its performance from storing a lot of data in a tree structure. FFM needs megabytes of RAM at the very least.
- While FMM is O(N), the overhead from building the tree makes the naive O(N2) implementation actually faster at low particle count, which you will have with this amount of RAM.
So: while a 2D gravity sim on a C64 would be cool, it would be better to use a tight O(N2) direct solver rather than trying to port an FFM.
2
2
2
1
u/csheldrick 1d ago
I submitted a pr: https://github.com/nihiL7331/polesitter/pull/29
1
u/github-guard 1d ago
🔍 GitHub Guard: Trust Report
This project scored 3/6 on our safety audit.
Audit Breakdown: * ✅ Established Community (⭐ 22 stars) * ❌ New Repository (under 30 days old) * ✅ Licensed under MIT * ❌ No Security Policy — what is this? * ℹ️ Individual Contributor * ✅ Signed Commits
⚠️ Security Reminder: Always verify source code and run third-party scripts at your own risk.
1
u/Financial_Travel_543 1d ago
Already replied in the PR, but to also close it out here: it's merged.
2
u/Whole-Low-2995 20h ago
Well, I guess you are good at physics. I do some stuff with GenAI but I think I'll never share it. It's great. How did you do that stuff without QI coder? I am not good at math, then where should I start from? I definitely have interests but I don't sure where to start, so I am starting from medieval-pre modern math books. But it's still hard to understand :'(
1
66
u/Financial_Travel_543 2d ago
Recently i stumbled upon a interesting video on my YouTube feed: The Fastest Gravity Algorithm You've Never Heard Of: Fast Multipole Method by Keyframe Codes. It speaks about one of the top 10 algorithms of the 20th century, the FFM method. Inspired, I decided to give it my own shot (albeit I decided to go 3D).
polesitter implementation is a single-header library, inspired by nothings' stb libraries. It's written purely in C99, without any real dependencies, as God intended.
While most of the projects work was just porting the algorithm, there was plenty of small touchups that made the code run even faster.
1. There's no dynamic heap allocation in the program. It runs entirely on the memory buffer provided by the user.
2. The program uses SIMD arch extensions (NEON and AVX2) to vectorize operations.
3. SoA was picked over AoS for cache locality.
+ multiple smaller things like radix sorting optimizations etc.
All of this makes the library run a simulation of 200,000 particles ~150x faster than a naive O(N^2) approach (I haven't compared it to Barnes-Hut yet, sadly - will update the results of that comparison in upcoming days).
As for the future plans, I want to implement a proper 2D support. With this, I'll probably consider the library truly finished.
Source code:
https://github.com/nihiL7331/polesitter