CollisionManager performance when new vessels are created.

[BrettRyland]

As part of the on-going development of BDArmory, I was profiling KSP while launching a series of 12 missiles from standard BDA+ missile rails on a vessel. As can be seen from this image,

each launch causes a large spike in the frame duration due to the CollisionManager and involves a large amount of small GC allocations. The size of these spikes gets significantly worse the more vessels (with part counts on the order of 50—100 parts) that are in play (in the above image there were 6 vessels, but only one was firing). During combat with vessels of >100 parts, I've seen instances where the CollisionManager takes over 1000ms (of a 1200ms frame) whenever missiles are launched / new vessels are created (it doesn't need to be missiles, the same spikes are seen when just decoupling parts).

Is this something that the KSPCommunityFixes team could take a look at and maybe improve?

[gotmachine]

Did a bit of additional profiling :

The GetAllVesselColliders method is responsible for all the GC allocs and could be vastly optimized, but as you can see, it is responsible for a tiny fraction (< 1%) of the overhead.

The UpdatePartCollisionIgnores method is made of 6 nested loops and is basically a O(n²) operation (actually O(n*(n-1)/2)), where n is amount of loaded parts colliders. Decoupling a single part from a 450 parts vessel made of 985 colliders, this result in around 480000 iterations where every collider is checked against every other.

The purpose of that method is to set the physics state of colliders to avoid vessel parts from colliding which each other, done by a call to Physics.IgnoreCollision(Collider collider1, Collider collider2, bool ignore). Each collider pair needs to be set, and it seems to me the method is doing the minimal amount of iterations to achieve that.

So in short, the cost of the operation is exponentially worse with the loaded part count, and there isn't much that can be done to avoid it...

I guess we could look at micro-optimizing the loops. Not very reliable profiling show that the native call overhead to Physics.IgnoreCollision is significant, something like 15-30% of the operation, but that leave some headroom for optimization.

A possible micro-optimization would be to avoid the comparison between Collider.attachedRigidbody properties (which have some native call overhead) :

collider.attachedRigidbody == collider2.attachedRigidbody

Those are likely quite impactful and could maybe be optimized away by replacing the object comparison by caching the instanceID of the rigidbodies in GetAllVesselColliders() and comparing those int ids in the loop.

Other potential optimizations could be to reimplement the data generated by GetAllVesselColliders() in a more efficient way than nested lists of classes, something like CPU cache friendly arrays of structures.

Might try to take a look at this, but in the end I doubt the cost of the operation can be reduced enough to make a significant change to the "decoupling something in a high part count environment will produce a quite perceptible hitch" situation.

[BrettRyland]

From what I saw, the spikes were worse when there were multiple vessels in play. Shouldn't the colliders between vessels that are already separate already have Physic.IgnoreCollision set and not require re-setting? If those are all getting set too, then restricting the colliders returned from GetAllVesselColliders() to only those of the vessel involved in the decoupling should be a significant performance improvement.

[gotmachine]

I don't see any significant difference when profiling the same 450 parts as one vessel or separated as 6 vessels.
Indeed there could be some optimization by avoiding checking the other vessels when decoupling/coupling is involved, but that would only cover the specific case of multiple vessels in loading range, and the implementation might be difficult, as the method is called in a generic, event-driven way with the context being lost, in situations where every collider on every vessel need to be iterated upon anyway.

[BrettRyland]

Well, for BDArmory combats, there are frequently 6 or more vessels in loading range (often more for those that like to do fleet combat) (the Physics Range Extender mod is used to increase the physics range), so for our usage, it would likely be quite a significant improvement.
As an alternative to overriding the method for the generic situation of vessels decoupling, would it be possible to explicitly call an alternate method that only operated on the affected vessel (typically, it's a single part detaching from a single vessel) and bypassed the generic call? (I'm not sure how difficult it would be to flag the event as already handled elsewhere.)

Thanks for looking into this, btw!

[gotmachine]

Anything is possible, but I would rather try to optimize the general case first before attempting complicated corner-case optimizations requiring behavior changes that are always prone to introducing insidious bugs and side effects.

[gotmachine]

Okay, dafter fiddling a bit, for my 450 parts test vessel I'm around 12ms vs 43ms for the stock method when benchmarking manually in a non-debug install. Need to do a few more tests to ensure there is no behavior change, but this sounds good enough to me.

On a side note, the stock method behavior is quite erratic in regard to how the "enable same vessel interactions" PAW option is treated when physicless parts are involved. Not really worth a fix IMO, especially since that would add back quite bit of overhead...

[BrettRyland]

That's great and very much appreciated!

[gotmachine]

Some profiling results (non-debug install, average over 100 calls) :

// 495 parts
[STOCK IMPL] 50.656 ms (setup = 0.909 ms)
[KSPCF IMPL] 15.248 ms (setup = 0.636 ms)
// 465 parts + 15 2 parts vessels
[STOCK IMPL] 49.741 ms (setup = 0.691 ms)
[KSPCF IMPL] 15.267 ms (setup = 0.650 ms)
// 990 parts
[STOCK IMPL] 195.696 ms (setup = 1.776 ms)
[KSPCF IMPL] 55.876 ms (setup = 1.564 ms)

So KSPCF is between 3 and 4 times faster than stock.

Doing some frame time profiling, when accounting for the 3-4 frames where some extra processing is done as a result of the decoupling action, when comparing the cost of the CollisionManager update vs the overall overhead on top of the baseline frame time, it is less than 5% for the 500 parts case, but still around 30-40% for the 1000 parts case, and this of course will scale exponentially worse with higher part counts.

I gave a more in depth look at the possibility of doing less work in the multiple vessels case, but this is very difficult as KSP is triggering the update from dozens of code paths. This would require a lot of careful stock code path analysis to make it work, and would break anyway if a plugin uses the mess of related public APIs. There are at least 5 public direct ways this can be triggered : GameEvents.OnCollisionIgnoreUpdate, Vessel.ResetCollisionIgnores(), Part.ResetCollisionIgnores(), Part.ScheduleSetCollisionIgnores(), CollisionManager.UpdateAllColliders(), and at least a dozen other indirect ways in various other methods. In the specific case of decoupling, I've seen the update being requested from at least 3 code paths, but many more in some cases (this is even triggered from some partmodules...)

[gotmachine]

Patch pushed in release 1.33.0