Difference between revisions of "Garbage Reduction"

From Kerbal Space Program Wiki
Jump to: navigation, search
(Eliminated untrue and misleading advice re: short lived variables.)
(Reordered sections)
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
''Some of this information may be incorrect, speculative or out of date. Unity provides an [https://unity3d.com/learn/tutorials/topics/performance-optimization/optimizing-garbage-collection-unity-games in-depth tutorial] with more up to date and accurate information. As of version 1.4, Kerbal Space Program runs on Unity 2017.1, which, for example, reduces the concern about foreach loops (problematic for Unity versions before 5.5). All advice is situational and the largest source of garbage collection issues in most user made plugins will be lack of/poor design.''
 
''Some of this information may be incorrect, speculative or out of date. Unity provides an [https://unity3d.com/learn/tutorials/topics/performance-optimization/optimizing-garbage-collection-unity-games in-depth tutorial] with more up to date and accurate information. As of version 1.4, Kerbal Space Program runs on Unity 2017.1, which, for example, reduces the concern about foreach loops (problematic for Unity versions before 5.5). All advice is situational and the largest source of garbage collection issues in most user made plugins will be lack of/poor design.''
  
==What is garbage, and why is it bad?==
+
== Memory Allocation and Garbage Collection ==
  
C# is a garbage-collected language, which means that the programmer doesn't have to worry about deleting variables when done with them; the system will do it automatically.
+
KSP and its mods run in a managed runtime, which means that the programmer doesn't have to worry about allocating and deallocating memory directly when creating objects. The runtime will do it automatically.
  
However, the way it does this is by freezing the system and then walking through the list of variables and removing the unused ones ("garbage" variables). This can cause stutters, and the stutters will be more frequent and longer the more garbage there is.
+
This does not mean that the programmer can ignore these concerns entirely, however. It is useful to note that there are two basic types of allocation in this runtime: stack allocations and heap allocations. Stack allocations are used for value types (most simple primitives with a fixed width) and references to structures (simple data containers that also have a fixed width) [http://content.atalasoft.com/h/i/58208059-improving-performance-through-stack-allocation-net-memory-management-part-2 Improving performance through stack allocation] goes into greater detail on stack allocation. Heap allocations are used for everything else and these are the allocations that will be managed through garbage collection.
  
==Measuring garbage production==
+
Garbage collection can have large impacts on gameplay because the runtime needs to stop executing code (which could allocate and deallocate more memory, creating a moving target) while it scans allocated objects looking for those that can no longer be accessed. One common strategy for optimizing this garbage collection is to use a generational GC. This means that as objects survive rounds of garbage collection, they move to older generations and are scanned differently. They also become more expensive to deallocate as they move into older generations and these generations have an outsized impact on memory fragmentation (because it's more likely new allocations will have to be made "around" them). The frequency with which garbage collection will be triggered and how long this process takes will be tied not only to how many objects are allocated and their size, but also how they are allocated. The result of these factors when programming within a game or mod where users will be sensitive to pauses and stuttering is that it can be beneficial to code in a way that allocates new memory efficiently.
[http://forum.kerbalspaceprogram.com/index.php?/topic/139128-113-memgraph-10010-with-stutter-reduction/ MemGraph] can show you how much garbage KSP is creating. It is not broken down by mod, so to test a specific mod you'll need a copy of KSP with only that mod installed.
 
 
 
== What does Squad say about garbage?==
 
 
 
[http://kerbaldevteam.tumblr.com/post/146620984599/devnote-tuesday-smashing-buttons "removing old foreach() loops, Singletons and generally de-linqing the game. We recommend that modders to the same in anticipation of the next update to help increase performance for all KSP players. Linq and foreach() loops in particular create a lot of garbage, which is what causes the stutter that some people experience while running the game."]
 
  
 
==Best practices to avoid creating garbage==
 
==Best practices to avoid creating garbage==
  
===avoid foreach===
+
=== foreach ===
Replace "foreach" with "for".
+
Use of the foreach loop introduces overhead, especially in previous versions of unity (prior to 5.5, KSP 1.4 updated to Unity 2017.1). Traditional for loops can save the allocation of an enumerator object in certain cases and execute slightly faster at times because they can omit a method call (which may or may not be inlined depending on the situation).
  
Less garbage, but goes through the list backwards:
+
In modern Unity development, this advice is highly situational, however. To illustrate, some code from the [https://github.com/UbioWeldingLtd/UbioWeldContinued UbioWeldContinued mod]:
 
<syntaxhighlight>
 
<syntaxhighlight>
for (int i = <something>.Length - 1; i >= 0; --i)
+
string[] breakingAttributes = new string[newModule.values.DistinctNames().Count()];
</syntaxhighlight>
+
for (int i = 0; i < newModule.values.DistinctNames().Count(); i++)
 
+
{
One extra variable, but goes through the list forwards:
+
    breakingAttributes[i] = string.Concat(newModuleName, Constants.underline, newModule.values.DistinctNames()[i]);
<syntaxhighlight>
+
}
int count = <something>.Length; // (or .Count or whatever works for the object concerned)
 
for (int i = 0; i < count; ++i)
 
 
</syntaxhighlight>
 
</syntaxhighlight>
 
+
Here, the use of linq and piecemeal string manipulations are not the biggest performance issue. The biggest issue is the repeated expression `newModule.values.DistinctNames()[i]`. Not only is it possible for an attribute like `values` to create a new container (list, array, etc.) to return each time it is called, calling `DistinctNames` over and over in the for loop and then indexing into it to retrieve one item is going to create and immediately discard collections of objects for no gain. In this case, a coding style that prefers `foreach` and evaluates performance critical sections of code for possible improvements would have been significantly better.  This is a great example of how indexing into some collection over and over can introduce unintended allocation and performance consequences.
If you're using Visual Studio instead of MonoDevelop, replacing foreach is not strictly necessary in some cases:
 
 
 
"foreach" can be ok in Visual Studio [http://forum.kerbalspaceprogram.com/index.php?/topic/7542-the-official-unoffical-quothelp-a-fellow-plugin-developerquot-thread/&do=findComment&comment=2677079 "if the GetEnumerator function of the object you are doing it on returns a struct type. If it returns a class type or an interface then it will cause garbage with any compiler.  System classes like List<T> do return a struct but some of the KSP classes that are basically a wrapper around a List<T> return an interface (e.g. PartResourceList).  These are on the list for fixing for KSP 1.2 though with that sort of nesting, you will probably get better performance with plain for loops (using foreach also requires the code to make two function calls to the enumerator object every time around the loop)."]
 
  
 
[http://forum.kerbalspaceprogram.com/index.php?/topic/148448-12pre-gravityturn-continued-automated-efficient-launches/&do=findComment&comment=2779177 "You don't need to convert all your foreach loops into plain for loops unless the thing being enumerated happens to return an interface or class from GetEnumerator (even Squad no longer *need* to avoid foreach because Unity have updated the included compiler to fix the issue)."]
 
[http://forum.kerbalspaceprogram.com/index.php?/topic/148448-12pre-gravityturn-continued-automated-efficient-launches/&do=findComment&comment=2779177 "You don't need to convert all your foreach loops into plain for loops unless the thing being enumerated happens to return an interface or class from GetEnumerator (even Squad no longer *need* to avoid foreach because Unity have updated the included compiler to fix the issue)."]
  
However if you want a hard and fast rule, "don't use foreach" is pretty simple.
+
=== Singletons ===
===avoid Singletons===
 
  
No info on this.
+
Singletons are often designed to survive the life of the program's execution. This long life means they may hold references to objects long after they are useful which can result in the objects never being released (a memory leak), surviving long enough that they have to be considered by the garbage collector in a more expensive generation (slowing GC over time), or deallocated after a similar set of objects has been allocated in another spot on the heap (memory fragmentation). It is therefore important to carefully evaluate the objects a singleton can reference. This can include more than the immediate attributes of the singleton, i.e. those attributes may hold references to other objects.
  
===remove "using System.Linq"===
+
=== LINQ ===
  
Linq creates a lot of garbage. Don't use it.
+
Use of LINQ over traditional looping control structures introduces similar overhead as a foreach loop. If you identify performance critical sections of code, repeated or deeply nested LINQ expressions are worth looking at. On the flip side, using LINQ methods in cases where an effective algorithm is necessary to perform the operation efficiently is a good practice. Sorting, grouping, finding distinct items, and even flattening require choosing and implementing an effective algorithm which increases the probability of bugs, incorrect algorithm choice, or poorly implemented algorithms. Implementing these algorithms by hand is probably best left to algorithm experts and even then, only on the most performance critical code (code that executes every frame).
  
 
[http://forum.kerbalspaceprogram.com/index.php?/topic/7542-the-official-unoffical-quothelp-a-fellow-plugin-developerquot-thread/&do=findComment&comment=2677132 "the quickest way to check if you are using Linq is to delete that using line if it's there. Then everything with Linq will have errors. And there are many more things other than the From, Select that use Linq; lots of methods that are used to modify or specify certain members of a list use it, like Any, OfType, Where, First, FirstOrDefault, etc..."]
 
[http://forum.kerbalspaceprogram.com/index.php?/topic/7542-the-official-unoffical-quothelp-a-fellow-plugin-developerquot-thread/&do=findComment&comment=2677132 "the quickest way to check if you are using Linq is to delete that using line if it's there. Then everything with Linq will have errors. And there are many more things other than the From, Select that use Linq; lots of methods that are used to modify or specify certain members of a list use it, like Any, OfType, Where, First, FirstOrDefault, etc..."]
Line 70: Line 59:
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
 +
== Measuring garbage production ==
 +
[http://forum.kerbalspaceprogram.com/index.php?/topic/139128-113-memgraph-10010-with-stutter-reduction/ MemGraph] can show you how much garbage KSP is creating.  It is not broken down by mod, so to test a specific mod you'll need a copy of KSP with only that mod installed.
 +
 +
== What does Squad say about garbage? ==
 +
 +
[http://kerbaldevteam.tumblr.com/post/146620984599/devnote-tuesday-smashing-buttons "removing old foreach() loops, Singletons and generally de-linqing the game. We recommend that modders to the same in anticipation of the next update to help increase performance for all KSP players. Linq and foreach() loops in particular create a lot of garbage, which is what causes the stutter that some people experience while running the game."]

Latest revision as of 22:24, 14 June 2018

Some of this information may be incorrect, speculative or out of date. Unity provides an in-depth tutorial with more up to date and accurate information. As of version 1.4, Kerbal Space Program runs on Unity 2017.1, which, for example, reduces the concern about foreach loops (problematic for Unity versions before 5.5). All advice is situational and the largest source of garbage collection issues in most user made plugins will be lack of/poor design.

Memory Allocation and Garbage Collection

KSP and its mods run in a managed runtime, which means that the programmer doesn't have to worry about allocating and deallocating memory directly when creating objects. The runtime will do it automatically.

This does not mean that the programmer can ignore these concerns entirely, however. It is useful to note that there are two basic types of allocation in this runtime: stack allocations and heap allocations. Stack allocations are used for value types (most simple primitives with a fixed width) and references to structures (simple data containers that also have a fixed width) Improving performance through stack allocation goes into greater detail on stack allocation. Heap allocations are used for everything else and these are the allocations that will be managed through garbage collection.

Garbage collection can have large impacts on gameplay because the runtime needs to stop executing code (which could allocate and deallocate more memory, creating a moving target) while it scans allocated objects looking for those that can no longer be accessed. One common strategy for optimizing this garbage collection is to use a generational GC. This means that as objects survive rounds of garbage collection, they move to older generations and are scanned differently. They also become more expensive to deallocate as they move into older generations and these generations have an outsized impact on memory fragmentation (because it's more likely new allocations will have to be made "around" them). The frequency with which garbage collection will be triggered and how long this process takes will be tied not only to how many objects are allocated and their size, but also how they are allocated. The result of these factors when programming within a game or mod where users will be sensitive to pauses and stuttering is that it can be beneficial to code in a way that allocates new memory efficiently.

Best practices to avoid creating garbage

foreach

Use of the foreach loop introduces overhead, especially in previous versions of unity (prior to 5.5, KSP 1.4 updated to Unity 2017.1). Traditional for loops can save the allocation of an enumerator object in certain cases and execute slightly faster at times because they can omit a method call (which may or may not be inlined depending on the situation).

In modern Unity development, this advice is highly situational, however. To illustrate, some code from the UbioWeldContinued mod:

string[] breakingAttributes = new string[newModule.values.DistinctNames().Count()];
for (int i = 0; i < newModule.values.DistinctNames().Count(); i++)
{
    breakingAttributes[i] = string.Concat(newModuleName, Constants.underline, newModule.values.DistinctNames()[i]);
}

Here, the use of linq and piecemeal string manipulations are not the biggest performance issue. The biggest issue is the repeated expression `newModule.values.DistinctNames()[i]`. Not only is it possible for an attribute like `values` to create a new container (list, array, etc.) to return each time it is called, calling `DistinctNames` over and over in the for loop and then indexing into it to retrieve one item is going to create and immediately discard collections of objects for no gain. In this case, a coding style that prefers `foreach` and evaluates performance critical sections of code for possible improvements would have been significantly better. This is a great example of how indexing into some collection over and over can introduce unintended allocation and performance consequences.

"You don't need to convert all your foreach loops into plain for loops unless the thing being enumerated happens to return an interface or class from GetEnumerator (even Squad no longer *need* to avoid foreach because Unity have updated the included compiler to fix the issue)."

Singletons

Singletons are often designed to survive the life of the program's execution. This long life means they may hold references to objects long after they are useful which can result in the objects never being released (a memory leak), surviving long enough that they have to be considered by the garbage collector in a more expensive generation (slowing GC over time), or deallocated after a similar set of objects has been allocated in another spot on the heap (memory fragmentation). It is therefore important to carefully evaluate the objects a singleton can reference. This can include more than the immediate attributes of the singleton, i.e. those attributes may hold references to other objects.

LINQ

Use of LINQ over traditional looping control structures introduces similar overhead as a foreach loop. If you identify performance critical sections of code, repeated or deeply nested LINQ expressions are worth looking at. On the flip side, using LINQ methods in cases where an effective algorithm is necessary to perform the operation efficiently is a good practice. Sorting, grouping, finding distinct items, and even flattening require choosing and implementing an effective algorithm which increases the probability of bugs, incorrect algorithm choice, or poorly implemented algorithms. Implementing these algorithms by hand is probably best left to algorithm experts and even then, only on the most performance critical code (code that executes every frame).

"the quickest way to check if you are using Linq is to delete that using line if it's there. Then everything with Linq will have errors. And there are many more things other than the From, Select that use Linq; lots of methods that are used to modify or specify certain members of a list use it, like Any, OfType, Where, First, FirstOrDefault, etc..."

don't loop through all Parts/Resources/whatever every frame

Looping through every part on the ship is expensive. Don't do this every frame, but instead get notified when the ship changes and then re-scan it. Same for resources, or anything else that you can cache and then get notified when you need to act.

List<Part> partsICareAbout = new List<Part>();
 
Start()
{
  rescanMethod(); // run this at startup
 
  GameEvents.onVesselChange.Add(rescanMethod);
  // onVesselChange - switching between vessels with [ or ] keys
 
  GameEvents.onVesselStandardModification.Add(rescanMethod);
  // onVesselStandardModification collects various vessel events and fires them off with a single one.
  // Specifically - onPartAttach,onPartRemove,onPartCouple,onPartDie,onPartUndock,onVesselWasModified,onVesselPartCountChanged
}
 
public void rescanMethod(Vessel gameEventVessel=null)
{
  // scan the ship for the parts you need, and save them in partsICareAbout
}


Measuring garbage production

MemGraph can show you how much garbage KSP is creating. It is not broken down by mod, so to test a specific mod you'll need a copy of KSP with only that mod installed.

What does Squad say about garbage?

"removing old foreach() loops, Singletons and generally de-linqing the game. We recommend that modders to the same in anticipation of the next update to help increase performance for all KSP players. Linq and foreach() loops in particular create a lot of garbage, which is what causes the stutter that some people experience while running the game."