N-Body Simulation in C++: The Plan

What I’m Building and Why

Every programmer seems to have a ray tracer, a chip-8 emulator, or an N-Body simulator on their project bucket list. Guess it’s my turn to build an N-Body simulator.

An N-Body simulation is basically a physics sandbox that predicts the motion of many objects all pulling on each other with a force like gravity.

My real goal here is to finally get a proper handle on modern GPU programming and high-performance C++. An N-Body simulation is perfect because it’s easy to understand but incredibly difficult to make fast.

The $O(N^2)$ Problem

The most direct method is to calculate the interaction between every single pair of particles. This is called a brute-force approach.

The issue is that this is an $O(N^2)$ algorithm. Basically, if you double the particles, you quadruple the work. It gets slow, really fast.

The Different Approaches

There are a few ways to tackle this problem:

• Brute-Force ($O(N^2)$): As I said, it’s the simple but slow method. However, since the work is highly repetitive and parallel, it’s a great candidate to offload to a GPU.

• Barnes-Hut ($O(N \log N)$): A much smarter approach. It groups distant particles into clusters and treats each cluster as a single, larger particle. This is the main “clever” algorithm I want to compare against.

• Fast Multipole Method (FMM) ($O(N)$): This uses some pretty complex math to get even better performance. Honestly, implementing it correctly is a massive project in itself and so it’s out of scope for what I’m trying to do here.

So, The Main Question Is…

Can a modern GPU, with its thousands of cores, run a “dumb” brute-force algorithm so fast that it beats a CPU running a “clever” algorithm like Barnes-Hut?

Probably, the answer is that it changes depending on how many particles you have, and I want to find out where that point is.

The Game Plan

Here’s how I plan to tackle this:

1. Get It Working: First, a simple, single-threaded version in C++ that runs on the CPU. The main goal here is to make sure the physics is actually correct before trying to optimize anything.

2. Add CPU Parallelism: Take the working code and speed it up using Intel’s TBB (Threading Building Blocks) to run across multiple CPU cores.

3. Move to the GPU: Port the brute-force calculation to CUDA to run on the GPU. This is where I expect to see the first big performance jump.

4. The AoS vs. SoA Showdown: Once on the GPU, I’ll test a classic optimization: Array of Structures (AoS) vs. Structure of Arrays (SoA) to see what the performance difference really is.

5. Build Barnes-Hut: Finally, I’ll implement the Barnes-Hut algorithm on the CPU. This will be the final piece needed to compare it against the optimized GPU version and answer the main question.

Checklist

This is the checklist of questions I want answers to by the end of this project:

• How much faster is the multi-threaded CPU code than the single-threaded version?
• What’s the real speedup of the GPU brute-force over the best CPU brute-force?
• Does SoA provide a trivial or a massive performance boost over AoS?
• Where is the crossover point? At 10k, 50k, or 100k+ particles?

The Tech Stack

• Language: C++23
• CPU Parallelism: Intel TBB
• GPU: NVIDIA CUDA
• Visualization: SDL3 (using its built-in renderer for now. My priority is the simulation logic, so I’m avoiding extra layers like OpenGL unless I really need them later.)

The Hardware

To keep the results consistent, I’ll be running all benchmarks for this project on the same hardware.

• GPU: NVIDIA GeForce RTX 5060 Ti
  • VRAM: 16 GB GDDR7
  • Compute Capability: 12.0 (Blackwell)
• CPU: AMD Ryzen 5 9600X (Zen 5)
  • Clock Speed: 3.9 GHz (Base) / 5.4 GHz (Boost)
  • Cores/Threads: 6 Cores / 12 Threads
• System Memory: 16 GB DDR5

What’s Next

By the next post, I’m hoping to build out the complete CPU implementation. The goal is to get it running first with a single thread, and then create a fully parallel version to maximize its performance before we move on to the GPU implementation.