Simulation Parallelization | Steam Revolution Game Devlog #9
Vložit
- čas přidán 6. 06. 2024
- In this video I talk about how I parallelized the simulation code in my game Steam Revolution. I measured accumulated times after running 1M simulation ticks. This makes the math nice so that the number of seconds taken equals the number of microseconds per simulation tick. In the world map with 214 trains, parallelizing my code made the time go from 43.2 s to 17.7 s on my computer, a 2.4x speedup.
Speeding up the simulation via multi-threading is challenging for a few reasons.
1. The duration of each simulation step is very short, so the overhead of parallelization is difficult to overcome. Each simulation step is also composed of multiple interdependent stages that further reduce the time per parallel section. There are 6 parallel steps per tick, in 43 us (7 us per step).
2. The simulation is not trivially parallelizable, because trains interact with each other and with shared resources such as sections of track and industries.
3. Results of the simulation must be deterministic and identical between serial and parallel versions. Re-running a simulation should give the same score every time to make playing the game fun. Also, server verification of results requires the server and client results to match.
I will give an in-depth description of the challenges to making each part of the simulation parallel and the strategies I used to overcome them. Although I’m specifically describing my solutions to my problems, they may provide inspiration for parallelizing your own code.
My game is a blend of OpenTTD and Zachtronics games like SpaceChem or Infinifactory. Compared to other train games, my game's focus is more on optimizing static levels for good scores rather than showing how a transportation empire progresses over time. In this series I document my progress developing a game from scratch with no pre-made engine; one could call it handmade.
Timestamps:
00:00 - Intro
03:10 - Overview of game
03:48 - Benchmark hardware
05:20 - Benchmark times
09:10 - Simulation overview
11:40 - Benchmark simulation steps
13:35 - Overhead sources
21:38 - Update track occupancy
23:12 - Propose location
28:55 - Wait and cargo
39:30 - Commit movement
42:45 - Collision detection
44:38 - Add cars and trains
45:16 - Update industries
45:48 - Cargo loaders
47:32 - Remove smoke
47:55 - Update game state
48:35 - Revisit timings
50:55 - Conclusion - Hry
Good video, interesting how multi track train networks and signals are a convenient analogy for code parallelization and concurrency
Hooray! More really informative content, stuff that makes sense and is actually useful!
Interesting programming information and a train game. I'm going to subscribe to follow along with. :)
Nice technical video! Always a pleasure learning about how you overcome challenges
Pretty cool content!
I do have a question:
Have you tried batching modifications of shared state? Especially cases like spawning puffs of smoke and noises seem like they should be trivially changeable to storing them in a local list in the thread first, then locking the global list if any were created and just shoving either the list object or each element of the local list into it.
It may be benefitial because it means you only need to lock/atomically insert at most once per worker, or totally worse because of the extra code and copies, so I'd love to hear if you have benchmarked this!
Good question. I think I mentioned in the video, but the sounds actually are already batched per train over several simulation ticks and are consumed by the main thread during the render update. So, sounds have no locks during the simulation.
For smoke puffs I could have done the same thing, but it doesn't cost much performance as it is since the puffs aren't generated all that often (like maybe 1 in 10 frames and only if a train is moving). So, it barely shows up in profiling, a quick test just now showed 0.143 s out of a total 18.344 s run time was spent acquiring the smoke lock. But you are right, that I could probably avoid that overhead.
Thanks for the suggestion. Maybe I will implement that.
I gave smoke puffs the same treatment as sounds. I store them only in the train now, and there is no reason to have a global array to collect the smoke in, because the renderer can directly use the train arrays.
I also removed the per-tick stage of the simulation where I remove smoke, because this only needs to happen once per rendered frame. At the fastest rate that is once per 1000 ticks, which also reduces overhead some. I also made my benchmarking code (that doesn't render) match that to remove finished smoke every 1000 ticks.
Rough timings of the best run over like 5:
17.68 before
17.13 after train smoke optimization
There is a variance of up to a second between timings, so it is hard to know precisely how much it helped, but it is clearly somewhat better by on the order of half a second.
I could in theory do similar for the cargo loaders, but since those affect the sim I will still need to touch them once per tick so the benefits won't be as large. I might try that next.
Nice to hear back the results!
Yeah, I didn't expect a big benefit out of the smoke spawning because it didn't seem like something that would happen too often, so I'm pretty amazed if it really is half a second in the end. I mainly mentioned it because this is a common technique in entity component systems to allow multithreaded systems to spawn new entities.
You could probably use it in other steps of your simulation, but once one needs more than "many threads create values for one accumulation without order" you may need to add a serial fixup step or something like that, so the smoke seemed like low hanging fruit!
And on the audio, you may have mentioned it, I mainly listened to the video over two days when I ate or was on break so I don't remember all the details 😅.
@@Kanonenwind Ya, I wouldn't expect you to remember every detail. I think the main benefit from the smoke change was not about the locking, but about my being able to skip the step in most sim ticks and do a big batch update every 1000 ticks. Most ticks there is no change in state for the smoke puffs, so repeatedly processing them was wasteful. Also there is no harm in letting smoke remain in the array past its expiration so skipping the tick it should be removed is safe.
These things aren't true for cargo loaders, so I don't expect anywhere near the same benefit.
3:10 The logo has a typo "Steam Revloution" lol
lol. oops. thanks for catching that!
Typos increase engagement!
Ireland!!!!!
What game is this ?
It is a game I am working on as my hobby, called Steam Revolution.
@@josiahmanson I love how you have a deep understanding a parallel processing and parallel programming and simulation. I have the same it is so hard to teach in a YT video. but you did a great job.
Where can.I download your software?
@@lynnwilliam Thanks for the compliment and your interest. The game hasn't been released, so isn't available for download yet.
@@josiahmanson can you setup maybe a reddit subreddit and link that in all the YT videos about this? Would love to hear what other programmers think. What you are doing is amazing by the way,
@@lynnwilliam That is a good suggestion. I'll have to consider it.