scp-fs2open / scp-fs2open/fs2open.github.com
General proposal: A path forward on cache coherency
- Dominant language
- C++
- Stars
- 487
- Forks
- 184
- PR merge metrics
- PR metrics pending
Description
In recent years performance discussions have often led to the conclusion that our biggest CPU bottleneck is cache coherency/misses, especially in cases of people seeing their game slow down over extended play. My understanding is that this has two main likely sources:
* Linked lists make for lots and lots of jumping back and forth in memory when iterating over them, and iterating by following the *next pointers means the CPU can't just chew through the storage array from start to finish
* Very large structs exacerbate the first problem.
The #5121 PR is an effort to give us a way to start fixing this. That PR is in my estimation not very far from complete, but whole-hog implementing SCP_Pool storage and iteration everywhere is a titanic task, and there are challenges to trying to do the core object type arrays in steps due to how the instance index system works. Also currently accessing the pool objects strongly favors working in object references instead of pointers, so converting old logic can be somewhat noisy.
That said, once the pools are available I think there's things that can be done one at a time and move us gradually to a better place.
## Isolated conversions
Identify linked lists that have relatively limited code footprint and convert them wholesale to SCP_pools. Trails was one, objectsnd and lightning are possible others, and I'm sure there's more. Some places get kind of gnarly with pointer shenanigans so this isn't going to be trivial. In most cases we can't expect serious measurable performance savings from any one of these, but we can expect improved reference safety and if done right can seriously improve code clarity in spots.
## Linked list iterators
Writing a generic reference-providing iterator(such as that written for pools) for our linked lists and converting anywhere that iterates with the current macro based pattern:
`for (object *objp = GET_FIRST(&obj_used_list); objp != END_OF_LIST(&obj_used_list); objp = GET_NEXT(objp))`
to use said iterator would probably make eventual adoption of pool storage for those cases a lot smoother.
## Isolate updating and iteration
Look for places where we can separate update functions. An example:
Right now ship_process post iterates through all ships. If the ship has damage lighting that lightning is updated, then if it has contrails those contrails are updated, then if it has engine washes those are updated. Each of these is either it's own SCP_Vector per ship or pointers into a linked list shared storage. If those storages don't all fit into cache then the CPU is going to be dumping and loading them in turn *for every ship*, which is pretty bad.
Instead, our ideal here is that each of these is an SCP_pool storage, and each has it's own frame update function. That update function would iterate over the particular piece involved, get data from the ship storage to do the updating that is currently done by the ship, and if the ship no-longer exists it would clean up those pool entries however is appropriate to them. Then we call those updates after the current ship update in the main loop.
Then the cache process would be that the ship storage is loaded, ships are all processed, then the damage lightning is loaded and iterated through with access to the ship storage on each iteration, then the contrails data is loaded and the damage lightning is not touched again that frame. Ships being a big huge linked struct in a linked list is still going to be a burden on cache access, but I think it would be no worse than current.
We should probably make sure accessing the primary storage in these new iterations is done in a way that is relatively painless to flip to accessing a pool in time, either a function small enough to be always in-lined or a macro or something.
As a bonus, if we can hit that pattern strictly then we actually can drop a lot of the arrays in the `ship` and similar structs, and probably shed many of the associated limits. If a ship's damage lightning is just an entry in a damage_lighting pool that will clean up after itself, and a ship can set it up and initialize it and never have to reference it again then we can drop all the info for current arc state from [ship] and make use of a global arc limit instead of a local one, for example
This is something I could potentially extend the pooled trails to do as a trial execution of to ensure practicality.
## Break up the big structs
This continues the trend of the above; find places where the current big structs can be split up and new single-topic structs can be isolated. This can extend to any data we only need part of the time, like we potentially could have a ship_ets_info struct and an index into it, there's probably enough time when we want to iterate over ships but don't care about ets state that this could be to our benefit.
This will depend on the structure of the code using these. For `ship` anything used in the nest we call AI code is going to be challenging to isolate I'm sure. We may want to prioritize things we can isolate as described above first, and that will hopefully free up some other parts as the number of things handled in the main iteration relaxes.
Once as much of this breaking up and isolating is done as possible, I hope it should be more manageable to convert the core `object` type lists and `objects` itself.
## Summary, caveats and pitfalls
If you're familiar with the [ECS design pattern](https://en.wikipedia.org/wiki/Entity_component_system) this is probably sounding familiar, and if you aren't then it's probably useful to give it a look. I'm not proposing we rebuild FSO as a full ECS engine, but many of the concepts and patterns are relevant here. And the way the `object` struct and it's subtypes fit together and get updated already some resemblance to ECS, so it's not a fundamentally alien direction to push the engine.
Two big problems are evident to me. First, ensuring stability of the engine and the gameplay while making these changes may prove challenging. Second, this gradual process is unlikely to be easily verified via benchmarking, and may even create some performance regressions in the short term before significant gains appear, especially in the isolation and breakup processes. Our big data structures are relatively speaking really big, and jumping around them them while updating other storages may only be a net gain after several iterations of this process.
And I don't think we can really make this a single branch off to one side while we work on it until it proves fruitful. It's going to touch everywhere, unless development of everything is frozen it would mean likely years of trying to merge in changes to dramatically overhauled code in places, even the handful of changes I need to merge into the trails branch now is a bit much.
I'm reasonably confident it'd be worth it, but it's not something I can undertake alone or even promise continual contribution to. If we're all on board with it as a goal and try to work it in here and there, it might be achievable and a chance to really fundamentally improve the engine, so I would love to have everyone's input on it.
(edit1: added a paragraph on ECS)
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.